《网络信息安全第四章公钥密码系统PPT课件》由会员分享，可在线阅读，更多相关《网络信息安全第四章公钥密码系统PPT课件（51页珍藏版）》请在金锄头文库上搜索。
1、Company LOGO第二部分第二部分 信息加密与信息隐藏信息加密与信息隐藏 第第4章章 公钥密码系统公钥密码系统 导读导读v本本章章我我们们将将讨讨论论解解密密密密钥钥与与加加密密密密钥钥不不同同的的情情况况。非非对对称称密密码码系系统统的的解解密密密密钥钥与与加加密密密密钥钥是是不不同同的的，一一个个称称为为公公开开密密钥钥，另另一一个个称称为为私私人人密密钥钥（或或秘秘密密密密钥钥），因因此此这这种种密密码码体体系系也也称称为为公公钥钥密密码码体体系系。公公钥钥密密码码除除可可用用于于加加密密外外，还还可可用用于于数数字字签签名名。中中华华人人民民共共和和国国电电子子签签名名法法已已于
2、于20052005年年4 4月月1 1日实行。日实行。2Contents公钥密码概述公钥密码概述1数字签名的算法数字签名的算法5 RSARSA密码系统密码系统2Diffie-HellmanDiffie-Hellman密钥交换密钥交换3数字签名数字签名43 公钥密码概述公钥密码概述v公钥的起源公钥的起源公钥密码体制于公钥密码体制于19761976年由年由W. DiffieW. Diffie和和M. HellmanM. Hellman提出，同时，提出，同时，R. MerkleR. Merkle也独立提出了这一体制。也独立提出了这一体制。这种密码体制采用了一对密钥这种密码体制采用了一对密钥加密密钥和
3、解加密密钥和解密密钥密密钥( (且从解密密钥推出加密密钥是不可行的且从解密密钥推出加密密钥是不可行的) )，这一对密钥中，一个可以公开，这一对密钥中，一个可以公开( (称之为称之为公钥公钥) )，另一个为用户专用另一个为用户专用( (私钥私钥) )。公开密钥密码体制的产生主要是因为两个方面的公开密钥密码体制的产生主要是因为两个方面的原因，一是由于常规密钥密码体制的密钥分配原因，一是由于常规密钥密码体制的密钥分配(distribution)(distribution)问题，另一是由于对数字签名的问题，另一是由于对数字签名的需求。需求。4公钥密码概述公钥密码概述v陷门单向函数陷门单向函数公钥密码系
4、统是基于陷门单向函数的概念。公钥密码系统是基于陷门单向函数的概念。 单单向向函函数数是是易易于于计计算算但但求求逆逆困困难难的的函函数数，而而陷陷门门单单向向函函数数是是在在不不知知道道陷陷门门信信息息情情况况下下求求逆逆困困难难，而而在在知知道道陷陷门门信信息息时时易易于于求求逆逆的函数。的函数。5公钥密码概述公钥密码概述v公钥密码系统可用于以下三个方面：公钥密码系统可用于以下三个方面： (1) 通通信信保保密密：此此时时将将公公钥钥作作为为加加密密密密钥钥，私私钥钥作作为为解解密密密密钥钥，通通信信双双方方不不需需要要交交换换密密钥钥就就可可以以实实现保密通信。现保密通信。 6公钥密码概述
5、公钥密码概述(2) (2) 数数字字签签名名：将将私私钥钥作作为为加加密密密密钥钥，公公钥钥作作为为解解 密密密密钥钥，可可实实现现由由一一个个用用户户对对数数据据加加密密而而使使多多个个用户解读。用户解读。7公钥密码概述公钥密码概述(3) (3) 密钥交换：通信双方交换会话密钥，以密钥交换：通信双方交换会话密钥，以 加密通信双方加密通信双方后续连接后续连接所传输的信息。所传输的信息。 每次逻辑连接使用一把新的会话密钥，每次逻辑连接使用一把新的会话密钥， 用完就丢弃。用完就丢弃。 8公钥密码概述公钥密码概述v公开密钥算法的特点公开密钥算法的特点: :（1 1）发发送送者者用用加加密密密密钥钥P
6、KPK对对明明文文X X加加密密后后，在在接接收收者者用解密密钥用解密密钥SKSK解密，即可恢复出明文，或写为：解密，即可恢复出明文，或写为：D DSKSK(E(EPKPK(X)(X) X X 解解密密密密钥钥是是接接收收者者专专用用的的秘秘密密密密钥钥，对对其其他他人人都保密。都保密。此外，加密和解密的运算可以对调，即此外，加密和解密的运算可以对调，即 E EPKPK(D(DSKSK(X) (X) X X（2 2）加密密钥是公开的，但不能用它来解密，即）加密密钥是公开的，但不能用它来解密，即D DPKPK(E(EPKPK(X)(X) X X 9公钥密码概述公钥密码概述（3 3）在在计计算算机
7、机上上可可以以容容易易地地产产生生成成对对的的PKPK和和SKSK。 （4 4）从从已已知知的的PKPK实实际际上上不不可可能能推推导导出出SKSK，即即从从PKPK到到SKSK是是“计算上计算上不可能的不可能的”。（5 5）加密和解密算法都是公开的。）加密和解密算法都是公开的。10ContentsRSA密码系统密码系统2数字签名的算法数字签名的算法5公钥密码概述公钥密码概述1Diffie-HellmanDiffie-Hellman密钥交换密钥交换3数字签名数字签名411 RSA密码系统密码系统v公开密钥算法公开密钥算法RSARSA ( (根据其发明者命名，即根据其发明者命名，即R. R. R
8、ivest, A. ShamirRivest, A. Shamir和和L. Adleman)L. Adleman)。 vRSARSA密码系统的安全性基于大数分解的困难性。密码系统的安全性基于大数分解的困难性。 v求一对大素数的乘积很容易，但要对这个乘积进求一对大素数的乘积很容易，但要对这个乘积进行因式分解则非常困难，因此，行因式分解则非常困难，因此，可以把一对大素可以把一对大素数的乘积公开作为公钥，而把素数作为私钥，数的乘积公开作为公钥，而把素数作为私钥，从从而由一个公开密钥和密文中恢复出明文的难度等而由一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。价于分解两个大素数之积。v公
9、钥密码系统一般都涉及数论的知识，如素数、公钥密码系统一般都涉及数论的知识，如素数、欧拉函数、中国剩余定理等等。欧拉函数、中国剩余定理等等。12RSA密码系统密码系统（1）加密算法）加密算法若若用用整整数数X表表示示明明文文，用用整整数数Y表表示示密密文文(X和和Y均均小小于于n)，则则加加密密和和解解密密运运算为：算为： 加密：加密：Y Xe mod n解密：解密：X Yd mod n 13RSA密码系统密码系统（2 2）密钥的产生）密钥的产生 现在讨论现在讨论RSARSA公开密钥密码体制中每个参数是如何公开密钥密码体制中每个参数是如何选择和计算的。选择和计算的。 计算计算n n。用户秘密地选
10、择两个大素数。用户秘密地选择两个大素数p p和和q q，计，计 算出算出n n pqpq。n n称为称为RSARSA算法的模数。算法的模数。 计算计算( (n n) )。用户再计算出。用户再计算出n n的欧拉函数的欧拉函数 ( (n n) ) ( (p p 1)( 1)(q q 1) 1) 。 选择选择e e。用户从。用户从1, 1, ( (n n) ) 1 1中选择一个中选择一个与与 ( (n n) )互素的数互素的数e e作为公开的加密指数。作为公开的加密指数。14RSA密码系统密码系统 计算计算d d作为解密指数。用户计算出满足下式的作为解密指数。用户计算出满足下式的d d ed ed
11、1mod(n)1mod(n) 即：即：(ed 1) mod(n)=0(ed 1) mod(n)=0由此推出由此推出 ed =t (n)+1 ed =t (n)+1 (t (t 是大于等于是大于等于1 1的正整数）的正整数） 得出所需要的公开密钥和秘密密钥：得出所需要的公开密钥和秘密密钥： 公开密钥公开密钥( (即加密密钥即加密密钥)PK )PK e, n e, n 秘密密钥秘密密钥( (即解密密钥即解密密钥)SK )SK d, n d, n 其中，其中，p p、q q、(n)(n)和和d d就是秘密的陷门就是秘密的陷门( (四项四项 并不是相互独立的并不是相互独立的) )，这些信息不可以泄露。
12、，这些信息不可以泄露。15RSA密码系统密码系统vRSA加加密密消消息息m时时(这这里里假假设设m是是以以十十进进制制表表示示的的)，首首先先将将消消息息分分成成大大小小合合适适的的数数据据分分组组，然然后后对对分分组组分分别别进进行行加加密密。每每个个分分组的大小应该比组的大小应该比n小。小。v设设ci为为明明文文分分组组mi加加密密后后的的密密文文，则则加加密密公式为公式为ci=mie (mod n)v解密时，对每一个密文分组进行如下运算：解密时，对每一个密文分组进行如下运算：mi=cid (mod n)16RSA密码系统密码系统v例子例子:说明说明RSA的加的加/解密过程。解密过程。 选
13、选p=5，q=11，则，则n=pq=55，(n)=(p1)(q1)=40v明文空间为在闭区间明文空间为在闭区间1, 54内且不能被内且不能被5和和11整除的数。如果明文整除的数。如果明文m同同n不是互为不是互为素数，就有可能出现消息暴露情况，这样素数，就有可能出现消息暴露情况，这样我们就可能通过计算我们就可能通过计算n与加密以后的与加密以后的m的最的最大公约数来分解出大公约数来分解出n。17RSA密码系统密码系统v一个明文同一个明文同n有公约数的概率小于有公约数的概率小于1/p+1/q，因此，对于大的，因此，对于大的p和和q来说，来说，这种概率是非常小的。选择这种概率是非常小的。选择e=7，则
14、，则d=23。由加。由加/解密公式可以得到加密表如解密公式可以得到加密表如表表4-1所示。所示。 18加加 密密 表表明文密文明文密文明文密文明文密文11149285242482181636293943323421783126465144918173243475364119243434482772821213631491482231237385169424293847521312232616391953371372734146545419ContentsDiffie-HellmanDiffie-Hellman密钥交换密钥交换3数字签名的算法数字签名的算法5 RSARSA密码系统密码系统2公钥密
15、码概述公钥密码概述1数字签名数字签名420Diffie-Hellman密钥交换密钥交换vDiffie-Hellman算法算法 Diffie-HellmanDiffie-Hellman算算法法是是第第一一个个公公开开密密钥钥算算法法，发发明明于于19761976年年。Diffie-HellmanDiffie-Hellman算算法法能能够够用用于于密密钥钥分分配配，但但不不能能用用于于加加密密或或解解密信息。密信息。21Diffie-Hellman密钥交换密钥交换vDiffie-HellmanDiffie-Hellman算算法法的的安安全全性性在在于于在在有有限限域域上上计计算离散对数非常困难。算
16、离散对数非常困难。 v定定义义素素数数p p的的本本原原根根(Primitive (Primitive Root)Root)为为一一种种能能生生成成1 1p p1 1所所有有数数的的一一个个数数，即即如如果果a a为为p p的的本本原原根根，则则a mod pa mod p，a a2 2 mod p mod p，a ap p1 1 mod p mod pv两两两两互互不不相相同同，构构成成1 1p p1 1的的全全体体数数的的一一个个排排列列( (例例如如p=11p=11，a=2)a=2)。对对于于任任意意数数b b及及素素数数p p的的本本原原根根a a，可以找到一个惟一的指数，可以找到一个
17、惟一的指数i i，满足：，满足：b = ab = ai i mod p, 0ip mod p, 0ip1 1v 称指数称指数i i为以为以a a为底模为底模p p的的b b的离散对数。的离散对数。22Diffie-Hellman密钥交换密钥交换v如如果果AliceAlice和和BobBob想想在在不不安安全全的的信信道道上上交交换换密密钥钥，他他们们可可以以采采用如下步骤：用如下步骤：(1)Alice(1)Alice和和BobBob协商一个大素数协商一个大素数p p及及p p的本原根的本原根a a，a a和和p p 可以公开；可以公开；(2)Alice(2)Alice秘密产生一个随机数秘密产生
18、一个随机数x x，计算，计算X=aX=ax x mod p mod p， 然后把然后把X X发送给发送给BobBob；(3)Bob(3)Bob秘密产生一个随机数秘密产生一个随机数y y，计算，计算Y= aY= ay y mod p mod p，然，然 后把后把Y Y发送给发送给AliceAlice；( (4)Alice4)Alice计算计算k=Yk=Yx x mod p mod p；(5)Bob(5)Bob计算计算k=Xk=Xy y mod p mod p。 23Diffie-Hellman密钥交换密钥交换 k k和和kk是恒等的，因为是恒等的，因为 k= Y k= Yx x mod p=(a
19、 mod p=(ay y) )x x mod p=(a mod p=(ax x) )y y mod p mod p = X = Xy y mod p = k mod p = kv线路上的搭线窃听者只能得到线路上的搭线窃听者只能得到a、p、X和和Y的值，的值，除非能计算离散对数，恢复出除非能计算离散对数，恢复出x和和y，否则就无法，否则就无法得到得到k，因此，因此，k为为Alice和和Bob独立计算的秘密独立计算的秘密密钥。密钥。24Diffie-Hellman密钥交换密钥交换v下下面面用用一一个个例例子子来来说说明明上上述述过过程程。AliceAlice和和BobBob需需进进行行密密钥钥交换
20、，如图交换，如图4-34-3所示，则：所示，则： 二者协商后决定采用素数二者协商后决定采用素数p=353p=353及其本原根及其本原根a=3a=3。 Alice Alice选择随机数选择随机数x=97x=97， 计算计算X=3X=39797 mod 353 mod 3534040，并发送给，并发送给BobBob。 Bob Bob选择随机数选择随机数y=233y=233， 计算计算Y=3Y=3233233 mod 353 mod 353248248，并发送给，并发送给AliceAlice。 Alice Alice计算计算k=Yk=Yx x mod p mod p2482489797 mod 35
21、3=160 mod 353=160。 Bob Bob计算计算k=Xk=Xy y mod p mod p4040233233 mod 353=160 mod 353=160。 k k和和kk即为秘密密钥即为秘密密钥. .25Diffie-Hellman密钥交换密钥交换26中间人攻击中间人攻击vDiffie-HellmanDiffie-Hellman密钥交换容易遭受密钥交换容易遭受中间人攻击中间人攻击：(1)(1)AliceAlice发发送送公公开开值值(a(a和和p)p)给给BobBob，攻攻击击者者CarolCarol截获这些值并把自己产生的公开值发送给截获这些值并把自己产生的公开值发送给Bo
22、bBob。(2)(2)BobBob发发送送公公开开值值给给AliceAlice，CarolCarol截截获获它它然然后后把把自己的公开值自己的公开值(a(a和和p)p)发送给发送给AliceAlice。(3)(3)AliceAlice和和CarolCarol计算出二人之间的共享密钥计算出二人之间的共享密钥k1k1。(4)(4)BobBob和和CarolCarol计算出另外一对共享密钥计算出另外一对共享密钥k2k2。27中间人攻击中间人攻击28中间人攻击中间人攻击vAlice用密钥用密钥k1给给Bob发送消息；发送消息；Carol截获消截获消息后用息后用k1解密就可读取消息；然后将获得的明文解密
23、就可读取消息；然后将获得的明文消息用消息用k2加密加密(加密前可能会对消息作某些修改加密前可能会对消息作某些修改)后发送给后发送给Bob。v对对Bob发送给发送给Alice的消息，的消息，Carol同样可以读同样可以读取和修改。造成中间人攻击的原因是取和修改。造成中间人攻击的原因是Diffie-Hellman密钥交换密钥交换不认证对方不认证对方。利用数字签名可。利用数字签名可以挫败中间人攻击。以挫败中间人攻击。29认证的认证的Diffie-Hellman密钥交换密钥交换v密密钥钥交交换换双双方方通通过过数数字字签签名名和和公公钥钥证证书书相相互互认认证证可可以以挫挫败败中中间间人人攻攻击击。在
24、在密密钥钥交交换换之之前前，密密钥钥交交换换的的双双方方AliceAlice和和BobBob各各自自拥拥有有公公钥钥/ /私私钥钥对对和和公公开开密密钥钥证证书书，AliceAlice和和BobBob签签名名算算法法和和验验证证算算法法分分别别为为SigSigA A、SigSigB B、VerVerA A、VerVerB B。可可信信中中心心TATA也也有有一一个个签签名名方方案案，签签名名算算法法为为SigSigTATA，公公开开的的签签名名验验证证算算法为法为VerVerTATA，AliceAlice和和BobBob持有一个证书：持有一个证书：C(A)=(ID(A), VerC(A)=(I
25、D(A), VerA A,Sig,SigTATA(ID(A),Ver(ID(A),VerA A)C(B)=(ID(B), VerC(B)=(ID(B), VerB B,Sig,SigTATA(ID(B),Ver(ID(B),VerB B)v其其中中ID(A)ID(A)为为用用户户身身份份信信息息, ,证证书书C(A)C(A)由由TATA事事先先签签发发 30AliceAlice和和BobBob产生共享秘密密钥的过程产生共享秘密密钥的过程(1) Alice(1) Alice秘密产生一个随机数秘密产生一个随机数x x，计算，计算X=aX=ax x mod mod p p，然后把，然后把X X发送给
26、发送给BobBob； (2) (2) BobBob秘秘密密产产生生一一个个随随机机数数y y，首首先先计计算算Y= Y= a ay y mod mod p p，然后计算，然后计算 k=Xk=Xy y mod pmod p 和和y yB B=Sig=SigB B(Y, X),(Y, X),最后，最后，BobBob把把(C(B),Y, y(C(B),Y, yB B) )发送给发送给AliceAlice；(3) (3) AliceAlice计计算算k=Yk=Yx x mod mod p p，并并使使用用VerVerB B 验验证证y yB B ，使使用用VerVerTATA验验证证C(B)C(B)；
27、计计算算y yA A=Sig=SigA A(Y, (Y, X),X),并并将将结结果果 (C(A),y(C(A),yA A) ) 发给用户发给用户BobBob(4) Bob(4) Bob使用使用VerVerA A 验证验证y yA A, ,使用使用VerVerTATA验证验证C(A)C(A)。31AliceAlice和和BobBob产生共享秘密密钥的过程产生共享秘密密钥的过程v简要分析抗击中间入侵攻击的过程。简要分析抗击中间入侵攻击的过程。v若若攻攻击击者者CarolCarol插插在在用用户户AliceAlice和和BobBob之之间间，显显然然CarolCarol可可能能截截获获AliceA
28、lice发发送送的的X X，并并将将其其替替换换为为X=aX=axxmod mod p,p,然然后后CarolCarol截截获获BobBob发发送送的的Y= Y= a ay y mod mod p p 和和SigSigB B(Y, (Y, X)X)。攻攻击击者者CarolCarol有有可可能能将将Y Y替替换换为为Y=aY=ayymod mod p,p,或或将将SigSigB B(Y, (Y, X X ) )替替换换为为SigSigB B(Y(Y , , X)X)，但但由由于于CarolCarol不不知知道道BobBob的的签签名名算算法法SigSigB B，所所以以他他无无法法计计算算Sig
29、SigB B(Y(Y , , X)X)。同同样样，CarolCarol也也无无法法知知道道A A 的的签签名名SigSigA A。这这样样就就达达到到了了抗抗击击中中间间人人攻攻击击的的目目的。的。32三方或多方三方或多方Diffie-Hellman33三方或多方三方或多方Diffie-Hellman(1) Alice选选取取一一个个大大随随机机整整数数x，计计算算X=ax mod p，然后把，然后把X发送给发送给Bob；(2) Bob选选取取一一个个大大随随机机整整数数y，计计算算Y= ay mod p，然后把，然后把Y发送给发送给Carol；(3) Carol选选取取一一个个大大随随机机整
30、整数数z，计计算算Z= az mod p，然后把，然后把Z发送给发送给Alice；(4) Alice计计算算Z= Zx mod p并并发发送送Z给给Bob；(5) Bob计计算算X= Xy mod p并并发发送送X给给Carol；34三方或多方三方或多方Diffie-Hellman(6) Carol计算计算Y= Yz mod p并发送并发送Y给给Alice；(7) Alice计算计算k= Yx mod p；(8) Bob计算计算k= Zy mod p；(9) Carol计算计算k= Xz mod p。 共共享享秘秘密密密密钥钥k等等于于axyz mod p。这这个个协协议议很很容容易扩展到更多
31、方。易扩展到更多方。35Contents数字签名数字签名4数字签名的算法数字签名的算法5 RSARSA密码系统密码系统2Diffie-HellmanDiffie-Hellman密钥交换密钥交换3公钥密码概述公钥密码概述136数字签名数字签名v数字签名概述数字签名概述 在在文文件件上上手手写写签签名名长长期期以以来来被被用用作作作作者者身身份份的的证证明明，或或表表示示同同意意文文件件的的内内容容。签签名名为为什什么么会会如如此此引人注目呢？引人注目呢？ 1. 1.签名是可信的。签名是可信的。 2. 2.签名不可伪造。签名不可伪造。 3. 3.签名不可重用。签名不可重用。 4. 4.签名的文件是
32、不可改变的。签名的文件是不可改变的。 5. 5.签名是不可抵赖的。签名是不可抵赖的。37数字签名数字签名v在现实生活中，关于签名的这些陈述没有一个是在现实生活中，关于签名的这些陈述没有一个是完全真实的。完全真实的。 公公钥钥密密码码学学使使得得数数字字签签名名成成为为可可能能。用用私私钥钥加加密密信信息息，这这时时就就称称为为对对信信息息进进行行数数字字签签名名。将将密密文文附附在在原原文文后后，称称为为数数字字签签名名。其其他他人人用用相相应应的的公公钥钥去去解解密密密密文文，将将解解出出的的明明文文与与原原文文相相比比较较，如如果相同则验证成功，这称为果相同则验证成功，这称为验证签名验证签
33、名。 现现在在，已已有有很很多多国国家家制制订订了了电电子子签签名名法法。中中华华人人民民共共和和国国电电子子签签名名法法已已于于20042004年年8 8月月2828日日第第十十届届全全国国人人民民代代表表大大会会常常务务委委员员会会第第十十一一次次会会议议通通过，并已于过，并已于20052005年年4 4月月1 1日开始施行。日开始施行。38数字签名的方法数字签名的方法基本的数字签名协议是简单的：基本的数字签名协议是简单的：1.Alice1.Alice用她的私钥对文件加密，从而对文件签名。用她的私钥对文件加密，从而对文件签名。2.Alice2.Alice将签名的文件传给将签名的文件传给Bo
34、bBob。3.Bob3.Bob用用AliceAlice的公钥解密文件，从而验证签名。的公钥解密文件，从而验证签名。v这这个个协协议议不不需需要要第第三三方方去去签签名名和和验验证证。甚甚至至协协议议的的双双方方也也不不需需要要第第三三方方来来解解决决争争端端；如如果果BobBob不不能能完成第完成第3 3步，那么他知道签名是无效的。步，那么他知道签名是无效的。39这个协议也满足我们期待的特征：这个协议也满足我们期待的特征：1.1.签签名名是是可可信信的的。当当BobBob用用AliceAlice的的公公钥钥验验证证信信息息时时，他知道是由他知道是由AliceAlice签名的。签名的。2.2.签
35、名是不可伪造的签名是不可伪造的。只有。只有AliceAlice知道她的私钥。知道她的私钥。3.3.签签名名是是不不可可重重用用的的。签签名名是是文文件件的的函函数数，并并且且不不可能转换成另外的文件。可能转换成另外的文件。4.4.被被签签名名的的文文件件是是不不可可改改变变的的。如如果果文文件件有有任任何何改改变，文件就不可能用变，文件就不可能用AliceAlice的公钥验证成功。的公钥验证成功。5.5.签签名名是是不不可可抵抵赖赖的的。BobBob不不用用AliceAlice的的帮帮助助就就能能验验证证AliceAlice的签名。的签名。40数字签名的方法数字签名的方法 在在实实际际的的实实
36、现现过过程程中中，采采用用公公钥钥密密码码算算法法对对长长文文件件签签名名效效率率太太低低。为为了了节节约约时时间间，数数字字签签名名协协议议经经常常和和单单向向散散列列函函数数一一起起使使用用。AliceAlice并并不不对对整整个个文件签名，只对文件的散列值签名。文件签名，只对文件的散列值签名。1.Alice1.Alice产生文件的散列值。产生文件的散列值。2.Alice2.Alice用用她她的的私私钥钥对对散散列列值值加加密密，凭凭此此表表示示对对文文件件签名。签名。3.Alice3.Alice将文件和散列签名送给将文件和散列签名送给BobBob。4.Bob4.Bob用用AliceAli
37、ce发发送送的的文文件件产产生生文文件件的的散散列列值值，然然后后用用AliceAlice的的公公钥钥对对签签名名的的散散列列值值解解密密。如如果果解解密密的的散散列列值值与与自自己己产产生生的的散散列列值值相相同同，签签名名就就是是有有效效的。的。41多重签名多重签名采用单向散列函数，是容易的：采用单向散列函数，是容易的：1.Alice1.Alice对文件的散列值签名。对文件的散列值签名。2.Bob2.Bob对文件的散列值签名。对文件的散列值签名。3.Bob3.Bob将他的签名交给将他的签名交给AliceAlice。4.Alice4.Alice把文件、她的签名和把文件、她的签名和BobBob
38、的签名发给的签名发给CarolCarol。5.Carol5.Carol验证验证AliceAlice和和BobBob的签名。的签名。 Alice Alice和和BobBob能同时或顺序地完成能同时或顺序地完成1 1和和2 2，CarolCarol可以可以只验证其中一人的签名而不用验证另一人的签名。只验证其中一人的签名而不用验证另一人的签名。42带加密的数字签名带加密的数字签名v通通过过把把公公钥钥密密码码和和数数字字签签名名结结合合起起来来，我我们们能能够够产产生生一一个个协协议议，可可把把数数字字签签名名的的真真实实性性和和加加密密的的安安全全性性合合起起来来。想想象象你你写写的的一一封封信信
39、：签签名名提提供供了了原原作作者者的证明，而信封提供了秘密性。的证明，而信封提供了秘密性。43带加密的数字签名带加密的数字签名1.Ailce1.Ailce用她的私钥对信息签名：用她的私钥对信息签名：S SA A(M)(M)2.Alice2.Alice用用BobBob的的公公钥钥对对签签名名的的信信息息加加密密，然然后后送送给给BobBob：E EB B(S(SA A(M)(M)3.Bob3.Bob用他的私钥解密：用他的私钥解密：D DB B(E(EB B(S(SA A(M)=S(M)=SA A(M)(M)4.Bob4.Bob用用AliceAlice的公钥验证并且恢复出信息：的公钥验证并且恢复出
40、信息：V VA A(S(SA A(M)=M(M)=M44Contents数字签名的算法数字签名的算法5数字签名数字签名4 RSARSA密码系统密码系统2Diffie-HellmanDiffie-Hellman密钥交换密钥交换3公钥密码概述公钥密码概述145数字签名算法数字签名算法DSADSAv19911991年年8 8月月，美美国国NISTNIST公公布布了了用用于于数数字字签签名名标标准准DSSDSS的的数数字字签签名名算算法法DSADSA，19941994年年1212月月1 1日日正正式式采采用用为为美美国国联联邦邦信信息息处处理标准。理标准。vDSADSA中用到了以下参数：中用到了以下参
41、数：(1) (1) p p为为L L位位长长的的素素数数，其其中中，L L为为51251210241024之之间间且且是是6464倍数的数。倍数的数。(2) (2) q q是是160160位长的素数，且为位长的素数，且为p-1p-1的因子。的因子。(3) (3) g=hg=h(p-1)/q(p-1)/q mod mod p p，其其中中，h h是是满满足足1 1h hp-1p-1且且h h(p-1)/q(p-1)/q mod p mod p大于大于1 1的整数。的整数。(4) (4) x x是随机产生的大于是随机产生的大于0 0而小于而小于q q的整数。的整数。(5) (5) y=gy=gx
42、x mod p mod p。(6) (6) k k是随机产生的大于是随机产生的大于0 0而小于而小于q q的整数。的整数。46数字签名算法数字签名算法DSADSAv前前三三个个参参数数p p、q q、g g是是公公开开的的；x x为为私私钥钥，y y为为公公钥钥；x x和和k k用用于于数数字字签签名名，必必须须保保密密；对对于于每每一一次次签签名名都都应应该该产产生生一一次次k k。v对消息对消息m m签名：签名：r = (gr = (gk k mod p) mod q mod p) mod qs = (ks = (k-1-1(SHA-1(m) + xr) mod q(SHA-1(m) +
43、xr) mod qr r和和s s就是签名。验证签名时，计算：就是签名。验证签名时，计算：w = sw = s-1-1 mod q mod qu1 = (SHA-1(m)w) mod qu1 = (SHA-1(m)w) mod qu2 = (rw) mod qu2 = (rw) mod qv = (gv = (gu1u1y yu2u2 ) mod p) mod q ) mod p) mod q如果如果v=rv=r，则签名有效。，则签名有效。 47RSA签名方案签名方案v前前面面提提到到RSA可可以以用用于于数数字字签签名名。根根据据4.1中中的的描描述述，我我们们可可以以获获得得私私钥钥d，公
44、公钥钥e和和n，则则对对消消息息m签名有签名有r=sig(m)=(H(m)d mod n 其其中中，H(m)计计算算消消息息m的的消消息息摘摘要要，可可由由散散列列函函数数SHA1或或MD5得得到到；r即即为为对对消消息息的的签名。签名。v 验证签名时，验证：验证签名时，验证：H(m)re mod nv 若上式成立，则签名有效。若上式成立，则签名有效。48RSA数字签名数字签名49小结v本本章章讨讨论论了了公公钥钥密密码码系系统统，这这种种密密码码体体制制采采用用了了一一对对密密钥钥公公钥钥和和私私钥钥，而而且且很很难难从从公公钥钥推推导导出出私私钥钥。首首先先介介绍绍了了RSARSA公公钥钥密密码码算算法法，然然后后介介绍绍了了Diffie-HellmanDiffie-Hellman密密钥钥交交换换。公公钥钥密密码码的的一一个个主主要要应应用用就就是是数数字字签签名名，这这时时用用私私钥钥加加密密而而用用公公钥钥解解密密，如如果果解解密密出出的的明明文文与与原原文文相相同同，则则验验证证签签名名通通过过。在在实实际际应应用用中中，通通常常不不直直接接对对消消息息签签名名，而而是是对对消消息息的的单单向向散散列列值值签签名名，这这具具有有很很多多优优点点。最后介绍了数字签名的算法最后介绍了数字签名的算法DSADSA和和RSARSA。50Company LOGO
