《第8讲 公钥密码学.ppt》由会员分享,可在线阅读,更多相关《第8讲 公钥密码学.ppt(46页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第8讲 公钥密码学1 公钥密码学o公钥密码学思想oRSA算法o公钥的应用2 公钥密码学的发展是整个密码学发公钥密码学的发展是整个密码学发展历史中最伟大的一次革命。展历史中最伟大的一次革命。公钥密码体制公钥算法基于数学函数而不是基于替换和置换公钥算法基于数学函数而不是基于替换和置换它使用两个独立的密钥,在消息的保密性、它使用两个独立的密钥,在消息的保密性、密钥分配和认证领域有重要意义。密钥分配和认证领域有重要意义。3 公钥密码比传统密码更安全公钥密码比传统密码更安全两个误解公钥密码是一种通用的方法,所以公钥密码是一种通用的方法,所以传统密码已经过时。传统密码已经过时。4 密钥分配问题:如果密钥
2、被偷,设计再好的密钥分配问题:如果密钥被偷,设计再好的密码体制都没有用密码体制都没有用传统密码中的两个问题数字签名问题:能否设计一种方法确保数字数字签名问题:能否设计一种方法确保数字签名出自某个特定的人,并且各方无异议?签名出自某个特定的人,并且各方无异议?5 1976年年 Diffie和和Hellman针对上述问题提出针对上述问题提出了一种方法,它是密码学的一次革命了一种方法,它是密码学的一次革命密码学革命6 公钥密码体制介绍7 仅根据仅根据密码算法密码算法和和加密密钥加密密钥来确定来确定解密密钥解密密钥在在计算上是不可行的。计算上是不可行的。公钥密码体制特点两个密钥中的任何一个可以用来加密
3、,另一个两个密钥中的任何一个可以用来加密,另一个用来解密。用来解密。有有6个组成部分:明文、加密算法、公钥、个组成部分:明文、加密算法、公钥、私钥、密文、解密算法私钥、密文、解密算法8 用公钥进行加密2 Alice产生一对密钥,用于加密和解密3 Alice将一个密钥公开,另一个密钥私有BobAlice1 Bob要发送消息给Alice4 Bob用Alice的公钥对消息加密,发送给Alice。只有Alice能解密9 公钥进行加密B的公钥KUbB的私钥KRb待发送的明文XA要发消息给BY=EKUb(X)X=DKRb(Y)破译者10 用公钥进行认证BobAlice11 用公钥进行认证A用自己的私钥进行
4、加密Y=EKRa(X)B用A的公钥钥进行解密认证X=DKUa(Y)12 用公钥进行认证:问题?问题1 需要对整条消息加密,占用大量存储空间解决的方法:仅对消息的认证符加密问题2 不能提供保密性如何解决?13 公钥体制:保密和认证14 公钥密码体制的应用1 加密/解密2 数字签名3 密钥交换算法 RSA 椭圆曲线 Diffie-Hellman DSS是是是是是是是是是是是是否否否否是是否否是是否否15 对公钥密码体制的要求:1 B产生一对密钥(KUb,KRb)在计算上是容易的2 发送方A加密消息 C=EKUb(M)在计算上是容易的3 接收方B对密文解密 M=DKRb(C)在计算上是容易的4 攻击
5、者从KUb计算出KRb在计算上不可行的5 攻击者从KUb和C计算出M在计算上不可行的6 附加条件(并非所有都满足):加密解密顺序可交换:M=EKUb(DKRb(M)=DKUb(EKRb(M)16 公钥密码学的研究情况o与计算复杂性理论密切相关o计算复杂性理论可以提供指导n但是需求不尽相同o计算复杂性通常针对一个孤立的问题进行研究o而公钥密码学往往需要考虑一些相关的问题比如,密码分析还需要考虑已知明文、选择明文等相关的情形n讨论的情形不同o计算复杂性考虑最坏的情形o而对于公钥密码学则是不够的o一个困难问题必然会导致一个保密性很好的密码系统吗?n不一定,还需要有好的构造17 背包(knapsack
6、)问题o0-1背包问题:n给定一个正整数S和一个背包向量A=(a1,an),其中ai是正整数,求满足方程S=aixi 的二进制向量X=(x1,xn)。n这是一个NP完全问题,解决这个问题所需要的时间与n呈指数增长o背包问题用于公钥密码学n做法方法:明文为X,S为密文n奥妙在于有两类背包,一类可以在线性时间内求解,另一类则不能n把易解的背包问题修改成难解的背包问题o公开密钥使用难解的背包问题o私钥使用易解的背包问题18 易解的背包问题超递增背包o满足下列条件的背包ai aj(j=1,i-1)o这样的背包也被称为简单背包o求解n从最大的ai开始,如果S大于这个数,则减去ai,记xi为1,否则记xi
7、为0n如此下去,直到最小的aio例如背包序列2,3,6,13,27,52n求解70的背包o结果为2,3,13,52o所以,密文70对应的明文为11010119 转换背包o简单背包用作私钥o如何产生相应的公钥转换n做法:选择一个整数 m ai(i=1,n)然后选择一个与m互素的整数w,然后ai=wai(mod m)(i=1,n)这里的ai是伪随机分布的这样得到的背包是非超递增背包20 基于背包问题的公钥密码系统MH公钥算法o加密n将明文分为长度为n的块X=(x1,xn)n然后用公钥A=(a1,an),将明文变为密文SS=E(X)=aixio解密n先计算S=w-1S mod mn再求解简单背包问题
8、S=aixi21 背包密码系统的意义o是第一个公钥密码系统o有较好的理论价值o在实践过程中,大多数的背包方案都已被破解,或者证明存在缺陷22 只有两个算法被普遍接受1 RSA2 椭圆曲线 就是要找一个单向陷门函数:不太容易23 单向陷门函数(1)Y=fk(X)容易(k 和X已知)X=f-1k(Y)计算上不可行(k未知,Y已知)X=f-1k(Y)容易(k已知,Y已知)寻找合适的单向陷门函数是公钥密码体制应用关键!24 单向陷门函数(2)o困难程度o举例n打碎/拼接、平方/开方、乘法/分解*单向函数存在否n尚无严格的数学证明25 单向陷门函数(3)o单向陷门函数n如果知道某个陷门(秘诀),即能容易
9、恢复xn(陷门即为私钥)o举例n魔方的置乱/恢复o如果有那个口诀,就能很快恢复n加密/解密26 RSA 算法o先从一个简单例子开始o给出算法o证明27 简单例子选中两个素数 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 n)=?其中M=19 请练习 计算 M1=Cd(mod n)=?请练习 d=77c=6628 Exponentiation(c为辅助,求ab)c=0;f=1for i=k downto 0 do c=2 c f=(f
10、 f)mod n if bi=1 then c=c+1 f=(f a)mod n return f 这里b可以先看成2的整数幂,便于理解29 RSA 示例总结o选p7,q17则npq119且(n)(p-1)(q-1)61696o取e5则d77 (57738549611 mod 96)o公钥(5,119),私钥(77,119)o加密m19则cme mod n=195 mod 119=66 mod 119o解密c66mcd mod n=6677mod 11919 mod 11930 设置参数p,q,d,eoboolrsa:set_pqde(intm_in,inte_in)ooe=e_in;om=m
11、_in;op=depart(m_in);oq=m_in/p;oif(p=1|p=2|!prime(q)ooreturnfalse;oo/2on=(p-1)*(q-1);od=n/e;/这里要注意这里要注意e与与n要互素?要互素?owhile(e*d)%n)!=1)d+;o/3omax=m_in;owhile(maxmaxint)max+=m_in;omax=max-m_in;oreturntrue;o31 分解整数xoint rsa:depart(int x)ooint i;oif(prime(x)return 1;/X是素数oif(!(x%2)return 2;/X是偶数oi=3;owhil
12、e(x%i)ooi+;ooreturn i;o32 素数测试obool rsa:prime(int x)ooint i;oif(x=1)return false;/合数oif(x=2)return true;/素数oif(!(x%2)return false;ofor(i=3;imaxint)l=l-max;oli=(int)l;oreturnli%m;ooelseool=rsaencry(x,y-1,m);ol=l*x;owhile(lmaxint)l=l-max;oli=(int)l;oreturnli%m;oo34 解密算法oint rsa:rsadecode(int x,int y,i
13、nt m)ooint x1=x,y1=y,f1=1;owhile(y1!=0)oowhile(y1%2=0)ooy1=y1/2;ox1=ff(x1,x1,m);ooy1=y1-1;of1=ff(f1,x1,m);ooreturn f1;o35 36 RSA算法o作者n1977年,R,S,AoRon Rivesthttp:/theory.lcs.mit.edu/rivest/oAdi Shamirhttp:/www.wisdom.weizmann.ac.il/shamir/oLen Adleman http:/www.usc.edu/dept/molecular-science/o基本参数n分组
14、密码算法n基于整数乘法n明/密文分组以及公/私钥被看作小于n的整数n加/解密是模乘运算37 RSA算法总结:密钥产生o找素数n选取两个大的随机的素数p,qo计算模n和Euler函数(n)nnpqn(n)=(p-1)(q-1)o找ed1 mod(n)n随机取一个数e(与(n)互素),用扩展Euclid算法求d即可o发布nd保密,(d,n)是私钥 KUn发布(e,n),这是公钥KRn销毁p、q38 RSA的正确性o加密明文分组m做为整数须小于nc=me mod no解密m=cd mod no证明依据Euler定理,在mod n的含义下有:cd(me)dmed mk(n)+1(m(n)k mm 39
15、 RSA考虑o素数n必须够大,否则对手可能很快分解nn判定,采用Miller-Rabin概率测试方法o假素数意味着加解密不能正确进行,故可放弃之n强素数o(p-1)/2和(q-1)/2应是素数o选取较小的e和较大的dne:3、65537o快速计算xy%zo发布公钥n证书中心 CA40 攻击RSA数学方法o分解nn得到p和q,就可以知道(n),就可从e求得do直接求(n)n不分解n,而直接求(n),再求d o直接求d n不求(n),直接求d 41 http:/ 阅读:RSA挑战赛o numberdigitsprizefactored(references)RSA-100100Apr.1991RS
16、A-110110Apr.1992RSA-120120Jun.1993RSA-129129$100Apr.1994(Leutwyler1994,Cipra1995)RSA-130130Apr.10,1996RSA-140140Feb.2,1999(teRiele1999a)RSA-150150withdrawn?Apr.6,2004(Aoki2004)RSA-155155Aug.22,1999(teRiele1999b,Peterson1999)RSA-160160Apr.1,2003(Bahret al.2003)RSA-576174$10kDec.3,2003(Franke2003)RSA-
17、64019320kopenRSA-70421230kopenRSA-76823250kopenRSA-89627075kopenRSA-1024309100kopenRSA-1536463150kopenRSA-2048617200kopen43 使用公钥传递会话密钥 o直接使用公钥算法太慢n对称算法一般几十兆字节/秒n1024位RSA解密约100多次/秒(加密快10倍以上)o只用来传递会话密钥n(假设A已经有B的公钥KeB)nA发起和B的通信nA产生会话密钥Ks,并用KeB加密后传给BnB能用自己的私钥KdB解开n他人不会知道Ks44 对称算法 vs.公钥算法o安全性o速度n典型相差1000倍o密钥管理n对称算法需要额外安全信道n公钥o证书中心o混合密码体制n公钥算法用于签名和认证n用公钥算法传输会话密钥n用会话密钥/对称算法加密批量(bulk)数据45 作业:用RSA 加密解密op=3,q=11,e=7,M=5op=5,q=11,e=3,M=9o如果:e=31,n=3599,d=?oc=10,e=5,n=35,M能够求出吗?od=3,27,546