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 ~600 possible digraphs
rather than the 26 possible monographs. Frequency analysis thus requires much more ciphertext in order to
work.
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."
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
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)
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'
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'
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]
a)
m * * a * * * * * * * * * * * l * * s * * * * * *
Hence, al -> ms
b)
* * * * * * h y b d * * * * * * * * * * * * * * *
Hence, hb -> yd
c)
* * n * * * * y * * * * * * * * * q * * * * w * *
Hence, nq -> yw
An example encryption, "we are discovered, safe yourself" using the key square shown at the beginning of this section:
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.
Code
I have included here some C code that does encryption and decryption of
the playfair cipher. It is only meant to show the working of the
algorithm, not be a final polished solution. C example of the playfair cipher
References
[1] Wikipedia
has a good description of the encryption/decryption process, history
and cryptanalysis of this algorithm
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.