sha256 长度大于 56 时输出错误
sha256 incorrect output when the length is more than 56
我正在尝试学习 sha256 的每一步，所以我用 python 编写了一个代码，它使用二进制字符串而不是数学运算来完全理解它。
当输入少于 56 个字符时，代码工作正常，但当输入等于或多于 56 个字符时，输出不正确：
例如当输入是：
ba7816bf8f01cfea414140de5dae2223bda12ae1a5324sfdserew3ra
而不是1caa150674ab1aed030dc69f9b86dbcbc412e6e1dd20344eeaa21687acae7789
我得到8492782cc396d4454980c9b63f127c5730da7d838822f8f37b1c7705d2630b88
代码：
Operations.py
class Operations:
def add(self, data1, data2):
x = data1
y = data2
carry = 0
result = ""
for i in range(len(data1) -1, -1, -1):
r = carry
r += 1 if x[i] == '1' else 0
r += 1 if y[i] == '1' else 0
result = ('1' if r % 2 == 1 else '0') + result
carry = 0 if r < 2 else 1
if carry != 0: result = '1' + result
return result[-len(data1):]
def xor(self, data1, data2):
result = ""
for i in range(len(data1)):
temp1 = data1[i]
temp2 = data2[i]
if (temp1 == "0" and temp2 == "0") or (temp1 == "1" and temp2 == "1"):
result += "0"
else:
result += "1"
return result
def shiftRight(self, data, turn):
result = "0" * turn + data
return result[:len(data)]
def rotateRight(self, data, turn):
result = None
for i in range(turn):
if result:
temp = result[-1]
result = (temp + result)[:len(data)]
else:
temp = data[-1]
result = (temp + data)[:len(data)]
return result
Functions.py
from operations import Operations
class Functions(Operations):
def sigma0(self, data): # Lowercase sigma
temp1 = self.rotateRight(data, 7)
temp2 = self.rotateRight(data, 18)
temp3 = self.shiftRight(data, 3)
result = self.xor(temp3, self.xor(temp1, temp2))
return result
def sigma1(self, data): # Lowercase sigma
temp1 = self.rotateRight(data, 17)
temp2 = self.rotateRight(data, 19)
temp3 = self.shiftRight(data, 10)
result = self.xor(temp3, self.xor(temp1, temp2))
return result
def gamma0(self, data): # Uppercase sigma
temp1 = self.rotateRight(data, 2)
temp2 = self.rotateRight(data, 13)
temp3 = self.rotateRight(data, 22)
result = self.xor(temp3, self.xor(temp1, temp2))
return result
def gamma1(self, data): # Uppercase sigma
temp1 = self.rotateRight(data, 6)
temp2 = self.rotateRight(data, 11)
temp3 = self.rotateRight(data, 25)
result = self.xor(temp3, self.xor(temp1, temp2))
return result
def choice(self, x, y, z):
result = ""
for i in range(len(x)):
result += y[i] if x[i] == "1" else z[i]
return result
def majority(self, x, y, z):
result = ""
for i in range(len(x)):
temp0 = 0
temp1 = 0
temp0 += 1 if x[i] == "0" else 0
temp1 += 1 if x[i] == "1" else 0
temp0 += 1 if y[i] == "0" else 0
temp1 += 1 if y[i] == "1" else 0
temp0 += 1 if z[i] == "0" else 0
temp1 += 1 if z[i] == "1" else 0
if temp0 > temp1:
result += "0"
else:
result += "1"
return result
Main.py
from math import ceil
from copy import copy
from functions import Functions
_k = [0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2]
_h = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]
class SHA256(Functions):
blocks = []
def __init__(self):
global _k, _h
_k = [f'{i:b}'.zfill(32) for i in _k]
_h = [f'{i:b}'.zfill(32) for i in _h]
def message_to_blocks(self, message):
chunk = 56
data = [format(ord(x), 'b').zfill(8) for x in message]
for i in range(ceil(len(data) / chunk)):
self.blocks.append(data[chunk * i:chunk * (i + 1)])
self.blocks[i] = ''.join(self.blocks[i])
length = f'{len(self.blocks[i]):b}'
self.blocks[i] += '1'
self.blocks[i] = self.blocks[i].ljust(512, '0')
# add length to last 64 bit
self.blocks[i] = self.blocks[i][:-len(length)]
self.blocks[i] += length
def message_schedule(self, data):
schedule = []
n = 32
# first 16 words
schedule = [(data[i:i+n]) for i in range(0, len(data), n)]
# generate the rest
for i in range(16, 64):
temp1 = self.sigma1(schedule[-2])
temp2 = self.sigma0(schedule[-15])
result = self.add(temp1, self.add(schedule[-7], self.add(temp2, schedule[-16])))
schedule.append(result)
return schedule
def compress(self):
for block in self.blocks:
temp_h = copy(_h)
_w = self.message_schedule(block)
for i in range(64):
T1 = [self.gamma1(_h[4]), self.choice(_h[4], _h[5], _h[6]), _h[7], _k[i], _w[i]]
T1 = self.add(T1[0], self.add(T1[1], self.add(T1[2], self.add(T1[3], T1[4]))))
T2 = [self.gamma0(_h[0]), self.majority(_h[0], _h[1], _h[2])]
T2 = self.add(T2[0], T2[1])
# shift all constants down
_h[7] = _h[6] # h
_h[6] = _h[5] # g
_h[5] = _h[4] # f
_h[4] = _h[3] # e
_h[3] = _h[2] # d
_h[2] = _h[1] # c
_h[1] = _h[0] # b
# compress
_h[0] = self.add(T1, T2)
_h[4] = self.add(_h[4], T1)
# add with initial values
_h[0] = self.add(_h[0], temp_h[0])
_h[1] = self.add(_h[1], temp_h[1])
_h[2] = self.add(_h[2], temp_h[2])
_h[3] = self.add(_h[3], temp_h[3])
_h[4] = self.add(_h[4], temp_h[4])
_h[5] = self.add(_h[5], temp_h[5])
_h[6] = self.add(_h[6], temp_h[6])
_h[7] = self.add(_h[7], temp_h[7])
return self.digest(_h)
def digest(self, hashes):
final_hash = ""
for hash in hashes:
t = hex(int(hash, 2))
final_hash += t[2:]
return final_hash
a = SHA256()
a.message_to_blocks("ba7816bf8f01cfea414140de5dae2223bda12ae1a5324sfdserew3ra")
print(a.compress())
The code works fine when the input is less than 56 characters but when it's equal or more than 56 characters the output is incorrect
这部分有问题：
length = f'{len(self.blocks[i]):b}'
self.blocks[i] += '1'
self.blocks[i] = self.blocks[i].ljust(512, '0')
# add length to last 64 bit
self.blocks[i] = self.blocks[i][:-len(length)]
self.blocks[i] += length
错误在于零填充的计算方式与非 64 位宽度的长度相结合。实际上，您的代码用零填充最后一个消息块，因此它的长度为 512 位，然后用未填充的二进制长度 (111000000) 替换最后的 n 位，但这在某些情况下无法正常工作其中零填充小于 64 位。
结果是代码将总消息输入处理为：
01100010011000010011011100111000 00110001001101100110001001100110 00111000011001100011000000110001 01100011011001100110010101100001 00110100001100010011010000110001 00110100001100000110010001100101 00110101011001000110000101100101 00110010001100100011001000110011 01100010011001000110000100110001 00110010011000010110010100110001 01100001001101010011001100110010 00110100011100110110011001100100 01110011011001010111001001100101 01110111001100110111001001100001 10000000000000000000000000000000 00000000000000000000000111000000
而不是：
01100010011000010011011100111000 00110001001101100110001001100110 00111000011001100011000000110001 01100011011001100110010101100001 00110100001100010011010000110001 00110100001100000110010001100101 00110101011001000110000101100101 00110010001100100011001000110011 01100010011001000110000100110001 00110010011000010110010100110001 01100001001101010011001100110010 00110100011100110110011001100100 01110011011001010111001001100101 01110111001100110111001001100001 10000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000111000000
我正在尝试学习 sha256 的每一步，所以我用 python 编写了一个代码，它使用二进制字符串而不是数学运算来完全理解它。
当输入少于 56 个字符时，代码工作正常，但当输入等于或多于 56 个字符时，输出不正确：
例如当输入是：
ba7816bf8f01cfea414140de5dae2223bda12ae1a5324sfdserew3ra
而不是1caa150674ab1aed030dc69f9b86dbcbc412e6e1dd20344eeaa21687acae7789
我得到8492782cc396d4454980c9b63f127c5730da7d838822f8f37b1c7705d2630b88
代码：
Operations.py
class Operations:
def add(self, data1, data2):
x = data1
y = data2
carry = 0
result = ""
for i in range(len(data1) -1, -1, -1):
r = carry
r += 1 if x[i] == '1' else 0
r += 1 if y[i] == '1' else 0
result = ('1' if r % 2 == 1 else '0') + result
carry = 0 if r < 2 else 1
if carry != 0: result = '1' + result
return result[-len(data1):]
def xor(self, data1, data2):
result = ""
for i in range(len(data1)):
temp1 = data1[i]
temp2 = data2[i]
if (temp1 == "0" and temp2 == "0") or (temp1 == "1" and temp2 == "1"):
result += "0"
else:
result += "1"
return result
def shiftRight(self, data, turn):
result = "0" * turn + data
return result[:len(data)]
def rotateRight(self, data, turn):
result = None
for i in range(turn):
if result:
temp = result[-1]
result = (temp + result)[:len(data)]
else:
temp = data[-1]
result = (temp + data)[:len(data)]
return result
Functions.py
from operations import Operations
class Functions(Operations):
def sigma0(self, data): # Lowercase sigma
temp1 = self.rotateRight(data, 7)
temp2 = self.rotateRight(data, 18)
temp3 = self.shiftRight(data, 3)
result = self.xor(temp3, self.xor(temp1, temp2))
return result
def sigma1(self, data): # Lowercase sigma
temp1 = self.rotateRight(data, 17)
temp2 = self.rotateRight(data, 19)
temp3 = self.shiftRight(data, 10)
result = self.xor(temp3, self.xor(temp1, temp2))
return result
def gamma0(self, data): # Uppercase sigma
temp1 = self.rotateRight(data, 2)
temp2 = self.rotateRight(data, 13)
temp3 = self.rotateRight(data, 22)
result = self.xor(temp3, self.xor(temp1, temp2))
return result
def gamma1(self, data): # Uppercase sigma
temp1 = self.rotateRight(data, 6)
temp2 = self.rotateRight(data, 11)
temp3 = self.rotateRight(data, 25)
result = self.xor(temp3, self.xor(temp1, temp2))
return result
def choice(self, x, y, z):
result = ""
for i in range(len(x)):
result += y[i] if x[i] == "1" else z[i]
return result
def majority(self, x, y, z):
result = ""
for i in range(len(x)):
temp0 = 0
temp1 = 0
temp0 += 1 if x[i] == "0" else 0
temp1 += 1 if x[i] == "1" else 0
temp0 += 1 if y[i] == "0" else 0
temp1 += 1 if y[i] == "1" else 0
temp0 += 1 if z[i] == "0" else 0
temp1 += 1 if z[i] == "1" else 0
if temp0 > temp1:
result += "0"
else:
result += "1"
return result
Main.py
from math import ceil
from copy import copy
from functions import Functions
_k = [0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2]
_h = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]
class SHA256(Functions):
blocks = []
def __init__(self):
global _k, _h
_k = [f'{i:b}'.zfill(32) for i in _k]
_h = [f'{i:b}'.zfill(32) for i in _h]
def message_to_blocks(self, message):
chunk = 56
data = [format(ord(x), 'b').zfill(8) for x in message]
for i in range(ceil(len(data) / chunk)):
self.blocks.append(data[chunk * i:chunk * (i + 1)])
self.blocks[i] = ''.join(self.blocks[i])
length = f'{len(self.blocks[i]):b}'
self.blocks[i] += '1'
self.blocks[i] = self.blocks[i].ljust(512, '0')
# add length to last 64 bit
self.blocks[i] = self.blocks[i][:-len(length)]
self.blocks[i] += length
def message_schedule(self, data):
schedule = []
n = 32
# first 16 words
schedule = [(data[i:i+n]) for i in range(0, len(data), n)]
# generate the rest
for i in range(16, 64):
temp1 = self.sigma1(schedule[-2])
temp2 = self.sigma0(schedule[-15])
result = self.add(temp1, self.add(schedule[-7], self.add(temp2, schedule[-16])))
schedule.append(result)
return schedule
def compress(self):
for block in self.blocks:
temp_h = copy(_h)
_w = self.message_schedule(block)
for i in range(64):
T1 = [self.gamma1(_h[4]), self.choice(_h[4], _h[5], _h[6]), _h[7], _k[i], _w[i]]
T1 = self.add(T1[0], self.add(T1[1], self.add(T1[2], self.add(T1[3], T1[4]))))
T2 = [self.gamma0(_h[0]), self.majority(_h[0], _h[1], _h[2])]
T2 = self.add(T2[0], T2[1])
# shift all constants down
_h[7] = _h[6] # h
_h[6] = _h[5] # g
_h[5] = _h[4] # f
_h[4] = _h[3] # e
_h[3] = _h[2] # d
_h[2] = _h[1] # c
_h[1] = _h[0] # b
# compress
_h[0] = self.add(T1, T2)
_h[4] = self.add(_h[4], T1)
# add with initial values
_h[0] = self.add(_h[0], temp_h[0])
_h[1] = self.add(_h[1], temp_h[1])
_h[2] = self.add(_h[2], temp_h[2])
_h[3] = self.add(_h[3], temp_h[3])
_h[4] = self.add(_h[4], temp_h[4])
_h[5] = self.add(_h[5], temp_h[5])
_h[6] = self.add(_h[6], temp_h[6])
_h[7] = self.add(_h[7], temp_h[7])
return self.digest(_h)
def digest(self, hashes):
final_hash = ""
for hash in hashes:
t = hex(int(hash, 2))
final_hash += t[2:]
return final_hash
a = SHA256()
a.message_to_blocks("ba7816bf8f01cfea414140de5dae2223bda12ae1a5324sfdserew3ra")
print(a.compress())
The code works fine when the input is less than 56 characters but when it's equal or more than 56 characters the output is incorrect
这部分有问题：
length = f'{len(self.blocks[i]):b}'
self.blocks[i] += '1'
self.blocks[i] = self.blocks[i].ljust(512, '0')
# add length to last 64 bit
self.blocks[i] = self.blocks[i][:-len(length)]
self.blocks[i] += length
错误在于零填充的计算方式与非 64 位宽度的长度相结合。实际上，您的代码用零填充最后一个消息块，因此它的长度为 512 位，然后用未填充的二进制长度 (111000000) 替换最后的 n 位，但这在某些情况下无法正常工作其中零填充小于 64 位。
结果是代码将总消息输入处理为：
01100010011000010011011100111000 00110001001101100110001001100110 00111000011001100011000000110001 01100011011001100110010101100001 00110100001100010011010000110001 00110100001100000110010001100101 00110101011001000110000101100101 00110010001100100011001000110011 01100010011001000110000100110001 00110010011000010110010100110001 01100001001101010011001100110010 00110100011100110110011001100100 01110011011001010111001001100101 01110111001100110111001001100001 10000000000000000000000000000000 00000000000000000000000111000000
而不是：
01100010011000010011011100111000 00110001001101100110001001100110 00111000011001100011000000110001 01100011011001100110010101100001 00110100001100010011010000110001 00110100001100000110010001100101 00110101011001000110000101100101 00110010001100100011001000110011 01100010011001000110000100110001 00110010011000010110010100110001 01100001001101010011001100110010 00110100011100110110011001100100 01110011011001010111001001100101 01110111001100110111001001100001 10000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000111000000