14
\$\begingroup\$

This is a solution for the June 2015 Community Challenge: a program that decrypts a monoalphabetic substitution cipher. It's written in Python 3, but should be portable to Python 2 if you use from __future__ import division.

Please review! Is the technique clear and the code easy to follow? Does the code correctly implement the algorithm? Can you recommend better names for functions and parameters? Would a different search technique (for example, simulated annealing, or beam search) be better?

The program has two main parts: a scoring function and a search function.

The scoring function evaluates the quality of a candidate decryption by computing the log-likelihood of the frequency of n-grams in the candidate, compared to a model corpus.

from collections import Counter
from math import log

def ngram_count(n, text):
    """Return the number of n-grams in text."""
    return len(text) - n + 1

def ngrams(n, text):
    """Generate the n-grams in text.

    >>> list(ngrams(3, 'HELLOWORLD'))
    ['HEL', 'ELL', 'LLO', 'LOW', 'OWO', 'WOR', 'ORL', 'RLD']

    """
    for i in range(ngram_count(n, text)):
        yield text[i:i+n]

def plaintext_score_function(n, corpus):
    """Return a function that scores a plaintext based on the
    log-likelihood of the occurrence of n-grams compared to those
    found in corpus.

    """
    # Number of n-grams in the corpus
    k = ngram_count(n, corpus)

    # Count of occurrences of each n-gram in the corpus.
    counts = Counter(ngrams(n, corpus))

    # Map from n-gram to the logarithm of its frequency in the corpus.
    log_freq = {ngram: log(count / k) for ngram, count in counts.items()}

    # Log-frequency to use for n-grams that don't appear in the corpus
    # (an arbitrary value that's much smaller than the log-frequency
    # for any n-gram that does appear in the corpus).
    min_log_freq = log(0.01 / k)

    def score(plaintext):
        return sum(log_freq.get(ngram, min_log_freq)
                   for ngram in ngrams(n, plaintext))
    return score

