Challenge 8a done, 8b not attempted
[cipher-tools.git] / 2015 / sol.py
diff --git a/2015/sol.py b/2015/sol.py
new file mode 100644 (file)
index 0000000..35da266
--- /dev/null
@@ -0,0 +1,174 @@
+#!/bin/env python\r
+\r
+"""\r
+Python implementation of Bruce Schneier's Solitaire Encryption\r
+Algorithm (http://www.counterpane.com/solitaire.html).\r
+\r
+John Dell'Aquila <jbd@alum.mit.edu>\r
+"""\r
+\r
+import string, sys\r
+\r
+def toNumber(c):\r
+    """\r
+    Convert letter to number: Aa->1, Bb->2, ..., Zz->26.\r
+    Non-letters are treated as X's.\r
+    """\r
+    if c in string.letters:\r
+        return ord(string.upper(c)) - 64\r
+    return 24  # 'X'\r
+\r
+def toChar(n):\r
+    """\r
+    Convert number to letter: 1->A,  2->B, ..., 26->Z,\r
+    27->A, 28->B, ... ad infitum\r
+    """\r
+    return chr((n-1)%26+65)\r
+\r
+\r
+class Solitaire:\r
+    """ Solitaire Encryption Algorithm\r
+    http://www.counterpane.com/solitaire.html\r
+    """\r
+\r
+    def _setKey(self, passphrase):\r
+        """\r
+        Order deck according to passphrase.\r
+        """\r
+        self.deck = range(1,55)\r
+        # card numbering:\r
+        #  1, 2,...,13 are A,2,...,K of clubs\r
+        # 14,15,...,26 are A,2,...,K of diamonds\r
+        # 27,28,...,39 are A,2,...,K of hearts\r
+        # 40,41,...,52 are A,2,...,K of spades\r
+        # 53 & 54 are the A & B jokers\r
+        for c in passphrase:\r
+            self._round()\r
+            self._countCut(toNumber(c))\r
+\r
+    def _down1(self, card):\r
+        """\r
+        Move designated card down 1 position, treating\r
+        deck as circular.\r
+        """\r
+        d = self.deck\r
+        n = d.index(card)\r
+        if n < 53: # not last card - swap with successor\r
+            d[n], d[n+1] = d[n+1], d[n]\r
+        else: # last card - move below first card\r
+            d[1:] = d[-1:] + d[1:-1]\r
+        \r
+    def _tripleCut(self):\r
+        """\r
+        Swap cards above first joker with cards below\r
+        second joker.\r
+        """\r
+        d = self.deck\r
+        a, b = d.index(53), d.index(54)\r
+        if a > b:\r
+            a, b = b, a\r
+        d[:] = d[b+1:] + d[a:b+1] + d[:a]\r
+        \r
+    def _countCut(self, n):\r
+        """\r
+        Cut after the n-th card, leaving the bottom\r
+        card in place.\r
+        """\r
+        d = self.deck\r
+        n = min(n, 53) # either joker is 53\r
+        d[:-1] = d[n:-1] + d[:n]\r
+\r
+    def _round(self):\r
+        """\r
+        Perform one round of keystream generation.\r
+        """\r
+        self._down1(53) # move A joker down 1\r
+        self._down1(54) # move B joker down 2\r
+        self._down1(54)\r
+        self._tripleCut()\r
+        self._countCut(self.deck[-1])\r
+\r
+    def _output(self):\r
+        """\r
+        Return next output card.\r
+        """\r
+        d = self.deck\r
+        while 1:\r
+            self._round()\r
+            topCard = min(d[0], 53)  # either joker is 53\r
+            if d[topCard] < 53:  # don't return a joker\r
+                return d[topCard]\r
+\r
+    def encrypt(self, txt, key):\r
+        """\r
+        Return 'txt' encrypted using 'key'.\r
+        """\r
+        self._setKey(key)\r
+        # pad with X's to multiple of 5\r
+        txt = txt + 'X' * ((5-len(txt))%5)\r
+        cipher = [None] * len(txt)\r
+        for n in range(len(txt)):\r
+            cipher[n] = toChar(toNumber(txt[n]) + self._output())\r
+        # add spaces to make 5 letter blocks\r
+        for n in range(len(cipher)-5, 4, -5):\r
+            cipher[n:n] = [' ']\r
+        return string.join(cipher, '')\r
+\r
+    def decrypt(self, cipher, key):\r
+        """\r
+        Return 'cipher' decrypted using 'key'.\r
+        """\r
+        self._setKey(key)\r
+        # remove white space between code blocks\r
+        cipher = string.join(string.split(cipher), '')\r
+        txt = [None] * len(cipher)\r
+        for n in range(len(cipher)):\r
+            txt[n] = toChar(toNumber(cipher[n]) - self._output())\r
+        return string.join(txt, '')\r
+                \r
+testCases = ( # test vectors from Schneier paper\r
+    ('AAAAAAAAAAAAAAA', '', 'EXKYI ZSGEH UNTIQ'),\r
+    ('AAAAAAAAAAAAAAA', 'f', 'XYIUQ BMHKK JBEGY'),\r
+    ('AAAAAAAAAAAAAAA', 'fo', 'TUJYM BERLG XNDIW'), \r
+    ('AAAAAAAAAAAAAAA', 'foo', 'ITHZU JIWGR FARMW'),\r
+    ('AAAAAAAAAAAAAAA', 'a', 'XODAL GSCUL IQNSC'), \r
+    ('AAAAAAAAAAAAAAA', 'aa', 'OHGWM XXCAI MCIQP'), \r
+    ('AAAAAAAAAAAAAAA', 'aaa', 'DCSQY HBQZN GDRUT'),\r
+    ('AAAAAAAAAAAAAAA', 'b', 'XQEEM OITLZ VDSQS'), \r
+    ('AAAAAAAAAAAAAAA', 'bc', 'QNGRK QIHCL GWSCE'), \r
+    ('AAAAAAAAAAAAAAA', 'bcd', 'FMUBY BMAXH NQXCJ'), \r
+    ('AAAAAAAAAAAAAAAAAAAAAAAAA', 'cryptonomicon', \r
+     'SUGSR SXSWQ RMXOH IPBFP XARYQ'),\r
+    ('SOLITAIRE','cryptonomicon','KIRAK SFJAN')\r
+)\r
+\r
+def usage():\r
+    print """Usage:\r
+    sol.py {-e | -d} _key_ < _file_\r
+    sol.py -test\r
+    \r
+    N.B. WinNT requires "python sol.py ..."\r
+    for input redirection to work (NT bug).\r
+    """\r
+    sys.exit(2)\r
+\r
+if __name__ == '__main__':\r
+    args = sys.argv\r
+    if len(args) < 2:\r
+        usage()\r
+    elif args[1] == '-test':\r
+        s = Solitaire()\r
+        for txt, key, cipher in testCases:\r
+            coded = s.encrypt(txt, key)\r
+            assert cipher == coded\r
+            decoded = s.decrypt(coded, key)\r
+            assert decoded[:len(txt)] == string.upper(txt)\r
+        print 'All tests passed.'\r
+    elif len(args) < 3:\r
+        usage()\r
+    elif args[1] == '-e':\r
+        print Solitaire().encrypt(sys.stdin.read(), args[2])\r
+    elif args[1] == '-d':\r
+        print Solitaire().decrypt(sys.stdin.read(), args[2])\r
+    else:\r
+        usage()\r