公钥密码系统.ppt

CompanyLogo,1,导读,本章我们将讨论解密密钥与加密密钥不同的情况。非对称密码系统的解密密钥与加密密钥是不同的，一个称为公开密钥，另一个称为私人密钥（或秘密密钥），因此这种密码体系也称为公钥密码体系。公钥密码除可用于加密外，还可用于数字签名。中华人民共和国电子签名法已于2005年4月1日实行。,CompanyLogo,2,Contents,CompanyLogo,3,公钥密码概述,公钥的起源公钥密码体制于1976年由W.Diffie和M.Hellman提出，同时，R.Merkle也独立提出了这一体制。这种密码体制采用了一对密钥加密密钥和解密密钥(且从解密密钥推出加密密钥是不可行的)，这一对密钥中，一个可以公开(称之为公钥)，另一个为用户专用(私钥)。公开密钥密码体制的产生主要是因为两个方面的原因，一是由于常规密钥密码体制的密钥分配(distribution)问题，另一是由于对数字签名的需求。,CompanyLogo,4,公钥密码概述,陷门单向函数公钥密码系统是基于陷门单向函数的概念。单向函数是易于计算但求逆困难的函数，而陷门单向函数是在不知道陷门信息情况下求逆困难，而在知道陷门信息时易于求逆的函数。,CompanyLogo,5,公钥密码概述,公钥密码系统可用于以下三个方面：(1)通信保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实现保密通信。,CompanyLogo,6,公钥密码概述,(2)数字签名：将私钥作为加密密钥，公钥作为解密密钥，可实现由一个用户对数据加密而使多个用户解读。,CompanyLogo,7,公钥密码概述,(3)密钥交换：通信双方交换会话密钥，以加密通信双方后续连接所传输的信息。每次逻辑连接使用一把新的会话密钥，用完就丢弃。,CompanyLogo,8,公钥密码概述,公开密钥算法的特点:（1）发送者用加密密钥PK对明文X加密后，在接收者用解密密钥SK解密，即可恢复出明文，或写为：DSK(EPK(X)X解密密钥是接收者专用的秘密密钥，对其他人都保密。此外，加密和解密的运算可以对调，即EPK(DSK(X)X（2）加密密钥是公开的，但不能用它来解密，即DPK(EPK(X)X,CompanyLogo,9,公钥密码概述,（3）在计算机上可以容易地产生成对的PK和SK。（4）从已知的PK实际上不可能推导出SK，即从PK到SK是“计算上不可能的”。（5）加密和解密算法都是公开的。,CompanyLogo,10,Contents,CompanyLogo,11,RSA密码系统,公开密钥算法RSA(根据其发明者命名，即R.Rivest,A.Shamir和L.Adleman)。RSA密码系统的安全性基于大数分解的困难性。求一对大素数的乘积很容易，但要对这个乘积进行因式分解则非常困难，因此，可以把一对大素数的乘积公开作为公钥，而把素数作为私钥，从而由一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。公钥密码系统一般都涉及数论的知识，如素数、欧拉函数、中国剩余定理等等。,CompanyLogo,12,1000以内的素数（部分）,311*709=220499220499=？*？,CompanyLogo,13,RSA密码系统,（1）加密算法若用整数X表示明文，用整数Y表示密文(X和Y均小于n)，则加密和解密运算为：加密：YXemodn解密：XYdmodn,CompanyLogo,14,RSA密码系统,（2）密钥的产生现在讨论RSA公开密钥密码体制中每个参数是如何选择和计算的。计算n。用户秘密地选择两个大素数p和q，计算出npq。n称为RSA算法的模数。计算(n)。用户再计算出n的欧拉函数(n)(p1)(q1)。选择e。用户从1,(n)1中选择一个与(n)互素的数e作为公开的加密指数。,CompanyLogo,15,RSA密码系统,计算d作为解密指数。用户计算出满足下式的ded1mod(n)即：(ed1)mod(n)=0由此推出ed=t(n)+1(t是大于等于1的正整数）得出所需要的公开密钥和秘密密钥：公开密钥(即加密密钥)PKe,n秘密密钥(即解密密钥)SKd,n其中，p、q、(n)和d就是秘密的陷门(四项并不是相互独立的)，这些信息不可以泄露。,CompanyLogo,16,RSA密码系统,RSA加密消息m时(这里假设m是以十进制表示的)，首先将消息分成大小合适的数据分组，然后对分组分别进行加密。每个分组的大小应该比n小。设ci为明文分组mi加密后的密文，则加密公式为ci=mie(modn)解密时，对每一个密文分组进行如下运算：mi=cid(modn),CompanyLogo,17,RSA密码系统,例子:说明RSA的加/解密过程。选p=5，q=11，则n=pq=55，(n)=(p1)(q1)=40明文空间为在闭区间1,54内且不能被5和11整除的数。如果明文m同n不是互为素数，就有可能出现消息暴露情况，这样我们就可能通过计算n与加密以后的m的最大公约数来分解出n。,CompanyLogo,18,RSA密码系统,一个明文同n有公约数的概率小于1/p+1/q，因此，对于大的p和q来说，这种概率是非常小的。选择e=7，则d=23。由加/解密公式可以得到加密表如表4-1所示。,CompanyLogo,19,加密表,CompanyLogo,20,Contents,CompanyLogo,21,Diffie-Hellman密钥交换,Diffie-Hellman算法Diffie-Hellman算法是第一个公开密钥算法，发明于1976年。Diffie-Hellman算法能够用于密钥分配，但不能用于加密或解密信息。,CompanyLogo,22,Diffie-Hellman密钥交换,Diffie-Hellman算法的安全性在于在有限域上计算离散对数非常困难。定义素数p的本原根(PrimitiveRoot)为一种能生成1p1所有数的一个数，即如果a为p的本原根，则amodp，a2modp，ap1modp两两互不相同，构成1p1的全体数的一个排列(例如p=11，a=2)。对于任意数b及素数p的本原根a，可以找到一个惟一的指数i，满足：b=aimodp,0ip1称指数i为以a为底模p的b的离散对数。,CompanyLogo,23,Diffie-Hellman密钥交换,如果Alice和Bob想在不安全的信道上交换密钥，他们可以采用如下步骤：(1)Alice和Bob协商一个大素数p及p的本原根a，a和p可以公开；(2)Alice秘密产生一个随机数x，计算X=axmodp，然后把X发送给Bob；(3)Bob秘密产生一个随机数y，计算Y=aymodp，然后把Y发送给Alice；(4)Alice计算k=Yxmodp；(5)Bob计算k=Xymodp。,CompanyLogo,24,Diffie-Hellman密钥交换,k和k是恒等的，因为k=Yxmodp=(ay)xmodp=(ax)ymodp=Xymodp=k线路上的搭线窃听者只能得到a、p、X和Y的值，除非能计算离散对数，恢复出x和y，否则就无法得到k，因此，k为Alice和Bob独立计算的秘密密钥。,CompanyLogo,25,Diffie-Hellman密钥交换,下面用一个例子来说明上述过程。Alice和Bob需进行密钥交换，如图4-3所示，则：二者协商后决定采用素数p=353及其本原根a=3。Alice选择随机数x=97，计算X=397mod35340，并发送给Bob。Bob选择随机数y=233，计算Y=3233mod353248，并发送给Alice。Alice计算k=Yxmodp24897mod353=160。Bob计算k=Xymodp40233mod353=160。k和k即为秘密密钥.,CompanyLogo,26,Diffie-Hellman密钥交换,CompanyLogo,27,中间人攻击,Diffie-Hellman密钥交换容易遭受中间人攻击：(1)Alice发送公开值(a和p)给Bob，攻击者Carol截获这些值并把自己产生的公开值发送给Bob。(2)Bob发送公开值给Alice，Carol截获它然后把自己的公开值(a和p)发送给Alice。(3)Alice和Carol计算出二人之间的共享密钥k1。(4)Bob和Carol计算出另外一对共享密钥k2。,CompanyLogo,28,中间人攻击,CompanyLogo,29,中间人攻击,Alice用密钥k1给Bob发送消息；Carol截获消息后用k1解密就可读取消息；然后将获得的明文消息用k2加密(加密前可能会对消息作某些修改)后发送给Bob。对Bob发送给Alice的消息，Carol同样可以读取和修改。造成中间人攻击的原因是Diffie-Hellman密钥交换不认证对方。利用数字签名可以挫败中间人攻击。,CompanyLogo,30,认证的Diffie-Hellman密钥交换,密钥交换双方通过数字签名和公钥证书相互认证可以挫败中间人攻击。在密钥交换之前，密钥交换的双方Alice和Bob各自拥有公钥/私钥对和公开密钥证书，Alice和Bob签名算法和验证算法分别为SigA、SigB、VerA、VerB。可信中心TA也有一个签名方案，签名算法为SigTA，公开的签名验证算法为VerTA，Alice和Bob持有一个证书：C(A)=(ID(A),VerA,SigTA(ID(A),VerA)C(B)=(ID(B),VerB,SigTA(ID(B),VerB)其中ID(A)为用户身份信息,证书C(A)由TA事先签发,CompanyLogo,31,Alice和Bob产生共享秘密密钥的过程,(1)Alice秘密产生一个随机数x，计算X=axmodp，然后把X发送给Bob；(2)Bob秘密产生一个随机数y，首先计算Y=aymodp，然后计算k=Xymodp和yB=SigB(Y,X),最后，Bob把(C(B),Y,yB)发送给Alice；(3)Alice计算k=Yxmodp，并使用VerB验证yB，使用VerTA验证C(B)；计算yA=SigA(Y,X),并将结果(C(A),yA)发给用户Bob(4)Bob使用VerA验证yA,使用VerTA验证C(A)。,CompanyLogo,32,Alice和Bob产生共享秘密密钥的过程,简要分析抗击中间入侵攻击的过程。若攻击者Carol插在用户Alice和Bob之间，显然Carol可能截获Alice发送的X，并将其替换为X=axmodp,然后Carol截获Bob发送的Y=aymodp和SigB(Y,X)。攻击者Carol有可能将Y替换为Y=aymodp,或将SigB(Y,X)替换为SigB(Y,X)，但由于Carol不知道Bob的签名算法SigB，所以他无法计算SigB(Y,X)。同样，Carol也无法知道A的签名SigA。这样就达到了抗击中间人攻击的目的。,CompanyLogo,33,三方或多方Diffie-Hellman,CompanyLogo,34,三方或多方Diffie-Hellman,(1)Alice选取一个大随机整数x，计算X=axmodp，然后把X发送给Bob；(2)Bob选取一个大随机整数y，计算Y=aymodp，然后把Y发送给Carol；(3)Carol选取一个大随机整数z，计算Z=azmodp，然后把Z发送给Alice；(4)Alice计算Z=Zxmodp并发送Z给Bob；(5)Bob计算X=Xymodp并发送X给Carol；,CompanyLogo,35,三方或多方Diffie-Hellman,(6)Carol计算Y=Yzmodp并发送Y给Alice；(7)Alice计算k=Yxmodp；(8)Bob计算k=Zymodp；(9)Carol计算k=Xzmodp。共享秘密密钥k等于axyzmodp。这个协议很容易扩展到更多方。,CompanyLogo,36,Contents,CompanyLogo,37,数字签名,数字签名概述在文件上手写签名长期以来被用作作者身份的证明，或表示同意文件的内容。签名为什么会如此引人注目呢？1.签名是可信的。2.签名不可伪造。3.签名不可重用。4.签名的文件是不可改变的。5.签名是不可抵赖的。,CompanyLogo,38,数字签名,在现实生活中，关于签名的这些陈述没有一个是完全真实的。公钥密码学使得数字签名成为可能。用私钥加密信息，这时就称为对信息进行数字签名。将密文附在原文后，称为数字签名。其他人用相应的公钥去解密密文，将解出的明文与原文相比较，如果相同则验证成功，这称为验证签名。现在，已有很多国家制订了电子签名法。中华人民共和国电子签名法已于2004年8月28日第十届全国人民代表大会常务委员会第十一次会议通过，并已于2005年4月1日开始施行。,CompanyLogo,39,数字签名的方法,基本的数字签名协议是简单的：1.Alice用她的私钥对文件加密，从而对文件签名。2.Alice将签名的文件传给Bob。3.Bob用Alice的公钥解密文件，从而验证签名。这个协议不需要第三方去签名和验证。甚至协议的双方也不需要第三方来解决争端；如果Bob不能完成第3步，那么他知道签名是无效的。,CompanyLogo,40,这个协议也满足我们期待的特征：,1.签名是可信的。当Bob用Alice的公钥验证信息时，他知道是由Alice签名的。2.签名是不可伪造的。只有Alice知道她的私钥。3.签名是不可重用的。签名是文件的函数，并且不可能转换成另外的文件。4.被签名的文件是不可改变的。如果文件有任何改变，文件就不可能用Alice的公钥验证成功。5.签名是不可抵赖的。Bob不用Alice的帮助就能验证Alice的签名。,CompanyLogo,41,数字签名的方法,在实际的实现过程中，采用公钥密码算法对长文件签名效率太低。为了节约时间，数字签名协议经常和单向散列函数一起使用。Alice并不对整个文件签名，只对文件的散列值签名。1.Alice产生文件的散列值。2.Alice用她的私钥对散列值加密，凭此表示对文件签名。3.Alice将文件和散列签名送给Bob。4.Bob用Alice发送的文件产生文件的散列值，然后用Alice的公钥对签名的散列值解密。如果解密的散列值与自己产生的散列值相同，签名就是有效的。,CompanyLogo,42,多重签名,采用单向散列函数，是容易的：1.Alice对文件的散列值签名。2.Bob对文件的散列值签名。3.Bob将他的签名交给Alice。4.Alice把文件、她的签名和Bob的签名发给Carol。5.Carol验证Alice和Bob的签名。Alice和Bob能同时或顺序地完成1和2，Carol可以只验证其中一人的签名而不用验证另一人的签名。,CompanyLogo,43,带加密的数字签名,通过把公钥密码和数字签名结合起来，我们能够产生一个协议，可把数字签名的真实性和加密的安全性合起来。想象你写的一封信：签名提供了原作者的证明，而信封提供了秘密性。,CompanyLogo,44,带加密的数字签名,1.Ailce用她的私钥对信息签名：SA(M)2.Alice用Bob的公钥对签名的信息加密，然后送给Bob：EB(SA(M)3.Bob用他的私钥解密：DB(EB(SA(M)=SA(M)4.Bob用Alice的公钥验证并且恢复出信息：VA(SA(M)=M,CompanyLogo,45,Contents,CompanyLogo,46,数字签名算法DSA,1991年8月，美国NIST公布了用于数字签名标准DSS的数字签名算法DSA，1994年12月1日正式采用为美国联邦信息处理标准。DSA中用到了以下参数：(1)p为L位长的素数，其中，L为5121024之间且是64倍数的数。(2)q是160位长的素数，且为p-1的因子。(3)