公钥密码系统ppt课件.ppt

《公钥密码系统ppt课件.ppt》由会员分享，可在线阅读，更多相关《公钥密码系统ppt课件.ppt（96页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第4 4章章 公钥密码体系公钥密码体系 1为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security第第4 4章公钥密码体系章公钥密码体系第第4 4章章 公钥密码体系公钥密码体系 2为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security主要内容主要内容4.1 4.1 公钥密码概述公钥密码概述4.2 RSA4.2 RSA密码系统密码系统4.3 Dif

2、fie-Hellman4.3 Diffie-Hellman密钥交换密钥交换4.4 4.4 数字签名数字签名4.54.5数字签名的算法数字签名的算法4.6 PGP4.6 PGP第第4 4章章 公钥密码体系公钥密码体系 3为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益问题的提出：问题的提出：传统的对称加密仅用一个密钥，由发送方和接收方共享传统的对称加密仅用一个密钥，由发送方和接收方共享如果密钥公开，则通信是不安全的如果密钥公开，则通信是不安全的存在的存在的问题问题：无法保护发送方无法保护发送方，如果接收方伪造一个消息并宣称是由发

3、送，如果接收方伪造一个消息并宣称是由发送发发送的发发送的密钥的分配：密钥的分配：通信双方要进行加密通信，需要通过秘密的安通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，如何安全交换密钥？全信道协商加密密钥，如何安全交换密钥？密钥管理问题密钥管理问题 若若N N个人相互保密通信，每人必须拥有（个人相互保密通信，每人必须拥有（N-1)N-1)个密钥，个密钥，N N很大时，需要保存的密钥很多。如何解决？在有多很大时，需要保存的密钥很多。如何解决？在有多个用户的网络中，任何两个用户之间都需要有共享的密钥。个用户的网络中，任何两个用户之间都需要有共享的密钥。思考：需要的密钥量是多少？思考：需

4、要的密钥量是多少？Network and Information Security第第4 4章章 公钥密码体系公钥密码体系 4为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益挑战！挑战！Network and Information Security第第4 4章章 公钥密码体系公钥密码体系 5为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益公钥加密算法公钥加密算法Network and Information Security第第4 4章章 公钥密码体系公钥密

5、码体系 6为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security1公钥的起源公钥的起源公钥密码体系于公钥密码体系于1976年由美国斯坦福大学的年由美国斯坦福大学的W.Diffie和和M.Hellman提出。提出。公钥密码又叫公钥密码又叫非对称密码，非对称密码，这种密码体系的这种密码体系的基本思想基本思想:将密钥将密钥K一分为二，一个专门加密，一个专门解密，即一分为二，一个专门加密，一个专门解密，即kekd可以将可以将ke公开，密钥量小，分配比较简单公开，密钥量小，分配比

6、较简单有有ke不能计算出不能计算出kd，所以，所以kd便成为用户的指纹，实现数便成为用户的指纹，实现数字签名。字签名。4.1公钥密码概述公钥密码概述第第4 4章章 公钥密码体系公钥密码体系 7为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security2数学原理数学原理-陷门单向函数陷门单向函数公钥密码系统是公钥密码系统是基于陷门单向函数基于陷门单向函数的概念。的概念。陷陷门门单单向向函函数数：单单向向函函数数是是求求逆逆困困难难的的函函数数，而而单单向向陷陷门门函函数数，是

7、是在在不不知知陷陷门门信信息息下下求求逆逆困困难难的的函函数数，当当知知道道陷陷门门信信息息后后，求求逆是易于实现的。逆是易于实现的。单向陷门函数单向陷门函数f(x)，必须满足以下三个条件。，必须满足以下三个条件。给定给定x x，计算，计算y=f(x)y=f(x)是容易的；是容易的；给定给定y,y,计算计算x x使使y=f(x)y=f(x)是困难的（所谓计算是困难的（所谓计算x=fx=f-1-1(y)(y)困困难是指计算上相当复杂已无实际意义）；难是指计算上相当复杂已无实际意义）；存在存在，已知，已知时对给定的任何时对给定的任何y y，若相应的，若相应的x x存在，则存在，则计算计算x x使使

