SHA Message Digest

The Secure Hash Algorithm (SHA) is a family of cryptographic hash functions certified by FIPS. It computes a fixed-length string (also known as a message digest) from a given digital message, with a very high probability that different messages will produce different strings.

1. Introduction to SHA

SHA currently has four algorithm versions: SHA-0, SHA-1, SHA-2, and SHA-3. The most widely used today is SHA-2.

Since the various SHA-2 algorithm variants differ only slightly in digest length, number of rounds, and other minor details while sharing the same basic structure, and since there are many detailed explanations of SHA-256 available online, we will use SHA-256 as our working example here.

The original text is based on “Understanding the SHA-256 Algorithm: Principles and Implementation”. For easier understanding, a SHA-256 Algorithm Step-by-Step Visualization is provided; it is recommended to follow along with the visualization as you read.

2. Principle Analysis

2.1. Constant Initialization

The initial hash value $H^{(0)}$ is derived from the fractional parts of the square roots of the first 8 prime numbers $(2,3,5,7,11,13,17,19)$, taking the first 32 bits of each. For example, the fractional part of $\sqrt{2}$ is approximately $0.414213562373095048$, where

$$0.414213562373095048\approx6*16^{-1}+a*16^{-2}+0*16^{-3}+\cdots$$

Thus, the first 32 bits of the fractional part of the square root of prime 2 correspond to 0x6a09e667.

Following the same process, the initial hash value $H^{(0)}$ consists of the following eight 32-bit hash initial values:

$$H_{1}^{(0)}=6a09e667$$ $$H_{2}^{(0)}=bb67ae85$$ $$H_{3}^{(0)}=3c6ef372$$ $$H_{4}^{(0)}=a54ff53a$$ $$H_{5}^{(0)}=510e527f$$ $$H_{6}^{(0)}=9b05688c$$ $$H_{7}^{(0)}=1f83d9ab$$ $$H_{8}^{(0)}=5be0cd19$$

The SHA-256 algorithm also uses 64 round constants, derived from the first 32 bits of the fractional parts of the cube roots of the first 64 prime numbers. Expressed in hexadecimal, the constants are as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

428a2f98 71374491 b5c0fbcf e9b5dba5
3956c25b 59f111f1 923f82a4 ab1c5ed5
d807aa98 12835b01 243185be 550c7dc3
72be5d74 80deb1fe 9bdc06a7 c19bf174
e49b69c1 efbe4786 0fc19dc6 240ca1cc
2de92c6f 4a7484aa 5cb0a9dc 76f988da
983e5152 a831c66d b00327c8 bf597fc7
c6e00bf3 d5a79147 06ca6351 14292967
27b70a85 2e1b2138 4d2c6dfc 53380d13
650a7354 766a0abb 81c2c92e 92722c85
a2bfe8a1 a81a664b c24b8b70 c76c51a3
d192e819 d6990624 f40e3585 106aa070
19a4c116 1e376c08 2748774c 34b0bcb5
391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3
748f82ee 78a5636f 84c87814 8cc70208
90befffa a4506ceb bef9a3f7 c67178f2

2.2. Message Preprocessing

The message is first padded so that its final length is a multiple of 512 bits. It is then divided into 512-bit blocks: $M^{(1)},M^{(2)},\cdots,M^{(N)}$.

Suppose the binary encoding of the message $M$ has a length of $l$ bits. First, a single “$1$” bit is appended to the message, followed by $k$ “$0$” bits, where $k$ is the smallest non-negative integer satisfying:

$$l+1+k=448\ mod\ 512$$

This padding ensures the message length is brought to $448$ bits modulo $512$, because the final 64 bits will be used to encode the original message length $l$ as a 64-bit binary value, bringing the total length to an exact multiple of $512$ bits.

Two important notes here:

• Regardless of the original message length, padding must always be performed—even if the message length already satisfies $l \equiv 448 \pmod{512}$, in which case a full 512-bit block of padding is added.
• Additionally, since the message length $l$ is encoded as a 64-bit binary value, the length must be less than $2^{64}$, which is more than sufficient for virtually all use cases.

After padding, the message is divided into 512-bit blocks: $M^{(1)},M^{(2)},\cdots,M^{(N)}$, where the first 32 bits of the $i$-th block are denoted $M_{0}^{(i)}$, the next 32 bits $M_{1}^{(i)}$, and so on, with the final 32 bits denoted $M_{15}^{(i)}$. We use the $Big\ endian$ (big-endian) convention for data encoding, meaning the first byte is the most significant byte; therefore, for each 32-bit word, the leftmost bit is the most significant bit.

2.3. Main Digest Calculation Loop

For convenience, we define the following operators (all operations are performed on 32-bit binary data):

