SHA-256 is everywhere: git object ids, TLS certificates, password storage schemes, package lockfiles, blockchains. Most of us call hashlib.sha256() and move on. But the inside is surprisingly small: some bit rotations, some additions modulo 2^32, and a loop that runs 64 times.
In this post we will write SHA-256 from scratch in Python, in under 60 lines, and check it against hashlib on thousands of random inputs.
The big picture
SHA-256 works in three steps:
- Pad the message so its length is a multiple of 512 bits (64 bytes).
- Split it into 64 byte blocks.
- Compress each block into a running state of eight 32 bit words. The final state, written as hex, is the digest.
Everything works on 32 bit unsigned integers, so we need a mask and a right rotation:
MASK = 0xFFFFFFFF
def rotr(x, n):
return ((x >> n) | (x << (32 - n))) & MASK
Python integers are unbounded, so we mask after every addition to emulate 32 bit overflow.
Step 1: padding
The rule: append a single 1 bit, then 0 bits until the length is 56 bytes mod 64, then the original length in bits as a 64 bit big endian integer.
def pad(message: bytes) -> bytes:
bit_len = len(message) * 8
message += b"\x80"
while len(message) % 64 != 56:
message += b"\x00"
return message + bit_len.to_bytes(8, "big")
0x80 is 10000000 in binary: the 1 bit followed by seven zeros. A classic bug is writing the length in bytes instead of bits, or little endian instead of big endian. Both produce a hash that looks perfectly plausible and is completely wrong.
Note that a 55 byte message fits in one block, but a 56 byte message needs two, because the length field no longer fits. Test that boundary.
The constants are not magic
SHA-256 uses two tables of constants. They look random but they are "nothing up my sleeve" numbers:
- The initial state
H0is the first 32 bits of the fractional parts of the square roots of the first 8 primes. - The round constants
Kare the first 32 bits of the fractional parts of the cube roots of the first 64 primes.
You can regenerate them with integer math to convince yourself:
import math
primes = [p for p in range(2, 400) if all(p % d for d in range(2, math.isqrt(p) + 1))][:64]
def icbrt(n):
lo, hi = 0, 1 << 40
while lo < hi:
mid = (lo + hi + 1) // 2
if mid ** 3 <= n:
lo = mid
else:
hi = mid - 1
return lo
K = [icbrt(p << 96) & MASK for p in primes]
H0 = [math.isqrt(p << 64) & MASK for p in primes[:8]]
Shifting left by 96 before the cube root (or 64 before the square root) gives us 32 fractional bits, and the mask throws away the integer part. In the full listing below the tables are written out as literals, which is how most implementations ship them.
Step 2: the message schedule
Each 64 byte block becomes sixteen 32 bit big endian words. SHA-256 then expands them to 64 words, mixing earlier words with rotations and shifts:
w = [int.from_bytes(block[i:i + 4], "big") for i in range(0, 64, 4)]
for t in range(16, 64):
s0 = rotr(w[t - 15], 7) ^ rotr(w[t - 15], 18) ^ (w[t - 15] >> 3)
s1 = rotr(w[t - 2], 17) ^ rotr(w[t - 2], 19) ^ (w[t - 2] >> 10)
w.append((w[t - 16] + s0 + w[t - 7] + s1) & MASK)
Watch the last term in s0 and s1: it is a plain shift (>>), not a rotation. Mixing those up is the most common mistake in hand written SHA-256.
Step 3: the 64 rounds
The state is eight words, traditionally called a to h. Each round computes two temporary values and shifts the words down by one position:
a, b, c, d, e, f, g, h = state
for t in range(64):
S1 = rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25)
ch = (e & f) ^ (~e & g)
t1 = (h + S1 + ch + K[t] + w[t]) & MASK
S0 = rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22)
maj = (a & b) ^ (a & c) ^ (b & c)
t2 = (S0 + maj) & MASK
h, g, f, e = g, f, e, (d + t1) & MASK
d, c, b, a = c, b, a, (t1 + t2) & MASK
Two small functions do the nonlinear work:
-
ch("choose"): for each bit, ifeis 1 take the bit fromf, otherwise fromg. -
maj("majority"): each output bit is whatever at least two ofa,b,cagree on.
~e in Python is negative, but the & g with a 32 bit value brings it back into range, so no extra mask is needed there.
After the 64 rounds, add the result back into the previous state word by word. That feed forward is what makes the compression function hard to invert.
The full listing
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,
]
H0 = [
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
]
MASK = 0xFFFFFFFF
def rotr(x, n):
return ((x >> n) | (x << (32 - n))) & MASK
def pad(message: bytes) -> bytes:
bit_len = len(message) * 8
message += b"\x80"
while len(message) % 64 != 56:
message += b"\x00"
return message + bit_len.to_bytes(8, "big")
def compress(state, block):
w = [int.from_bytes(block[i:i + 4], "big") for i in range(0, 64, 4)]
for t in range(16, 64):
s0 = rotr(w[t - 15], 7) ^ rotr(w[t - 15], 18) ^ (w[t - 15] >> 3)
s1 = rotr(w[t - 2], 17) ^ rotr(w[t - 2], 19) ^ (w[t - 2] >> 10)
w.append((w[t - 16] + s0 + w[t - 7] + s1) & MASK)
a, b, c, d, e, f, g, h = state
for t in range(64):
S1 = rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25)
ch = (e & f) ^ (~e & g)
t1 = (h + S1 + ch + K[t] + w[t]) & MASK
S0 = rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22)
maj = (a & b) ^ (a & c) ^ (b & c)
t2 = (S0 + maj) & MASK
h, g, f, e = g, f, e, (d + t1) & MASK
d, c, b, a = c, b, a, (t1 + t2) & MASK
return [(x + y) & MASK for x, y in zip(state, [a, b, c, d, e, f, g, h])]
def sha256(message: bytes) -> str:
state = H0[:]
padded = pad(message)
for i in range(0, len(padded), 64):
state = compress(state, padded[i:i + 64])
return "".join(f"{x:08x}" for x in state)
Testing it
Start with the standard test vectors:
assert sha256(b"") == "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
assert sha256(b"abc") == "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"
Then compare against hashlib on random inputs, making sure to cover every length around the padding boundary:
import hashlib, os
for n in list(range(200)) + [1000, 4096, 100000]:
m = os.urandom(n)
assert sha256(m) == hashlib.sha256(m).hexdigest(), n
print("all good")
This passes for every length from 0 to 199 bytes plus a few large inputs. It is slow compared to hashlib (pure Python, one bit operation at a time), and it is for learning only: use your standard library for anything real.
Where to go next
Once you have SHA-256, the natural next step is HMAC: H((K xor opad) || H((K xor ipad) || message)). It is only a few more lines and it lets you sign and verify tokens. When you verify, compare the signatures in constant time (hmac.compare_digest in Python) so you do not leak timing information.
If you want to build this step by step with tests at every stage (padding, message schedule, one round, full digest, HMAC and signed tokens) in any language, we put together a guided project for it: Build SHA-256 and HMAC from scratch. It is in beta, so feedback is very welcome.
Top comments (0)