8、y=f(x)y=f(x)是容易的。是容易的。注注：仅满足仅满足(1)(1)、(2)(2)两条的称为单向函数；第两条的称为单向函数；第(3)(3)条称为条称为陷陷门性门性，称为陷门信息。称为陷门信息。第第4 4章章 公钥密码体系公钥密码体系 8为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security（1）发发送送者者用用加加密密密密钥钥PK（publickey）对对明明文文X加加密密后后，接接收收者者用用解密密钥解密密钥SK（securekey）解密，即可恢复出明文，或写为

9、：）解密，即可恢复出明文，或写为：DSK(EPK(X)X此外，加密和解密的运算可以对调，即此外，加密和解密的运算可以对调，即EPK(DSK(X)X。（2）加密密钥是公开的，但不能用它来解密，即）加密密钥是公开的，但不能用它来解密，即DPK(EPK(X)X（3）在计算机上可以容易地产生成对的）在计算机上可以容易地产生成对的PK和和SK。（4）从已知的）从已知的PK实际上实际上不可能推导出不可能推导出SK，即从，即从PK到到SK是是“计算计算上上不可行的不可行的”。（5）加密和解密算法都是公开的。）加密和解密算法都是公开的。3公开密钥算法的特点公开密钥算法的特点第第4 4章章 公钥密码体系公钥密码

10、体系 9为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益94.公钥密码系统可用于以下三个方面：公钥密码系统可用于以下三个方面：(1)通信保密：通信保密：此时将此时将公钥作为加密密钥，私钥作为解密密钥公钥作为加密密钥，私钥作为解密密钥，通信，通信双方不需要交换密钥就可以实现保密通信。这时，通过公钥或密文双方不需要交换密钥就可以实现保密通信。这时，通过公钥或密文分析出明文或私钥是不可行的。如图所示，分析出明文或私钥是不可行的。如图所示，Bob拥有多个人的公钥，拥有多个人的公钥，当他需要向当他需要向Alice发送机密消息时，他用发送

11、机密消息时，他用Alice公布的公钥对明文消息公布的公钥对明文消息加密，当加密，当Alice接收到后用她的私钥解密。由于私钥只有接收到后用她的私钥解密。由于私钥只有Alice本人知本人知道，所以能实现通信保密。道，所以能实现通信保密。第第4 4章章 公钥密码体系公钥密码体系 10为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益10(2)(2)数数字字签签名名：将将私私钥钥作作为为加加密密密密钥钥，公公钥钥作作为为解解密密密密钥钥，可可实实现现由由一一个个用用户户对对数数据据加加密密而而使使多多个个用用户户解解读读。如如图图所所

12、示示，BobBob用用私私钥钥对对明明文文进进行行加加密密并并发发布布，AliceAlice收收到到密密文文后后用用BobBob公公布布的的公公钥钥解解密密。由由于于BobBob的的私私钥钥只只有有BobBob本本人人知知道道，因因此此，AliceAlice看看到到的的明明文文肯肯定定是是BobBob发发出出的的，从从而而实实现了数字签名。现了数字签名。第第4 4章章 公钥密码体系公钥密码体系 11为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security (3)密钥交换密

13、钥交换：通信双方交换会话密钥，这种应：通信双方交换会话密钥，这种应用也称为用也称为混合密码系统混合密码系统，即用，即用常规密码体制加密常规密码体制加密需要保密传输的消息本身，然后用公钥密码体制需要保密传输的消息本身，然后用公钥密码体制加密常规密码体制中使用的会话密钥加密常规密码体制中使用的会话密钥，将两者结，将两者结合使用，充分利用对称密码体制在处理速度上的合使用，充分利用对称密码体制在处理速度上的优势和非对称密码体制在密钥分发和管理方面的优势和非对称密码体制在密钥分发和管理方面的优势。优势。第第4 4章章 公钥密码体系公钥密码体系 12为了规范事业单位聘用关系，建立和完善适应社会主义市场经济

14、体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第第4 4章章 公钥密码体系公钥密码体系 13为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第第4 4章章 公钥密码体系公钥密码体系 14为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security5对称密钥与非对称密钥的比较对称密钥与非对称密钥的比较第第4 4章章 公钥密码体系公钥密码体系 15为了规范事业单位聘用关系，建立和完善适应社会主义市场

15、经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security4.2RSA密码系统密码系统4.2.1RSA算法算法1977年由年由Rivest、Shamir和和Adleman在麻省理工学在麻省理工学院发明，院发明，1978年公布第一个比较完善的同时也是应年公布第一个比较完善的同时也是应用最广泛的公钥密码算法。用最广泛的公钥密码算法。第第4 4章章 公钥密码体系公钥密码体系 16为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益RSARSA的基本原理的基本原理:RS

16、A:RSA是基于大整数难分解的公钥密码技术。是基于大整数难分解的公钥密码技术。大整数的分解问题可以被表述：大整数的分解问题可以被表述：已知整数已知整数n n，n n是两个素是两个素数的积，即数的积，即n=p.q n=p.q。求解。求解p p、q q的值。的值。大整数分解是计算上困难的问题，目前还不存在一大整数分解是计算上困难的问题，目前还不存在一般性的有效解决算法。般性的有效解决算法。Network and Information Security第第4 4章章 公钥密码体系公钥密码体系 17为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和

17、职工的合法权益RSA的数学基础的数学基础除数除数(因子因子)：设设z为由全体整数而构成的集合，若为由全体整数而构成的集合，若b0且且a，b，mz，使得使得a=mb,此时称此时称b整除整除a.记为记为b a,还称还称b为为a的的除数除数(因子因子).素数：素数：对一个自然数对一个自然数P，如果，如果P只能被只能被1和自身除尽时，则称和自身除尽时，则称P为素数（或质数），否则为合数。为素数（或质数），否则为合数。例：例：100以内的素数共有以内的素数共有25个：个：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89

18、，97第第4 4章章 公钥密码体系公钥密码体系 18为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益最大公约数与互为素数：最大公约数与互为素数：设设且且a，b，cz，如果，如果c|a,c|b，称，称c是是a和和b的公约数。正整数的公约数。正整数d称为称为a和和b的最大公约数，如果它满足：的最大公约数，如果它满足：（1）d是是a和和b的公约数；的公约数；（2）对）对a和和b的任何一个公约数的任何一个公约数c，有，有c|d.a a和和b b的最大公约数记为的最大公约数记为gcd(a,b)=dgcd(a,b)=d。如果如果gcd(a

19、,b)=1gcd(a,b)=1，则称，则称a a与与b b是互素的，即是互素的，即a a和和b b互为素数。互为素数。例：例：8 8和和1515是互素的，即是互素的，即gcdgcd（8 8，1515）1 1。Network and Information Security第第4 4章章 公钥密码体系公钥密码体系 19为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益19整数同余：整数同余：设设n是一个正整数，是一个正整数，a,bZ，如果如果amodn=bmodn，则称，则称a和和b模模n同余，同余，记作记作ab(modn)，称整

20、数，称整数n为同余模为同余模。模模m求余运算称为求余运算称为模运算模运算,下面是模运算的一些性质。下面是模运算的一些性质。(1)(a+b)modm=(amodm)+(bmodm)modm(2)(a-b)modm=(amodm)-(bmodm)modm(3)(ab)mod m=(amodm)(bmodm)modm(4)(a(b+c)mod m=(ab)modm)+(ac)modm)modm(5)a8 mod m=(aaaaaaaa)modm化简为：化简为：(a2 modm)2 modm)2 modm 第第4 4章章 公钥密码体系公钥密码体系 20为了规范事业单位聘用关系，建立和完善适应社会主义市

21、场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益11mod8=3；15mod8=7（11+15）mod8=26mod8=2（11mod8）+（15mod8）mod8=（3+7）mod8=2（11-15）mod8=-4mod8=4（11mod8）-（15mod8）mod8=（3-7）mod8=4（11*15）mod8=165mod8=5（11mod8）*（15mod8）mod8=（3*7）mod8=5计算计算117mod13112=1214mod13114=（112）216mod133mod13117=11*112*11411*4*3mod13132mod132mod13第第4

22、 4章章 公钥密码体系公钥密码体系 21为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益加法逆元：加法逆元：对于对于a a Zn，存在，存在b b Zn，使得，使得a ab b0（mod nmod n）,则则b b是是a a的加法逆元。记的加法逆元。记b=-ab=-a。例：例：111115150（mod 26mod 26），则称），则称1111模模2626的加法逆元是的加法逆元是1515即即-11-11（代表（代表1111模模2626的加法逆元）的加法逆元）的结果为的结果为1515乘法逆元：乘法逆元：设设aZn，如果存在，如果

23、存在bZn满足满足ab1(modn)，则称，则称b是是a的模的模n乘法逆元，记为乘法逆元，记为x=a-1(modn)7151(mod26)，则称，则称7模模26的乘法逆元是的乘法逆元是15加法一定存在逆元，乘法不一定存在逆元。加法一定存在逆元，乘法不一定存在逆元。第第4 4章章 公钥密码体系公钥密码体系 22为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益22欧几里德算法欧几里德算法用途：用途：(1)求两个正整数的最大公约数求两个正整数的最大公约数性质性质1：对任意非负整数对任意非负整数a和正整数和正整数b，有，有gcd(a,

24、b)=gcd(b,amodb)(a=b)可重复使用上式求出最大公约数。重复计算结束的条件是可重复使用上式求出最大公约数。重复计算结束的条件是后一个整数后一个整数等于等于0，此时前一个数即为二者的最大公约数。，此时前一个数即为二者的最大公约数。例：求例：求gcd(18,12)=gcd(12,18mod12)=gcd(12,6)=gcd(6,12mod6)=gcd(6,0)=6第第4 4章章 公钥密码体系公钥密码体系 23为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Securit

25、y用途：用途：(2)两个正整数互素，可以求一个数关于两个正整数互素，可以求一个数关于另一个数的乘法逆元另一个数的乘法逆元性质性质2：若若gcd(n,a)=1,则则a在模在模n下有乘法逆元下有乘法逆元（设（设an）即存在）即存在x1时，时，(m)表示比表示比m小且与小且与m互素的正整互素的正整数的个数。数的个数。例：例：m24，比，比24小且与小且与24互素的正整数有：互素的正整数有：1、5、7、11、13、17、19、23，共，共8个。因此个。因此(24)81）m是素数，则是素数，则(m)=m-12)m=pq,且且p和和q是互异的素数，则是互异的素数，则(m)=(p)(q)=(p-1)(q-1

26、)例：例：(21)=(3)(7)=（3-1)(7-1)=12,这这12个数是个数是1,2,4,5,8,10,11,13,16,17,19,20欧拉定理：欧拉定理：对于任何互素的两个整数对于任何互素的两个整数a和和m，有，有a(m)1(modm)例：设例：设a=4，m=5则有则有(5)=4，44=256，2561(mod5)a(m)+1a(modm)第第4 4章章 公钥密码体系公钥密码体系 28为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益RSA密码算法密码算法RSA密码体制密码体制(安全性基于大整数因子分解的困难性）安全性基

27、于大整数因子分解的困难性）明文和密文均是明文和密文均是0到到n之间的整数，之间的整数，n通常为通常为1024位二进制位二进制数或数或309位十进制数位十进制数明文空间明文空间P=密文空间密文空间C=xZ|0 xn,Z为整数集合为整数集合。RSA密码的密码的密钥生成具体步骤密钥生成具体步骤如下：如下：选择选择互异的素数互异的素数p和和q，计算，计算n=pq，(n)=(p-1)(q-1)；选择整数选择整数e，使，使gcd(n),e)=1，且，且1e(n)；计算计算d，d e-1mod(n)，即，即d为模为模(n)下下e的乘法逆元；的乘法逆元；公钥公钥Pk=e,n，私钥，私钥Sk=d,n加密：加密：

