第04章公钥密码体制优秀PPT.ppt

上传人:石*** 文档编号:78779097 上传时间:2023-03-19 格式:PPT 页数:25 大小:1.38MB
返回 下载 相关 举报
第04章公钥密码体制优秀PPT.ppt_第1页
第1页 / 共25页
第04章公钥密码体制优秀PPT.ppt_第2页
第2页 / 共25页
点击查看更多>>
资源描述

《第04章公钥密码体制优秀PPT.ppt》由会员分享,可在线阅读,更多相关《第04章公钥密码体制优秀PPT.ppt(25页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第04章公钥密码体制章公钥密码体制1现在学习的是第1页,共25页一、RSA算法概述 传统密码体制的缺陷传统密码体制的缺陷:密钥管理的麻烦:密钥管理的麻烦:n个用户保存个用户保存n*(n-1)/2个密钥。个密钥。不能提供法律证据不能提供法律证据:不仅要保密还要解决证实问题。1976年,美国学者Diffie和Hellman发表了著名论文密码学的新方向,提出了建立“公开密钥密码体制”:若用户A有加密密钥ka(公开),不同于解秘密钥ka(保密),要求ka的公开不影响ka的安全。若B要向A保密送去明文m,可查A的公开密钥ka,若用ka加密得密文c,A收到c后,用只有A自己才掌握的解密密钥ka对x进行解

2、密得到m。公开密钥算法 2现在学习的是第2页,共25页一、RSA算法概述 1978年,美国麻省理工学院(MIT)的研究小组成员:李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提出了一种基于公钥密码体制的优秀加密算法RSA算法。RSA算法是一种分组密码体制算法,它的保密强度是建立在具有大素数因子的合数,其因子分解是困难的。是否是NP问题尚未确定。RSA得到了世界上的最广泛的应用,ISO在1992年颁布的国际标准X.509中,将RSA算法正式纳入国际标准。1999年美国参议院已通过了立法,规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力。公开密钥算法3现在

3、学习的是第3页,共25页数论知识简介n互素:若gcd(a,b)=1,则整数a和b互素。n定义:若ax mod n=1,则称a与x对于模n互为逆元。n用Euclid算法求乘法逆元 若a和n互素,则a在模n下有逆元。nEuler函数:(n)=与n互素的、小于n的正整数的个数,n1。例:(3)=(4)=(6)=2,(5)=4,(7)=6 (12)=6 4现在学习的是第4页,共25页数论知识简介模运算性质:同余n模运算满足自反性、对称性、传递性;a=a mod n;若a=b mod n,则b=a mod n;若a=b mod n,b=c mod n,则a=c mod nn若a mod n=b mod

4、n,则(a-b)mod n=0;(a mod n)+(b mod n)mod n=(a+b)mod n;-;*;例:152 mod 12=(3*3)mod 12=95现在学习的是第5页,共25页n若n是素数,则(n)=n-1 若n=p*q,p、q是素数,则(n)=(p-1)*(q-1)例:(21)=(3*7)=2*6=12nFermat小定理:若m是素数,且a不是m的倍数,则am-1 mod m=1。或者:若m是素数,则am mod m=a例:46 mod 7=4096 mod 7=1 47 mod 7=16384 mod 7=46现在学习的是第6页,共25页n Euler定理:a(n)mod

5、 n=1 推论:若a与n互素,则a与a(n)-1 互为逆元。互为逆元。例:a=4,n=7,(7)=6,a(7)-1=45=1024 所以,4和1024在模7下互为逆元。验证:4x1024 mod7=17现在学习的是第7页,共25页求乘法逆元求乘法逆元Function Euclid(d,f)/求d在模f下的逆元1)(x1,x2,x3)-(1,0,f);(y1,y2,y3)-(0,1,d);2)If y3=1 then print“逆元是”y2 else print“无逆元”;End.3)Q=x3/y34)(t1,t2,t3)-(x1-Q*y1,x2-Q*y2,x3-Q*y3)5)(x1,x2,x

6、3)-(y1,y2,y3);6)(y1,y2,y3)-(t1,t2,t3)7)Go to 2)8现在学习的是第8页,共25页高次幂剩余的运算公开密钥算法要计算 gn mod p,因g、n、p都是大数而不能采用先高次幂再求剩余的方法来处理,而要采用平方取模的算法,即每一次平方或相乘后,立即取模运算。欧几里德算法欧几里德算法可以迅速地找出给定的两个整数a和b的最大公因数 gcd(a,b),并可判断a与b是否互素,因此该算法可用来寻找加密密钥和解密密钥。9现在学习的是第9页,共25页X r mod p 的快速算法流程图的快速算法流程图 A-xB-rC-1B=0输出CB mod 2=0B-B/2A-A

