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.

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 630 other followers

%d bloggers like this: