The Playfair Cipher
July 3, 2009
One of the most famous of the classical ciphers was the Playfair cipher, invented by Sir Charles Wheatstone in 1854 but popularized by Lord Lyon Playfair. The cipher was used by the British during the Boer War and World War I, and was still in use as a field-grade cipher as late as World War II, probably because it is simple to teach, fast to use, requires no special equipment, and was reasonably secure by the standards of the day; by the time enemy cryptanalysts could break the message, its contents were useless to them.
Playfair uses a 5-square block containing the pass-phrase; the letter J is mapped to I to make the 26-letter alphabet fit the 5-square block. The pass-phrase is first filled in to the 5-square block, then the remaining letters of the alphabet complete the 5-square block, with duplicates removed. For instance, the pass-phrase PLAYFAIR leads to this 5-square block:
P L A Y F
I R B C D
E G H K M
N O Q S T
U V W X Z
Some variants of Playfair omit Q instead of J, or start the key from the bottom-right corner and work backwards; we’ll stick with the standard method.
The message to be encrypted is split into digrams, with J mapped to I. In addition, no digram may use the same letter twice, so an X is inserted if needed (some Playfair variants use Z or Q instead of X). Likewise, if the last digram has only a single letter, an X is added to the end of the message. For instance, the plain-text PROGRAMMING PRAXIS is split as:
PR OG RA MX MI NG PR AX IS
Then each digram is enciphered separately according to the following rules:
- If the two letters of the digram are in the same row, they are replaced pairwise by the letters to their immediate right, wrapping around to the left of the row if needed.
- If the two letters of the digram are in the same column, they are replaced pairwise by the letters immediately below, wrapping around to the top of the column if needed.
- Otherwise, the first letter of the digram is replaced by the letter in the same row as the first letter of the digram and the same column as the second letter of the digram, and the second letter of the digram is replaced by the letter in the same row as the second letter of the digram and the same column as the first letter of the digram.
For instance, the PR digram is enciphered as LI, because P and R are in different rows and columns, and the OG digram is enciphered as VO, since O and G are in the same column. The complete encipherment is shown below:
PR OG RA MX MI NG PR AX IS
LI VO BL KZ ED OE LI YW CN
The coded message is thus LIVOBLKZEDOELIYWCN. Decryption is simply the inverse of encryption.
Playfair is rather more secure than simpler substitution ciphers because it works with digrams rather than single letters, rendering simple frequency analysis moot. Frequency analysis on digrams is possible, but requires considerably more cipher-text than frequency analysis on single letters because Playfair admits 600 digrams whereas simple substitution admits only 26 letters. Manual cryptanalysis looks at commonly-reversed digrams such as REceivER and DEcodED; if some plain-text is known (such as a standard message header), it is easy to recover at least a partial key.
The most famous use of the Playfair cipher came in 1943. David Kahn writes in 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 USEDQThe 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 and learned of Kennedy’s fate. […] About ten hours later, at 10:00 p.m. Kennedy and his crew was rescued.
Your task is to write functions that encipher and decipher messages using the Playfair cipher. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
[…] Praxis – The Playfair Cipher By Remco Niemeijer Today’s Programming Praxis problem is about the Playfair Cipher, a way of encrypting messages that was used […]
My Haskell solution (see http://bonsaicode.wordpress.com/2009/07/03/programming-praxis-the-playfair-cipher/ for a version with comments):
Elsewhere, Remco asks:
Both errors are in the original. You can confirm that because Kahn includes in his book, in the chapter “The Inscrutable Orientals,” a picture of the original hand-written decipherment by Arthur Evans at 9:30am on the morning of August 2, 1943 (it’s on page 592 of my copy of the 1996 edition). His key ROYAL NEW ZEALAND NAVY forms the following Polybius square:
R O Y A L
N E W Z D
V B C F G
H I K M P
Q S T U X
In the original message, BLACKETT STRAIT is enciphered as GOYFI WTTTU OLKS. The three Ts all in a row is a violation of the Playfair rules. Evans decoded the message as:
GO YF IW TT TU OL KS
BL AC KE TT ST RA IT
When Evans reached the TT digram, he deciphered it as TT; that was easy, because he was sitting on his jungle hilltop looking at Blackett Strait. But though it is easy to adjust by hand, the program does the wrong thing, as you noted.
The COVE/COCE error is undoubtedly a transcription error either by the original sender or by Evans. The corresponding cipher-text is BYBW. A correct encipherment of COVE is BYBN, and somewhere the N was transcribed as a W; easy enough to do if the pencil slips just at the beginning of the N, forming a small serif that causes N to be mistaken as W. Again, Evans had no trouble fixing the error; since he lived there, he knew the message said MERESU COVE rather than MERESU COCE.
It is worth reading Kahn’s book to learn the entire cryptographic history of the incident. There is much more to it than just a few errors in a Playfair cipher.
[…] bailouts as a brilliant success with no unpleasant side effects.” We’ll refer to the previous exercise for […]
where is the c code
Thanks to the writer and commentators
I have benefited a lot from you ^ ^
As Kahn points out, Wheatstone’s original was much stronger, because it involved a completely randomized Polybius square.
There’s an excellent description of Playfair and its decipherment in Dorothy L. Sayers’s mystery novel Have His Carcase. The ciphertext and a quick explanation of how Playfair works is at the beginning of Chapter 26. Most of Chapter 28 is concerned with deducing the key, and the decrypt appears at the beginning of Chapter 29. The solution is “special”: the rest of the alphabet remains intact in Playfair (but not in Wheatstone), the users were known to choose keys without duplicated letters (and as such more easily reconstructible), and most importantly a known-plaintext attack was available on the message header.
Long ago, I wrote a C implementation of the Hill cipher, which is in a sense a generalization of Playfair/bifid, and is also described in Kahn. Basically, you multiply a vector containing N characters of the plaintext by an N x N key matrix, and output the resultant vector as keytext. You have to make sure the matrix is invertible before using it, of course, but it’s easy given a random matrix to pervert it slightly until it is invertible. Hill is quite strong against classical cryptanalysis (we don’t have frequency tables of 64-grams, and they wouldn’t help much if we did), but also falls at once to known-plaintext attacks. This might make an interesting exercise.