History of the Playfair Cipher

The Playfair cipher was created in 1854 by Charles Wheatstone. It was championed by Lord Playfair (hence the name) and used by Britain in the Boer War and both World Wars and also by Australia and New Zealand in World War II. It is said that it was rejected for use by the British Foreign Office due to its perceived complexity.

The first solution to the Playfair cipher was published by Lieutenant Joseph Mauborgne in 1914. It is no longer used since it is insecure.

Description of the Playfair Cipher

Key and Matrix

The Playfair cipher uses a 5x5 matrix of letters for encryption/decryption. The secrets in the Playfair cipher are a keyword and the method by which the 5x5 matrix is filled.

To fill the 5x5 matrix, first the keyword is written in the matrix using some pattern (left to right, spiral, etc.) ignoring repetitions of letters within the keyword. After the keyword has been written, the rest of the alphabet is written into the matrix in order following the set pattern. Since the entire alphabet cannot fit in the matrix (twenty-six letters for twenty-five slots), part of the secret is knowing if a given letter is to be dropped (typically J or Q) or if two letters will share a spot (typically I and J). For example, assume that the keyword is “COMMONLOUNGE” and that the matrix will be filled in from left to right across a row, in rows from top to bottom and that the letter Q will not be included. The resulting encryption matrix will be as follows:

Encryption

To encrypt a message with the Playfair cipher, it must be broken into sets of two letters or digrams. For each of these digrams, the following rules are applied.

1. If both letters are the same or only one letter remains (at the end of the message or a sentence within it), replace the second letter with an X and move to the next step.
2. If both letters are in the same row of the matrix, replace each with the letter to its right (wrapping around to the beginning of the row if necessary) and move on to the next digram
3. If both letters are in the same column of the matrix, replace each with the letter below (wrapping around to the top of the column if necessary) and move on to the next digram
4. If neither of the previous two rules are true, create a rectangle on the grid with the two letters at its corners. Replace each letter of the digram with the letter on the corner of the rectangle that is on the same row.

Example

As an example, let’s encrypt the phrase “Playfair Message” using the above matrix. First, the message is broken into digrams: PL AY FA IR ME SS AG E. Next, we apply the rules to the diagrams as follows:

• PL: Letters are in neither the same row nor column. The imaginary rectangle has corners at O, L, P, and T. Since T is in the same row as P, PL becomes TO.
• AY: Letters are in the same column and should be replaced by the letter below them. AY becomes IN.
• FA: Letters are in neither the same row nor column. The imaginary rectangle has corners at G, A, F, and I. Since I is in the same row as F, FA becomes IG.
• IR: Letters are in neither the same row nor column. The imaginary rectangle has corners at H, I, R, and S. Since H is in the same row as I, IR becomes HS.
• ME: Letters are in the same column and should be replaced by the letter below them. ME becomes EH.
• SS: Letters are repeated and are replaced with SX. S and X are in neither the same row nor column. The imaginary rectangle has corners at R, S, X, and Y. Since R is in the same row as S, SS becomes RY.
• AG: Letters are in the same row and should be replaced by the letter to their right. AG becomes BE.
• E: Only a single letter remains, so an X is added producing EX. E and X are in the same column and should be replaced by the letter below them. E becomes HM.

As a result of encryption with the Playfair cipher, PLAYFAIRMESSAGE becomes TOINIGHSEHRYBEHM.

Decryption

To decrypt with the Playfair cipher, the same matrix is used. In decryption, the reverse of the encryption operations are performed. These are as follows:

1. If both letters are in the same row of the matrix, replace each with the letter to its left (wrapping around to the beginning of the row if necessary) and move on to step 4
2. If both letters are in the same column of the matrix, replace each with the letter above (wrapping around to the top of the column if necessary) and move on to step 4
3. If neither of the previous two rules are true, create a rectangle on the grid with the two letters at its corners. Replace each letter of the digram with the letter on the corner of the rectangle that is on the same row.
4. If the second letter is an X, evaluate whether or not it makes sense to be an X based on context. If not, replace it with the first letter or drop it (if the last letter of the message)

Cryptanalysis of the Playfair Cipher

Long message

Similar to Substitution ciphers, the Playfair cipher can be attacked by means of a frequency attack. However, such an attack on a Playfair cipher is much more difficult since the Playfair cipher uses digrams rather than single letters (as used in most substitution ciphers). Rather than determining a mapping of twenty-six plaintext letters to ciphertext letters, attacking a Playfair cipher requires finding over six hundred mappings between pairs of digrams. This requires a much larger ciphertext to be effective since each digram must appear a sufficient number of times for a reasonable estimate of its relative probability of use to be computed (for example, if each digram appears only a few times in the ciphertext, the least probable diagram may appear the most simply by chance).

Short message

To break the Playfair cipher, it is necessary to reconstruct the encryption matrix. The number of possible matrices is roughly 25 factorial = 25! = 1 x 2 x 3 … 25. This assumes that rather than a key word, that a complete ordering of the 25 letters is used as a key. This is quite infeasible on a standard computer.

As mentioned previously, a standard frequency attack is difficult against Playfair ciphers with a short ciphertext. However, this performance can be improved by using the shotgun hill climbing method. This attack follows the following process:

1. Populate the matrix with a random permutation of the 25 letters
2. Decrypt using the current decryption matrix
3. Score the decryption based upon how well the decrypted ciphertext matches expected frequencies.
4. If the score passes a predefined threshold, have a human evaluate the plaintext for correctness. If it is incorrect, continue.
5. Transform the matrix using one of the following operations: reflection, rotation of a row, rotation a column, switching two letters.
6. Go back to step 2

Using this method, a computer has a reasonable probability of decrypting a Playfair cipher even if it has a short ciphertext. The procedure’s effectiveness can be increased further by repeating the entire process multiple times, which may lead to different results due to randomized steps in the process.