Playfair Cipher

Introduction §

The Playfair cipher was the first practical digraph substitution cipher. The scheme was invented in 1854 by Charles Wheatstone, but was named after Lord Playfair who promoted the use of the cipher. The technique encrypts pairs of letters (digraphs), instead of single letters as in the simple substitution cipher. The Playfair is significantly harder to break since the frequency analysis used for simple substitution ciphers does not work with it. Frequency analysis can still be undertaken, but on the 25*25=625 possible digraphs rather than the 25 possible monographs. Frequency analysis thus requires much more ciphertext in order to work. For a tutorial on breaking Playfair with a simulated annealing algorithm, see Cryptanalysis of the Playfair Cipher.

It was used for tactical purposes by British forces in the Second Boer War and in World War I and for the same purpose by the Australians during World War II. This was because Playfair is reasonably fast to use and requires no special equipment. A typical scenario for Playfair use would be to protect important but non-critical secrets during actual combat. By the time the enemy cryptanalysts could break the message the information was useless to them [1].

From Kahn's 'The CodeBreakers':

Perhaps the most famous cipher of 1943 involved the future president of the U.S., J. F. Kennedy, Jr. On 2 August 1943, Australian Coastwatcher Lieutenant Arthur Reginald Evans of the Royal Australian Naval Volunteer Reserve saw a pinpoint of flame on the dark waters of Blackett Strait from his jungle ridge on Kolombangara Island, one of the Solomons. He did not know that the Japanese destroyer Amagiri had rammed and sliced in half an American patrol boat PT-109, under the command of Lieutenant John F. Kennedy, United States Naval Reserve. Evans received the following message at 0930 on the morning of the 2 of August 1943:
KXJEY  UREBE  ZWEHE  WRYTU  HEYFS 
KREHE  GOYFI  WTTTU  OLKSY  CAJPO 
BOTEI  ZONTX  BYBWT  GONEY  CUZWR 
GDSON  SXBOU  YWRHE  BAAHY  USEDQ
    
The translation:
PT BOAT ONE OWE NINE LOST IN ACTION IN BLACKETT 
STRAIT TWO MILES SW MERESU COVE X CREW OF TWELVE 
X REQUEST ANY INFORMATION.
    
The coastwatchers regularly used the Playfair system. Evans deciphered it with the key ROYAL NEW ZEALAND NAVY [note that this is key square ROYALNEWZDVBCFGHIKMPQSTUX] and learned of Kennedy's fate. [...] About ten hours later, at 10:00 p.m. Kennedy and his crew was rescued.

Note the ciphertext above has some errors in it, see this comment for a more correct version.

The Algorithm §

The 'key' for a playfair cipher is generally a word, for the sake of example we will choose 'monarchy'. This is then used to generate a 'key square', e.g.

m o n a r
c h y b d
e f g i k
l p q s t
u v w x z

Any sequence of 25 letters can be used as a key, so long as all letters are in it and there are no repeats. Note that there is no 'j', it is combined with 'i'. We now apply the encryption rules to encrypt the plaintext.

Remove any punctuation or characters that are not present in the key square (this may mean spelling out numbers, punctuation etc.).
Identify any double letters in the plaintext and replace the second occurence with an 'x' e.g. 'hammer' -> 'hamxer'.
If the plaintext has an odd number of characters, append an 'x' to the end to make it even.
Break the plaintext into pairs of letters, e.g. 'hamxer' -> 'ha mx er'
The algorithm now works on each of the letter pairs.
Locate the letters in the key square, (the examples given are using the key square above)
1. If the letters are in different rows and columns, replace the pair with the letters on the same row respectively but at the other pair of corners of the rectangle defined by the original pair. The order is important – the first encrypted letter of the pair is the one that lies on the same row as the first plaintext letter. 'ha' -> 'bo', 'es' -> 'il'
2. If the letters appear on the same row of the table, replace them with the letters to their immediate right respectively (wrapping around to the left side of the row if a letter in the original pair was on the right side of the row). 'ma' -> 'or', 'lp' -> 'pq'
3. If the letters appear on the same column of the table, replace them with the letters immediately below respectively (wrapping around to the top side of the column if a letter in the original pair was on the bottom side of the column). 'rk' -> 'dt', 'pv' -> 'vo'

Clarification with pictures - Assume one wants to encrypt the digraph OR. There are three general cases: [1]

m * * a *
* * * * *
* * * * *
l * * s *
* * * * *

