chiark - git - mdw - catacomb/blob - utils/keccak-toy

   1 #! /usr/bin/python
   2
   3 import itertools as I
   4
   5 INTERLACE = 1
   6 FAKE_INTERLACE = 2
   7 COMPLEMENT = 4
   8 COMPLHACK = 8
   9 OPTIONS = 0
  10
  11 def lfsr():
  12   poly = 0x171
  13   a = 1
  14   while True:
  15     yield a&1
  16     a <<= 1
  17     if a&0x100: a ^= poly
  18
  19 M32 = (1 << 32) - 1
  20 M64 = (1 << 64) - 1
  21 BEBIGOKIMISA = [(1, 0), (2, 0), (3, 1), (2, 2), (2, 3), (0, 4)]
  22 def rotl(x, n): return ((x << n) | (x >> 64 - n))&M64
  23 def rotl_32(x, n): return ((x << n) | (x >> 32 - n))&M32
  24
  25 def interlace(x):
  26   x0, x1 = x&M32, (x >> 32)&M32                            # 543210
  27   t = ((x0 >> 16) ^ x1)&0x0000ffff; x0 ^= t << 16; x1 ^= t # 453210
  28   t = ((x0 >>  8) ^ x1)&0x00ff00ff; x0 ^= t <<  8; x1 ^= t # 354210
  29   t = ((x0 >>  4) ^ x1)&0x0f0f0f0f; x0 ^= t <<  4; x1 ^= t # 254310
  30   t = ((x0 >>  2) ^ x1)&0x33333333; x0 ^= t <<  2; x1 ^= t # 154320
  31   t = ((x0 >>  1) ^ x1)&0x55555555; x0 ^= t <<  1; x1 ^= t # 054321
  32   return x0, x1
  33
  34 def deinterlace((x0, x1)):
  35   t = ((x0 >>  1) ^ x1)&0x55555555; x0 ^= t <<  1; x1 ^= t # 154320
  36   t = ((x0 >>  2) ^ x1)&0x33333333; x0 ^= t <<  2; x1 ^= t # 254310
  37   t = ((x0 >>  4) ^ x1)&0x0f0f0f0f; x0 ^= t <<  4; x1 ^= t # 354210
  38   t = ((x0 >>  8) ^ x1)&0x00ff00ff; x0 ^= t <<  8; x1 ^= t # 453210
  39   t = ((x0 >> 16) ^ x1)&0x0000ffff; x0 ^= t << 16; x1 ^= t # 543210
  40   return x0 | (x1 << 32)
  41
  42 def identity(x): return x
  43
  44 RC = 24*[0]
  45 bits = lfsr()
  46 for i in xrange(24):
  47   for j in xrange(7):
  48     RC[i] |= bits.next() << (1 << j) - 1
  49 print 'Round constants...'
  50 for i, rc in enumerate(RC):
  51   rc0, rc1 = interlace(rc)
  52   print '%2d: 0x%016x = 0x%08x, 0x%08x' % (i, rc, rc0, rc1)
  53
  54 ROT = [5*[0] for i in xrange(5)]
  55 x, y = 1, 0
  56 for t in xrange(24):
  57   ROT[x][y] = ((t + 1)*(t + 2)/2)%64
  58   x, y = y, (2*x + 3*y)%5
  59 print '\nRotations...'
  60 for y in xrange(2, -3, -1):
  61   print '%2d: %s' % (y, ', '.join('%3d' % ROT[x%5][y%5]
  62                                   for x in xrange(-2, 3)))
  63
  64 def print_state(A):
  65   if OPTIONS & (INTERLACE | FAKE_INTERLACE):
  66     fn = (OPTIONS & FAKE_INTERLACE) and interlace or identity
  67     for y in xrange(5):
  68       print '%2d: %s' % (y, ' '.join('%08x:%08x' % fn(A[x%5][y%5])
  69                                       for x in xrange(5)))
  70   else:
  71     for y in xrange(5):
  72       print '%2d: %s' % (y, ' '.join('%016x' % (A[x%5][y%5] ^
  73                                                  ROOT[x%5][y%5])
  74                                       for x in xrange(5)))
  75
  76 def p(what, A):
  77   print '\n%s...' % what
  78   print_state(A)
  79   return A
  80
  81 def statemap(fn, A):
  82   return [[fn(A[x][y]) for y in xrange(5)] for x in xrange(5)]
  83
  84 if OPTIONS & INTERLACE:
  85
  86   def to_interlace(A): return statemap(interlace, A)
  87   def from_interlace(A): return statemap(deinterlace, A)
  88
  89   def theta(A):
  90     C = [reduce(lambda a, b: (a[0] ^ b[0], a[1] ^ b[1]),
  91                 (A[x][y] for y in xrange(5)))
  92          for x in xrange(5)]
  93     D = [(C[(x - 1)%5][0] ^ rotl_32(C[(x + 1)%5][1], 1),
  94           C[(x - 1)%5][1] ^ C[(x + 1)%5][0])
  95          for x in xrange(5)]
  96     return p('theta', [[(A[x][y][0] ^ D[x][0], A[x][y][1] ^ D[x][1])
  97                         for y in xrange(5)] for x in xrange(5)])
  98
  99   def rho(A):
 100     def f((a0, a1), n):
 101       if n%2 == 0: return rotl_32(a0, n/2), rotl_32(a1, n/2)
 102       else: return rotl_32(a1, (n + 1)/2), rotl_32(a0, (n - 1)/2)
 103     return p('rho', [[f(A[x][y], ROT[x][y])
 104                       for y in xrange(5)] for x in xrange(5)])
 105
 106   def pi(A):
 107     ## x' = y, y' = 2 x + 3 y
 108     ## y = x', x = (y' - 3 x')/2 = 3 y' - 4 x' = x' + 3 y'
 109     return p('pi', [[(A[(x + 3*y)%5][x][0], A[(x + 3*y)%5][x][1])
 110                      for y in xrange(5)] for x in xrange(5)])
 111
 112   def chi(A):
 113     return p('chi', [[(A[x][y][0] ^ (~A[(x + 1)%5][y][0]&A[(x + 2)%5][y][0]),
 114                        A[x][y][1] ^ (~A[(x + 1)%5][y][1]&A[(x + 2)%5][y][1]))
 115                       for y in xrange(5)] for x in xrange(5)])
 116
 117   def iota(A, i):
 118     rc = interlace(RC[i])
 119     return p('iota[%d]' % i, [[(A[x][y][0] ^ (x == y == 0 and rc[0] or 0),
 120                                 A[x][y][1] ^ (x == y == 0 and rc[1] or 0))
 121                                for y in xrange(5)] for x in xrange(5)])
 122
 123   def round(A, i):
 124     return iota(chi(pi(rho(theta(A)))), i)
 125
 126   ROOT = [5*[(0, 0)] for i in xrange(5)]
 127
 128 else:
 129
 130   def theta(A):
 131     C = [reduce(lambda a, b: a ^ b, (A[x][y] for y in xrange(5)))
 132          for x in xrange(5)]
 133     D = [C[(x - 1)%5] ^ rotl(C[(x + 1)%5], 1) for x in xrange(5)]
 134     return p('theta', [[A[x][y] ^ D[x]
 135                         for y in xrange(5)] for x in xrange(5)])
 136
 137   def rho(A):
 138     return p('rho', [[rotl(A[x][y], ROT[x][y])
 139                       for y in xrange(5)] for x in xrange(5)])
 140
 141   def pi(A):
 142     ## x' = y, y' = 2 x + 3 y
 143     ## y = x', x = (y' - 3 x')/2 = 3 y' - 4 x' = x' + 3 y'
 144     return p('pi', [[A[(x + 3*y)%5][x]
 145                      for y in xrange(5)] for x in xrange(5)])
 146
 147   if OPTIONS & COMPLEMENT:
 148     def chi(A):
 149       Z = [5*[None] for i in xrange(5)]
 150
 151       ##  a ^ ( b | ~c) = ~z    | . . * -> *
 152       ##  a ^ (~b &  c) =  z    | . * . -> .
 153       ## ~a ^ ( b | ~c) =  z    | * . * -> .
 154       ## ~a ^ (~b &  c) = ~z    | * * . -> *
 155
 156       Z[0][0] = A[0][0] ^ ( A[1][0] |  A[2][0]) #  *   .   *          -> .
 157       Z[1][0] = A[1][0] ^ (~A[2][0] |  A[3][0]) #      .  [.]  *      -> *
 158       Z[2][0] = A[2][0] ^ ( A[3][0] &  A[4][0]) #          *   *   .  -> *
 159       Z[3][0] = A[3][0] ^ ( A[4][0] |  A[0][0]) #  *           *   .  -> .
 160       Z[4][0] = A[4][0] ^ ( A[0][0] &  A[1][0]) #  *   .           .  -> .
 161
 162       Z[0][1] = A[0][1] ^ ( A[1][1] |  A[2][1]) #  *   .   *          -> .
 163       Z[1][1] = A[1][1] ^ ( A[2][1] &  A[3][1]) #      .   *   .      -> .
 164       Z[2][1] = A[2][1] ^ ( A[3][1] | ~A[4][1]) #          *   .  [*] -> .
 165       Z[3][1] = A[3][1] ^ ( A[4][1] |  A[0][1]) #  *           .   .  -> *
 166       Z[4][1] = A[4][1] ^ ( A[0][1] &  A[1][1]) #  *   .           .  -> .
 167
 168       t = ~A[3][2]                              #             [*]
 169       Z[0][2] = A[0][2] ^ ( A[1][2] |  A[2][2]) #  *   .   *          -> .
 170       Z[1][2] = A[1][2] ^ ( A[2][2] &  A[3][2]) #      .   *   .      -> .
 171       Z[2][2] = A[2][2] ^ ( t       &  A[4][2]) #          *  [*]  .  -> *
 172       Z[3][2] = t       ^ ( A[4][2] |  A[0][2]) #  *          [*]  .  -> .
 173       Z[4][2] = A[4][2] ^ ( A[0][2] &  A[1][2]) #  *   .           .  -> .
 174
 175       t = ~A[3][3]                              #             [.]
 176       Z[0][3] = A[0][3] ^ ( A[1][3] &  A[2][3]) #  .   *   .          -> .
 177       Z[1][3] = A[1][3] ^ ( A[2][3] |  A[3][3]) #      *   .   *      -> .
 178       Z[2][3] = A[2][3] ^ ( t       |  A[4][3]) #          .  [.]  *  -> *
 179       Z[3][3] = t       ^ ( A[4][3] &  A[0][3]) #  .          [.]  *  -> .
 180       Z[4][3] = A[4][3] ^ ( A[0][3] |  A[1][3]) #  .   *           *  -> .
 181
 182       t = ~A[1][4]                              #     [*]
 183       Z[0][4] = A[0][4] ^ ( t       &  A[2][4]) #  *  [*]  .          -> *
 184       Z[1][4] = t       ^ ( A[2][4] |  A[3][4]) #     [*]  .   *      -> .
 185       Z[2][4] = A[2][4] ^ ( A[3][4] &  A[4][4]) #          .   *   .  -> .
 186       Z[3][4] = A[3][4] ^ ( A[4][4] |  A[0][4]) #  *           *   .  -> .
 187       Z[4][4] = A[4][4] ^ ( A[0][4] &  A[1][4]) #  *   .           .  -> .
 188
 189       return p('chi', statemap(lambda i: i&M64, Z))
 190   else:
 191     def chi(A):
 192       return p('chi', [[A[x][y] ^ (~A[(x + 1)%5][y]&A[(x + 2)%5][y])
 193                         for y in xrange(5)] for x in xrange(5)])
 194
 195   def iota(A, i):
 196     return p('iota[%d]' % i, [[A[x][y] ^ (x == y == 0 and RC[i] or 0)
 197                                for y in xrange(5)] for x in xrange(5)])
 198
 199   def round(A, i):
 200     return iota(chi(pi(rho(theta(A)))), i)
 201
 202   if OPTIONS & COMPLEMENT:
 203     ROOT = [[(x, y) in BEBIGOKIMISA and M64 or 0
 204              for y in xrange(5)] for x in xrange(5)]
 205   else:
 206     ROOT = [5*[0] for i in xrange(5)]
 207
 208 def keccak1600_p(A, n):
 209   for i in xrange(n): A = round(A, i)
 210   return p('done', A)
 211
 212 p('init', ROOT)
 213 keccak1600_p(ROOT, 24)