Straddling Checkerboard
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.
Programming Praxis 
[…] Praxis – Straddling Checkerboard By Remco Niemeijer In today’s Programming Praxis problem we have to implement the straddling checkerboard cipher. Let’s get […]
My Haskell solution (see http://bonsaicode.wordpress.com/2010/01/29/programming-praxis-straddling-checkerboard/ for a version with comments):
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]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)[0]-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[0].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[0]).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 board = Straddling.new("sharpen your saw",2,5,9) puts(board.create) board.e("2641","programming praxis") board.d("2641","S811R53S87A18RUAS8PSSH5") puts("\n\n") board = Straddling.new("my secret keys",2,5,9) puts(board.create) board.e("241","ruby programming rocks") board.d("241","SF5E5*5MIREESEACY45YIS5****MESE")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”
:)
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?
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
Mike is there a simpler Python version or code to use for that cipher?
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.