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:

  1. 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.
  2. 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.
  3. 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 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 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.

About these ads

Pages: 1 2

6 Responses to “The Playfair Cipher”

  1. [...] 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 [...]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2009/07/03/programming-praxis-the-playfair-cipher/ for a version with comments):

    import Data.Char
    import Data.List
    import Data.List.HT
    import Data.List.Split
    import qualified Data.Map as M
    
    type Key = M.Map (Int, Int) Char
    
    process :: String -> String
    process = replace "J" "I" . map toUpper . filter isLetter
    
    key :: String -> Key
    key = M.fromList . concat .
          zipWith (\y -> zipWith (\x c -> ((x, y), c)) [0..]) [0..] .
          chunk 5 . (`union` delete 'J' ['A'..'Z']) . nub . process
    
    bigram :: Key -> Int -> Char -> Char -> String
    bigram k dir c1 c2
        | y1 == y2  = get (x1 + dir, y1) : [get (x2 + dir, y2)]
        | x1 == x2  = get (x1, y1 + dir) : [get (x2, y2 + dir)]
        | otherwise = get (x2, y1)       : [get (x1, y2)]
        where (x1, y1) = head . M.keys $ M.filter (== c1) k
              (x2, y2) = head . M.keys $ M.filter (== c2) k
              get (x,y) = k M.! (mod x 5, mod y 5)
    
    encode' :: Key -> String -> String
    encode' _ []       = []
    encode' k [x]      = encode' k (x : "X")
    encode' k (x:y:xs) | x == y    = encode' k [x] ++ encode' k (y:xs)
                       | otherwise = bigram k 1 x y ++ encode' k xs
    
    decode' :: Key -> String -> String
    decode' k = concatMap (\[x,y] -> bigram k (-1) x y) . chunk 2
    
    encode :: String -> String -> String
    encode k = encode' (key k) . process
    
    decode :: String -> String -> String
    decode k = decode' (key k) . process
    
    main :: IO ()
    main = do print $ encode "PLAYFAIR" "PROGRAMMING PRAXIS"
              print $ decode "PLAYFAIR" "LIVOBLKZEDOELIYWCN"
    
  3. programmingpraxis said

    Elsewhere, Remco asks:

    Interestingly, if you try to decode the 1943 message, you’ll notice two errors in the result: it says Blackess instead of Blackett and coce instead of cove. I wonder if the errors were made by the original sender or by the first person to type it on a computer.

    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.

  4. [...] bailouts as a brilliant success with no unpleasant side effects.” We’ll refer to the previous exercise for [...]

  5. hiral said

    where is the c code

  6. alkadri31 said

    Thanks to the writer and commentators
    I have benefited a lot from you ^ ^

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 598 other followers

%d bloggers like this: