Solitaire Cipher
January 18, 2011
In his book Cryptonomicon, Neal Stephenson has his characters communicate using a cipher called Pontifex. Pontifex is based on the Solitaire cipher developed by Bruce Schneier, and uses an ordinary deck of cards, thirteen cards in each of four suits, plus two distinguishable jokers, to generate a keystream that is added to plain-text to form cipher-text, or subtracted from cipher-text to form plain-text.
After the deck is keyed, a single step consists of four operations on the deck. First, the “A” joker is moved one card down the deck, wrapping around the end of the deck if necessary. Second, the “B” joker is moved two cards down the deck, again wrapping around the deck if necessary. Third, a triple-cut swaps all the cards above the highest joker in the deck with all the cards below the lowest joker in the deck, leaving the two jokers and the cards between them in place. Fourth, a counted cut, based on the number of the bottom card in the deck, moves the top “count” cards to just above the bottom card; the cards are numbered 1 to 52 in “bridge order” with ace low to king high in each suit, clubs, diamonds, hearts, spades, and either joker counting as 53. Then look at the top card in the deck and count down the given number to determine the current key card.
For example, given an initial deck in bridge order 1, 2, …, 52, A, B, where the two jokers are A and B, the first operation moves the A joker one card down the deck leaving 1, 2, …, 52, B A, the second operation moves the B joker two cards down the deck leaving 1, B, 2, …, 52, A, the third operation performs a triple cut (the second half of the cut is empty) leaving B, 2, …, 52, A, 1, and the fourth step performs a count cut taking one card (because the bottom card on the deck is 1) leaving 2, …, 52, A, B, 1. Then the output card is 4, the four of clubs, because the top card of the deck is 2 and the second card below it is 4.
Before encrypting or decrypting a message, the deck must be “keyed.” Begin with a deck in bridge order and perform a single step. Then, for each character in the key, do a counted cut on the number of the current character, with A=1 … Z=26, followed by another single step. Once the deck is keyed and you have a keystream, each character is added (for encryption) or subtracted (for decryption) from the current text character, wrapping around the alphabet as necessary, so that A+A=B and T+Q=K; note that Z is the identity character, so F+Z=F. The plain-text has nulls (the letter X) added to the end to make the message length a multiple of five, and the cipher-text is split into five-character blocks for convenience.
Schneier gives three examples. Given the plaintext AAAAAAAAAA and null key, the keystream is 4 49 10 (53) 24 8 51 44 6 4 33 (the joker is skipped) and the ciphertext is EXKYI ZSGEH. Given the plaintext AAAAAAAAAAAAAAA and key FOO, the keystream is 8 19 7 25 20 (53) 9 8 22 32 43 5 26 17 (53) 38 48 and the ciphertext is ITHZU JIWGR FARMW. Given the plaintext SOLITAIRE and key CRYPTONOMICON, the keystream is 44 46 32 18 17 18 23 44 22 42 and the ciphertext is KIRAK SFJAN.
If you actually run the cipher with a deck of cards, you will find that, with just a little practice, your hands work the keystream generator themselves with little conscious thought, and you will soon memorize the wrap-around character addition rules like T+Q=K; the biggest problem with the cipher, like any output-feedback cipher, is that a single mistake renders all trailing text unreadable. This cipher is best used for low-volume transmission of short messages. If you use it for real security, your key should have at least eighty characters, and you should never use the same key to transmit two different messages. An easy way for two communicants to manage keys is for both to use some printed source, say the lead editorial in the daily newspaper or the pages of a favorite novel (be sure both are using the same edition), selecting the key as the first 80 characters starting at the 37th, say, and giving the date or page as a header to the encrypted message.
Your task is to write functions that encrypt and decrypt using the solitaire cipher. 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
My Python solution:
def movedown(deck,entry,move): """Move a card down a number of cards in the deck""" newindex = deck.index(entry) + move if newindex >= len(deck): newindex -= len(deck) - 1 deck.remove(entry) deck.insert(newindex,entry) def countcut(deck,count): """a counted cut, based on the number of the bottom card in the deck, moves the top count cards to just above the bottom card""" deck[-1:1] = deck[:count] del(deck[:count]) def joker(card): """Is the card a joker?""" return card in ('A','B') def step(deck): """Perform a step on the deck returning the key""" # A joker is moved one card down the deck, wrapping around the # end of the deck if necessary movedown(deck,'A',1) # the B joker is moved two cards down the deck, again wrapping # around the deck if necessary. movedown(deck,'B',2) # a triple-cut swaps all the cards above the highest joker in the # deck with all the cards below the lowest joker in the deck, # leaving the two jokers and the cards between them in place. indexa = deck.index('A') indexb = deck.index('B') if indexb > indexa: topindex, botindex = indexa, indexb else: topindex, botindex = indexb, indexa deck.extend(deck[topindex:botindex + 1]) deck.extend(deck[:topindex]) del(deck[:botindex + 1]) # Fourth, a counted cut, based on the number of the bottom card in # the deck. the cards are numbered 1 to 52 in bridge order with # ace low to king high in each suit, clubs, diamonds, hearts, # spades, and either joker counting as 53 count = deck[-1] if joker(count): count = 53 countcut(deck,count) # Then look at the top card in the deck and count down the given # number to determine the current key card. count = deck[0] if joker(count): count = 53 return deck[count] def keydeck(deck,key): # For each character in the key, perform a single step then do a # counted cut on the number of the current character, with # A=1...Z=26 for count in [ord(c) - 64 for c in key.upper()]: step(deck) countcut(deck,count) def solitare(plaintext,key="",decrypt=False): """encrypt and decrypt using the solitare cyper""" # Make uppercase and remove spaces plaintext = plaintext.upper().replace(' ','') # The plain-text has nulls (the letter X) added to the end to make # the message length a multiple of five pad = 5 - len(plaintext) % 5 if pad != 5: plaintext += 'X' # Create a deck in bridge order deck = range(1,53) + ['A','B'] keydeck(deck,key) ciphertext = '' count = 0 for c in plaintext: # the cipher-text is split into five-character blocks for # convenience. if count == 5: ciphertext += ' ' count = 0 key = step(deck) # the jokers are skipped while joker(key): key = step(deck) # each character is added (for encryption) or subtracted (for # decryption) from the current text character, wrapping around # the alphabet as necessary e = ord(c) if (decrypt): e -= key while e < ord('A'): e += 26 else: e += key while e > ord('Z'): e -= 26 count += 1 ciphertext += chr(e) return ciphertext print solitare("AAAAAAAAAA") print solitare("AAAAAAAAAAAAAAA","FOO") print solitare("SOLITAIRE","CRYPTONOMICON") print solitare("EXKYI ZSGEH",decrypt=True) print solitare("ITHZU JIWGR FARMW","FOO",decrypt=True) print solitare("KIRAK SFJAN","CRYPTONOMICON",decrypt=True)Line 84 should be:
and not:
My solution (Haskell): https://gist.github.com/785960
My python version.
from itertools import chain, ifilter, imap, izip A = 53 B = 54 N_CARDS = 54 ORD_A = ord('A') class Deck(list): def __init__(self, key=''): list.__init__(self, range(1,55)) self.step() for ch in key: self.counted_cut(ord(ch) - ORD_A + 1) self.step() def move(self, card, distance): fm = self.index(card) to = fm + distance if to >= N_CARDS: to -= (N_CARDS-1) self.insert(to, self.pop(fm)) def triple_cut(self): a = self.index(A) b = self.index(B) s, e = (a, b+1) if a < b else (b, a+1) self[:] = self[e:] + self[s:e] + self[:s] def counted_cut(self, count): self[:] = self[count:-1] + self[:count] + self[-1:] def step(self): self.move(A, 1) self.move(B, 2) self.triple_cut() self.counted_cut(min(self[-1], A)) def __iter__(self): while True: ndx = min(self[0], A) if self[ndx] < A: yield self[ndx] self.step() def encrypt(text, key=''): encode = lambda c,k: chr((ord(c) - ORD_A + k)%26 + ORD_A) padded_text = chain(text, ['X']*(-len(text)%5)) cyphertext = imap(encode, padded_text, Deck(key)) groups = imap(''.join, izip(*[cyphertext]*5)) return ' '.join(groups) def decrypt(text, key=''): decode = lambda c,k: chr((ord(c) - ORD_A - k)%26 + ORD_A) letters = (c for c in text if c.isupper()) return ''.join(imap(decode, letters, Deck(key)))My attempt in scheme.
(define (joker? n) (or (= n joker1) (= n joker2))) (define joker1 53) (define joker2 54) ;utils (define (find-elem i v pred?) (cond [(= i (vector-length v)) (error 'oops)] [(pred? (vector-ref v i)) i] [else (find-elem (+ i 1) v pred?)])) (define (string->nums s) (let ([l (string->list (string-upcase s))]) (map (lambda (c) (mod (mod (char->integer c) 64) 26)) l))) (define (nums->string nl) (map (lambda (n) (if (= 0 n) #\Z (integer->char (+ n 64)))) nl)) ;start (define (shift v index end op) (let ([val (vector-ref v index)]) (let loop ([index index]) (cond [(= index end) (vector-set! v index val)] [else (vector-set! v index (vector-ref v (op index 1))) (loop (op index 1))])))) (define (mov v i n ) (let ([index (mod i (vector-length v))]) (let ([end-index (mod (+ index n) (vector-length v))]) (if (<= index end-index) (shift v index end-index +) (shift v index (+ 1 end-index) -))))) (define (count-cut v n ei) (let ([si (- n 1)]) (let loop ([si si] [ei ei]) (cond [(< si 0) v] [(zero? si) (shift v si ei +)] [else (shift v si ei +) (loop (- si 1) (- ei 1))])))) (define (triple-cut v) (let ([joker1 (find-elem 0 v joker?)]) (count-cut v joker1 (- (vector-length v) 1)) (let ([joker2 (find-elem 1 v joker?)]) (count-cut v (+ joker2 1) (- (vector-length v) (+ 1 joker1))) v))) (define (move-jokers deck) (mov deck (find-elem 0 deck (lambda (n) (= n joker1))) 1) (mov deck (find-elem 0 deck (lambda (n) (= n joker2))) 2)) (define (steps deck) (move-jokers deck) (triple-cut deck) (let ([last-num (vector-ref deck (- (vector-length deck) 1))]) (count-cut deck (min 53 last-num) (- (vector-length deck) 2)))) (define (key-deck key deck) (for-each (lambda (i) (steps deck) (count-cut deck i (- (vector-length deck) 2))) key)) (define (enc-dec msg key op) (define (get-next deck) (steps deck) (let ([n (vector-ref deck (min 53 (vector-ref deck 0)))]) (if (>= n 53) (get-next deck) n))) (let ([msg (string->nums msg)] [key (string->nums key)] [deck (build-vector 54 (lambda (i) (+ i 1)))]) (key-deck key deck) (list->string (nums->string (map (lambda (m) (mod (op m (get-next deck)) 26)) msg))))) (define (enc msg key) (enc-dec msg key +)) (define (dec msg key) (enc-dec msg key -)) (define (test) (and (equal? (enc "AAAAAAAAAA" "" ) "EXKYIZSGEH") (equal? (enc "AAAAAAAAAAAAAAA" "FOO" ) "ITHZUJIWGRFARMW") (equal? (enc "SOLITAIRE" "CRYPTONOMICON" ) "KIRAKSFJA") (equal? (dec "EXKYIZSGEH" "") "AAAAAAAAAA") (equal? (dec "ITHZUJIWGRFARMW" "FOO") "AAAAAAAAAAAAAAA") (equal? (dec "KIRAKSFJA" "CRYPTONOMICON") "SOLITAIRE")))Another attempt using pattern matching.
(define DECK (build-list 54 (lambda (i) (+ i 1)))) (define joker1 53) (define joker2 54) (define (joker? j) (or (equal? j joker1) (equal? j joker2))) (define (to-num c) (modulo (- (char->integer (char-upcase c)) 64) 26)) (define (to-char n) (let ([n (modulo n 26)]) (if (zero? n) #\Z (integer->char (+ n 64))))) (define (eq=? val1) (lambda (val2) (= val1 val2))) (define (move-joker v joker) (match v [(list a x ... (? (eq=? joker)) ) (append (list a joker) x)] [(list x ... (? (eq=? joker)) b y ...) (append x (list b joker) y)])) (define (move-jokers v) (move-joker (move-joker (move-joker v joker1) joker2) joker2)) (define (triple-cut v) (match v [(list x ... (? joker? j1) y ... (? joker? j2) z ... ) (append z (list j1) y (list j2) x)])) (define (cut v n) (let ([val (list-ref v (- n 1))]) (match v [(list x ... (? (eq=? val) b) z ... c) (append z x (list b c))]))) (define (step v) (let ([v (triple-cut (move-jokers v))]) (cut v (min 53 (list-ref v (- (length v) 1)))))) (define (key-deck v key) (match key [(list ) v] [(list a b ...) (key-deck (cut (step v) (to-num a)) b) ])) (define (enc-dec msg deck op) (let ([deck (step deck)]) (let ([n (list-ref deck (min 53 (first deck)))]) (cond [(empty? msg) empty] [(joker? n) (enc-dec msg deck op)] [else (cons (to-char (op (to-num (first msg)) n)) (enc-dec (rest msg) deck op))])))) (define (enc msg key) (let ([deck (key-deck DECK (string->list key))]) (list->string (enc-dec (string->list msg) deck +)))) (define (dec msg key) (let ([deck (key-deck DECK (string->list key))]) (list->string (enc-dec (string->list msg) deck -))))