## 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") "LIVOBLKZEDOELIYWCN" > (decipher (make-key "PLAYFAIR") "LIVOBLKZEDOELIYWCN") "PROGRAMXMINGPRAXIS"```

We have used `string-upcase` and `string-index` from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/1lKnWAtU.

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

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

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