SHA 256 pseuedocode?

user_1001104 0
Viewed 37970

I've been trying to work out how SHA-256 works. One thing I've been doing for other algorithms is I've worked out a sort of step by step pseudocode function for the algorithm.

I've tried to do the same for SHA256 but thus far I'm having quite a bit of trouble.

I've tried to work out how the Wikipedia diagram works but besides the text part explaining the functions I'm not sure I've got it right.

Wikipedia diagram of SHA256 Caption for Wikipedia diagram of SHA256

Here's what I have so far:

  • Input is an array 8 items long where each item is 32 bits.
  • Output is an array 8 items long where each item is 32 bits.
  • Calculate all the function boxes and store those values. I'll refer to them by function name.
  • Store input, right shifted by 32 bits, into output.
    • At this point, in the out array, E is the wrong value and A is empty
  • Store the function boxes.
    • now we need to calculate out E and out A.
    • note: I've replaced the modulo commands with a bitwise AND 2^(32-1)

I can't figure out how the modulus adding lines up, but I think it is like this:

  • Store (Input H + Ch + ( (Wt+Kt) AND 2^31 ) ) AND 2^31 As mod1
  • Store (sum1 + mod1) AND 2^31 as mod2
  • Store (d + mod2) AND 2^31 into output E
    • now output E is correct and all we need is output A
  • Store (MA + mod2) AND 2^31 as mod3
  • Store (sum0 + mod3) AND 2^31 into output A
    • output now contains the correct hash of input.
    • Do we return now or does this need to be run repeatedly?

Did I get all of those addition modulos right?

what are Wt and Kt?

Would this get run once, and you're done or does it need to be run a certain number of times, with the output being re-used as input?

Here's the link by the way. http://en.wikipedia.org/wiki/SHA-2#Hash_function

Thanks alot, Brian

pseudocode sha sha256 cryptography
3 Answers

W_t is derived from the current block being processed while K_t is a fixed constant determined by the iteration number. The compression function is repeated 64 times for each block in SHA256. There is a specific constant K_t and a derived value W_t for each iteration 0 <= t <= 63.

I have provided my own implementation of SHA256 using Python 3.6. The tuple K contains the 64 constant values of K_t. The Sha256 function shows how the value of W_t is computed in the list W. The implementation focuses on code clarity and not high-performance.

W = 32          #Number of bits in word
M = 1 << W
FF = M - 1      #0xFFFFFFFF (for performing addition mod 2**32)

#Constants from SHA256 definition
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)

#Initial values for compression function
I = (0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
     0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19)

def RR(x, b):
    '''
    32-bit bitwise rotate right
    '''
    return ((x >> b) | (x << (W - b))) & FF

def Pad(W):
    '''
    Pads a message and converts to byte array
    '''
    mdi = len(W) % 64           
    L = (len(W) << 3).to_bytes(8, 'big')        #Binary of len(W) in bits
    npad = 55 - mdi if mdi < 56 else 119 - mdi  #Pad so 64 | len; add 1 block if needed
    return bytes(W, 'ascii') + b'\x80' + (b'\x00' * npad) + L   #64 | 1 + npad + 8 + len(W)

def Sha256CF(Wt, Kt, A, B, C, D, E, F, G, H):
    '''
    SHA256 Compression Function
    '''
    Ch = (E & F) ^ (~E & G)
    Ma = (A & B) ^ (A & C) ^ (B & C)        #Major
    S0 = RR(A, 2) ^ RR(A, 13) ^ RR(A, 22)   #Sigma_0
    S1 = RR(E, 6) ^ RR(E, 11) ^ RR(E, 25)   #Sigma_1
    T1 = H + S1 + Ch + Wt + Kt
    return (T1 + S0 + Ma) & FF, A, B, C, (D + T1) & FF, E, F, G

def Sha256(M):
    '''
    Performs SHA256 on an input string 
    M: The string to process
    return: A 32 byte array of the binary digest
    '''
    M = Pad(M)          #Pad message so that length is divisible by 64
    DG = list(I)        #Digest as 8 32-bit words (A-H)
    for j in range(0, len(M), 64):  #Iterate over message in chunks of 64
        S = M[j:j + 64]             #Current chunk
        W = [0] * 64
        W[0:16] = [int.from_bytes(S[i:i + 4], 'big') for i in range(0, 64, 4)]  
        for i in range(16, 64):
            s0 = RR(W[i - 15], 7) ^ RR(W[i - 15], 18) ^ (W[i - 15] >> 3)
            s1 = RR(W[i - 2], 17) ^ RR(W[i - 2], 19) ^ (W[i - 2] >> 10)
            W[i] = (W[i - 16] + s0 + W[i-7] + s1) & FF
        A, B, C, D, E, F, G, H = DG #State of the compression function
        for i in range(64):
            A, B, C, D, E, F, G, H = Sha256CF(W[i], K[i], A, B, C, D, E, F, G, H)
        DG = [(X + Y) & FF for X, Y in zip(DG, (A, B, C, D, E, F, G, H))]
    return b''.join(Di.to_bytes(4, 'big') for Di in DG)  #Convert to byte array

if __name__ == "__main__":
    bd = Sha256('Hello World')
    print(''.join('{:02x}'.format(i) for i in bd))
Admin1
Related