Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

What are the different steps in SHA-256?

Imama Zahoor

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

The SHA-256 algorithm is a part of the SHA-2Secure Hashing Algorithm 2, a set of secure cryptographic hash functions used for the protection and encryption of online data.

We can divide the algorithm for SHA-256 into three steps, as outlined below.

Step one: Appending bits

The first step involves preprocessing the input message to make it compatible with the hash function. It can be divided into two main substeps:

Padding bits

The total length of our message must be a multiple of 512512. In this step, we append bits to the end of our message such that the final length of the message must be 64 bits less than a multiple of 512. The formula below depicts this step:

        m+p=(n512)64 m+p=(n*512)-64

where mm = length of the message, pp = length of the padding, and nn = a constant.

The first bit that we append is 11 followed by all 00 bits.

Length bits

Next, we take the modulus of the original message with 232 to get 6464 bits of data. Appending this to the padded message makes our processed message an exact multiple of 512512.

The image below illustrates the final message after step one is completed.

The original message after preprocessing

Step two: Buffer initialization

Before we begin carrying out computations on the message, we need to initialize some buffer values. The default eight buffer values are shown below. These are hard-coded constants representing hash values.

A = 0x6a09e667
B = 0xbb67ae85
C = 0x3c6ef372
D = 0xa54ff53a
E = 0x510e527f
F = 0x9b05688c
G = 0x1f83d9ab
H = 0x5be0cd19

Moreover, we have to initialize an array containing 6464 constants, denoted by kk.

k[0..63] = 
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 three: Compression function

Now that we have our message and buffers ready, we can begin computation. Recall that our processed message is n512n*512 bits long. This will be divided into nn chunks of 512512 bits. Each of these chunks is then put through 6464 rounds of operations and the output from each round serves as the next input.

The image below illustrates the complete cycle:

The 64 rounds of operation performed on a message chunk

Moreover, each input consists of two constants—K(i)K(i) and W(i)W(i). K(i)K(i) is pre-initialized and W(i)W(i) is initialized by breaking each of the 512512 bit chunks into 1616 subblocks of 3232 bits each for the first 16 rounds. After that, W(i)W(i) must be calculated at each subsequent round. The following formulas show the calculation:

  1. s0=(W[i15] s^0=(W[i-15] right rotate 7) 7) XOR (W[i15] (W[i-15] right rotate 18) 18) XOR (W[i15] (W[i-15] right shift 3) 3)
  2. s1=(W[i2] s^1=(W[i-2] right rotate 17) 17) XOR (W[i2] (W[i-2] right rotate 19) 19) XOR (W[i2] (W[i-2] right shift 10) 10)
  3. W(i)=W[i16]+s+W[97]+s¹ W(i) = W[i-16] + s⁰ + W[9-7] + s¹

Now that we know how a message chunk is processed, let us take a look at each round. Consider the diagram below:

Each round of operation

Each round carries out the following set of computations:

  • Ch=(E Ch = (E AND F) F)XOR (( ((NOT E)E) AND G)G)
  • Ma=(A Ma = (A AND B) B)XOR (A (AAND C)C) XOR (B(B AND C)C)
  • A=(A>>>2) ∑A = (A>>>2)XOR (A>>>13) (A >>> 13)XOR (A>>>22) (A >>> 22)
  • E=(E>>>6) ∑E = (E>>>6)XOR (E>>>11) (E >>> 11)XOR (E>>>25) (E >>> 25)
  • Am= Am= (addition) mod (232 )

The output from each round is fed as input to the next round until the last chunk is reached. The output from the last block will be the final hash digest of length 256256 bits.

RELATED TAGS

CONTRIBUTOR

Imama Zahoor
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring