1、主 要 内 容一、杂凑函数的概念和基本安全要求二、MD5杂凑算法三、数字签名 杂凑函数又称为杂凑函数又称为Hash函数、报文摘要函数、报文摘要函数、散列函数等。其目的是将任意长度的函数、散列函数等。其目的是将任意长度的报文报文m都压缩成都压缩成指定长度指定长度的数据的数据H(m) H(m)又称为又称为m的指纹，代表了消息的指纹，代表了消息m的的身份身份。如下图所示。如下图所示:报文报文摘要杂凑函数杂凑函数H H一、一、 杂凑函数的概念和基本安全需求杂凑函数的概念和基本安全需求长度是固定的，与报文的长度无关 杂凑函数的用途杂凑函数的用途: (1) 完整性检验完整性检验-利用二元对利用二元对(m,
2、 H(m)的的不可更改性实现。不可更改性实现。 此时，此时，m 的变化将导致的变化将导致 H(m)的变化的变化. (2) 提供文件的指纹提供文件的指纹.用于数字签名。用于数字签名。 只要只要H(m)不可替换不可替换,就保证就保证m不可能再更改不可能再更改 (3) 将杂凑值作为密钥将杂凑值作为密钥，从而压缩掉密钥的，从而压缩掉密钥的冗余度冗余度; (4) 伪随机数生成伪随机数生成.一、杂凑函数的概念和基本安全需求一、杂凑函数的概念和基本安全需求(续续)杂凑函数技术-优缺点优缺点 由于报文摘要不包含不包含报文持有者的秘密信息，故杂凑函数的：优点优点: 任何人都可对报文的“指纹”进行检验；缺点缺点:
3、 掌握报文的人都可生成报文的“指纹” 上述缺点导致当将报文及其指纹放在一报文及其指纹放在一起起时，只能检验出对报文无意的修改，不能检验出有意的篡改或伪造。报文报文摘要杂凑函数杂凑函数H H (1) 单向性（第一原像不可求）单向性（第一原像不可求）. 给出一个杂凑值给出一个杂凑值 z，从计算量上讲，求出，从计算量上讲，求出一个一个m，或者以不可忽略的概率求出一个，或者以不可忽略的概率求出一个m ，使得使得 H(m) = z 成立是不可行的。成立是不可行的。 杂凑函数的安全性要求杂凑函数的安全性要求报文 m报文摘要杂凑函数杂凑函数H H在实际上求不出理论方法：穷举攻击 (2) 强无碰撞性强无碰撞性
4、. 从计算量上讲，求出，或者以不可忽略的从计算量上讲，求出，或者以不可忽略的概率求出，具有相同杂凑值概率求出，具有相同杂凑值H(m1) = H(m2)的的两份报文两份报文m1和和m2是不可行的。是不可行的。杂凑函数的安全性要求杂凑函数的安全性要求(续续1)报文 m1报文摘要杂凑函数杂凑函数H H报文 m2杂凑函数杂凑函数H H理论方法：(1)穷举攻击-固定一个，穷举另一个 (2)碰撞攻击 - 两个一起“穷举” (3) 求第二原像不可行求第二原像不可行(弱无碰撞性）弱无碰撞性） 任意给定一个报文任意给定一个报文m1，找出或者以不可，找出或者以不可忽略的概率找出另一个报文忽略的概率找出另一个报文m
5、2，使得，使得H(m2) = H(m1)在计算上不可行。在计算上不可行。 意义：意义： 将一份报文的指纹伪造成另一份报文的将一份报文的指纹伪造成另一份报文的指纹在计算上是不可行的。指纹在计算上是不可行的。 预先固定的理论方法：(1) 穷举攻击（穷举m2)杂凑函数的安全性要求杂凑函数的安全性要求(续续2)对杂凑函数的基本攻击方法对杂凑函数的基本攻击方法-碰撞攻击碰撞攻击20365)19365(364365p3651920 e目的目的: 构造报文构造报文m1和报文和报文m2使得使得H(m1)=H(m2)生日悖论生日悖论:20个人的生日互不相同的概率是多少个人的生日互不相同的概率是多少错错!正确答案
6、是正确答案是:190)3651 (tt041. 1 ee1718. 21368. 020个人中至少有两人生日相同的概率是个人中至少有两人生日相同的概率是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)作为结果输出，算法终止；
7、如果找不到，就报告碰撞攻击失败，算法终止。碰撞攻击算法的性能指标碰撞攻击算法的性能指标 算法所需的存储量算法所需的存储量: 需要存储表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)碰撞攻击算法的性能指标碰撞攻击算法的性能指标1221nNe特别地，当 时，碰撞攻击的成功率近似为12nN632. 0368. 017
8、18. 21111e 成功率分析：成功率分析： 定理定理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)的最后一个分
9、组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的输入的输入位置是密钥的位置位置是密钥的位置!被杂凑的消息必被杂凑的消
10、息必须经过须经过MD强化强化!圈函数为圈函数为 Hi = h(Hi-1, Mi) Hi-13. DM杂凑函数模型杂凑函数模型(Davies-Meyer方案方案)函数hHi-1HiMi初值H0：是固定的常数被杂凑的消息必被杂凑的消息必须经过须经过MD强化强化!特例：取 h(Hi-1, Mi) = DESMi(Hi-1) 此时：此时：消息是消息是56比特为一块，杂凑值是比特为一块，杂凑值是64比特比特三、三、MD5算法算法 MD4 是Ron Rivest 于1990年设计的，MD5是MD4的改进形式。二者的设计思想思想相似。 MD5的特点： 对任意长度的输入，都产生128位的输出；其安全性不依赖于
11、任何假设，适合高速实现。三、三、MD5算法算法 MD5的安全分析现状： 2004年夏，山东大学的王小云宣布找到使MD5的杂凑值相同的两个报文，这两个报文的差是一个特殊的值，但没有公开构造方法。 之后，王小云教授公布了她的方法。人们后来发现，找出MD5的一个碰撞在PC机是非常容易的事情。 由于能产生碰撞的报文未必有实际的意义，而且按王小云的方法构造的两个报文都不能人为地控制，因而该攻击并不对MD5造成实际的威胁。方法：方法：设原始报文设原始报文x的长度是的长度是L比特比特.(1) 求出d0，使得L+1+d+64是512的倍数；(2) 在原始报文x后面先添加一个1， MD5 算法第一步: 消息填充
12、目的目的:使MD强化后报文长度是512的整数倍x |1| 0d|L扩充后的报文 =然后添加d个0，最后将消息的长度L用64比特表示，加在最后。(L+1+d+64)mod512 = 0d = (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
13、逐位取补运算：x 模232位加运算：x + y 循环左移s位: x s(1):(, , )()()(2): (, , )()()(3)(, , )(4)(, , )()f X Y ZXYXZg X Y ZXZYZh X Y ZXYZI X Y ZYXZ控选函数控选函数四个密码变换四个密码变换: : 面向32字设计-全部采用32位字的运算 逐位与运算：x y 逐位或运算：x yX,Y,Z都是都是32位字位字MD5 初始化变量(1) MD5的迭代函数一次处理512比特报文块(2) 512比特报文块分为16个32比特字。(3) N个32比特字共分为T = N/16个512比特块(4) 首先初始化MD
14、5的4个变量(A, B, C, D), 每个变量 32 位。4 个变量分别取初始值如下（16进制表示）：0 67452301,089,0 98,0 10325476AxBxefcdabCxbadcfeDx记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, X
15、15M16i+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)
16、函数函数Round 1的结构的结构: 用 a b c d i s t 表示运算a (b+a + f(b,c,d) + Mi+ti) s). (仅替换a)()(),(dbcbdcbf则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
17、 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 (b, c, d) isat(b,c,d)isatti是232abs(sin i)的整数部分. 函数函数Round 2的结构的结构: 用 a b c d i s t表示运算a (b+a + g(b,c,d) + Mi+ti) s) (仅替换a)( , , )()()g b c dbdcd(b, c, d)isat(b, c, d)isatA B C D 1 5 t17 A B C D 9 5 t25 D A B
18、 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的结构的结
19、构: 用 a b c d i s t 表示运算a (b+a + h(b,c,d) + Mi+ti) s) (仅替换a)(, ,)h X Y ZXYZA 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
20、 B 15 16 t47 B C D A 10 23 t40 B C D A 2 23 t48 i(b, c, d)isat(b, c, d)satti是232abs(sin i)的整数部分.则Round3先执行左8列,再执行右8列: 函数函数Round 4Round 4的结构的结构: : 用 a b c d i s t 表示运算a (b+a + I(b,c,d) + Mi+ti) s) (仅替换a)(, ,)()I X Y ZYXZA 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
21、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 i(b, c, d)isat(b, c, d)satti是232abs(sin i)的整数部分.则Round3先执行左8列,再执行右8列: 山东大学的王小云教授构造出的MD5的具有修改起点、指定模2和的一类碰撞为:
22、起点: (与实际的MD5的初始值不同) A取: 0 x01234567 B取: 0 x89abcd4f C取: 0 xfedcba98 D取: 0 x76543210明文1: (M, N )为1024比特，M, N均为512比特其中:311531311531(0,0,0,0,2 ,2 ,2 ,0)(0,0,0,0,2 , 2 ,2 ,0)MMNN(,)MN明文2: 也是1024比特, 均为512比特,MN这里每个数都是32比特数。其中非零值位于从左边数、从序号0起算第4,11,14位置。(,)(,)H MNH M N杂凑函数SHA背景介绍 SHA (Secure Hash Algorithm)
23、 是美国国家标准技术研究所（NIST）与美国国家安全局共同设计的。 1992年1月31日SHA在联邦记录中公布。 1992年5月11日起采纳为国家标准(SHS)。 1994年7月11日作了一个小的修改，1995年4月17日公布了修改后的版本，称为SHA-1。 此后又陆续公布了SHA的各种版本.数字签名技术手工签名的目的和作用手工签名的目的和作用 (1) 表示签名者对消息的认可； (2) 其他人可以识别和验证识别和验证出是谁的签名； (3)其他人无法伪造和更改伪造和更改签名，即 (A) 无法凭空伪造出一个签名； (B) 对一个文件的签名不能复制或篡改成对另一个文件的签名； (4) 可仲裁性：出现
24、争议时第三方可仲裁. 仲裁的内容仲裁的内容: (A) 是否是签名者在抵赖、否认抵赖、否认其签名；其签名； (B) 签名是否是伪造的。手工签名的目的和作用（续）手工签名的目的和作用（续） 签名的实现方式：签名的实现方式： 就是在原文件上追加一定的笔迹笔迹信息，并使二者形成一个整体。 对电子文档的签名也应达到同样的目的。如何才能达到签名的目的如何才能达到签名的目的?(1) 签名者对消息进行某种变换完成签名;(2) 识别和验证识别和验证: 利用签名者的公开信息(签名识别密钥)和文件的公开性;(3) 它人不能伪造签名它人不能伪造签名: 签名应与签名者独有的秘密信息(签名密钥)密切相关; (4) 可仲裁
25、性可仲裁性: 靠法律解决.签名者的签名识别密钥应由可信的第三方的确认、公布和认可解决. 法律介入法律介入: -两个中心: (1) 发证中心发证中心(发布签名识别密钥发布签名识别密钥); (2) 认证中心认证中心(仲裁中心仲裁中心)。数字签名方案的分类数字签名方案的分类 (1) 利用特殊的公钥加密算法实现。 并非所有的公钥加密算法都能实现数字签名，只有满足xxDEdekk)( (2) 利用专用的数字签名算法实现。 例如： EIGamal数字签名方案数字签名方案的公钥加密算法的才能实现数字签名。其中D是脱密算法，E是加密算法。数字签名的一般过程数字签名的一般过程报文报文摘要杂凑函数杂凑函数对摘要的
26、签名报文公布签名者的身份 如果两份文件的杂凑值相同，则这两份文如果两份文件的杂凑值相同，则这两份文件的数字签名一定相同。件的数字签名一定相同。 设计方法：设计方法：用户Alice将其私钥 kd 作为她的签名密钥，将对应的公钥 ke 作为签名识别密钥；基于公钥加密算法的数字签名方案基于公钥加密算法的数字签名方案)()(mHashDmsigndk 用户用户Alice对文件对文件m的签名过程的签名过程： (1) Alice选择一个安全的杂凑函数Hash(x)； (3) 签名者Alice将文件m及其签名sign(m)一起公布。 (2) Alice利用签名密钥kd对Hash(m)执行脱密变换D，得到Al
27、ice对文件m的签名基于公钥加密算法的数字签名方案基于公钥加密算法的数字签名方案 第三方的仲裁第三方的仲裁: 与签名识别过程相同. )(msignEek 用户用户B对签名的识别过程对签名的识别过程： 利用用户A的签名识别密钥ke对签名sign(m)执行加密变换D,若它与m相等，则判断Sign(m)是用户A对文件m的签名；否则判断Sign(m)不是用户A对文件m的签名.Hash(m)?判断依据: xxDExDEdedekkkk)()(一般有公开密钥)(mHashDEdekk基于基于RSARSA公钥加密算法的数字签名方案公钥加密算法的数字签名方案 数字签名实例数字签名实例: 设设RSA算法为算法为
28、:用户Alice的RSA密钥为：公开密钥：(e, n) =(7, 33)秘密密钥：(d, n) =(3, 33)Sign(m)e mod n221mod33(210)22mod33 (1024)22mod33(1024mod33)22mod33 (31331)mod3322mod332mod33 2已知消息m的杂凑值是3，判断8是否是Alice对消息m的签名由于Alice的公开密钥是 (e, n) =(7, 33)，且，且Sign(m) = 887mod333 Hash(m)8不是Alice对消息m的签名 1985年由T.EIGamal提出,是专用的数字签名方案，其安全性基于有限域上的离散对数
29、问题的难解性。EIGamal数字签名方案数字签名方案 上述过程与上述过程与EIGamal加密算法相同过程加密算法相同过程 用户用户A的设计过程的设计过程： (1) 选取大素数p和Z/(p)中的本原元本原元g,将p和g公开; (2) 随机选取整数x:1xp-2,计算y=gxmodp，并将y作为公开的签名识别密钥，将x作为保密的签名密钥。 - 40 -精品课件精品课件！- 41 -精品课件精品课件！ 签名过程签名过程: 设mZ/(p)0是待签文件.用户A秘密地随机随机选取整数k:1kp-2,计算sign(m)=(r,),其中r=gk modp, =(m-xr)k-1 mod(p-1)将(m,sign(m)公布,并清除k.x为私钥, y=gxmodp为公钥. 验证过程验证过程: 对于(m,sign(m),如果yrrmodp = gmmodp,则接受签名,否则不承认签名。 验证依据验证依据: 注意：注意： 涉及的都是涉及的都是g的指数的指数 yrrmodp = (gx)r(gk)modp= gxr-kmodp = g(xr-k)mod(p-1)modp = gxr-(m-xr)mod(p-1)modp = gmmodp 如果不知道x,也不知道k,就造不出,因而签名无法伪造.若能解决离散对数问题,就能伪造签名.EIGamal数字签名方案（续）数字签名方案（续）
