#!/usr/local/bin/python # $Id: serpref.py,v 1.19 1998/09/02 21:28:02 fms Exp $ # # Python reference implementation of Serpent. # # Written by Frank Stajano, # Olivetti Oracle Research Laboratory <http://www.orl.co.uk/~fms/> and # Cambridge University Computer Laboratory <http://www.cl.cam.ac.uk/~fms27/>. # # (c) 1998 Olivetti Oracle Research Laboratory (ORL) # # Original (Python) Serpent reference development started on 1998 02 12. # C implementation development started on 1998 03 04. # # Serpent cipher invented by Ross Anderson, Eli Biham, Lars Knudsen. # Serpent is a candidate for the Advanced Encryption Standard. # -------------------------------------------------------------- """This is an illustrative reference implementation of the Serpent cipher invented by Eli Biham, Ross Anderson, Lars Knudsen. It is written for the human reader more than for the machine and, as such, it is optimised for clarity rather than speed. ("Premature optimisation is the root of all evil.") It can print out all the intermediate results (such as the subkeys) for a given input and key so that implementers debugging erroneous code can quickly verify which one of the building blocks is giving the wrong answers. This version implements Serpent-1, i.e. the variant defined in the final submission to NIST. """ # -------------------------------------------------------------- # Requires python 1.5, freely available from http://www.python.org/ # -------------------------------------------------------------- import string import sys import getopt import re # -------------------------------------------------------------- # Functions used in the formal description of the cipher def S(box, input): """Apply S-box number 'box' to 4-bit bitstring 'input' and return a 4-bit bitstring as the result.""" return SBoxBitstring[box%8][input] # There used to be 32 different S-boxes in serpent-0. Now there are # only 8, each of which is used 4 times (Sboxes 8, 16, 24 are all # identical to Sbox 0, etc). Hence the %8. def SInverse(box, output): """Apply S-box number 'box' in reverse to 4-bit bitstring 'output' and return a 4-bit bitstring (the input) as the result.""" return SBoxBitstringInverse[box%8][output] def SHat(box, input): """Apply a parallel array of 32 copies of S-box number 'box' to the 128-bit bitstring 'input' and return a 128-bit bitstring as the result.""" result = "" for i in range(32): result = result + S(box, input[4*i:4*(i+1)]) return result def SHatInverse(box, output): """Apply, in reverse, a parallel array of 32 copies of S-box number 'box' to the 128-bit bitstring 'output' and return a 128-bit bitstring (the input) as the result.""" result = "" for i in range(32): result = result + SInverse(box, output[4*i:4*(i+1)]) return result def SBitslice(box, words): """Take 'words', a list of 4 32-bit bitstrings, least significant word first. Return a similar list of 4 32-bit bitstrings obtained as follows. For each bit position from 0 to 31, apply S-box number 'box' to the 4 input bits coming from the current position in each of the items in 'words'; and put the 4 output bits in the corresponding positions in the output words.""" result = ["", "", "", ""] for i in range(32): # ideally in parallel quad = S(box, words[0][i] + words[1][i] + words[2][i] + words[3][i]) for j in range(4): result[j] = result[j] + quad[j] return result def SBitsliceInverse(box, words): """Take 'words', a list of 4 32-bit bitstrings, least significant word first. Return a similar list of 4 32-bit bitstrings obtained as follows. For each bit position from 0 to 31, apply S-box number 'box' in reverse to the 4 output bits coming from the current position in each of the items in the supplied 'words'; and put the 4 input bits in the corresponding positions in the returned words.""" result = ["", "", "", ""] for i in range(32): # ideally in parallel quad = SInverse( box, words[0][i] + words[1][i] + words[2][i] + words[3][i]) for j in range(4): result[j] = result[j] + quad[j] return result def LT(input): """Apply the table-based version of the linear transformation to the 128-bit string 'input' and return a 128-bit string as the result.""" if len(input) != 128: raise ValueError, "input to LT is not 128 bit long" result = "" for i in range(len(LTTable)): outputBit = "0" for j in LTTable[i]: outputBit = xor(outputBit, input[j]) result = result + outputBit return result def LTInverse(output): """Apply the table-based version of the inverse of the linear transformation to the 128-bit string 'output' and return a 128-bit string (the input) as the result.""" if len(output) != 128: raise ValueError, "input to inverse LT is not 128 bit long" result = "" for i in range(len(LTTableInverse)): inputBit = "0" for j in LTTableInverse[i]: inputBit = xor(inputBit, output[j]) result = result + inputBit return result def LTBitslice(X): """Apply the equations-based version of the linear transformation to 'X', a list of 4 32-bit bitstrings, least significant bitstring first, and return another list of 4 32-bit bitstrings as the result.""" X[0] = rotateLeft(X[0], 13) X[2] = rotateLeft(X[2], 3) X[1] = xor(X[1], X[0], X[2]) X[3] = xor(X[3], X[2], shiftLeft(X[0], 3)) X[1] = rotateLeft(X[1], 1) X[3] = rotateLeft(X[3], 7) X[0] = xor(X[0], X[1], X[3]) X[2] = xor(X[2], X[3], shiftLeft(X[1], 7)) X[0] = rotateLeft(X[0], 5) X[2] = rotateLeft(X[2], 22) return X def LTBitsliceInverse(X): """Apply, in reverse, the equations-based version of the linear transformation to 'X', a list of 4 32-bit bitstrings, least significant bitstring first, and return another list of 4 32-bit bitstrings as the result.""" X[2] = rotateRight(X[2], 22) X[0] = rotateRight(X[0], 5) X[2] = xor(X[2], X[3], shiftLeft(X[1], 7)) X[0] = xor(X[0], X[1], X[3]) X[3] = rotateRight(X[3], 7) X[1] = rotateRight(X[1], 1) X[3] = xor(X[3], X[2], shiftLeft(X[0], 3)) X[1] = xor(X[1], X[0], X[2]) X[2] = rotateRight(X[2], 3) X[0] = rotateRight(X[0], 13) return X def IP(input): """Apply the Initial Permutation to the 128-bit bitstring 'input' and return a 128-bit bitstring as the result.""" return applyPermutation(IPTable, input) def FP(input): """Apply the Final Permutation to the 128-bit bitstring 'input' and return a 128-bit bitstring as the result.""" return applyPermutation(FPTable, input) def IPInverse(output): """Apply the Initial Permutation in reverse.""" return FP(output) def FPInverse(output): """Apply the Final Permutation in reverse.""" return IP(output) def applyPermutation(permutationTable, input): """Apply the permutation specified by the 128-element list 'permutationTable' to the 128-bit bitstring 'input' and return a 128-bit bitstring as the result.""" if len(input) != len(permutationTable): raise ValueError, "input size (%d) doesn't match perm table size (%d)"\ % (len(input), len(permutationTable)) result = "" for i in range(len(permutationTable)): result = result + input[permutationTable[i]] return result def R(i, BHati, KHat): """Apply round 'i' to the 128-bit bitstring 'BHati', returning another 128-bit bitstring (conceptually BHatiPlus1). Do this using the appropriately numbered subkey(s) from the 'KHat' list of 33 128-bit bitstrings.""" O.show("BHati", BHati, "(i=%2d) BHati" % i) xored = xor(BHati, KHat[i]) O.show("xored", xored, "(i=%2d) xored" % i) SHati = SHat(i, xored) O.show("SHati", SHati, "(i=%2d) SHati" % i) if 0 <= i <= r-2: BHatiPlus1 = LT(SHati) elif i == r-1: BHatiPlus1 = xor(SHati, KHat[r]) else: raise ValueError, "round %d is out of 0..%d range" % (i, r-1) O.show("BHatiPlus1", BHatiPlus1, "(i=%2d) BHatiPlus1" % i) return BHatiPlus1 def RInverse(i, BHatiPlus1, KHat): """Apply round 'i' in reverse to the 128-bit bitstring 'BHatiPlus1', returning another 128-bit bitstring (conceptually BHati). Do this using the appropriately numbered subkey(s) from the 'KHat' list of 33 128-bit bitstrings.""" O.show("BHatiPlus1", BHatiPlus1, "(i=%2d) BHatiPlus1" % i) if 0 <= i <= r-2: SHati = LTInverse(BHatiPlus1) elif i == r-1: SHati = xor(BHatiPlus1, KHat[r]) else: raise ValueError, "round %d is out of 0..%d range" % (i, r-1) O.show("SHati", SHati, "(i=%2d) SHati" % i) xored = SHatInverse(i, SHati) O.show("xored", xored, "(i=%2d) xored" % i) BHati = xor(xored, KHat[i]) O.show("BHati", BHati, "(i=%2d) BHati" % i) return BHati def RBitslice(i, Bi, K): """Apply round 'i' (bitslice version) to the 128-bit bitstring 'Bi' and return another 128-bit bitstring (conceptually B i+1). Use the appropriately numbered subkey(s) from the 'K' list of 33 128-bit bitstrings.""" O.show("Bi", Bi, "(i=%2d) Bi" % i) # 1. Key mixing xored = xor (Bi, K[i]) O.show("xored", xored, "(i=%2d) xored" % i) # 2. S Boxes Si = SBitslice(i, quadSplit(xored)) # Input and output to SBitslice are both lists of 4 32-bit bitstrings O.show("Si", Si, "(i=%2d) Si" % i, "tlb") # 3. Linear Transformation if i == r-1: # In the last round, replaced by an additional key mixing BiPlus1 = xor(quadJoin(Si), K[r]) else: BiPlus1 = quadJoin(LTBitslice(Si)) # BIPlus1 is a 128-bit bitstring O.show("BiPlus1", BiPlus1, "(i=%2d) BiPlus1" % i) return BiPlus1 def RBitsliceInverse(i, BiPlus1, K): """Apply the inverse of round 'i' (bitslice version) to the 128-bit bitstring 'BiPlus1' and return another 128-bit bitstring (conceptually B i). Use the appropriately numbered subkey(s) from the 'K' list of 33 128-bit bitstrings.""" O.show("BiPlus1", BiPlus1, "(i=%2d) BiPlus1" % i) # 3. Linear Transformation if i == r-1: # In the last round, replaced by an additional key mixing Si = quadSplit(xor(BiPlus1, K[r])) else: Si = LTBitsliceInverse(quadSplit(BiPlus1)) # SOutput (same as LTInput) is a list of 4 32-bit bitstrings O.show("Si", Si, "(i=%2d) Si" % i, "tlb") # 2. S Boxes xored = SBitsliceInverse(i, Si) # SInput and SOutput are both lists of 4 32-bit bitstrings O.show("xored", xored, "(i=%2d) xored" % i) # 1. Key mixing Bi = xor (quadJoin(xored), K[i]) O.show("Bi", Bi, "(i=%2d) Bi" % i) return Bi def encrypt(plainText, userKey): """Encrypt the 128-bit bitstring 'plainText' with the 256-bit bitstring 'userKey', using the normal algorithm, and return a 128-bit ciphertext bitstring.""" O.show("fnTitle", "encrypt", None, "tu") O.show("plainText", plainText, "plainText") O.show("userKey", userKey, "userKey") K, KHat = makeSubkeys(userKey) BHat = IP(plainText) # BHat_0 at this stage for i in range(r): BHat = R(i, BHat, KHat) # Produce BHat_i+1 from BHat_i # BHat is now _32 i.e. _r C = FP(BHat) O.show("cipherText", C, "cipherText") return C def encryptBitslice(plainText, userKey): """Encrypt the 128-bit bitstring 'plainText' with the 256-bit bitstring 'userKey', using the bitslice algorithm, and return a 128-bit ciphertext bitstring.""" O.show("fnTitle", "encryptBitslice", None, "tu") O.show("plainText", plainText, "plainText") O.show("userKey", userKey, "userKey") K, KHat = makeSubkeys(userKey) B = plainText # B_0 at this stage for i in range(r): B = RBitslice(i, B, K) # Produce B_i+1 from B_i # B is now _r O.show("cipherText", B, "cipherText") return B def decrypt(cipherText, userKey): """Decrypt the 128-bit bitstring 'cipherText' with the 256-bit bitstring 'userKey', using the normal algorithm, and return a 128-bit plaintext bitstring.""" O.show("fnTitle", "decrypt", None, "tu") O.show("cipherText", cipherText, "cipherText") O.show("userKey", userKey, "userKey") K, KHat = makeSubkeys(userKey) BHat = FPInverse(cipherText) # BHat_r at this stage for i in range(r-1, -1, -1): # from r-1 down to 0 included BHat = RInverse(i, BHat, KHat) # Produce BHat_i from BHat_i+1 # BHat is now _0 plainText = IPInverse(BHat) O.show("plainText", plainText, "plainText") return plainText def decryptBitslice(cipherText, userKey): """Decrypt the 128-bit bitstring 'cipherText' with the 256-bit bitstring 'userKey', using the bitslice algorithm, and return a 128-bit plaintext bitstring.""" O.show("fnTitle", "decryptBitslice", None, "tu") O.show("cipherText", cipherText, "cipherText") O.show("userKey", userKey, "userKey") K, KHat = makeSubkeys(userKey) B = cipherText # B_r at this stage for i in range(r-1, -1, -1): # from r-1 down to 0 included B = RBitsliceInverse(i, B, K) # Produce B_i from B_i+1 # B is now _0 O.show("plainText", B, "plainText") return B def makeSubkeys(userKey): """Given the 256-bit bitstring 'userKey' (shown as K in the paper, but we can't use that name because of a collision with K[i] used later for something else), return two lists (conceptually K and KHat) of 33 128-bit bitstrings each.""" # Because in Python I can't index a list from anything other than 0, # I use a dictionary instead to legibly represent the w_i that are # indexed from -8. # We write the key as 8 32-bit words w-8 ... w-1 # ENOTE: w-8 is the least significant word w = {} for i in range(-8, 0): w[i] = userKey[(i+8)*32:(i+9)*32] O.show("wi", w[i], "(i=%2d) wi" % i) # We expand these to a prekey w0 ... w131 with the affine recurrence for i in range(132): w[i] = rotateLeft( xor(w[i-8], w[i-5], w[i-3], w[i-1], bitstring(phi, 32), bitstring(i,32)), 11) O.show("wi", w[i], "(i=%2d) wi" % i) # The round keys are now calculated from the prekeys using the S-boxes # in bitslice mode. Each k[i] is a 32-bit bitstring. k = {} for i in range(r+1): whichS = (r + 3 - i) % r k[0+4*i] = "" k[1+4*i] = "" k[2+4*i] = "" k[3+4*i] = "" for j in range(32): # for every bit in the k and w words # ENOTE: w0 and k0 are the least significant words, w99 and k99 # the most. input = w[0+4*i][j] + w[1+4*i][j] + w[2+4*i][j] + w[3+4*i][j] output = S(whichS, input) for l in range(4): k[l+4*i] = k[l+4*i] + output[l] # We then renumber the 32 bit values k_j as 128 bit subkeys K_i. K = [] for i in range(33): # ENOTE: k4i is the least significant word, k4i+3 the most. K.append(k[4*i] + k[4*i+1] + k[4*i+2] + k[4*i+3]) # We now apply IP to the round key in order to place the key bits in # the correct column KHat = [] for i in range(33): KHat.append(IP(K[i])) O.show("Ki", K[i], "(i=%2d) Ki" % i) O.show("KHati", KHat[i], "(i=%2d) KHati" % i) return K, KHat def makeLongKey(k): """Take a key k in bitstring format. Return the long version of that key.""" l = len(k) if l % 32 != 0 or l < 64 or l > 256: raise ValueError, "Invalid key length (%d bits)" % l if l == 256: return k else: return k + "1" + "0"*(256 -l -1) # -------------------------------------------------------------- # Generic bit-level primitives # Internally, we represent the numbers manipulated by the cipher in a # format that we call 'bitstring'. This is a string of "0" and "1" # characters containing the binary representation of the number in # little-endian format (so that subscripting with an index of i gives bit # number i, corresponding to a weight of 2^i). This representation is only # defined for nonnegative numbers (you can see why: think of the great # unnecessary mess that would result from sign extension, two's complement # and so on). Example: 10 decimal is "0101" in bitstring format. def bitstring(n, minlen=1): """Translate n from integer to bitstring, padding it with 0s as necessary to reach the minimum length 'minlen'. 'n' must be >= 0 since the bitstring format is undefined for negative integers. Note that, while the bitstring format can represent arbitrarily large numbers, this is not so for Python's normal integer type: on a 32-bit machine, values of n >= 2^31 need to be expressed as python long integers or they will "look" negative and won't work. E.g. 0x80000000 needs to be passed in as 0x80000000L, or it will be taken as -2147483648 instead of +2147483648L. EXAMPLE: bitstring(10, 8) -> "01010000" """ if minlen < 1: raise ValueError, "a bitstring must have at least 1 char" if n < 0: raise ValueError, "bitstring representation undefined for neg numbers" result = "" while n > 0: if n & 1: result = result + "1" else: result = result + "0" n = n >> 1 if len(result) < minlen: result = result + "0" * (minlen - len(result)) return result def binaryXor(n1, n2): """Return the xor of two bitstrings of equal length as another bitstring of the same length. EXAMPLE: binaryXor("10010", "00011") -> "10001" """ if len(n1) != len(n2): raise ValueError, "can't xor bitstrings of different " + \ "lengths (%d and %d)" % (len(n1), len(n2)) # We assume that they are genuine bitstrings instead of just random # character strings. result = "" for i in range(len(n1)): if n1[i] == n2[i]: result = result + "0" else: result = result + "1" return result def xor(*args): """Return the xor of an arbitrary number of bitstrings of the same length as another bitstring of the same length. EXAMPLE: xor("01", "11", "10") -> "00" """ if args == []: raise ValueError, "at least one argument needed" result = args[0] for arg in args[1:]: result = binaryXor(result, arg) return result def rotateLeft(input, places): """Take a bitstring 'input' of arbitrary length. Rotate it left by 'places' places. Left means that the 'places' most significant bits are taken out and reinserted as the least significant bits. Note that, because the bitstring representation is little-endian, the visual effect is actually that of rotating the string to the right. EXAMPLE: rotateLeft("000111", 2) -> "110001" """ p = places % len(input) return input[-p:] + input[:-p] def rotateRight(input, places): return rotateLeft(input, -places) def shiftLeft(input, p): """Take a bitstring 'input' of arbitrary length. Shift it left by 'p' places. Left means that the 'p' most significant bits are shifted out and dropped, while 'p' 0s are inserted in the the least significant bits. Note that, because the bitstring representation is little-endian, the visual effect is actually that of shifting the string to the right. Negative values for 'p' are allowed, with the effect of shifting right instead (i.e. the 0s are inserted in the most significant bits). EXAMPLE: shiftLeft("000111", 2) -> "000001" shiftLeft("000111", -2) -> "011100" """ if abs(p) >= len(input): # Everything gets shifted out anyway return "0" * len(input) if p < 0: # Shift right instead return input[-p:] + "0" * len(input[:-p]) elif p == 0: return input else: # p > 0, normal case return "0" * len(input[-p:]) + input[:-p] def shiftRight(input, p): """Take a bitstring 'input' and shift it right by 'p' places. See the doc for shiftLeft for more details.""" return shiftLeft(input, -p) def keyLengthInBitsOf(k): """Take a string k in I/O format and return the number of bits in it.""" return len(k) * 4 # -------------------------------------------------------------- # Hex conversion functions # For I/O we use BIG-ENDIAN hexstrings. Do not get confused: internal stuff # is LITTLE-ENDIAN bitstrings (so that digit i has weight 2^i) while # external stuff is in BIG-ENDIAN hexstrings (so that it's shorter and it # looks like the numbers you normally write down). The external (I/O) # representation is the same as used by the C reference implementation. bin2hex = { # Given a 4-char bitstring, return the corresponding 1-char hexstring "0000": "0", "1000": "1", "0100": "2", "1100": "3", "0010": "4", "1010": "5", "0110": "6", "1110": "7", "0001": "8", "1001": "9", "0101": "a", "1101": "b", "0011": "c", "1011": "d", "0111": "e", "1111": "f", } # Make the reverse lookup table too hex2bin = {} for (bin, hex) in bin2hex.items(): hex2bin[hex] = bin def bitstring2hexstring(b): """Take bitstring 'b' and return the corresponding hexstring.""" result = "" l = len(b) if l % 4: b = b + "0" * (4-(l%4)) for i in range(0, len(b), 4): result = result+bin2hex[b[i:i+4]] return reverseString(result) def hexstring2bitstring(h): """Take hexstring 'h' and return the corresponding bitstring.""" result = "" for c in reverseString(h): result = result + hex2bin[c] return result def reverseString(s): l = list(s) l.reverse() return string.join(l, "") # -------------------------------------------------------------- # Format conversions def quadSplit(b128): """Take a 128-bit bitstring and return it as a list of 4 32-bit bitstrings, least significant bitstring first.""" if len(b128) != 128: raise ValueError, "must be 128 bits long, not " + len(b128) result = [] for i in range(4): result.append(b128[(i*32):(i+1)*32]) return result def quadJoin(l4x32): """Take a list of 4 32-bit bitstrings and return it as a single 128-bit bitstring obtained by concatenating the internal ones.""" if len(l4x32) != 4: raise ValueError, "need a list of 4 bitstrings, not " + len(l4x32) return l4x32[0] + l4x32[1] + l4x32[2] + l4x32[3] # -------------------------------------------------- # Seeing what happens inside class Observer: """An object of this class can selectively display the values of the variables you want to observe while the program is running. There are tags that you can switch on or off. You sprinkle show() statements throughout the program to show the value of a variable at a particular point: show() will display the relevant variable only if the corresponding tag is currently on. The special tag "ALL" forces all show() statements to display their variable.""" typesOfVariable = { "tu": "unknown", "tb": "bitstring", "tlb": "list of bitstrings",} def __init__(self, tags=[]): self.tags = {} for tag in tags: self.tags[tag] = 1 def addTag(self, *tags): """Add the supplied tag(s) to those that are currently active, i.e. those that, if a corresponding "show()" is executed, will print something.""" for t in tags: self.tags[t] = 1 def removeTag(self, *tags): """Remove the supplied tag(s) from those currently active.""" for t in tags: if t in self.tags.keys(): del self.tags[t] def show(self, tag, variable, label=None, type="tb"): """Conditionally print a message with the current value of 'variable'. The message will only be printed if the supplied 'tag' is among the active ones (or if the 'ALL' tag is active). The 'label', if not null, is printed before the value of the 'variable'; if it is null, it is substituted with the 'tag'. The 'type' of the 'variable' (giving us a clue on how to print it) must be one of Observer.typesOfVariable.""" if label == None: label = tag if "ALL" in self.tags.keys() or tag in self.tags.keys(): if type == "tu": output = `variable` elif type == "tb": output = bitstring2hexstring(variable) elif type == "tlb": output = "" for item in variable: output = output + " %s" % bitstring2hexstring(item) output = "[" + output[1:] + "]" else: raise ValueError, "unknown type: %s. Valid ones are %s" % ( type, self.typesOfVariable.keys()) print label, if output: print "=", output else: print # We make one global observer object that is always available O = Observer(["plainText", "userKey", "cipherText"]) # -------------------------------------------------------------- # Constants phi = 0x9e3779b9L r = 32 # -------------------------------------------------------------- # Data tables # Each element of this list corresponds to one S-box. Each S-box in turn is # a list of 16 integers in the range 0..15, without repetitions. Having the # value v (say, 14) in position p (say, 0) means that if the input to that # S-box is the pattern p (0, or 0x0) then the output will be the pattern v # (14, or 0xe). SBoxDecimalTable = [ [ 3, 8,15, 1,10, 6, 5,11,14,13, 4, 2, 7, 0, 9,12 ], # S0 [15,12, 2, 7, 9, 0, 5,10, 1,11,14, 8, 6,13, 3, 4 ], # S1 [ 8, 6, 7, 9, 3,12,10,15,13, 1,14, 4, 0,11, 5, 2 ], # S2 [ 0,15,11, 8,12, 9, 6, 3,13, 1, 2, 4,10, 7, 5,14 ], # S3 [ 1,15, 8, 3,12, 0,11, 6, 2, 5, 4,10, 9,14, 7,13 ], # S4 [15, 5, 2,11, 4,10, 9,12, 0, 3,14, 8,13, 6, 7, 1 ], # S5 [ 7, 2,12, 5, 8, 4, 6,11,14, 9, 1,15,13, 3,10, 0 ], # S6 [ 1,13,15, 0,14, 8, 2,11, 7, 4,12,10, 9, 3, 5, 6 ], # S7 ] # NB: in serpent-0, this was a list of 32 sublists (for the 32 different # S-boxes derived from DES). In the final version of Serpent only 8 S-boxes # are used, with each one being reused 4 times. # Make another version of this table as a list of dictionaries: one # dictionary per S-box, where the value of the entry indexed by i tells you # the output configuration when the input is i, with both the index and the # value being bitstrings. Make also the inverse: another list of # dictionaries, one per S-box, where each dictionary gets the output of the # S-box as the key and gives you the input, with both values being 4-bit # bitstrings. SBoxBitstring = [] SBoxBitstringInverse = [] for line in SBoxDecimalTable: dict = {} inverseDict = {} for i in range(len(line)): index = bitstring(i, 4) value = bitstring(line[i], 4) dict[index] = value inverseDict[value] = index SBoxBitstring.append(dict) SBoxBitstringInverse.append(inverseDict) # The Initial and Final permutations are each represented by one list # containing the integers in 0..127 without repetitions. Having value v # (say, 32) at position p (say, 1) means that the output bit at position p # (1) comes from the input bit at position v (32). IPTable = [ 0, 32, 64, 96, 1, 33, 65, 97, 2, 34, 66, 98, 3, 35, 67, 99, 4, 36, 68, 100, 5, 37, 69, 101, 6, 38, 70, 102, 7, 39, 71, 103, 8, 40, 72, 104, 9, 41, 73, 105, 10, 42, 74, 106, 11, 43, 75, 107, 12, 44, 76, 108, 13, 45, 77, 109, 14, 46, 78, 110, 15, 47, 79, 111, 16, 48, 80, 112, 17, 49, 81, 113, 18, 50, 82, 114, 19, 51, 83, 115, 20, 52, 84, 116, 21, 53, 85, 117, 22, 54, 86, 118, 23, 55, 87, 119, 24, 56, 88, 120, 25, 57, 89, 121, 26, 58, 90, 122, 27, 59, 91, 123, 28, 60, 92, 124, 29, 61, 93, 125, 30, 62, 94, 126, 31, 63, 95, 127, ] FPTable = [ 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124, 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, 101, 105, 109, 113, 117, 121, 125, 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 114, 118, 122, 126, 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99, 103, 107, 111, 115, 119, 123, 127, ] # The Linear Transformation is represented as a list of 128 lists, one for # each output bit. Each one of the 128 lists is composed of a variable # number of integers in 0..127 specifying the positions of the input bits # that must be XORed together (say, 72, 144 and 125) to yield the output # bit corresponding to the position of that list (say, 1). LTTable = [ [16, 52, 56, 70, 83, 94, 105], [72, 114, 125], [2, 9, 15, 30, 76, 84, 126], [36, 90, 103], [20, 56, 60, 74, 87, 98, 109], [1, 76, 118], [2, 6, 13, 19, 34, 80, 88], [40, 94, 107], [24, 60, 64, 78, 91, 102, 113], [5, 80, 122], [6, 10, 17, 23, 38, 84, 92], [44, 98, 111], [28, 64, 68, 82, 95, 106, 117], [9, 84, 126], [10, 14, 21, 27, 42, 88, 96], [48, 102, 115], [32, 68, 72, 86, 99, 110, 121], [2, 13, 88], [14, 18, 25, 31, 46, 92, 100], [52, 106, 119], [36, 72, 76, 90, 103, 114, 125], [6, 17, 92], [18, 22, 29, 35, 50, 96, 104], [56, 110, 123], [1, 40, 76, 80, 94, 107, 118], [10, 21, 96], [22, 26, 33, 39, 54, 100, 108], [60, 114, 127], [5, 44, 80, 84, 98, 111, 122], [14, 25, 100], [26, 30, 37, 43, 58, 104, 112], [3, 118], [9, 48, 84, 88, 102, 115, 126], [18, 29, 104], [30, 34, 41, 47, 62, 108, 116], [7, 122], [2, 13, 52, 88, 92, 106, 119], [22, 33, 108], [34, 38, 45, 51, 66, 112, 120], [11, 126], [6, 17, 56, 92, 96, 110, 123], [26, 37, 112], [38, 42, 49, 55, 70, 116, 124], [2, 15, 76], [10, 21, 60, 96, 100, 114, 127], [30, 41, 116], [0, 42, 46, 53, 59, 74, 120], [6, 19, 80], [3, 14, 25, 100, 104, 118], [34, 45, 120], [4, 46, 50, 57, 63, 78, 124], [10, 23, 84], [7, 18, 29, 104, 108, 122], [38, 49, 124], [0, 8, 50, 54, 61, 67, 82], [14, 27, 88], [11, 22, 33, 108, 112, 126], [0, 42, 53], [4, 12, 54, 58, 65, 71, 86], [18, 31, 92], [2, 15, 26, 37, 76, 112, 116], [4, 46, 57], [8, 16, 58, 62, 69, 75, 90], [22, 35, 96], [6, 19, 30, 41, 80, 116, 120], [8, 50, 61], [12, 20, 62, 66, 73, 79, 94], [26, 39, 100], [10, 23, 34, 45, 84, 120, 124], [12, 54, 65], [16, 24, 66, 70, 77, 83, 98], [30, 43, 104], [0, 14, 27, 38, 49, 88, 124], [16, 58, 69], [20, 28, 70, 74, 81, 87, 102], [34, 47, 108], [0, 4, 18, 31, 42, 53, 92], [20, 62, 73], [24, 32, 74, 78, 85, 91, 106], [38, 51, 112], [4, 8, 22, 35, 46, 57, 96], [24, 66, 77], [28, 36, 78, 82, 89, 95, 110], [42, 55, 116], [8, 12, 26, 39, 50, 61, 100], [28, 70, 81], [32, 40, 82, 86, 93, 99, 114], [46, 59, 120], [12, 16, 30, 43, 54, 65, 104], [32, 74, 85], [36, 90, 103, 118], [50, 63, 124], [16, 20, 34, 47, 58, 69, 108], [36, 78, 89], [40, 94, 107, 122], [0, 54, 67], [20, 24, 38, 51, 62, 73, 112], [40, 82, 93], [44, 98, 111, 126], [4, 58, 71], [24, 28, 42, 55, 66, 77, 116], [44, 86, 97], [2, 48, 102, 115], [8, 62, 75], [28, 32, 46, 59, 70, 81, 120], [48, 90, 101], [6, 52, 106, 119], [12, 66, 79], [32, 36, 50, 63, 74, 85, 124], [52, 94, 105], [10, 56, 110, 123], [16, 70, 83], [0, 36, 40, 54, 67, 78, 89], [56, 98, 109], [14, 60, 114, 127], [20, 74, 87], [4, 40, 44, 58, 71, 82, 93], [60, 102, 113], [3, 18, 72, 114, 118, 125], [24, 78, 91], [8, 44, 48, 62, 75, 86, 97], [64, 106, 117], [1, 7, 22, 76, 118, 122], [28, 82, 95], [12, 48, 52, 66, 79, 90, 101], [68, 110, 121], [5, 11, 26, 80, 122, 126], [32, 86, 99], ] # The following table is necessary for the non-bitslice decryption. LTTableInverse = [ [53, 55, 72], [1, 5, 20, 90], [15, 102], [3, 31, 90], [57, 59, 76], [5, 9, 24, 94], [19, 106], [7, 35, 94], [61, 63, 80], [9, 13, 28, 98], [23, 110], [11, 39, 98], [65, 67, 84], [13, 17, 32, 102], [27, 114], [1, 3, 15, 20, 43, 102], [69, 71, 88], [17, 21, 36, 106], [1, 31, 118], [5, 7, 19, 24, 47, 106], [73, 75, 92], [21, 25, 40, 110], [5, 35, 122], [9, 11, 23, 28, 51, 110], [77, 79, 96], [25, 29, 44, 114], [9, 39, 126], [13, 15, 27, 32, 55, 114], [81, 83, 100], [1, 29, 33, 48, 118], [2, 13, 43], [1, 17, 19, 31, 36, 59, 118], [85, 87, 104], [5, 33, 37, 52, 122], [6, 17, 47], [5, 21, 23, 35, 40, 63, 122], [89, 91, 108], [9, 37, 41, 56, 126], [10, 21, 51], [9, 25, 27, 39, 44, 67, 126], [93, 95, 112], [2, 13, 41, 45, 60], [14, 25, 55], [2, 13, 29, 31, 43, 48, 71], [97, 99, 116], [6, 17, 45, 49, 64], [18, 29, 59], [6, 17, 33, 35, 47, 52, 75], [101, 103, 120], [10, 21, 49, 53, 68], [22, 33, 63], [10, 21, 37, 39, 51, 56, 79], [105, 107, 124], [14, 25, 53, 57, 72], [26, 37, 67], [14, 25, 41, 43, 55, 60, 83], [0, 109, 111], [18, 29, 57, 61, 76], [30, 41, 71], [18, 29, 45, 47, 59, 64, 87], [4, 113, 115], [22, 33, 61, 65, 80], [34, 45, 75], [22, 33, 49, 51, 63, 68, 91], [8, 117, 119], [26, 37, 65, 69, 84], [38, 49, 79], [26, 37, 53, 55, 67, 72, 95], [12, 121, 123], [30, 41, 69, 73, 88], [42, 53, 83], [30, 41, 57, 59, 71, 76, 99], [16, 125, 127], [34, 45, 73, 77, 92], [46, 57, 87], [34, 45, 61, 63, 75, 80, 103], [1, 3, 20], [38, 49, 77, 81, 96], [50, 61, 91], [38, 49, 65, 67, 79, 84, 107], [5, 7, 24], [42, 53, 81, 85, 100], [54, 65, 95], [42, 53, 69, 71, 83, 88, 111], [9, 11, 28], [46, 57, 85, 89, 104], [58, 69, 99], [46, 57, 73, 75, 87, 92, 115], [13, 15, 32], [50, 61, 89, 93, 108], [62, 73, 103], [50, 61, 77, 79, 91, 96, 119], [17, 19, 36], [54, 65, 93, 97, 112], [66, 77, 107], [54, 65, 81, 83, 95, 100, 123], [21, 23, 40], [58, 69, 97, 101, 116], [70, 81, 111], [58, 69, 85, 87, 99, 104, 127], [25, 27, 44], [62, 73, 101, 105, 120], [74, 85, 115], [3, 62, 73, 89, 91, 103, 108], [29, 31, 48], [66, 77, 105, 109, 124], [78, 89, 119], [7, 66, 77, 93, 95, 107, 112], [33, 35, 52], [0, 70, 81, 109, 113], [82, 93, 123], [11, 70, 81, 97, 99, 111, 116], [37, 39, 56], [4, 74, 85, 113, 117], [86, 97, 127], [15, 74, 85, 101, 103, 115, 120], [41, 43, 60], [8, 78, 89, 117, 121], [3, 90], [19, 78, 89, 105, 107, 119, 124], [45, 47, 64], [12, 82, 93, 121, 125], [7, 94], [0, 23, 82, 93, 109, 111, 123], [49, 51, 68], [1, 16, 86, 97, 125], [11, 98], [4, 27, 86, 97, 113, 115, 127], ] # -------------------------------------------------- # Handling command line arguments and stuff help = """ # $Id: serpref.py,v 1.19 1998/09/02 21:28:02 fms Exp $ # # Python reference implementation of Serpent. # # Written by Frank Stajano, # Olivetti Oracle Research Laboratory <http://www.orl.co.uk/~fms/> and # Cambridge University Computer Laboratory <http://www.cl.cam.ac.uk/~fms27/>. # # (c) 1998 Olivetti Oracle Research Laboratory (ORL) # # Original (Python) Serpent reference development started on 1998 02 12. # C implementation development started on 1998 03 04. # # Serpent cipher invented by Ross Anderson, Eli Biham, Lars Knudsen. # Serpent is a candidate for the Advanced Encryption Standard. Encrypts or decrypts one block of data using the Serpent cipher and optionally showing you what's going on inside at the various stages of the computation. SYNTAX: serpref mode [options] MODE is one of the following: -e -> encrypt -d -> decrypt -h -> help (the text you're reading right now) OPTIONS are: -p plainText -> The 128-bit value to be encrypted. Required in mode -e, ignored otherwise. Short texts are zeropadded. -c cipherText -> The 128-bit value to be decrypted. Required in mode -d, ignored otherwise. Short texts are zeropadded. -k key -> The value of the key (allowed lengths are from 64 to 256 bits, but must be a multiple of 32 bits). Keys shorter than 256 bits are internally transformed into the equivalent long keys (NOT the same as zeropadding!). Required for -e and -d. -t tagName -> Turn on the observer tag with that name. This means that any observer messages associated with this tag will now be displayed. This option may be specified several times to add multiple tags. The special tag ALL turns on all the messages. -b -> Use the bitslice version instead of the traditional version, which is otherwise used by default. Optional. TAGS: These are the tags of the quantities you can currently observe with -t. Names are modelled on the paper's notation. For the non-bitslice: BHati xored SHati BHatiPlus1 wi KHati For the bitslice: Bi xored Si BiPlus1 wi Ki Generic: plainText userKey cipherText testTitle fnTitle I/O FORMAT: All I/O is performed using hex numbers of the appropriate size, written as sequences of hex digits, most significant digit first (big-endian), without any leading or trailing markers such as 0x, &, h or whatever. Example: the number ten is "a" in four bits or "000a" in sixteen bits. USAGE EXAMPLES: serpref -e -k 123456789abcdef -p 0 Encrypt the plaintext "all zeros" with the given key. serpref -e -b -k 123456789abcdef -p 0 Same as above, but the extra -b requests bitslice operation. As things are, we won't notice the difference, but see below... serpref -e -b -k 123456789abcdef -p 0 -t Bi Same as above, but the "-t Bi" prints out all the intermediate results with a tag of Bi, allowing you to see what happens inside the rounds. Compare this with the following... serpref -e -k 123456789abcdef -p 0 -t BHati Same as above except that we are back to the non-bitslice version (there is no -b) and we are printing the items with the BHati tag (which is the equivalent of Bi for the non-bitslice version). serpref -e -k 123456789abcdef -p 0 -t xored -t SHati -t BHati Same as above but we are requesting even more details, basically looking at all the intermediate results of each round as well. (You could use the single magic tag -t ALL if you didn't want to have to find out the names of the individual tags.) """ def helpExit(message = None): print help if message: print "ERROR:", message sys.exit() def convertToBitstring(input, numBits): """Take a string 'input', theoretically in std I/O format, but in practice liable to contain any sort of crap since it's user supplied, and return its bitstring representation, normalised to numBits bits. Raise the appropriate variant of ValueError (with explanatory message) if anything can't be done (this includes the case where the 'input', while otherwise syntactically correct, can't be represented in 'numBits' bits).""" if re.match("^[0-9a-f]+$", input): bitstring = hexstring2bitstring(input) else: raise ValueError, "%s is not a valid hexstring" % input # assert: bitstring now contains the bitstring version of the input if len(bitstring) > numBits: # Last chance: maybe it's got some useless 0s... if re.match("^0+$", bitstring[numBits:]): bitstring = bitstring[:numBits] else: raise ValueError, "input too large to fit in %d bits" % numBits else: bitstring = bitstring + "0" * (numBits-len(bitstring)) return bitstring def main(): optList, rest = getopt.getopt(sys.argv[1:], "edhbt:k:p:c:") if rest: helpExit("Sorry, can't make sense of this: '%s'" % rest) # Transform the list of options into a more comfortable # dictionary. This only works with non-repeated options, though, so # tags (which are repeated) must be dealt with separately. options = {} for key, value in optList: if key == "-t": O.addTag(value) else: if key in options.keys(): helpExit("Multiple occurrences of " + key) else: options[string.strip(key)] = string.strip(value) # Not more than one mode mode = None for k in options.keys(): if k in ["-e", "-d", "-h"]: if mode: helpExit("you can only specify one mode") else: mode = k if not mode: helpExit("No mode specified") # Put plainText, userKey, cipherText in bitstring format. plainText = userKey = cipherText = None if options.has_key("-k"): bitsInKey = keyLengthInBitsOf(options["-k"]) rawKey = convertToBitstring(options["-k"], bitsInKey) userKey = makeLongKey(rawKey) if options.has_key("-p"): plainText = convertToBitstring(options["-p"], 128) if options.has_key("-c"): cipherText = convertToBitstring(options["-c"], 128) if mode == "-e" or mode == "-d": if not userKey: helpExit("-k (key) required with -e (encrypt) or -d (decrypt)") if mode == "-e": if not plainText: helpExit("-p (plaintext) is required when doing -e (encrypt)") if mode == "-d": if not cipherText: helpExit("-c (ciphertext) is required when doing -d (decrypt)") # Perform the action specified by the mode # NOTE that the observer will automatically print the basic stuff such # as plainText, userKey and cipherText (in the right format too), so we # only need to perform the action, without adding any extra print # statements here. if mode == "-e": if options.has_key("-b"): cipherText = encryptBitslice(plainText, userKey) else: cipherText = encrypt(plainText, userKey) elif mode == "-d": if options.has_key("-b"): plainText = decryptBitslice(cipherText, userKey) else: plainText = decrypt(cipherText, userKey) elif mode == "-s": O.addTag("testTitle", "fnTitle") printTest(test1(plainText, userKey)) printTest(test2(plainText, userKey)) printTest(test3(plainText, userKey)) else: helpExit() if __name__ == "__main__": main()
HTML 4.0/CSS generated by Frank Stajano's html-pretty-print
for Emacs.
If you view this page in a browser with Cascading Style
Sheets enabled, the listing appears beautified. Besides, the markup is
parametric and you can change the font characteristics of the various
syntactical elements by simply redefining the style sheet.