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算法原理及其实现