### 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.

Pages: 1 2

### 8 Responses to “Straddling Checkerboard”

1. […] Praxis – Straddling Checkerboard By Remco Niemeijer In today’s Programming Praxis problem we have to implement the straddling checkerboard cipher. Let’s get […]

2. Remco Niemeijer said

```import Data.Char
import Data.List

alphabet :: String
alphabet = ['A'..'Z'] ++ " "

clean :: String -> String
clean = filter (`elem` alphabet ++ ['0'..'9']) . map toUpper

board :: String -> [Int] -> String
board key = spaces (replace =<< nub (clean key ++ alphabet))
where spaces    = foldl (\a x -> take x a ++ "_" ++ drop x a)
replace c = c : (maybe "" id . lookup c \$ zip alphabet
(map show [1..9] ++ "0" : repeat ""))

run :: (Int -> Int -> Int) -> String -> [Int] -> Int -> String -> String
run op text ss add key = f \$ show =<<
zipWith (\a b -> mod (op (read [a]) b) 10)
(toIndex =<< clean text)
(cycle . map digitToInt \$ show add) where
f []       = []
f (a:xs)   = if elem (digitToInt a) ss
then fromIndex ([a], take 1 xs) ++ f (tail xs)
else fromIndex ("" , [a]      ) ++ f xs
fromIndex  = maybe "" return . look id
toIndex    = maybe "" (uncurry (++)) . look flip
look dir k = lookup k . dir zip indices \$ board key ss
indices    = [(y, show x) | y <- "" : map show ss, x <- [0..9]]

encipher :: String -> Int -> Int -> Int -> Int -> String -> String
encipher xs s1 s2 s3 = run (+) xs [s1, s2, s3]

decipher :: String -> Int -> Int -> Int -> Int -> String -> String
decipher xs s1 s2 s3 = run (-) xs [s1, s2, s3]
```
3. novatech said

my ruby attemp

```class Straddling
def initialize( key, n1, n2, n3 )
key = key+"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
key = key.upcase.split(//).uniq
@key = key;@n1 = n1;@n2 = n2;@n3 = n3
end

def create
@board = Array.new(4)
k = 0;prev = ""
for a in 0..40 do
if (a == @n1 || a == @n2 || a == @n3)
@board[a] = " "
else
if ("A".."J") === prev

@board[a] = prev == "J"? 0:((prev)-16).chr
else
@board[a] = @key[k] == " " ? "*" : @key[k]
k+=1
end
prev = @board[a]
end
end
return @board.to_s
end

def tp(key,text)
@key = key.split(//)
@text = text.gsub(' ','*').upcase.split(//)
end

def keygen
@keygen = Array.new
@checker_board = @board.to_s.split(//)
for a in 0..@text.length-1 do
found = @checker_board.index(@text[a])
if (0..9) === found
@keygen.push(found)
elsif (10..19) === found
@keygen.push(@n1,found%10)
elsif (20..29) === found
@keygen.push(@n2,found%10)
else
@keygen.push(@n3,found%10)
end
end
end

def e(key,text)
self.tp(key,text)
self.keygen
print "#{@keygen.to_s}\n"
@t = Array.new
@keygen.each do |value|
@t.push((@key.to_i+value.to_i)%10)
@key << @key.shift
end
print "#{@t.to_s}\n"
print "Encrypt=#{self.show}\n"
end

def d(key,text)
self.tp(key,text)
self.keygen
@t = Array.new
@keygen.each do |value|
@t.push((value+10-(@key).to_i)%10)
@key << @key.shift
end
print "Decrypt=#{self.show.gsub('*',' ')}\n"
end

def show
a = 0
result = ""
while a < @t.length
unless @t[a] == @n1 || @t[a] == @n2 || @t[a] == @n3
result = result + @checker_board[@t[a]]
else
result = result + @checker_board[(@t[a] == @n1 ? 1 : @t[a] == @n2? 2:3)*10+@t[a+1]]
a+=1
end
a+=1
end
return result
end

end
puts(board.create)
board.e("2641","programming praxis")
board.d("2641","S811R53S87A18RUAS8PSSH5")
puts("\n\n")
puts(board.create)
board.e("241","ruby programming rocks")
board.d("241","SF5E5*5MIREESEACY45YIS5****MESE")
```
4. novatech said

