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.
[…] 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):
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"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 LN 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 KSBL 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.