Hash函数分解课件

1、 第七章 杂 凑 函 数第1页，共38页。杂凑函数(Hash函数）杂凑函数是密码学的一个基本工具，在数字签名、身份认证和消息的完整性检测等方面有着重要的应用杂凑函数H是一公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值H(M)，作为认证符，称函数值H(M)为杂凑值、杂凑码或消息摘要。杂凑码是消息中所有比特的函数，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个比特都会使杂凑码发生改变。特点：H 打上了输入数字串的烙印，为数字指纹(Digital Finger Print)第2页，共38页。散列函数的性质 （1）一般杂凑函数h(m)算法公开，不需要密钥 （2）具有数据压缩功

2、能，可将任意长度的输入数据转换成一个固定长度的输出。 （3）对任何给定的m，h(m)易于计算。第3页，共38页。Hash函数的应用 在密码学和数据安全技术中，它是实现有效、安全可靠数字签字和认证的重要工具，是安全认证协议中的重要模块。第4页，共38页。Hash函数的应用注：实际应用中，未必一定是如h(mk)的计算方式，明文与密钥k的组合方式因不同的实现可以不同。 第5页，共38页。单向杂凑函数要求密码学中所用的杂凑函数必须满足一定安全性的要求，要能防伪造，抗击各种类型的攻击，如生日攻击、中途相遇攻击等等。安全要求：（1）具有单向性。给定消息的散列值h(m)，要得到消息m在计算上不可行；（2）具

3、有弱抗碰撞性（Weak collision resistance）。对任何给定的消息m，寻找与m不同的消息m，使得它们的散列值相同，即h(m)h (m)，在计算上不可行。 （3）具有强抗碰撞性（Strong collision resistance) 。寻找任意两个不同的消息m和m， 使得h(m)h (m) 在计算上不可行。第6页，共38页。H是多对一映射杂凑函数是多对一映射，所以必然存在碰撞outputhHMMH第7页，共38页。Hash函数的无碰撞性弱单向杂凑，是在给定M下，考察与特定M的无碰撞性；而强单向杂凑函数是考察输入集中任意两个元素的无碰撞性。显然，对于给定的输入数字串的集合，后一

4、种碰撞要容易实现。因为从下面要介绍的生日悖论知，在N个元素的集中，给定M找与M相匹配的M的概率要比从N中任取一对元素M，M相匹配的概率小得多。第8页，共38页。单向杂凑函数安全性要求 杂凑函数的安全性取决于其抗击各种攻击的能力，对手的目标是找到两个不同消息映射为同一杂凑值。一般假定对手知道杂凑算法，采用选择明文攻击法 对杂凑函数的基本攻击方法：（1）穷举攻击（或暴力攻击）：不涉及杂凑算法的结构，能对任何类型的散列函数进行攻击。其中最典型方法是“生日攻击”：给定初值H0，寻找MM，使h(H0, M)=h(H0, M)。（2）密码分析法，这类攻击方法依赖于对散列函数的结构和代数性质分析，采用针对散

5、列函数弱性质的方法进行攻击。这类攻击方法有中间相遇攻击、修正分组攻击和差分分析等等。第9页，共38页。生日攻击1生日悖论：在一个会场参加会议的人中，找一个与某人生日相同的概率超过0.5时，所需参会人员为183人。但要问使参会人员中至少有两个同日生的概率超过0.5的参会人数仅为23人。这是因为，对于与某个已知生日的人同日生的概率为1/365，若房中有t人，则至少找到一人与此人同日生的概率为多少。易于解出，当t183时可使p0.5。第一个人在特定日生的概率为1/365，而第二人不在该日生的概率为(1-1/365)，类似地第三人与前两位不同日生的概率为(1-2/365)，以此类推，t个人都不同时生日

6、概率为Pt=(1-1/365)(1-2/365)(1-(t-1)/365)，因此，至少有两人于同日生的概率为1-Pt. 解之，当t23时，p0.5。第10页，共38页。对散列函数的生日攻击 与散列函数相关的类似问题可表述如下：给定一个散列函数h的输出长度为n位，共有2n个可能的散列值输出，找x和y满足H(x)=H(y)，则尝试多少个报文可以找到一对（假设散列值n比特）显然，最多尝试2n1个报文，必有一对冲突其实，远在到达2n1之前，很可能早就找到了(期望2n-1)如果只要达到一定的概率(如1/2)，约需尝试多少个不同报文？答案：2n/2第11页，共38页。杂凑函数的构造(Merkle-Damg

7、ard)迭代型散列函数的一般结构：算法中重复使用某个函数f 。函数f的输入有两项，一项是上一轮（第i-1轮）的输出CVi-1，称为链接变量，另一项是算法在本轮（第i轮）b位的输入分组mi。整个散列函数的逻辑关系可表示为： CV0 =IV； CVi = f（CVi-1，mi）；1it； h（M）= CVt第12页，共38页。直接设计散列函数MD5、SHA1是当前国际通行的两大密码标准。MD5由国际著名密码学家图灵奖获得者兼公钥加密算法RSA的创始人Rivest设计，SHA1是由美国专门制定密码算法的标准机构美国国家标准技术研究院（NIST）与美国国家安全局（NSA）设计。两大算法是目前国际电子签

