SHA-256 From Scratch

hard · cryptography, hashing, bitwise

SHA-256 From Scratch

Implement SHA-256 without using any crypto libraries.

You must handle:

Merkle-Damgard padding
Message schedule
Compression rounds
Final digest formatting

Function signature

func SHA256(msg []byte) [32]byte

SHA-256 summary

Block size: 512 bits (64 bytes)
Output size: 256 bits (32 bytes)
Word size: 32 bits

Padding

Given a message of length L bytes:

Append 0x80.
Append 0x00 bytes until length is 56 mod 64.
Append the original length in bits as a 64-bit big-endian integer.

Message schedule

For each 64-byte block, parse 16 big-endian words W[0..15]. Then for i=16..63:

W[i] = s1(W[i-2]) + W[i-7] + s0(W[i-15]) + W[i-16]

where:

s0(x) = ROTR7(x)  ^ ROTR18(x) ^ (x >> 3)
s1(x) = ROTR17(x) ^ ROTR19(x) ^ (x >> 10)

Compression (64 rounds)

Initialize a..h from the IV. For i=0..63:

T1 = h + S1(e) + Ch(e,f,g) + K[i] + W[i]
T2 = S0(a) + Maj(a,b,c)

h = g
f = e
 e = d + T1
 d = c
 c = b
 b = a
 a = T1 + T2

where:

Ch(x,y,z)  = (x & y) ^ (^x & z)
Maj(x,y,z) = (x & y) ^ (x & z) ^ (y & z)
S0(x) = ROTR2(x) ^ ROTR13(x) ^ ROTR22(x)
S1(x) = ROTR6(x) ^ ROTR11(x) ^ ROTR25(x)

Finally, add a..h back into the hash state.

Notes

Use big-endian for word parsing and output.
All arithmetic is 32-bit with wraparound.
This is a learning exercise. Do not ship your own SHA-256 implementation.

package solution

import "encoding/binary"

var sha256IV = [8]uint32{
	0x6a09e667,
	0xbb67ae85,
	0x3c6ef372,
	0xa54ff53a,
	0x510e527f,
	0x9b05688c,
	0x1f83d9ab,
	0x5be0cd19,
}

var sha256K = [64]uint32{
	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,
}

func rotr32(x uint32, n uint) uint32 {
	return (x >> n) | (x << (32 - n))
}

func ch(x, y, z uint32) uint32 {
	return (x & y) ^ (^x & z)
}

func maj(x, y, z uint32) uint32 {
	return (x & y) ^ (x & z) ^ (y & z)
}

func bigSigma0(x uint32) uint32 {
	return rotr32(x, 2) ^ rotr32(x, 13) ^ rotr32(x, 22)
}

func bigSigma1(x uint32) uint32 {
	return rotr32(x, 6) ^ rotr32(x, 11) ^ rotr32(x, 25)
}

func smallSigma0(x uint32) uint32 {
	return rotr32(x, 7) ^ rotr32(x, 18) ^ (x >> 3)
}

func smallSigma1(x uint32) uint32 {
	return rotr32(x, 17) ^ rotr32(x, 19) ^ (x >> 10)
}

// SHA256 computes the SHA-256 digest of msg.
func SHA256(msg []byte) [32]byte {
	// TODO: implement padding, message schedule, compression, and output.
	var out [32]byte
	_ = binary.BigEndian
	return out
}