《应用密码学》课件10-认证理论与技术- Hash函数

1第7章认证理论与技术

----Hash函数2上讲内容回顾流密码（序列密码）的思想起源流密码的分类基于移位寄存器的流密码算法RC4算法3本章主要内容单向函数Hash函数的定义及发展现状SHA-1算法hash函数的用途消息认证码简介CBC-MAC算法HMAC算法4定义.

函数若满足下列两个条件，则称之为强单向函数：1计算是容易的，即是多项式时间可计算的；2计算函数的逆是困难的，即对每一多项式时间概率算法，每一多项式和充分大的有单向函数5单向函数注.1可能有少量x给出的f(x)可用多项式时间概率算法求逆；2单向函数的存在性没有理论上的证明，但是有些函数，经过实践检验，至今没有发现多项式时间的求逆算法，仍在使用.例1伪随机数生成器(种子密钥—密钥流)例2因子分解问题（因子—合数）6Hash函数定义消息是任意有限长度，哈希值是固定长度.Hash的概念起源于1956年，Dumey用它来解决symboltablequestion(符号表问题)。使得数据表的插入、删除、查询操作可以在平均常数时间完成。1A3FD4128A198FB3CA345932Thisisaninputtoacrypto-graphichashfunction.Theinputisaverylongstring,thatisreducedbythehashfunctiontoastringoffixedlength.Thereareadditionalsecurityconditions:itshouldbeveryhardtofindaninputhashingtoagivenvalue(apreimage)ortofindtwocollidinginputs(acollision).h奇偶校验码新版身份证7散列算法的概念及结构outputhH（M）h是多对一映射M碰撞或冲突8Hash函数的定义单向性（抗原像）：对干任意给定的消息，计算其哈希值容易.但是，对于给定的哈希值h，要找到M使得H(M)＝h在计算上是不可行的.

弱抗碰撞（抗二次原像）：对于给定的消息M1，要发现另一个消息M2，满足H(M1)＝H(M2)在计算上是不可行的.强抗碰撞：找任意一对不同的消息M1，M2

，使H(M1)＝H(M2)在计算上是不可行的.随机性.9散列算法的概念及结构Moutputh由m计算h(m)容易H(M)outputhM由h(m)计算上m不容易H(M)10散列算法的概念及结构outputhH抗弱碰撞性M给定H(M)mm‘11散列算法的概念及结构outputH(m)=H(m’)H抗强碰撞性Mmm‘12Hash函数的定义Hash函数的安全性需求鸽子原理生日攻击13Hash函数的定义Hash函数的分类不带密钥的哈希函数主要用于消息完整性带密钥的哈希函数主要用于消息源认证和消息完整性14不带密钥的哈希函数的发展1978年，Merkle和Damagad设计MD迭代结构

1993年，莱学家和Messay改进为MD加强结构15不带密钥的哈希函数的发展散列算法MD族是在90年代初由mitlaboratoryforcomputerscience和RSAdatasecurityinc的Ron・Rivest设计的，MD代表消息摘要（message-digest）.md2、md4和md5都产生一个128位的信息摘要.MD2

1989年开发出md2算法.在这个算法中，首先对信息进行数据补位，使信息的字节长度是16的倍数.然后，以一个16位的检验和追加到信息末尾。并且根据这个新产生的信息计算出散列值。后来，rogier和chauvaud发现如果忽略了检验和将产生md2碰撞.MD4

1990年开发出md4算法.Denboer和bosselaers以及其他人很快的发现了攻击md4版本中第一步和第三步的漏洞.dobbertin向大家演示了如何利用一部普通的个人电脑在几分钟内找到md4完整版本中的碰撞.MD5

1991年，rivest开发出技术上更为趋近成熟的md5算法.denboer和bosselaers曾发现md5算法中的伪碰撞（pseudo-collisions），但除此之外就没有其他被发现的分析结果了.RIPEMD-128/160/320

RIPEMD由欧洲财团开发和设计.16不带密钥的哈希函数的发展SHA系列算法是NIST根据Rivest设计的MD4和MD5开发的算法.国家安全当局发布SHA作为美国政府标准.SHA表示安全散列算法.SHA-0

