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.

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