[Note. This question has mild spoilers, but no answers, for a crossword puzzle in the May 2022 issue of The MagPie.]
In the puzzle, we are given a 52-character string. It is encrypted using Playfair, with a 9-letter English word as key. There are about seven thousand 9-letter English words with no duplicate letters [a requirement for Playfair], so it's easy enough to try them all. I now have seven thousand strings of 52 letters and I need to figure out which one is actually English text.
Based on other StackOverflow queries, my first thought was letter frequencies. The standard method for comparing two letter frequencies to see if they are similar is to take their normalized dot product. I used as a sample text some fiction from Project Gutenberg to be my "standard English text".
So I have:
from collections import Counter
from itertools import pairwise
import math
class Frequency:
def __init__(self, text):
# Playfair merges I and J into a single letter
text = [x for x in text.upper().replace("J", "I") if x.isalpha()]
# table of letter counts
self.table = Counter(text)
# length of the "vector" represented by this counter
self.length = math.sqrt(sum(v * v for v in self.table.values()))
def __matmul__(self, other): # might as well use @
# calculates the "cosine" between the two vectors using normalized dot product
assert isinstance(other, Frequency)
other_table = other.table
total = sum(value * other_table.get(key, 0)
for key, value in self.table.items())
return total / (self.length * other.length)
If I wanted to look at digrams, I would change the one line to be
self.table = Counter(pairwise(text))
and for trigrams:
self.table = Counter((i, j, k) for ((i, j),(_, k)) in pairwise(pairwise(text)))
My results for simple letter frequency were disappointing. With simple letter frequencies, the correct decryption came in 376th place in "looking like English". It had a score of .782, with the top score being .843.
Looking at both digraphs and trigraphs,
FEXLYRSITHEWACLWNTHECEEGXGLCEDEFONEOTALDYREGSUKUMAGR
looked more like English text to my program than the actual English text. For digraphs, it scored significantly better (.431 vs .400) and for trigraphs slightly better (.223 vs .222).
I'm sure that this is not the last time I'll need to recognize English text amidst gibberish, and I'm disappointed at how poorly this did. CLWNTH should have been clearly disqualifying.
Are there better algorithms?