The search function uses the scoring function to guide a search for the best cipher using the hill climbing technique. Given a current best cipher, it considers swapping pairs of letters in the cipher and sees which (if any) of those swaps yield ciphers with improved scores. To introduce some randomness into the process (so that the search doesn't always end up stuck in the same dead end), it starts with a random cipher, and at each step it picks randomly among the ten best candidates.

from heapq import nlargest
from itertools import combinations
from random import choice, shuffle
from string import ascii_uppercase as LETTERS

def decipher(ciphertext, cipher):
    """Decipher ciphertext according to cipher, which must be an iterable
    giving a permutation of uppercase letters.

    >>> decipher('URYYBJBEYQ', 'NOPQRSTUVWXYZABCDEFGHIJKLM') # rot-13
    'HELLOWORLD'

    """
    return ciphertext.translate(str.maketrans(''.join(cipher), LETTERS))

def find_cipher(ciphertext, score_fun, initial=None, choices=10):
    """Attempt to decrypt ciphertext, using score_fun to score the
    candidate plaintexts. Return a tuple (score, cipher, plaintext)
    for the best cipher found.

    Keyword arguments:
    initial -- starting guess as to the cipher (if omitted, the search
               starts at a randomly chosen cipher).
    choices -- at each step, choose the next state in the search
               randomly from this many top candidates (default: 10).

    """
    if initial is None:
        initial = list(LETTERS)
        shuffle(initial)

    # Current best cipher and its score
    best_cipher = initial
    best_score = score_fun(decipher(ciphertext, initial))

    # List of all possible swaps of two letters in the cipher.
    swaps = list(combinations(range(len(LETTERS)), 2))

    def neighbours():
        # Yield neighbouring ciphers (those that differ from the
        # current best cipher by a single swap of letters) that are
        # better than the current cipher.
        for i, j in swaps:
            cipher = list(best_cipher)
            cipher[i], cipher[j] = cipher[j], cipher[i]
            score = score_fun(decipher(ciphertext, cipher))
            if score > best_score:
                yield score, cipher

    while True:
        try:
            best_score, best_cipher = choice(nlargest(choices, neighbours()))
        except IndexError:
            # No swap yielded an improved score.
            best_cipher = ''.join(best_cipher)
            return best_score, best_cipher, decipher(ciphertext, best_cipher)

Let's use the Project Gutenberg edition of War and Peace as our model corpus:

import re
corpus = re.sub('[^A-Z]+', '', open('pg2600.txt').read().upper())
score = plaintext_score_function(3, corpus)

and take the first ciphertext from the original problem description:

ciphertext = '''\
UXLIRNXSOPQAKJBJTXSVTJKRHXKKJKLIQQOEBLXRSNJKWQKQKYSAQKLRVQNLJKQD\
QRPLJRSEWIRSWQWJHQKTRKKQRWIXSODXNXJSNJTLIQBRNLLIXNXNUIRLXYSAQKLR\
VQLJAJTJKEJYKQRAQK\
'''

and see how it does:

>>> find_cipher(ciphertext, score)
(-1290.7855849944956, 'QUTHJYELRZPAVOXWCIKNSMBFDG',
 'BOHRITOUNKALSEWECOUMCESIDOSSESHRAANGWHOIUTESPASASFULASHIMATHESAY
  AIKHEIUGPRIUPAPEDASCISSAIPROUNYOTOEUTECHRAWITHHROTOTBRIHOFULASHI
  MAHELECESGEFSAILAS')

Not so good! But it starts with a random cipher, so we can try it several times and pick the best:

>>> max(find_cipher(ciphertext, score) for _ in range(10))
(-1100.5170945163568, 'RFWAQTOIXZVPDSJBMKNLYHUCEG',
 'WITHASINGLEDROPOFINKFORAVIRRORTHEEGYPTIANSORCERERUNDERTAKESTOREM
  EALTOANYCHANCECOVERFARREACHINGMISIONSOFTHEPASTTHISISWHATIUNDERTA
  KETODOFORYOUREADER')

Which is not quite correct, but it's easy now for the cryptanalyst to spot that M and V must be swapped.

\$\endgroup\$
4
\$\begingroup\$

The first code block, with ngram_count(), ngrams(), and plaintext_score_function(), seems straightforward enough. The docstrings and comments were all helpful.

Since we are dealing with logarithms,

  • log(count / k) could be log(count) - log(k), and log(k) can be precomputed. Subtraction should be faster than division, and it also happens to take care of your Python 2/3 compatibility problem.
  • min_log_freq is, for all practical purposes, PENALTY = -9999999.
  • Have you tried multiplying the frequencies rather than adding the logs of the frequencies? Does it make a difference in answer quality or performance?

In decipher() and find_cipher(), I'm not fond of the terminology. What you call the "cipher" is what I would call the "key".

The neighbours() closure makes this line a bit mysterious:

best_score, best_cipher = choice(nlargest(choices, neighbours()))

I would prefer to a more explicit iteration feedback loop:

score, key = choice(nlargest(choices, neighbours(score, key)))

But the (score, key) tuple appear frequently together, and you've repeated score_fun(decipher(…, …)), so I think there is room for improvement.

\$\endgroup\$
  • \$\begingroup\$ Sorry, the answer is kind of sketchy towards the end. Gotta run for now. \$\endgroup\$ – 200_success Jun 13 '15 at 0:26
  • \$\begingroup\$ 1. min_log_freq mustn't be too much of a penalty, because we expect that even a large corpus is missing some n-grams. War and Peace has about 2.5 million trigrams, so min_log_freq is about −19 in this case. 2. Multiplying frequencies quickly underflows the double-precision range: you'll see in the example output that even the best plaintext has a log-likelihood of around −1100, and exp(-1100) underflows to zero. \$\endgroup\$ – Gareth Rees Jun 13 '15 at 0:49
  • \$\begingroup\$ Otherwise, good points! \$\endgroup\$ – Gareth Rees Jun 13 '15 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.