# 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/
Sign in with Wallet
Connect another wallet