第8讲 公钥密码学.ppt

1、1,第8讲 公钥密码学,2,公钥密码学,公钥密码学思想 RSA算法 公钥的应用,3,公钥密码学的发展是整个密码学发 展历史中最伟大的一次革命。,公钥密码体制,公钥算法基于数学函数而不是基于替换和置换,它使用两个独立的密钥，在消息的保密性、 密钥分配和认证领域有重要意义。,4,公钥密码比传统密码更安全,两个误解,公钥密码是一种通用的方法，所以 传统密码已经过时。,5,密钥分配问题：如果密钥被偷，设计再好的 密码体制都没有用,传统密码中的两个问题,数字签名问题：能否设计一种方法确保数字 签名出自某个特定的人，并且各方无异议？,6,1976年 Diffie和Hellman针对上述问题提出 了一种方法

2、，它是密码学的一次革命,密码学革命,7,公钥密码体制介绍,8,仅根据密码算法和加密密钥来确定解密密钥在 计算上是不可行的。,公钥密码体制特点,两个密钥中的任何一个可以用来加密，另一个 用来解密。,有6个组成部分：明文、加密算法、公钥、 私钥、密文、解密算法,9,用公钥进行加密,2 Alice产生一对密钥，用于加密和解密,3 Alice将一个密钥公开，另一个密钥私有,Bob,Alice,1 Bob要发送消息给Alice,4 Bob用Alice的公钥对消息加密，发送给Alice。只有Alice能解密,10,公钥进行加密,B的公钥KUb,B的私钥KRb,待发送的明文X,A要发消息给B,Y=EKUb(

3、X),X=DKRb(Y),破译者,11,用公钥进行认证,Bob,Alice,12,用公钥进行认证,A用自己的私钥进行加密Y=EKRa(X),B用A的公钥钥进行解密认证X=DKUa(Y),13,用公钥进行认证:问题？,问题1 需要对整条消息加密，占用大量存储空间,解决的方法：仅对消息的认证符加密,问题2 不能提供保密性,如何解决？,14,公钥体制：保密和认证,15,公钥密码体制的应用,1 加密/解密,2 数字签名,3 密钥交换,算法 RSA 椭圆曲线 Diffie-Hellman DSS,是 是 是,是 是 是,否 否 是,否 是 否,16,对公钥密码体制的要求：,1 B产生一对密钥（KUb，K

4、Rb）在计算上是容易的,2 发送方A加密消息 C=EKUb(M) 在计算上是容易的,3 接收方B对密文解密 M=DKRb(C) 在计算上是容易的,4 攻击者从KUb计算出KRb在计算上不可行的,5 攻击者从KUb和C计算出M在计算上不可行的,6 附加条件（并非所有都满足）：加密解密顺序可 交换： M=EKUb(DKRb(M) ) =DKUb(EKRb(M) ),17,公钥密码学的研究情况,与计算复杂性理论密切相关 计算复杂性理论可以提供指导 但是需求不尽相同 计算复杂性通常针对一个孤立的问题进行研究 而公钥密码学往往需要考虑一些相关的问题比如，密码分析还需要考虑已知明文、选择明文等相关的情形

5、讨论的情形不同 计算复杂性考虑最坏的情形 而对于公钥密码学则是不够的 一个困难问题必然会导致一个保密性很好的密码系统吗？ 不一定，还需要有好的构造,18,背包(knapsack)问题,0-1背包问题： 给定一个正整数S和一个背包向量A=(a1,an)，其中ai是正整数，求满足方程S = aixi 的二进制向量X=(x1,xn)。 这是一个NP完全问题，解决这个问题所需要的时间与n呈指数增长 背包问题用于公钥密码学 做法方法：明文为X，S为密文 奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能 把易解的背包问题修改成难解的背包问题 公开密钥使用难解的背包问题 私钥使用易解的背包问题,1

6、9,易解的背包问题超递增背包,满足下列条件的背包 ai aj (j = 1,i-1) 这样的背包也被称为简单背包 求解 从最大的ai开始，如果S大于这个数，则减去ai, 记xi为1，否则记xi为0 如此下去，直到最小的ai 例如背包序列2, 3, 6, 13, 27, 52 求解70的背包 结果为2, 3, 13, 52 所以，密文70对应的明文为110101,20,转换背包,简单背包用作私钥 如何产生相应的公钥转换 做法： 选择一个整数 m ai (i = 1,n) 然后选择一个与m互素的整数w，然后ai = wai (mod m) (i = 1,n) 这里的ai是伪随机分布的 这样得到的背

7、包是非超递增背包,21,基于背包问题的公钥密码系统MH公钥算法,加密 将明文分为长度为n的块X=(x1,xn) 然后用公钥A = (a1, , an)，将明文变为密文SS = E(X) = aixi 解密 先计算S = w-1S mod m 再求解简单背包问题 S = aixi,22,背包密码系统的意义,是第一个公钥密码系统 有较好的理论价值 在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷,23,只有两个算法被普遍接受,1 RSA,2 椭圆曲线,就是要找一个单向陷门函数：不太容易,24,单向陷门函数（1）,Y=fk(X) 容易(k 和X已知),X=f-1k (Y) 计算上不可行（k

8、未知，Y已知）,X=f-1k (Y) 容易（k已知，Y已知）,寻找合适的单向陷门函数是公钥密码 体制应用关键！,25,单向陷门函数（2）,困难程度 举例 打碎/拼接、平方/开方、乘法/分解 * 单向函数存在否 尚无严格的数学证明,26,单向陷门函数（3）,单向陷门函数 如果知道某个陷门(秘诀)，即能容易恢复x （陷门即为私钥） 举例 魔方的置乱/恢复 如果有那个口诀，就能很快恢复 加密/解密,27,RSA 算法,先从一个简单例子开始 给出算法 证明,28,简单例子,选中两个素数 p7，q17,npq (n)请练习,任务：对明文 M=19 加密,npq119 (n)(p-1)(q-1)61696

9、,选取整数1e (n)与(n) 互素：e5,求e的逆元d：ed1 mod (n) 请练习,计算 C=Me(mod n)=? 其中M=19 请练习,计算 M1=Cd(mod n)=? 请练习,d=77,c=66,29,Exponentiation (c为辅助,求ab),c = 0; f = 1 for i = k downto 0 do c = 2 c f = (f f) mod n if bi = 1 then c = c + 1 f = (f a) mod n return f 这里b可以先看成2的整数幂,便于理解,30,RSA 示例总结,选p7，q17 则npq119 且(n)(p-1)(

10、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 n = 6677mod 11919 mod 119,31,设置参数p,q,d,e,bool rsa:set_pqde( int m_in, int e_in ) e=e_in; m=m_in; p=depart(m_in); q=m_in/p; if(p=1 | p=2 | !prime(q) ) return false; /2 n=(p-1)*(q-1);

11、d=n/e;/这里要注意e与n要互素？ while( ( (e*d)%n )!=1 ) d+; /3 max=m_in; while( maxmaxint ) max+=m_in; max=max-m_in; return true; ,32,分解整数x,int rsa:depart( int x ) int i; if(prime(x) return 1; /X是素数 if(!(x%2) return 2;/X是偶数 i=3; while(x%i) i+; return i; ,33,素数测试,bool rsa:prime( int x ) int i; if (x=1)return fal

12、se; /合数 if (x=2)return true; /素数 if ( !(x%2) ) return false; for(i=3;i=sqrt(x);i+=2) if(!(x%i) return false; return true; ,34,加密算法,int rsa:rsaencry(int x,int y,int m ) int yy,li; double l; if( y=1 ) return x%m; yy=y%2;/分几偶数 if( yy=0 ) l=rsaencry(x,y/2,m); l=l*l; while( lmaxint ) l=l-max; li=(int)l;

13、return li%m; else l=rsaencry(x,y-1,m); l=l*x; while( lmaxint ) l=l-max; li=(int)l; return li%m; ,35,解密算法,int rsa:rsadecode(int x,int y,int m) int x1=x,y1=y,f1=1; while(y1!=0) while(y1%2=0) y1=y1/2; x1=ff(x1,x1,m); y1=y1-1; f1=ff(f1,x1,m); return f1; ,36,37,RSA算法,作者 1977年，R, S, A Ron Rivesthttp:/theo

14、/rivest/ Adi Shamirhttp:/www.wisdom.weizmann.ac.il/shamir/ Len Adleman /dept/molecular-science/ 基本参数 分组密码算法 基于整数乘法 明/密文分组以及公/私钥被看作小于n的整数 加/解密是模乘运算,38,RSA算法总结：密钥产生,找素数 选取两个大的随机的素数p，q 计算模n和Euler函数(n) npq (n)=(p-1)(q-1) 找ed1 mod (n) 随机取一个数e(与(n)互素)，用扩展Euclid算法求d即可 发布 d保密，

15、(d, n)是私钥 KU 发布(e,n)，这是公钥KR 销毁p、q,39,RSA的正确性,加密 明文分组m做为整数须小于n c=me mod n 解密 m=cd mod n 证明 依据Euler定理，在mod n的含义下有： cd(me)dmed mk(n)+1 (m(n)k mm,40,RSA考虑,素数 必须够大，否则对手可能很快分解n 判定，采用Miller-Rabin概率测试方法 假素数意味着加解密不能正确进行，故可放弃之 强素数 (p-1)/2和(q-1)/2应是素数 选取较小的e和较大的d e：3、65537 快速计算xy%z 发布公钥 证书中心 CA,41,攻击RSA,数学方法 分解n 得到p和q，就可以知道(n)，就可从e求得d 直接求(n) 不分解n，而直接求(n)，再求d 直接求d 不求(n)，直接求d,42,43,阅读：RSA挑战赛,44,使用公钥传递会话密钥,直接使用公钥算法太慢 对称算法一般几十兆字节/秒 1024位RSA解密约100多次/秒(加密快10倍以上) 只用来传递会话密钥 (假设A已经有B的公钥KeB) A发起和B的通信 A产生会话密钥Ks，并用