2015/sol.py

   1 #!/bin/env python
   2
   3 """
   4 Python implementation of Bruce Schneier's Solitaire Encryption
   5 Algorithm (http://www.counterpane.com/solitaire.html).
   6
   7 John Dell'Aquila <jbd@alum.mit.edu>
   8 """
   9
  10 import string, sys
  11
  12 def toNumber(c):
  13     """
  14     Convert letter to number: Aa->1, Bb->2, ..., Zz->26.
  15     Non-letters are treated as X's.
  16     """
  17     if c in string.letters:
  18         return ord(string.upper(c)) - 64
  19     return 24  # 'X'
  20
  21 def toChar(n):
  22     """
  23     Convert number to letter: 1->A,  2->B, ..., 26->Z,
  24     27->A, 28->B, ... ad infitum
  25     """
  26     return chr((n-1)%26+65)
  27
  28
  29 class Solitaire:
  30     """ Solitaire Encryption Algorithm
  31     http://www.counterpane.com/solitaire.html
  32     """
  33
  34     def _setKey(self, passphrase):
  35         """
  36         Order deck according to passphrase.
  37         """
  38         self.deck = range(1,55)
  39         # card numbering:
  40         #  1, 2,...,13 are A,2,...,K of clubs
  41         # 14,15,...,26 are A,2,...,K of diamonds
  42         # 27,28,...,39 are A,2,...,K of hearts
  43         # 40,41,...,52 are A,2,...,K of spades
  44         # 53 & 54 are the A & B jokers
  45         for c in passphrase:
  46             self._round()
  47             self._countCut(toNumber(c))
  48
  49     def _down1(self, card):
  50         """
  51         Move designated card down 1 position, treating
  52         deck as circular.
  53         """
  54         d = self.deck
  55         n = d.index(card)
  56         if n < 53: # not last card - swap with successor
  57             d[n], d[n+1] = d[n+1], d[n]
  58         else: # last card - move below first card
  59             d[1:] = d[-1:] + d[1:-1]
  60
  61     def _tripleCut(self):
  62         """
  63         Swap cards above first joker with cards below
  64         second joker.
  65         """
  66         d = self.deck
  67         a, b = d.index(53), d.index(54)
  68         if a > b:
  69             a, b = b, a
  70         d[:] = d[b+1:] + d[a:b+1] + d[:a]
  71
  72     def _countCut(self, n):
  73         """
  74         Cut after the n-th card, leaving the bottom
  75         card in place.
  76         """
  77         d = self.deck
  78         n = min(n, 53) # either joker is 53
  79         d[:-1] = d[n:-1] + d[:n]
  80
  81     def _round(self):
  82         """
  83         Perform one round of keystream generation.
  84         """
  85         self._down1(53) # move A joker down 1
  86         self._down1(54) # move B joker down 2
  87         self._down1(54)
  88         self._tripleCut()
  89         self._countCut(self.deck[-1])
  90
  91     def _output(self):
  92         """
  93         Return next output card.
  94         """
  95         d = self.deck
  96         while 1:
  97             self._round()
  98             topCard = min(d[0], 53)  # either joker is 53
  99             if d[topCard] < 53:  # don't return a joker
 100                 return d[topCard]
 101
 102     def encrypt(self, txt, key):
 103         """
 104         Return 'txt' encrypted using 'key'.
 105         """
 106         self._setKey(key)
 107         # pad with X's to multiple of 5
 108         txt = txt + 'X' * ((5-len(txt))%5)
 109         cipher = [None] * len(txt)
 110         for n in range(len(txt)):
 111             cipher[n] = toChar(toNumber(txt[n]) + self._output())
 112         # add spaces to make 5 letter blocks
 113         for n in range(len(cipher)-5, 4, -5):
 114             cipher[n:n] = [' ']
 115         return string.join(cipher, '')
 116
 117     def decrypt(self, cipher, key):
 118         """
 119         Return 'cipher' decrypted using 'key'.
 120         """
 121         self._setKey(key)
 122         # remove white space between code blocks
 123         cipher = string.join(string.split(cipher), '')
 124         txt = [None] * len(cipher)
 125         for n in range(len(cipher)):
 126             txt[n] = toChar(toNumber(cipher[n]) - self._output())
 127         return string.join(txt, '')
 128
 129 testCases = ( # test vectors from Schneier paper
 130     ('AAAAAAAAAAAAAAA', '', 'EXKYI ZSGEH UNTIQ'),
 131     ('AAAAAAAAAAAAAAA', 'f', 'XYIUQ BMHKK JBEGY'),
 132     ('AAAAAAAAAAAAAAA', 'fo', 'TUJYM BERLG XNDIW'),
 133     ('AAAAAAAAAAAAAAA', 'foo', 'ITHZU JIWGR FARMW'),
 134     ('AAAAAAAAAAAAAAA', 'a', 'XODAL GSCUL IQNSC'),
 135     ('AAAAAAAAAAAAAAA', 'aa', 'OHGWM XXCAI MCIQP'),
 136     ('AAAAAAAAAAAAAAA', 'aaa', 'DCSQY HBQZN GDRUT'),
 137     ('AAAAAAAAAAAAAAA', 'b', 'XQEEM OITLZ VDSQS'),
 138     ('AAAAAAAAAAAAAAA', 'bc', 'QNGRK QIHCL GWSCE'),
 139     ('AAAAAAAAAAAAAAA', 'bcd', 'FMUBY BMAXH NQXCJ'),
 140     ('AAAAAAAAAAAAAAAAAAAAAAAAA', 'cryptonomicon',
 141      'SUGSR SXSWQ RMXOH IPBFP XARYQ'),
 142     ('SOLITAIRE','cryptonomicon','KIRAK SFJAN')
 143 )
 144
 145 def usage():
 146     print """Usage:
 147     sol.py {-e | -d} _key_ < _file_
 148     sol.py -test
 149
 150     N.B. WinNT requires "python sol.py ..."
 151     for input redirection to work (NT bug).
 152     """
 153     sys.exit(2)
 154
 155 if __name__ == '__main__':
 156     args = sys.argv
 157     if len(args) < 2:
 158         usage()
 159     elif args[1] == '-test':
 160         s = Solitaire()
 161         for txt, key, cipher in testCases:
 162             coded = s.encrypt(txt, key)
 163             assert cipher == coded
 164             decoded = s.decrypt(coded, key)
 165             assert decoded[:len(txt)] == string.upper(txt)
 166         print 'All tests passed.'
 167     elif len(args) < 3:
 168         usage()
 169     elif args[1] == '-e':
 170         print Solitaire().encrypt(sys.stdin.read(), args[2])
 171     elif args[1] == '-d':
 172         print Solitaire().decrypt(sys.stdin.read(), args[2])
 173     else:
 174         usage()