8、名及许多其它密码应用领域的关键技术，广泛应用于金融、证券等电子商务领域。其中，SHA1早在1994年便为美国政府采纳，目前是美国政府广泛应用的计算机密码系统。第13页，共38页。1990MD419911992MD51993SHA019941995SHA119961997199819992000200120022003SHA-256,384,512200420052006MD4 is brokentheoretical attack on SHA0MD5, SHA0 broken, theoretical attack on SHA1直接设计散列函数第14页，共38页。MD系列MIT 一系列杂凑

9、算法 (Ronal Rivest 设计) /rivest/Message Digest (MD)MD2 (RFC 1319) MD4 (RFC 1320) MD5 (RFC 1321) 应用曾经是最广泛的摘要算法但是摘要太短(128bits)而SHA有160bits第15页，共38页。MD5特性：输入：任意长度的消息 输出：128位消息摘要 处理：以512位输入数据块为单位步骤1(填充消息): 使得消息的长度（bit为单位）模512为448。如果数据长度正好是模512为448，增加512个填充bit，也就是说填充的个数为1-512。 填充方法：第一个bit为1，其余全部为0。步骤2(补足长度)

10、: 将数据长度转换为64bit的数值，如果长度超过64bit所能表示的数据长度的范围，值保留最后64bit，增加到前面填充的数据后面，使得最后的数据为512bit的整数倍。然后对每个512bit按每组32bit进行分组,可分为16组。 512=32*16第16页，共38页。报文K bitsL512 bits=N 32bits报文长度(K mod 264)1000Y0512 bitsY1512 bitsYq512 bitsYL-1512 bitsHMD5IV128HMD5CV1128HMD5CVq128HMD5CVL-1128512512512512128-bit 摘要MD5产生报文摘要的过程填

