密码学教程 课件 4-Hash函数

第四章杂凑函数

4.1

概述

4.2SHA-1和SHA-2

4.3SHA-34.4我国商密标准SM3

4.

5

MAC和认证加密

4.1概述认证（authentication）：

采取一些措施保证实体（entity）是他们所宣称那些

人，或消息不被非法者修改。

两类基本认证：

身份认证（identificationorentityauthentication）

双方在线、实时，例如电话；消息认证（messageauthentication；或

数据源认证dataoriginauthentication)

单向、可延时，例如E-mail。数据完整性（DataIntegrity）：

保证消息的不被修改（但不含数据源合法性）。实现数据完整性：

应用抗碰撞的杂凑函数，检查摘要值。实现消息认证：

消息认证=完整性+数据源认证

采用：有密钥的杂凑函数（消息认证码-MAC）；

数字签名等。另外：在数字签名中：

用杂凑函数将消息进行压缩后，对摘要值签名；在随机数产生器中：

用杂凑函数的摘要值作为随机数；因此，杂凑函数是密码学中最常用的部件之一。实现区块链的基本工具！杂凑函数（算法）：

将任意长输入的消息压缩为短的摘要值。有密钥的杂凑函数（MAC：MessageAuthenticationCode）有两个输入：密钥和消息。给定消息，只有知道密钥的人可计算MAC。

无密钥的杂凑函数（MDC：ModificationDetectionCode）只有一个输入即消息。

给定消息，任何人都可计算hash值；一般，将无密钥的杂凑函数就叫做杂凑函数；而将有密钥的杂凑函数叫做消息认证码MAC。杂凑函数的安全性：

抗原象性(pre-imageresistance):

由y=h(x)计算x是计算困难的；yxxx’yyx’x

生日问题：最少多少人中有人生日相同，概率大于50%？

不相同的迭代结构＋压缩函数杂凑函数的构造：最常见的Merkle-Damgard(MD)迭代结构利用分组密码工作模式-构造杂凑函数：利用分组密码的密码分组链接模式CBC和密码反馈模

式CFB。Ekx1y1kx2y2kkH（x1..xn)yn初始矢量EkEkCBCCFBx1y1kx2kkH（x1..xn)xn初始矢量EkEky2Ek直接构造f函数：采用类似分组密码的基本部件和基本运算，构造伪随机函数（避免分组密码中不必要的密钥扩展过程）。利用模运算构造f函数：采用第五章介绍的公钥密码的方法，从单向函数设计压缩函数。MASH-1国际标准，采用模平方运算；利用格计算问题设计的SWIFFT算法；利用纠错码设计的FSB算法；虽然具有较好的理论基础，但实现效率仍有差距。SHA-1和SHA-2是美国（NIST）杂凑函数标准算法。（SHA：StandardHashAlgorithm）

4.2

SHA-1和SHA-2这是一系列杂凑函数MD4、MD5的发展，共同特点是：采用简单的运算多次迭代构造压缩函数。

被攻破的MD4、MD5的轮函数

轮常数消息子块每个512比特消息块分为16个32bit的消息字，经扩展，形成80个（步）的消息字；最后将输入链接值反馈到输出，保证压缩函数单向性。

2002年美国NIST根据实际情况，增加了Hash算法

输出长度，形成SHA-256、SHA-384、SHA-512，

这些算法统称为SHA-2。2004年又提出SHA-224。SHA-2：SHA-256的输出为256bit，链接值分为8个字，压缩函数整体迭代64步，没有明显的轮界限。

SHA－256步运算SHA-224：

与SHA-256初始值不同；

输出从256bit左端截取224bit。SHA-512：

每个字64bit，链接值为512bit；

消息分块为1024bit；迭代89步；SHA-384：

与SHA-512初始值不同；

输出从512bit左端截取384bit。名称输出长度消息块长度字长度轮数*每轮步数SHA-1160512324*20SHA-224/256224/256512321*64SHA-384/512384/5121024641*80我们国家商密标准杂凑函数是SM3关于MD-5、SHA-1的攻击

关于MD结构的攻击2004年，A.Joux提出了多碰撞攻击，已知碰撞时

找到多碰撞很容易；2005年，J.Keley等提出长消息的第二原像攻击，

降低了复杂度，但需要较长的消息；2006年，J.Kelsey等提出了Herding攻击，已知碰

撞时产生有意义的第二原像。第一阶段：（2007年）在全世界征集了51个算法；第二阶段：（2010年）剩余14个算法；第三阶段：（2011年）剩余5个算法；(BLAKE、Groestl、JH、Keccak、Skein)2012年10月初

最终获胜者是Keccak。美国NIST关于SHA-3的征集活动：

4.3

SHA-3Keccak：整体结构为Sponge结构，好处是输出任意长；结构具有一定的可证明安全性。1600bit置换1600bit状态，外部状态r长度，内部状态为c长度；初始值为全0，排列为5*5*64的三维比特数组。SHA3-224：r=1024,c=576SHA3-256:r=1024,c=576SHA3-384:r=512,c=1088SHA3-512:r=512,c=1088后有修改！rc

加轮常数每一行进行这一变换；唯一的非线性部件（5*5的S盒）。Keccak软件实现速度较好；

硬件实现速度最好。

新颖的结构设计；

与SHA-2完全不同。SHA3-256输出摘要长度（固定）为256的SHA3算法；SHA3-512输出摘要长度（固定）为512的SHA3算法；SHAKE256输出摘要长度可变（r=1024）的SHA3算法；SHAKE512输出摘要长度可变（r=512）的SHA3算法。

4.

4我国商密标准SM3SM3是2010年10月我国商用密码管理局颁布的商用密码Hash标准算法。迭代结构仍采用MD结构，中间状态长度为256比特，规模与SHA-2的SHA-256相当，但要防止了发现的问题，增强了安全性。它在克服MD-x系列存在的问题基础上，仍采用简单运算的组合，保持了计算简便和速度优势。

其中两个布尔函数为：其中两个置换函数为：

4.5

MAC和认证加密利用Hash构造MAC。两个输入：消息+密钥

没有密钥不能计算摘要；实现消息认证。

消息认证码（MAC）是带密钥的Hash函数。

认证加密：

保密性+密文认证，密文+标签tag加密-then-MACMAC-then-加密（一般不安全）CAESAR竞赛：

2013年1月由著名密码学家Bernstein在NIST支持下

组织开展的密码算法竞赛，目的是选择安全高效的

认证加密算法，推动其设计与分析技术的发展。2014年3月开始提交算法，48个算法；2015年7月选出29个算法进入第二轮；2018年8月选出15个算法进入第三轮；2019年2月宣布6个算法入选最终算法集。Ascon算法

利用Sponge结构构造的轻量级算法。

四个阶段：初始阶段、关联数据、形成密文和

最后产生标签阶段。Cryptographiccompetitions(http://competitions.cr.yp.to)NESSIE（2000-2003）:

(NewEuropeanSchemesforSignatures,IntegrityandEncryption)欧洲研究项目，筛选各种算法NIST

AES

（1997-2000）：

美国筛选分组算法活动，确定AESeStream（2004-2008）：

欧洲ECRYPT筛选流密码活动NISTSHA-3（2007-2012）：

美国筛选杂凑函数活动，确定SHA-3CAESAR（2012-2017）：

轻量级认证加密算法PHC:Password