28、c=memodn；解密解密：m=cdmodn。第第4 4章章 公钥密码体系公钥密码体系 29为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益RSA算法操作过程算法操作过程第第4 4章章 公钥密码体系公钥密码体系 30为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益RSA算法加密算法加密/解密过程解密过程第第4 4章章 公钥密码体系公钥密码体系 31为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权

29、益RSA算法的证明算法的证明第第4 4章章 公钥密码体系公钥密码体系 32为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例1：选选p=7，q=17。n=pq=119，(n)=(p-1)(q-1)=96。取取e=5，满足满足1e(n)，且且gcd(n),e)=1。确确定满足定满足de=1mod96且小于且小于96的的d，d77。因因此此公钥公钥为为5，119，私钥，私钥为为77，119。设设明文明文m=19，则由加密过程得密文为则由加密过程得密文为C195mod1192476099mod11966解解密密为为M6677mod

30、11919RSA加密和解密的例子：加密和解密的例子：在以下实例中只选取小数值的素数在以下实例中只选取小数值的素数p,q,以及以及e第第4 4章章 公钥密码体系公钥密码体系 33为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例2假设用户假设用户A需要将明文需要将明文“key”通过通过RSA加密后传递给用户加密后传递给用户B。（1）设计公私密钥）设计公私密钥(e,n)和和(d,n)。令令p=3，q=11，得出，得出n=pq=311=33；(n)=(p-1)(q-1)=210=20；取取e=3，（，（3与与20互质）则互质）则e

