Playfair cracker - measure of best fit?
From: Rob Sullivan (cogito.ergo.cogito_at_gmail.com)
Date: 6 Aug 2005 04:05:51 -0700
I'm writing a Playfair cipher cracker (yes, I know there are several on
the internet), and I'm using a shotgun hillclimbing method. I basically
do the following:
1. Generate a random key.
2. Decrypt the ciphertext using the key, and score it against the
plaintext. This is done by taking the logarithms of the trigram
frequencies in standard English text and the ciphertext, and then
calculating the chi square statistic ( (O - E)^2 / E). Note that the
logarithms of the standard English text are only calculated once, and
then placed in an array - this is done at the beginning of the program.
3. Try some perturbations of the key - swap letters around, and so on.
Score the key for each perturbation.
4. If the score improves, check it against the global score. If it is
greater than the global score, output the key and start from another
5. If it is not, try a few other perturbations, and then start from
another random key.
The problem I'm having is with step 2 - compared to other Playfair
crackers, mine can only try a fraction of the keys tried by the other
programs in a given time. Is there a better statistic I can use, in
terms of appropriateness and efficiency?
The pseudocode for step 2 would be:
x = decrypt(ciphertext)
ciphertext_trigrams = get_trigrams(x)
for each element of ciphertext_trigrams:
ciphertext_trigram[element] = log(ciphertext_trigram[element])
score += ((ciphertext_trigram - plaintext_trigram)^2) /