SHA-256, binary

sha256.py

"""
This code has been written just for fun, it is slow and may produce inaccurate results.

The idea was to transition from mathematics to an algorithm.
"""

import binascii
import hashlib
import itertools


def int_to_list(n):

    return [int(i) for i in '{:32b}'.format(n).replace(' ', '0')]


def list_to_int(l):

    s = 0
    c = 1
    for i in reversed(l):
        s += i * c
        c *= 2

    return s


def list_to_digest(binary):

    res = b''
    for i in range(0, len(binary), 8):
        res += list_to_int(binary[i: i + 8]).to_bytes(1, byteorder='big')
    return res


def bin_maj(*parts):

    res = []
    for i in range(0, 32):
        s = 0
        for part in parts:
            s += part[i]
        res.append(1 if s > len(parts) // 2 else 0)

    return res


def bin_rrot(a, shift):

    return a[-shift:] + a[:-shift]


def bin_rshift(a, shift):

    return (shift * [0]) + list(a[:-shift])


def bin_xor(*parts):

    res = []
    for i in range(0, len(parts[0])):
        s = 0
        for part in parts:
            s += part[i]
        res.append(1 if s % 2 == 1 else 0)
    return res


def bin_ch(n, l1, l2):

    res = []
    for i in range(0, len(n)):
        res.append(l1[i] if n[i] else l2[i])
    return res


def bin_sum(*parts):

    res = []
    mov = 0
    for i in range(0, len(parts[0])):
        s = 0
        for p in parts:
            s += p[-i-1]
        s += mov
        res.append(s % 2)
        mov = s // 2
    res.reverse()
    return res[-32:]


def to_chunks(iterable, n=512):

    it = iter(iterable)
    while True:
        chunk = tuple(itertools.islice(it, n))
        if not chunk:
            return
        yield chunk


# Provided by NSA

_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
)

_h = (
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
    0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
)


def preprocess(data_str):

    data_bin = []
    for c in data_str:
        for i in '{:8b}'.format(c).replace(' ', '0'):
            data_bin.append(int(i))

    data_bin.append(1)

    while len(data_bin) % 512 != 448:
        data_bin.append(0)

    for i in '{:64b}'.format(len(data_str) * 8).replace(' ', '0'):
        data_bin.append(int(i))

    return data_bin


def sha256(data):

    a0, b0, c0, d0, e0, f0, g0, h0 = map(int_to_list, _h)

    for chunk in to_chunks(preprocess(data), n=512):

        w = [0] * 64
        w[0:16] = to_chunks(chunk, n=32)

        for i in range(16, 64):
            s0 = bin_xor(bin_rrot(w[i-15], 7), bin_rrot(w[i-15], 18), bin_rshift(w[i-15], 3))
            s1 = bin_xor(bin_rrot(w[i-2], 17), bin_rrot(w[i-2], 19), bin_rshift(w[i-2], 10))

            w[i] = bin_sum(
                w[i-16],
                s0,
                w[i-7],
                s1
            )

        a, b, c, d, e, f, g, h = a0, b0, c0, d0, e0, f0, g0, h0

        for i in range(0, 64):

            sum1 = bin_sum(
                w[i],
                int_to_list(_k[i]),
                h,
                bin_ch(e, f, g),
                bin_xor(bin_rrot(e, 6), bin_rrot(e, 11), bin_rrot(e, 25))
            )

            sum2 = bin_sum(
                bin_xor(bin_rrot(a, 2), bin_rrot(a, 13), bin_rrot(a, 22)),
                bin_maj(a, b, c),
                sum1
            )

            a, b, c, d, e, f, g, h = sum2, a, b, c, bin_sum(d, sum1)[-32:], e, f, g

        a0 = bin_sum(a0, a)
        b0 = bin_sum(b0, b)
        c0 = bin_sum(c0, c)
        d0 = bin_sum(d0, d)
        e0 = bin_sum(e0, e)
        f0 = bin_sum(f0, f)
        g0 = bin_sum(g0, g)
        h0 = bin_sum(h0, h)

    return a0 + b0 + c0 + d0 + e0 + f0 + g0 + h0


if __name__ == '__main__':
    assert binascii.b2a_hex(list_to_digest(sha256(''))) == b'e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855'
    block = b'0000002005dff584057d6f6fa7276bf0df228b5afc7f75db1c164601000000000000000076101602fbe0b2afe3fd7a5cc8da47ebcfe5c09d160ccb2df22b280798126e535e76ea57d48e0418f6a8b09b'
    assert list_to_digest(sha256(block)) == hashlib.sha256(block).digest()