SHA-256 hash function explained step by step

Introduction

A hash function is simply a function which takes an input of variable length and gives out an output of a specific length. SHA-256 is one of such function. It transform an input with a maximum size of (2⁶⁴- 1) bits to a 256 bits value called a hash.

Step 1: Preprocessing

Suppose the input message is the word medium. In binary, this translate to

01101101 01100101 01100100 01101001 01110101 01101101

• Append 1 as a single bit at the end

01101101 01100101 01100100 01101001 01110101 01101101 1

• Add zeros to this until the number of bits is a multiple of 512.

01101101 01100101 01100100 01101001 01110101 01101101 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000

• Replace the last 64 bits with the length of the original input as a big-endian integer

01101101 01100101 01100100 01101001 01110101 01101101 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00111000

Step 2:Message schedule

• Restructure the whole thing as an array of 16 words this is called the message schedule

w = [
01101101011001010110010001101001, 01110101011011011000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000111000]

• Run this loop to create the rest of the message schedule

For i from 16 to 63:
  s0 = (w[i-15] rightrotate 7) xor 
       (w[i-15] rightrotate 18) xor   
       (w[i-15] rightshift 3)
  
  s1 = (w[i- 2] rightrotate 17) xor 
       (w[i- 2] rightrotate 19) xor 
       (w[i- 2] rightshift 10)
  
  w[i] = w[i-16] + s0 + w[i-7] + s1

For example, let’s compute for i = 16

s0 = (01110101011011011000000000000000 rightrotate  7) xor 
     (01110101011011011000000000000000 rightrotate 18) xor   
     (01110101011011011000000000000000 rightshift   3)
   
   = 00000000111010101101101100000000 xor
     01100000000000000001110101011011 xor
     00001110101011011011000000000000 
   
   = 01101110010001110111011001011011
s1 = (00000000000000000000000000000000 rightrotate 17) xor 
     (00000000000000000000000000000000 rightrotate 19) xor 
     (00000000000000000000000000000000 rightshift 10)
  
   = 00000000000000000000000000000000 xor
     00000000000000000000000000000000 xor
     00000000000000000000000000000000
   
   = 00000000000000000000000000000000
w[16] = 01101101011001010110010001101001 +  
        01101110010001110111011001011011 + 
        00000000000000000000000000000000 +
        00000000000000000000000000000000
      
      = 11011011101011001101101011000100

• After doing the whole thing, we end up with

w = [ 
01101101011001010110010001101001, 01110101011011011000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 00000000000000000000000000000000, 
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000000000,
00000000000000000000000000000000, 00000000000000000000000000110000, 11011011101011001101101011000100, 01110101100010001000000000000000,
11110110000011000001110110010101, 01010000000111010101011001010101,
10001101010001011100011011000000, 00000001111101000000010101011000,
01011011100110110000011010110011, 01011101101101000101100010001001,
01011001001000011010000001111111, 10011101000011110000011000001111,
00110100100000110110011000110001, 11110000111001110100010110100111,
11100001100001111010000101100000, 10100101111101100100011001110001,
11110010011001100110010110101011, 11101001011101010011000010010001,
10100101001100100001110000011011, 00011011001101101010000100010011,
00101001100100100001001001010101, 10010110110101000010101100001110,
00110000010100101000101110001100, 00110001000001100001011111111010,
10001000011110101011011010010010, 10001010001111101101010011010001,
01101110111010100000011010111111, 00010101011010011111101101111011,
10001110100000000100101101101110, 00011010001110101100011010101001,
10100110111100000011110100011011, 01011001101110011001101011010101,
11001011100000111000110001010011, 00011100101100000110111111010100,
00111101010001010001001110010101, 00110001111111011001101001100000,
10110010011101001000100111001110, 10110110000000001110001001000010,
01110011111110101101101101001000, 01100111100001100111001111100110,
10100101011000110011010101010110, 00101111000001101111011001110101,
11100010101011010100100110110010, 11000111001100111110001110000010,
10111100001010011001111111010111, 11000001000100010010011111011101,
01110101001000101110101011111000, 00000001011100110111000110000000,
10101001111000100100100101100000, 11110000010011000001110011010101]

Step 3:Initialise constants

• Create an array with the 32 bits of the fractional part of the square root of the first 8 primes.

h = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 
     0x9b05688c, 0x1f83d9ab, 0x5be0cd19]

• Create an array with the 32 bits of the fractional part of the cube root of the first 64 primes.

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]

Step 4: Initialise the working variables

• Create 8 (a,b, .., h) variables and assign (h[0], h[1], …, h[7]) to them

