Commit | Line | Data |
---|---|---|
a905c0d6 MW |
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) |