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

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

5.5.1 SM3算法简介

SM3是我国商用密码管理局颁布的商用密码哈希函数，广泛应用于：商用密码应用中的辅助数字签名和验证、消息认证码的生成与验证、随机数的生成等领域。SM3在结构上属于基本压缩函数迭代型的哈希函数。

5.5.2 SM3算法描述

输入数据长度为l比特，1≤l ≤2⁶⁴-1；输出哈希值的长度为256比特。

– 常量与函数 –

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

常量

初始值IV=7380166f 4914b2b9 172442d7 da8a0600 a96f30bc 163138aa e38dee4d b0fb0e4e。

函数

布尔函数

置换函数

其中：∧表示按位“与”；∨表示按位“或” ；¬ 表示按位“补”；⊕表示按位“异或”；<<<表示循环左移；

– 算法描述 –

• 填充

对数据填充的目的是使填充后的数据长度为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比特的数据：

• 消息扩展

对一个消息分组B⁽ⁱ⁾迭代压缩之前，首先进行消息扩展：

将16个字的消息分组B⁽ⁱ⁾扩展生成如下的132个字，供压缩函数CF使用W_0，W₁，…，W₆₇，W′₀，W′₁，…，W′₆₃

消息扩展把原消息位打乱，隐蔽原消息位之间的关联，增强了安全性

消息扩展的步骤如下：

将消息分组B⁽ⁱ⁾划分为16个字W₀，W₁，…，W₁₅

———–

FOR j=16 TO 67

W_j←P₁(W_{j –16} ⊕W_j−9⊕(W_j−3<<< 15)) ⊕(W_j−13<<< 7) ⊕W_j−6

END FOR

———-

FOR j=0 TO 63

W_j′= W_j⊕ W_j +4

END FOR

• 迭代压缩处理

将填充后的消息m′按512比特分组：m′= B⁽⁰⁾B⁽¹⁾…B⁽ⁿ⁻¹⁾，其中：n = (l+k+65)/512

对m′按下列方式迭代压缩：//外层迭代

FOR i = 0 TO n-1 

——–

V ⁽ⁱ⁺¹⁾⁼ CF( V⁽ⁱ⁾，B⁽ⁱ⁾ ) 

——–

ENDFOR

其中CF是压缩函数，V ⁽⁰⁾为256比特初始值IV，B⁽ⁱ⁾为填充后的消息分组，迭代压缩的结果为V⁽ⁿ⁾，它为消息m的哈希值.

• 压缩函数

压缩函数是SM3的核心，令A, B, C, D, E, F, G, H为字寄存器，SS1, SS2, TT1, TT2为中间变量，压缩函数：V^( i+1) = CF(V⁽ⁱ⁾，B⁽ⁱ⁾), 0 ≤i ≤n -1

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

FOR j=0 TO 63 

——–

CF= F(SS1, SS2, TT1, TT2 ， A, B, C, D, E, F, G, H ，W_j，W′_j) //基本压缩函数 

——–

ENDFOR

• 基本压缩函数F

SS1 ←((A <<< 12) + E + (T_j<<< j)) <<< 7 

——–

SS2 ←SS1 ⊕(A <<< 12) 

——–

TT1 ←FF_j (A，B，C) + D + SS2 +W_j’ 

——–

TT2 ←GG_j (E，F，G ) + H + SS1 + W_j  

——–

D ←C 

——–

C ←B <<< 9 

——–

B ←A 

——–

A ←TT1 

——–

H ←G 

——–

G ←F <<<19 

F ←E E ←P0( TT2 )

• SM3工作全过程

• 压缩函数的作用

压缩函数是SM3安全的关键。

第一个作用是数据压缩。SM3的压缩函数CF把每一个512位的消息分组B⁽ⁱ⁾压缩成256位.经过各数据分组之间的迭代处理后把l位的消息压缩成256位的哈希值。

第二个作用是提供安全性。在SM3的压缩函数CF中，布尔函数FF_j(X,Y,Z)和GG_j(X,Y,Z)是非线性函数，经过循环迭代后提供混淆作用。

置换函数P0(X)和P1(X)是线性函数，经过循环迭代后提供扩散作用.加上压缩函数CF中的其它运算的共同作用，压缩函数CF具有很高的安全性，从而确保SM3具有很高的安全性。

– 安全性 –

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

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

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

常用的SM3算法就讲到这里啦，下节课我们将学习常用哈希函数在区块链中的应用，敬请期待！

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