五公钥密码体制edit

1、112 Warm up 1. 2.23 解密是加密的逆运算解密是加密的逆运算: : Dk( )=( )=Ek-1-1( )( )； 解密与加密使用同样的密钥，解密与加密使用同样的密钥， 掌握了加密方法与密钥的人，就能解密。掌握了加密方法与密钥的人，就能解密。 这样的密码系统被称为这样的密码系统被称为对称密钥体系对称密钥体系（也叫（也叫单密钥制系统单密钥制系统）。）。对称密钥系统对称密钥系统(symmetric cipher)温旧引新温旧引新 4提 纲公公钥钥密密码码体制体制概概述述RSA密密钥钥分配分配与与管理管理123455.1 公钥密码体制概述公钥密码体制概述(asymmetric cip

2、her) 参考文献：参考文献：1卢开澄：卢开澄：计算机密码学计算机密码学 清华大学出版社清华大学出版社（1998年年7月第二版）月第二版） 2章照之：章照之：现代密码学基础现代密码学基础 北京邮电大学北京邮电大学出版社出版社 （20042004年年4 4月第月第1 1版）版） 6外语关键词外语关键词 公钥密钥体系：公钥密钥体系： asymmetric cipher 计算复杂性：计算复杂性：computational complexity 素数分解素数分解：factorization of prime number 离散对数：离散对数：Discrete Logarithms 单向陷门函数：单向陷

3、门函数：trap-door one-way function 公钥与私钥：公钥与私钥：Public Key and Private Key 7 20 20世纪末世纪末, ,电子商务与因特网迅速发展，一方面电子商务与因特网迅速发展，一方面极大地方便了人们对信息的交换和共享极大地方便了人们对信息的交换和共享, ,另一方面，另一方面，也给安全通信提出了很多新的需求，传统的单钥制也给安全通信提出了很多新的需求，传统的单钥制密码系统对此无能为力。如何更好地解决信息安全密码系统对此无能为力。如何更好地解决信息安全问题，已成为刻不容缓的任务。问题，已成为刻不容缓的任务。1 1、对称密码体制面对的形势、对称密

4、码体制面对的形势 5.1.1 5.1.1 公钥密码体系产生的背景：公钥密码体系产生的背景：82 2、传统密码体制已不适应形势的发展、传统密码体制已不适应形势的发展1). 功能上的缺憾功能上的缺憾 传统密码学不擅长认证功能。传统密码学不擅长认证功能。 2). 使用上的难题使用上的难题 密钥交换是对称密钥体制的难题。密钥交换是对称密钥体制的难题。 3). 管理上的困难管理上的困难 密钥管理问题成了通信的瓶颈。密钥管理问题成了通信的瓶颈。9 在这种情况下，一种新的密码体制在这种情况下，一种新的密码体制出现了。它就是公开密钥系统，也称出现了。它就是公开密钥系统，也称非非对称密钥体系对称密钥体系（也叫（

5、也叫双密钥制系统双密钥制系统）。）。从理论到实践上逐步解决了对称密钥存从理论到实践上逐步解决了对称密钥存在的问题，并从根本上提升了密码学的在的问题，并从根本上提升了密码学的理念，标志着密码学进入了崭新的发展理念，标志着密码学进入了崭新的发展阶段。阶段。 3 3、非对称密钥体系开始出现、非对称密钥体系开始出现105.1.2 公钥密码体系的几种算法 一种新理论新技术的产生，一方面是因一种新理论新技术的产生，一方面是因为实际问题的需求，另一方面，也是科学发为实际问题的需求，另一方面，也是科学发展的必然结果。展的必然结果。 创新成果的产生，源于对前人成果的不断积累与改进，也离不开发明者开创性的思维。

6、我们将通过三个典型案例的介绍，向同学们展示公钥密码体系的产生过程。111.Merkle难题 (Puzzle)： 起初人们并没有想到去发明一个公钥密码，起初人们并没有想到去发明一个公钥密码，只不过是为了解决在只不过是为了解决在普通信道中完成密钥交换普通信道中完成密钥交换问题而进行了一系列探索和努力。问题而进行了一系列探索和努力。 1974年，年，Merkle为解决对称单钥制密钥体为解决对称单钥制密钥体系的密钥交换问题，提出了一个设想。系的密钥交换问题，提出了一个设想。 Merkle密钥交换协议如下：密钥交换协议如下： 12uxi是是0999999之间一个任意的但又各不相同的随机数；之间一个任意的

7、但又各不相同的随机数；uYi也也是是0999999之间任意但又各不相同的随机数，分之间任意但又各不相同的随机数，分别作为每条消息的密钥。别作为每条消息的密钥。uAlice秘密保存所有秘密保存所有yi与与xi的密钥对照表后，就把这的密钥对照表后，就把这100万条消息分别用所宣布的万条消息分别用所宣布的yi加密，发给加密，发给Bob。Eyi(这条信息是这条信息是xi，它的密钥是，它的密钥是yi)明文明文 xj （1）Alice向向Bob发送发送100万条消息万条消息；13(2) Bob收到收到100万条消息，从中任选一条，然后遍历万条消息，从中任选一条，然后遍历100万个密钥进行尝试，总有一个万个

8、密钥进行尝试，总有一个yj可将其解密，从可将其解密，从而得知而得知xj的值。的值。(3) Bob以明文形式将以明文形式将xj发给发给Alice (4) Alice收到收到xj，即知，即知Bob所选的是哪个所选的是哪个yj，从而二人，从而二人都有了同样的密钥都有了同样的密钥yj。14Merkle安全性探讨安全性探讨 非法窃听者非法窃听者Eve，即使收到了全部往来的明文，即使收到了全部往来的明文和密文，为了找到和密文，为了找到xj对应的对应的yj，他需要对约，他需要对约100万条消息一一作遍历万条消息一一作遍历100万万个密钥的尝试。个密钥的尝试。 若尝试若尝试1个密钥耗时个密钥耗时1毫秒，尝试毫

9、秒，尝试100万万个密钥个密钥耗时耗时10001000秒秒17 7分钟，这才解译了一条消息，分钟，这才解译了一条消息，100万条消息约万条消息约3 31年才能全部试完。年才能全部试完。 而合法用户乙最多只需要而合法用户乙最多只需要17 7分钟。分钟。 此设计方案显然不现实，但其思想是很先进的。他用的是公开此设计方案显然不现实，但其思想是很先进的。他用的是公开的算法，的算法，通过普通（不安全）信道完成了密钥交换，其保密机制是通过普通（不安全）信道完成了密钥交换，其保密机制是基于计算复杂性，安全理念是基于破译的时效性，其设计理念已经基于计算复杂性，安全理念是基于破译的时效性，其设计理念已经进入了公

10、钥密码的大门。进入了公钥密码的大门。 14152 双钥制的提出 1976年年11月，美国斯坦福大学电月，美国斯坦福大学电气工程系研究生气工程系研究生W.Diffie和副教授和副教授Helman在在IEEE上发表了题为上发表了题为“密码学新密码学新方向方向“的学术论文，利用离散对数复杂性的学术论文，利用离散对数复杂性实际地解决了单钥制的密钥交换问题。实际地解决了单钥制的密钥交换问题。 16(1)(1)离散对数问题离散对数问题 设设p一个为大素数，已知整数一个为大素数，已知整数x和和b ，不难求，不难求出出: modxybp例如，例如，y=3=36 6 mod 7=729 mod 7=1mod 7

11、=729 mod 7=1；然而若已知然而若已知 y 和和 b，用逆运算求，用逆运算求x却十分困难却十分困难: : logmodbxyp为了求上例的逆运算：为了求上例的逆运算：x=log3 1 mod 7=? 需要算出需要算出全部指数数据，全部指数数据，查表求反函数：查表求反函数：x 1 2 3 4 5 6y 3 2 6 4 5 1 17 遍历法虽然是万能的方法，却是个笨方法。设想遍历法虽然是万能的方法，却是个笨方法。设想如果如果p是一个六位数，计算大约是一个六位数，计算大约100万个万个x与与y的对照的对照表，再快也不会少于表，再快也不会少于1毫秒吧，而如果毫秒吧，而如果p是一个一百是一个一百

12、零六位的数，按照同样的计算速度就需要零六位的数，按照同样的计算速度就需要10100毫秒毫秒=3.171089年。年。 实际上，上面的估计还是太保守了。随着数位实际上，上面的估计还是太保守了。随着数位的增大，加减乘除都会变得更加繁杂，对于大数的乘的增大，加减乘除都会变得更加繁杂，对于大数的乘方运算与求模运算，计算量已经远远增大，不能再沿方运算与求模运算，计算量已经远远增大，不能再沿用计算小数的速度来估计了。用计算小数的速度来估计了。18（2 2）计算复杂性）计算复杂性 所谓复杂性指计算所必须的基本运算步骤数量，它决定了所谓复杂性指计算所必须的基本运算步骤数量，它决定了计算所必须的机时和占用的计算

13、机资源。计算所必须的机时和占用的计算机资源。 计算复杂性理论告诉我们，随着数位计算复杂性理论告诉我们，随着数位N的增大，计算量从的增大，计算量从小到大的次序是：小到大的次序是：常数常数对数函数对数函数logN 线性函数线性函数aN 二次函数二次函数N2 三次函数三次函数N3多项式函数多项式函数Nd 亚指数函亚指数函数数2 2logN logN 指数函数指数函数2 2N N或或1010N N。 多项式以下的运算都认为是有效算法，属于可解问题（多项式以下的运算都认为是有效算法，属于可解问题（P类），而比多项式发散更快的算法都被认为是难解问题类），而比多项式发散更快的算法都被认为是难解问题（NP类，

14、类，NPC类）。类）。 数学上已经证明离散对数是非正常（数学上已经证明离散对数是非正常（NP）类复杂问题）类复杂问题, ,计计算量随着算量随着N的增大而趋于无穷。的增大而趋于无穷。 19补充：补充：P问题、问题、NP问题和问题和NPC问题问题1 P问题问题 P是一个判定问题类，这些问题可以用一个确定性算法在是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模是该问题的一个实例的规模n的多项式函数，则我们说这种的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于可以

15、在多项式时间内解决的判定性问题属于P类问题。类问题。P类类问题就是所有复杂度为多项式时间的问题的集合。问题就是所有复杂度为多项式时间的问题的集合。2 NP问题（问题（Non-deterministic Polynomial） NP是一个判定问题类，这些问题可以用一个确定算法在是一个判定问题类，这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解。也可以说这些问题多项式时间内检查或验证出它们的解。也可以说这些问题可以在非确定性多项式时间内解决，它并不要求给出一个可以在非确定性多项式时间内解决，它并不要求给出一个算法来求解问题本身，而只要求给出一个确定性算法在多算法来求解问题本身，而只要求

16、给出一个确定性算法在多项式时间内验证它的解。项式时间内验证它的解。显然所有显然所有P类问题都属于类问题，但是是否等于？类问题都属于类问题，但是是否等于？未解。未解。20 NPC问题问题 NPC，NP完全问题，是求完全问题，是求NP中判中判定问题的一个子类，是最不可能被定问题的一个子类，是最不可能被简化为简化为P的决定性问题的集合。的决定性问题的集合。 每一个每一个NPC问题都可以在多项式时问题都可以在多项式时间内转化为任何一个间内转化为任何一个NP问题。问题。补充：补充：P问题、问题、NP问题和问题和NPC问题问题21用户用户I 选选xi为私钥为私钥求出求出 yi=bxi mod p 为公钥为

17、公钥用户用户J 选选xj为私钥为私钥求出求出 yj=bxj mod p 为公钥为公钥发发b, p, yi发发 yj=(bxj)xi=kij =(bxi)xj=（3 3）DiffieDiffie和和HelmanHelman的方案：的方案： 收到收到yj后后, 由由 (yj )xi mod p 得到会话密钥得到会话密钥收到收到yi后后, 由由 (yi )xj mod p 得到会话密钥得到会话密钥22 尽管公布了尽管公布了yi，yj和和p p，基于离散对数的困难性，基于离散对数的困难性，任何第三者难以求出任何第三者难以求出xi和和xj，因此无法获得，因此无法获得kij。 DiffieDiffie和和

18、HelmanHelman虽然讨论的仍然是单钥制的密钥虽然讨论的仍然是单钥制的密钥交换问题，但他们的观念交换问题，但他们的观念是很超前的。他们采用的算是很超前的。他们采用的算法是公开的，他们的法是公开的，他们的保密机制是基于计算复杂性，并保密机制是基于计算复杂性，并且他们首次提出了双密钥的观点且他们首次提出了双密钥的观点。因此这篇论文被认。因此这篇论文被认为是现代密码学的开篇之作。为是现代密码学的开篇之作。 22235.1.3 RSA公开密钥体系公开密钥体系 1978年美国麻省理工大学的年美国麻省理工大学的 Ron.Rivest、Adi.Shamir 和和 Len.Adleman 提出提出RSA

19、公钥密码体公钥密码体系。系。 它是它是第一个具有实用价值的公钥密码算法第一个具有实用价值的公钥密码算法. . 它是应用最广泛的公钥密码算法。它是应用最广泛的公钥密码算法。 它的原理是根据数论的欧拉定理。它的原理是根据数论的欧拉定理。 它的安全性是基于大数分解因数的复杂性。它的安全性是基于大数分解因数的复杂性。240、介绍-模运算模运算 模运算：简单的说，就是求余数。模运算：简单的说，就是求余数。 设设r是是a除以除以b的余数，的余数，a与与b的关系可表示为的关系可表示为a=r(mod b)，这就是，这就是模运算模运算。 例：例：23=11(mod12) 29 (mod 26) = 3 10 (

20、mod 26) = 3 -1 (mod 26) = 25模运算在数论和程序设计模运算在数论和程序设计中都有着广泛的应用，从中都有着广泛的应用，从奇偶数的判别到素数的判奇偶数的判别到素数的判别，从模幂运算到最大公别，从模幂运算到最大公约数的求法，从孙子问题约数的求法，从孙子问题到凯撒密码问题，无不充到凯撒密码问题，无不充斥着模运算的身影。斥着模运算的身影。 250、介绍-同余同余 一般地，两个整数一般地，两个整数a和和b，除以一个大于，除以一个大于1的自然的自然数数m所得的余数相同，就称所得的余数相同，就称a和和b对于模对于模m同余或同余或a和和b在模在模m下同余，记为下同余，记为ab(mod

21、m) 读作a与b(模m)同余，“”读作读作“同余于同余于”。 如，如，1811(mod 7) 可用模将全体整数分类。可用模将全体整数分类。 如用如用4来将整数分类，由于余数可为来将整数分类，由于余数可为0、1、2、3共四种，因而可分为四类：共四种，因而可分为四类：0，4，8，12，161，5，9，13，172，6，10，14，183，7，11，15，19260、介绍-模逆元模逆元 在公钥密码体制中，往往需要求解模逆元。在公钥密码体制中，往往需要求解模逆元。 求模逆元，即寻找一个求模逆元，即寻找一个x，使得，使得 a*x=1(mod n) 或或 1=(a*x) mod n 其中其中a和和n是正整

22、数，是正整数，x称为称为a的模的模n逆元。逆元。 也写作：也写作：a-1=x mod n例：例：4-1mod7=? 5-1mod14=? 2-1mod14=?4*2(mod 7)=123没有逆元！没有逆元！求解模逆元问题很困难，有时有结果，有时没有结果。270 0、介、介绍-分解分解 因子分解就是对合数的分解。因子分解就是对合数的分解。 例：例：18=2*32，96=25*3，110=2*5*11 较好的因子分解方法：试除法、数域筛选法、椭圆曲较好的因子分解方法：试除法、数域筛选法、椭圆曲线法等。线法等。 但对于很大的数（但对于很大的数（1024bit以上的数）进行因子分解，以上的数）进行因子

23、分解，所需计算时间在目前条件下是一个天文数字。所需计算时间在目前条件下是一个天文数字。 所以，已知两个大素数所以，已知两个大素数p和和q，求其积很容易；，求其积很容易； 反之，知道反之，知道n求求p和和q就很困难。就很困难。RSARSA公钥密码体制公钥密码体制这样的分解是独一无二这样的分解是独一无二281、RSA算法原理 设设p和和q为两个大素数，计算为两个大素数，计算 n = pq 在小于在小于n的的 n- -1个正整数中个正整数中: 有有p- -1个正整数：个正整数：q, 2q, 3q, , (p-1)q 含因子含因子q； 有有q-1个正整数：个正整数：p, 2p, 3p, , (q-1)

24、p含因子含因子p； 除此之外的数（同余类）都与除此之外的数（同余类）都与n互素，其数目为：互素，其数目为： (n-1)-(p-1)-(q-1) = n-p-q+1 = pq-p-q+1 = (p-1)(q-1)； 令：令：(n) = (p-1)(q-1) 叫做欧拉数，代表小于叫做欧拉数，代表小于n且与且与n互素的数（同余类）的个数。互素的数（同余类）的个数。 注：严谨的表述应当是同余类注：严谨的表述应当是同余类-凡除以凡除以n后余数相同的整后余数相同的整 数为一个同余类）。数为一个同余类）。29 Euler(欧拉) 定理： 若若m与与n为互素的正整数，为互素的正整数， 则： m (n) 1 (

25、mod n) 若若k是任意整数是任意整数,则则 mk也与也与n互素，于是有：互素，于是有： m k (n) 1 (mod n) m k (n) +1 m (mod n) （对任意（对任意 0 m n） 只要选择只要选择e,d, 满足满足ed 1 mod (n) ，（叫做在模，（叫做在模 (n) 运算下运算下d 和和e互为模逆元）互为模逆元） 即有：即有： ed=k(n)+1, 于是上式变为：于是上式变为： med =m (mod n)得到得到d、e、n后，后，p、q、 (n)都销毁都销毁2930设设m为明文，由为明文，由：med = =m mod mod n出发出发可以设计出一种加、可以设计出

26、一种加、解密方案：解密方案：如果用如果用 me mod mod n作为加密计算结果，作为加密计算结果， 就可用就可用( (me) )d = = m mod mod n来解密；来解密；如果用如果用 md mod n作为加密计算结果，作为加密计算结果， 就可用就可用 (m d )e = =m mod n来解密。来解密。一般取一般取 (n, e) 为公钥，为公钥， 对明文对明文m进行加密得到密文进行加密得到密文 ：c=me mod n d d为私钥，解密算法是：为私钥，解密算法是： m=cd mod n 当然也可以用私钥加密：当然也可以用私钥加密： c=md mod n用公钥解密：用公钥解密： m=

27、c e mod n 31例例1取两个小素数取两个小素数p=11，q=3来演示来演示RSA的加、解密过程。的加、解密过程。解：先求出：解：先求出：n=pq=33,(n)=(p-1)(q-1)=20； 在在1 e (n)中中,取取e=7为公钥为公钥(与与20互素即可互素即可) 不难看到不难看到: 73 mod 20=1 d= 3（为私钥）；（为私钥）；设明文设明文m= (010)2 = 2，则，则: 密文密文 c = 2 7 =128 mod 33 mod 33 =29； 解密：解密：m = 293 mod 33 =24389 mod 33 =2； 32 因为因为e和和d是在模是在模(n) )运算

28、下的互为倒数，当运算下的互为倒数，当e与与d被被确定后，应当把确定后，应当把 p、q 和和(n) )都销毁，仅留下都销毁，仅留下n，e和和d是无法互相推导的。是无法互相推导的。 除非能将除非能将n分解，求出分解，求出p和和q，而大数的分解因数是，而大数的分解因数是Np类难题。因此类难题。因此RSA的安全得到保证。的安全得到保证。 2 2、RSARSA的安全性的安全性33提提 纲纲公公钥钥密密码码体制体制介介绍绍公钥密码体制特点公钥密码体制特点密密钥钥分配分配与与管理管理123 33345.2.1 公钥密码体制的特点1. 从形式上讲：由对称单钥制到非对称的双钥制加密和解密所用的算法和密钥不同，而

29、且二加密和解密所用的算法和密钥不同，而且二者不可互相推导。者不可互相推导。加密过程：加密过程：C = Ek1 M解密过程：解密过程：M = Dk2 C 352. 从使用上讲：由隐蔽密钥制到公开密钥制 双钥制的出现引入了一个新观念：一对不对双钥制的出现引入了一个新观念：一对不对称的密钥中，可以只私密保密一把密钥，称称的密钥中，可以只私密保密一把密钥，称为为私钥私钥；另一把公开，叫做；另一把公开，叫做公钥公钥，就解决了，就解决了密钥交换难题。密钥交换难题。 N个用户的系统，虽然每个用户需要各自建个用户的系统，虽然每个用户需要各自建立一对公钥与私钥，但网络管理员只须保管立一对公钥与私钥，但网络管理员

30、只须保管（不必隐藏）（不必隐藏）N把公钥，私钥由用户个人保把公钥，私钥由用户个人保管，也解除了网管的负担。管，也解除了网管的负担。 点击此处添加标题文字用于保密功能用于认证功能发信人用发信人用收信人的公钥收信人的公钥加密加密，收信人用自己的收信人用自己的私钥解密私钥解密。其他人因没。其他人因没有密文所要求的私钥而有密文所要求的私钥而不能解密。不能解密。发信人用自己的私钥加发信人用自己的私钥加密，收信人用发信人的密，收信人用发信人的公钥解密公钥解密，只要能解译，只要能解译密文，就表明这个密文密文，就表明这个密文是掌握私钥的那个人发是掌握私钥的那个人发出，别人做不出这样的出，别人做不出这样的密文。

31、密文。3. 从功能上讲：由单纯保密功能到保密认证双重功能 37基于公开密钥的加密过程38 每个用户拥有自己的密钥对每个用户拥有自己的密钥对(KP , KS) 公钥公钥KP公开公开, 私钥私钥KS保密；保密； 当当AB通信时，用通信时，用B的公钥的公钥KPB加密加密: C=EKPB(M) B收密信后，用自己私钥收密信后，用自己私钥KSB解密解密: DKSB(C)= DKSB(EKPB(M)=M用公钥密码实现保密用公钥密码实现保密39基于公开密钥的认证过程40用公钥密码实现认证 A为了向别人表明所发信息是自己的，应当用自己为了向别人表明所发信息是自己的，应当用自己私钥私钥KSA加密信息加密信息:

32、C=DKSA(M) 凡是拿到凡是拿到A的公钥的公钥KPA的人都可以解密这个信息：的人都可以解密这个信息： EKPA(C)=EKPA(DKSA(M)=M 由此表明此信息是由此表明此信息是A所签发。所签发。而而B进行双重解进行双重解密密: EKPA(DKSB(Z)=M如果如果A 只想让只想让B验证所发信息，验证所发信息，应双重加密应双重加密:Z= EKPB(DKSA(M)用公钥密码实现认证和加密小结小结 公钥密码体制的出现，解决了对称密码体制很公钥密码体制的出现，解决了对称密码体制很难解决的一些问题，主要体现三个方面：难解决的一些问题，主要体现三个方面： 密钥分发问题密钥分发问题 密钥管理问题密钥

33、管理问题 数字签名问题数字签名问题 42435.2.2公开密钥体制的构建公开密钥体制的构建单钥制密码体系中，单钥制密码体系中，解密使用的密钥与加密密钥解密使用的密钥与加密密钥相同；能加密的人就能解密。因而又称为相同；能加密的人就能解密。因而又称为对称密对称密钥制钥制。而公钥密码体系中，加密与解密使用的密钥不同，而公钥密码体系中，加密与解密使用的密钥不同，并且无法从一把密钥推导出另一把密钥；故又称并且无法从一把密钥推导出另一把密钥；故又称为为非对称密钥制非对称密钥制。44单钥制密码体系中，解密是加密的逆运算，数学单钥制密码体系中，解密是加密的逆运算，数学上两个算法互为反函数；上两个算法互为反函数

34、；而公钥密码体系中，加密算法的反函数应当是不而公钥密码体系中，加密算法的反函数应当是不可行的。可行的。可见构建公钥密码体系，需要找到除了反函数之可见构建公钥密码体系，需要找到除了反函数之外的另外一种逆运算方法。外的另外一种逆运算方法。这个方法的实现还需要使用不同于加密算法的另这个方法的实现还需要使用不同于加密算法的另外一把密钥。外一把密钥。数学上是否存在这样的算法？数学上是否存在这样的算法？45单向陷门函数（one way trapdoor function ） 单向陷门函数是满足下列条件的函数单向陷门函数是满足下列条件的函数f(x)：(1) 给定给定x，计算，计算y=f(x)是容易的；是容易

35、的；(加密可行加密可行)(2) 给定给定y, 计算计算x=f -1(y)是不可行的是不可行的; (安全有保障安全有保障)(3) 对给定的任何对给定的任何y，还存在另一种计算，还存在另一种计算x 的方法的方法 xgk(y)，在已知，在已知 k 的情况下完成计算是容易的的情况下完成计算是容易的. k 就是密钥。就是密钥。(合法用户得以解密合法用户得以解密)46 而逆运算即求而逆运算即求 的整数解十分复的整数解十分复杂。表明它是单向函数，逆运算不可行。杂。表明它是单向函数，逆运算不可行。 对于已知密钥对于已知密钥 d 的人，还存在另一种计算的人，还存在另一种计算 m 的方的方法：法： m=c d (

36、mod n) RSA的安全性在于攻击者用逆运算求解不可行，由的安全性在于攻击者用逆运算求解不可行，由公钥公钥e和和n出发计算私钥出发计算私钥d 也是不可行的。（指计算也是不可行的。（指计算 复杂到不可行的程度）复杂到不可行的程度） RSA就是一种单向陷门函数就是一种单向陷门函数. .计算计算c=me (mod n)是容易的。是容易的。(mod)emcn47 RSA公钥密码体制公钥密码体制 安全性基于大整数的素分解问题的安全性；安全性基于大整数的素分解问题的安全性；ElGamal公钥密码体制公钥密码体制 安全性基于有限域上的离散对数问题的困难性；安全性基于有限域上的离散对数问题的困难性；Mene

37、zes-Vanstone公钥密码体制公钥密码体制 安全性基于椭圆曲线上的离散对数问题的困难性；安全性基于椭圆曲线上的离散对数问题的困难性；目前大部分的公钥密码体制都是基于这三类问题，已经提目前大部分的公钥密码体制都是基于这三类问题，已经提出的许多公钥密码学的标准，譬如出的许多公钥密码学的标准，譬如IEEE P1363等，也大都等，也大都建立在这三类问题之上。建立在这三类问题之上。485.2.3 现代密码学的新理念现代密码学的新理念 1. 1. 从基于算法的神秘性到基于算法的复杂性从基于算法的神秘性到基于算法的复杂性 传统的保密观念，寄托安全性于某种鲜为人知的奇妙算法传统的保密观念，寄托安全性于

38、某种鲜为人知的奇妙算法上。其安全是暂时的，侥幸的，脆弱的。上。其安全是暂时的，侥幸的，脆弱的。 现代密码学基于算法的复杂性，现代密码学基于算法的复杂性，不靠神奇靠麻烦不靠神奇靠麻烦。其安全其安全是牢固的，可信的，科学的。是牢固的，可信的，科学的。 从基于算法的神秘性到基于算法的复杂性是现代密码学设从基于算法的神秘性到基于算法的复杂性是现代密码学设计理念上一次重大转变。密文能否被破译的关键不再是从计理念上一次重大转变。密文能否被破译的关键不再是从密文中提取信息有无可能性，而是从密文中提取信息有无密文中提取信息有无可能性，而是从密文中提取信息有无可行性。可行性。492.2.算法可公开性算法可公开性

39、 由于算法失去了保密价值，算法可以公开，让它在攻由于算法失去了保密价值，算法可以公开，让它在攻击中不断改进和完善，并以此显示其安全的坚固性。击中不断改进和完善，并以此显示其安全的坚固性。 算法公开了，合法用户与非法用户的区别在那里呢？算法公开了，合法用户与非法用户的区别在那里呢？ 合法用户拥有密钥，解译密文十分容易；非法用户没合法用户拥有密钥，解译密文十分容易；非法用户没有密钥，破译密文谈何容易；有密钥，破译密文谈何容易；不藏算法藏密钥不藏算法藏密钥是设计是设计理念上一致的观点。理念上一致的观点。 503 3 安全的相对性安全的相对性 当然，应充分估计破译者的计算能力和计算技术当然，应充分估计

40、破译者的计算能力和计算技术未来的发展，从这个意义讲，破译只是时间和金未来的发展，从这个意义讲，破译只是时间和金钱的问题。钱的问题。 如果破译工作所花的代价大于秘密本身的价值，如果破译工作所花的代价大于秘密本身的价值，或破译花费的时间大于秘密的有效期，则破译失或破译花费的时间大于秘密的有效期，则破译失去意义，而该保密系统就可以认为是安全的。这去意义，而该保密系统就可以认为是安全的。这才是实事求是的科学的保密观和破译观。才是实事求是的科学的保密观和破译观。不保绝不保绝对保相对对保相对是密码设计理念上的又一个转变。是密码设计理念上的又一个转变。 比较比较 公钥密码体制与对称密码体制相比公钥密码体制与

41、对称密码体制相比： 优点：优点： 密钥的分发相对容易；密钥的分发相对容易； 密钥管理简单；密钥管理简单； 可以有效地实现数字签名。可以有效地实现数字签名。 缺点：缺点： 与对称密码体制相比，加解密速度比较慢；与对称密码体制相比，加解密速度比较慢； 同等安全强度下，要求的密钥位数要多一些；同等安全强度下，要求的密钥位数要多一些； 密文的长度往往大于明文长度。密文的长度往往大于明文长度。51521.公开密钥体制的新理念： (1)(1)系统安全基于计算复杂性，算法可以公开。系统安全基于计算复杂性，算法可以公开。 (2)(2)加密解密使用非对程的双密钥，一把可以公开。加密解密使用非对程的双密钥，一把可

42、以公开。 (3)(3)科学的可靠的系统设计思想。科学的可靠的系统设计思想。2.公钥密码的功能： (1)(1)用于保密：用接收方的公钥加密，私钥解密。用于保密：用接收方的公钥加密，私钥解密。 (2)(2)用于认证：用发送方的私钥加密，公钥验证。用于认证：用发送方的私钥加密，公钥验证。3.RSA公钥密码的原理与方法： (1) (1) 系统搭建：系统搭建：n=pq, (n)=(p-1)(q-1), de=1 mod (n) (2)(2)加、解密方法：加、解密方法：c=me mod n, m=cd mod n内容要点（小结）内容要点（小结）5253提提 纲纲公公钥钥密密码码体制体制概概述述公钥密码体制

43、的特点公钥密码体制的特点密密钥钥分配分配与与管理管理123 53545.3密钥分配方案密钥分配方案 要使要使常规加密常规加密有效地进行，信息交互的双方必须共享有效地进行，信息交互的双方必须共享一个密钥，并且这个密钥还要防止被其他人获得。一个密钥，并且这个密钥还要防止被其他人获得。 要使要使公开加密公开加密有效地进行，信息接收的一方必须发布有效地进行，信息接收的一方必须发布其公开密钥，同时要防止其私有密钥被其他人获得。其公开密钥，同时要防止其私有密钥被其他人获得。 密钥还需密钥还需经常更换经常更换，以便在攻击者知道密钥的情况下，以便在攻击者知道密钥的情况下使得泄漏的数据量最小化。对于通信的双方使

44、得泄漏的数据量最小化。对于通信的双方A和和B，密密钥的分配可以有以下的几种方法：钥的分配可以有以下的几种方法：55密钥分配的四种方法密钥分配的四种方法(1)密钥可以由密钥可以由A选定，然后通过选定，然后通过物理的方法物理的方法安全地传递给安全地传递给B。(2) 密钥可以由可信任的第三方密钥可以由可信任的第三方C选定，然后通过选定，然后通过物理的方法物理的方法安全地传安全地传递给递给A和和B。 (3) 如果如果A和和B都有一个到可信任的第三方都有一个到可信任的第三方C的的加密连接加密连接，那，那么么C就可以通过加密连接将密钥安全地传递给就可以通过加密连接将密钥安全地传递给A和和B。 采用的是采用

45、的是密钥分配中心技术密钥分配中心技术，可信任的第三方，可信任的第三方C就是密钥就是密钥分配中心分配中心 KDC (key distribute center) ，常常用于常规加密常常用于常规加密密钥的分配。密钥的分配。上述方法由于需要对密钥进行上述方法由于需要对密钥进行人工传递人工传递，对于大量连接的现代通信而，对于大量连接的现代通信而言，显然不适用。言，显然不适用。56(4) 如果如果A和和B都在可信任的第三方发布自己的公开密钥，都在可信任的第三方发布自己的公开密钥，那么它们都可以用彼此的公开密钥加密进行通信。那么它们都可以用彼此的公开密钥加密进行通信。 采用的是密钥认证中心技术，可信任的第

46、三方采用的是密钥认证中心技术，可信任的第三方C就是证就是证书授权中心书授权中心 C A (certificate authority)C A (certificate authority)，更多用更多用于公开加密密钥的分配。于公开加密密钥的分配。主要讲主要讲(3) KDC (4) CA方式方式575.3.1常规加密密钥的分配常规加密密钥的分配1. 集中式密钥分配方案集中式密钥分配方案 由一个中心节点或者由一组节点组成层次结构负责由一个中心节点或者由一组节点组成层次结构负责密钥的产生并分配给通信的双方，在这种方式下，用密钥的产生并分配给通信的双方，在这种方式下，用户不需要保存大量的会话密钥，只需

47、要保存同中心节户不需要保存大量的会话密钥，只需要保存同中心节点的加密密钥，用于安全传送点的加密密钥，用于安全传送由中心节点产生的即将由中心节点产生的即将用于与第三方通信的会话密钥用于与第三方通信的会话密钥。这种方式缺点是通信。这种方式缺点是通信量大，同时需要较好的鉴别功能以鉴别中心节点和通量大，同时需要较好的鉴别功能以鉴别中心节点和通信方。信方。 目前这方面的主流技术是目前这方面的主流技术是密钥分配中心密钥分配中心KDC技术。技术。58 其中的第三方通常其中的第三方通常是一个负责为用户分配密钥的密钥分是一个负责为用户分配密钥的密钥分配中心配中心(KDC)。 这时每一用户必须和密钥分配中心有一个

48、共享密钥，称这时每一用户必须和密钥分配中心有一个共享密钥，称为为主密钥。（可通过第二种方法）主密钥。（可通过第二种方法） 通过主密钥分配给一对用户的密钥通过主密钥分配给一对用户的密钥Ks称为会话密钥称为会话密钥，用，用于这一对用户之间的保密通信。于这一对用户之间的保密通信。 通信完成后，会话密钥即被销毁通信完成后，会话密钥即被销毁。如上所述，如果用户。如上所述，如果用户数为数为n，则会话密钥数为，则会话密钥数为n(n-1)/2。但主密钥数却只需。但主密钥数却只需n个，所以个，所以主密钥可通过物理手段发送主密钥可通过物理手段发送。59密钥分配中心密钥分配中心KDC的密钥分配方案的密钥分配方案(1

49、) AKDC：IDA | IDB | N1(2) KDC A ：EKA Ks | IDA| IDB |N1|EKbKs|IDA(3) AB： EKBKs|IDA(4) BA： EKsN2(5) A B： EKsf(N2)60 实际上，到第实际上，到第(3)步已经完成步已经完成密钥的分配密钥的分配过程，通过程，通信的双方已经共享了当前的会话密钥信的双方已经共享了当前的会话密钥Ks，第第(4)步步和第和第(5)步完成的是步完成的是鉴别功能鉴别功能。 第第2项项N1， Nonce 现时，现时，是这次业务的惟一识别是这次业务的惟一识别符符N1，称，称N1为一次性随机数，可以是时戳、计数器为一次性随机数

50、，可以是时戳、计数器或随机数或随机数 每次的每次的N1都应不同，且为防止假冒，都应不同，且为防止假冒，应使敌手对应使敌手对N1难以猜测难以猜测。因此用随机数作为这个识别符最为。因此用随机数作为这个识别符最为合适。合适。61问题问题单个密钥分配中心单个密钥分配中心KDC无法支持大型的通信网络。每无法支持大型的通信网络。每两个可能要进行安全通信的终端都必须同某个密钥分两个可能要进行安全通信的终端都必须同某个密钥分配中心共享主密钥。当通信的终端数量很大时，将出配中心共享主密钥。当通信的终端数量很大时，将出现这样的情况：现这样的情况：每个终端都要同许多密钥分配中心共享主密钥，增加了终每个终端都要同许多

51、密钥分配中心共享主密钥，增加了终端的成本和人工分发密钥分配中心和终端共享的主密钥的端的成本和人工分发密钥分配中心和终端共享的主密钥的成本。成本。需要几个特别大的密钥分配中心，每个密钥分配中心都同需要几个特别大的密钥分配中心，每个密钥分配中心都同几乎所有终端共享主密钥。然而各个单位往往希望自己来几乎所有终端共享主密钥。然而各个单位往往希望自己来选择或建立自己的密钥分配中心。选择或建立自己的密钥分配中心。62解决办法解决办法 网络中如果用户数目非常多且分布的地域非常广，则使用网络中如果用户数目非常多且分布的地域非常广，则使用多个多个KDC的分层结构的分层结构: 在每个小范围（如一个在每个小范围（如

52、一个LAN或一个建筑物）内，都建立一个本或一个建筑物）内，都建立一个本地地KDC。同一范围的用户在进行保密通信时，由本地。同一范围的用户在进行保密通信时，由本地KDC为他为他们分配密钥们分配密钥; 如果两个不同范围的用户想获得共享密钥，则可通过各自的本如果两个不同范围的用户想获得共享密钥，则可通过各自的本地地KDC，而两个本地，而两个本地KDC的沟通又需经过一个全局的沟通又需经过一个全局KDC。这样。这样就建立了两层就建立了两层KDC; 根据网络中用户的数目及分布的地域，可建立根据网络中用户的数目及分布的地域，可建立3层或多层层或多层KDC. 分层结构可减少主密钥的分布，因为大多数主密钥是在本

53、分层结构可减少主密钥的分布，因为大多数主密钥是在本地地KDC和本地用户之间共享。和本地用户之间共享。 分层结构还可将虚假分层结构还可将虚假KDC的危害限制到一个局部区域，但的危害限制到一个局部区域，但 会降低信任度。会降低信任度。632. 无中心的密钥控制无中心的密钥控制 用密钥分配中心为用户分配密钥时，用密钥分配中心为用户分配密钥时，要求所有用户要求所有用户都信任都信任KDC，同时，同时还要求对还要求对KDC加以保护加以保护。如果密。如果密钥的分配是无中心的，则不必有以上两个要求钥的分配是无中心的，则不必有以上两个要求 然而如果每个用户都能和自己想与之建立联系的另一用然而如果每个用户都能和自

54、己想与之建立联系的另一用户安全地通信，则对有户安全地通信，则对有n个用户的网络来说，主密钥应多个用户的网络来说，主密钥应多达达n(n-1)/2个。个。 当当n很大时，这种方案无实用价值很大时，这种方案无实用价值; 但但在整个网络的局部范围却非常有用在整个网络的局部范围却非常有用.64发起方响应方（1）（2）（3）1.AB：IDa|N1 无中心的密钥分配时，两个用户无中心的密钥分配时，两个用户A和和B建立会话密钥需经过建立会话密钥需经过以下以下3步：步： A向向B发出建立会话密钥的请求和一个一次性随机数发出建立会话密钥的请求和一个一次性随机数N1 B用与用与A共享的主密钥共享的主密钥MKm对应答

55、的消息加密，并发送给对应答的消息加密，并发送给A 应答的消息中有应答的消息中有B选取的会话密钥选取的会话密钥KS、B的身份的身份IDb、f(N1)和另一和另一个一次性随机数个一次性随机数N2 A使用新建立的会话密钥使用新建立的会话密钥KS对对f(N2)加密后返回给加密后返回给B2.BA：EMKmKs|IDa|IDb|f(N1)|N23.AB：EKsf(N2)优点：每个通信方都优点：每个通信方都必须保存多达必须保存多达(n一一1)个主密钥，但是需要个主密钥，但是需要多少会话密钥就可以多少会话密钥就可以产生多少。产生多少。655.3.2公钥加密体制的密钥管理公钥加密体制的密钥管理 密钥可根据其不同

56、用途分为会话密钥和主密钥两种类密钥可根据其不同用途分为会话密钥和主密钥两种类型型 会话密钥会话密钥又称为数据加密密钥又称为数据加密密钥 主密钥主密钥又称为密钥加密密钥又称为密钥加密密钥 由于密钥用途不同，对密钥的使用方式也希望加以某种控由于密钥用途不同，对密钥的使用方式也希望加以某种控制制 如果主密钥泄露了，则相应的会话密钥也将泄露，因如果主密钥泄露了，则相应的会话密钥也将泄露，因此主密钥的安全性应高于会话密钥的安全性此主密钥的安全性应高于会话密钥的安全性 一般在密钥分配中心以及终端系统中主密钥都是物理上安一般在密钥分配中心以及终端系统中主密钥都是物理上安全的全的 如果把主密钥当作会话密钥注入

57、加密设备，那么其安全性如果把主密钥当作会话密钥注入加密设备，那么其安全性则降低则降低66 本节介绍两方面内容：本节介绍两方面内容： 一是公钥密码体制所用的一是公钥密码体制所用的公开密钥的分配公开密钥的分配 二是如何用公钥体制来二是如何用公钥体制来分配单钥密码体制所分配单钥密码体制所需的密钥需的密钥 这是公钥加密的一个主要用途这是公钥加密的一个主要用途PGP介绍 PGP：全名：全名：Pretty Good Privacy，一种混合加密算，一种混合加密算法（综合了对称加密算法法（综合了对称加密算法IDEA，非对称加密算法，非对称加密算法RSA，MD5、以及伪随机数产生器等）。通常只理解、以及伪随机

58、数产生器等）。通常只理解为是为是PGP公司的系列软件。能对邮件、文件、文件夹公司的系列软件。能对邮件、文件、文件夹、整个硬盘加密，全网段加密权限和访问权限控制等、整个硬盘加密，全网段加密权限和访问权限控制等。PGP的使用 加密时加密时：PGP用的是用的是RSA和传统加密的杂合算法，因为和传统加密的杂合算法，因为RSA算算法计算量极大在速度上不适合加密大量数据，所以法计算量极大在速度上不适合加密大量数据，所以PGP用来加用来加密信息的不是密信息的不是RSA，而是对称加密算法，而是对称加密算法IDEA 。 数字签名：数字签名：PGP还可以只签名而不加密，这适用于公开发表声还可以只签名而不加密，这适

59、用于公开发表声明时，声明人为了证实自己的身份，可以用自己的私钥签名。明时，声明人为了证实自己的身份，可以用自己的私钥签名。 PGP 通过单向散列算法通过单向散列算法MD5(message digest 5)对邮件处理，对邮件处理，生成一个生成一个128位的二进制数作为位的二进制数作为“邮件文摘邮件文摘” ，一旦邮件有任，一旦邮件有任何改变这个何改变这个digest都会变化，那么这个数加上作者的名字（实都会变化，那么这个数加上作者的名字（实际上在作者的密匙里）还有日期等等，就可以作为一个签名。际上在作者的密匙里）还有日期等等，就可以作为一个签名。 数字签名和认证数字签名和认证：甲用自己的私钥将上

60、述的：甲用自己的私钥将上述的128位的摘要加密位的摘要加密，附加在邮件上，再用乙的公钥将整个邮件加密。乙收到这份，附加在邮件上，再用乙的公钥将整个邮件加密。乙收到这份密文以后，乙用自己的私钥将邮件解密，得到甲的原文和签名密文以后，乙用自己的私钥将邮件解密，得到甲的原文和签名，乙的，乙的PGP也从原文计算出一个也从原文计算出一个128位的摘要，再与用甲的公位的摘要，再与用甲的公钥解密签名得到的数比较，如果符合就说明这份邮件确实是甲钥解密签名得到的数比较，如果符合就说明这份邮件确实是甲寄来的。这样既实现了保密又实现了认证。寄来的。这样既实现了保密又实现了认证。 691. 公开密钥的公开宣布公开密钥