1 #!/usr/local/bin/python
3 # $Id: serpref.py,v 1.19 1998/09/02 21:28:02 fms Exp $
5 # Python reference implementation of Serpent.
7 # Written by Frank Stajano,
8 # Olivetti Oracle Research Laboratory <http://www.orl.co.uk/~fms/> and
9 # Cambridge University Computer Laboratory <http://www.cl.cam.ac.uk/~fms27/>.
11 # (c) 1998 Olivetti Oracle Research Laboratory (ORL)
13 # Original (Python) Serpent reference development started on 1998 02 12.
14 # C implementation development started on 1998 03 04.
16 # Serpent cipher invented by Ross Anderson, Eli Biham, Lars Knudsen.
17 # Serpent is a candidate for the Advanced Encryption Standard.
19 # --------------------------------------------------------------
21 """This is an illustrative reference implementation of the Serpent cipher
22 invented by Eli Biham, Ross Anderson, Lars Knudsen. It is written for the
23 human reader more than for the machine and, as such, it is optimised for
24 clarity rather than speed. ("Premature optimisation is the root of all
27 It can print out all the intermediate results (such as the subkeys) for a
28 given input and key so that implementers debugging erroneous code can
29 quickly verify which one of the building blocks is giving the wrong
32 This version implements Serpent-1, i.e. the variant defined in the final
36 # --------------------------------------------------------------
38 # --------------------------------------------------------------
41 def __init__(self
,key
):
42 key
= key
.encode('hex')
43 bitsInKey
= keyLengthInBitsOf(key
)
44 rawKey
= convertToBitstring(reverse(key
.lower()), bitsInKey
)
45 self
.userKey
= makeLongKey(rawKey
)
47 def encrypt(self
,block
):
48 plainText
= convertToBitstring(reverse(block
.encode("hex").lower()), 128)
49 cipherText
= encrypt(plainText
, self
.userKey
)
50 return reverse(bitstring2hexstring(cipherText
)).decode('hex')
52 def decrypt(self
,block
):
53 cipherText
= convertToBitstring(reverse(block
.encode("hex").lower()), 128)
54 plainText
= decrypt(cipherText
, self
.userKey
)
55 return reverse(bitstring2hexstring(plainText
)).decode('hex')
57 def get_block_size(self
):
60 def reverse(toreverse
):
62 for i
in range(len(toreverse
)/2):
63 out
+= toreverse
[len(toreverse
)-i
*2-2:len(toreverse
)-i
*2]
65 # --------------------------------------------------------------
67 # --------------------------------------------------------------
69 # --------------------------------------------------------------
70 # Requires python 1.5, freely available from http://www.python.org/
71 # --------------------------------------------------------------
77 # --------------------------------------------------------------
78 # Functions used in the formal description of the cipher
81 """Apply S-box number 'box' to 4-bit bitstring 'input' and return a
82 4-bit bitstring as the result."""
84 return SBoxBitstring
[box
%8][input]
85 # There used to be 32 different S-boxes in serpent-0. Now there are
86 # only 8, each of which is used 4 times (Sboxes 8, 16, 24 are all
87 # identical to Sbox 0, etc). Hence the %8.
89 def SInverse(box
, output
):
90 """Apply S-box number 'box' in reverse to 4-bit bitstring 'output' and
91 return a 4-bit bitstring (the input) as the result."""
93 return SBoxBitstringInverse
[box
%8][output
]
97 """Apply a parallel array of 32 copies of S-box number 'box' to the
98 128-bit bitstring 'input' and return a 128-bit bitstring as the
103 result
= result
+ S(box
, input[4*i
:4*(i
+1)])
106 def SHatInverse(box
, output
):
107 """Apply, in reverse, a parallel array of 32 copies of S-box number
108 'box' to the 128-bit bitstring 'output' and return a 128-bit bitstring
109 (the input) as the result."""
113 result
= result
+ SInverse(box
, output
[4*i
:4*(i
+1)])
117 def SBitslice(box
, words
):
118 """Take 'words', a list of 4 32-bit bitstrings, least significant word
119 first. Return a similar list of 4 32-bit bitstrings obtained as
120 follows. For each bit position from 0 to 31, apply S-box number 'box'
121 to the 4 input bits coming from the current position in each of the
122 items in 'words'; and put the 4 output bits in the corresponding
123 positions in the output words."""
125 result
= ["", "", "", ""]
126 for i
in range(32): # ideally in parallel
127 quad
= S(box
, words
[0][i
] + words
[1][i
] + words
[2][i
] + words
[3][i
])
129 result
[j
] = result
[j
] + quad
[j
]
132 def SBitsliceInverse(box
, words
):
133 """Take 'words', a list of 4 32-bit bitstrings, least significant word
134 first. Return a similar list of 4 32-bit bitstrings obtained as
135 follows. For each bit position from 0 to 31, apply S-box number 'box'
136 in reverse to the 4 output bits coming from the current position in
137 each of the items in the supplied 'words'; and put the 4 input bits in
138 the corresponding positions in the returned words."""
140 result
= ["", "", "", ""]
141 for i
in range(32): # ideally in parallel
143 box
, words
[0][i
] + words
[1][i
] + words
[2][i
] + words
[3][i
])
145 result
[j
] = result
[j
] + quad
[j
]
150 """Apply the table-based version of the linear transformation to the
151 128-bit string 'input' and return a 128-bit string as the result."""
153 if len(input) != 128:
154 raise ValueError, "input to LT is not 128 bit long"
157 for i
in range(len(LTTable
)):
160 outputBit
= xor(outputBit
, input[j
])
161 result
= result
+ outputBit
164 def LTInverse(output
):
165 """Apply the table-based version of the inverse of the linear
166 transformation to the 128-bit string 'output' and return a 128-bit
167 string (the input) as the result."""
169 if len(output
) != 128:
170 raise ValueError, "input to inverse LT is not 128 bit long"
173 for i
in range(len(LTTableInverse
)):
175 for j
in LTTableInverse
[i
]:
176 inputBit
= xor(inputBit
, output
[j
])
177 result
= result
+ inputBit
183 """Apply the equations-based version of the linear transformation to
184 'X', a list of 4 32-bit bitstrings, least significant bitstring first,
185 and return another list of 4 32-bit bitstrings as the result."""
187 X
[0] = rotateLeft(X
[0], 13)
188 X
[2] = rotateLeft(X
[2], 3)
189 X
[1] = xor(X
[1], X
[0], X
[2])
190 X
[3] = xor(X
[3], X
[2], shiftLeft(X
[0], 3))
191 X
[1] = rotateLeft(X
[1], 1)
192 X
[3] = rotateLeft(X
[3], 7)
193 X
[0] = xor(X
[0], X
[1], X
[3])
194 X
[2] = xor(X
[2], X
[3], shiftLeft(X
[1], 7))
195 X
[0] = rotateLeft(X
[0], 5)
196 X
[2] = rotateLeft(X
[2], 22)
200 def LTBitsliceInverse(X
):
201 """Apply, in reverse, the equations-based version of the linear
202 transformation to 'X', a list of 4 32-bit bitstrings, least significant
203 bitstring first, and return another list of 4 32-bit bitstrings as the
206 X
[2] = rotateRight(X
[2], 22)
207 X
[0] = rotateRight(X
[0], 5)
208 X
[2] = xor(X
[2], X
[3], shiftLeft(X
[1], 7))
209 X
[0] = xor(X
[0], X
[1], X
[3])
210 X
[3] = rotateRight(X
[3], 7)
211 X
[1] = rotateRight(X
[1], 1)
212 X
[3] = xor(X
[3], X
[2], shiftLeft(X
[0], 3))
213 X
[1] = xor(X
[1], X
[0], X
[2])
214 X
[2] = rotateRight(X
[2], 3)
215 X
[0] = rotateRight(X
[0], 13)
221 """Apply the Initial Permutation to the 128-bit bitstring 'input'
222 and return a 128-bit bitstring as the result."""
224 return applyPermutation(IPTable
, input)
227 """Apply the Final Permutation to the 128-bit bitstring 'input'
228 and return a 128-bit bitstring as the result."""
230 return applyPermutation(FPTable
, input)
233 def IPInverse(output
):
234 """Apply the Initial Permutation in reverse."""
238 def FPInverse(output
):
239 """Apply the Final Permutation in reverse."""
244 def applyPermutation(permutationTable
, input):
245 """Apply the permutation specified by the 128-element list
246 'permutationTable' to the 128-bit bitstring 'input' and return a
247 128-bit bitstring as the result."""
249 if len(input) != len(permutationTable
):
250 raise ValueError, "input size (%d) doesn't match perm table size (%d)"\
251 % (len(input), len(permutationTable
))
254 for i
in range(len(permutationTable
)):
255 result
= result
+ input[permutationTable
[i
]]
259 def R(i
, BHati
, KHat
):
260 """Apply round 'i' to the 128-bit bitstring 'BHati', returning another
261 128-bit bitstring (conceptually BHatiPlus1). Do this using the
262 appropriately numbered subkey(s) from the 'KHat' list of 33 128-bit
265 #O.show("BHati", BHati, "(i=%2d) BHati" % i)
267 xored
= xor(BHati
, KHat
[i
])
268 #O.show("xored", xored, "(i=%2d) xored" % i)
270 SHati
= SHat(i
, xored
)
271 #O.show("SHati", SHati, "(i=%2d) SHati" % i)
274 BHatiPlus1
= LT(SHati
)
276 BHatiPlus1
= xor(SHati
, KHat
[r
])
278 raise ValueError, "round %d is out of 0..%d range" % (i
, r
-1)
279 #O.show("BHatiPlus1", BHatiPlus1, "(i=%2d) BHatiPlus1" % i)
284 def RInverse(i
, BHatiPlus1
, KHat
):
285 """Apply round 'i' in reverse to the 128-bit bitstring 'BHatiPlus1',
286 returning another 128-bit bitstring (conceptually BHati). Do this using
287 the appropriately numbered subkey(s) from the 'KHat' list of 33 128-bit
290 #O.show("BHatiPlus1", BHatiPlus1, "(i=%2d) BHatiPlus1" % i)
293 SHati
= LTInverse(BHatiPlus1
)
295 SHati
= xor(BHatiPlus1
, KHat
[r
])
297 raise ValueError, "round %d is out of 0..%d range" % (i
, r
-1)
298 #O.show("SHati", SHati, "(i=%2d) SHati" % i)
300 xored
= SHatInverse(i
, SHati
)
301 #O.show("xored", xored, "(i=%2d) xored" % i)
303 BHati
= xor(xored
, KHat
[i
])
304 #O.show("BHati", BHati, "(i=%2d) BHati" % i)
309 def RBitslice(i
, Bi
, K
):
310 """Apply round 'i' (bitslice version) to the 128-bit bitstring 'Bi' and
311 return another 128-bit bitstring (conceptually B i+1). Use the
312 appropriately numbered subkey(s) from the 'K' list of 33 128-bit
315 #O.show("Bi", Bi, "(i=%2d) Bi" % i)
318 xored
= xor (Bi
, K
[i
])
319 #O.show("xored", xored, "(i=%2d) xored" % i)
322 Si
= SBitslice(i
, quadSplit(xored
))
323 # Input and output to SBitslice are both lists of 4 32-bit bitstrings
324 #O.show("Si", Si, "(i=%2d) Si" % i, "tlb")
327 # 3. Linear Transformation
329 # In the last round, replaced by an additional key mixing
330 BiPlus1
= xor(quadJoin(Si
), K
[r
])
332 BiPlus1
= quadJoin(LTBitslice(Si
))
333 # BIPlus1 is a 128-bit bitstring
334 #O.show("BiPlus1", BiPlus1, "(i=%2d) BiPlus1" % i)
339 def RBitsliceInverse(i
, BiPlus1
, K
):
340 """Apply the inverse of round 'i' (bitslice version) to the 128-bit
341 bitstring 'BiPlus1' and return another 128-bit bitstring (conceptually
342 B i). Use the appropriately numbered subkey(s) from the 'K' list of 33
343 128-bit bitstrings."""
345 #O.show("BiPlus1", BiPlus1, "(i=%2d) BiPlus1" % i)
347 # 3. Linear Transformation
349 # In the last round, replaced by an additional key mixing
350 Si
= quadSplit(xor(BiPlus1
, K
[r
]))
352 Si
= LTBitsliceInverse(quadSplit(BiPlus1
))
353 # SOutput (same as LTInput) is a list of 4 32-bit bitstrings
355 #O.show("Si", Si, "(i=%2d) Si" % i, "tlb")
358 xored
= SBitsliceInverse(i
, Si
)
359 # SInput and SOutput are both lists of 4 32-bit bitstrings
361 #O.show("xored", xored, "(i=%2d) xored" % i)
364 Bi
= xor (quadJoin(xored
), K
[i
])
366 #O.show("Bi", Bi, "(i=%2d) Bi" % i)
372 def encrypt(plainText
, userKey
):
373 """Encrypt the 128-bit bitstring 'plainText' with the 256-bit bitstring
374 'userKey', using the normal algorithm, and return a 128-bit ciphertext
377 #O.show("fnTitle", "encrypt", None, "tu")
378 #O.show("plainText", plainText, "plainText")
379 #O.show("userKey", userKey, "userKey")
381 K
, KHat
= makeSubkeys(userKey
)
383 BHat
= IP(plainText
) # BHat_0 at this stage
385 BHat
= R(i
, BHat
, KHat
) # Produce BHat_i+1 from BHat_i
386 # BHat is now _32 i.e. _r
389 #O.show("cipherText", C, "cipherText")
394 def encryptBitslice(plainText
, userKey
):
395 """Encrypt the 128-bit bitstring 'plainText' with the 256-bit bitstring
396 'userKey', using the bitslice algorithm, and return a 128-bit ciphertext
399 #O.show("fnTitle", "encryptBitslice", None, "tu")
400 #O.show("plainText", plainText, "plainText")
401 #O.show("userKey", userKey, "userKey")
403 K
, KHat
= makeSubkeys(userKey
)
405 B
= plainText
# B_0 at this stage
407 B
= RBitslice(i
, B
, K
) # Produce B_i+1 from B_i
410 #O.show("cipherText", B, "cipherText")
414 def decrypt(cipherText
, userKey
):
415 """Decrypt the 128-bit bitstring 'cipherText' with the 256-bit
416 bitstring 'userKey', using the normal algorithm, and return a 128-bit
417 plaintext bitstring."""
419 #O.show("fnTitle", "decrypt", None, "tu")
420 #O.show("cipherText", cipherText, "cipherText")
421 #O.show("userKey", userKey, "userKey")
423 K
, KHat
= makeSubkeys(userKey
)
425 BHat
= FPInverse(cipherText
) # BHat_r at this stage
426 for i
in range(r
-1, -1, -1): # from r-1 down to 0 included
427 BHat
= RInverse(i
, BHat
, KHat
) # Produce BHat_i from BHat_i+1
429 plainText
= IPInverse(BHat
)
431 #O.show("plainText", plainText, "plainText")
435 def decryptBitslice(cipherText
, userKey
):
436 """Decrypt the 128-bit bitstring 'cipherText' with the 256-bit
437 bitstring 'userKey', using the bitslice algorithm, and return a 128-bit
438 plaintext bitstring."""
440 #O.show("fnTitle", "decryptBitslice", None, "tu")
441 #O.show("cipherText", cipherText, "cipherText")
442 #O.show("userKey", userKey, "userKey")
444 K
, KHat
= makeSubkeys(userKey
)
446 B
= cipherText
# B_r at this stage
447 for i
in range(r
-1, -1, -1): # from r-1 down to 0 included
448 B
= RBitsliceInverse(i
, B
, K
) # Produce B_i from B_i+1
451 #O.show("plainText", B, "plainText")
455 def makeSubkeys(userKey
):
456 """Given the 256-bit bitstring 'userKey' (shown as K in the paper, but
457 we can't use that name because of a collision with K[i] used later for
458 something else), return two lists (conceptually K and KHat) of 33
459 128-bit bitstrings each."""
461 # Because in Python I can't index a list from anything other than 0,
462 # I use a dictionary instead to legibly represent the w_i that are
465 # We write the key as 8 32-bit words w-8 ... w-1
466 # ENOTE: w-8 is the least significant word
468 for i
in range(-8, 0):
469 w
[i
] = userKey
[(i
+8)*32:(i
+9)*32]
470 #O.show("wi", w[i], "(i=%2d) wi" % i)
472 # We expand these to a prekey w0 ... w131 with the affine recurrence
475 xor(w
[i
-8], w
[i
-5], w
[i
-3], w
[i
-1],
476 bitstring(phi
, 32), bitstring(i
,32)),
478 #O.show("wi", w[i], "(i=%2d) wi" % i)
480 # The round keys are now calculated from the prekeys using the S-boxes
481 # in bitslice mode. Each k[i] is a 32-bit bitstring.
484 whichS
= (r
+ 3 - i
) % r
489 for j
in range(32): # for every bit in the k and w words
490 # ENOTE: w0 and k0 are the least significant words, w99 and k99
492 input = w
[0+4*i
][j
] + w
[1+4*i
][j
] + w
[2+4*i
][j
] + w
[3+4*i
][j
]
493 output
= S(whichS
, input)
495 k
[l
+4*i
] = k
[l
+4*i
] + output
[l
]
497 # We then renumber the 32 bit values k_j as 128 bit subkeys K_i.
500 # ENOTE: k4i is the least significant word, k4i+3 the most.
501 K
.append(k
[4*i
] + k
[4*i
+1] + k
[4*i
+2] + k
[4*i
+3])
503 # We now apply IP to the round key in order to place the key bits in
507 KHat
.append(IP(K
[i
]))
509 #O.show("Ki", K[i], "(i=%2d) Ki" % i)
510 #O.show("KHati", KHat[i], "(i=%2d) KHati" % i)
516 """Take a key k in bitstring format. Return the long version of that
520 if l
% 32 != 0 or l
< 64 or l
> 256:
521 raise ValueError, "Invalid key length (%d bits)" % l
526 return k
+ "1" + "0"*(256 -l
-1)
528 # --------------------------------------------------------------
529 # Generic bit-level primitives
531 # Internally, we represent the numbers manipulated by the cipher in a
532 # format that we call 'bitstring'. This is a string of "0" and "1"
533 # characters containing the binary representation of the number in
534 # little-endian format (so that subscripting with an index of i gives bit
535 # number i, corresponding to a weight of 2^i). This representation is only
536 # defined for nonnegative numbers (you can see why: think of the great
537 # unnecessary mess that would result from sign extension, two's complement
538 # and so on). Example: 10 decimal is "0101" in bitstring format.
540 def bitstring(n
, minlen
=1):
541 """Translate n from integer to bitstring, padding it with 0s as
542 necessary to reach the minimum length 'minlen'. 'n' must be >= 0 since
543 the bitstring format is undefined for negative integers. Note that,
544 while the bitstring format can represent arbitrarily large numbers,
545 this is not so for Python's normal integer type: on a 32-bit machine,
546 values of n >= 2^31 need to be expressed as python long integers or
547 they will "look" negative and won't work. E.g. 0x80000000 needs to be
548 passed in as 0x80000000L, or it will be taken as -2147483648 instead of
551 EXAMPLE: bitstring(10, 8) -> "01010000"
555 raise ValueError, "a bitstring must have at least 1 char"
557 raise ValueError, "bitstring representation undefined for neg numbers"
562 result
= result
+ "1"
564 result
= result
+ "0"
566 if len(result
) < minlen
:
567 result
= result
+ "0" * (minlen
- len(result
))
571 def binaryXor(n1
, n2
):
572 """Return the xor of two bitstrings of equal length as another
573 bitstring of the same length.
575 EXAMPLE: binaryXor("10010", "00011") -> "10001"
578 if len(n1
) != len(n2
):
579 raise ValueError, "can't xor bitstrings of different " + \
580 "lengths (%d and %d)" % (len(n1
), len(n2
))
581 # We assume that they are genuine bitstrings instead of just random
585 for i
in range(len(n1
)):
587 result
= result
+ "0"
589 result
= result
+ "1"
594 """Return the xor of an arbitrary number of bitstrings of the same
595 length as another bitstring of the same length.
597 EXAMPLE: xor("01", "11", "10") -> "00"
601 raise ValueError, "at least one argument needed"
605 result
= binaryXor(result
, arg
)
609 def rotateLeft(input, places
):
610 """Take a bitstring 'input' of arbitrary length. Rotate it left by
611 'places' places. Left means that the 'places' most significant bits are
612 taken out and reinserted as the least significant bits. Note that,
613 because the bitstring representation is little-endian, the visual
614 effect is actually that of rotating the string to the right.
616 EXAMPLE: rotateLeft("000111", 2) -> "110001"
619 p
= places
% len(input)
620 return input[-p
:] + input[:-p
]
622 def rotateRight(input, places
):
623 return rotateLeft(input, -places
)
625 def shiftLeft(input, p
):
626 """Take a bitstring 'input' of arbitrary length. Shift it left by 'p'
627 places. Left means that the 'p' most significant bits are shifted out
628 and dropped, while 'p' 0s are inserted in the the least significant
629 bits. Note that, because the bitstring representation is little-endian,
630 the visual effect is actually that of shifting the string to the
631 right. Negative values for 'p' are allowed, with the effect of shifting
632 right instead (i.e. the 0s are inserted in the most significant bits).
634 EXAMPLE: shiftLeft("000111", 2) -> "000001"
635 shiftLeft("000111", -2) -> "011100"
638 if abs(p
) >= len(input):
639 # Everything gets shifted out anyway
640 return "0" * len(input)
642 # Shift right instead
643 return input[-p
:] + "0" * len(input[:-p
])
646 else: # p > 0, normal case
647 return "0" * len(input[-p
:]) + input[:-p
]
649 def shiftRight(input, p
):
650 """Take a bitstring 'input' and shift it right by 'p' places. See the
651 doc for shiftLeft for more details."""
653 return shiftLeft(input, -p
)
656 def keyLengthInBitsOf(k
):
657 """Take a string k in I/O format and return the number of bits in it."""
661 # --------------------------------------------------------------
662 # Hex conversion functions
664 # For I/O we use BIG-ENDIAN hexstrings. Do not get confused: internal stuff
665 # is LITTLE-ENDIAN bitstrings (so that digit i has weight 2^i) while
666 # external stuff is in BIG-ENDIAN hexstrings (so that it's shorter and it
667 # looks like the numbers you normally write down). The external (I/O)
668 # representation is the same as used by the C reference implementation.
671 # Given a 4-char bitstring, return the corresponding 1-char hexstring
672 "0000": "0", "1000": "1", "0100": "2", "1100": "3",
673 "0010": "4", "1010": "5", "0110": "6", "1110": "7",
674 "0001": "8", "1001": "9", "0101": "a", "1101": "b",
675 "0011": "c", "1011": "d", "0111": "e", "1111": "f",
678 # Make the reverse lookup table too
680 for (bin
, hex) in bin2hex
.items():
684 def bitstring2hexstring(b
):
685 """Take bitstring 'b' and return the corresponding hexstring."""
690 b
= b
+ "0" * (4-(l
%4))
691 for i
in range(0, len(b
), 4):
692 result
= result
+bin2hex
[b
[i
:i
+4]]
693 return reverseString(result
)
695 def hexstring2bitstring(h
):
696 """Take hexstring 'h' and return the corresponding bitstring."""
699 for c
in reverseString(h
):
700 result
= result
+ hex2bin
[c
]
703 def reverseString(s
):
706 return string
.join(l
, "")
711 # --------------------------------------------------------------
715 """Take a 128-bit bitstring and return it as a list of 4 32-bit
716 bitstrings, least significant bitstring first."""
719 raise ValueError, "must be 128 bits long, not " + len(b128
)
723 result
.append(b128
[(i
*32):(i
+1)*32])
728 """Take a list of 4 32-bit bitstrings and return it as a single 128-bit
729 bitstring obtained by concatenating the internal ones."""
732 raise ValueError, "need a list of 4 bitstrings, not " + len(l4x32
)
734 return l4x32
[0] + l4x32
[1] + l4x32
[2] + l4x32
[3]
736 # --------------------------------------------------
737 # Seeing what happens inside
740 """An object of this class can selectively display the values of the
741 variables you want to observe while the program is running. There are
742 tags that you can switch on or off. You sprinkle show() statements
743 throughout the program to show the value of a variable at a particular
744 point: show() will display the relevant variable only if the
745 corresponding tag is currently on. The special tag "ALL" forces all
746 show() statements to display their variable."""
749 "tu": "unknown", "tb": "bitstring", "tlb": "list of bitstrings",}
751 def __init__(self
, tags
=[]):
757 def addTag(self
, *tags
):
758 """Add the supplied tag(s) to those that are currently active,
759 i.e. those that, if a corresponding "show()" is executed, will
765 def removeTag(self
, *tags
):
766 """Remove the supplied tag(s) from those currently active."""
768 if t
in self
.tags
.keys():
771 def show(self
, tag
, variable
, label
=None, type="tb"):
772 """Conditionally print a message with the current value of
773 'variable'. The message will only be printed if the supplied 'tag'
774 is among the active ones (or if the 'ALL' tag is active). The
775 'label', if not null, is printed before the value of the
776 'variable'; if it is null, it is substituted with the 'tag'. The
777 'type' of the 'variable' (giving us a clue on how to print it) must
778 be one of Observer.typesOfVariable."""
782 if "ALL" in self
.tags
.keys() or tag
in self
.tags
.keys():
786 output
= bitstring2hexstring(variable
)
789 for item
in variable
:
790 output
= output
+ " %s" % bitstring2hexstring(item
)
791 output
= "[" + output
[1:] + "]"
793 raise ValueError, "unknown type: %s. Valid ones are %s" % (
794 type, self
.typesOfVariable
.keys())
803 # We make one global observer object that is always available
804 O
= Observer(["plainText", "userKey", "cipherText"])
806 # --------------------------------------------------------------
810 # --------------------------------------------------------------
814 # Each element of this list corresponds to one S-box. Each S-box in turn is
815 # a list of 16 integers in the range 0..15, without repetitions. Having the
816 # value v (say, 14) in position p (say, 0) means that if the input to that
817 # S-box is the pattern p (0, or 0x0) then the output will be the pattern v
820 [ 3, 8,15, 1,10, 6, 5,11,14,13, 4, 2, 7, 0, 9,12 ], # S0
821 [15,12, 2, 7, 9, 0, 5,10, 1,11,14, 8, 6,13, 3, 4 ], # S1
822 [ 8, 6, 7, 9, 3,12,10,15,13, 1,14, 4, 0,11, 5, 2 ], # S2
823 [ 0,15,11, 8,12, 9, 6, 3,13, 1, 2, 4,10, 7, 5,14 ], # S3
824 [ 1,15, 8, 3,12, 0,11, 6, 2, 5, 4,10, 9,14, 7,13 ], # S4
825 [15, 5, 2,11, 4,10, 9,12, 0, 3,14, 8,13, 6, 7, 1 ], # S5
826 [ 7, 2,12, 5, 8, 4, 6,11,14, 9, 1,15,13, 3,10, 0 ], # S6
827 [ 1,13,15, 0,14, 8, 2,11, 7, 4,12,10, 9, 3, 5, 6 ], # S7
829 # NB: in serpent-0, this was a list of 32 sublists (for the 32 different
830 # S-boxes derived from DES). In the final version of Serpent only 8 S-boxes
831 # are used, with each one being reused 4 times.
834 # Make another version of this table as a list of dictionaries: one
835 # dictionary per S-box, where the value of the entry indexed by i tells you
836 # the output configuration when the input is i, with both the index and the
837 # value being bitstrings. Make also the inverse: another list of
838 # dictionaries, one per S-box, where each dictionary gets the output of the
839 # S-box as the key and gives you the input, with both values being 4-bit
842 SBoxBitstringInverse
= []
843 for line
in SBoxDecimalTable
:
846 for i
in range(len(line
)):
847 index
= bitstring(i
, 4)
848 value
= bitstring(line
[i
], 4)
850 inverseDict
[value
] = index
851 SBoxBitstring
.append(dict)
852 SBoxBitstringInverse
.append(inverseDict
)
855 # The Initial and Final permutations are each represented by one list
856 # containing the integers in 0..127 without repetitions. Having value v
857 # (say, 32) at position p (say, 1) means that the output bit at position p
858 # (1) comes from the input bit at position v (32).
860 0, 32, 64, 96, 1, 33, 65, 97, 2, 34, 66, 98, 3, 35, 67, 99,
861 4, 36, 68, 100, 5, 37, 69, 101, 6, 38, 70, 102, 7, 39, 71, 103,
862 8, 40, 72, 104, 9, 41, 73, 105, 10, 42, 74, 106, 11, 43, 75, 107,
863 12, 44, 76, 108, 13, 45, 77, 109, 14, 46, 78, 110, 15, 47, 79, 111,
864 16, 48, 80, 112, 17, 49, 81, 113, 18, 50, 82, 114, 19, 51, 83, 115,
865 20, 52, 84, 116, 21, 53, 85, 117, 22, 54, 86, 118, 23, 55, 87, 119,
866 24, 56, 88, 120, 25, 57, 89, 121, 26, 58, 90, 122, 27, 59, 91, 123,
867 28, 60, 92, 124, 29, 61, 93, 125, 30, 62, 94, 126, 31, 63, 95, 127,
870 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60,
871 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124,
872 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61,
873 65, 69, 73, 77, 81, 85, 89, 93, 97, 101, 105, 109, 113, 117, 121, 125,
874 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62,
875 66, 70, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 114, 118, 122, 126,
876 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63,
877 67, 71, 75, 79, 83, 87, 91, 95, 99, 103, 107, 111, 115, 119, 123, 127,
881 # The Linear Transformation is represented as a list of 128 lists, one for
882 # each output bit. Each one of the 128 lists is composed of a variable
883 # number of integers in 0..127 specifying the positions of the input bits
884 # that must be XORed together (say, 72, 144 and 125) to yield the output
885 # bit corresponding to the position of that list (say, 1).
887 [16, 52, 56, 70, 83, 94, 105],
889 [2, 9, 15, 30, 76, 84, 126],
891 [20, 56, 60, 74, 87, 98, 109],
893 [2, 6, 13, 19, 34, 80, 88],
895 [24, 60, 64, 78, 91, 102, 113],
897 [6, 10, 17, 23, 38, 84, 92],
899 [28, 64, 68, 82, 95, 106, 117],
901 [10, 14, 21, 27, 42, 88, 96],
903 [32, 68, 72, 86, 99, 110, 121],
905 [14, 18, 25, 31, 46, 92, 100],
907 [36, 72, 76, 90, 103, 114, 125],
909 [18, 22, 29, 35, 50, 96, 104],
911 [1, 40, 76, 80, 94, 107, 118],
913 [22, 26, 33, 39, 54, 100, 108],
915 [5, 44, 80, 84, 98, 111, 122],
917 [26, 30, 37, 43, 58, 104, 112],
919 [9, 48, 84, 88, 102, 115, 126],
921 [30, 34, 41, 47, 62, 108, 116],
923 [2, 13, 52, 88, 92, 106, 119],
925 [34, 38, 45, 51, 66, 112, 120],
927 [6, 17, 56, 92, 96, 110, 123],
929 [38, 42, 49, 55, 70, 116, 124],
931 [10, 21, 60, 96, 100, 114, 127],
933 [0, 42, 46, 53, 59, 74, 120],
935 [3, 14, 25, 100, 104, 118],
937 [4, 46, 50, 57, 63, 78, 124],
939 [7, 18, 29, 104, 108, 122],
941 [0, 8, 50, 54, 61, 67, 82],
943 [11, 22, 33, 108, 112, 126],
945 [4, 12, 54, 58, 65, 71, 86],
947 [2, 15, 26, 37, 76, 112, 116],
949 [8, 16, 58, 62, 69, 75, 90],
951 [6, 19, 30, 41, 80, 116, 120],
953 [12, 20, 62, 66, 73, 79, 94],
955 [10, 23, 34, 45, 84, 120, 124],
957 [16, 24, 66, 70, 77, 83, 98],
959 [0, 14, 27, 38, 49, 88, 124],
961 [20, 28, 70, 74, 81, 87, 102],
963 [0, 4, 18, 31, 42, 53, 92],
965 [24, 32, 74, 78, 85, 91, 106],
967 [4, 8, 22, 35, 46, 57, 96],
969 [28, 36, 78, 82, 89, 95, 110],
971 [8, 12, 26, 39, 50, 61, 100],
973 [32, 40, 82, 86, 93, 99, 114],
975 [12, 16, 30, 43, 54, 65, 104],
979 [16, 20, 34, 47, 58, 69, 108],
983 [20, 24, 38, 51, 62, 73, 112],
987 [24, 28, 42, 55, 66, 77, 116],
991 [28, 32, 46, 59, 70, 81, 120],
995 [32, 36, 50, 63, 74, 85, 124],
999 [0, 36, 40, 54, 67, 78, 89],
1003 [4, 40, 44, 58, 71, 82, 93],
1005 [3, 18, 72, 114, 118, 125],
1007 [8, 44, 48, 62, 75, 86, 97],
1009 [1, 7, 22, 76, 118, 122],
1011 [12, 48, 52, 66, 79, 90, 101],
1013 [5, 11, 26, 80, 122, 126],
1017 # The following table is necessary for the non-bitslice decryption.
1034 [1, 3, 15, 20, 43, 102],
1038 [5, 7, 19, 24, 47, 106],
1042 [9, 11, 23, 28, 51, 110],
1046 [13, 15, 27, 32, 55, 114],
1048 [1, 29, 33, 48, 118],
1050 [1, 17, 19, 31, 36, 59, 118],
1052 [5, 33, 37, 52, 122],
1054 [5, 21, 23, 35, 40, 63, 122],
1056 [9, 37, 41, 56, 126],
1058 [9, 25, 27, 39, 44, 67, 126],
1060 [2, 13, 41, 45, 60],
1062 [2, 13, 29, 31, 43, 48, 71],
1064 [6, 17, 45, 49, 64],
1066 [6, 17, 33, 35, 47, 52, 75],
1068 [10, 21, 49, 53, 68],
1070 [10, 21, 37, 39, 51, 56, 79],
1072 [14, 25, 53, 57, 72],
1074 [14, 25, 41, 43, 55, 60, 83],
1076 [18, 29, 57, 61, 76],
1078 [18, 29, 45, 47, 59, 64, 87],
1080 [22, 33, 61, 65, 80],
1082 [22, 33, 49, 51, 63, 68, 91],
1084 [26, 37, 65, 69, 84],
1086 [26, 37, 53, 55, 67, 72, 95],
1088 [30, 41, 69, 73, 88],
1090 [30, 41, 57, 59, 71, 76, 99],
1092 [34, 45, 73, 77, 92],
1094 [34, 45, 61, 63, 75, 80, 103],
1096 [38, 49, 77, 81, 96],
1098 [38, 49, 65, 67, 79, 84, 107],
1100 [42, 53, 81, 85, 100],
1102 [42, 53, 69, 71, 83, 88, 111],
1104 [46, 57, 85, 89, 104],
1106 [46, 57, 73, 75, 87, 92, 115],
1108 [50, 61, 89, 93, 108],
1110 [50, 61, 77, 79, 91, 96, 119],
1112 [54, 65, 93, 97, 112],
1114 [54, 65, 81, 83, 95, 100, 123],
1116 [58, 69, 97, 101, 116],
1118 [58, 69, 85, 87, 99, 104, 127],
1120 [62, 73, 101, 105, 120],
1122 [3, 62, 73, 89, 91, 103, 108],
1124 [66, 77, 105, 109, 124],
1126 [7, 66, 77, 93, 95, 107, 112],
1128 [0, 70, 81, 109, 113],
1130 [11, 70, 81, 97, 99, 111, 116],
1132 [4, 74, 85, 113, 117],
1134 [15, 74, 85, 101, 103, 115, 120],
1136 [8, 78, 89, 117, 121],
1138 [19, 78, 89, 105, 107, 119, 124],
1140 [12, 82, 93, 121, 125],
1142 [0, 23, 82, 93, 109, 111, 123],
1144 [1, 16, 86, 97, 125],
1146 [4, 27, 86, 97, 113, 115, 127],
1150 # --------------------------------------------------
1151 # Handling command line arguments and stuff
1154 # $Id: serpref.py,v 1.19 1998/09/02 21:28:02 fms Exp $
1156 # Python reference implementation of Serpent.
1158 # Written by Frank Stajano,
1159 # Olivetti Oracle Research Laboratory <http://www.orl.co.uk/~fms/> and
1160 # Cambridge University Computer Laboratory <http://www.cl.cam.ac.uk/~fms27/>.
1162 # (c) 1998 Olivetti Oracle Research Laboratory (ORL)
1164 # Original (Python) Serpent reference development started on 1998 02 12.
1165 # C implementation development started on 1998 03 04.
1167 # Serpent cipher invented by Ross Anderson, Eli Biham, Lars Knudsen.
1168 # Serpent is a candidate for the Advanced Encryption Standard.
1170 Encrypts or decrypts one block of data using the Serpent cipher and
1171 optionally showing you what's going on inside at the various stages of
1174 SYNTAX: serpref mode [options]
1176 MODE is one of the following:
1179 -h -> help (the text you're reading right now)
1182 -p plainText -> The 128-bit value to be encrypted. Required in mode -e,
1183 ignored otherwise. Short texts are zeropadded.
1184 -c cipherText -> The 128-bit value to be decrypted. Required in mode -d,
1185 ignored otherwise. Short texts are zeropadded.
1186 -k key -> The value of the key (allowed lengths are from 64 to
1187 256 bits, but must be a multiple of 32 bits). Keys
1188 shorter than 256 bits are internally transformed into
1189 the equivalent long keys (NOT the same as zeropadding!).
1190 Required for -e and -d.
1191 -t tagName -> Turn on the observer tag with that name. This means that
1192 any observer messages associated with this tag will
1193 now be displayed. This option may be specified several
1194 times to add multiple tags.
1195 The special tag ALL turns on all the messages.
1197 -b -> Use the bitslice version instead of the traditional
1198 version, which is otherwise used by default. Optional.
1201 These are the tags of the quantities you can currently observe with
1202 -t. Names are modelled on the paper's notation.
1204 For the non-bitslice: BHati xored SHati BHatiPlus1 wi KHati
1205 For the bitslice: Bi xored Si BiPlus1 wi Ki
1206 Generic: plainText userKey cipherText testTitle fnTitle
1210 All I/O is performed using hex numbers of the appropriate size, written
1211 as sequences of hex digits, most significant digit first (big-endian),
1212 without any leading or trailing markers such as 0x, &, h or whatever.
1213 Example: the number ten is "a" in four bits or "000a" in sixteen bits.
1218 serpref -e -k 123456789abcdef -p 0
1219 Encrypt the plaintext "all zeros" with the given key.
1221 serpref -e -b -k 123456789abcdef -p 0
1222 Same as above, but the extra -b requests bitslice operation. As
1223 things are, we won't notice the difference, but see below...
1225 serpref -e -b -k 123456789abcdef -p 0 -t Bi
1226 Same as above, but the "-t Bi" prints out all the intermediate
1227 results with a tag of Bi, allowing you to see what happens inside
1228 the rounds. Compare this with the following...
1230 serpref -e -k 123456789abcdef -p 0 -t BHati
1231 Same as above except that we are back to the non-bitslice version
1232 (there is no -b) and we are printing the items with the BHati tag
1233 (which is the equivalent of Bi for the non-bitslice version).
1235 serpref -e -k 123456789abcdef -p 0 -t xored -t SHati -t BHati
1236 Same as above but we are requesting even more details, basically
1237 looking at all the intermediate results of each round as well. (You
1238 could use the single magic tag -t ALL if you didn't want to have to
1239 find out the names of the individual tags.)
1243 def helpExit(message
= None):
1246 print "ERROR:", message
1249 def convertToBitstring(input, numBits
):
1250 """Take a string 'input', theoretically in std I/O format, but in
1251 practice liable to contain any sort of crap since it's user supplied,
1252 and return its bitstring representation, normalised to numBits
1253 bits. Raise the appropriate variant of ValueError (with explanatory
1254 message) if anything can't be done (this includes the case where the
1255 'input', while otherwise syntactically correct, can't be represented in
1258 if re
.match("^[0-9a-f]+$", input):
1259 bitstring
= hexstring2bitstring(input)
1261 raise ValueError, "%s is not a valid hexstring" % input
1263 # assert: bitstring now contains the bitstring version of the input
1265 if len(bitstring
) > numBits
:
1266 # Last chance: maybe it's got some useless 0s...
1267 if re
.match("^0+$", bitstring
[numBits
:]):
1268 bitstring
= bitstring
[:numBits
]
1270 raise ValueError, "input too large to fit in %d bits" % numBits
1272 bitstring
= bitstring
+ "0" * (numBits
-len(bitstring
))
1279 optList
, rest
= getopt
.getopt(sys
.argv
[1:], "edhbt:k:p:c:")
1282 helpExit("Sorry, can't make sense of this: '%s'" % rest
)
1284 # Transform the list of options into a more comfortable
1285 # dictionary. This only works with non-repeated options, though, so
1286 # tags (which are repeated) must be dealt with separately.
1288 for key
, value
in optList
:
1292 if key
in options
.keys():
1293 helpExit("Multiple occurrences of " + key
)
1295 options
[string
.strip(key
)] = string
.strip(value
)
1297 # Not more than one mode
1299 for k
in options
.keys():
1300 if k
in ["-e", "-d", "-h"]:
1302 helpExit("you can only specify one mode")
1306 helpExit("No mode specified")
1308 # Put plainText, userKey, cipherText in bitstring format.
1309 plainText
= userKey
= cipherText
= None
1310 if options
.has_key("-k"):
1311 bitsInKey
= keyLengthInBitsOf(options
["-k"])
1312 rawKey
= convertToBitstring(options
["-k"], bitsInKey
)
1313 userKey
= makeLongKey(rawKey
)
1314 if options
.has_key("-p"):
1315 plainText
= convertToBitstring(options
["-p"], 128)
1316 if options
.has_key("-c"):
1317 cipherText
= convertToBitstring(options
["-c"], 128)
1318 if mode
== "-e" or mode
== "-d":
1320 helpExit("-k (key) required with -e (encrypt) or -d (decrypt)")
1323 helpExit("-p (plaintext) is required when doing -e (encrypt)")
1326 helpExit("-c (ciphertext) is required when doing -d (decrypt)")
1328 # Perform the action specified by the mode
1329 # NOTE that the observer will automatically print the basic stuff such
1330 # as plainText, userKey and cipherText (in the right format too), so we
1331 # only need to perform the action, without adding any extra print
1334 if options
.has_key("-b"):
1335 cipherText
= encryptBitslice(plainText
, userKey
)
1337 cipherText
= encrypt(plainText
, userKey
)
1339 if options
.has_key("-b"):
1340 plainText
= decryptBitslice(cipherText
, userKey
)
1342 plainText
= decrypt(cipherText
, userKey
)
1344 O
.addTag("testTitle", "fnTitle")
1346 printTest(test1(plainText
, userKey
))
1347 printTest(test2(plainText
, userKey
))
1348 printTest(test3(plainText
, userKey
))
1353 if __name__
== "__main__":