Hence, al -> ms

* * * * *
* h y b d
* * * * *
* * * * *
* * * * *

Hence, hb -> yd

* * n * *
* * y * *
* * * * *
* * q * *
* * w * *

Hence, nq -> yw

An example encryption, "we are discovered, save yourself" using the key square shown at the beginning of this section:

plaintext:  wearediscoveredsaveyourselfx
ciphertext: ugrmkcsxhmufmkbtoxgcmvatluiv

JavaScript Example of the Playfair Cipher §

Plaintext

keysquare =

Ciphertext

Other Implementations §

To encipher your own messages in python, you can use the pycipher module. To install it, use pip install pycipher. To encipher messages with the Playfair cipher (or another cipher, see here for documentation):

>>>from pycipher import Playfair
>>>Playfair('zgptfoihmuwdrcnykeqaxvsbl').encipher('defend the east wall of the castle')
'RKPAWRPMYSELZCLFXUZFRSNQBPSA'
>>>Playfair('zgptfoihmuwdrcnykeqaxvsbl').decipher('RKPAWRPMYSELZCLFXUZFRSNQBPSA')
'DEFENDTHEXASTWALLOFTHECASTLE'

Cryptanalysis §

For a tutorial on breaking Playfair with a simulated annealing algorithm, see Cryptanalysis of the Playfair Cipher.

Obtaining the key is relatively straightforward if both plaintext and ciphertext are known, however we want to find the key without knowing the plaintext. Guessing some of the words using knowledge of where the message came from, when it came from, etc. can be a huge help in reconstructing the key square. It should be recognized that guessing some of the plaintext and using that to reconstruct the keysquare is by far the easiest way to crack this cipher.

Cryptanalysis of the playfair cipher is much more difficult than normal simple substitution ciphers, because digraphs (pairs of letters) are being substituted instead of monographs (single letters). If we use frequency analysis of english digraphs, we can use this information in the same way as we used the monograph frequencies, however, there are ~600 digraphs and only 26 monographs. We need far more ciphertext for the digraphic system to make reliable key choices compared to the monographic system.

When cryptanalysing by hand, the following trick can be used. A Playfair digraph and its reverse (e.g. AB and BA) will decrypt to the same letter pattern in the plaintext (e.g. RE and ER). In English, there are many words which contain these reversed digraphs such as REceivER and DEpartED. Identifying nearby reversed digraphs in the ciphertext and matching the pattern to a list of known plaintext words containing the pattern is an easy way to generate possible plaintext strings with which to begin constructing the key. A good tutorial on reconstructing the key for a Playfair cipher can be found in chapter 7, "Solution to Polygraphic Substitution Systems," of Field Manual 34-40-2, produced by the United States Army.

When trying to decide which algorithm was used to encrypt some ciphertext, it is useful to know that Playfair will never contain a double-letter digraph, e.g. EE. If there are no double letter digraphs in the ciphertext and the length of the message is long enough to make this statistically significant, it is very likely that the method of encryption is Playfair. Other things that will be true about the ciphertext message:

The cipher message contains an even number of letters.
A frequency count will show no more than 25 letters (with no letter J).
If long repeats occur, they will be separated by an even number of characters. Repeated sequences will usually be an even number of characters.

When Solving by computer, an easy way of finding a key is to start with a random square of letters. Minor changes are then introduced (i.e. swapping letters in the key) to see if the candidate plaintext is more like standard plaintext than before the change (e.g. using markov models, or trigram frequency counts). If the new square is deemed to be an improvement (plaintext has higher likelyhood), then it is adopted and then further mutated to find an even better candidate. Eventually, the plaintext or something very close to it is found by chosing the key that provides a plaintext with the highest likelyhood.

References §

[1] Wikipedia has a good description of the encryption/decryption process, history and cryptanalysis of this algorithm
Basic Cryptanalysis, FM 34-40-2, FIELD MANUAL, DEPARTMENT OF THE ARMY http://www.umich.edu/~umich/fm-34-40-2/
A fairly decent look at some of the history of playfair, along with good cryptanalysis tips:
Lecture 3 "Cryptanalysis of the Classical Ciphers", by Dr. Alex Biryukov.
http://www.wisdom.weizmann.ac.il/~albi/cryptanalysis/lect3.htm
Simon Singh's 'The Code Book' is an excellent introduction to ciphers and codes, and includes a section on playfair ciphers.
Singh, Simon (2000). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. ISBN 0-385-49532-3.