Can't get implementation of hill climb algorithm for solving ciphers to work

user_11403 0
Viewed 308

I found a hill climb algorithm for solving monoalphabetic substitution ciphers in a paper and have tried implementing it in Python. The algorithm isn't really that complicated but I still can't get it to work. No meaningful results are generated even with very long ciphertexts, which according to the author should have a 90+ % success rate (i.e. 90% of letters correct compared to known plaintext). These are the results to expect according to the paper:

Percentage solved

This is the full description of the algorithm in pseudocode:

enter image description here

Assuming all the bits I import from functions are correct (this is actually a simple testcase from a much larger project where I have extensive tests for each function), can anyone spot any obvious errors in the code below?

(A full, self-contained version that you can run yourself is here.)

from collections import Counter
from string import ascii_lowercase

import numpy as np
from functions import _get_digram_frequencies, _get_plaintext, _score, _swap

ciphertext = (
    "uknkgmhksztkmexmpbxtgxesxekeskvuakgluepbhvpmhhpvxtwhphmvydmrbuthhgkfxgse"
    "xmpbhmeymhhohwgkzdwxenzfbhhlvabufbymkfhvnzehmihvkestuggvnhaupbshgurbpsxz"
    "xddeshmvpkespbuvthhguerpbuvymhhohabufbbkvpmkihgghstmxnpbhmhruxevpxakmsva"
    "bufbuknksikefuerruihvnhktxmhpkvphxtpbxvhufzfgunhvuevwumuphsyzpbuvauesxtw"
    "mxnuvhnzskzs"
)

print(f"\nCiphertext:\n{ciphertext}")

# Initial key is the letters in the ciphertext in order of most common first, and with
# remaining letters (not present in ciphertext) added at the end.
c = Counter(ciphertext)
key = [letter[0] for letter in c.most_common()]

for c in ascii_lowercase:
    if c not in key:
        key += c

print(f"\nInitial Key:\n{''.join(key)}")

# Algorithm starts here.

putative_plaintext = _get_plaintext(ciphertext, key)
digram_frequencies = _get_digram_frequencies(putative_plaintext)

best_score = _score(digram_frequencies)
print(f"\nInitial score is {best_score}")
print("Starting climb algorithm\n")

for i in range(1, 26):
    for j in range(26 - i):
        d = np.copy(digram_frequencies)
        _swap(d, j, j + i)
        score = _score(d)
        if score < best_score:
            digram_frequencies = np.copy(d)
            key[j], key[j + i] = key[j + i], key[j]
            best_score = score
            print(f"Got new best score {score:.02f} and key is now {''.join(key)}")

print(f"\nFinal Key:\n{''.join(key)}")

plaintext = _get_plaintext(ciphertext, key)

print(f"\nPlaintext:\n{plaintext}\n")
algorithm python
1 Answers

I finally solved this yesterday. The problem was that the digram matrices, both the constant English one and the one calculated from the ciphertext, were constructed using alphabetical order, meaning element (0, 0) for "aa", (0, 1) for "ab" and so on. This would not work since the initial key is in most common order, and the equivalence of the matrix swaps and key swaps is only valid if they match up to begin with. So the correct order to use for the digram matrices is most common in English first, meaning (0, 0) for "ee", (0, 1) for "et" and so on.

user_114030
Related