公钥密码体制

1、1,公钥密码学,2,公钥密码学,公钥密码学思想 RSA算法 公钥的应用,3,密码体制产生,俄罗斯人邮寄盒子的故事,4,公钥密码学的发展是整个密码学发 展历史中最伟大的一次革命。,公钥密码体制,公钥算法基于数学函数而不是基于替换和置换,它使用两个独立的密钥，在消息的保密性、 密钥分配和认证领域有重要意义。,5,密钥分配问题：如果密钥被偷，设计再好的 密码体制都没有用,传统密码中的两个问题,数字签名问题：能否设计一种方法确保数字 签名出自某个特定的人，并且各方无异议？,6,1976年 Diffie和Hellman针对上述问题提出 了一种方法，它是密码学的一次革命,密码学革命,7,公钥密码体制介绍,

2、8,是密码学一次伟大的革命 1976年，Diffie和Hellman 在“密码学新方向”一文中提出。 使用两个密钥：公开密钥、私有密钥 加解密的非对称性 利用数论的方法 是对对称密码的重要补充,9,仅根据密码算法和加密密钥来确定解密密钥在 计算上是不可行的。,公钥密码体制特点,两个密钥中的任何一个可以用来加密，另一个 用来解密。,有6个组成部分：明文、加密算法、公钥、 私钥、密文、解密算法,10,用公钥进行加密,2 Alice产生一对密钥，用于加密和解密,3 Alice将一个密钥公开，另一个密钥私有,Bob,Alice,1 Bob要发送消息给Alice,4 Bob用Alice的公钥对消息加密，

3、发送给Alice。只有Alice能解密,11,用公钥进行认证,Bob,Alice,12,用公钥进行认证:问题？,问题1 需要对整条消息加密，占用大量存储空间,解决的方法：仅对消息的认证符加密,问题2 不能提供保密性,如何解决？,13,公钥密码体制的种类,1 加密/解密,2 数字签名,3 密钥交换,算法 RSA 椭圆曲线 Diffie-Hellman DSS,是 是 是,是 是 是,否 否 是,否 是 否,14,对公钥密码体制的要求：,1 B产生一对密钥（Kpb，Ksb）在计算上是容易的,2 发送方A加密消息 C=EKpb(M) 在计算上是容易的,3 接收方B对密文解密 M=DKsb(C) 在计

4、算上是容易的,4 攻击者从Kpb计算出Ksb在计算上不可行的,5 攻击者从Kpb和C计算出M在计算上不可行的,15,只有两个算法被普遍接受,1 RSA,2 椭圆曲线,就是要找一个单向陷门函数：不太容易,所谓单向陷门函数是这样的函数，即除非知道某种附 加的信息，否则这样的函数在一个方向上容易计算， 而在反方向上要计算是不可行的。,16,单向陷门函数（1）,Y=fk(X) 容易(k 和X已知),X=fk-1(Y) 计算上不可行（k未知，Y已知）,X=fk-1(Y) 容易（k已知，Y已知）,寻找合适的单向陷门函数是公钥密码 体制应用的关键！,17,单向陷门函数（2）,困难程度 举例 打碎/拼接、平方

5、/开方、乘法/分解 * 单向函数存在否 尚无严格的数学证明,18,单向陷门函数（3）,单向陷门函数 如果知道某个陷门(秘诀)，即能容易恢复x （陷门即为私钥） 举例 魔方的置乱/恢复 如果有那个口诀，就能很快恢复,19,20,RSA 算法,先从一个简单例子开始 给出算法 证明,21,1.素数：素数是一个比1大，其因子只有1和它本身，没有其它数可以整除它的数。素数是无限的。例如，2，3，5，7等。 2.两个数互为素数：指的是它们除了1之外没有共同的因子。也可以说这两个数的最大公因子是1。例如，4和9，13和27等。用gcd（x,y）=1表示x和y互素。 3.模运算：如A模N运算，它给出了A的余数

6、，余数是从0到N-1的某个整数，这种运算称为模运算。 4.Euler 函数：设p=3, q=5, 那么（15）=（3-1）*（5-1）=8，这8个模15的剩余类是：1，2，4，7，8，11，13，14，其中剩余类是在1至14中除掉是3和5倍数的数，即除掉3，5，6，9，10，12。,22,补充一些数学知识,同余 a b mod m B mod m a c mod m,23,补充一些数学知识,欧拉函数 不超过n，且与n互素的正整数个数，(2)=1。 推论：任何自然数都可以表示为素数米的乘积。6=2*3 (p)=p-1,24,RSA加密算法实现过程,(1)取两个随机大素数p和q（保密）。 (2)计

