公钥密码体制

1、 1公钥密码学公钥密码学 2公钥密码学公钥密码学l公钥密码学思想lRSA算法l公钥的应用 3公钥密码学的发展是整个密码学发公钥密码学的发展是整个密码学发展历史中最伟大的一次革命。展历史中最伟大的一次革命。公钥密码体制公钥密码体制公钥算法基于数学函数而不是基于替换和置换公钥算法基于数学函数而不是基于替换和置换它使用两个独立的密钥，在消息的保密性、它使用两个独立的密钥，在消息的保密性、密钥分配和认证领域有重要意义。密钥分配和认证领域有重要意义。 4密钥分配问题：如果密钥被偷，设计再好的密钥分配问题：如果密钥被偷，设计再好的密码体制都没有用密码体制都没有用传统密码中的两个问题传统密码中的两个问题数字

2、签名问题：能否设计一种方法确保数字数字签名问题：能否设计一种方法确保数字签名出自某个特定的人，并且各方无异议？签名出自某个特定的人，并且各方无异议？ 51976年年 Diffie和和Hellman针对上述问题提出针对上述问题提出了一种方法，它是密码学的一次革命了一种方法，它是密码学的一次革命密码学革命密码学革命 6公钥密码体制介绍 7n是密码学一次伟大的革命是密码学一次伟大的革命n1976年，年，Diffie和和Hellman 在在“密码学新方密码学新方向向”一文中提出。一文中提出。n使用两个密钥：公开密钥、私有密钥使用两个密钥：公开密钥、私有密钥n加解密的非对称性加解密的非对称性n利用数论的

3、方法利用数论的方法n是对对称密码的重要补充是对对称密码的重要补充 8仅根据仅根据密码算法密码算法和和加密密钥加密密钥来确定来确定解密密钥解密密钥在在计算上是不可行的。计算上是不可行的。公钥密码体制特点公钥密码体制特点两个密钥中的任何一个可以用来加密，另一个两个密钥中的任何一个可以用来加密，另一个用来解密。用来解密。有有6个组成部分：明文、加密算法、公钥、个组成部分：明文、加密算法、公钥、私钥、密文、解密算法私钥、密文、解密算法 9用公钥进行加密用公钥进行加密2 Alice产生一对密钥，用于加密和解密产生一对密钥，用于加密和解密3 Alice将一个密钥公开，另一个密钥私有将一个密钥公开，另一个密

4、钥私有BobAlice1 Bob要发送消息给要发送消息给Alice4 Bob用用Alice的公钥对消息加密，发送给的公钥对消息加密，发送给Alice。只有。只有Alice能解密能解密 10用公钥进行认证用公钥进行认证BobAlice 11用公钥进行认证用公钥进行认证:问题？问题？问题问题1 需要对整条消息加密，占用大量存储空间需要对整条消息加密，占用大量存储空间解决的方法：仅对消息的认证符加密解决的方法：仅对消息的认证符加密问题问题2 不能提供保密性不能提供保密性如何解决？如何解决？ 12公钥密码体制的种类公钥密码体制的种类1 加密加密/解密解密2 数字签名数字签名3 密钥交换密钥交换算法算法

5、 RSA 椭圆曲线椭圆曲线 Diffie-Hellman DSS是是是是是是是是是是是是否否否否是是否否是是否否 13对公钥密码体制的要求：对公钥密码体制的要求：1 B产生一对密钥（Kpb，Ksb）在计算上是容易的2 发送方A加密消息 C=EKpb(M) 在计算上是容易的3 接收方B对密文解密 M=DKsb(C) 在计算上是容易的4 攻击者从Kpb计算出Ksb在计算上不可行的5 攻击者从Kpb和C计算出M在计算上不可行的 14只有两个算法被普遍接受只有两个算法被普遍接受1 RSA2 椭圆曲线 就是要找一个单向陷门函数：不太容易所谓单向陷门函数是这样的函数，即除非知道某种附所谓单向陷门函数是这样

