1、第5章 签名与认证第第5 5章章 签名与认证签名与认证5.1 数字签名数字签名5.2 单向散列单向散列(Hash)函数函数5.3 身份识别身份识别5.4 消息认证码消息认证码(MAC)习题习题 5实践练习实践练习 5第5章 签名与认证 信息技术带来现代社会变革的一个重大方面是电子商务，它极大地促进了传统商务模式的改变和结构的更新。而电子商务的发展，对信息安全技术又提出了多方位的新要求，主要表现在形形色色的签名与认证需求方面。密码技术近年来的巨大发展，也正集中体现在这些方面。第5章 签名与认证5.1数字签名数字签名 A收到B以明文方式送来的信息后，A如何鉴别是B所发而非别人伪造或篡改的呢？又如公
2、钥密码系统中，各用户从网络上获取对方的公开密钥，如何保证它没有被篡改或替代呢？倘若C用自己的公钥替换了B的公钥，那么它就可以用自己的私钥解读所有人发给B的密文。再如，单钥体系中，A、B两方均掌握密钥K，如果没有签名，一旦发生争议就说不清楚，因为B可以修改A发来的密文，A也可以自己修改原文以赖账，法律上缺乏判定谁是谁非的凭证。传统的(手写)签名借助纸张将文件的内容与签发人的笔迹(认可凭证)有效地结合在一起，使文件具有了可认证性。然而，第5章 签名与认证由于电子文档的易拷贝性和可粘贴性，使机械地照搬手写签名到电子文档上的做法失效，必须引入功能相似，但方式不同的有效认证方式。数字签名是含有发送方身份
3、的一段数字或代码串。它应有以下特征：(1)签名是可以验证的，收到签名的人容易由签名确定来信人。(2)签名是不可伪造的，除了签名者之外的任何人无法实现这个签名。(3)签名是不可重用的，一个签名只对一个文件生效，无法用于其他文件。(4)签名是不可改变的，一旦签名发出便不能再作修改。第5章 签名与认证 (5)签名是不可抵赖的，存在某种方法充分证明该签名确为发信人所为。用发信人私钥加密所发信件得到的密文，就是具有上述特征的一种数字签名。为了适应多种不同的用途，为了使用起来更方便更安全，滋生出了一系列不同形式的数字签名，下文将陆续介绍。它们在电子商务和信息网络中发挥着不可替代的作用。数字签名的主要功能有
4、：(1)识别来信(函)的正确信源。(2)验证发信人的合法身份。(3)检查信函内容的完整性。(4)获得行为不可否认的证据。(5)标示知识产权的印记。第5章 签名与认证5.1.1RSA签名体系签名体系 RSA签名体系与RSA加密算法相同，但用法不同。系统参数系统参数 取两个大素数p和q，计算n=pq和 (n)=(p-1)(q-1)，随机选择整数d使gcd(d,(n)=1，求出模 (n)的逆元e，使它满足ed=1 mod(n)。取公开密钥为k1=(n,e)；私有密钥为k2=(p,q,d)。签名算法签名算法 用私钥“加密”明文x，得到的结果y叫做x的签名，即 Sig (x)=xd mod n=y (5
5、-1)验证算法 Ver (y)=ye mod nx (5-2)1k2k第5章 签名与认证 首先y只能是x的签名(是x的加密结果)，它不能用于其他文档；其次，y是用发信人的私钥“加密”所得，别人做不出这样的签名。任何人都可以用发信人的公钥解出x，与原来的x对照，即可证明以上两点。通常不仅要认证签名，还要加密明文，不让合法收信人以外的其他人看到明文x，这就要进行双重“加密”。如A给B发信，有两种方案：(1)先加密再签名：A做z=EB(x)，y=SigA(z)的运算，把(z,y)传输给B；B收到(z,y)后，用自己的私钥解读密文,即做x=DB(z)的运算，再用A的公钥验证签名VerA(z,y)，看是
6、否满足 =z。Aey第5章 签名与认证 这样做的不安全之处在于如果窃听者C收到(z,y)，它可以用自己的密文z=EB(x)替代z，并对z作自己的签名：SigC(z)=y，再用y代替y。而B收到(z,y)后，可能会做出发信人是C的误解，因为用C的公钥(eC,n)能够证明签名VerC(z,y),即 =zmod n，从而相信了C发来的密文x，结果受了骗。(2)先签名再加密：A先做SigA(x)=y的运算，再做连明文带签名一起加密EB(x,y)=z的运算，发送z给B；B收到z后先解密得到签名，再进行验证。这种方案中，窃听者C即使收到z，也因无A的私钥而不能解译，所以比较安全。Cey第5章 签名与认证5
7、.1.2ElGamal签名方案签名方案 1985年，ElGamal基于离散对数提出了一种签名方案。系统参数系统参数 p是大素数，g是 的一个生成元(即本原根)。定义密钥为 K=(p,g,y,x)：y=gx mod p，x 其中，公开密钥k1为y、p、g；私有密钥k2为x。签名算法签名算法 签名者拥有(k1k2)=(p，g，y，x)，随机数k 和待签消息m。生成的签名为 Sig (m,k)=(r,s)(5-3)这里,对r和s有 r=gk mod p,s=(m-xr)k-1 mod(p-1)(5-4)随机数k用以生成签名中的r部分，而明文用以生成签名中的s部分。pZpZ2k第5章 签名与认证 验证
8、算法验证算法 验证者有公钥k1=(p，g，y)，收到的明文m和签名(r,s)，从而验证算法为 Ver (r,s)=yrrsgm mod p (5-5)实际上，因为 ks=(m-xr)mod(p-1)即 ks=(p-1)+(m-xr)于是有 gks=g(p-1)+(m-xr)=g(p-1)g(m-xr)利用欧拉定理gp-1mod p=1，就有 g(p-1)=(gp-1)mod p=1 mod p 第5章 签名与认证所以 gks=g(m-xr)mod p因此有 yrrs=gxrgks=gxrg(m-xr)mod p=gm mod p 使用ElGamal方案应注意三方面的情况：(1)随机数k不能泄露
9、，否则用x=(m-sk)r-1 mod p就可以在已知明文的情况下窃取私钥。(2)k应当每次都不同，否则，若 m1=xr+ks1 mod(p-1),m2=xr+ks2 mod(p-1)两式相减得 m1-m2=k(s1-s2)mod(p-1)第5章 签名与认证 设d=gcds1-s2,p-1，因为d|(p-1)且d|(s1-s2),于是d|(m1-m2)。再定义dpp,dsss,dmmm1 2121则有 ，且 ，那么：pskm mod 1)gcd(p,spsmk mod 1)10(1dtsmp tk从而通过验证r=gk mod p就可以确定k。第5章 签名与认证 (3)由于验证只是核实等式yrr
10、s=gm mod p是否成立，因此可考虑通过伪造能使上式成立的(r,s)来攻击。然而它的作用只不过对给定明文m又作了一个能通过认可的签名，既没有破译系统，又不能为其他明文生成签名，仅此而已。所以，它并不能对ElGamal构成威胁。为了把明文与签名结合起来，可以有多种方式，前面所讲的方式是：ks=(m-xr)mod(p-1)其验证方程是 yrrs=gm mod p 其他方式及其验证方程列举如下：第5章 签名与认证 mx=(rk+s)mod(p-1)ym=rrgs mod p mx=(sk+r)mod(p-1)ym=rsgr mod p rx=(mk+s)mod(p-1)yr=rmgs mod p
11、 rx=(sk+m)mod(p-1)yr=rsgm mod p sx=(rk+m)mod(p-1)ys=rrgm mod p sx=(mk+r)mod(p-1)ys=rmgr mod p sx=(k+mr)mod(p-1)ys=rgmr mod p mrx=(k+s)mod(p-1)ymr=rgs mod p x=(mrk+s)mod(p-1)y=rmrgs mod p x=(sk+rm)mod(p-1)y=rsgmr mod p rmx=(sk+1)mod(p-1)ymr=rsg mod p第5章 签名与认证 sx=(mrk+1)mod(p-1)ys=rmrg mod p (r+m)x=(k
12、+s)mod(p-1)y(m+r)=rgs mod p x=(m+r)k+smod(p-1)y=r(m+r)gs mod p sx=k+(m+r)mod(p-1)ys=rg(m+r)mod p x=sk+(r+m)mod(p-1)y=rsg(m+r)mod p (r+m)x=(sk+1)mod(p-1)y(m+r)=rsg mod p sx=(r+m)k+1mod(p-1)ys=r(m+r)g mod p通式是：Ax=Bk+C mod(p-1)yA=rBgC mod p (5-6)第5章 签名与认证5.1.3DSS 数字签名标准(DSS)是美国国家标准和技术研究所(NIST)于1991年8月公
13、布的标准。它所采用的算法叫DSA，实际上是ElGamal的变形，签名中用的是明文的信息摘要。系统参数系统参数 p是一个5121024位的大素数，它满足离散对数难解问题；q是160位的素数,且q|p-1;g 是Zp域中q次单位元根。定义K=(p,q,g,y,x:y=gx mod p,h()为公开的Hash函数。取公开密钥k1=(p,q,g,y);私有密钥k2=(x)。pZ第5章 签名与认证 签名算法签名算法 签名者拥有私钥x，对于随机数k 和待签消息m ，生成的签名为 (m,k)=(r,s)(5-7)这里:r=(gk mod p)mod q(必然小于160位)(5-8)s=h(m)+xrk-1
14、mod q(必然小于160位)(5-9)验证算法验证算法 验证者有公钥k1=(p，g，y)，收到的明文m和签名(r,s)，验证算法为 (5-10)其中：e1=h(m)s-1 mod q,e2=rs-1 mod q (5-11)pZpZ2Sigkrqpygs,r,mVereek mod mod)(211第5章 签名与认证实际上，由k=h(m)+xrs-1 mod q知：DSS的公布引起了学术界和商业界的激烈反应：赞成的人认为它长度小、速度快、成本低，对金融业特别有用；反对的人则认为它不与国际标准(以RSA为标准的ISO、CCITT、SWIFT等)兼容。从技术上讲，s不能等于零，要加以排除，否则危
15、及安全性。rqpgqpgqpggqpygygksxrmhxrssmhrssmhee mod mod mod mod mod mod mod mod 1111121)()()(第5章 签名与认证5.1.4不可否认签名方案不可否认签名方案 不可否认签名方案与一般的签名方案相比较，最根本的特点是如果没有签名者的合作，签名就无法得到验证。这就防止了未经签名者同意就随意复制他的签名文件进行电子分发的可能性。有了这样的前提，一旦验证通过，签名者也就没有理由否认。一个不可否认签名由签名算法、验证算法和否认协议三部分组成。系统参数系统参数 设p=2q+1是一个大素数，这里q是素数且符合离散对数复杂性要求；是
16、域中q次单位元根，1q-1。设G表示阶为q的 的乘法子群，且定义：K=(p,a):=a mod p其中，私有密钥为a；公开密钥为p、。pZpZpZ第5章 签名与认证 签名算法签名算法 B掌握私钥a，欲对x签名，xG，则可计算：y=Sig a(x)=xa mod p yG (5-12)y就是B对x的签名。验证协议验证协议 (1)A欲验证签名，可任意选取e1,e2 。计算c=mod p，把它传给B。(2)B计算 ，并传回A。(3)A接收d并验证 mod p。(5-13)如果成立，便有充分必要的理由认为y是B对x的一条有效的签名。因为B用自己的私钥参与了验证过程，使A任意地选取e1和e2都能自恰。证
17、明如下：pZ21eeypcdqa modmod121eexd第5章 签名与认证 因为 2121aeaeeexyc所以 211eeaxcd不可否认签名方案的安全性分析不可否认签名方案的安全性分析 首先，A是验证了 后，才同意接收y作为x的签名的，理论上可以推知yxa mod p情况下 的概率只有 ，因此一个伪造的签名能使A相信的概率只有 。pxdee mod 21pxdee mod 21q1q1第5章 签名与认证 其次，若y=xa mod p且A遵守否认协议，但存在d和d使：，pxdee mod21pxdff mod21则理论上可以推知 成立的概率为 pddeffe mod)()(1212q1
18、它表明，如果B想用其他d值来否认y是他的签名，其结果就很难使等式成立(立刻会被发现)。因此，B能愚弄A的概率只有 。只要q充分大，B就没有理由否认自己的签名。q1第5章 签名与认证5.1.5群签名群签名 1991年，Chaum和VanHeyst基于以下问题提出群签名(GroupSignature)方案：一个公司所属各部门的计算机联网工作，各部门的打印机也联在网上。打印时，应先确定是本公司的人才可以使用，然而又要求不暴露用户的姓名。另一方面，如果打印机使用太频繁时，主管者应能够查出是谁打印了这么多东西。一般来说，群签名系统由组、组成员(签名者)、签名接受者(签名验证者)和权威(Authority
19、)组成，它具有以下特点：(1)用户组中每位合法用户都能独立对消息产生签名。(2)签名的接受者能验证签名的有效性。第5章 签名与认证 (3)签名的接受者不能辨认是谁的签名。(4)一旦发生争执，权威或组中所有成员的联合可以辨认签名者。这里介绍一种KPW可变群签名方案。系统参数系统参数 选择n=pq=(2fp+1)(2fq+1)，这里p、q、p、q为相异的大素数；g的阶为f；与d为整数且满足d=1 mod(n)，gcd,(n)=1；h为安全的Hash函数；IDG为用户组身份，由权威掌握。签名组的公钥为(n,g,f,h,IDG)；签名组的私钥为(d，p，q)。第5章 签名与认证 设IDA为组员A的身份
20、消息，A随机选取sA(0,f)，并将消息 发送给权威。权威计算 ，并将xA秘密地传送给成员A，使A掌握私有密钥(xA,sA)。同样的交换过程在权威与各个成员之间都要进行。ng,IDs modAAngIDxdsGAA mod 签名算法签名算法 对于待签消息m，组中任意成员都有权进行签名。比如A要签名，他可以随机选取整数(r1,r2)0,f),计算 (5-14)则签名为 (e,z1,z2)(5-15)V,mhn,ergVrmod21第5章 签名与认证其中:(5-16)在签名过程中，虽然签名者用的是自己随机选择的r1、r2和sA，但是他还必须使用来自权威的 ，由于 掌握在权威手里，这就留下了能被权威
21、辨认的把柄。nxrf ,zesrzeAA mod mod2211dsGAAgIDxAsg 签名验证算法签名验证算法 计算nzgIDVzeG mod 21(5-17)验证 是否成立。显然在这个验证算法中，仅使用了用户组身份IDG和公钥g和，并没有涉及A的身份问题，所以不会暴露是谁签的名。)(,mVhe 第5章 签名与认证 验证签名时，只需验证e是否等于 即可。但为了说明该验证方法是合理的，则应当在此证明 。实际上：)(,mVhVV eAesreGeA)esr(eGzeGxrggIDnxrgIDnzgIDVAA222111 mod)(mod因为 eseGedsGeAAAgIDgIDx所以 VrgV
22、r21第5章 签名与认证 身份验证算法身份验证算法 在发生争议需验证是不是A签的名时，权威部门可用A发给他的 来验证：AsgngrVgeszA mod)(21(5-18)计算中所需要的r2可以由 得到(因为 )，并不需要A提供任何信息(正因为A不愿暴露身份才需要权威部门出来验证)，仅由签名(e,z1,z2)和用户组权威部门掌握的 和xA，就可以验证A的身份。实际上，不难证明：eA22xzrnxr zeA mod 22Asg111)(mod 222zesresres-gggrrgngrVAAA第5章 签名与认证5.1.6多重数字签名多重数字签名 多重数字签名(DigitalMultisignat
23、ure)是一种要求多人对同一消息进行签名的数字签名方案，只有所有成员都正确完成了签名，签名才有效。根据签名过程的不同，可分为广播式(Broadcasting)和顺序式(Sequential)两种。1ElGamal顺序式多重数字签名方案顺序式多重数字签名方案 顺序式多重数字签名方案的流程如图5.1所示。图5.1中,U1Un是n个签名者，顺序进行签名，并且每人签名时要验证上一签名者的签名的有效性，否则终止签名过程。第5章 签名与认证图5.1顺序式多重数字签名方案流程 第5章 签名与认证 (1)系统初始化。选择大素数p，它满足Zp中离散对数复杂性。g是GF(p)的本原元素。函数h是GF(p)GF(p
24、)的单向Hash函数。每一签名者Ui(i=1,2,n)的私钥是xi1,p-1，公钥是yi=mod p,其中，p、g、yi和h()公开，xi由Ui密管。(2)签名算法。签名者Ui收到前一人的签名消息后(m1,(si-1,ri-1)后(第一个签名者取s0=0)，先验证，然后随机选取ki1,p-1，计算：pgriki mod 和)(mod 1pk-rxmssiiii-i(5-19)这里,m=h(m)。之后，将(m1,(si,ri)发送给下一签名者Ui+1，并将ri发给Ui以后的所有人。第5章 签名与认证 (3)验证算法。Ui对U1,U2,Ui-1签名有效性的验证是看等式：pyrgijmjijrjsj
25、i mod 11111(5-20)是否成立。实际上，由)(mod 1pkrxmssiiii-i就有)(mod 10pkrxmssijjjji第5章 签名与认证注意,若s0=0就有：)(mod 11pskrxmijijjjij因此，对任意i有下列等式恒成立：pggijjijijjpxmpskr mod11 mod mod 即 pyrgijmjijrjsii mod 11111第5章 签名与认证 验证者Ur对最后的结果进行验证时，只需在上式中取i-1=n即可：pyrgnjmjnjrjsin mod 11(5-21)2Harn广播多重数字签名方案广播多重数字签名方案 Harn广播多重数字签名方案如图
26、5.2所示。(1)系统初始化。选择大素数p,它满足Zp中离散对数复杂性。g是GF(p)的本原元素。函数h是GF(p)GF(p)的单向Hash函数。每一签名者Ui(i=1,2,n)的私钥是xi1,p-1，公钥是 ,其中p、g、yi和h()公开。pgyixi mod 第5章 签名与认证图5.2 广播多重数字签名方案流程 第5章 签名与认证 (2)单用户签名的产生。用户Ui收到消息后，计算 m=h(m)(5-22)然后随机选取ki1,p-1，计算 (5-23)将ri发给其他各个签名者Uj(ji)。等收到各个用户发来的rj后，计算：pgriki mod prRnirii mod 1(5-24)和)(m
27、od)(pkrxmRsiiii(5-25)最后将签名消息(m,(si,ri)发给签名收集者Uc。第5章 签名与认证 (3)单用户签名的验证。Uc收到Ui的签名消息后，计算:prRnirii mod 1(5-26)通过验证方程:pygrRmisriii mod(5-27)来验证Ui签名的有效性。实际上，因为 pxmRkrsiiii mod)(所以 pypyyggggrRmpRmpRmxpmodx)Rmsrksriiiiiiii mod mod )()()()()(第5章 签名与认证 只有各Ui的签名均有效，才能计算多重签名：S=s1+s2+sn mod p-1否则就终止签名。(R,S)即为多重签
28、名。(4)多重签名的验证。验证者UV验证Ver(m,r,s)=TURE的方法是：niRmisyRg1(5-28)理由是：niRmipnimRnipx)mRnipsrkpsssniriSpypyygggrRgiiiini1)1(1)(1)1mod(1)1(mod)()1)mod(1 mod mod 21第5章 签名与认证5.1.7代理数字签名代理数字签名 设A、B是两用户，他们的私钥和公钥分别为(xA,yA)和(xB,yB)。如果满足以下条件：(1)A利用他的秘密密钥xA计算出一个数,并将秘密交给B。(2)任何人，包括B试图求出xA时，不会对他有任何帮助。(3)B可以用和xB生成一个新的签名密钥
29、AB，并做签名s=Sig(AB,m)。(4)存在一个公开的验证算法VerAB，使其对任何sS和mM,都有：VerAB(yA,s,m)=TURE Sig(AB,m)式中：S是所有签名的集合；M是所有明文的集合。第5章 签名与认证 也就是说，对任何消息m及它的签名s，均可用A的公钥来验证。(5)任何人在试图求出xA、xB、或AB时，Sig(AB,m)都不会对他产生帮助。那么就说，用户A将他的签名权力委托给了用户B，称A为B的原始签名人，B为A的代理签名人，为托管密钥，AB为代理托管密钥，Sig(AB,m)是对消息m做的A的代理签名。能够产生代理签名的体制则称为代理签名系统。下面介绍一种基于离散对数
30、的代理签名体制。第5章 签名与认证 系统参数系统参数 (M,A,K,S,V)是基于离散对数的数字签名体制，其参数p、q、g满足：p是大素数，在Zp中离散对数是难解的;q是大素数,且q|p-1;g 是Zp域中q次单位元根。用户A和B的私钥分别是(xA,yA)和(xB,yB)，其中：(5-29)委托过程委托过程 A随机选择一整数k ，计算：r=gk mod p,=xA+kr mod g (5-30)将(,r)秘密传给B,B收到后验证等式g=yArr mod p是否成立。pZpgyAxA mod pgyBxB mod 第5章 签名与认证 代理签名的生成算法代理签名的生成算法 对于待签消息m，B生成普
31、通的数字签名：s=Sig(,m)比如 s=(xB+m)mod g (5-31)将(s,r)作为他代表A对消息m的数字签名，此即代理签名。代理签名的验证算法代理签名的验证算法 当代理签名的接收者收到消息m和代理签名(s,r)后，计算：v=yArr mod p (5-32)验证：Ver(yA,(s,r)=TURE Ver(v,s,m)=TURE比如验证：gs=yBvm mod p (5-33)第5章 签名与认证证明证明pggggryvkrxkrxrAAA mod 表明v可作为密钥的验证公钥。由对m所作数字签名s=Sig(,m)就可由Ver(v,s)=m来校验。证明：pggggvysmxmxmBBB
32、 mod)(代理数字签名的安全性如下：(1)基本不可伪造性：B不能根据(,r)求出xA，就无法伪造A的普通签名。(2)代理签名的不可伪造性：除A、B以外的人无法伪造有意义的代理签名。第5章 签名与认证 (3)代理签名的可区分性：代理签名由普通签名s和另一部分r组成，很容易与普通签名区分开来。如果同一人委托有两个代理人签名A的(s,r)和C的(s,r2)，则由rr2也很容易加以区分。(4)不可抵赖性：A自然不能抵赖他传给B的(,r)，而B却可以说是A代理B而不是B代理A，所以B必须是A的充分信任者。(5)身份证实性：A见到一个代理签名(s,r)时，可以由r知道是B代理的。(6)可注销性：A可以注
33、销B的代理权，只需向大家声明r作废就可以。第5章 签名与认证5.2单向散列单向散列(Hash)函数函数5.2.1概述概述 单向散列函数(Hash函数)也叫杂凑函数，在上段所讲的数字签名中已多次出现过。它实际上是一种特殊的压缩算法，它把任意长度的消息m压缩成一定长度(如128bit、160bit)的代码串(称之为消息摘要)。这种算法h(m)应当保证原消息的每一符号与压缩结果相关联，以至于任意改变原消息的一个符号时将导致其信息摘要一半以上的bit变化。它还要求：(1)h(m)应能对任意长度的消息m做计算。(2)计算h(m)的值h是容易的，而由h计算m是不可行的(单向性)。第5章 签名与认证 (3)
34、对于算法h(m)，要找出两个不同消息m1和m2有相同的摘要值：h(m1)=h(m2)(5-34)是非常困难的(或者说是不可行的)。因此，h(m)可作为m的“指纹”或“缩影”方便地保存。当原文档m被传输或转存后，可再次计算其摘要值，比较是否变化(因为摘要值“放大”了文档的差别)，以判断原文档是否被有意或无意改动过。可见，单向散列函数最基本的功能是对文件做“完整性”检验。其次，如果在计算摘要值的时候，必须利用发信人(作者)的私钥，则这个摘要值也就有了数字签名的功效。这样的签名短小方便，便于附于文后传输。因此摘要算法常常以多种方式与数字签名相结合使用。第5章 签名与认证下面介绍单向散列函数的常用构造
35、方法。5.2.2用分组加密函数构造散列函数用分组加密函数构造散列函数 第2章讲的分组加密算法,如DES，它将明文m分成长为64bit的许多小段m1m2mn，使用64bit的密钥，一段一段地加密，联结起来就是密文。现在可以把m1加密得到的64 bit的密文段c1作为密钥，去对m2加密，用得到的结果c2作为密钥，再对m3加密，如此下去，直到最后得到mn的密文cn，则cn就是所求得的64 bit的信息摘要。1.Rabin方案方案 Rabin方法加密产生信息摘要的方案如图5.3所示。第5章 签名与认证图5.3 Rabin方法加密产生信息摘要的方案 第5章 签名与认证 这种反复迭代计算，还可有多种不同方
36、式，如利用分组链接方案、密文链接方案和密钥链接方案加密产生信息摘要，分别如图5.45.6所示。分组链接方案中，每次ci与mi+1按位模2加后，送入加密器进行加密。第5章 签名与认证图5.4 分组链接产生信息摘要的方案第5章 签名与认证图5.5 密文链接产生信息摘要的方案 第5章 签名与认证图5.6 密钥链接产生信息摘要的方案 第5章 签名与认证5.2.3用候选单向函数构造散列函数用候选单向函数构造散列函数 (1)若 f=f(n,e)为RSA函数 令 h0=IV(初始值)(5-35)则 hi=(mi+hi-1)e mod n i=1,2,3,t (5-36)(2)若 f=f(p,g)为离散对数函
37、数 令 h0=IV(初始值)(5-37)则 i=1,2,3,t (5-38)总之，任何一种单向函数，迭代使用时都可构造h(m)函数。pghiimhi mod 1第5章 签名与认证5.2.4软件算法软件算法MD4 MD4算法是一种通过计算机程序将任意长消息压缩为128bit消息摘要的算法。首先将明文x按512bit分段，最后不足512bit的部分，扣除末尾64bit后添一个1和d个0，凑成448bit，再把这64bit加在末尾，使之也成为512bit的一段，共有N段。软件依次处理各个段落，每次把512bit的一个段落分组成32bit的16小段，装入数组：M=M0,M1,M15(5-39)(1)给
38、四个寄存器A、B、C、D赋初值，初值的十六进制表达为A=67452301，B=efcdab89，C=98badcfe，D=10325476(5-40)每符号4bit，A、B、C、D都是32bit的寄存器，正好可存数组的一个单元。第5章 签名与认证 (2)将A、B、C、D的数据拷贝到另外四个寄存器AA、BB、CC、DD中备用，而A、B、C、D作为计算过程中的变量使用。所用到的运算符号说明如下：xy表示按位逻辑与运算；xy表示按位逻辑或运算 xy表示按位逻辑异或运算；表示按位逻辑非运算 x+y表示整数的模232加法；xs表示x循环左移s位(0s31)(3)fori=0 to(N-1)do(循环处理
39、各个512 bit 的段落)(4)for j=0 to 15do(循环处理16个32bit数组单元)Xj=Mj(一次将一个32bit装入数组Xj中)x第5章 签名与认证 (5)执行第一轮：for k=0 to 3 do A=A+f(B,C,D)+X4k3 D=D+f(A,B,C)+X4k+17 C=C+f(D,A,B)+X4k+211 B=B+f(C,D,A)+X4k+319其中：f(x,y,z)=(xy)(z)(5-41)(6)执行第二轮：for k=0to3do A=A+g(B,C,D)+Xk+5a8279993 D=D+g(A,B,C)+X4+k+5a8279995 C=C+g(D,A,
40、B)+X8+k+5a8279999 B=B+g(C,D,A)+X12+k+5a82799913其中：g(x,y,z)=(xy)(xz)(yz)(5-42)x第5章 签名与认证 (7)执行第三轮：for k=0 to3do A=A+h(B,C,D)+X0+6ed9eba13 D=D+h(A,B,C)+X8+6ed9eba19 C=C+h(D,A,B)+X4+6ed9eba111 B=B+h(C,D,A)+X12+6ed9eba115 A=A+h(B,C,D)+X2+6ed9eba13 D=D+h(A,B,C)+X10+6ed9eba19 C=C+h(D,A,B)+X6+6ed9eba111 B=
41、B+h(C,D,A)+X14+6ed9eba115 A=A+h(B,C,D)+X1+6ed9eba13 D=D+h(A,B,C)+X9+6ed9eba19 C=C+h(D,A,B)+X5+6ed9eba111 第5章 签名与认证 B=B+h(C,D,A)+X13+6ed9eba115 A=A+h(B,C,D)+X3+6ed9eba13 D=D+h(A,B,C)+X11+6ed9eba19 C=C+h(D,A,B)+X7+6ed9eba111 B=B+h(C,D,A)+X15+6ed9eba115其中：h(x,y,z)=xyz (5-43)(8)再令AA=A+AA，BB=B+BB，CC=C+CC
42、，DD=D+DD (5-44)回到(3)，处理下一个512bit段落，直至全部。(9)最后将四个寄存器AA、BB、CC、DD中的432bit链接,即得到128bit的消息摘要。第5章 签名与认证5.2.5MD5算法算法 MD5是对MD4的改进，消息分组方式不变。但初始值变为 A=0 x01234567,B=0 x89abcdef C=0 xfedcba98,D=0 x76543210 (5-45)它用到的四个非线性函数是：，)()()(zxyxz,y,xF)()(),(zyzxzyxG，zyx)z,y,x(H)(),(zxyzyxI(5-46)并且引入以下四个符号表示四种运算过程，各自引用不同
43、的非线性函数：FF(a,b,c,d,Mj,s,ti)表示a=b+a+F(b,c,d)+Mj+tis第5章 签名与认证 GG(a,b,c,d,Mj,s,ti)表示a=b+a+G(b,c,d)+Mj+tis HH(a,b,c,d,Mj,s,ti)表示a=b+a+H(b,c,d)+Mj+tis II(a,b,c,d,Mj,s,ti)表示a=b+a+I(b,c,d)+Mj+tis (5-47)512bit的信息段被放入16个数组单元Mj中，各32bit，进行4轮加密，每轮循环16次，每次分别对一个数组单元进行，共64次。各次处理过程的程序全都相同，都是在4个变量中进行运算，先把其中3个变量进行非线性运
44、算，然后加上第4个变量，再与一个数组单元内的被处理信息和一个常数ti相加，之后循环左移s位，最后加上3个变量中的第一个，将结果赋予第4个变量。而64次处理过程的区别在于：A、B、C、D四个变量与a、b、c、d四个形参的对应关系不同，每次引用的信息数组单元Mj不同，所加常数ti不同，循环左移位数s不同，4大轮所用的非线性运算函数也不同。第5章 签名与认证第一轮是：FF(A,B,C,D,X0,7,0 xd76aa478)FF(D,A,B,C,X1,12,0 xe8c7b756)FF(C,D,A,B,X2,17,0 x242070db)FF(B,C,D,A,X3,22,0 xc1bdceee)FF(
45、A,B,C,D,X4,7,0 xf57c0faf)FF(D,A,B,C,X5,12,0 x4787c62a)FF(C,D,A,B,X6,17,0 x48304613)FF(B,C,D,A,X7,22,0 xfd469501)FF(A,B,C,D,X8,7,0 x698098d8)FF(D,A,B,C,X9,12,0 x8b44f7af)FF(C,D,A,B,X10,17,0 xffff5bb1)FF(B,C,D,A,X11,22,0 x895cd7be)第5章 签名与认证 FF(A,B,C,D,X12,7,0 x6b901122)FF(D,A,B,C,X13,12,0 xfd987193)FF
46、(C,D,A,B,X14,17,0 xa679438e)FF(B,C,D,A,X15,22,0 x49b40821)第二轮是：GG(A,B,C,D,X1,5,0 x561e2562)GG(D,A,B,C,X6,9,0 xc040b340)GG(C,D,A,B,X11,14,0 x265e5a51)GG(B,C,D,A,X0,20,0 xe96607aa)GG(A,B,C,D,X5,5,0 xd62f105d)GG(D,A,B,C,X10,9,0 x02441053)GG(C,D,A,B,X15,14,0 xd8a1e681)GG(B,C,D,A,X4,20,0 xe7d3fbc8)第5章 签名
47、与认证 GG(A,B,C,D,X9,5,0 x21e1cde6)GG(D,A,B,C,X14,9,0 xc33707d6)GG(C,D,A,B,X3,14,0 xf4d50d87)GG(B,C,D,A,X8,20,0 x455a14ed)GG(A,B,C,D,X13,5,0 xa9e3e905)GG(D,A,B,C,X2,9,0 xfcefa3f8)GG(C,D,A,B,X7,14,0 x676f02d9)GG(B,C,D,A,X12,20,0 x8d2a4c8a)第三轮是：HH(A,B,C,D,X5,4,0 xfffa3942)HH(D,A,B,C,X8,11,0 x87715681)HH(
48、C,D,A,B,X11,16,0 x6d9d6112)HH(B,C,D,A,X14,23,0 xfde5380c)第5章 签名与认证HH(A,B,C,D,X1,4,0 xa4beea44)HH(D,A,B,C,X4,11,0 x4bdecfa9)HH(C,D,A,B,X7,16,0 xf6bb4b60)HH(B,C,D,A,X10,23,0 xbebf6c70)HH(A,B,C,D,X13,4,0 x289b7ec6)HH(D,A,B,C,X0,11,0 xeaa107fa)HH(C,D,A,B,X3,16,0 xd4ef3085)HH(B,C,D,A,X6,23,0 x04881d05)HH
49、(A,B,C,D,X9,4,0 xd9d4d039)HH(D,A,B,C,X12,11,0 xe6db99e5)HH(C,D,A,B,X15,16,0 x1fa27cf8)HH(B,C,D,A,X2,23,0 xc4ac5665)第5章 签名与认证 第四轮是:II(A,B,C,D,X0,6,0 xf4292244)II(D,A,B,C,X7,10,0 x432aff97)II(C,D,A,B,X14,15,0 xab9423a7)II(B,C,D,A,X5,21,0 xfc93a039)II(A,B,C,D,X12,6,0 x655b59c3)II(D,A,B,C,X3,10,0 x8f0cc
50、c92)II(C,D,A,B,X10,15,0 xffeff47d)II(B,C,D,A,X1,21,0 x85845dd1)II(A,B,C,D,X8,6,0 x6fa87e4f)II(D,A,B,C,X15,10,0 xfe2ce6e0)第5章 签名与认证 II(C,D,A,B,X6,15,0 xa3014314)II(B,C,D,A,X13,21,0 x4e0811a1)II(A,B,C,D,X4,6,0 xf7537e82)II(D,A,B,C,X11,10,0 xbd3af235)II(C,D,A,B,X2,15,0 x2ad7d2bb)II(B,C,D,A,X9,21,0 xeb8