SHA-0正式地称作SHA，这个版本在发行后不久被指出存在弱点.SHA-1SHA-1是NIST于1994年发布的，它与MD4和MD5散列算法非常相似，被认为是MD4和MD5的后继者.SHA-2SHA-2实际上分为SHA-224、SHA-256、SHA-384和SHA-512算法.

17HAVAL

1992年YuliangZheng设计了HAVAL函数，它与许多其他散列函数不同.Gost

Gost是一套苏联标准.不带密钥的哈希函数的发展18不带密钥的哈希函数

碰撞攻击复杂度19碰撞攻击复杂度Bruteforce:1millionPCsorUS$100000hardware不带密钥的哈希函数20主要hash算法：HAVALMD5SHA-1SHA-2Ext.MD4RIPEMDRIPEMD-160MD4TigerWhirlpool不带密钥的哈希函数的发展21不带密钥的哈希函数的发展NESSIE工程推荐使用的hash算法有SHA-256/384/512和Whirlpool;日本密码研究与评估委员会推荐使用的算法有RIPEMD-160、SHA-1/256/384/512。ECRYPT也在hash算法研究方面举办了一系列活动。此外，NIST于2008年启动新的hash标准的征集活动。除迭代结构以外的结构适用于任何平台的压缩函数2008年10月提交文档，收到64个算法，公开56个，51个进入第一轮评估2009年10月，第二轮评估开始，剩余14个算法22SHA系列(SecureHashAlgorithm)SHA-1，SHA-256，SHA-384，SHA-512SHA-1，SHA-256的分组大小是512SHA-384，SHA-512的分组大小是1024SHA-1输出的摘要是160bitSHA-256输出的摘要是256SHA-384输出的摘要是384SHA-512输出的摘要是51223SHA1

算法原理

分段运算：512bits

杂凑值长度：160bits

初始向量：160bitsSHA-1消息摘要每个分块512比特，最后一个分块中最后64比特记录数据长度。任意有限长度消息输入，如何分512比特的块。24SHA-1算法第一步第一步：填充消息使得消息的长度（bit为单位）模512为448。如果数据长度正好是模512为448，增加512个填充bit，也就是说填充的个数为1~512bit。填充方法：第一个bit为1，其余全部为0。补零的个数计算公式d=(447－|x|)mod512X||1||0d||l(l=|x|表示消息长度）l+1+d

≡448mod512（X表示消息长度，k为填充0的位数）25SHA-1算法第二步第二步：补足长度

将数据长度转换为64bit的数值然后对每个512bit按每组32bit进行分组,可分为16组。512=32*1626SHA-1算法——数据扩充27SHA-1算法——数据扩充信息512bits先分成W[0]~W[15],32bits每段W[16]以后的填入方式：W[t]=CLS1(W[t-16]⊕W[t-14]⊕W[t-8]⊕W[t-3]),

t=16,17,…,79比如：

W[16]=CLS1

(W[0]⊕W[2]⊕W[8]⊕W[13])W[79]=CLS1

(W[63]⊕W[65]⊕W[71]⊕W[76])其中：CLS1表示向左循环移动一比特。W[K],

k=0,1,....,79，28SHA1的IV初值用到5个变量，分别为A、B、C、D，E均为32bit长。初始化为：

暂存器初始值A：67452301B：EFCDAB89C：98BADCFED：10325476E：C3D2E1F029SHA-1演算法(一)SHA-1算法

FIPSPUB180与

FIPSPUB180-1

杂凑值：160bits30处理程序：4回合，共计

80次；5个缓存器

A=E+f1-4(t,B,C,D)+S5(A)+W[t]+K1-4

B=AC=S30(B)D=CE=DSHA-1压缩函数31上图表达式的说明其中

f1-4(t,B,C,D)=步t的基本逻辑函数Sk=循环左移k位Wt=一个从当前512位输入数据块导出的32位字K1-4＝一个用于加法的常量，四个不同值+=模232加32f1-4逻辑函数的定义33

回合步骤序号输入常数取值方式(整數)第一回合0≦t≦19K1=5A82799[230×2^0.5]第二回合20≦t≦39K2=6ED9EBA1[230×3^0.5]第三回合40≦t≦59K3=8F1BBCDC[230×5^0.5]第四回合60≦t≦79K4=CA62C1D6[230×10^0.5]SHA-1算法——Kt的取值输入常数整数的功能34SHA算法处理步骤：步驟1：將输入明文（512bits）以每32bits為单位，分別存入W[k]中，其中k=0,1,2,..,15,Wt由W[k]扩展步驟2：初始化A、B、C与

D缓存器，如下：

A：67452301

B：EFCDAB89

C：98BADCFE

D：10325476

E：C3D2E1F035步驟3：进入第一回合运算，执行

20

次：

a,b,c,d,e←(e+f1(t,b,c,d)+S5(A)+Wt+Kt),A,S30(B),C,D)步驟4：进入第二回合运算，执行

20

次：

a,b,c,d,e←(

e+f2(t,b,c,d)+S5(A)+Wt+Kt),A,S30(B),C,D)步驟5：进入第三回合运算，同样执行

20

次：

a,b,c,d,e←(

e+f3(t,b,c,d)+S5(A)+Wt+Kt),A,S30(B),C,D)步驟6：进入第四回合运算，同样执行

20

次：

a,b,c,d,e←(

e+f4(t,b,c,d)+S5(A)+Wt+Kt),A,S30(B),C,D)步驟7：输出消息摘要，执行

SUM32计算。36SHA算法实例例7-1对字符串”abc”，运用SHA-1求散列值解:首先”abc”二进制表示为：011000010110001001100011，共24位长度第一步：按照SHA-1要求，填充数据

512－64－24＝424（填充1位“1”，423位“0”，及1000…000)512位的输入数据为(十六进制表示）：6162638000000000，……,0000001837而W0=61626380,W1=W2=…=W14=00000000,W15=00000018步驟2：初始化A、B、C与

D缓存器，如下：

A：67452301

B：EFCDAB89

C：98BADCFE

D：10325476

E：C3D2E1F038SHA算法步驟3：进入第一回合运算，执行

20

次：

a,b,c,d,e←(e+f1(t,b,c,d)+S5(A)+Wt+Kt),A,S30(B),C,D)求a，b，c，d,e的值39SHA算法哈希函数网络表述方法误区资料和网络上，经常说法MD5加密算法，SHA-1加密算法？或者MD5单向加密40“MD5加密算法”、“SHA-1加密算法”这种表述不妥。“MD5单向加密”，这种表述严格来说没有错误，哈希函数确实是单向的变换。但是一般说来在密码学上，称加密算法，一般意味着要能解密。而哈希函数是不能够解密，所以我们在密码学上，一般哈希函数，不会说成MD5加密、SHA-1加密，而是说哈希算法。哈希出来的结果，一般也成为摘要值，哈希值，散列值，而不会说“密文”。41Hash函数的用途消息完整性检测Hash链用于口令认证数字签名（速度快；防止消息伪造）消息完整性和消息源认证（MAC）。。。。。。42Hash函数的用途消息完整性检测

“网站卫士”是一个网络安全软件产品。它的主要功能是通过网络扫描网站的网页，监测网页是否被修改，当发现网页被修改后，系统能够自动报警和恢复。初始化过程（1）对监视网站的文件备份到监控主机上。（2）对每个备份的文件生成一个结构：文件位置、文件的哈希值。监控过程监控主机对监控网站进行轮回扫描，对扫描的文件进行如下操作：（1）计算文件的哈希值，并与备份的文件哈希值进行比较，如果相同，转（4）步。（2）如果不同，上载备份文件替换网站现有文件，转（4）步。（3）如果备份文件不存在，则删除网站上这个文件，转（4）步。（4）监控程序扫描下一文件。43Hash函数的用途消息完整性检测44Hash函数的用途口令认证

常见的Unix系统口令以及多数论坛/社区系统口令都是经MD5处理后保存其摘要信息串；45消息认证消息认证是一个过程，用以验证接收消息的真实性（的确是由它所声称的实体发来的）和完整性（未被篡改、插入、删除），同时还用于验证消息的顺序性和时间性（未重排、重放、延迟）。消息认证过程中检验内容应包括：（1）证实报文的源和宿；（2）报文内容是否曾受到偶然的或有意的篡改；（3）报文的序号和时间先后。

46消息认证使接收者能识别：消息的源，内容的真伪，时间性和信宿。这种认证只在相应通信的双方之间进行，而不允许第三者进行上述认证。认证不一定是实时的，可用消息认证码MAC（Messageauthenticacode）对消息做认证,主要有：（1）基于分组密码的MAC

（2）基于散列函数（HASH）的MAC47基于分组密码的MACCBC-MAC算法是最常用的一种基于分组的MAC算法48基于Hash的MACMD5-MAC算法的是由MD5算法经过变换得到，记为MD5’，它的性能与MD5接近，在软件实现中慢5%~20%49MD5-MAC算法50消息认证码使用方式

应用范围：

在密码学和数据安全技术中，它是实现有效、安全可靠数字签字和认证的重要工具，是安全认证协议中的重要模块。51消息认证52杂凑函数的使用消息认证与机密性（与明文相关）53消息认证与机密性（与密文相关）54HMAC是由H.Krawezyk，M.Bellare，R.Canetti于1996年提出的一种基于Hash函数和密钥进行消息认证的方法，已作为RFC2104被公布，并在IPSec和其他网络协议(如SSL)中得以应用。HMAC所能提供的消息认证包括两方面内容：（1）消息完整性认证：能够证明消息内容在传送过程没有被修改。（2）信源身份认证：因为通信双方共享了认证的密钥，接收方能够认证发送该数据的信源于所宣称的一致，即能够可靠的确认接收的消息与发送的一致HMAC算法55RFC2104目前已提出了很多将杂凑函数用于构造MAC的方法，其中HMAC就是其中之一，已作为RFC2104被公布，并在IPSec和其他网络协议(如SSL)中得以应用56HMAC的设计目标RFC2104列举了HMAC的以下设计目标：(1)不必修改而直接使用现有Hash函数。特别地，很容易免费得到软件上执行速度较快的Hasb函数及其代码；(2)如果找到或者需要更快或更安全的Hash函数，应能很容易地替代原来嵌入的Hash函数；(3)应保持Hash函数原有的性能，不因用于HMAC而使其性能降低；(4)以简单方式使用和处理密钥；

(5)如果已知嵌入的Hash函数的强度，易于分析HMAC用于认证时的密码强度。57设计目标的说明前两个目标是将杂凑函数当作一个黑盒使用最后一条设计目标则是HMAC优于其他不是基于杂凑函数的MAC的一个主要方面，HMAC在其镶嵌的杂凑函数具有合理密码强度的假设下，可证明是安全的58算法描述H：嵌入的杂凑函数(如MD5、SHA)M：HMAC的输入消息(包括杂凑函数所要求的填充位)，Yi：(0≤i≤L-1)是M的第i个分组，L：M的分组数，b：是一个分组中的比特数（sha-1的512）n：嵌入的杂凑函数所产生的杂凑值的长度（160？）K：密钥，如果密钥长度大于b，则将密钥输入到杂凑函数中产生一个n比特长的密钥，K+是左边经填充0后的K，K+的长度为b比特，ipad为b/8个00110110，opad为b/8个01011010。5960HMAC的实现61本节要点小结单向函数Hash函数的定义hash函数的用途SHA-1算法62课堂测试1试寻找几个生活中和数学上单向函数的例子.2为什么SHA-1和MD5处理的消息最大长度为264-1比特?3采用SHA-1哈希算法，输入10个字节的消息“0123456789”，请问需要填充多少比特，并写出填充之后的512比特块，W0，W1，W2，W14，W15，以及W16（用十六进制表示）字符“0”对于的ASCII值为48，对应十六进制为0x30。例题2讲解MD5和SHA-1数据长度为64比特，MD5可以任意长度，SHA-1最大为264-1bitsMD5最大消息长度SHA-1的最大消息长度例题3讲解

65补充内容66SHA-2561.消息填充首先将比特“1”添加到消息的末尾，再添加k个零，这里k是方程l+1+k≡448mod512的最小的非负解.然后再添加一个64比特长的块，其值等于消息M的长度l的二进制表示.使得填充后的消息的长度为512比特的倍数.67SHA-256

2SHA-256的初始变量

这些初值由计算前8个素数的平方根的小数部分的前32位(二进制)生成3压缩函数的消息分组长度为512比特，压缩函数共64步变换.4输出散列值长度为256比特.68SHA-25669SHA-256SHA-256压缩函数第(i-1)块的输出链接变量a、b、c、d、e、f、g和h分别赋值：fort=0to63计算第i个Hash值H(i)：需要临时寄存器T1和T270SHA-256SHA-256的消息编排当消息填充完成后，将消息块M(1)，M(2)，…，M(N)按序排列，然后执行以下步骤：Fori=1toN{7171SHA-256SHA-256使用了6个逻辑函数，设x,y和z为3个32比特长的自变量，输出结果都是32比特长的字，逻辑函数定义如下：72SHA-256SHA-256的常数共使用了64个32位字长的常数，它们分别由最小的64个素数的三次方根的小数部分的前32位产生（二进制表示）428a2f9871374491b5c0fbcfe9b5dba53956c25b59f111f1923f82a4ab1c5ed5d807aa9812835b01243185be550c7dc372be5d7480deb1fe9bdc06a7c19bf174e49b69c1efbe47860fc19dc6240ca1cc2de92c6f4a7484aa5cb0a9dc76f988da983e5152a831c66db00327c8bf597fc7c6e00bf3d5a7914706ca63511429296773SHA-25627b70a852e1b21384d2c6dfc53380d13650a7354766a0abb81c2c92e92722c85a2bfe8a1a81a664bc24b8b70c76c51a3d192e819d6990624f40e3585106aa07019a4c1161e376c082748774c34b0bcb5391c0cb34ed8aa4a5b9cca4f682e6ff3748f82ee78a5636f84c878148cc7020890befffaa4506cebbef9a3f7c67178f274SHA-512填充消息M,将消息填充到1024的整数倍.将填充消息分割为N个1024比特长的消息块M(1)，M(2)，…，M(N).设置初始Hash值H(0).迭代压缩，压缩函数消息分块长度为1024比特，压缩函数为80步运算.N次迭代后的输出512比特链接变量作为消息散列值输出.7475SHA-384SHA-384算法可用来Hash任意l(0≤l≤2128)位长的消息M。算法的具体实现和SHA-512是一样的，惟一不同的是以下两点：

1)初始Hash值H(0)的设置不同；

2)输出384比特长的消息摘要，即剪切H(N)的左边384比特位产生：7576SHA-384和SHA-5121消息填充假设消息M的长度为l,首先将比特“1”添加到消息的末尾，再添加k个零。这里k是方程l+1+k≡896mod1024

的最小的非负解。然后再添加一个128比特长的块，其值等于消息M的长度l的二进制表示。例如，消息“abc”,其8比特的ASCII表示长度为，因此，首先填充一个“1”，再填充896-(24+1)=871个零，然后再填充一个长度l=24的128位的二进制，即可得一长度1024位的二进制对SHA-384和SHA-512来说，填充消息被分为N个1024比特的块，.011000010110001001100011100…00 00…011000“a”“b”“c”871128l=247777SHA-384和SHA-5122SHA-384初始连接变量

这些初值由计算第九个至第十六个素数的平方根的小数部分的前64位(二进制)生成7878SHA-384和SHA-5122SHA-512初始链接变量

