Recently, I was learning some knowledge about algorithm encryption and decryption. I didn't have a special understanding of SHA256 algorithm before. I saw the detailed explanation and implementation process of SHA256 algorithm by many other leaders, and finally understood it a little. Thank you very much for integrating these materials here. The purpose of writing this learning note is to record the process of learning SHA256 algorithm for next time. Of course, it would be great if we could provide some ideas and inspiration to our partners in need.
1. Overview of Sha algorithm
SHA (Secure Hash Algorithm) is a family of cryptographic hash functions. It is FIPS (Federal Information Processing Standards)
The authenticated secure hash algorithm. An algorithm that can calculate a fixed length string (also known as message digest) corresponding to a digital message.
An n-bit hash function is a mapping from an arbitrarily long message to an n-bit hash value. An n-bit encrypted hash function is a one-way, collision free n-bit hash function. Such a function is a very important means in digital signature and password protection.
At present, the popular hash functions mainly include 128 bit MD4 and MD5 and 160 bit (20 byte) SHA-1. The SHA-2 family introduced today has more output hash values, which is more difficult to crack and can improve higher security.
SHA-2, whose name comes from the abbreviation of Secure Hash Algorithm 2 (English: Secure Hash Algorithm 2), is a cryptographic hash function algorithm standard developed by the national security administration and released by the National Institute of standards and Technology (NIST) in 2001. It is one of the Sha algorithms and the successor of SHA-1. It can be further divided into six different algorithm standards, including SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 and SHA-512/256.
In addition to some minor differences in the length of the generated summary and the number of cycles, the basic structure of the algorithm is the same.
2. Introduction to sha256 algorithm
When it comes to SHA256, it literally means that for messages of any length, SHA256 will generate a 256 bit hash value called message digest. This summary is equivalent to an array with a length of 32 bytes, a total of 256 bits. It is usually represented by a hexadecimal string with a length of 64, in which 1 byte = 8 bits and a hexadecimal character is 4 bits long.
SHA256 hashes the message, as shown in the following example:
1122334455667788 //news
The message summary obtained by the hash function SHA256 is:
1DCE6604591EFB439D5E87418A1D00DBFD014327D8C4DEA862815714B76AE9A5 //Hash value
Here, the original 8-byte message "1122334455667788" is calculated by SHA256 algorithm to obtain a 32-byte message summary, and small changes are made to the message, and the generated Hash will change greatly, which is completely different from the original value, as follows:
0122334455667788 //news 2B85738907AB2C4C39DFFFDD5328A694F4DF04B75E6F482F832279C6BBFE8530 //Hash value
Only by changing the value of one bit, the Hash value has changed greatly.
3. Detailed description of sha256 algorithm principle
In order to better understand the principle of SHA256, we first introduce the modules that can be extracted separately from the algorithm, including constant initialization, information preprocessing and used logic operation. After getting rid of these obstacles in understanding, let's explore the main part of SHA256 algorithm, that is, how to calculate the message summary.
3.1 constant initialization
SHA256 algorithm uses 8 initial hash values and 64 hash constants. 64 hash constants participate in the subsequent hash value calculation.
The 8 initial hash values of SHA256 algorithm are:
H1 := 0x6a09e667 H2 := 0xbb67ae85 H3 := 0x3c6ef372 H4 := 0xa54ff53a H5 := 0x510e527f H6 := 0x9b05688c H7 := 0x1f83d9ab H8 := 0x5be0cd19
The initial hash value H(1-8) is taken from the decimal part of the square root of the first 8 prime numbers (2,3,5,7,11,13,17,19) in the natural number, and takes the first 32 bits As an example, the decimal part of [Formula] is about 0.414213562373095048, where
Therefore, the first 32 bits of the decimal part of the square root of prime 2 correspond to 0x6a09e667. And so on, you can get 8 initial hash values.
The 64 hash constants of SHA256 algorithm are:
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
Similar to the 8 initial hash values, the 64 hash constants are obtained from the decimal part of the cube root of the first 64 prime numbers (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97...) in the natural number, and the first 32 bits are taken.
3.2 information preprocessing
The preprocessing in SHA256 algorithm is to supplement the required information after the message that wants to Hash, so that the whole message meets the specified structure.
The preprocessing of information is divided into two steps: additional padding bits and additional length
STEP1: additional padding bits
Fill in the end of the message so that the remainder of the message length after taking the modulus of 512 is 448
The filling is carried out in this way: first fill the first bit as 1, and then fill 0 until the length meets the modulo of 512, and the remainder is 448.
It should be noted that the information must be filled, that is, even if the length has met the requirement that the remainder after 512 modulo is 448, the bit filling must also be carried out. At this time, 512 bits must be filled.
Therefore, filling is to fill in at least one digit and up to 512 digits.
**Example: * * take the information "abc" as an example to display the filling process.
a. The ASCII codes corresponding to B and C are 97, 98 and 99 respectively
The original binary code of 100000111 is 10000111
The first step is to fill in a "1": 011000101100010 01100011 1
The second step is to fill in 423 "0": 0110001 01100010 01100011 10000000 0000000... 0000000
The data after filling is as follows (expressed in hexadecimal):
61626380 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
Why 448?
Because after the preprocessing in the first step, a 64bit data will be added in the second step to represent the length information of the original message. And 448 + 64 = 512, just put together a complete structure.
STEP2: additional length value
The additional length value is to add the length information of the original data (the message before the first filling step) to the message that has been filled.
SHA256 uses a 64 bit data to represent the length of the original message.
Therefore, the message length calculated by SHA256 must be less than $2 ^ 64 $, which is large enough in most cases.
The encoding method of length information is 64 bit big endian integer
The meaning of Big endian is supplemented at the end of the paper
Back to the example just now, the message "abc" has three characters and occupies 24 bit s
Therefore, after the complement length operation is performed, the whole message becomes as follows (hexadecimal format)
61626380 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000018
3.3 logic operation
The operations involved in SHA256 hash function are all logical bit operations
It includes the following logic functions:
Here are some operations:
Logical operation | meaning |
---|---|
∧ | Bitwise "and" |
¬ | Bitwise "and" |
⊕ | Bitwise XOR |
Sn | Rotate n bit s to the right |
Rn | Shift n bit s right |
3.4 logic operation
Now let's introduce the main part of SHA256 algorithm, that is, how to calculate the message digest.
First: decompose the message into 512 bit blocks
Assuming that the message M can be decomposed into n blocks, what the whole algorithm needs to do is to complete n iterations, and the result of N iterations is the final hash value, that is, the digital summary of 256bit.
The initial value H0 of a 256 bit summary is calculated by the first data block to obtain H1, that is, the first iteration is completed
H1 passes through the second data block to obtain H2,..., which is processed in turn to obtain Hn, which is the final 256 bit message summary
Use $map (H {I-1}) = h for the mapping of each iteration_ {i} $indicates that the iteration can be more vividly displayed as:
The 256 bit Hi in the figure is described as eight small blocks, because the smallest operation unit in SHA256 algorithm is called "Word", and one Word is 32 bits.
In addition, in the first iteration, the initial value of the mapping is set to the 8 hash initial values described above, as shown in the following figure:
Let's start with the content of each iteration, that is, mapping $map (H {I-1}) = H_ {i} Specific algorithm of $
STEP1: construct 64 word s
break chunk into sixteen 32-bit big-endian words w[0], ..., w[15]
For each block, the block is decomposed into 16 32-bit big endian words, which are recorded as w[0],..., w[15]
That is, the first 16 words are directly decomposed by the ith block of the message
The remaining words are obtained by the following iterative formula:
STEP2: perform 64 cycles
Map $map (H #u{i-1}) = h_ {i} $contains 64 encryption cycles
That is, 64 encryption cycles can complete one iteration
Each encryption cycle can be described by the following figure:
It can be seen from the above figure that the eight word s ABCDEFGH are being updated according to certain rules. The rules are as follows:
If the original data block is ABCDEFGH, one cycle is:
A'=H+Σ1(E)+Ch(E,F,G)+M(t)+K(t)+Ma(A,B,C)+Σ0(A) B'=A C'=B D'=C E'=D+H+Σ1(E)+Ch(E,F,G)+M(t)+K(t) F'=E G'=F H'=G
The dark blue box is a pre-defined nonlinear logic function, which has been paved above
The red field square represents mod $2 ^ {32} $addition, that is, add the two numbers together. If the result is greater than $2 ^ {32}, you must divide by 2 ^ {32} $and find the remainder. Of course, if we define the data as 32 bits, that is, four bytes, we don't have to deliberately take the remainder. The previous loop represents A '- H'.
The initial values of ABCDEFGH are $h at the beginning_ {i-1}(0),H_ {i-1}(1),…,H_{i-1}(7) $.
Kt is the t-th key, corresponding to the 64 constants mentioned above.
Wt is the t-th word generated in this block. The original message is cut into 512 bit blocks with a fixed length. For each block, 64 words are generated. The eight words ABCDEFGH are cyclically encrypted by repeating the cycle n times.
The eight words generated in the last loop together are the hash string $h corresponding to the ith block_ {i} $.
4.SHA256 algorithm implementation
4.1 logic function
typedef unsigned char BYTE; // 8 bits typedef unsigned int WORD; // 32-bit data, 4 bytes represent a word typedef struct { BYTE data[64]; // current 512-bit chunk of message data, just like a buffer WORD datalen; // sign the data length of current chunk unsigned long long bitlen; // the bit length of the total message WORD state[8]; // store the middle state of hash abstract } SHA256_CTX; //The logic functions are as follows /* ∧: Bitwise "and" !: Bitwise "complement" ⊕: Bitwise XOR Sn: Rotate n bit s to the right Rn: Shift n bit s right */ #define ROTRIGHT(a,b) (((a) >> (b)) | ((a) << (32-(b)))) // rotate right #define MAJ(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z))) //Ma(x,y,z)=(x∧y)⊕(x∧z)⊕(y∧z) #define EP0(x) (ROTRIGHT(x,2) ^ ROTRIGHT(x,13) ^ ROTRIGHT(x,22)) //Σ0(x)=S2(x)⊕S13(x)⊕S22(x) #define EP1(x) (ROTRIGHT(x,6) ^ ROTRIGHT(x,11) ^ ROTRIGHT(x,25)) //Σ1(x)=S6(x)⊕S11(x)⊕S25(x) #define SIG0(x) (ROTRIGHT(x,7) ^ ROTRIGHT(x,18) ^ ((x) >> 3)) //σ0(x)=S7(x)⊕S18(x)⊕R3(x) #define SIG1(x) (ROTRIGHT(x,17) ^ ROTRIGHT(x,19) ^ ((x) >> 10)) //σ1(x)=S17(x)⊕S19(x)⊕R10(x)
4.2 Hash value obtained by data block processing
//Operate a data block with a length of 512bit and convert it into Hash value void sha256_transform(SHA256_CTX *ctx, const BYTE data[]) { //Abcdefgh represents eight words of abcdefgh, and t1t2 stores the intermediate operation value WORD a, b, c, d, e, f, g, h, i, j, t1, t2, m[64];//m here represents 64 words (32 bits per word) // initialization for (i = 0, j = 0; i < 16; ++i, j += 4) m[i] = (data[j] << 24) | (data[j + 1] << 16) | (data[j + 2] << 8) | (data[j + 3]);//Divide the data block into 16 32bit words and store them in the first 16 words of m for ( ; i < 64; ++i) m[i] = SIG1(m[i - 2]) + m[i - 7] + SIG0(m[i - 15]) + m[i - 16];//Other words: 16-63, according to the formula Mt= σ 1(M(t-2))+M(t-7)+ σ 0(M(t-15))+M(t-16) calculation //In the first iteration, the initial mapping value is set to 8 hash initial values a = ctx->state[0]; b = ctx->state[1]; c = ctx->state[2]; d = ctx->state[3]; e = ctx->state[4]; f = ctx->state[5]; g = ctx->state[6]; h = ctx->state[7]; /* If the original data block is ABCDEFGH, one cycle is: A'=H+Σ1(E)+Ch(E,F,G)+M(t)+K(t)+Ma(A,B,C)+Σ0(A) B'=A C'=B D'=C E'=D+H+Σ1(E)+Ch(E,F,G)+M(t)+K(t) F'=E G'=F H'=G */ //64 encryption cycles for (i = 0; i < 64; ++i) { //There is no need to remove the remainder of 2 ^ 32, because the length of a-t2 is 32bit, and if it exceeds 2 ^ 32, the excess will be discarded t1 = h + EP1(e) + CH(e,f,g) + k[i] + m[i];//An operation required by SHA256 t2 = EP0(a) + MAJ(a,b,c); h = g; g = f; f = e; e = d + t1; d = c; c = b; b = a; a = t1 + t2; } //Integrate hash ctx->state[0] += a; ctx->state[1] += b; ctx->state[2] += c; ctx->state[3] += d; ctx->state[4] += e; ctx->state[5] += f; ctx->state[6] += g; ctx->state[7] += h; }
void sha256_final(SHA256_CTX *ctx, BYTE hash[]) { WORD i; i = ctx->datalen; // Pad whatever data is left in the buffer. if (ctx->datalen < 56) { ctx->data[i++] = 0x80; // pad 10000000 = 0x80 while (i < 56) ctx->data[i++] = 0x00; } else { ctx->data[i++] = 0x80; while (i < 64) ctx->data[i++] = 0x00; sha256_transform(ctx, ctx->data); memset(ctx->data, 0, 56); } //Append the total length of the message (in bits) to the padding and convert it //56-638 bytes represent the bit length and are stored according to the big end mode (low address put high) ctx->bitlen += ctx->datalen * 8; ctx->data[63] = ctx->bitlen; ctx->data[62] = ctx->bitlen >> 8; ctx->data[61] = ctx->bitlen >> 16; ctx->data[60] = ctx->bitlen >> 24; ctx->data[59] = ctx->bitlen >> 32; ctx->data[58] = ctx->bitlen >> 40; ctx->data[57] = ctx->bitlen >> 48; ctx->data[56] = ctx->bitlen >> 56; sha256_transform(ctx, ctx->data); // copying the final state to the output hash(use big endian). //hash[i] type is Byte, STX - > state [i] type is WORD(4 bytes) for (i = 0; i < 4; ++i) { //Take the upper left 8 bits, press the big end mode, hash[0] is the low address, take the high bit, and so on hash[i] = (ctx->state[0] >> (24 - i * 8)) & 0x000000FF; hash[i + 4] = (ctx->state[1] >> (24 - i * 8)) & 0x000000FF; hash[i + 8] = (ctx->state[2] >> (24 - i * 8)) & 0x000000FF; hash[i + 12] = (ctx->state[3] >> (24 - i * 8)) & 0x000000FF; hash[i + 16] = (ctx->state[4] >> (24 - i * 8)) & 0x000000FF; hash[i + 20] = (ctx->state[5] >> (24 - i * 8)) & 0x000000FF; hash[i + 24] = (ctx->state[6] >> (24 - i * 8)) & 0x000000FF; hash[i + 28] = (ctx->state[7] >> (24 - i * 8)) & 0x000000FF; } }
5. Reference
The main reference materials of this study note are as follows:
Detailed explanation of SHA256 algorithm principle
C language SHA256 encryption algorithm based on STM32
Understand the principle and implementation of SHA256 algorithm