7、*A mod pB-B-1C-C*A mod pYNNY10现在学习的是第10页,共25页一、RSA算法概述 公开密钥算法每个合数都可以唯一地分解出素数因子6=2 3999999=333711133727641 =131121从2 开始试验每一个小于等于27641 的素数。素数:只能被1和它本身整除的自然数;否则为合数。整数n的十进制位数 因子分解的运算次数 所需计算时间(每微秒一次)501.4x10103.9小时759.0 x1012104天1002.3x101574年2001.2x10233.8x109年3001.5x10294.0 x1015年5001.3x10394.2x1025年11

8、现在学习的是第11页,共25页素数的检验素数的产生目前,适用于RSA算法的最实用的办法是概率测试法。该法的思想是随机产生一个大奇数,然后测试其是否满足条件,如满足,则该大奇数可能是素数,否则是合数。素数定理说明素数有无穷多个,同时也说明通过随机产生一个大奇数来判断其素性是具有实用性的。12现在学习的是第12页,共25页素数的检验nWilson定理:P是素数 (P-1)!Mod P=-1 当P较大时,很费时间,无实际价值。nRabin-Miller方法 概率检验 Witness(a,n)/*将n-1表示为 bk b k-1b0的形式 n是待检验的数,a是小于n的整数。若返回True,则n肯定不是

9、素数;若返回False,则n有可能是素数。*/13现在学习的是第13页,共25页Rabin-Miller方法方法 d=1 for i=k down to 0 x=d;d=(d d)mod n;if d=1&(x1)&(x-1)return True;if bi=1 then d=(da)mod n if d1 then return True;return False;对于s个不同的a,重复调用此算法,每次返回False,则n是素数的概率至少为1-2-s14现在学习的是第14页,共25页二、RSA算法的实现 公开密钥算法RSA加密算法的过程加密算法的过程 1取两个随机大素数p和q(保密)2计算

