Straddling Checkerboard
January 29, 2010
We begin with the code to strip extraneous characters from the input and convert space characters to asterisks:
(define (clean text)
(let loop ((cs (string->list text)) (zs '()))
(cond ((null? cs) (reverse zs))
((char=? (car cs) #\space)
(loop (cdr cs) (cons #\* zs)))
((char-alphabetic? (car cs))
(loop (cdr cs) (cons (char-upcase (car cs)) zs)))
((char-numeric? (car cs))
(loop (cdr cs) (cons (car cs) zs)))
(else (loop (cdr cs) zs)))))
Make-checkerboard is a simple loop with two helper functions. Put adds a character to the checkerboard, unless it is already present, and matches digits with letters. Fix inserts the three space characters in the first row.
(define (make-checkerboard key s1 s2 s3)
(define alphabet (string->list "ABCDEFGHIJKLMNOPQRSTUVWXYZ"))
(define (put c zs)
(cond ((member c zs) '())
((char-numeric? c) (list c))
((char<=? #\A c #\I)
(append (put (integer->char (- (char->integer c) 16)) zs) (list c)))
((char=? c #\J)
(append (put #\0 zs) (list c)))
(else (list c))))
(define (fix xs)
(let loop ((k 0) (xs xs) (zs '()))
(cond ((null? xs) (reverse zs))
((= k s1) (loop (+ k 1) xs (cons #\space zs)))
((= k s2) (loop (+ k 1) xs (cons #\space zs)))
((= k s3) (loop (+ k 1) xs (cons #\space zs)))
(else (loop (+ k 1) (cdr xs) (cons (car xs) zs))))))
(let loop ((ks (append (clean key) alphabet)) (zs '()))
(if (null? ks)
(list->string (fix (reverse zs)))
(loop (cdr ks) (append (put (car ks) zs) zs)))))
The encryption key is represented as an a-list with each a-list item containing the plain-text character in its car, followed by a list of digits corresponding to the plain-text character; the digits are in reverse order because the output is accumulated in reverse order. The decryption key is represented as list of four a-lists, one for each row, each containing the digit in the car of the a-list item followed by the plain-text character in the cadr. Both e-key and d-key are global variables. There are also three global variables space1, space2 and space3 that tell the positions of the spaces in the first row. Input to make-keys is a forty-character string like SH 8A 1RP E5N*YOUWB2C3D4F6G7I9J0KLMQTVXZ, where the space characters represent the three empty positions in the first row; there is no output, but all the global variables are set appropriately.
(define space1 #f)
(define space2 #f)
(define space3 #f)
(define e-key '())
(define d-key '())
Make-keys is just a series of do-loops:
(define (make-keys checkerboard)
(do ((i 0 (+ i 1))) ((= i 10))
(cond ((not (char-whitespace? (string-ref checkerboard i)))
(set! e-key (cons (list (string-ref checkerboard i)
i) e-key)))
(space2 (set! space3 i))
(space1 (set! space2 i))
(else (set! space1 i))))
(do ((i 10 (+ i 1))) ((= i 20))
(set! e-key (cons (list (string-ref checkerboard i)
(- i 10) space1) e-key)))
(do ((i 20 (+ i 1))) ((= i 30))
(set! e-key (cons (list (string-ref checkerboard i)
(- i 20) space2) e-key)))
(do ((i 30 (+ i 1))) ((= i 40))
(set! e-key (cons (list (string-ref checkerboard i)
(- i 30) space3) e-key)))
(let ((d1 '()) (d2 '()) (d3 '()) (d4 '()))
(do ((i 0 (+ i 1))) ((= i 10))
(if (not (char-whitespace? (string-ref checkerboard i)))
(set! d1 (cons (list i
(string-ref checkerboard i)) d1))))
(do ((i 10 (+ i 1))) ((= i 20))
(set! d2 (cons (list (- i 10)
(string-ref checkerboard i)) d2)))
(do ((i 20 (+ i 1))) ((= i 30))
(set! d3 (cons (list (- i 20)
(string-ref checkerboard i)) d3)))
(do ((i 30 (+ i 1))) ((= i 40))
(set! d4 (cons (list (- i 30)
(string-ref checkerboard i)) d4)))
(set! d-key (list d1 d2 d3 d4))))
The rest is easy. Straddle converts plain-text to a list of digits, and unstraddle converts a list of digits to plain-text:
(define (straddle plain-text)
(let loop ((ps plain-text) (cs '()))
(cond ((null? ps) (reverse cs))
((assoc (car ps) e-key) =>
(lambda (xs) (loop (cdr ps) (append (cdr xs) cs))))
(else (loop (cdr ps) (cons (car ps) (cons (car ps) cs)))))))
(define (unstraddle list-of-digits)
(let loop ((cs list-of-digits) (ps '()))
(cond ((null? cs) (map cadr (reverse ps)))
((= (car cs) space1)
(loop (cddr cs) (cons (assoc (cadr cs) (cadr d-key)) ps)))
((= (car cs) space2)
(loop (cddr cs) (cons (assoc (cadr cs) (caddr d-key)) ps)))
((= (car cs) space3)
(loop (cddr cs) (cons (assoc (cadr cs) (cadddr d-key)) ps)))
(else (loop (cdr cs) (cons (assoc (car cs) (car d-key)) ps))))))
All that's left is encryption and decryption using non-carrying addition and subtraction. Here are encipher and decipher, which each take a four-digit key that is converted to a circular list of characters; cycle comes from the exercise on Flavius Josephus, and digits comes from the Standard Prelude:
(define (cycle xs) (set-cdr! (last-pair xs) xs) xs)
(define (encipher key plain-text)
(define (plus a b) (modulo (+ a b) 10))
(let loop ((xs (straddle (clean plain-text)))
(ks (cycle (digits key))) (zs '()))
(if (null? xs)
(list->string (unstraddle (reverse zs)))
(loop (cdr xs) (cdr ks) (cons (plus (car xs) (car ks)) zs)))))
(define (decipher key cipher-text)
(define (minus a b) (modulo (- a b) 10))
(let loop ((xs (straddle (string->list cipher-text)))
(ks (cycle (digits key))) (zs '()))
(if (null? xs)
(list->string
(map (lambda (c) (if (char=? c #\*) #\space c))
(unstraddle (reverse zs))))
(loop (cdr xs) (cdr ks) (cons (minus (car xs) (car ks)) zs)))))
Here's a sample:
> (make-checkerboard "sharpen your saw" 2 5 9)
"SH 8A 1RP E5N*YOUWB2C3D4F6G7I9J0KLMQTVXZ"
> (encipher 2641 "programming praxis")
"S811R53S87A18RUAS8PSSH5"
> (decipher 2641 "S811R53S87A18RUAS8PSSH5")
"PROGRAMMING PRAXIS"
You can run the program at http://programmingpraxis.codepad.org/jB1PVtjv.
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.