6、的函数，即除非知道某种附加的信息，否则这样的函数在一个方向上容易计算，加的信息，否则这样的函数在一个方向上容易计算，而在反方向上要计算是不可行的。而在反方向上要计算是不可行的。 15单向陷门函数（单向陷门函数（1）Y=fk(X) 容易(k 和X已知)X=fk-1(Y) 计算上不可行（k未知，Y已知）X=fk-1(Y) 容易（k已知，Y已知）寻找合适的单向陷门函数是公钥密码体制应用的关键！ 16单向陷门函数（单向陷门函数（2）l困难程度困难程度l举例举例打碎打碎/拼接、平方拼接、平方/开方、乘法开方、乘法/分解分解* 单向函数存在否单向函数存在否尚无严格的数学证明尚无严格的数学证明 17单向陷门

7、函数（单向陷门函数（3）l单向陷门函数单向陷门函数如果知道某个陷门如果知道某个陷门(秘诀秘诀)，即能容易恢复，即能容易恢复x（陷门即为私钥）（陷门即为私钥）l举例举例魔方的置乱魔方的置乱/恢复恢复l如果有那个口诀，就能很快恢复如果有那个口诀，就能很快恢复 18RSA 算法算法l先从一个简单例子开始先从一个简单例子开始l给出算法给出算法l证明证明 19简单例子简单例子选中两个素数 p7，q17 npq(n)请练习任务：对明文 M=19 加密 npq119(n)(p-1)(q-1)61696选取整数1e (n)与(n) 互素：e5求e的逆元d：ed1 mod (n) 请练习计算 C=Me(mod

8、n)=? 其中M=19 请练习 计算 M=Cd(mod n)=? 请练习 d=77c=66 20RSA 示例总结示例总结l选p7，q17则npq119且(n)(p-1)(q-1)61696l取e5则d77 (57738549611 mod 96)l公钥（5，119），私钥（77，119） l加密m19则cme mod n= 195 mod 119 = 66 mod 119l解密c66mcd mod n = 6677mod 11919 mod 119 21 22RSA算法算法l作者作者1977年，年，R, S, AlRon RivestlAdi ShamirlLen Adleman l基本参数基

9、本参数分组密码算法分组密码算法基于整数乘法基于整数乘法明明/密文分组以及公密文分组以及公/私钥被看作小于私钥被看作小于n的整数的整数加加/解密是模乘运算解密是模乘运算 23RSA算法总结：密钥产生算法总结：密钥产生l找素数找素数选取两个大的随机的素数选取两个大的随机的素数p，ql计算模计算模n和和Euler函数函数(n)npq(n)=(p-1)(q-1)l找找ed1 mod (n)随机取一个数随机取一个数e(与与(n)互素互素)，用扩展，用扩展Euclid算法求算法求d即可即可l发布发布d保密，保密，(d, n)是私钥是私钥 Ks发布发布(e,n)，这是公钥，这是公钥Kp销毁销毁p、q 24R

10、SA的正确性的正确性l加密加密明文分组明文分组m做为整数须小于做为整数须小于nc=me mod nl解密解密m=cd mod n 25RSA考虑考虑l素数素数必须够大，否则对手可能很快分解必须够大，否则对手可能很快分解n判定，采用判定，采用Miller-Rabin概率测试方法概率测试方法l假素数意味着加解密不能正确进行，故可放弃之假素数意味着加解密不能正确进行，故可放弃之强素数强素数l(p-1)/2和和(q-1)/2应是素数应是素数l选取较小的选取较小的e和较大的和较大的de：3、65537l发布公钥发布公钥证书中心证书中心 CA 26攻击攻击RSA数学方法数学方法l分解分解n得到得到p和和q

11、，就可以知道，就可以知道(n)，就可从，就可从e求得求得dl直接求直接求(n)不分解不分解n，而直接求，而直接求(n)，再求再求d l直接求直接求d 不求不求(n)，直接求，直接求d 27使用公钥传递会话密钥使用公钥传递会话密钥 l直接使用公钥算法太慢直接使用公钥算法太慢l只用来传递会话密钥只用来传递会话密钥(假设假设A已经有已经有B的公钥的公钥KeB)A发起和发起和B的通信的通信A产生会话密钥产生会话密钥Ks，并用，并用KeB加密后传给加密后传给BB能用自己的私钥能用自己的私钥KdB解开解开他人不会知道他人不会知道Ks 28对称算法对称算法 vs. 公钥算法公钥算法l速度速度典型相差典型相差1000倍倍l密钥管理密钥管理对称算法需要额外安全信道对称算法需要额外安全信道公钥公钥l证书中心证书中心l混合密码体制混合密码体制公钥算法用于签名和认证