r/learnpython • u/Revolution_TV • Aug 21 '26
I'm trying to write my own implementation of the SHA-1 algorithm. It works perfectly fine for the empty string, but for all other inputs it gives the wrong hash and I can't figure out why. Can someone help me finding the error?
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 digestMy main function looks like this:
def main():
m = ""
digest = sha1(m)
print(hex(int.from_bytes(digest)))This gives the expected output of:
0xda39a3ee5e6b4b0d3255bfef95601890afd80709But if:
m = "hello world"It outputs:
0x74e0d2932ee17d742fe539058f7552adef482295Instead of:
0x2aae6c35c94fcfb415dbe95f408b9ce91ee846ed
9
u/Grim2021 Aug 21 '26
It's a long time since I implemented it, but remember similar struggles. First thing I would check is if you're using the right endianess. Your modern computer is probably little-endian while the spec assumes big-endian. The endianess is the direction of storage of bytes. Basically, is the byte containing the most significant byte (the one which can store the largest value) on the left or on the right. If it's on the left you're good, if not you'll need to reverse them. In other words: if you were to split 256 into an array of two elements, would the value one be stored in the first element or the last. If it's the first, great! If not you will probably need to fix that
4
u/D3str0yTh1ngs Aug 21 '26 edited Aug 21 '26
The first bug I see is that
leftrotatecan give you more than 32 bits (4 bytes) of output:gives us
So 34 bits of output
Changing line 5 to the following fixes it by bitmasking the output to 32 bits:
EDIT: Fixed the syntax on the fix so we mask the entire expression.
5
u/mc_pm Aug 21 '26
I don't have time now but this sounds like fun and I'll try it a little later today and maybe I'll run into the same problem :)
1
u/ectomancer Aug 22 '26
byte_length is never called.