sha256.py

from bitarray import bitarray
from bitarray.util import ba2hex
from math import sqrt

def shr(x,s):
	return x >> s

def rotr(b, bits):
	return b[-bits:] + b[:-bits]

def xor2(a,b):
	return a^b

def xor3(a,b,c):
	return a^b^c

def b2int(b):
	return int(b.to01(),2)
	
def int2b(i,bits=32):
	return bitarray(bin(i)[2:].zfill(bits))

def addmod(*l):
	return int2b(sum([b2int(b) for b in l])%2**32)

def sigma0(x):
	return xor3(rotr(x,7), rotr(x,18), shr(x,3))

def sigma1(x):
	return xor3(rotr(x,17), rotr(x,19), shr(x,10))

def Sigma0(x):
	return xor3(rotr(x,2), rotr(x,13), rotr(x,22))

def Sigma1(x):
	return xor3(rotr(x,6), rotr(x,11), rotr(x,25))

def Ch(x,y,z):
	return x&y | ~x&z

def Maj(x,y,z):
	return (x&y)^(y&z)^(x&z)

def prime(i, primes):
    for prime in primes:
        if not (i == prime or i % prime):
            return False
    primes.add(i)
    return i

def historic(n):
    primes = set([2])
    i, p = 2, 0
    while True:
        if prime(i, primes):
            p += 1
            if p == n:
                return primes
        i += 1
        
def firstnprimes(n):
	return list(sorted(list(historic(n))))
        
P8 = firstnprimes(8)
P64 = firstnprimes(64)

print(P64)

def getcuberoots():
	primes = [int((prime**(1/3)-int(prime**(1/3)))*2**32) for prime in P64]
	primes = [bitarray(bin(prime)[2:].zfill(32)) for prime in primes]
	return primes

CONSTANTS = getcuberoots()

def pad(b):
	msglen = len(b)

	#print(b)
	b += bitarray("1")
	zeropadding = bitarray("0"*(512-(64+len(b))%512))
	print(len(zeropadding), "zpad")
	return b + zeropadding + bitarray(bin(msglen)[2:].zfill(64))

def msgsched(block):
	result = []
	for w in range(16):
		result.append(block[32*w:32*(w+1)])
		
	for w in range(16, 64):
		result.append(addmod(sigma1(result[-2]), result[-7], sigma0(result[-15]), result[-16]))
		
	return result

def ihv():
	primes = [int((sqrt(prime)-int(sqrt(prime)))*2**32) for prime in P8]
	primes = [bitarray(bin(prime)[2:].zfill(32)) for prime in primes]
	return primes

def compression(sched, initials=None):

	if initials is None:
		a,b,c,d,e,f,g,h = ihv()
	else:
		a,b,c,d,e,f,g,h = initials
	
	for w, W0 in enumerate(sched):
		
		K0 = CONSTANTS[w]
		
		T1 = addmod(Sigma1(e), Ch(e,f,g), h, K0, W0)
		T2 = addmod(Sigma0(a), Maj(a,b,c))
		
		a,b,c,d,e,f,g,h = addmod(T1,T2),a,b,c,addmod(d,T1),e,f,g
	
	ihvs = ihv() if initials is None else initials
	
	a,b,c,d,e,f,g,h = addmod(a,ihvs[0]),addmod(b,ihvs[1]),addmod(c,ihvs[2]),addmod(d,ihvs[3]),addmod(e,ihvs[4]),addmod(f,ihvs[5]),addmod(g,ihvs[6]),addmod(h,ihvs[7])

	return a,b,c,d,e,f,g,h

def hash(s):
	
	bytes = s.encode("utf8")
	
	b = bitarray()
	b.frombytes(bytes)
	print(len(b), "bits")
	b = pad(b)
	
	print(len(b), "bits padded")

	initials = None
	blocks = 1
	while len(b) > 0:
		print("Compressing block", blocks)
		sched = msgsched(b[:512])
		
		#for w, W in enumerate(sched):
		#	print("w"+str(w), W)
		
		initials = compression(sched, initials)
		#print("initials:")
		#for ini in initials:
		#	print(ini)
		b = b[512:]
		blocks += 1
	
	final = bitarray()
	for v in initials:
		final += v
	
	result = ba2hex(final)

	return result

from hashlib import sha256

for i in range(100):
	msg = "0"*i
	print(msg)
	result = hash(msg)
	true = sha256(msg.encode("utf8")).hexdigest()
	print(result)
	print(true)
	assert result == true