The Playfair Cipher

July 3, 2009

We begin with a function to split the plain-text into digrams; it’s is complicated only because of the special handling for J, doubled letters, and the need to complete the last digram:

(define (split plain-text)
  (let loop ((ps (string->list (string-upcase plain-text))) (x #\_) (xs '()))
    (cond ((null? ps) (if (char=? x #\_) (reverse xs)
                        (reverse (cons (string x #\X) xs))))
          ((not (char-alphabetic? (car ps))) (loop (cdr ps) x xs))
          ((char=? (car ps) #\J) (loop (cons #\I (cdr ps)) x xs))
          ((char=? x #\_) (loop (cdr ps) (car ps) xs))
          ((char=? (car ps) x) (loop ps #\_ (cons (string x #\X) xs)))
          (else (loop (cdr ps) #\_ (cons (string x (car ps)) xs))))))

A key is a 25-character string consisting of the pass-phrase followed by the 25-letter alphabet excluding J, with duplicates removed. It is easier to store the key in this form than in a two-dimensional matrix, calculating offsets as needed:

(define (make-key pass-phrase)
  (let loop ((pass (string->list (string-append
              (string-upcase pass-phrase) "ABCDEFGHIKLMNOPQRSTUVWXYZ")))
             (key '()))
    (cond ((null? pass) (list->string (reverse key)))
          ((not (char-alphabetic? (car pass))) (loop (cdr pass) key))
          ((char=? (car pass) #\J) (loop (cons #\I (cdr pass)) key))
          ((member (car pass) key) (loop (cdr pass) key))
          (else (loop (cdr pass) (cons (car pass) key))))))

Encryption follows the rules given on the previous page. The quotient and modulo functions perform the necessary conversions between the two-dimensional 5-square block and the one-dimensional key:

(define (encipher key plain-text)
  (define (p->c str)
    (let ((a (string-index (string-ref str 0) key))
          (b (string-index (string-ref str 1) key)))
      (cond ((= (quotient a 5) (quotient b 5)) ; same row
              (string (string-ref key (+ (* (quotient a 5) 5) (modulo (+ a 1) 5)))
                      (string-ref key (+ (* (quotient b 5) 5) (modulo (+ b 1) 5)))))
            ((= (modulo a 5) (modulo b 5)) ; same column
              (string (string-ref key (+ (* (modulo (+ (quotient a 5) 1) 5) 5) (modulo a 5)))
                      (string-ref key (+ (* (modulo (+ (quotient b 5) 1) 5) 5) (modulo b 5)))))
            (else (string (string-ref key (+ (* (quotient a 5) 5) (modulo b 5)))
                          (string-ref key (+ (* (quotient b 5) 5) (modulo a 5))))))))
  (apply string-append (map p->c (split plain-text))))

Decryption is just the opposite of encryption:

(define (decipher key cipher-text)
  (define (c->p str)
    (let ((a (string-index (string-ref str 0) key))
          (b (string-index (string-ref str 1) key)))
      (cond ((= (quotient a 5) (quotient b 5)) ; same row
              (string (string-ref key (+ (* (quotient a 5) 5) (modulo (- a 1) 5)))
                      (string-ref key (+ (* (quotient b 5) 5) (modulo (- b 1) 5)))))
            ((= (modulo a 5) (modulo b 5)) ; same column
              (string (string-ref key (+ (* (modulo (- (quotient a 5) 1) 5) 5) (modulo a 5)))
                      (string-ref key (+ (* (modulo (- (quotient b 5) 1) 5) 5) (modulo b 5)))))
            (else (string (string-ref key (+ (* (quotient a 5) 5) (modulo b 5)))
                          (string-ref key (+ (* (quotient b 5) 5) (modulo a 5))))))))
  (apply string-append (map c->p (split cipher-text))))

Here you can see the cipher in action:

> (encipher (make-key "PLAYFAIR") "PROGRAMMING PRAXIS")
> (decipher (make-key "PLAYFAIR") "LIVOBLKZEDOELIYWCN")

We have used string-upcase and string-index from the Standard Prelude. You can run the program at

About these ads

Pages: 1 2

7 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 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:


    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 ^ ^

  7. John Cowan said

    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.

Leave a Reply

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

You are commenting using your 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


Get every new post delivered to your Inbox.

Join 644 other followers

%d bloggers like this: