SHA256算法原理介绍以及实现

大家好，我是讯享网，很高兴认识大家。

最近在学习一些算法加解密方面的知识，之前对SHA256算法不是特别理解，看了许多其他大佬关于SHA256算法的详解和实现过程，终于是稍微理解了一些，真的非常感谢，这里整合了这些材料，写这篇学习笔记的目的是把自己学习SHA256算法的过程记录下来，方便下次查看。当然，如果能给有需要的小伙伴提供一些思路启发自然再好不过。

1.SHA算法概述

一个n位的哈希函数就是一个从任意长的消息到n位哈希值的映射，一个n位的加密哈希函数就是一个单向的、避免碰撞的n位哈希函数。这样的函数是目前在数字签名和密码保护当中极为重要的手段。

当前比较流行的哈希函数主要有128位的MD4和MD5和160位（20字节）的SHA-1，今天介绍的SHA-2族有着更多位的输出哈希值，激活成功教程难度更大，能够提高更高的安全性。

2.SHA256算法简介

说到SHA256，其字面意思便是，对于任意长度的消息，SHA256都会产生一个256位的哈希值，称作消息摘要。这个摘要相当于是个长度为32个字节的数组，共256位，通常由一个长度为64的十六进制字符串来表示，其中1个字节=8位，一个十六进制的字符的长度为4位。

SHA256对消息做Hash摘要，如下实例：

67788 //消息

讯享网

该消息经过哈希函数SHA256得到的消息摘要为：

讯享网1DCEEFB439D5E87418A1D00DBFD014327D8C4DEAB76AE9A5 //Hash值

这里原来的8字节消息“67788”经SHA256算法运算后得到一个32字节的消息摘要，且对消息做细小的改变，生成的Hash都会发生巨大改变，跟原先的值完全不同，如下：

07788 //消息 2BAB2C4C39DFFFDD5328A694F4DF04B75E6F482FC6BBFE8530 //Hash值

仅仅变换了一位的值，Hash值发生了巨大的改变。

3.SHA256算法原理细述

为了更好的理解SHA256的原理，这里首先将算法中可以单独抽出的模块，包括常量的初始化、信息预处理、使用到的逻辑运算分别进行介绍，甩开这些理解上的障碍后，一起来探索SHA256算法的主体部分，即消息摘要是如何计算的。

3.1常量初始化

讯享网H1 := 0x6a09e667 H2 := 0xbb67ae85 H3 := 0x3c6ef372 H4 := 0xa54ff53a H5 := 0x510e527f H6 := 0x9b05688c H7 := 0x1f83d9ab H8 := 0x5be0cd19

初始哈希值H(1-8)取自自然数中前面8个质数(2,3,5,7,11,13,17,19)的平方根的小数部分, 并且取前面的32位. 下面举个例子: [公式]小数部分约为0., 而其中
在这里插入图片描述
讯享网
于是, 质数2的平方根的小数部分取前32位就对应0x6a09e667。以此类推可得8个初始哈希值。

SHA256算法的64个哈希常量为：

0x428a2f98,0x,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5, 0xd807aa98,0x12835b01,0xbe,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174, 0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da, 0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x, 0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85, 0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd,0xf40e3585,0x106aa070, 0x19a4c116,0x1e376c08,0xc,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3, 0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2

与8个初始哈希值获取的方式类似，64个哈希常量取自自然数中前面64个质数(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…)的立方根的小数部分, 并且取前面的32位。

3.2信息预处理

SHA256算法中的预处理就是在想要Hash的消息后面补充需要的信息，使整个消息满足指定的结构。

信息的预处理分为两个步骤：附加填充比特和附加长度

STEP1：附加填充比特

在报文末尾进行填充，使报文长度在对512取模以后的余数是448

填充是这样进行的：先补第一个比特为1，然后都补0，直到长度满足对512取模后余数是448。

需要注意的是，信息必须进行填充，也就是说，即使长度已经满足对512取模后余数是448，补位也必须要进行，这时要填充512个比特。

因此，填充是至少补一位，最多补512位。

于是原始信息的二进制编码为：0 0 0

补位第一步，首先补一个“1” ： 00010 0 1

补位第二步,补423个“0”：0 0 0 00000000 … 00000000

补位完成后的数据如下（使用16进制表示）：

讯享网 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

为什么是448?

因为在第一步的预处理后，第二步会再附加上一个64bit的数据，用来表示原始报文的长度信息。而448+64=512，正好拼成了一个完整的结构。

STEP2：附加长度值

附加长度值就是将原始数据（第一步填充前的消息）的长度信息补到已经进行了填充操作的消息后面。

SHA256用一个64位的数据来表示原始消息的长度。

因此，通过SHA256计算的消息长度必须要小于$ 2^64 $，当然绝大多数情况这足够大了。

长度信息的编码方式为64-bit big-endian integer

关于Big endian的含义，文末给出了补充

