[Python] Problem Implementing Metropolis-Hastings Algorithm to Decrypt Substitution Cipher in...

So I tried to implement MCMC algorithm to decrypt mono-alphabetic substitution cipher as described in this paper.

The Algorithm:




Few things to note:

1. The symmetric density q: we get a new key by swapping two randomly selected letters in the current key.
2. The computation for score is done on log scale, and here is the scoring function (without log):
3. I use War and Peace by Leo Tolstoy as the reference text to compute the bi-gram frequency distribution.

My Attempt:

1. Some utility functions:

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" # global variable
import re
from collections import Counter

def clean_text(text):
return re.sub(r'[^A-Z]', '', text.upper())

def compute_bigram_counts(text, smoothing=1):
bigrams = [text[i:i+2] for i in range(len(text) - 1)]
counts = Counter(bigrams)
for a in alphabet:
for b in alphabet:
counts[a+b] += smoothing
return counts

def substitution_decrypt(ciphertext, key):
key = key.upper()
result = ""
for char in ciphertext:
if char.isalpha():
index = ord(char) - ord('A')
result += key[index]
else:
result += char
return result

1. MCMC algorithm implementation:

import math
import random
def compute_score(ref_counts, text):
score = 0.0
bigram_cipher_counts = compute_bigram_counts(ciphertext, smoothing=1)
for a in alphabet:
for b in alphabet:
score += bigram_cipher_counts[a + b] * math.log(ref_counts[a + b])
return score

def compute_proposed_key(key):
key_list = list(key)
i = random.randint(0, len(key_list) - 1)
j = random.randint(0, len(key_list) - 1)
key_list, key_list[j] = key_list[j], key_list
return ''.join(key_list)

def compute_mcmc(ref_counts, ciphertext, p, iter):
x = alphabet

for _ in range(iter):
y= compute_proposed_key(x)
pi_x = compute_score(ref_counts, substitution_decrypt(ciphertext, x))
pi_y = compute_score(ref_counts, substitution_decrypt(ciphertext, y))
u = random.random()

if u < p * (pi_y-pi_x):
x = y
return x

1. Example usage:

ciphertext = "YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ"
ciphertext = clean_text(ciphertext)
possible_key = compute_mcmc(bigram_counts, ciphertext, 1.0, 10000)
plaintext = substitution_decrypt(ciphertext, possible_key)
print(f"Ciphertext: {ciphertext}")
print(f"Output: {plaintext}")
print(f"Possible Key: {possible_key}")


Unfortunately, the output seems to suggest the key is not updated nor converged:

Ciphertext: YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ
Output: YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ
Possible Key: ABCDEFGHIJKLMNOPQRSTUVWXYZ


What am I missing here?

Continue reading...