7、算公开的模数n=pq（公开）。 (3)计算秘密的欧拉函数（n）=（p-1）（q-1）（保密），两个素数p和q不再需要，应该丢弃，不要让任何人知道。 (4) 随机选取整数e，满足gcd（e, （n）=1（公开e，加密密钥）。 计算d，满足de1（mod （n）（保密d，解密密钥，陷门信息）。 (5)将明文x（其值的范围在0到n-1之间）按模为n自乘e次幂以完成加密操作，从而产生密文y（其值也在0到r-1范围内） y=xe （mod n）。 将密文y按模为r自乘d次幂，完成解密操作 x=yd （mod n）=xed mod n=x。,25,简单例子,选中两个素数 p7，q17,npq (n)请练习

8、,任务：对明文 M=19 加密,npq119 (n)(p-1)(q-1)61696,选取整数1e (n)与(n) 互素：e5,求e的逆元d：ed1 mod (n) 请练习,计算 C=Me(mod n)=? 其中M=19 请练习,计算 M=Cd(mod n)=? 请练习,d=77,c=66,26,RSA 示例总结,选p7，q17 则npq119 且(n)(p-1)(q-1)61696 取e5 则d77 (57738549611 mod 96) 公钥（5，119），私钥（77，119） 加密m19 则cme mod n= 195 mod 119 = 66 mod 119 解密c66 mcd mod

9、 n = 6677mod 11919 mod 119,27,RSA算法总结：密钥产生,找素数 选取两个大的随机的素数p，q 计算模n和Euler函数(n) npq (n)=(p-1)(q-1) 找ed1 mod (n) 随机取一个数e(与(n)互素)，用扩展Euclid算法求d即可 发布 d保密，(d, n)是私钥 Ks 发布(e,n)，这是公钥Kp 销毁p、q,28,【例1】,取两个素数p=11，q=13，p和q的乘积为r=pq=143，算出秘密的欧拉函数（r）=（p-1）（q-1）=120，再选取一个与（r）=120互质的数，例如e=7，作为公开密钥，e的选择不要求是素数，但不同的e的抗攻

10、击性能力不一样，为安全起见要求选择为素数。对于这个e值，可以算出另一个值d=103，d是私有密钥，满足ed=1 mod （r），其实7103=721除以120确实余1。欧几里德算法可以迅速地找出给定的两个整数a和b的最大公因数gcd（a，b），并可判断a与b是否互素，因此该算法可用来寻找解密密钥。 120=717+1 1=120-717 mod 120=120-7（-120+17）mod 120 =120+7103 mod 120 （r,e）= （143,7） 这组数公开，即公钥，（r,d）=（143,103）这组数保密，为私钥,29,设想需要发送信息x=85。利用（n,e）=（143,7）计

11、算出加密值： y= xe（mod n）=857 mod 143=123 收到密文y=123后，利用（n,d）=（143,103）计算明文： x=yd（mod n）=123103mod 143=85 加密信息x（二进制表示）时，首先把x分成等长数据块 x1 ,x2,., xi ，块长s，其中 2s n，s尽可能的大。对应的密文是： yi = xie（mod n） 解密时作如下计算： xi = yid（mod n）,30,RSA的正确性,加密 明文分组m做为整数须小于n c=me mod n 解密 m=cd mod n,31,RSA考虑,素数 必须够大，否则对手可能很快分解n 判定，采用Mille

12、r-Rabin概率测试方法 假素数意味着加解密不能正确进行，故可放弃之 强素数 (p-1)/2和(q-1)/2应是素数 选取较小的e和较大的d e：3、65537 发布公钥 证书中心 CA,32,攻击RSA,数学方法 分解n 得到p和q，就可以知道(n)，就可从e求得d 直接求(n) 不分解n，而直接求(n)，再求d 直接求d 不求(n)，直接求d,33,使用公钥传递会话密钥,直接使用公钥算法太慢 只用来传递会话密钥 (假设A已经有B的公钥KeB) A发起和B的通信 A产生会话密钥Ks，并用KeB加密后传给B B能用自己的私钥KdB解开 他人不会知道Ks,34,对称算法 vs. 公钥算法,速度

13、 典型相差1000倍 密钥管理 对称算法需要额外安全信道 公钥 证书中心 混合密码体制 公钥算法用于签名和认证 用公钥算法传输会话密钥 用会话密钥/对称算法加密批量(bulk)数据,35,作业：用RSA 加密解密,p=5,q=11,e=3,M=9 如果：e=31,n=3599,d=? c=10,e=5,n=35,M能够求出吗？,36,模幂运算的扩展,如197405368125 mod 101,怎么计算,37,直接计算的问题,1.缓冲区溢出 缓冲区溢出的原理 void functon（char *str） char buffer16 ； strcpy（buffer，str）； 该程序的功能是通过strcpy函数把str中的字符串拷贝到数组buffer16中去，如果str的长度超过16就会造成数组buffer的溢