| 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) |