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.

About these ads

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

    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]
    
  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)[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")
    
  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.

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

%d bloggers like this: