[理学]现代密码学第7章：散列函数ppt课件

1、散列函数散列函数第第7章章本章主要内容本章主要内容n1 1、音讯认证码、音讯认证码n2 2、散列函数、散列函数n3 3、MD5MD5杂凑算法杂凑算法n4 4、平安杂凑算法、平安杂凑算法n5 5、HMACHMAC算法算法n习题习题 曾引见过信息平安所面临的根本攻击类型，包括被动攻击获取音讯的内容、业务流分析和自动攻击冒充、重放、音讯的篡改、业务回绝。抗击被动攻击的方法是前面已引见过的加密，本章引见的音讯认证那么是用来抗击自动攻击的。 音讯认证是一个过程，用以验证接纳音讯的真实性确实是由它所声称的实体发来的和完好性未被篡改、插入、删除，同时还用于验证音讯的顺序性和时间性未重排、重放、延迟。攻击的类

2、型攻击的类型n 除此之外，在思索信息平安时还需思索业务的不可否认性，即防止通讯双方中的某一方对所传输音讯的否认。实现音讯的不可否认性可经过数字签字，数字签字也是一种认证技术，它也可用于抗击自动攻击。攻击的类型攻击的类型攻击的类型攻击的类型攻击攻击自动攻击自动攻击被动攻击被动攻击获取音讯的内容获取音讯的内容业务流分析业务流分析冒充冒充重放重放篡改篡改 用来验证音讯的真实性。用来验证音讯的真实性。 用来验证音讯的完好性。用来验证音讯的完好性。 用来验证音讯的顺序性和时间性。用来验证音讯的顺序性和时间性。 用来验证音讯的不可否认性。用来验证音讯的不可否认性。 认证是一个过程，音讯认证机制需求认证是一

3、个过程，音讯认证机制需求有产生认证符的根本功能。认证符用来判别有产生认证符的根本功能。认证符用来判别音讯的真实性。认证符的产生有音讯认证码音讯的真实性。认证符的产生有音讯认证码MAC)MAC)和散列函数和散列函数(hash)(hash)两大类。两大类。认证的功能认证的功能音讯认证包括:音讯完好性 身份识别 不可否认性 音讯认证的含义音讯认证的含义 音讯认证码是指音讯被一密钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值，也称为密码校验和。此时需求通讯双方A和B共享一密钥K。设A欲发送给B的音讯是M，A首先计算MAC=CK(M)，其中CK()是密钥控制的公开函数，然后向B发送MMAC，

4、B收到后做与A一样的计算，求得一新MAC，并与收到的MAC做比较，如图1a所示。1.1.音讯认证码音讯认证码1.1 音讯认证码的定义及运用方式音讯认证码的定义及运用方式假设仅收发双方知道K，且B计算得到的MAC与接纳到的MAC一致，那么这一系统就实现了以下功能： 接纳方置信发送方发来的音讯未被篡改，这是由于攻击者不知道密钥，所以不可以在篡改音讯后相应地篡改MAC，而假设仅篡改音讯，那么接纳方计算的新MAC将与收到的MAC不同。 接纳方置信发送方不是冒充的，这是由于除收发双方外再无其他人知道密钥，因此其他人不能够对本人发送的音讯计算出正确的MAC。音讯认证码的定义及运用方式音讯认证码的定义及运用

5、方式 MAC函数与加密算法类似，不同之处为MAC函数不用是可逆的，因此与加密算法相比更不易被攻破。 上述过程中，由于音讯本身在发送过程中是明文方式，所以这一过程只提招认证性而未提供严密性。为提供严密性可在MAC函数以后(如图1(b)或以前(如图1(c)进展一次加密，而且加密密钥也需被收发双方共享。在图1(b)中，M与MAC链接后再被整体加密，在图1(c)中，M先被加密再与MAC链接后发送。通常希望直接对明文进展认证，因此图1(b)所示的运用方式更为常用。音讯认证码的定义及运用方式音讯认证码的定义及运用方式nmessage authentication code (MAC) message au

6、thentication code (MAC) n签名的电子等价方式签名的电子等价方式 n与音讯同时发送与音讯同时发送 n经过一些算法经过一些算法, , 依赖于音讯及双方共享的依赖于音讯及双方共享的n音讯可以是不恣意长音讯可以是不恣意长nMAC MAC 可以是恣意长可以是恣意长, ,但常选固定长度但常选固定长度n这需求这需求hash function hash function n“紧缩音讯成固定长度紧缩音讯成固定长度1.1.音讯认证码音讯认证码MAC的根本运用方式的根本运用方式音讯认证过程音讯认证过程 利用对称密码进展认证利用对称密码进展认证n利用对称密码加密的音讯可以作为认证内容n由于只需

7、密钥的拥有者才可以生成 n(要求音讯有一定的冗余度) n但不能处理音讯的不可否认性n无法证明谁生成的音讯 运用加密算法单钥算法或公钥算法加密音讯时，其平安性普通取决于密钥的长度。假设加密算法没有弱点，那么敌手只能运用穷搜索攻击以测试一切能够的密钥。假设密钥长为k比特，那么穷搜索攻击平均将进展2k-1个测试。特别地，对惟密文攻击来说，敌手假设知道密文C，那么将对一切能够的密钥值Ki执行解密运算Pi=DKi(C)，直到得到有意义的明文。1.2 产生产生MAC的函数应满足的要求的函数应满足的要求 对MAC来说，由于产生MAC的函数普通都为多到一映射，假设产生n比专长的MAC，那么函数的取值范围即为2

8、n个能够的MAC，函数输入的能够的音讯个数N2n，而且假设函数所用的密钥为k比特，那么能够的密钥个数为2k。 假设系统不思索严密性，即敌手能获取明文音讯和相应的MAC，那么在这种情况下要思索敌手运用穷搜索攻击来获取产生MAC的函数所运用的密钥。1.2 产生产生MAC的函数应满足的要求的函数应满足的要求 假定kn，且敌手已得到M1和MAC1，其中MAC1=CK1M1，敌手对一切能够的密钥值Ki求MACi=CKi(M1)，直到找到某个Ki使得MACi=MAC1。由于不同的密钥个数为2k，因此将产生2k个MAC，但其中仅有2n个不同，由于2k2n，所以有很多密钥平均有2k/2n=2k-n个都可产生出

9、正确的MAC1，而敌手无法知道进展通讯的两个用户用的是哪一个密钥，还必需按以下方式反复上述攻击：1.2 产生产生MAC的函数应满足的要求的函数应满足的要求 第1轮 知M1、MAC1，其中MAC1=CK(M1)。对一切2k个能够的密钥计算MACi=CKi(M1)，得2k-n个能够的密钥。 第2轮 知M2、MAC2，其中MAC2=CK(M2)。对上一轮得到的2k-n个能够的密钥计算MACi=CKi(M2)，得2k-2n个能够的密钥。 如此下去，假设k=n，那么上述攻击方式平均需求轮。例如，密钥长为80比特，MAC长为32比特，那么第1轮将产生大约248个能够密钥，第2轮将产生216个能够的密钥，第

10、3轮即可找出正确的密钥。1.2 产生产生MAC的函数应满足的要求的函数应满足的要求 假设密钥长度小于MAC的长度，那么第1轮就有能够找出正确的密钥，也有能够找出多个能够的密钥，假设是后者，那么仍需执行第2轮搜索。 所以对音讯认证码的穷搜索攻击比对运用一样长度密钥的加密算法的穷搜索攻击的代价还要大。然而有些攻击法却不需求寻觅产生MAC所运用的密钥。1.2 产生产生MAC的函数应满足的要求的函数应满足的要求例如，设M=(X1X2Xm)是由64比专长的分组Xi(i=1,m)链接得到的，其音讯认证码由以下方式得到：其中表示异或运算，加密算法是电码本方式的DES。12()()()mKKMXXXCMEM1

11、.2 产生产生MAC的函数应满足的要求的函数应满足的要求n 因此，密钥长为56比特，MAC长为64比特，假设敌手得到MCK(M)，那么敌手运用穷搜索攻击寻觅K将需做256次加密。然而敌手还可用以下方式攻击系统： 将X1到Xm-1分别用本人选取的Y1到Ym-1交换，求出Ym=Y1Y2Ym-1(M)，并用Ym交换Xm。因此敌手可胜利伪造一新音讯M=Y1Ym，且M的MAC与原音讯M的MAC一样。1.2 产生产生MAC的函数应满足的要求的函数应满足的要求 思索到MAC所存在的以上攻击类型，可知它应满足以下要求，其中假定敌手知道函数C，但不知道密钥K： 假设敌手得到M和CK(M)，那么构造一满足CK(M

12、)=CK(M)的新音讯M在计算上是不可行的。 CK(M)在以下意义下是均匀分布的： 随机选取两个音讯M、M，PrCK(M)=CK(M)=2-n，其中n为MAC的长。 假设M是M的某个变换，即M=f(M)，例如f为插入一个或多个比特，那么PrCK(M)=CK(M) = 2-n。1.2 产生产生MAC的函数应满足的要求的函数应满足的要求 第1个要求是针对上例中的攻击类型的，此要求是说敌手不需求找出密钥K而伪造一个与截获的MAC相匹配的新音讯在计算上是不可行的。 第2个要求是说敌手假设截获一个MAC，那么伪造一个相匹配的音讯的概率为最小。 最后一个要求是说函数C不应在音讯的某个部分或某些比特弱于其他

13、部分或其他比特，否那么敌手获得M和MAC后就有能够修正M中弱的部分，从而伪造出一个与原MAC相匹配的新音讯。1.2 产生产生MAC的函数应满足的要求的函数应满足的要求 数据认证算法是最为广泛运用的音讯认证码中的一个，已作为FIPS PublicationFIPS PUB 113并被ANSI作为X9.17规范。算法基于CBC方式的DES算法，其初始向量取为零向量。需被认证的数据音讯、记录、文件或程序被分为64比专长的分组D1，D2，DN，其中最后一个分组不够64比特的话，可在其右边填充一些0，然后按以下过程计算数据认证码见图2：1.3 数据认证算法数据认证算法数据认证算法数据认证算法 其中E为D

14、ES加密算法，K为密钥。 数据认证码或者取为ON或者取为ON的最左M个比特，其中16M64。112213321()()()()KKKNKNNOEDOEDOOEDOOEDO 散列函数H是一公开函数，用于将恣意长的音讯M映射为较短的、固定长度的一个值H(M)，作为认证符，称函数值H(M)为杂凑值、杂凑码或音讯摘要。杂凑码是音讯中一切比特的函数，因此提供了一种错误检测才干，即改动音讯中任何一个比特或几个比特都会使杂凑码发生改动。2.2.散列函数散列函数2.1 散列函数的定义及运用方式散列函数的定义及运用方式图3 表示散列函数用来提供音讯认证的根本运用方式，共有以下6种见142页图3： 音讯与杂凑码链

15、接后用单钥加密算法加密。由于所用密钥仅为收发双方A、B共享，因此可保证音讯确实来自A并且未被篡改。同时还由于音讯和杂凑码都被加密，这种方式还提供了严密性，见图3(a)。散列函数的运用方式散列函数的运用方式n 用单钥加密算法仅对杂凑码加密。这种方式用于不要求严密性的情况下，可减少处置负担。留意这种方式和图1(a)的MAC结果完全一样，即将EKH(M)看作一个函数，函数的输入为音讯M和密钥K，输出为固定长度，见图3(b)。散列函数的运用方式散列函数的运用方式 用公钥加密算法和发送方的钥仅加密杂凑码。和一样，这种方式提招认证性，又由于只需发送方能产生加密的杂凑码，因此这种方式还对发送方发送的音讯提供

16、了数字签字，现实上这种方式就是数字签字，见图3(c)。 音讯的杂凑值用公钥加密算法和发送方的钥加密后与音讯链接，再对链接后的结果用单钥加密算法加密，这种方式提供了严密性和数字签字，见图3(d)。散列函数的运用方式散列函数的运用方式 运用这种方式时要求通讯双方共享一个值S，A计算音讯M和值S链接在一同的杂凑值，并将此杂凑值附加到M后发往B。因B也有S，所以可重新计算杂凑值以对音讯进展认证。由于值S本身未被发送，敌手无法对截获的音讯加以篡改，也无法产生假音讯。这种方式仅提招认证，见图3(e)。 这种方式是在中音讯与杂凑值链接以后再添加单钥加密运算，从而又可提供严密性，见图3(f)。散列函数的运用方

17、式散列函数的运用方式 由于加密运算的速度较慢，代价较高，而且很多加密算法还遭到专利维护，因此在不要求严密性的情况下，方式和将比其他方式更具优势。散列函数的运用方式散列函数的运用方式 散列函数的目的是为需认证的数据产生一个“指纹。为了可以实现对数据的认证，散列函数应满足以下条件： 函数的输入可以是恣意长。 函数的输出是固定长。 知x，求H(x)较为容易，可用硬件或软件实现。2.2 2.2 散列函数应满足的条件散列函数应满足的条件n 知h，求使得H(x)=h的x在计算上是不可行的，这一性质称为函数的单向性，称H(x)为单向散列函数。n 知x，找出y(yx)使得H(y)=H(x)在计算上是不可行的。

18、假设单向散列函数满足这一性质，那么称其为弱单向散列函数。n 找出恣意两个不同的输入x、y，使得H(y)=H(x)在计算上是不可行的。2.2 散列函数应满足的条件散列函数应满足的条件 假设单向散列函数满足这一性质，那么称其为强单向散列函数。 第和第个条件给出了散列函数无碰撞性的概念，假设散列函数对不同的输入可产生一样的输出，那么称该函数具有碰撞性。2.2 2.2 散列函数应满足的条件散列函数应满足的条件 以上6个条件中，前3个是散列函数能用于音讯认证的根本要求。第4个条件即单向性那么对运用值的认证技术(见图3(e)极为重要。 假设散列函数不具有单向性，那么攻击者截获M和C=H(SM)后，求C的逆

19、SM，就可求出值S。第5个条件使得敌手无法在知某个音讯时，找到与该音讯具有一样杂凑值的另一音讯。 这一性质用于杂凑值被加密情况时(见图3(b)和图3(c)防止敌手的伪造，由于在这种情况下，敌手可读取传送的明文音讯M，因此能产生该音讯的杂凑值H(M)。2.2 2.2 散列函数应满足的条件散列函数应满足的条件 但由于敌手不知道用于加密杂凑值的密钥，他就不能够既伪造一个音讯M，又伪造这个音讯的杂凑值加密后的密文EKH(M)。 然而，假设第5个条件不成立，敌手在截获明文音讯及其加密的杂凑值后，就可按以下方式伪造音讯：首先求出截获的音讯的杂凑值，然后产生一个具有一样杂凑值的伪造音讯，最后再将伪造的音讯和

20、截获的加密的杂凑值发往通讯的接纳方。 第6个条件用于抵抗生日攻击。2.2 2.2 散列函数应满足的条件散列函数应满足的条件1. 相关问题 知一散列函数H有n个能够的输出，H(x)是一个特定的输出，假设对H随机取k个输入，那么至少有一个输入y使得H(y)=H(x)的概率为0.5时，k有多大？ 以后为表达方便，称对散列函数H寻觅上述y的攻击为第类生日攻击。2.3 生日攻击生日攻击 由于H有n个能够的输出，所以输入y产生的输出H(y)等于特定输出H(x)的概率是1/n，反过来说H(y)H(x)的概率是1-1/n。y取k个随机值而函数的k个输出中没有一个等于H(x)，其概率等于每个输出都不等于H(x)

21、的概率之积，为1-1/nk，所以y取k个随机值得到函数的k个输出中至少有一个等于H(x)的概率为1-1-1/nk。2.3 生日攻击生日攻击n 由(1+x)k1+kx，其中|x|365，那么不能够使得恣意两个数据都不一样，因此假定k365。k个数据项中恣意两个都不一样的一切取值方式数为365!365 364(3651)(365)!kk生日悖论生日悖论 即第1个数据项可从365个中任取一个，第2个数据项可在剩余的364个中任取一个，依次类推，最后一个数据项可从365-k+1个值中任取一个。假设去掉恣意两个都不一样这一限制条件，可得k个数据项中一切取值方式数为365k。所以可得365!(365, )

22、(365)! 365365!(365, )1(365, )1(365)! 365kkQkkPkQkk 生日悖论生日悖论 当k=23时，P(365,23)=0.5073，即上述问题只需23人，人数如此之少。假设k取100，那么P(365,100)=0.9999997，即获得如此大的概率。之所以称这一问题是悖论是由于当人数k给定时，得到的至少有两个人的生日一样的概率比想象的要大得多。 这是由于在k个人中思索的是恣意两个人的生日能否一样，在23个人中能够的情况数为C223=253。生日悖论生日悖论 将生日悖论推行为下述问题：知一个在1到n之间均匀分布的整数型随机变量，假设该变量的k个取值中至少有两个

23、取值一样的概率大于0.5，那么k至少多大？与上类似， ，令P(n, k)0.5，可得 。 假设取n=365，那么 。!( , )1()!knP n knkn 1.18knn1.18 36522.54k 生日悖论生日悖论3. 生日攻击 生日攻击是基于下述结论：设散列函数H有2m个能够的输出即输出长m比特，假设H的k个随机输入中至少有两个产生一样输出的概率大于0.5，那么 。 称寻觅函数H的具有一样输出的两个恣意输入的攻击方式为第类生日攻击。222mmk 生日攻击生日攻击第类生日攻击可按以下方式进展： 设用户将用图3(c)所示的方式发送音讯，即A用本人的钥对音讯的杂凑值加密，加密结果作为对音讯的签

24、字，连同明文音讯一同发往接纳者。 敌手对A发送的音讯M产生出2m/2个变形的音讯，每个变形的音讯本质上的含义与原音讯一样，同时敌手还预备一个冒充的音讯M，并对冒充的音讯产生出2m/2个变形的音讯。生日攻击生日攻击 敌手在产生的两个音讯集合中，找出杂凑值一样的一对音讯, ，由上述讨论可知敌手胜利的概率大于0.5。假设不胜利，那么重新产生一个冒充的音讯，并产生2m/2个变形，直到找到杂凑值一样的一对音讯为止。 敌手将 提交给A恳求签字，由于 与 的杂凑值一样，所以可将A对 的签字当作对 的签字，将此签字连同 一同发给意欲的接纳者。,M MMMMMMM生日攻击生日攻击 上述攻击中假设杂凑值的长为64

25、比特，那么敌手攻击胜利所需的时间复杂度为O(232)。将一个音讯变形为具有一样含义的另一音讯的方法有很多，例如对文件，敌手可在文件的单词之间插入很多“space-space-backspace字符对，然后将其中的某些字符对交换为“space-backspace-space 就得到一个变形的音讯。生日攻击生日攻击 目前运用的大多数散列函数如MD5、SHA，其构造都是迭代型的，如图4所示。其中函数的输入M被分为L个分组Y0,Y1,YL-1，每一个分组的长度为b比特，最后一个分组的长度不够的话，需对其做填充。 最后一个分组中还包括整个函数输入的长度值，这样一来，将使得敌手的攻击更为困难，即敌手假想象

26、胜利地产生冒充的音讯，就必需保证冒充音讯的杂凑值与原音讯的杂凑值一样，而且冒充音讯的长度也要与原音讯的长度相等。2.4 迭代型散列函数的普通构造迭代型散列函数的普通构造迭代型散列函数的普通构造迭代型散列函数的普通构造IV = 初始值初始值CV = 链接值链接值Yi = 第第i 个输入数据块个输入数据块f = 紧缩算法紧缩算法n = 散列码的长度散列码的长度b = 输入块的长度输入块的长度平安杂凑算法的普通构造平安杂凑算法的普通构造bY0nfbY1nfbYL-1nCVL-1fCV1nnCVLCV0=IV= initial n-bit valueCVi=f(CVi-1, Yi-1) (1 i L)

27、H(M) = CVL 算法中反复运用一紧缩函数f留意，有些书将散列函数也称为紧缩函数，在此用紧缩函数表示散列函数中的一个特定部分，f 的输入有两项，一项为哪一项上一轮第i-1轮输出的n比特值CVi-1，称为链接变量，另一项为哪一项算法在本轮第i轮的b比特输入分组Yi。f 的输出为n比特值CVi，CVi又作为下一轮的输入。迭代型散列函数的普通构造迭代型散列函数的普通构造n 算法开场时还需对链接变量指定一个初值IV，最后一轮输出的链接变量CVL即为最终产生的杂凑值。n 通常有bn，因此称函数f为紧缩函数。算法可表达如下：nCV0=IV=n比专长的初值；nCVi=f(CVi-1,Yi-1)；1iL；

28、nH(M)=CVL迭代型散列函数的普通构造迭代型散列函数的普通构造 算法的中心技术是设计无碰撞的紧缩函数f，而敌手对算法的攻击重点是f 的内部构造，由于f 和分组密码一样是由假设干轮处置过程组成，所以对f 的攻击需经过对各轮之间的位方式的分析来进展，分析过程经常需求先找出f 的碰撞。由于f 是紧缩函数，其碰撞是不可防止的，因此在设计f 时就应保证找出其碰撞在计算上是不可行的。下面引见几个重要的迭代型散列函数。迭代型散列函数的普通构造迭代型散列函数的普通构造Hash Functionsn把恣意长的音讯“紧缩成固定长的音讯的算法n数字签名时，常被运用n通常，HASH 函数是公开的 n输出长度应足够

29、大，防止生日攻击n64-bits 以为太小n通常 128-512bitsHash 函数设计原理函数设计原理nH H能用于任何大小的数据分组能用于任何大小的数据分组; ;nH H产生定长输出产生定长输出; ;n对恣意给定的对恣意给定的x, H(x)x, H(x)要相对易于计算要相对易于计算, ,使得软硬件使得软硬件实现都实践可行实现都实践可行; ;n对恣意给定的码对恣意给定的码h, h, 寻求寻求x x使得使得H(x)=hH(x)=h在计算上是不在计算上是不可行的可行的( (单向性单向性););n恣意给定分组恣意给定分组x, x, 寻求不等于寻求不等于x x的的y, y, 使得使得H(y)= H

30、(x)H(y)= H(x)在计算上不可行在计算上不可行( (弱抗攻击性弱抗攻击性););n寻求对任何的寻求对任何的(x,y)(x,y)对使得对使得H(x)=H(y)H(x)=H(y)在计算上不可在计算上不可行行( (强抗攻击性强抗攻击性););n生日攻击生日攻击( (基于生日悖论基于生日悖论) )n 在在k k个人中个人中, ,找一个与某人生日一样的人的找一个与某人生日一样的人的n概率超越概率超越0.50.5时时, ,只需只需k183; k183; 而在此人群中而在此人群中, ,n至少有两个人生日一样的概率超越至少有两个人生日一样的概率超越0.5,0.5,只需只需nk23.k23.Hash 函

31、数设计原理函数设计原理 MD4是MD5杂凑算法的前身，由Ron Rivest于1990年10月作为RFC提出，1992年4月公布的MD4的改良RFC 1320，1321称为MD5。3. MD5杂凑算法杂凑算法 MD5算法采用图4描画的迭代型散列函数的普通构造，算法的框图如图5所示。算法的输入为恣意长的音讯图中为K比特，分为512比专长的分组，输出为128比特的音讯摘要。3.1 算法描画算法描画MD5的算法框图的算法框图报文K bitsL512 bits=N 32bits报文长度报文长度(K mod 264)1000Y0512 bitsY1512 bitsYq512 bitsYL-1512 bi

32、tsHMD5IV128HMD5CV1128HMD5CVq128HMD5CVL-1128512填充填充(1 to 512 bits)512512512128-bit 摘要摘要MD5产生报文摘要的过程产生报文摘要的过程处置过程有以下几步： 对音讯填充对音讯填充，使得其比专长在模512下为448，即填充后音讯的长度为512的某一倍数减64，留出的64比特备第2步运用。 步骤是必需的，即使音讯长度已满足要求，仍需填充。例如，音讯长为448比特，那么需填充512比特，使其长度变为960，因此填充的比特数大于等于1而小于等于512。 填充方式是固定的，即第1位为1，其后各位皆为0。MD5算法描画算法描画

33、附加音讯的长度用步骤留出的64比特以little-endian方式来表示音讯被填充前的长度。假设音讯长度大于264，那么以264为模数取模。Little-endian方式是指按数据的最低有效字节byte或最低有效位优先的顺序存储数据，即将最低有效字节或最低有效位存于低地址字节或位。相反的存储方式称为big-endian方式。MD5算法描画算法描画 前两步执行完后，音讯的长度为512的倍数设为L倍，那么可将音讯表示为分组长为512的一系列分组Y0，Y1，YL-1，而每一分组又可表示为16个32比专长的字，这样音讯中的总字数为N=L16，因此音讯又可按字表示为M0,N-1。MD5算法描画算法描画

34、对MD缓冲区初始化算法运用128比专长的缓冲区以存储中间结果和最终杂凑值，缓冲区可表示为4个32比专长的存放器A，B，C，D，每个存放器都以littleendian方式存储数据，其初值取为以存储方式A=01234567，B=89ABCDEF， C=FEDCBA98，D=76543210，实践上为67452301，EFCDAB89， 98BADCFE，10325476。MD5算法描画算法描画n ：处置音讯块512位 = 16个32位字。一个紧缩函数是本算法的中心(HMD5)。它包括4轮处置。四轮处置具有类似的构造,但每次运用不同的根本逻辑函数，记为F,G,H,I。每一轮以当前的512位数据块(Y

35、q)和128位缓冲值ABCD作为输入，并修正缓冲值的内容。每次运用64元素表T164中的四分之一MD5算法描画算法描画n T表，由sin 函数构造而成。T的第i个元素表示为Ti，其值等于 232abs(sin(i),其中i是弧度。由于abs(sin(i)是一个0到1之间的数，T的每一个元素是一个可以表示成32位的整数。T表提供了随机化的32位模板，消除了在输入数据中的任何规律性的特征MD5算法描画算法描画T 表表T49 = F4292244T50 = 432AFF97T51 = AB9423A7T52 = FC93A039T64 = EB86D391T1 = D76AA478T2 = E8C7

36、B756T3 = 242070DBT4 = C1BDCEEET16 = 49b40821n 输出音讯的L个分组都被处置完后，最后一个HMD5的输出即为产生的音讯摘要。MD5算法描画算法描画n步骤步骤5：输出结果。一切：输出结果。一切L个个512位数据块处置终了后，位数据块处置终了后，最后的结果就是最后的结果就是128位音讯摘要。位音讯摘要。n CV0 = IVn CVq+1 = SUM32(CVq,RFIYq,RFHYq,RFGYq,RFFYq,CVq)n MD = CVLn 其中：其中：IV = ABCD的初始值见步骤的初始值见步骤3n Yq = 音讯的第音讯的第q个个512位数据块位数据块

37、n L = 音讯中数据块数；音讯中数据块数；n CVq = 链接变量，用于第链接变量，用于第q个数据块的处置个数据块的处置n RFx = 运用根本逻辑函数运用根本逻辑函数x的一轮功能函数。的一轮功能函数。n MD = 最终音讯摘要结果最终音讯摘要结果n SUM32=分别按分别按32位字计算的模位字计算的模232加法结果加法结果。MD5算法描画算法描画MD5的分组处置框图的分组处置框图F,T116,Xi16 stepsG,T1732,X2i16 stepsH,T3348,X3i16 stepsI,T4964,X4i16 steps+ABCDABCDABCDABCDCVq12832Yq512CVq

38、+1128+ is mod 232单个单个 512-bit 分组的分组的MD5 处置过程处置过程 HMD5的4轮处置过程构造一样，但所用的逻辑函数不同，分别表示为F、G、H、I。每轮的输入为当前处置的音讯分组Yq和缓冲区的当前值A、B、C、D，输出仍放在缓冲区中以产生新的A、B、C、D。每轮处置过程还需加上常数表T中四分之一个元素，分别为T116, T1732, T3348, T4964。表T有64个元素，见表6.1，第i个元素Ti为232abs(sin(i)的整数部分，其中sin为正弦函数，i以弧度为单位。MD5算法描画算法描画n 由于abs(sin(i)大于0小于1，所以Ti可由32比特的

39、字表示。第4轮的输出再与第1轮的输入CVq相加，相加时将CVq看作4个32比特的字，每个字与第4轮输出的对应的字按模232相加，相加的结果即为紧缩函数HMD5的输出。见151页表6.1MD5算法描画算法描画步骤到步骤的处置过程可总结如下：CV0=IV;CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVqMD=CVL 其中IV是步骤所取的缓冲区ABCD的初值，Yq是音讯的第q个512比专长的分组，L是音讯经过步骤和步骤处置后的分组数，CVq为处置音讯的第q个分组时输入的链接变量即前一个紧缩函数的输出，RFx为运用根本逻辑函数x的轮函数，+为对应字的模232加法，MD为最终的

40、杂凑值。MD5算法描画算法描画 紧缩函数HMD5中有4轮处置过程，每轮又对缓冲区ABCD进展16步迭代运算，每一步的运算方式为见图7 ab+CLSs(a+g(b,c,d)+Xk+TI)其中a、b、c、d为缓冲区的4个字，运算完成后再右循环一个字，即得这一步迭代的输出。g是根本逻辑函数F、G 、H、I之一。CLSs是左循环移s位，s的取值由表6.2给出。见152页表6.23.2 MD5的紧缩函数的紧缩函数2i = (1+5i) mod 163i = (5+3i) mod 162i = 7i mod 16根本根本MD5操作操作(单步单步)ABCDABCD+CLSs+gXkTiFunction g

41、g(b,c,d)1 F(b,c,d) (bc)(bd)2 G(b,c,d) (bd)(cd)3 H(b,c,d) bcd4 I(b,c,d) c(bd)紧缩函数中的一步迭代表示图紧缩函数中的一步迭代表示图 Ti为表T中的第i个字，+为模232加法。Xk=Mq16+k，即音讯第q个分组中的第k个字k=1,16。 4轮处置过程中，每轮以不同的次序运用16个字，其中在第1轮以字的初始次序运用。第2轮到第4轮分别对字的次序i做置换后得到一个新次序，然后以新次序运用16个字。3个置换分别为2(i)=(1+5i) mod 163(i)=(5+3i) mod 164(i)=7i mod 16紧缩函数中的一步

42、迭代紧缩函数中的一步迭代 4轮处置过程分别运用不同的根本逻辑函数F、G、H、I，每个逻辑函数的输入为3个32比特的字，输出是一个32比特的字，其中的运算为逐比特的逻辑运算，即输出的第n个比特是3个输入的第n个比特的函数，函数的定义由表6.3给出，其中，-，分别是逻辑与、逻辑或、逻辑非和异或运算，表6.4是四个函数的真值表。见153页表6.3和6.43.2 MD5的紧缩函数的紧缩函数MD4 (1990年年10月作为月作为RFC1320发表发表) by Ron Rivest at MITnMD4的设计目的的设计目的n平安性：平安性：n速度：速度：32位体系构造下计算速度快位体系构造下计算速度快.n

43、简明与紧凑：易于编程简明与紧凑：易于编程.n有利的小数在前的构造有利的小数在前的构造(Intel 80 xxx, Pentium )nMD4与与MD5的区别的区别nMD4用用3轮轮,每轮每轮16 步步,MD5用用4轮轮,每轮每轮16步步.nMD4中第一轮没有常量加；中第一轮没有常量加；MD5中中64步每一步用了一个步每一步用了一个不同的常量不同的常量 Ti；nMD5用了四个根本逻辑函数，每轮一个；用了四个根本逻辑函数，每轮一个；MD4用了三个用了三个.nMD5每轮加上前一步的结果；每轮加上前一步的结果；MD4没有没有. MD5有这样一个性质，即杂凑码中的每一个比特是一切输入比特的函数，因此获得

44、了很好的混淆效果，从而使得不能够随机选择两个具有一样杂凑值的音讯。 Rivest猜测作为128比专长的杂凑值来说，MD5的强度到达了最大，比如说找出具有一样杂凑值的两个音讯需执行O(264)次运算，而寻觅具有给定杂凑值的一个音讯需求执行O(2128)次运算。3.3 MD5的平安性的平安性目前对MD5的攻击已获得以下结果： 对单轮MD5运用差分密码分析，可在合理的时间内找出具有一样杂凑值的两个音讯。但这种攻击还未能胜利地推行到4轮MD5。 可找出一个音讯分组和两个相关的链接变量即缓冲区变量ABCD，使得算法产生出一样的输出。目前这种攻击还未能胜利地推行到整个算法。3.3 MD5的平安性的平安性n

45、 对单个512比专长的音讯分组已胜利地找出了碰撞，即可找出另一个音讯分组，使得算法对两个音讯分组的128比专长的输出一样。目前这种攻击还未胜利推行到在有初值IV时对整个音讯运转该算法。3.3 MD5的平安性的平安性 因此从密码分析的角度来看，MD5被以为是易受攻击的。 而从穷搜索的角度来看，第类生日攻击需进展O(264)次运算，因此以为MD5易受第类生日攻击的要挟。 所以必需寻觅新的杂凑算法，以使其产生的杂凑值更长，且抵抗知密码分析攻击的才干更强。下面要引见的SHA即为这样的一个算法。3.3 MD5的平安性的平安性 平安杂凑算法(secure hash algorithm, SHA)由美国NI

46、ST设计，于1993年作为联邦信息处置规范FIPS PUB 180公布。SHA是基于MD4的算法，其构造与MD4非常类似。4. 平安杂凑算法平安杂凑算法(SHA) 算法的输入为小于264比专长的恣意音讯，分为512比专长的分组，输出为160比专长的音讯摘要。算法的框图与图5一样，但杂凑值的长度和链接变量的长度为160比特。4.1 算法描画算法描画算法的处置过程有以下几步： 对音讯填充与MD5的步骤完全一样。 附加音讯的长度与MD5的步骤类似，不同之处在于以big-endian方式表示填充前音讯的长度。即步骤留出的64比特当作64比专长的无符号整数。SHA算法描画算法描画n 对MD缓冲区初始化算

47、法运用160比专长的缓冲区存储中间结果和最终杂凑值，缓冲区可表示为5个32比专长的存放器(A, B, C, D, E)，每个存放器都以big-endian方式存储数据，其初始值分别为nA=67452301，B=EFCDAB89，C=98BADCFB，D=10325476，E=C3D2E1F0。SHA算法描画算法描画 以分组为单位对音讯进展处置每一分组Yq都经一紧缩函数处置，紧缩函数由4轮处置过程如图8所示构成，每一轮又由20步迭代组成。4轮处置过程构造一样，但所用的根本逻辑函数不同，分别表示为f1,f2,f3,f4。SHA算法描画算法描画n 每轮的输入为当前处置的音讯分组Yq和缓冲区的当前值A

48、,B,C,D,E，输出仍放在缓冲区以替代A,B,C,D,E的旧值，每轮处置过程还需加上一个加法常量Kt，其中0t79表示迭代的步数。80个常量中实践上只需4个不同取值，如表6.5所示，其中 为x的整数部分。见155页表6.5x SHA算法描画算法描画SHA的分组处置框图的分组处置框图 第4轮的输出即第80步迭代的输出再与第1轮的输入CVq相加，以产生CVq+1，其中加法是缓冲区5个字中的每一个字与CVq中相应的字模232相加。 输出音讯的L个分组都被处置完后，最后一个分组的输出即为160比特的音讯摘要。SHA算法描画算法描画步骤到步骤的处置过程可总结如下：CV0=IV;CVq+1=SUM32(

49、CVq,ABCDEq);MD=CVL 其中IV是步骤定义的缓冲区ABCDE的初值，ABCDEq是第q个音讯分组经最后一轮处置过程处置后的输出，L是音讯包括填充位和长度字段的分组数，SUM32是对应字的模232加法，MD为最终的摘要值。SHA算法描画算法描画 如上所述，SHA的紧缩函数由4轮处置过程组成，每轮处置过程又由对缓冲区ABCDE的20步迭代运算组成，每一步迭代运算的方式为见图9 其中A，B，C，D，E为缓冲区的5个字，t是迭代的步数0t79，ft(B,C,D)是第t步迭代运用的根本逻辑函数，CLSs为左循环移s位，Wt是由当前512比专长的分组导出的一个32比专长的字导出方式见下面，K

50、t是加法常量，+是模232加法。4.2 SHA的紧缩函数的紧缩函数530, ,( ,)( ),( ),tttA B C D EEf B C DCLSAWKA CLSBC DSHA的紧缩函数中一步迭代表示图的紧缩函数中一步迭代表示图 根本逻辑函数的输入为3个32比特的字，输出是一个32比特的字，其中的运算为逐比特逻辑运算，即输出的第n个比特是3个输入的相应比特的函数。函数的定义如表6.6。表中, ,分别是与、或、非、异或4个逻辑运算，函数的真值表如表6.7所示。见156页表6.6，157页表6.7SHA的紧缩函数中一步迭代的紧缩函数中一步迭代 下面阐明如何由当前的输入分组512比专长导出Wt32

51、比专长。前16个值即W0,W1,W15直接取为输入分组的16个相应的字，其他值即W16,W17,W79取为 见图10。与MD5比较，MD5直接用一个音讯分组的16个字作为每步迭代的输入，而SHA那么将输入分组的16个字扩展成80个字以供紧缩函数运用，从而使得寻觅具有一样紧缩值的不同的音讯分组更为困难。1161483()tttttWCLS WWWWSHA的紧缩函数中一步迭代的紧缩函数中一步迭代SHA分组处置所需的分组处置所需的80个字的产生过程个字的产生过程 由于SHA与MD5都是由MD4演化而来，所以两个算法极为类似。1. 抗穷搜索攻击的强度 由于SHA和MD5的音讯摘要长度分别为160和12

52、8，所以用穷搜索攻击寻觅具有给定音讯摘要的音讯分别需做O(2160)和O(2128)次运算，而用穷搜索攻击找出具有一样音讯摘要的两个不同音讯分别需做O(280)和O(264)次运算。因此SHA抗击穷搜索攻击的强度高于MD5抗击穷搜索攻击的强度。4.3 SHA与与MD5的比较的比较2. 抗击密码分析攻击的强度由于SHA的设计准那么未被公开，所以它抗击密码分析攻击的强度较难判别，似乎高于MD5的强度。SHA与与MD5的比较的比较n3. 速度速度n 由于两个算法的主要运算都是模由于两个算法的主要运算都是模232加加法，因此都易于在法，因此都易于在32位构造上实现。但比位构造上实现。但比较起来较起来,

53、SHA的迭代步数的迭代步数(80步步)多于多于MD5的的迭代步数迭代步数64步，所用的缓冲区步，所用的缓冲区160比特大于比特大于MD5运用的缓冲区运用的缓冲区128比比特，因此在一样硬件上实现时，特，因此在一样硬件上实现时，SHA的的速度要比速度要比MD5的速度慢。的速度慢。SHA与与MD5的比较的比较4. 简约与紧致性简约与紧致性 两个算法描画起来都较为简单，实现起两个算法描画起来都较为简单，实现起来也较为简单，都不需求大的程序和代换表。来也较为简单，都不需求大的程序和代换表。5. 数据的存储方式数据的存储方式 MD5运用运用little-endian方式，方式，SHA运用运用big-en

54、dian方式。两种方式相比看不出哪个方式。两种方式相比看不出哪个更具优势，之所以运用两种不同的存储方式更具优势，之所以运用两种不同的存储方式是由于设计者最初实现各自的算法时，运用是由于设计者最初实现各自的算法时，运用的机器的存储方式不同。的机器的存储方式不同。SHA与与MD5的比较的比较 以前曾引见过一个MAC的例子数据认证算法，该算法反映了传统上构造MAC最为普遍运用的方法，即基于分组密码的构造方法。但近年来研讨构造MAC的兴趣已转移到基于密码散列函数的构造方法，这是由于： 密码散列函数(如MD5、SHA)的软件实现快于分组密码(如DES)的软件实现；密码散列函数的库代码来源广泛； 密码散列

55、函数没有出口限制，而分组密码即使用于MAC也有出口限制。5. HMAC算法算法 散列函数并不是为用于MAC而设计的，由于散列函数不运用密钥，因此不能直接用于MAC。 目前已提出了很多将散列函数用于构造MAC的方法，其中HMAC就是其中之一，已作为RFC2104被公布，并在IPSec和其他网络协议(如SSL)中得以运用。 RFC2104列举了HMAC的以下设计目的： 可不经修正而运用现有的散列函数，特别是那些易于软件实现的、源代码可方便获取且免费运用的散列函数。 其中镶嵌的散列函数可易于交换为更快或更平安的散列函数。5.1 HMAC的设计目的的设计目的 坚持镶嵌的散列函数的最初性能，不因用于HM

56、AC而使其性能降低。 以简一方式运用和处置密钥。 在对镶嵌的散列函数合理假设的根底上，易于分析HMAC用于认证时的密码强度。HMAC的设计目的的设计目的 其中前两个目的是HMAC被公众普遍接受的主要缘由，这两个目的是将散列函数当作一个黑盒运用，这种方式有两个优点: 第一，散列函数的实现可作为实现HMAC的一个模块，这样一来，HMAC代码中很大一块就可事先预备好，无需修正就可运用； 第二，假设HMAC要求运用更快或更平安的散列函数，那么只需用新模块替代旧模块，例如用实现SHA的模块替代MD5的模块。HMAC的设计目的的设计目的 最后一条设计目的那么是HMAC优于其他基于散列函数的MAC的一个主要

57、方面，HMAC在其镶嵌的散列函数具有合理密码强度的假设下，可证明是平安的。HMAC的设计目的的设计目的 图11是HMAC算法的运转框图，其中H为嵌入的散列函数(如MD5、SHA)，M为HMAC的输入音讯(包括散列函数所要求的填充位)，Yi(0iL-1)是M的第i个分组，L是M的分组数，b是一个分组中的比特数，n为由嵌入的散列函数所产生的杂凑值的长度，K为密钥，假设密钥长度大于b，那么将密钥输入到散列函数中产生一个n比专长的密钥，K+是左边经填充0后的K，K+的长度为b比特，ipad为b/8个00110110，opad为b/8个01011010。5.2 HMAC算法描画算法描画HMAC的算法框图

58、的算法框图算法的输出可如下表示:()|()|kHMACH KopadH KipadMHMAC算法描画算法描画算法的运转过程可描画如下： K的左边填充0以产生一个b比专长的K+ 例如K的长为160比特，b=512，那么需填充44个零字节0 x00。 K+与ipad 逐比特异或以产生b比特的分组Si。 将M链接到Si后。HMAC算法描画算法描画n 将H作用于步骤产生的数据流。n K+与opad逐比特异或,以产生b比专长的分组S0。n 将步骤得到的杂凑值链接在S0后。n 将H作用于步骤产生的数据流并输出最终结果。HMAC算法描画算法描画 留意，K+与ipad逐比特异或以及K+与opad逐比特异或的结果是将K中的一半比特取反，但两次取反的比特的位置不同。而Si和S0经过散列函数中紧缩函数的处置，那么相当于以伪随机方式从K产生两个密钥。HMAC算法描画算法描画