#! /usr/bin/python import itertools as I INTERLACE = 1 FAKE_INTERLACE = 2 COMPLEMENT = 4 COMPLHACK = 8 OPTIONS = 0 def lfsr(): poly = 0x171 a = 1 while True: yield a&1 a <<= 1 if a&0x100: a ^= poly M32 = (1 << 32) - 1 M64 = (1 << 64) - 1 BEBIGOKIMISA = [(1, 0), (2, 0), (3, 1), (2, 2), (2, 3), (0, 4)] def rotl(x, n): return ((x << n) | (x >> 64 - n))&M64 def rotl_32(x, n): return ((x << n) | (x >> 32 - n))&M32 def interlace(x): x0, x1 = x&M32, (x >> 32)&M32 # 543210 t = ((x0 >> 16) ^ x1)&0x0000ffff; x0 ^= t << 16; x1 ^= t # 453210 t = ((x0 >> 8) ^ x1)&0x00ff00ff; x0 ^= t << 8; x1 ^= t # 354210 t = ((x0 >> 4) ^ x1)&0x0f0f0f0f; x0 ^= t << 4; x1 ^= t # 254310 t = ((x0 >> 2) ^ x1)&0x33333333; x0 ^= t << 2; x1 ^= t # 154320 t = ((x0 >> 1) ^ x1)&0x55555555; x0 ^= t << 1; x1 ^= t # 054321 return x0, x1 def deinterlace((x0, x1)): t = ((x0 >> 1) ^ x1)&0x55555555; x0 ^= t << 1; x1 ^= t # 154320 t = ((x0 >> 2) ^ x1)&0x33333333; x0 ^= t << 2; x1 ^= t # 254310 t = ((x0 >> 4) ^ x1)&0x0f0f0f0f; x0 ^= t << 4; x1 ^= t # 354210 t = ((x0 >> 8) ^ x1)&0x00ff00ff; x0 ^= t << 8; x1 ^= t # 453210 t = ((x0 >> 16) ^ x1)&0x0000ffff; x0 ^= t << 16; x1 ^= t # 543210 return x0 | (x1 << 32) def identity(x): return x RC = 24*[0] bits = lfsr() for i in xrange(24): for j in xrange(7): RC[i] |= bits.next() << (1 << j) - 1 print 'Round constants...' for i, rc in enumerate(RC): rc0, rc1 = interlace(rc) print '%2d: 0x%016x = 0x%08x, 0x%08x' % (i, rc, rc0, rc1) ROT = [5*[0] for i in xrange(5)] x, y = 1, 0 for t in xrange(24): ROT[x][y] = ((t + 1)*(t + 2)/2)%64 x, y = y, (2*x + 3*y)%5 print '\nRotations...' for y in xrange(2, -3, -1): print '%2d: %s' % (y, ', '.join('%3d' % ROT[x%5][y%5] for x in xrange(-2, 3))) def print_state(A): if OPTIONS & (INTERLACE | FAKE_INTERLACE): fn = (OPTIONS & FAKE_INTERLACE) and interlace or identity for y in xrange(5): print '%2d: %s' % (y, ' '.join('%08x:%08x' % fn(A[x%5][y%5]) for x in xrange(5))) else: for y in xrange(5): print '%2d: %s' % (y, ' '.join('%016x' % (A[x%5][y%5] ^ ROOT[x%5][y%5]) for x in xrange(5))) def p(what, A): print '\n%s...' % what print_state(A) return A def statemap(fn, A): return [[fn(A[x][y]) for y in xrange(5)] for x in xrange(5)] if OPTIONS & INTERLACE: def to_interlace(A): return statemap(interlace, A) def from_interlace(A): return statemap(deinterlace, A) def theta(A): C = [reduce(lambda a, b: (a[0] ^ b[0], a[1] ^ b[1]), (A[x][y] for y in xrange(5))) for x in xrange(5)] D = [(C[(x - 1)%5][0] ^ rotl_32(C[(x + 1)%5][1], 1), C[(x - 1)%5][1] ^ C[(x + 1)%5][0]) for x in xrange(5)] return p('theta', [[(A[x][y][0] ^ D[x][0], A[x][y][1] ^ D[x][1]) for y in xrange(5)] for x in xrange(5)]) def rho(A): def f((a0, a1), n): if n%2 == 0: return rotl_32(a0, n/2), rotl_32(a1, n/2) else: return rotl_32(a1, (n + 1)/2), rotl_32(a0, (n - 1)/2) return p('rho', [[f(A[x][y], ROT[x][y]) for y in xrange(5)] for x in xrange(5)]) def pi(A): ## x' = y, y' = 2 x + 3 y ## y = x', x = (y' - 3 x')/2 = 3 y' - 4 x' = x' + 3 y' return p('pi', [[(A[(x + 3*y)%5][x][0], A[(x + 3*y)%5][x][1]) for y in xrange(5)] for x in xrange(5)]) def chi(A): return p('chi', [[(A[x][y][0] ^ (~A[(x + 1)%5][y][0]&A[(x + 2)%5][y][0]), A[x][y][1] ^ (~A[(x + 1)%5][y][1]&A[(x + 2)%5][y][1])) for y in xrange(5)] for x in xrange(5)]) def iota(A, i): rc = interlace(RC[i]) return p('iota[%d]' % i, [[(A[x][y][0] ^ (x == y == 0 and rc[0] or 0), A[x][y][1] ^ (x == y == 0 and rc[1] or 0)) for y in xrange(5)] for x in xrange(5)]) def round(A, i): return iota(chi(pi(rho(theta(A)))), i) ROOT = [5*[(0, 0)] for i in xrange(5)] else: def theta(A): C = [reduce(lambda a, b: a ^ b, (A[x][y] for y in xrange(5))) for x in xrange(5)] D = [C[(x - 1)%5] ^ rotl(C[(x + 1)%5], 1) for x in xrange(5)] return p('theta', [[A[x][y] ^ D[x] for y in xrange(5)] for x in xrange(5)]) def rho(A): return p('rho', [[rotl(A[x][y], ROT[x][y]) for y in xrange(5)] for x in xrange(5)]) def pi(A): ## x' = y, y' = 2 x + 3 y ## y = x', x = (y' - 3 x')/2 = 3 y' - 4 x' = x' + 3 y' return p('pi', [[A[(x + 3*y)%5][x] for y in xrange(5)] for x in xrange(5)]) if OPTIONS & COMPLEMENT: def chi(A): Z = [5*[None] for i in xrange(5)] ## a ^ ( b | ~c) = ~z | . . * -> * ## a ^ (~b & c) = z | . * . -> . ## ~a ^ ( b | ~c) = z | * . * -> . ## ~a ^ (~b & c) = ~z | * * . -> * Z[0][0] = A[0][0] ^ ( A[1][0] | A[2][0]) # * . * -> . Z[1][0] = A[1][0] ^ (~A[2][0] | A[3][0]) # . [.] * -> * Z[2][0] = A[2][0] ^ ( A[3][0] & A[4][0]) # * * . -> * Z[3][0] = A[3][0] ^ ( A[4][0] | A[0][0]) # * * . -> . Z[4][0] = A[4][0] ^ ( A[0][0] & A[1][0]) # * . . -> . Z[0][1] = A[0][1] ^ ( A[1][1] | A[2][1]) # * . * -> . Z[1][1] = A[1][1] ^ ( A[2][1] & A[3][1]) # . * . -> . Z[2][1] = A[2][1] ^ ( A[3][1] | ~A[4][1]) # * . [*] -> . Z[3][1] = A[3][1] ^ ( A[4][1] | A[0][1]) # * . . -> * Z[4][1] = A[4][1] ^ ( A[0][1] & A[1][1]) # * . . -> . t = ~A[3][2] # [*] Z[0][2] = A[0][2] ^ ( A[1][2] | A[2][2]) # * . * -> . Z[1][2] = A[1][2] ^ ( A[2][2] & A[3][2]) # . * . -> . Z[2][2] = A[2][2] ^ ( t & A[4][2]) # * [*] . -> * Z[3][2] = t ^ ( A[4][2] | A[0][2]) # * [*] . -> . Z[4][2] = A[4][2] ^ ( A[0][2] & A[1][2]) # * . . -> . t = ~A[3][3] # [.] Z[0][3] = A[0][3] ^ ( A[1][3] & A[2][3]) # . * . -> . Z[1][3] = A[1][3] ^ ( A[2][3] | A[3][3]) # * . * -> . Z[2][3] = A[2][3] ^ ( t | A[4][3]) # . [.] * -> * Z[3][3] = t ^ ( A[4][3] & A[0][3]) # . [.] * -> . Z[4][3] = A[4][3] ^ ( A[0][3] | A[1][3]) # . * * -> . t = ~A[1][4] # [*] Z[0][4] = A[0][4] ^ ( t & A[2][4]) # * [*] . -> * Z[1][4] = t ^ ( A[2][4] | A[3][4]) # [*] . * -> . Z[2][4] = A[2][4] ^ ( A[3][4] & A[4][4]) # . * . -> . Z[3][4] = A[3][4] ^ ( A[4][4] | A[0][4]) # * * . -> . Z[4][4] = A[4][4] ^ ( A[0][4] & A[1][4]) # * . . -> . return p('chi', statemap(lambda i: i&M64, Z)) else: def chi(A): return p('chi', [[A[x][y] ^ (~A[(x + 1)%5][y]&A[(x + 2)%5][y]) for y in xrange(5)] for x in xrange(5)]) def iota(A, i): return p('iota[%d]' % i, [[A[x][y] ^ (x == y == 0 and RC[i] or 0) for y in xrange(5)] for x in xrange(5)]) def round(A, i): return iota(chi(pi(rho(theta(A)))), i) if OPTIONS & COMPLEMENT: ROOT = [[(x, y) in BEBIGOKIMISA and M64 or 0 for y in xrange(5)] for x in xrange(5)] else: ROOT = [5*[0] for i in xrange(5)] def keccak1600_p(A, n): for i in xrange(n): A = round(A, i) return p('done', A) p('init', ROOT) keccak1600_p(ROOT, 24)