Мне нужно реализовать хеширование SHA3. Вроде все сделал, но выводит неправильный результат.
Код писал на основе данной статьи. Исключением является только преобразование ι
, которое я реализовал по-другому, с использованием раундовых констант, которые у меня изначально хранятся в массиве, а не высчитываются, как это делается в документе (если, конечно, я правильно понял).
Также для хранения битов использовал класс BitArray из модуля bitstring, который загрузил отсюда.
Код на питоне 3:
from math import log
from bitstring import BitArray
rc = [
BitArray('0x0000000000000001'), BitArray('0x0000000000008082'),
BitArray('0x800000000000808A'), BitArray('0x8000000080008000'),
BitArray('0x000000000000808B'), BitArray('0x0000000080000001'),
BitArray('0x8000000080008081'), BitArray('0x8000000000008009'),
BitArray('0x000000000000008A'), BitArray('0x0000000000000088'),
BitArray('0x0000000080008009'), BitArray('0x000000008000000A'),
BitArray('0x000000008000808B'), BitArray('0x800000000000008B'),
BitArray('0x8000000000008089'), BitArray('0x8000000000008003'),
BitArray('0x8000000000008002'), BitArray('0x8000000000000080'),
BitArray('0x000000000000800A'), BitArray('0x800000008000000A'),
BitArray('0x8000000080008081'), BitArray('0x8000000000008080'),
BitArray('0x0000000080000001'), BitArray('0x8000000080008008')]
def init_state(b, r):
w = b // 25
l = int(log(w, 2))
nr = 12 + 2*l
c = b - r
return w, c, l, nr
b = 1600
r = 576
d = 512
w, c, l, nr = init_state(b, r)
# 3-мерный массив -> BitArray
def from_cube(a):
return BitArray([a[x][y][z] for x in range(5) for y in range(5) for z in range(w)])
# BitArray -> 3-мерный массив
def to_cube(s):
return [[[s[(5*x + y)*w + z] for z in range(w)] for y in range(5)] for x in range(5)]
def theta(a):
c = [[False for z in range(w)] for x in range(5)]
d = [[False for z in range(w)] for x in range(5)]
for x in range(5):
for z in range(w):
c[x][z] = a[x][0][z] ^ a[x][1][z] ^ a[x][2][z] ^ a[x][3][z] ^ a[x][4][z]
for x in range(5):
for z in range(w):
d[x][z] = c[(x-1) % 5][z] ^ c[(x+1) % 5][(z-1) % w]
for x in range(5):
for y in range(5):
for z in range(w):
a[x][y][z] ^= d[x][z]
return a
def ro(a):
x, y = 1, 0
for t in range(24):
for z in range(w):
a[x][y][z] = a[x][y][(z - (t + 1)*(t + 2)//2) % w]
x, y = y, ((2*x + 3*y) % 5)
return a
def pi(a):
for x in range(5):
for y in range(5):
for z in range(w):
a[x][y][z] = a[(x + 3*y) % 5][x][z]
return a
def hi(a):
for x in range(5):
for y in range(5):
for z in range(w):
a[x][y][z] ^= (~a[(x + 1) % 5][y][z] and a[(x + 2) % 5][y][z])
return a
def yota(a, ir):
a[0][0] = list(a[0][0] ^ rc[ir])
return a
def f(s):
a = to_cube(s)
for ir in range(12 + 2*l - nr, 12 + 2*l):
a = yota(hi(pi(ro(theta(a)))), ir)
s = from_cube(a)
return s
# Дополнение pad10*1
def pad10_1(x, m):
j = (-2-m) % x
return BitArray(bin='1' + j * '0' + '1')
# Строка -> BitArray
def str_to_hashable(s):
bar = BitArray(s.encode())
return bar, len(bar)
# Деление на блоки, хеширование
def hash(string):
s, s_l = str_to_hashable(string)
s += pad10_1(r, s_l)
blocks = [s[i:i+r] for i in range(0, len(s), r)]
n = len(blocks)
state = BitArray(bin=b * '0')
for i in range(n):
state = f(state ^ (blocks[i] + BitArray(bin=c * '0')))
z = state[:r]
while d > len(z):
state = f(state)
z += state[:r]
return z[:d].hex
Пример:
string = 'The quick brown fox jumps over the lazy dog'
print(hash(string))
Должен выводить:
01dedd5de4ef14642445ba5f5b97c15e47b9ad931326e4b0727cd94cefc44fff23f07bf543139939b49128caf436dc1bdee54fcb24023a08d9403f9b4bf0d450
Выводит:
536672ec4d9b50475d3e5615d3e5615d89eafac4f57d627a6b06dee4444995acfc71c4f15a7929b48f0d8085609cab1d9e84fa2e7926dbf1480d19480d19480d