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
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
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)
42 def identity(x
): return x
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
)
54 ROT
= [5*[0] for i
in xrange(5)]
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)))
65 if OPTIONS
& (INTERLACE | FAKE_INTERLACE
):
66 fn
= (OPTIONS
& FAKE_INTERLACE
) and interlace
or identity
68 print '%2d: %s' %
(y
, ' '.join('%08x:%08x' % fn
(A
[x
%5][y
%5])
72 print '%2d: %s' %
(y
, ' '.join('%016x' %
(A
[x
%5][y
%5] ^
77 print '\n%s...' % what
82 return [[fn(A
[x
][y
]) for y
in xrange(5)] for x
in xrange(5)]
84 if OPTIONS
& INTERLACE
:
86 def to_interlace(A
): return statemap(interlace
, A
)
87 def from_interlace(A
): return statemap(deinterlace
, A
)
90 C
= [reduce(lambda a
, b
: (a
[0] ^ b
[0], a
[1] ^ b
[1]),
91 (A
[x
][y
] for y
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])
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)])
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)])
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)])
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)])
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)])
124 return iota(chi(pi(rho(theta(A
)))), i
)
126 ROOT
= [5*[(0, 0)] for i
in xrange(5)]
131 C
= [reduce(lambda a
, b
: a ^ b
, (A
[x
][y
] for y
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)])
138 return p('rho', [[rotl(A
[x
][y
], ROT
[x
][y
])
139 for y
in xrange(5)] for x
in xrange(5)])
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)])
147 if OPTIONS
& COMPLEMENT
:
149 Z
= [5*[None] for i
in xrange(5)]
151 ## a ^ ( b | ~c) = ~z | . . * -> *
152 ## a ^ (~b & c) = z | . * . -> .
153 ## ~a ^ ( b | ~c) = z | * . * -> .
154 ## ~a ^ (~b & c) = ~z | * * . -> *
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]) # * . . -> .
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]) # * . . -> .
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]) # * . . -> .
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]) # . * * -> .
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]) # * . . -> .
189 return p('chi', statemap(lambda i
: i
&M64
, Z
))
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)])
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)])
200 return iota(chi(pi(rho(theta(A
)))), i
)
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)]
206 ROOT
= [5*[0] for i
in xrange(5)]
208 def keccak1600_p(A
, n
):
209 for i
in xrange(n
): A
= round(A
, i
)
213 keccak1600_p(ROOT
, 24)