11、充(1 to 512 bits)第17页，共38页。MD5算法实例例7-1 对字符串”abc”，运用MD5求散列值解: 首先”abc”二进制表示为：01100001 01100010 01100011，共24位长度MD5算法：第一步：按照MD5要求，填充数据: 5126424424（填充1位“1”，423位“0”，及 1000000)512位的输入数据为(十六进制表示 ）：61626380 00000000 , 00000018而 W0= 61626380, W1=W2=W14=00000000, W15=00000018第18页，共38页。MD5算法步骤三：初始化变量 用到4个变量，分别为A

12、、B、C、D，均为32bit长。初始化为： A= 01 23 45 67 B=89 ab cd ef C=fe dc ba 98 D=76 54 32 10 第19页，共38页。MD5算法第四步：数据处理，共进行四轮。设对512bit按每组32bit进行分组为M0,M1, M15。第一轮的辅助函数： F(X,Y,Z) = (X Y) (X Z )X Y表示按位与，X Y表示按位或， X表示按位取反。第一轮的操作：FF(a,b,c,d, Mj,s, ti)表示为： a=b+(a+(F(b,c,d)+Mj+ti)s) 其中： Mj表示第j个分组， s表示循环左移s位 ti 是给定的常数， ti=0

13、 x(int(232*sin(i).第20页，共38页。a = b + (a + g(b, c, d) + Mk + Ti) s) b = b c = c d = d 然后交换：A=dB=aC=bD=cMD5 压缩函数第21页，共38页。MD5算法-计算t1计算t1x=sin(1)=0.8414709848078965066525023216303y=232=4294967296z=x*y=232*sin(1)=3614090360.2828283386251439079649int(z)=3614090360=oxD76AA478第22页，共38页。MD5算法第一轮循环 FF (a, b,

14、c, d, M 0, 7, 0 xd76aa478); /* 1 */ FF (d, a, b, c, M 1, 12, 0 xe8c7b756); /* 2 */ FF (c, d, a, b, M 2, 17, 0 x242070db); /* 3 */ FF (b, c, d, a, M 3, 22, 0 xc1bdceee); /* 4 */ FF (a, b, c, d, M 4, 7, 0 xf57c0faf); /* 5 */ FF (d, a, b, c, M 5, 12, 0 x4787c62a); /* 6 */ FF (c, d, a, b, M 6, 17, 0 xa8

15、304613); /* 7 */ FF (b, c, d, a, M 7, 22, 0 xfd469501); /* 8 */ FF (a, b, c, d, M 8, 7, 0 x698098d8); /* 9 */ FF (d, a, b, c, M 9, 12, 0 x8b44f7af); /* 10 */ FF (c, d, a, b, M10, 17, 0 xffff5bb1); /* 11 */ FF (b, c, d, a, M11, 22, 0 x895cd7be); /* 12 */ FF (a, b, c, d, M12, 7, 0 x6b901122); /* 13 */

16、 FF (d, a, b, c, M13, 12, 0 xfd987193); /* 14 */ FF (c, d, a, b, M14, 17, 0 xa679438e); /* 15 */ FF (b, c, d, a, M15, 22, 0 x49b40821); /* 16 */ 第23页，共38页。MD5算法第二、三、四轮第二、三、四轮与第一轮非常相似。第二轮的辅助函数： G(X,Y,Z) = (X Z) (Y Z) 第三轮的辅助函数： H(X,Y,Z) = X Y Z 第四轮的辅助函数： I(X,Y,Z) = Y (X Z) 第二轮的操作：GG(a,b,c,d, Mj,s, ti)

17、表示： a=b+(a+(G(b,c,d)+Mj+ti)s) 第三轮的操作HH(a,b,c,d, Mj,s, ti)表示： a=b+(a+(H(b,c,d)+Mj+ti)s) 第四轮的操作II(a,b,c,d, Mj,s, ti)表示： a=b+(a+(I(b,c,d)+Mj+ti)s) 第24页，共38页。 GG (a, b, c, d, M 1, 5, 0 xf61e2562); /* 17 */ GG (d, a, b, c, M 6, 9, 0 xc040b340); /* 18 */ GG (c, d, a, b, M11, 14, 0 x265e5a51); /* 19 */ GG

18、(b, c, d, a, M 0, 20, 0 xe9b6c7aa); /* 20 */ GG (a, b, c, d, M 5, 5, 0 xd62f105d); /* 21 */ GG (d, a, b, c, M10, 9, 0 x2441453); /* 22 */ GG (c, d, a, b, M15, 14, 0 xd8a1e681); /* 23 */ GG (b, c, d, a, M 4, 20, 0 xe7d3fbc8); /* 24 */ GG (a, b, c, d, M 9, 5, 0 x21e1cde6); /* 25 */ GG (d, a, b, c, M14

19、, 9, 0 xc33707d6); /* 26 */ GG (c, d, a, b, M 3, 14, 0 xf4d50d87); /* 27 */ GG (b, c, d, a, M 8, 20, 0 x455a14ed); /* 28 */ GG (a, b, c, d, M13, 5, 0 xa9e3e905); /* 29 */ GG (d, a, b, c, M 2, 9, 0 xfcefa3f8); /* 30 */ GG (c, d, a, b, M 7, 14, 0 x676f02d9); /* 31 */ GG (b, c, d, a, M12, 20, 0 x8d2a4c

20、8a); /* 32 */ /* 第二轮循环 */ 第25页，共38页。 HH (a, b, c, d, M 5, 4, 0 xfffa3942); /* 33 */ HH (d, a, b, c, M 8, 11, 0 x8771f681); /* 34 */ HH (c, d, a, b, M11, 16, 0 x6d9d6122); /* 35 */ HH (b, c, d, a, M14, 23, 0 xfde5380c); /* 36 */ HH (a, b, c, d, M 1, 4, 0 xa4beea44); /* 37 */ HH (d, a, b, c, M 4, 11,

21、0 x4bdecfa9); /* 38 */ HH (c, d, a, b, M 7, 16, 0 xf6bb4b60); /* 39 */ HH (b, c, d, a, M10, 23, 0 xbebfbc70); /* 40 */ HH (a, b, c, d, M13, 4, 0 x289b7ec6); /* 41 */ HH (d, a, b, c, M 0, 11, 0 xeaa127fa); /* 42 */ HH (c, d, a, b, M 3, 16, 0 xd4ef3085); /* 43 */ HH (b, c, d, a, M 6, 23, 0 x4881d05);

22、/* 44 */ HH (a, b, c, d, M 9, 4, 0 xd9d4d039); /* 45 */ HH (d, a, b, c, M12, 11, 0 xe6db99e5); /* 46 */ HH (c, d, a, b, M15, 16, 0 x1fa27cf8); /* 47 */ HH (b, c, d, a, M 2, 23, 0 xc4ac5665); /* 48 */ /* 第三轮循环 */ 第26页，共38页。 II (a, b, c, d, M 0, 6, 0 xf4292244); /* 49 */ II (d, a, b, c, M 7, 10, 0 x43

23、2aff97); /* 50 */ II (c, d, a, b, M14, 15, 0 xab9423a7); /* 51 */ II (b, c, d, a, M 5, 21, 0 xfc93a039); /* 52 */ II (a, b, c, d, M12, 6, 0 x655b59c3); /* 53 */ II (d, a, b, c, M 3, 10, 0 x8f0ccc92); /* 54 */ II (c, d, a, b, M10, 15, 0 xffeff47d); /* 55 */ II (b, c, d, a, M 1, 21, 0 x85845dd1); /* 5

24、6 */ II (a, b, c, d, M 8, 6, 0 x6fa87e4f); /* 57 */ II (d, a, b, c, M15, 10, 0 xfe2ce6e0); /* 58 */ II (c, d, a, b, M 6, 15, 0 xa3014314); /* 59 */ II (b, c, d, a, M13, 21, 0 x4e0811a1); /* 60 */ II (a, b, c, d, M 4, 6, 0 xf7537e82); /* 61 */ II (d, a, b, c, M11, 10, 0 xbd3af235); /* 62 */ II (c, d,

25、 a, b, M 2, 15, 0 x2ad7d2bb); /* 63 */ II (b, c, d, a, M 9, 21, 0 xeb86d391); /* 64 */ /* 第四轮循环 */ 第27页，共38页。MD5算法做完四轮操作后，执行：a = A ab = B bc = C cd = D d如果还有下一个512分组，则对其进行从第一轮开始的操作。如果所有512分组操作完毕，输出：a b cd, 此即为所给消息的md5值,即所谓的消息摘要。第28页，共38页。处理程序非线性函数：sun(x) 的整数部分Ti = 232 *(abs(sin(i)，i 為弧度。MD5算法第29页，共3

26、8页。SHA1: Secure Hash Algorithm-1SHA-1是数字签名标准DSS（Digtial Signature Standard）中使用的散列算法。基于MD4 所以类似MD5输入 任意报文(264)输出 160bitsSHA-1，SHA-256，SHA-384，SHA-512 SHA-1，SHA-256的分组大小是512 SHA-384，SHA-512的分组大小是1024 SHA-1输出的摘要是160bit SHA-256输出的摘要是256 SHA-384输出的摘要是384 SHA-512输出的摘要是512第30页，共38页。SHA5算法第一、二步第一步：填充消息 使得消息

27、的长度（bit为单位）模512为448。如果数据长度正好是模512为448，增加512个填充bit，也就是说填充的个数为1-512。填充方法：第一个bit为1，其余全部为0。 计算公式 补零的个数d=(447|x|) mod 512(l=|x|表示消息长度）X|1|0d|l第二步：补足长度 将数据长度转换为64bit的数值 然后对每个512bit按每组32bit进行分组,可分为16组。512=32*16第31页，共38页。SHA1 算法原理 分段运算：512 bits 杂凑值长度：160 bits 初始向量：160 bitsSHA1消息摘要第32页，共38页。处理程序：4 回合，共计 80 次

28、；5 个缓存器 A = E + f1-4(t,B, C, D) + S5(A) + Wt + K1-4 B = A C = S30(B) D = C E = D其中 f1-4(t,B, C, D)=步t的基本逻辑函数Sk =循环左移k位Wt=一个从当前512位输入 数据块导出的32位字K1-4一个用于加法的常量， 四个不同值+=模 232加SHA-1 压缩函数第33页，共38页。SHA1 的IV初值用到5个变量，分别为A、B、C、D，E均为32bit长。初始化为： 暂存器初始值 A：67 45 23 01 B：EF CD AB 89 C：98 BA DC FE D：10 32 54 76 E ：C3 D2 E1 F0 第34页，共38页。回合 步骤序号输入常数取值方式 (整數) 第一回合 0 t 19 K1 = 5A82799 230 sqrt(2) 第二回合 20 t 39 K2 = 6ED9EBA1 230 sqrt(3) 第三回合 40 t 59 K3 = 8F1BBCDC 230 sqrt(5) 第四回合 60 t 79 K4 =