I am trying to implement SHA-3 using this document and have a question about the iota step.
This step consists in a single XOR between the central (0, 0) lane of the state (illustration of the state p.8 if needed) and a round constant. In other terms:
for z in [0, w[:
let new_state(0, 0, z) = state(0, 0, z) ^ RC[z]
where RC is viewed as a bit string.
The first round constant of the first round is 1, thus only one bit will be changed. As it can be seen in this document providing test vectors, we have in round #0:
After Chi
00 00 00 00 00 00 00 00 ...
After Iota
01 00 00 00 00 00 00 00 ... (following is equal to above)
However, there is something I don't understand: the bit that is changed in those test vectors is the eighth one, but our round constant is a 1 written on w-bits. If $w=8$ (implying a 200-bits message), everything is fine, but in the previous link, we have a message of 1600 bits, hence $w=64$. How can XOR-ing this 64-bits 0...01 change the eighth bit of the lane ?
EDIT: I will add my code below (it is still work in progress):
class Keccak(object):
def __init__(self):
self.l = 6
self.w = pow(2, self.l)
self.state = [[[0 for x in range(5)] for y in range(5)] for z in range(self.w)]
self.tmp_state = [[[0 for x in range(5)] for y in range(5)] for z in range(self.w)]
def init_state(self, S):
for x in range(5):
for y in range(5):
for z in range(self.w):
self.set_state(x, y, z, int(S[self.w*(5*y + x) + z], 2))
def init_tmp_state(self):
for x in range(5):
for y in range(5):
for z in range(self.w):
self.set_tmp_state(x, y, z, 0)
def index_processing(self, x, y, z):
return (z % self.w, (y + 2) % 5, (x + 2) % 5)
def get_state(self, x, y, z):
x, y, z = self.index_processing(x, y, z)
return self.state[x][y][z]
def set_state(self, x, y, z, v):
x, y, z = self.index_processing(x, y, z)
self.state[x][y][z] = v
def get_tmp_state(self, x, y, z):
x, y, z = self.index_processing(x, y, z)
return self.tmp_state[x][y][z]
def set_tmp_state(self, x, y, z, v):
x, y, z = self.index_processing(x, y, z)
self.tmp_state[x][y][z] = v
def state_to_string(self):
bit_string = []
for y in range(5):
for x in range(5):
for z in range(self.w):
bit_string.append(str(self.get_state(x, y, z)))
return ''.join(bit_string)
def rc(self, t):
if t % 255 == 0:
return 1
R = [1, 0, 0, 0, 0, 0, 0, 0]
for i in range(1, (t % 255) + 1):
R = [0] + R
R[0] ^= R[8]
R[4] ^= R[8]
R[5] ^= R[8]
R[6] ^= R[8]
R = R[:8]
return R[0]
def iota(self, i):
RC = [0 for j in range(self.w)]
for j in range(self.l + 1):
RC[pow(2, j) - 1] = self.rc(j + 7*i)
for z in range(self.w):
self.set_state(0, 0, z, self.get_state(0, 0, z) ^ RC[z])
def test_iota():
initial_state = "0000000000000000D2D2D2D2D2D2D2D20000000000000000E8E8E8E8E8E8E8E83A3A3A3A3A3A3A3A535353535353535300000000000000001D1D1D1D1D1D1D1D4E4E4E4E4E4E4E4E00000000000000004141414141414141E8E8E8E8E8E8E8E80000000000000000414141414141414126262626262626261D1D1D1D1D1D1D1D0000000000000000474747474747474718181818181818184747474747474747E8E8E8E8E8E8E8E835353535353535350000000000000000AFAFAFAFAFAFAFAF1212121212121212"
initial_state = bin(int(initial_state, 16))[2:].zfill(1600)
keccak = Keccak()
keccak.init_state(initial_state)
keccak.iota(0)
result = keccak.state_to_string()
correct_result = "0100000000000000D2D2D2D2D2D2D2D20000000000000000E8E8E8E8E8E8E8E83A3A3A3A3A3A3A3A535353535353535300000000000000001D1D1D1D1D1D1D1D4E4E4E4E4E4E4E4E00000000000000004141414141414141E8E8E8E8E8E8E8E80000000000000000414141414141414126262626262626261D1D1D1D1D1D1D1D0000000000000000474747474747474718181818181818184747474747474747E8E8E8E8E8E8E8E835353535353535350000000000000000AFAFAFAFAFAFAFAF1212121212121212"
correct_result = bin(int(correct_result, 16))[2:].zfill(1600)
print("\tIota:\t" + str(result == correct_result))
print(result[0:64] + '\n\n' + correct_result[0:64])
The test prints:
Iota: False
1000000000000000000000000000000000000000000000000000000000000000
0000000100000000000000000000000000000000000000000000000000000000