10、公开的模数n=p*q(公开)3计算秘密的欧拉函数(n)=(p-1)*(q-1)(保密),丢弃p和q,不要让任何人知道。4随机选取整数e,满足 gcd(e,(n)=1(公开e加密密钥)5计算d满足de1(mod(n)(保密d解密密钥)6将明文x(按模为r自乘e次幂以完成加密操作,从而产生密文y(X、Y值在0到n-1范围内)。Y=xe mod n7解密:将密文y按模为n自乘d次幂。X=Yd mod n15现在学习的是第15页,共25页二、RSA算法的实现 公开密钥算法例设p=43,q=59,r=pq=43*59=2537,(r)=(p-1)(q-1)=42*58=2436,取e=13,求e的逆元d

11、解方程 d e=1 mod 24362436=13*187+5,13=2*5+35=3+2,3=2+1所以1=3-2,2=5-3,3=13-2*55=2436-13*187所以,1=3-2=3-(5-3)=2*3-5=2*(13-2*5)-5=2*13-5*5=2*13-5*(2436-13*187)=937*13-5*2346即937*13 1 mod 2436取e=13 时d=93716现在学习的是第16页,共25页二、RSA算法的实现 公开密钥算法若有明文public key encryptions先将明文分块为pu bl ic ke nc ry pt io ns将明文数字化令a b z

12、 分别为00 01 25 得1520 0111 0802 1004 24041302 1724 1519 0814 1418利用加密可得密文0095 1648 1410 1299 13651379 2333 2132 1751 128917现在学习的是第17页,共25页公开密钥算法关于素数的分布 1-100 25 101-200 21 201-300 16 301-400 16 401-500 17 501-600 14 601-700 16 701-800 14 801-900 15 901-1000 14素数定理:当X变得很大时,从2到X区间的素数数目(X)与X/ln(X)的比值趋近于1,

13、即(X)X/ln(X)=1limxX (X)X/ln(X)(X)X/ln(X)1000 168 145 1.159 10,000 1,229 1,086 1.132 100,000 9,592 8,686 1.1041,000,000 78,498 72,382 1.084 10,000,000 664,579 620,421 1.071 100,000,000 5,761,455 5,428,681 1.0611,000,000,000 50,847,478 48,254,942 1.05418现在学习的是第18页,共25页二、RSA算法的实现 公开密钥算法在 2到X的区间中,随机选择一个值

14、为素数的概率近似等于(X)/(X-1)。可以证明,在找到一个素数之前,平均要进行(X-1)/(X)LN(X)次实验。大数的运算上百位大数之间的运算是实现RSA算法的基础,因此程序设计语言本身提供的加减乘除及取模算法都不能使用,否则会产生溢出,必须重新编制算法。在编程中要注意进位和借位,并定义几百位的大数组来存放产生的大数。19现在学习的是第19页,共25页RSA 的安全性的安全性公开密钥算法依赖于大数分解,但是否等同于大数分解一直未能证明。不管怎样,分解n是最显然的攻击方法。1994年4月26日,美国各大媒体报道:由RSA发明人在17年前出的129位数字已被因子分解,并破解了附带的密语:The

15、 magic words are squeamish ossifrage.目前,已能分解140位十进制的大素数。因此,模数n必须选大一些。RSA最快的情况也比DES慢上100倍,无论是软件还是硬件实现。速度一直是RSA的缺陷。一般只用于少量数据加密。20现在学习的是第20页,共25页 RSA算法的脆弱性公开密钥算法1)不能证明RSA密码破译等同于大数因子分解2)速度问题 提高pq将使开销指数级增长3)至少有9个明文,加密后不变,即me mod n=m4)普通用户难于选择p、q。对p、q的基本要求:p、q不相同,即不要太接近,又不能差别太大p-1、q-1都有大素数因子,增加猜测(r)难度Gcd(

16、p-1,q-1)应当小21现在学习的是第21页,共25页 RSA算法的脆弱性公开密钥算法5)P、q选择不当,则变换周期性、封闭性而泄密 例:p=17,q=11,e=7,则n=187。设m=123,则 C1=1237 mod 187=183 C2=1837 mod 187=72 C3=727 mod 187=30 C4=307 mod 187=123 明文m经过4次加密,恢复成明文。总之,RSA对用户要求太苛刻,密钥不能常更换。22现在学习的是第22页,共25页其它公钥密码体制n背包体制 1978年提出 5年后被 Shamir破解nElGamal 体制 1985年 基于有限域上计算离散对数难解性

17、,已用于DSS(数字签名标准)例:3x mod 17=5,解得:x=6 3x mod 13=7,无解n椭圆曲线体制(ECC)1985年 基于离散对数优点:安全性高;密钥短;灵活性好。同等安全下的密钥长度:RSA:512 1024 2048 21000ECC:106 160 211 60023现在学习的是第23页,共25页ElGamel 加密体制:安全性:基于求解离散对数问题的困难性.给定Zp的一个本原元,对Zp*,寻找惟一的整数a(0 a p-2),使得 a=mod p,记为a=log.一般的,如果仔细选择p,则认为该问题是困难的.目前还没有找到计算离散对数问题的多项式时间算法.为了抗击已知的

18、攻击,p至少是150位以上的十进制整数,并且p-1至少有一个大的素因子.24现在学习的是第24页,共25页 要设计一个ELGamal密码体制,需要完成如下的步骤:(1)选足够大的素数P使得求解离散对数问题的在Zp上是困难的;(2)在Zp*中选择一个本原元;(3)随机选一整数a,使得a(0 a p-2),并计算 =a mod p;(4)对密钥k=(p,a,),定义加密变换 ek(x,r)=(y1,y2),这里明文x Zp*,r(0 r p-2)是每次加密前选择的随机数,y1=ar mod p,y2=x r mod p;定义解密变换为dk(y1,y2)=y2(y1a)-1 这里密文(y1,y2)Zp*x Zp*;(5)以p,为公开密钥,a为私有密钥.25现在学习的是第25页,共25页

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 生活休闲 > 资格考试

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