September 1999 Programmer's Challenge

Playfair Decipher

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm ET, Monday, 6 September 1999

This month the Challenge ventures into the world of codebreaking. Simple codes, perhaps, but codes with a real-world history. Tom Saxton recently wrote to suggest a Challenge based on a simple substitution cipher. The problem we picked is a little more complicated, being based on letter pairs (digraphs) rather than single character substitutions. Invented by Sir Charles Wheatstone in the mid-1800s, the Playfair cipher (named after his friend, Baron Lyon Playfair) was used to encrypt telegraphic traffic and was also used during the Boer War and the First World War.

The Playfair cipher uses a 5x5 encryption matrix, in which each letter of the alphabet appears once. (The letters "i" and "j" map to the same cell.) While we codebreakers don’t know what the keyword is, or what the matrix is for any given cipherText, we are fortunate in that our Intelligence organization has determined that our adversaries create their matrices from a keyword in a known manner.

As an example, let’s use the keyword "cryptogram" to generate the encryption matrix. First, we write the unique characters in the keyword across in one line: Notice that the letter "r" appears only once, even though it occurs twice in the keyword.

        CRYPTOGAM

Next, the remaining letters of the alphabet are written below:

        
        CRYPTOGAM
        BDEFHIKLN
        QSUVWXZ--

To form the 5x5 encryption matrix, the letters are read off by columns:

        
        C  B  Q  R  D
        S  Y  E  U  P
        F  V  T  H  W
        O IJ  X  G  K
        Z  A  L  M  N

To encode a message, the plainText is split into two-letter groups. If a two-letter group would consist of a double letter, an ‘X’ is inserted between the double letters. An ‘X’ is also added at the end if needed to complete the last group. So, if the plainText is "The scheme really works." the two-letter groups formed as follows:

        TH ES CH EM ER EA LX LY WO RK SX

Each letter pair is encoded using the encryption matrix. If the letters are in the same row, the letter to its right in that row (wrapping the row if necessary) replaces each letter. If the letters are in the same column, each letter is replaced by the letter beneath it in that column (again, wrapping the column back to the top if necessary). If the letters are in different rows and columns, each letter is replaced with the letter at the intersection of its row and the other letter’s column. So, in our example, the cipherText becomes:

        HW UY RF UL UQ YL QL AE FK DG EO

So, with that explanation, the prototype for the code you should write is:

#if defined(__cplusplus)
extern "C" {
#endif

void InitPlayfair(
  const char *words[],      /* dictionary words */
  long numDictionaryWords   /* number of null-terminated words in dictionary */
);

void DecodePlayfair(
  const char *cipherText,   /* null-terminated text to decode */
  char *plainText           /* null-terminated decoded text */
);

void TermPlayfair(void);

#if defined(__cplusplus)
}
#endif