---
# System prepended metadata

title: SHA-256 Algorithm

---

# SHA-256 Algorithm

First of all, I'd like to share this nice book: https://webspace.science.uu.nl/~tel00101/liter/Books/CrypCont.pdf

## A - Preprocess steps
1 - Padding the message
2 - Parsing the message into message blocks
3 - Setting the initial hash value


### Step 1: Padding the message

- This padding is to ensure that the padded msg is a multiple of 512. 
- Append the bit '1' to the end of the message followed by k zero bits
- And then, append 64-bits block to represent the message size

Suppose M contains l bits and k is the smallest positive integer to the equation

$l + 1 + k ≡ 448 mod 512$

example: abc = 8*3=24 bits, so l = 24 
We need to find how many zero's

```
a = 01100001 
b = 01100010
c = 01100011
```

Following this `l + 1 + k = 448mod512`
We have `512 - 448 = 64`

Then we append 64-bits block to express the number l, that in this example is l=24= 00...011000 

So, we have:
**abc  1	00..00	00...011000**

k = 448 zero bits 00..00 
where the last 5 bits in the sequence is 24 that represents l

Now, the lenght of the padded message has to be a multiple of 512 bits

### Step 2: Parsing the message into message blocks

The message and its padding must be parsed into N 512-bit blocks. Since the 512 bits of the input block may be expressed as 16 32-bit words, the first 32 bits of message block i are denoted M0_i, the next 32 bits are M1_i ... M15_i.

In other words, each 512 bit block is broken into 16 sub blocks of 32 bit each.

In the example abc, N = 1 and then we have only one 512-bit block. 

```1c=
M0 = a b c 1 0000000
M1 = 0000000000..00
.
.
.
M15 = 000.. 011000 (where the final here is l that is 24)
```

### Step 3: Setting the initial hash value

Before hash computation starts, the initial hash value must be set. 

The initial hash value consists of 8 32-bit words:

```gcode
H0 = 6a09e667
H1 = bb67ae85
H2 = 3c6ef372
H3 = a54ff53a
H4 = 512e527f
H5 = 9b05688c
H6 = 1f83d9ab
H7 = 5be0cd19
```
These words are results of the first 32-bits of the fractional parts of the square roots of the first eight prime numbers. 

 
## B- Hash Computation

Uses functions and constants. 
#### B.1 - Constants:
Its a sequence of the 64 constant 32-bit words. These words represent the first 32-bits of the fractional parts of the cube roots of the first 64 prime numbers.

Each message block, M0 ... M15 is processed in order using the following steps:

In the example abc, N = 1.

#### B.2 - Algorithm to compute 64 32-bits words W:

```c=
for i = 1 to N
Prepare the message schedule (Wt). Let's construct the 64 blocks Wi from M(t)
  While 0 <= t <= 63
    if t <= 15 Wt = Mt
    else
      Wt = D1(Wt-2) + Wt-7 + D0(Wt-15) + Wt-16
  
  setWorkingVariables(i)
  compression()
  computeNewValueOfH(i)
  
// How compute D0 and D1: 
D0 (x) = RotationR7(x)  XOR RotationR18(x) XOR ShiftR3(x)
D1 (x) = RotationR17(x) XOR RotationR19(x) XOR ShiftR10(x)
```
#### Remember: x = 32 bit-word

Rotation examples to apply on D0 and D1:
```1c
X = 11000111000111000110010011000001
```

#### Understanding how D0 works:

```1c 
D0 (x) = RotationR7(x)  XOR RotationR18(x) XOR ShiftR3(x)
```

```1c!  
RotationR7(x) 
take the 7h bit and shift to the right in a circular way (similar behavior of circular list)
``` 

The result for X is:
```1c
RotationR7(x) = 10000011100011100011100011001001
```

Similarly, we apply to the remaining rotation operations. 

```1c! 
ShiftR3(x) is quite simple, just shift without applying circular concept.

ShiftR3(x) = 00011000111000111000110010011000
```
#### XOR Operations

After applying shift and rotation operations, we now, apply XOR operations. 



```1c
x = 11000111000111000110010011000001

D0 (x) = RotationR7(x) XOR RotationR18(x) XOR ShiftR3(x)

D0 (x) = 10000011100011100011100011001001
         XOR
         00011001001100000111000111000111
         XOR
         00011000111000111000110010011000
D0 (x) = 10000010010111011100010110010110
```

We do the same thing for **D1**. And then we compute W16, W17, W18, ... W63.

#### Variable Initialization

Here, we use those hash values set in **Step 3** during the preprocessing phase to set eight working variables. The function `setWorkingVariables(i)` is called in the algorithm presented in the `pseudocode (line 8)`.

```c=
setWorkingVariables(i)
    a = H0^(i-1)
    b = H1^(i-1)
    c = H2^(i-1)
    d = H3^(i-1)
    e = H4^(i-1)
    f = H5^(i-1)
    g = H6^(i-1)
    h = H7^(i-1)
```
In our example, we know that $N=1$. So, `setWorkingVariables(i)` function runs just once and we have the following values:

```gcode
a = H0 = 6a09e667
b = H1 = bb67ae85
c = H2 = 3c6ef372
d = H3 = a54ff53a
e = H4 = 512e527f
f = H5 = 9b05688c
g = H6 = 1f83d9ab
h = H7 = 5be0cd19
```

#### Compression 

The `compression()` function bellow is called in the `pseudocode (line 9)`. 

```c=
compression()
  for i=0 to 63
    S1 = (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
    ch = (e and f) xor ((not e) and g)
    T1 = 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)
    T2 := S0 + maj
    h = g
    g = f
    f = e
    e = d + T1
    d = c
    c = b
    b = a
    a = T1 + T2
    
```

#### Compute the new value of H_j

```c=
computeNewValueOfH(i)
    //In our example, i=N=1, so this code is runned once
    h0 = h0 + a 
    h1 = h1 + b 
    h2 = h2 + c 
    h3 = h3 + d 
    h4 = h4 + e 
    h5 = h5 + f 
    h6 = h6 + g 
    h7 = h7 + h 
```




Link shared by Shebin to run some tests: https://sha256algorithm.com/

Link shared by Kris with a step-by-step: https://blog.boot.dev/cryptography/how-sha-2-works-step-by-step-sha-256/