31、d1mod(n)，即，即3d1mod20。用扩展的欧几里德方法求得：用扩展的欧几里德方法求得：d=7。从而可以设计出一对公私密钥，从而可以设计出一对公私密钥，加密密钥（公钥）为：加密密钥（公钥）为：KU=(e,n)=(3,33)，解密密钥（私钥）为：解密密钥（私钥）为：KR=(d,n)=(7,33)。第第4 4章章 公钥密码体系公钥密码体系 34为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益(2)(2)英文数字化。英文数字化。将明文信息数字化。假定明文英文字母编码表为按字将明文信息数字化。假定明文英文字母编码表为按字母顺序排

32、列数值母顺序排列数值 则得到分组后的则得到分组后的keykey的明文信息为：的明文信息为：1111，0505，2525。34第第4 4章章 公钥密码体系公钥密码体系 35为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益（3）明文加密）明文加密用户加密密钥用户加密密钥(3,33)将数字化明文分组信将数字化明文分组信息加密成密文。由息加密成密文。由CMe(modn)得：得：得到相应的密文信息为：得到相应的密文信息为：11，26，16。C1(M1)e(mod n)=113(mod 33)=11C2(M2)e(mod n)=53(mo

33、d 33)=26C3(M3)e(mod n)=253(mod 33)=1635第第4 4章章 公钥密码体系公钥密码体系 36为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益（4 4）密文解密。）密文解密。用户用户B B收到密文，若将其解密，只需要计算收到密文，若将其解密，只需要计算 ，即：，即：用户用户B B得到明文信息为：得到明文信息为：1111，0505，2525。根据上面的编码表将其。根据上面的编码表将其转换为英文，我们又得到了恢复后的原文转换为英文，我们又得到了恢复后的原文“keykey”。2636第第4 4章章 公钥

