# How does cryptanalysis of the Playfair cipher work?

I have a set of Playfair-enciphered data that I'm trying to crack without the key. I know I need to analyse bigrams; I've currently worked out what decrypts to th, er, in, and he, and have figured out where th and he are in the grid. However, now I'm stumped.

I've looked at the "Solution to Polygraphic Substitution Systems" field manual, but it didn't help. How do I complete the cryptanalysis of Playfair having a few bigrams decrypted and knowing where two of those go in the grid?

There are several algorithms available which can attack a Playfair cipher.

Hill climbing might be one option. Basically it starts with a random key (assuming it's the best one) and decrypts the cipher. The resulting clear text is scored using a fitness function. Then small changes are applied to the key and if the resulting clear text of the modified key scores better, the modified key is regarded as the best key and the process of applying small changes to the key starts over again until no better key can be found.

Sometimes Hill Climbing does not find the best solution, the algorithm gets stuck at a local maximum. An effective way to resolve this issue is to use the Shotgun hill climbing (refer to the Wikipedia link provided above).

It's not elegant, but the brute force method is to write a program that creates a table of 25x25 digraphs (assuming i=j), yielding 625 rows. I'd also add a column that lists the relative frequency of each digraph (given enough ciphertext you can use that to identify frequent substitutions, as you already have done). You start off with 625! possible solutions, but after identifying n digraphs this drops to (625-n)! But if the longest word in the language is N digraphs long, then take a 2N section and decode that (preferably use a section that already has some digraphs decoded). I'm thinking the overall complexity becomes picking something like $\frac{(625-n)!}{(625-2N-n)!}$