The following functions are defined: $$Ch(x,y,z)=(x \wedge y) \oplus (\neg x \wedge z)$$ $$M_{aj}(x,y,z)=(x \wedge y) \oplus (x \wedge z) \oplus (y \wedge z)$$ $$\Sigma_{0}(x)=S^{2}(x) \oplus S^{13}(x) \oplus S^{22}(x)$$ $$\Sigma_{1}(x)=S^{6}(x) \oplus S^{11}(x) \oplus S^{25}(x)$$ $$\sigma_{0}(x)=S^{7}(x) \oplus S^{18}(x) \oplus R^{3}(x)$$ $$\sigma_{1}(x)=S^{17}(x) \oplus S^{19}(x) \oplus R^{10}(x)$$

2.3.1. Message Schedule Expansion

Each original message block $M^{(i)}$ is expanded from 512 bits to 2048 bits for computation, where every 32 bits form one word $W_{j}$.

The expanded message words $W_{0},W_{1},\cdots,W_{63}$ are computed as follows:

• $for\ j = 0 \rightarrow 15$ $$W_{j}=M_{j}^{(i)}$$

• $for\ j = 16 \rightarrow 63$ $$W_{j}=W_{j-16}+\sigma_{0}(W_{j-15})+W_{j-7}+\sigma_{1}(W_{j-2})$$

Once all words are computed, we proceed to the next step.

2.3.2. Intermediate Hash Value Calculation

The constant initialization section provided the initial hash value $H^{(0)}$ and the 64 constants $K_{0},K_{1},\cdots,K_{63}$, which are used in this section. We also introduce $a,b,c,d,e,f,g,h$ as working variables.

• $for\ i = 1 \rightarrow N$（where $N$ is the number of padded message blocks） $$a=H_{1}^{(i-1)}$$ $$b=H_{2}^{(i-1)}$$ $$\vdots$$ $$h=H_{8}^{(i-1)}$$

  That is, for the first block (when $i=1$), the working variables $a,b,c,d,e,f,g,h$ are initialized with $H^{(0)}$. For each subsequent block, they are initialized with the intermediate hash values $H^{(i-1)}$.

  • $for\ j = 0 \rightarrow 63$

    First, compute $T_{1}$ and $T_{2}$: $$T_{1}=h+\Sigma_{1}(e)+Ch(e,f,g)+K_{j}+W_{j}$$ $$T_{2}=\Sigma_{0}(a)+M_{aj}(a,b,c)$$

    For each expanded message word $W_{j}$ in $W_{0},W_{1},\cdots,W_{63}$, perform the following operations: $$h=g$$ $$g=f$$ $$f=e$$ $$e=d+T_{1}$$ $$d=c$$ $$c=b$$ $$b=a$$ $$a=T_{1}+T_{2}$$

    Once all iterations are complete, the final values of $a,b,c,d,e,f,g,h$ for this block are used to compute: $$H_{1}^{(i)}=a+H_{1}^{(i-1)}$$ $$H_{2}^{(i)}=b+H_{2}^{(i-1)}$$ $$\vdots$$ $$H_{8}^{(i)}=h+H_{8}^{(i-1)}$$

    $H_{1}^{(i)},H_{2}^{(i)},\cdots,H_{8}^{(i)}$ are the intermediate hash values for this block, which also serve as the initial values of $a,b,c,d,e,f,g,h$ for the next block.

2.4. Obtaining the Hash Result

After processing every 512-bit padded message block, we obtain $H_{1}^{(N)},H_{2}^{(N)},\cdots,H_{8}^{(N)}$. These are expressed in hexadecimal and concatenated together, with $H_{1}^{(N)}$ as the most significant part, followed by $H_{2}^{(N)},H_{3}^{(N)},\cdots,H_{8}^{(N)}$ in order, and $H_{8}^{(N)}$ as the least significant part. The resulting hexadecimal string is the final output, expressed in big-endian order.

2.5. Summary

The SHA-256 algorithm can be summarized as follows:

• The message is padded so that its final length is a multiple of 512 bits, then divided into 512-bit blocks.
• Starting from a fixed initial hash $H^{(0)}$, each message block is processed sequentially with the following computation: $$H^{(i)}=H^{(i-1)}+C_{M^{(i)}}(H^{(i-1)})$$ where $C$ is the SHA-256 compression function, $+$ denotes addition modulo $2^{32}$ (i.e., adding two numbers and taking the result modulo $2^{32}$), and $H^{(N)}$ is the final hash value of the message.

References

• SHA Family
• Understanding the SHA-256 Algorithm: Principles and Implementation
• SHA-256 Algorithm Step-by-Step Visualization