while i try to improve my coding i’ve notice few bug with this type of straddling checkerboard
it’s when the end of digit list is 2, 5 or 9. assuming we check the last value as single digit, compare it against board will give us ‘_’ or space in this case. reverse it back wont be valid due to 3 position of spaces..

for example
“encrypt this text”
will be
466376136437493731214937463912
match this number to checker board we get
4 6 6 3 7 6 1 3 6 4 3 7 4 93 7 3 1 21 4 93 7 4 6 3 91 2 (we not check next value is nil)
A 1 1 8 R 1 H 8 1 A 8 R A L R 8 H 5 A L R A 1 8 0 _

another example is
“a a”
“i can get a”
:)

5. programmingpraxis said

The normal solution when using the straddling checkerboard by hand is to add an extra digit, forming a null character. Perhaps you would like to propose a fix for the suggested solution?

6. Mike said

Python version.

```from itertools import cycle, izip

def digits(n, base=10):
seq = []
while n:
n,r = divmod(n,base)
seq.append(r)
seq.reverse()
return seq

class Checkerboard:
def __init__(self, passphrase, d1, d2, d3, pin):
'''the key for the checkerboard cypher includes a word or phrase
(passphrase), three different digits (d1, d2, and d3), and a
multiple digit number (pin).
'''

self.rows = [d1, d2, d3]
self.pin  = digits( pin )
self.unpin = [ 10 - d for d in self.pin ]

board = []
for n,ltr in enumerate( passphrase + "ABCDEFGHIJKLMNOPQRSTUVWXYZ" ):
if ltr in board: continue

if 'A' <= ltr <= 'J':
board.append(ltr)
board.append('1234567890'[ord(ltr)-ord('A')])

elif '0' <= ltr <= '9':
board.append('JABCDEFGHI'[int(ltr)])
board.append(ltr)

else:
board.append(ltr)
else:
for n in self.rows:
board[n:n] = '_'

self.emap = {}
self.dmap = {}

for n,ltr in enumerate( board ):
if n < 10:
self.emap[ ltr ] = (n,)
self.dmap[n] = ltr
else:
k = ( self.rows[ n / 10 - 1 ], n % 10 )
self.emap[ ltr ] = k
self.dmap[k] = ltr

def _encode(self, chars):
return [d for ltr in chars for d in self.emap[ltr]]

def _process(self, digits, key):
return [(d + m)%10 for d,m in izip(digits, cycle(key))]

def _decode(self, digits):
out = []
r = 0
for c in digits:
if r:
out.append( self.dmap[(r,c)] )
r = 0

elif c in self.rows:
r = c

else:
out.append( self.dmap[ c ] )

return out

def encrypt(self, message):
buf = self._encode(message)
buf = self._process(buf, self.pin)
buf = self._decode(buf)

return ''.join(buf)

def decrypt(self, message):
buf = self._encode(message)
buf = self._process(buf, self.unpin)
buf = self._decode(buf)

return ''.join(buf)
```

Sample usage and output:

cb = Checkerboard("SHARPEN YOUR SAW", 2,5,9, 2641)

cyphertext = cb.encrypt("PROGRAMMING PRAXIS")
print "cyphertext =", cyphertext

plaintext = cb.decrypt(cyphertext)
print "plaintext =", plaintext

cyphertext = S811R53S87A18RUAS8PSSH5
plaintext = PROGRAMMING PRAXIS

7. Moe W said

Mike is there a simpler Python version or code to use for that cipher?

8. Ed said

The bug is actually worse than stated; often there is an intermediate transposition involved and an extra character may throw that transposition off and distort the shape of the cipher. My solution is to replace the spaces with punctuation for the reverse substitution, so that disallowed digits in the final position can be substituted. For instance,
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
(apologies– reply block is not monospaced)

This punctuation (@#%) is not used in the plain text, but if the final digit of the substituted (and possibly transposed) ciphertext is an unpaired 2, 5 or 9, it is reverse substituted with the @, #, or \$. This gets rid of the “phantom digit” in the intermediate stage.