《杂凑函数和数字签名》由会员分享，可在线阅读，更多相关《杂凑函数和数字签名（41页珍藏版）》请在金锄头文库上搜索。
1、第6讲 杂凑算法和数字签名,信息安全概论课程幻灯片,一、杂凑函数的概念和基本安全要求 二、MD5杂凑算法 三、数字签名,杂凑函数又称为Hash函数、报文摘要函数、散列函数等。其目的是将任意长度的报文m都压缩成指定长度的数据H(m)H(m)又称为m的指纹，代表了消息m的身份。如下图所示:,一、 杂凑函数的概念和基本安全需求,长度是固定的，与报文的长度无关,杂凑函数的用途:(1) 完整性检验-利用二元对(m, H(m)的不可更改性实现。 此时，m 的变化将导致 H(m)的变化.(2) 提供文件的指纹.用于数字签名。只要H(m)不可替换,就保证m不可能再更改(3) 将杂凑值作为密钥，从而压缩掉密钥的
2、冗余度; (4) 伪随机数生成.,一、杂凑函数的概念和基本安全需求(续),杂凑函数技术-优缺点,由于报文摘要不包含报文持有者的秘密信息，故杂凑函数的： 优点: 任何人都可对报文的“指纹”进行检验； 缺点: 掌握报文的人都可生成报文的“指纹”上述缺点导致当将报文及其指纹放在一起时，只能检验出对报文无意的修改，不能检验出有意的篡改或伪造。,(1) 单向性（第一原像不可求）. 给出一个杂凑值 z，从计算量上讲，求出一个m，或者以不可忽略的概率求出一个m ，使得 H(m) = z 成立是不可行的。,杂凑函数的安全性要求,在实际上求不出,理论方法：穷举攻击,(2) 强无碰撞性.从计算量上讲，求出，或者以
3、不可忽略的概率求出，具有相同杂凑值H(m1) = H(m2)的两份报文m1和m2是不可行的。,杂凑函数的安全性要求(续1),理论方法：(1)穷举攻击-固定一个，穷举另一个(2)碰撞攻击 - 两个一起“穷举”,(3) 求第二原像不可行(弱无碰撞性）任意给定一个报文m1，找出或者以不可忽略的概率找出另一个报文m2，使得 H(m2) = H(m1) 在计算上不可行。,意义：将一份报文的指纹伪造成另一份报文的指纹在计算上是不可行的。,预先固定的,理论方法：(1) 穷举攻击（穷举m2),杂凑函数的安全性要求(续2),对杂凑函数的基本攻击方法-碰撞攻击,目的: 构造报文m1和报文m2使得H(m1)=H(m
4、2) 生日悖论:20个人的生日互不相同的概率是多少,错!,正确答案是:,20个人中至少有两人生日相同的概率是0.632,是20/365吗?,?,对杂凑函数的碰撞攻击算法,Step1 随机选取N个报文m1,m2, mN;Step2 以这N个报文作为杂凑函数的输入,计算出相应的杂凑值,得到集合 S=(mk, H(mk): k = 1,2, NStep3 根据H(mk)的大小，对集合S利用快速排序算法重新排序。在排序过程中，如果找到了使H(mk)= H(mt) 的两个不同元mk和mt，就将(mk,mt)作为结果输出，算法终止；如果找不到，就报告碰撞攻击失败，算法终止。,碰撞攻击算法的性能指标,算法所
5、需的存储量: 需要存储表S，以便进行快速排序，故存储复杂性是表S的规模O(N),S=(mk, H(mk): k = 1,2, N,算法所需的计算量： (1) 该算法生成集合S的计算量是计算N次杂凑函数；(2) 对集合S快速排序并找出全部碰撞的计算量为 |N|log2|N| 次比较。故总的计算量为 N + |N|log2|N| = O(N),碰撞攻击算法的性能指标,特别地，当 时，碰撞攻击的成功率近似为,成功率分析： 定理1 设杂凑值为n比特且N远小于2n,则碰撞攻击的成功率近似为,特例：如果n = 64,则 N1.4232 = 5.6G，此时碰撞攻击算法可实现。,是存储复杂性和计算复杂性,表S
6、=(mk, H(mk): k = 1,2, N的规模,攻击能力,能够对抗碰撞攻击的 杂凑函数的安全界限,如果对抗穷举攻击的能力的密钥长度的安全界限为 n 比特，则对抗碰撞攻击的杂凑算法的杂凑值的比特数的安全界限应为 2n 。,1. MD强化技术(Merkle-Damaard强化)将消息M = (M1,M2,Mn)的最后一个分组Mn设置为“真正消息”的长度，这个过程称为MD强化。,二、基于分组密码设计的杂凑函数,2. 迭代型杂凑函数,一个迭代杂凑函数H(H0,M)是由一个容易计算的函数h(x,y)确定的一个杂凑函数H,其中 h: 0,1m :0,1t 0,1m杂凑函数对给定的初始值H0, 递归地
7、计算Hi=h(Hi-1,Mi),从而将报文M = (M1,M2,Mn)杂凑到杂凑值Hn。特别地,选取h=E(x,k)是一个安全的分组密码,则当将消息经MD强化后,就得到一个安全的杂凑函数。,新的报文块Mi的输入位置是密钥的位置!,被杂凑的消息必须经过MD强化!,圈函数为 Hi = h(Hi-1, Mi) Hi-1,3. DM杂凑函数模型(Davies-Meyer方案),函数h,Hi-1,Hi,Mi,初值H0： 是固定的常数,被杂凑的消息必须经过MD强化!,特例：取 h(Hi-1, Mi) = DESMi(Hi-1) 此时：消息是56比特为一块，杂凑值是64比特,三、MD5算法,MD4 是Ron
8、 Rivest 于1990年设计的，MD5是MD4的改进形式。二者的设计思想思想相似。MD5的特点：对任意长度的输入，都产生128位的输出；其安全性不依赖于任何假设，适合高速实现。,三、MD5算法,MD5的安全分析现状： 2004年夏，山东大学的王小云宣布找到使MD5的杂凑值相同的两个报文，这两个报文的差是一个特殊的值，但没有公开构造方法。之后，王小云教授公布了她的方法。人们后来发现，找出MD5的一个碰撞在PC机是非常容易的事情。由于能产生碰撞的报文未必有实际的意义，而且按王小云的方法构造的两个报文都不能人为地控制，因而该攻击并不对MD5造成实际的威胁。,方法：设原始报文x的长度是L比特. (
9、1) 求出d0，使得L+1+d+64是512的倍数； (2) 在原始报文x后面先添加一个1，,MD5 算法第一步: 消息填充,目的:使MD强化后报文长度是512的整数倍,x,|1,| 0d,|L,扩充后的报文 =,然后添加d个0，,最后将消息的长度L用64比特表示，加在最后。,(L+1+d+64)mod512 = 0,d = (L65)mod512,由,MD5 填充的例子,设x是具有 20768比特的长信息，则 d =( L65)mod512 =(20768 65)mod512=20833mod512=(40512+353)mod512=353mod512= 512353= 159 故应在x后
10、面添加一个 1和159个0，最后再添加原始消息长度20768的64位表示。,MD5使用的编码变换,逐位模2加运算： x y,逐位取补运算：,模232位加运算：x + y,循环左移s位: x s,四个密码变换:,面向32字设计-全部采用32位字的运算,逐位与运算：x y逐位或运算：x y,X,Y,Z都是32位字,MD5 初始化变量,(1) MD5的迭代函数一次处理512比特报文块 (2) 512比特报文块分为16个32比特字。 (3) N个32比特字共分为T = N/16个512比特块 (4) 首先初始化MD5的4个变量(A, B, C, D), 每个变量 32 位。4 个变量分别取初始值如下（
11、16进制表示）：,记M = M0M1MN-1是M的32位字表示。,MD5 的主算法,圈函数模型: Hi = h(Hi-1,Mi) Hi-1.其中Hi-1=(A,B,C,D), h由round1,round2,round3和round4组成.,DM模型,具体过程:对i=0至N/16-1,依次执行以下步骤：/ N/16是512比特块的个数 Step1 执行X0M16i, X1M16i+1, X15M16i+15 / 16是512比特块中32位字的个数,一次处理16个32比特块 Step2 暂存(A,B,C D),即执行: AAA, BBB,CCC,DDD Step3 执行: (A,B,C D) R
12、ound1(A,B,C D,X0, X15) Step4 执行: (A,B,C D) Round2(A,B,C D,X0, X15) Step5 执行: (A,B,C D) Round3(A,B,C D,X0, X15) Step7 执行: (A,B,C D) Round4(A,B,C D,X0, X15) Step6 执行: (A,B,C D) (A,B,C D) +(AA,BB,CC, DD),函数Round 1的结构: 用 a b c d i s t 表示运算 a (b+a + f(b,c,d) + Mi+ti) s). (仅替换a),则Round1依次执行下述16层运算:(执行完左边8
13、列,再 执行右边8列),A B C D 0 7 t1 A B C D 8 7 t9 D A B C 1 12 t2 D A B C 9 12 t10 C D A B 2 17 t3 C D A B 10 17 t11 B C D A 3 22 t4 B C D A 11 22 t12 A B C D 4 7 t5 A B C D 12 7 t13 D A B C 5 12 t6 D A B C 13 12 t14 C D A B 6 17 t7 C D A B 14 17 t15 B C D A 7 22 t8 B C D A 15 22 t16,ti是232abs(sin i)的整数部分.,
14、函数Round 2的结构: 用 a b c d i s t表示运算 a (b+a + g(b,c,d) + Mi+ti) s) (仅替换a),A B C D 1 5 t17 A B C D 9 5 t25 D A B C 6 9 t18 D A B C 14 9 t26 C D A B 11 14 t19 C D A B 3 14 t27 B C D A 0 20 t20 B C D A 8 20 t28 A B C D 5 5 t21 A B C D 13 5 t29 D A B C 10 9 t22 D A B C 2 9 t30 C D A B 15 14 t23 C D A B 7 1
15、4 t31 B C D A 4 20 t24 B C D A 12 20 t32,ti是232abs(sin i)的整数部分.,则Round2先执行左8列,再执行右8列: (仅替换a),函数Round 3的结构: 用 a b c d i s t 表示运算 a (b+a + h(b,c,d) + Mi+ti) s) (仅替换a),A B C D 5 4 t33 A B C D 13 4 t41 D A B C 8 11 t34 D A B C 0 11 t42 C D A B 11 16 t35 C D A B 3 16 t43 B C D A 14 23 t36 B C D A 6 23 t44 A B C D 1 4 t37 A B C D 9 4 t45 D A B C 4 11 t38 D A B C 12 11 t46 C D A B 7 16 t39 C D A B 15 16 t47 B C D A 10 23 t40 B C D A 2 23 t48,
