January 29, 2010

We examined the bifid cipher, which uses a polybius square to convert letters to digits and back again, in a previous exercise. Today we will look at another tool for converting between letters and digits known as a straddling checkerboard. A sample straddling checkerboard, based on the key SHARPEN YOUR SAW with spaces at 2, 5, and 9, is shown below (the three underscores in the first row make the space character visible):

```  0 1 2 3 4 5 6 7 8 9   S H _ 8 A _ 1 R P _ 2 E 5 N * Y O U W B 2 5 C 3 D 4 F 6 G 7 I 9 9 J 0 K L M Q T V X Z```

The checkerboard has four rows and ten columns. Three of the positions in the first row are spaces, leaving twenty-six letters, ten digits, and an asterisk to represent the space character. The row numbers correspond to the positions of the three first-row spaces. Our method is traditional: the pass phrase followed by the alphabet, with duplicates removed and digits paired with the first ten letters of the alphabet (A=1, B=2, …, J=0). But any other method of filling out the key may be used.

To use the checkerboard, simply write one digit for letters that appear in the first row and two digits for letters in the subsequent rows, row digit first then column digit. For instance, the plain-text PROGRAMMING PRAXIS is converted to digits like this:

```P R O   G   R A M   M   I   N   G   *   P R A X   I   S 8 7 2 5 5 6 7 4 9 4 9 4 5 8 2 2 5 6 2 3 8 7 4 9 8 5 8 0```

Then the digits are processed in some way. A traditional method is double transposition, but we will use non-carrying (modulo 10) addition with key 2641:

```8 7 2 5 5 6 7 4 9 4 9 4 5 8 2 2 5 6 2 3 8 7 4 9 8 5 8 0 2 6 4 1 2 6 4 1 2 6 4 1 2 6 4 1 2 6 4 1 2 6 4 1 2 6 4 1 0 3 6 6 7 2 1 5 1 0 3 5 7 4 6 3 7 2 6 4 0 3 8 0 0 1 2 1```

Then the sums are converted back to letters and digits using the checkerboard in reverse. Although some letters are represented by one digit and other letters are represented by two digits, there is no ambiguity since the leading digits are known:

```0 3 6 6 7 2 1 5 1 0 3 5 7 4 6 3 7 2 6 4 0 3 8 0 0 1 2 1 S 8 1 1 R 5   3   S 8 7   A 1 8 R U   A S 8 P S S H 5```

Thus, the completed cipher-text is S811RS3S87A18RUAS8PSSH5. Decryption is the inverse operation.

Your task is to write functions that perform encryption and decryption using the straddling checkerboard as shown above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.