区块链与密码学全民课堂第5-3讲：详解常用哈希函数（一）

导语：本课堂用通俗易懂的系列内容为大家呈现区块链与密码学领域相关知识。这里有知识也有故事，从感兴趣到有乐趣，全民课堂等你来学。这个系列中的课程内容首先从比特币着手进行入门介绍，再延伸至区块链的相关技术原理与发展趋势，然后深入浅出地依次介绍在区块链中应用的各类密码学技术。欢迎大家订阅本公众号，持续进行学习。

5.3 SHA-256算法简介

目前常用的哈希函数有三种，分别为SHA-256算法、Keccak算法、SM3算法，今天我们对SHA-256算法进行讲解。

– 概况 –

SHA系列标准哈希函数是由美国标准与技术研究所(National Institute of Standards and Technology，NIST)组织制定的。

• 1993年公布了SHA-0 (FIPS PUB 180)，后发现不安全。

• 1995年公布了SHA-1(FIPS PUB 180–1)。

• 2002年公布了SHA-2( FIPS PUB 180–2)，包括3种算法：SHA-256, SHA-384, SHA-512。

• 2005年王小云院士给出一种攻击SHA-1的方法，用269操作找到一个强碰撞，以前认为是280。

• 2017年2月23日，谷歌宣布找到SHA-1碰撞的算法，需要耗费110块GPU一年的运算量。

– SHA-256算法描述 –

• 输入数据长度为l比特，1≤l≤2⁶⁴-1

• 输出哈希值的长度为256比特

(1) 常量与函数

SHA-256算法使用以下常数与函数：

① 常量

初始值IV为：

0x6a09e667 bb67ae85 3c6ef372 a54ff53a 

510e527f 9b05688c 1f83d9ab 5be0cd19

这些初值是对自然数中前8个质数(2,3,5,7,11,13,17,19)的平方根的小数部分取前32比特而来。

举个例子来说，√2小数部分约：

0.414213562373095048

而0.414213562373095048 ≈ 6∗16−1 +a∗16−2+0∗16−3 +9∗16−4 +…

于是，质数2的平方根的小数部分取前32比特就对应出0x6a09e667。

另外，SHA-256还用到了64个常数：K₀, K₁, …,K₆₃ =

和8个初始值类似，这些常量是对自然数中前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比特而来。

② 函数

SHA-256用到了以下函数

其中：∧表示按位“与”；¬ 表示按位“补”；⊕表示按位“异或”；

ROTRi(x)表示循环右移i比特；SHRi(x)表示右移i比特；

(2) 算法描述

① 填充

• 对数据填充的目的是使填充后的数据长度为512的整数倍。因为迭代压缩是对512位数据块进行的，如果数据的长度不是512的整数倍，最后一块数据将是短块，这将无法处理。

• 设消息m长度为l比特。首先将比特“1”添加到m的末尾，再添加k个“0”，其中，k是满足下式的最小非负整数l+1+k = 448mod512。

• 然后再添加一个64位比特串，该比特串是长度l的二进制表示。填充后的消息m的比特长度一定为512的倍数。

• 以信息“abc”为例显示补位的过程。a, b, c对应的ASCII码分别是97, 98, 99；于是原始信息的二进制编码为：01100001 01100010 01100011。

补一个“1” ：0110000101100010 01100011 1

补423个“0”：01100001 01100010 01100011 10000000 00000000 … 00000000

补比特长度24 (64位表示)，得到512比特的数据：

② 消息分块

将填充后的消息m′按512比特分成n组：

m′= M⁽⁰⁾||M⁽¹⁾|| · · · ||M^(n-1)

其中：n = (l+k+65)/512

③ 消息扩展

对一个消息分组M(t) 迭代压缩之前，首先进行消息扩展：将16个字的消息分组M ^t 扩展生成如下的64个字，供压缩函数使用W₀，W₁，…，W_63，消息扩展把原消息位打乱，隐蔽原消息位之间的关联，增强了安全性。

消息扩展的步骤如下：

④ 压缩函数

压缩函数是SHA-256的核心，令a, b, c, d, e, f, g, h为字寄存器，T₁, T₂为中间变量。

压缩函数：V^(t+1)= CF(V^(t)，M^(t)), 0 ≤ t ≤n -1。

压缩函数CF的压缩处理：内层迭代

① FOR t = 0 TO 63

② CF= F(T₁ , T₂ , a, b, c, d, e, f, g, h , M^(t))

③ END FOR

⑤ 基本压缩函数

基本压缩函数的流程如右边公式所述。

说明：

• a, b, c, d, e, f, g, h为字寄存器，T₁, T₂为中间变量。

• +运算为mod 2³²算术加运算。

字的存储为大端(big-endian)格式。即，左边为高有效位，右边为低有效位。

⑥ SHA-256工作全过程

– 安全性 –

• 专业机构设计，经过充分测试和论证

• 安全性可满足应用的安全需求

• 学者已开展对SHA-256的安全分析(如缩减轮的分析)，尚未发现本质的缺陷

– 程序设计 –

• typedef.h：定义数据类型

• sha256.h：定义SHA-256算法相关功能函数、数据接口声明

• sha256.c：实现SHA-256算法相关功能函数

• sha256_test.h：定义测试函数、数据接口声明

• Sha256_test.c：实现测试功能函数

• main.c：实现main函数，测试程序的正确性、性能等

常用的SHA-256算法就讲到这里啦，下节课我们将学习常用哈希函数Keccak算法，敬请期待！

同学们可以关注PlatON World，学习更多图学院系列课程。我们下节课见啦。