第04章公钥密码体制精选文档.ppt

《第04章公钥密码体制精选文档.ppt》由会员分享，可在线阅读，更多相关《第04章公钥密码体制精选文档.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

3、，共二十五页数论知识简介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本讲稿第四页，共二十五页数论知识简介模运算性质：同余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 n，则(a-b)

4、mod n=0；(a mod n)+(b mod n)mod n=(a+b)mod n；-；*；例：152 mod 12=(3*3)mod 12=95本讲稿第五页，共二十五页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本讲稿第六页，共二十五页n Euler定理：a(n)mod n=1 推论：若a与n

5、互素，则a与a(n)-1 互为逆元。互为逆元。例：a=4，n=7，(7)=6，a(7)-1=45=1024 所以，4和1024在模7下互为逆元。验证：4x1024 mod7=17本讲稿第七页，共二十五页求乘法逆元求乘法逆元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,x3)-(y1,y2,y3);

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

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

9、本讲稿第十三页，共二十五页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本讲稿第十四页，共二十五页二、RSA算法的实现 公开密钥算法RSA加密算法的过程加密算法的过程 1取两个随机大素数p和q（保密）2计算公开的模数n=p*q(公开)3计算秘密的欧拉函数(n)=（

10、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本讲稿第十五页，共二十五页二、RSA算法的实现 公开密钥算法例设p=43,q=59,r=pq=43*59=2537,(r)=(p-1)(q-1)=42*58=2436,取e=13,求e的逆元d解方程 d e=1 mod 24362436=13*187+5

11、,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本讲稿第十六页，共二十五页二、RSA算法的实现 公开密钥算法若有明文public key encryptions先将明文分块为pu bl ic ke nc ry pt io ns将明文数字化令a b z 分别为00 01 25 得1520 0111 0802 1004

12、 24041302 1724 1519 0814 1418利用加密可得密文0095 1648 1410 1299 13651379 2333 2132 1751 128917本讲稿第十七页，共二十五页公开密钥算法关于素数的分布 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，即(X)X/ln(X)=1limxX (X)X/ln(X)(X)X/l

13、n(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本讲稿第十八页，共二十五页二、RSA算法的实现 公开密钥算法在 2到X的区间中，随机选择一个值为素数的概率近似等于(X)/(X-1)。可以证明，在找到一个素数之前，平均

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

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

16、算法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本讲稿第二十二页，共二十五页其它公钥密码体制n背包体制 1978年提出 5年后被 Shamir破解nElGamal 体制 1985年 基于有限域上计算离散对数难解性，已用于DSS(数字签名标准）例：3x mod 17=5，解得：x=6 3x mod

17、13=7，无解n椭圆曲线体制(ECC)1985年 基于离散对数优点：安全性高；密钥短；灵活性好。同等安全下的密钥长度：RSA:512 1024 2048 21000ECC:106 160 211 60023本讲稿第二十三页，共二十五页ElGamel 加密体制：安全性:基于求解离散对数问题的困难性.给定Zp的一个本原元,对Zp*,寻找惟一的整数a(0 a p-2),使得 a=mod p,记为a=log.一般的,如果仔细选择p,则认为该问题是困难的.目前还没有找到计算离散对数问题的多项式时间算法.为了抗击已知的攻击,p至少是150位以上的十进制整数,并且p-1至少有一个大的素因子.24本讲稿第二十四页，共二十五页 要设计一个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本讲稿第二十五页，共二十五页