回到刚刚的例子，消息“abc”，3个字符，占用24个bit

因此，在进行了补长度的操作以后，整个消息就变成下面这样了（16进制格式）

 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000018

3.3逻辑运算

SHA256散列函数中涉及的操作全部是逻辑的位运算

包括如下的逻辑函数：

逻辑函数

这里的一些运算：

逻辑运算	含义
∧	按位“与”
¬	按位“与”
⊕	按位“异或”
Sn	循环右移n个bit
Rn	右移n个bit

3.4逻辑运算

现在来介绍SHA256算法的主体部分，即消息摘要是如何计算的。

首先：将消息分解成512-bit大小的块
分解消息
假设消息M可以被分解为n个块，于是整个算法需要做的就是完成n次迭代，n次迭代的结果就是最终的哈希值，即256bit的数字摘要。

一个256-bit的摘要的初始值H0，经过第一个数据块进行运算，得到H1，即完成了第一次迭代

H1经过第二个数据块得到H2，……，依次处理，最后得到Hn，Hn即为最终的256-bit消息摘要

将每次迭代进行的映射用$ Map(H_{i-1}) = H_{i} $表示，于是迭代可以更形象的展示为：
迭代过程
图中256-bit的Hi被描述8个小块，这是因为SHA256算法中的最小运算单元称为“字”（Word），一个字是32位。

此外，第一次迭代中，映射的初值设置为前面介绍的8个哈希初值，如下图所示：
映射初值
下面开始介绍每一次迭代的内容，即映射$ Map(H_{i-1}) = H_{i} $的具体算法

STEP1：构造64个字（word）

break chunk into sixteen 32-bit big-endian words w[0], …, w[15]

对于每一块，将块分解为16个32-bit的big-endian的字，记为w[0], …, w[15]

也就是说，前16个字直接由消息的第i个块分解得到

其余的字由如下迭代公式得到：
公式2
STEP2：进行64次循环

映射 $ Map(H_{i-1}) = H_{i} $ 包含了64次加密循环

即进行64次加密循环即可完成一次迭代

每次加密循环可以由下图描述：
加密循环单次循环
由上图可知，ABCDEFGH这8个字（word）在按照一定的规则进行更新，规则如下：

原数据块为ABCDEFGH，则一次循环为：

讯享网 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

ABCDEFGH一开始的初始值分别为$ H_{i-1}(0),H_{i-1}(1),…,H_{i-1}(7) $。

Kt是第t个密钥，对应我们上文提到的64个常量。

Wt是本区块产生第t个word。原消息被切成固定长度512-bit的区块，对每一个区块，产生64个word，通过重复运行循环n次对ABCDEFGH这八个字循环加密。

最后一次循环所产生的八个字合起来即是第i个块对应到的散列字符串$ H_{i} $。

4.SHA256算法实现

4.1逻辑函数

typedef unsigned char BYTE; // 8位 typedef unsigned int WORD; // 32位数据，4字节表示一个字 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; //逻辑函数如下 /* ∧：按位“与” !：按位“补” ⊕：按位“异或” Sn：循环右移n个bit Rn：右移n个bit */ #define ROTRIGHT(a,b) (((a) >> (b)) | ((a) << (32-(b)))) //循环右移 #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值

讯享网//对一个长度为512bit的数据块进行操作，将其转换成Hash值 void sha256_transform(SHA256_CTX *ctx, const BYTE data[]) { 
    //abcdefgh代表ABCDEFGH八个字，t1t2存放中间运算值 WORD a, b, c, d, e, f, g, h, i, j, t1, t2, m[64];//这里的m表示的是64个字（一个字32位） // 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]);//将数据块划分成16个32bit的字，存放到m的前16个字中 for ( ; i < 64; ++i) m[i] = SIG1(m[i - 2]) + m[i - 7] + SIG0(m[i - 15]) + m[i - 16];//其余的字：16-63则按照公式Mt=σ1(M(t-2))+M(t-7)+σ0(M(t-15))+M(t-16)计算  //第一次迭代，映射初值设为8个哈希初值 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]; /* 原数据块为ABCDEFGH，则一次循环为： 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次加密循环 for (i = 0; i < 64; ++i) { 
    //这里就不必去除以2^32取余数了，因为a-t2长度均为32bit，和超出2^32，超出部分便会被舍弃 t1 = h + EP1(e) + CH(e,f,g) + k[i] + m[i];//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; } //整合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 = 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); } //将消息的总长度(以比特为单位)追加到填充并进行转换 //56-638个字节表示位长，按大端模式(低地址放高位)存放 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]类型为Byte，stx->state[i]类型为WORD(4个Byte) for (i = 0; i < 4; ++i) { 
    //取左高8位，按大端模式，hash[0]为低地址，应取高位，以此类推 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.参考

本篇学习笔记主要参考整合的资料如下：
SHA256算法原理详解
基于STM32的C语言SHA256加密算法
一文读懂SHA256算法原理及其实现