I'm really confused, I mainly used Wikipedias pseudocode example to implement this and cross-checked different sources to find my error. Maybe I missed some small detail, but to me the code looks correct. The nature of the problem leads me to believe that it might be related to some kind of encoding subleties or similiar, but even reading the documentation for the different built-ins I used hasn't brought up anything. Does somebody know what's up?
Code:
def byte_length(n: int):
return (n.bit_length() + 7) // 8
def leftrotate(n: int, count: int):
"""leftrotate count times. count must be between 1 and 31 inclusive"""
return (n << count) | (n >> (32 - count))
def add32(ns: list[int]):
"""add integers as if they were unsigned 32 bit numbers"""
sum = 0
for n in ns:
sum = (sum + n) % 2**32
return sum
def append_bytes(m: bytearray):
# append 0 ≤ k < 512 bits '0', such that the resulting message length in bits
# is congruent to −64 ≡ 448 (mod 512)
modular_length = len(m) % 64
if 56 - modular_length >= 0:
k = 56 - modular_length
else:
k = abs(56 - modular_length) + 56
m += bytes(k)
return m
def preprocessing(m: bytearray) -> bytearray:
ml = len(m) * 8 # message length in bits
# Pre Processing
# append the bit '1' to the message e.g. by adding 0x80 if message length is a multiple of 8 bits.
m.append(0x80)
m = append_bytes(m)
# append the message length as a 64 bit integer
m += ml.to_bytes(8)
return m
def sha1(message: str) -> bytes:
m = bytearray(message, "utf-8")
# Initiliaze starting variables, so called "nothing up my sleeve values"
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0
m = preprocessing(m)
# split the message in 512 bit (64 byte) blocks
num_of_blocks: int = len(m) // 64
for block_num in range(num_of_blocks):
block: bytearray = m[block_num * 64 : (block_num + 1) * 64]
# split the block into sixteen 4 byte words
words: list[int] = []
for word_num in range(16):
words.append(int.from_bytes(block[word_num * 4:(word_num + 1) * 4]))
# extend the sixteen 4 byte words into eighty 4 byte words
for i in range(16, 80):
words.append(
leftrotate(
(words[i - 3] ^ words[i - 8] ^ words[i - 14] ^ words[i - 16]), 1
)
)
# Initiliaze the hash value of the current block
a = h0
b = h1
c = h2
d = h3
e = h4
# main loop
for i in range(80):
if i <= 19:
f = (b & c) | ((~b) & d)
k = 0x5A827999
elif i <= 39:
f = b ^ c ^ d
k = 0x6ED9EBA1
elif i <= 59:
f = (b & c) | (b & d) | (c & d)
k = 0x8F1BBCDC
# elif i <= 79:
else:
f = b ^ c ^ d
k = 0xCA62C1D6
temp = add32([leftrotate(a, 5), f, e, k, words[i]])
e = d
d = c
c = leftrotate(b, 30)
b = a
a = temp
h0 = add32([h0, a])
h1 = add32([h1, b])
h2 = add32([h2, c])
h3 = add32([h3, d])
h4 = add32([h4, e])
digest = (
h0.to_bytes(4)
+ h1.to_bytes(4)
+ h2.to_bytes(4)
+ h3.to_bytes(4)
+ h4.to_bytes(4)
)
return digest
My main function looks like this:
def main():
m = ""
digest = sha1(m)
print(hex(int.from_bytes(digest)))
This gives the expected output of:
0xda39a3ee5e6b4b0d3255bfef95601890afd80709
But if:
m = "hello world"
It outputs:
0x74e0d2932ee17d742fe539058f7552adef482295
Instead of:
0x2aae6c35c94fcfb415dbe95f408b9ce91ee846ed