A fairly fast Playfair program which I made will solve Stage 6 of the Singh Cipher Challenge in about 2 seconds on an 800 MHz PC (times ranging from 0.9 seconds to 3 seconds). Download source code (with an ms-dos executable) here.

This program works with the method of Simulated Annealing. It cannot guarantee a correct solution, but if it finds one it is very fast.

Fast Playfair Programs

Playfair ciphers can be solved by testing keys and computing how well the plaintext conforms to the target language: e.g. roughly The solution is found by testing various keys according to some scheme. The testing cannot be exhaustive; we don't have time to test 25! keys. It will surely lead to the solution; but it takes too much time. Shortcut methods (to be discussed) will take much less time, but cannot guarantee a correct solution. The dilemma becomes more pronounced as cryptograms get shorter.

One way to search the solution space is hillclimbing; start somewhere in the space, try small steps in various directions to proceed, choose the direction of the steepest way upward. Unfortunately this does not guarantee that we won't be stuck on a local maximum.

With Playfair, in particular, there are some interesting local maxima which correspond to particular symmetries of the keysquare. One program I made got stuck in a decryption which was almost right; while the true keysquare was, say (using a straight alphabet for clarity): 

     A B C D E
     F G H I K
     L M N O P
     Q R S T U
     V W X Y Z
the program reconstructed a keysquare 
     A F L Q V
     B G M R W
     C H N S X 
     D I O T Y
     E K P U Z
In other words, reflected with respect to a diagonal. The solution was almost right, in fact fairly understandable; but it is clearly not possible to move from the reflected keysquare to the true one in 'small' steps, e.g., by swapping of individual letter pairs, without disturbing the keysquare severely (thus reducing the score tremendously). The true square and its reflection represent local maxima. After I added "reflect keysquare" as an elementary operation to my program, its performance got a lot better.

Follow it so far? Then let's investigate this systematically.

There are three Playfair encoding rules, depending on how the plaintext letters are arranged in the keysquare:

There are eight reflection/rotation symmetries of a (key-)square. One conserves all rules (namely, doing nothing with the square), one breaks all three of the rules, and in fact to each combination of "rule 1, 2, or 3", either "broken" or "conserved", corresponds exactly one symmetry. Isn't that nice! Counting symmetries of the square in binary, using Playfair encryption rules as bits.

Here are the symmetries, labelled arbitrarily with the Roman numerals I - VIII. The top row shows the rotations by 90 degrees to the right, while the bottom row shows their top-to-bottom mirror images: 

      (I)         (II)         (III)        (IV)
   A B C D E    V Q L F A    Z Y X W V    E K P U Z
   F G H I K    W R M G B    U T S R Q    D I O T Y
   L M N O P    X S N H C    P O N M L    C H N S X
   Q R S T U    Y T O I D    K I H G F    B G M R W
   V W X Y Z    Z U P K E    E D C B A    A F L Q V

   
      (V)         (VI)         (VII)        (VIII)
   V W X Y Z    Z U P K E    E D C B A    A F L Q V
   Q R S T U    Y T O I D    K I H G F    B G M R W
   L M N O P    X S N H C    P O N M L    C H N S X
   F G H I K    W R M G B    U T S R Q    D I O T Y
   A B C D E    V Q L F A    Z Y X W V    E K P U Z

It is easy to verify that these symmetries have the following properties with respect to the Playfair encryption rules (1 means "rule conserved", and 0 means "rule broken"):

  I II III IV V VI VII VIII
Rule 1 1 0 1 0 1 0 1 0
Rule 2 1 1 0 0 1 0 0 1
Rule 3 1 0 0 1 0 0 1 1

("Rule 1 conserved" means that a particular symmetry of the keysquare has the property that the rule produces the same result as symmetry I (the unchanged square), for instance that AZ becomes EV. Likewise for rules 2 and 3.)

The first "local maximum symmetry" that I found by accident is symmetry VIII (a reflection about the top-left / bottom-right diagonal). No wonder its solutions are "almost readable": it conserves rules 2 and 3, and the "breaking" of rule 1 only means that the order of the components of a digram is swapped.

We can expect symmetries V and VII to likewise produce clear local maxima, because they break only one rule. So when looking for a global maximum, we should also include symmetries V and VII among the "small steps" we take during our search. They are reflections about a horizontal and about a vertical line, respectively. Symmetry VI, a reflection about the top-right / bottom-left diagonal, breaks all the rules, so we cannot expect it to produce decryptions looking at all like plaintext. Therefore it is not likely that a program will be "stuck" in it.
Back to Puzzles & Cipher Page