这些初值由计算前八个素数的平方根的小数部分的前64位(二进制)生成79SHA-384和SHA-5123SHA-384和SHA-512中的函数SHA-384和SHA-512都使用了6个逻辑函数，x,y和z为3个64比特长自变量，输出结果都是64比特长的字80SHA-384和SHA-5124SHA-238和SHA-512的常数SHA-238和SHA-512使用了80个64位字长的常数，这些常数由最小的80个素数的三次方根的小数部分的前64位产生（二进制表示）。在十六进制的情况下，其值为：428a2f98d728ae227137449123ef65cdb5c0fbcfec4d3b2fe9b5dba58189dbbc3956c25bf348b53859f111f1b605d019923f82a4af194f9bab1c5ed5da6d8118d807aa98a303024212835b0145706fbe243185be4ee4b28c550c7dc3d5ffb4e272be5d74f27b896f80deb1fe3b1696b19bdc06a725c71235c19bf174cf692694e49b69c19ef14ad2efbe4786384f25e30fc19dc68b8cd5b5240ca1cc77ac9c652de92c6f592b02754a7484aa6ea6e4835cb0a9dcbd41fbd476f988da831153b5983e5152ee66dfaba831c66d2db43210b00327c898fb213fbf597fc7beef0ee4c6e00bf33da88fc2d5a79147930aa72506ca6351e003826f142929670a0e6e7027b70a8546d22ffc2e1b21385c26c9264d2c6dfc5ac42aed53380d139d95b3df650a73548baf63de766a0abb3c77b2a881c2c92e47edaee692722c851482353b81SHA-384和SHA-512a2bfe8a14cf10364a81a664bbc423001c24b8b70d0f89791c76c51a30654be30d192e819d6ef5218d69906245565a910f40e35855771202a106aa07032bbd1b819a4c116b8d2d0c81e376c085141ab532748774cdf8eeb9934b0bcb5e19b48a8391c0cb3c5c95a634ed8aa4ae3418acb5b9cca4f7763e373682e6ff3d6b2b8a3748f82ee5defb2fc78a5636f43172f6084c87814a1f0ab728cc702081a6439ec90befffa23631e28a4506cebde82bde9bef9a3f7b2c67915c67178f2e372532bca273eceea26619cd186b8c721c0c207eada7dd6cde0eb1ef57d4f7fee6ed17806f067aa72176fba0a637dc5a2c898a6113f9804bef90dae1b710b35131c471b28db77f523047d8432caab7b40c724933c9ebe0a15c9bebc431d67c49c100d4c4cc5d4becb3e42b6597f299cfc657e2a5fcb6fab3ad6faec6c44198c4a475817.82SHA-384和SHA-5125消息编排当预处理过程完成后，将消息块M(1)，M(2)，…，M(N)按序排列，然后执行以下步骤：Fori=1toN

准备消息进程表{Wt}：8283SHA-384和SHA-5126压缩函数把第(i-1)次迭代的输出的链接变量分别赋值给8个工作变量a、b、c、d、e、f、g和h；fort=0to79：计算第i个Hash值H(i)：SHA-3自2007年，NIST发起了SHA-3竞赛以征集新的Hash算法以来，截止到2010年10月，第二轮遴选结束，共有五种算法进入最终轮遴选，入选的五个算法是：BLAKE、Grøstl、JH、Keccak、Skein，到2012年，NIST最终选择Keccak算法作为SHA-3标准(即美国的FIPSPUB202）。SHA-3为了与SHA-2完全兼容，SHA-3中也提出了4个Hash算法SHA3-224,SHA3-256,SHA3-384,SHA3-512，可完全替换SHA-2。Keccak算法是由GuidoBertoni，JoanDaemen，MichaëlPeeters，以及GillesVanAssche设计的。作为SHA家族最新的算法，其采用了不同于传统MD结构，而选择了海绵构造（sponge结构）。通过采用这种结构，常用于MD结构的攻击方法难以进行，增加了其算法安全性。84Keccak算法的总体描述85

86SHA3中Keccak算法相关参数说明

87Keccak算法消息填充

8889Keccak算法流程90

91Keccak算法中一维