34、密码体系公钥密码体系 37为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例3：设通信双方使用：设通信双方使用RSA加密体制，接收方的加密体制，接收方的公开密钥是（公开密钥是（5,35），接收到的密文是），接收到的密文是10，求，求明文。明文。Network and Information Security解：据题意知：解：据题意知：e=5，n=35，C=10因此有：因此有：(n）=(35）=(5）(7）=46=24d=e-1mod(n）=5-1mod24=5所以有：所以有：M=Cdmodn=105mod35=5第第4 4章

35、章 公钥密码体系公钥密码体系 38为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例4：已知：已知RSA密码体制的公钥为（密码体制的公钥为（11，51）（1）若明文）若明文M=3，求，求C（2）若截获得的密文）若截获得的密文C=9，求，求MNetwork and Information Security解：据题意知：解：据题意知：e=11，n=51因此有：因此有：(n）=(51）=(3）(17=216=32因为加密指数因为加密指数e和私密钥和私密钥d满足：满足：edmod(n)=1,所以所以d=e-1mod(n),私钥私钥d

36、的计算过程如下的计算过程如下第第4 4章章 公钥密码体系公钥密码体系 39为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security由以上计算可知私密钥由以上计算可知私密钥d=3。（1）若明文）若明文M=3，则，则C=Memodn=311mod51=24；（2）若截获得的密文）若截获得的密文C=9，则，则M=Cdmodn=93mod51=15循环次数循环次数QX1X2X3Y1Y2Y3初值初值无无103201111201111-210211-210-131第第4 4章章 公钥

37、密码体系公钥密码体系 40为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益实际运用时，要比这复杂得多。实际运用时，要比这复杂得多。由于由于RSARSA算法的公钥私钥的长度（模长度）要到算法的公钥私钥的长度（模长度）要到10241024位甚至位甚至20482048位才能保证安全，因此，位才能保证安全，因此，p p、q q、e e的的选取、公钥私钥的生成，加密解密模指数运算都有选取、公钥私钥的生成，加密解密模指数运算都有一定的计算程序，需要仰仗计算机的高速计算来完一定的计算程序，需要仰仗计算机的高速计算来完成。成。第第4 4章章

38、公钥密码体系公钥密码体系 41为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益RSA算法安全性算法安全性在在RSA密密码码应应用用中中，公公钥钥KU是是被被公公开开的的，即即e和和n的的数数值值可以被第三方得到。可以被第三方得到。破破解解RSA密密码码的的问问题题就就是是从从已已知知的的e和和n的的数数值值（n等等于于pq），设设法法求求出出d的的数数值值，这这样样就就可可以以得得到到私私钥钥来来破破解解密密文。文。RSA算算法法的的安安全全性性取取决决于于p、q的的保保密密性性，以以及及分分解解大大数数的的难度，所以在计算出

39、难度，所以在计算出n后要立即彻底删除后要立即彻底删除p、q值。值。当当前前运运用用计计算算机机和和素素数数理理论论，已已能能分分解解出出129位位长长的的十十进进制数。制数。密钥长度应在密钥长度应在1024位到位到2048位之间。位之间。第第4 4章章 公钥密码体系公钥密码体系 42为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对称密码体制中的一个苦恼对称密码体制中的一个苦恼如果有如果有n n个用户，需要两两共用个用户，需要两两共用1 1对密对密钥，一共需要多少对密钥？钥，一共需要多少对密钥？4.3 Diffie-Hellm

40、an密密钥交交换第第4 4章章 公钥密码体系公钥密码体系 43为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益怎样进行密钥协商怎样进行密钥协商一个生活中的例子一个生活中的例子在网络上，这样的秘密在网络上，这样的秘密“传递传递”能用数学方法实现吗？能用数学方法实现吗？第第4 4章章 公钥密码体系公钥密码体系 44为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3、一个基于离散对数的密钥协商协议、一个基于离散对数的密钥协商协议Diffie-Hellman密钥协商密

41、钥协商1976年，年，Diffie和和Hellman发表了一篇划时代的密码学论发表了一篇划时代的密码学论文文密码学新方向密码学新方向（NewDirectionsinCryptography），提出公钥密码模型。），提出公钥密码模型。第第4 4章章 公钥密码体系公钥密码体系 45为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益有限域上的离散对数问题有限域上的离散对数问题离散对数困难性难题：离散对数困难性难题：已知整数已知整数y、g、p求整数求整数x，这非常困难。，这非常困难。有多难有多难512bit离散对数困难度离散对数困难度1

42、024bit大整数分解难度大整数分解难度相当相当第第4 4章章 公钥密码体系公钥密码体系 46为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益数学知识数学知识生成元生成元素数素数p p的生成元（的生成元（primitive rootprimitive root）的定义：如果）的定义：如果a a是素数是素数p p的生成元，则数的生成元，则数a mod p,aa mod p,a2 2 mod p,mod p,a,ap-1p-1 mod p mod p是不同是不同的并且的并且包含从包含从1 1到到p-1p-1之间的所有整数的某种排列

43、之间的所有整数的某种排列。注：本原根不唯一。可验证注：本原根不唯一。可验证1919的本原根除了的本原根除了2 2、3 3外，还有外，还有1010、1313、1414、1515。第第4 4章章 公钥密码体系公钥密码体系 47为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益离散对数离散对数若若a a是素数是素数p p的一个生成元，则相对于任意整数的一个生成元，则相对于任意整数b b（b mod pb mod p0 0），必然存在唯一的整数），必然存在唯一的整数i i（1 1i ip-1p-1），使得），使得b ba ai i mo

44、d p mod p，称指数，称指数i i为以为以a a为底模为底模p p的的b b的的离散对数离散对数。对于对于函数函数y yg gx x mod p mod p，其中，其中，g g为素数为素数p p的生的生成元，成元，y y与与x x均为正整数，均为正整数，已知已知g g、x x、p p，计算，计算y y是容易的是容易的；而已知而已知y y、g g、p p，计算，计算x x是困难的是困难的，即求解即求解y y的离散对数的离散对数x x。注：离散对数的求解为数学界公认的困难问题。注：离散对数的求解为数学界公认的困难问题。第第4 4章章 公钥密码体系公钥密码体系 48为了规范事业单位聘用关系，建

45、立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security第第4 4章章 公钥密码体系公钥密码体系 49为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security第第4 4章章 公钥密码体系公钥密码体系 50为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益巧妙的巧妙的Diffie-Hellman密钥交换密钥交换现在

46、要在公开网络上协商一个公共密钥现在要在公开网络上协商一个公共密钥Kgxmodpgymodp发送方发送方计算计算(gy)xmodp接收方接收方计算计算(gx)ymodpKgxymodp第第4 4章章 公钥密码体系公钥密码体系 51为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益举例举例11319mod(2127-1)11323mod(2127-1)爱爱丽丽丝丝计计算算(11323)19mod(2127-1)鲍鲍勃勃计计算算(11319)23mod(2127-1)K309708883423153867577061032632581

47、0083第第4 4章章 公钥密码体系公钥密码体系 52为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益中间人攻击中间人攻击gxmodpgymodpgzmodpgzmodpK1=(gz)xmodpK2=(gz)ymodpK1=(gx)zmodpK2=(gy)zmodp第第4 4章章 公钥密码体系公钥密码体系 53为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益问题问题如何避免中间人的攻击？如何避免中间人的攻击？第第4 4章章 公钥密码体系公钥密码体系 61为了规

48、范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and Information Security图4-5 三方或多方的密钥交换 4.3.4 三方或多方Diffie-HellmanDiffie-Hellman密钥交换协议很容易扩展到三方或密钥交换协议很容易扩展到三方或多方的密钥交换。下例中，多方的密钥交换。下例中，Alice、Bob和和Carol一起产生一起产生秘密密钥秘密密钥。(1)Alice选选取取一一个个大大随随机机整整数数x，计计算算X=axmodp，然然后后把把X发发送给送给Bob；(2)Bob选取一个大随机

49、整数选取一个大随机整数y，计算，计算Y=aymodp，然后把，然后把Y发发送给送给Carol；(3)Carol选选取取一一个个大大随随机机整整数数z，计计算算Z=azmodp，然然后后把把Z发送给发送给Alice；(4)Alice计算计算Z=Zxmodp并发送并发送Z给给Bob；(5)Bob计算计算X=Xymodp并发送并发送X给给Carol；(6)Carol计算计算Y=Yzmodp并发送并发送Y给给Alice；第第4 4章章 公钥密码体系公钥密码体系 62为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Network and

50、 Information Security(7)Alice计算计算k=Yxmodp；(8)Bob计算计算k=Zymodp；(9)Carol计算计算k=Xzmodp。共共享享秘秘密密密密钥钥k等等于于axyzmodp。这这个个协协议议很容易扩展到更多方。很容易扩展到更多方。四方共享密钥要交换计算多少次信息？四方共享密钥要交换计算多少次信息？五方共享密钥要交换计算多少次信息？五方共享密钥要交换计算多少次信息？N个人共享密钥交换计算次数的公式个人共享密钥交换计算次数的公式n2第第4 4章章 公钥密码体系公钥密码体系 63为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