杂凑函数和数字签名.ppt

第6讲 杂凑算法和数字签名,信息安全概论课程幻灯片,主 要 内 容,一、杂凑函数的概念和基本安全要求 二、MD5杂凑算法 三、数字签名,杂凑函数又称为Hash函数、报文摘要函数、散列函数等。其目的是将任意长度的报文m都压缩成指定长度的数据H(m) H(m)又称为m的指纹，代表了消息m的身份。如下图所示:,一、 杂凑函数的概念和基本安全需求,长度是固定的，与报文的长度无关,杂凑函数的用途: (1) 完整性检验-利用二元对(m, H(m)的不可更改性实现。 此时，m 的变化将导致 H(m)的变化. (2) 提供文件的指纹.用于数字签名。 只要H(m)不可替换,就保证m不可能再更改 (3) 将杂凑值作为密钥，从而压缩掉密钥的冗余度; (4) 伪随机数生成.,一、杂凑函数的概念和基本安全需求(续),杂凑函数技术-优缺点,由于报文摘要不包含报文持有者的秘密信息，故杂凑函数的： 优点: 任何人都可对报文的“指纹”进行检验； 缺点: 掌握报文的人都可生成报文的“指纹” 上述缺点导致当将报文及其指纹放在一起时，只能检验出对报文无意的修改，不能检验出有意的篡改或伪造。,(1) 单向性（第一原像不可求）. 给出一个杂凑值 z，从计算量上讲，求出一个m，或者以不可忽略的概率求出一个m ，使得 H(m) = z 成立是不可行的。,杂凑函数的安全性要求,在实际上求不出,理论方法：穷举攻击,(2) 强无碰撞性. 从计算量上讲，求出，或者以不可忽略的概率求出，具有相同杂凑值H(m1) = H(m2)的两份报文m1和m2是不可行的。,杂凑函数的安全性要求(续1),理论方法：(1)穷举攻击-固定一个，穷举另一个 (2)碰撞攻击 - 两个一起“穷举”,(3) 求第二原像不可行(弱无碰撞性） 任意给定一个报文m1，找出或者以不可忽略的概率找出另一个报文m2，使得 H(m2) = H(m1) 在计算上不可行。,意义： 将一份报文的指纹伪造成另一份报文的指纹在计算上是不可行的。,预先固定的,理论方法：(1) 穷举攻击（穷举m2),杂凑函数的安全性要求(续2),对杂凑函数的基本攻击方法-碰撞攻击,目的: 构造报文m1和报文m2使得H(m1)=H(m2) 生日悖论:20个人的生日互不相同的概率是多少,错!,正确答案是:,20个人中至少有两人生日相同的概率是0.632,是20/365吗?,?,对杂凑函数的碰撞攻击算法,Step1 随机选取N个报文m1,m2, mN; Step2 以这N个报文作为杂凑函数的输入,计算出相应的杂凑值,得到集合 S=(mk, H(mk): k = 1,2, N Step3 根据H(mk)的大小，对集合S利用快速排序算法重新排序。 在排序过程中，如果找到了使H(mk)= H(mt) 的两个不同元mk和mt，就将(mk,mt)作为结果输出，算法终止；如果找不到，就报告碰撞攻击失败，算法终止。,碰撞攻击算法的性能指标,算法所需的存储量: 需要存储表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=(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, 递归地计算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 Rivest 于1990年设计的，MD5是MD4的改进形式。二者的设计思想思想相似。 MD5的特点： 对任意长度的输入，都产生128位的输出；其安全性不依赖于任何假设，适合高速实现。,三、MD5算法,MD5的安全分析现状： 2004年夏，山东大学的王小云宣布找到使MD5的杂凑值相同的两个报文，这两个报文的差是一个特殊的值，但没有公开构造方法。 之后，王小云教授公布了她的方法。人们后来发现，找出MD5的一个碰撞在PC机是非常容易的事情。 由于能产生碰撞的报文未必有实际的意义，而且按王小云的方法构造的两个报文都不能人为地控制，因而该攻击并不对MD5造成实际的威胁。,方法：设原始报文x的长度是L比特. (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后面添加一个 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 个变量分别取初始值如下（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) Round1(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列,再 执行右边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)的整数部分.,函数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 14 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,ti是232abs(sin i)的整数部分.,则Round3先执行左8列,再执行右8列:,函数Round 4的结构: 用 a b c d i s t 表示运算 a (b+a + I(b,c,d) + Mi+ti) s) (仅替换a),A B C D 0 6 t49 A B C D 2 6 t57 D A B C 7 10 t50 D A B C 15 10 t58 C D A B 14 15 t51 C D A B 6 15 t59 B C D A 5 21 t52 B C D A 13 21 t60 A B C D 12 6 t53 A B C D 4 6 t61 D A B C 3 10 t54 D A B C 11 10 t62 C D A B 10 15 t55 C D A B 2 15 t63 B C D A 1 21 t56 B C D A 9 21 t64,ti是232abs(sin i)的整数部分.,则Round3先执行左8列,再执行右8列:,山东大学的王小云教授构造出的MD5的具有修改起点、指定模2和的一类碰撞为: 起点: (与实际的MD5的初始值不同) A取: 0x01234567 B取: 0x89abcd4f C取: 0xfedcba98 D取: 0x76543210 明文1: (M, N )为1024比特，M, N均为512比特,其中:,明文2: 也是1024比特, 均为512比特,这里每个数都是32比特数。其中非零值位于从左边数、从序号0起算第4,11,14位置。,杂凑函数SHA背景介绍,SHA (Secure Hash Algorithm) 是美国国家标准技术研究所（NIST）与美国国家安全局共同设计的。 1992年1月31日SHA在联邦记录中公布。 1992年5月11日起采纳为国家标准(SHS)。 1994年7月11日作了一个小的修改，1995年4月17日公布了修改后的版本，称为SHA-1。 此后又陆续公布了SHA的各种版本.,数字签名技术,手工签名的目的和作用,(1) 表示签名者对消息的认可； (2) 其他人可以识别和验证出是谁的签名； (3)其他人无法伪造和更改签名，即 (A) 无法凭空伪造出一个签名； (B) 对一个文件的签名不能复制或篡改成对另一个文件的签名； (4) 可仲裁性：出现争议时第三方可仲裁. 仲裁的内容: (A) 是否是签名者在抵赖、否认其签名； (B) 签名是否是伪造的。,手工签名的目的和作用（续）,签名的实现方式： 就是在原文件上追加一定的笔迹信息，并使二者形成一个整体。 对电子文档的签名也应达到同样的目的。,如何才能达到签名的目的?,(1) 签名者对消息进行某种变换完成签名; (2) 识别和验证: 利用签名者的公开信息(签名识别密钥)和文件的公开性; (3) 它人不能伪造签名: 签名应与签名者独有的秘密信息(签名密钥)密切相关; (4) 可仲裁性: 靠法律解决.签名者的签名识别密钥应由可信的第三方的确认、公布和认可解决. 法律介入: -两个中心: (1) 发证中心(发布签名识别密钥); (2) 认证中心(仲裁中心)。,数字签名方案的分类 (1) 利用特殊的公钥加密算法实现。 并非所有的公钥加密算法都能实现数字签名，只有满足,(2) 利用专用的数字签名算法实现。 例如： EIGamal数字签名方案,的公钥加密算法的才能实现数字签名。 其中D是脱密算法，E是加密算法。,数字签名的一般过程,报文摘要,对摘要的签名,公布,签名者的身份,如果两份文件的杂凑值相同，则这两份文件的数字签名一定相同。,设计方法：用户Alice将其私钥 kd 作为她的签名密钥，将对应的公钥 ke 作为签名识别密钥；,基于公钥加密算法的数字签名方案,用户Alice对文件m的签名过程： (1) Alice选择一个安全的杂凑函数Hash(x)；,(3) 签名者Alice将文件m及其签名sign(m)一起公布。,(2) Alice利用签名密钥kd对Hash(m)执行脱密变换D，得到Alice对文件m的签名,基于公钥加密算法的数字签名方案,第三方的仲裁: 与签名识别过程相同.,用户B对签名的识别过程： 利用用户A的签名识别密钥ke对签名sign(m)执行加密变换D,若它与m相等，则判断Sign(m)是用户A对文件m的签名；否则判断Sign(m)不是用户A对文件m的签名.,Hash(m),判断依据:,公开密钥,基于RSA公钥加密算法的数字签名方案,数字签名实例: 设RSA算法为:,用户Alice的RSA密钥为： 公开密钥：(e, n) =(7, 33) 秘密密钥：(d, n) =(3, 33),Sign(m)e mod n