博客

SHA256算法原理介绍以及实现

  • Post author:
  • Post category:其他

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

1.SHA算法概述

SHA（Secure Hash Algorithm安全散列算法）是一个密码散列函数的家族，是FIPS（联邦信息处理标准 Federal Information Processing Standards）
所认证的安全散列算法。能计算出一个数字消息所对应到的，长度固定的字符串（又称消息摘要）的算法。

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

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

SHA-2，名称来自于安全散列算法2（英语：Secure Hash Algorithm 2）的缩写，一种密码散列函数算法标准，由美国国家安全局研发，由美国国家标准与技术研究院（NIST）在2001年发布。属于SHA算法之一，是SHA-1的后继者。其下又可再分为六个不同的算法标准，包括了：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。
这些变体除了生成摘要的长度 、循环运行的次数等一些微小差异外，算法的基本结构是一致的。

2.SHA256算法简介

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

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

1122334455667788    //消息

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

1DCE6604591EFB439D5E87418A1D00DBFD014327D8C4DEA862815714B76AE9A5    //Hash值

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

0122334455667788    //消息
2B85738907AB2C4C39DFFFDD5328A694F4DF04B75E6F482F832279C6BBFE8530   //Hash值

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

3.SHA256算法原理细述

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

3.1常量初始化

SHA256算法中用到了8个哈希初值以及64个哈希常量，64个哈希常量参与到后面的哈希值计算。
SHA256算法的8个哈希初值为：

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.414213562373095048, 而其中
在这里插入图片描述
于是, 质数2的平方根的小数部分取前32位就对应0x6a09e667。以此类推可得8个初始哈希值。

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

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

与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位。

**例：**以信息“abc”为例显示补位的过程。
a,b,c对应的ASCII码分别是97,98,99

于是原始信息的二进制编码为：01100001 01100010 01100011

补位第一步，首先补一个“1” ： 0110000101100010 01100011 1

补位第二步,补423个“0”：01100001 01100010 01100011 10000000 00000000 … 00000000

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

61626380 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进制格式）

61626380 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

其中深蓝色方块是事先定义好的非线性逻辑函数，上文已经做过铺垫
红色田字方块代表 mod $ 2^{32} $ addition，即将两个数字加在一起，如果结果大于$ 2^{32} ，你必须除以 2^{32} $并找到余数。当然，如果我们之定义了数据为32位即四字节，就不必去刻意取余，前面的循环表示A’-H’便是如此。

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 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);
	}
	//将消息的总长度(以比特为单位)追加到填充并进行转换
	//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算法原理及其实现