a = h[0]
b = h[1]
c = h[2]
d = h[3]
e = h[4]
f = h[5]
g = h[6]
h = h[7]

Step 5:Compression loop

• Run this loop to modify the values of a,b, …, h

for i from 0 to 63
        S1    = (e rightrotate  6) xor 
                (e rightrotate 11) xor 
                (e rightrotate 25)
        ch    = (e and f) xor ((not e) and g)
        
        temp1 = h + S1 + ch + k[i] + w[i]
        
        S0    = (a rightrotate 2) xor 
                (a rightrotate 13) xor 
                (a rightrotate 22)
        maj   = (a and b) xor (a and c) xor (b and c)
        temp2 = S0 + maj
 
        h = g
        g = f
        f = e
        e = d + temp1
        d = c
        c = b
        b = a
        a = temp1 + temp2

For example, let’s compute a, b, …, h when i = 0

S1 = (01010001000011100101001001111111 rightrotate  6) xor 
     (01010001000011100101001001111111 rightrotate 11) xor 
     (01010001000011100101001001111111 rightrotate 25)
   = 11111101010001000011100101001001 xor  
     01001111111010100010000111001010 xor
     10000111001010010011111110101000

   = 00110101100001110010011100101011
ch = (01010001000011100101001001111111 and 
      10011011000001010110100010001100) 
     xor 
     ((not 01010001000011100101001001111111) and 
     00011111100000111101100110101011)
     
   = 00011111100001011100100110001100  
temp1 = 01011011111000001100110100011001 + 
        00110101100001110010011100101011 +
        00011111100001011100100110001100 + 
        01000010100010100010111110011000 + 
        01101101011001010110010001101001
    
      = 01100000110111010101000111010001
S0    = (01101010000010011110011001100111 rightrotate 2) xor 
        (01101010000010011110011001100111 rightrotate 13) xor 
        (01101010000010011110011001100111 rightrotate 22)
      = 11011010100000100111100110011001 xor
        00110011001110110101000001001111 xor
        00100111100110011001110110101000
   
      = 11001110001000001011010001111110
maj   = (01101010000010011110011001100111 and 
         10111011011001111010111010000101) 
        xor 
        (01101010000010011110011001100111 and  
         00111100011011101111001101110010) 
        xor 
        (10111011011001111010111010000101 and 
         00111100011011101111001101110010)
      
      = 00111010011011111110011001100111
temp2 = 11001110001000001011010001111110 + 
        00111010011011111110011001100111
      = 00001000100100001001101011100101
h = 00011111100000111101100110101011
g = 10011011000001010110100010001100
f = 01010001000011100101001001111111
e = 10100101010011111111010100111010 + 
    01100000110111010101000111010001
  
  = 00000110001011010100011100001011
d = 00111100011011101111001101110010
c = 10111011011001111010111010000101
b = 01101010000010011110011001100111
a = 01100000110111010101000111010001 + 
    00001000100100001001101011100101
 
  = 01101001011011011110110010110110

• After computing this 63 more times for i = 1, i = 2, …, i = 63 we get

a = 0x56785f03
b = 0xbbff33b5
c = 0xdc6c14da
d = 0x2dfb7abb
e = 0xbfac9cd1
f = 0xca43500b
g = 0xacfd100c
h = 0x780054af

Step 6:Updating the hash values

• We now update the values of h[0], h[1], …, h[7] by doing this

h[0] = h[0] + a = 0xc082456a
h[1] = h[1] + b = 0x7766e23a
h[2] = h[2] + c = 0x18db084c
h[3] = h[3] + d = 0xd34b6ff5
h[4] = h[4] + e = 0x10baef50
h[5] = h[5] + f = 0x6548b897
h[6] = h[6] + g = 0xcc80e9b7
h[7] = h[7] + h = 0xd3e121c8

Step 7:Chunk loop

• Now since our input (the word medium) is so small we only had one chunk of 512 bits. But suppose we wanted the hash of a bigger message, we would have more than one chunk of 512 bits. In this case we would need to do the step 2,4,5 for every single chunk.

Step 8:Final hash value

• After processing every single chunk of 512 bits (only 1 in our case), we concatenate together h[0], h[1], …, h[7] in this order to get the hash.

hash = h[0] append 
       h[1] append 
       h[2] append 
       h[3] append 
       h[4] append 
       h[5] append 
       h[6] append 
       h[7]
     = c082456a7766e23a18db084cd34b6ff510baef506548b897cc80e9b7d3e121c8

• We’ve now computed the hash of the word medium.