密码学sec-chap06.07.ppt

《密码学sec-chap06.07.ppt》由会员分享，可在线阅读，更多相关《密码学sec-chap06.07.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六、七讲第六、七讲 公钥密码公钥密码第第6讲的主要内容讲的主要内容公钥密码体制的基本概念公钥密码体制的基本概念常用的数论知识常用的数论知识公钥算法公钥算法 1/2/20232公钥密码公钥密码公钥密码体制基本概念公钥密码体制基本概念公钥密码(又称双钥密码和非对称密码)，是1976年由W.Diffie和 M.Hellman在其“密码学新方向”一文中提出的，见划时代的文献（救密码学于穷途末路）W.Diffie and M.E.Hellman,New Directrions in Cryptography,IEEE Transaction on Information Theory,V.IT-22.

2、No.6,Nov 1976,PP.644-654 1/2/20233公钥密码公钥密码公钥密码体制基本概念公钥密码体制基本概念(Cont.)Cont.)三个误解三个误解1、更安全？、更安全？2、对称加密过时了？、对称加密过时了？3、密钥分配简单了？、密钥分配简单了？1/2/20234公钥密码公钥密码公钥密码体制基本概念公钥密码体制基本概念(Cont.)Cont.)两个动因两个动因1、密钥管理、密钥管理2、”数字签名数字签名”1/2/20235公钥密码公钥密码双钥体制（公钥体制）双钥体制（公钥体制）系统中，加密密钥称公开密钥（系统中，加密密钥称公开密钥（public Key）可以公开发布（电话号码

3、注册）；而解密密可以公开发布（电话号码注册）；而解密密钥称私人密钥（钥称私人密钥（private key,简称私钥）。简称私钥）。加密：图加密：图9.2M=D(E(M,pub-key),private-key)认证：图认证：图9.3M=E(D(M,private-key),pub-key)1/2/20236公钥密码公钥密码双钥体制（公钥体制）双钥体制（公钥体制）同时实现加密和认证同时实现加密和认证(A-B)图图9.4C:A发给发给B的密文的密文c=E(E(m,private-key-A),pub-key-B)m：B恢复出的明文恢复出的明文m=D(D(c,private-key-B),pub-k

4、ey-A)和对称加密有何不同之处？和对称加密有何不同之处？1/2/20237公钥密码公钥密码对称加密和公钥加密 1/2/20238公钥密码公钥密码公钥密码体制基本概念公钥密码体制基本概念(Cont.)Cont.)单向函数单向函数是满足下列条件的函数f：(1)给定x，计算y=f(x)是容易的；(2)给定y,计算x使y=f(x)是困难的。(所谓计算x=f-1(Y)困难是指计算上相当复杂，已无实际意义。)1/2/20239公钥密码公钥密码公钥密码体制基本概念公钥密码体制基本概念(Cont.)Cont.)陷门单向函数陷门单向函数满足以上（1），（2）和（3）存在，已知 时,对给定的任何y，若相应的x存

5、在，则计算x使y=f(x)是容易的。称为陷门信息。1/2/202310公钥密码公钥密码公钥密码体制基本概念公钥密码体制基本概念(Cont.)Cont.)用于公钥体制的陷门单向函数用于公钥体制的陷门单向函数n离散对数问题n大数分解n二次剩余问题n多项式求根 1/2/202311公钥密码公钥密码公钥密码体制基本概念公钥密码体制基本概念(Cont.)Cont.)公钥体制的应用公钥体制的应用n加密解密n数字签名n密钥交换某些算法适合所有的三种应用，而有些可能只适用于这些应用的一种或两种。1/2/202312公钥密码公钥密码常用数学基础常用数学基础素数素数（质数）（质数）模运算模运算费马定理（小）和欧拉

6、定理素数检测欧几里德算法中国剩余定理离散对数 1/2/202313公钥密码公钥密码整除对整数对整数 b!=0b!=0 及及 a,如果存在整数 mm 使得使得 a=a=mbmb,称称 b b 整除整除 a,a,也称也称b b是是a a的因子的因子记作记作 b|ab|a 例例 1,2,3,4,6,8,12,241,2,3,4,6,8,12,24 整除整除 2424 1/2/202314公钥密码公钥密码素数与不可约多项式素数素数:只有因子只有因子 1 和自身和自身1 是一个平凡素数是一个平凡素数例例 2,3,5,7 是素数是素数,4,6,8,9,10 不是不是素多项式或不可约多项式素多项式或不可约多

7、项式irreducible:不可写成其他因式的乘积不可写成其他因式的乘积 x x2 2+x=+x=（x x）（）（x+1 x+1）是非不可约多项式是非不可约多项式;x x3 3+x+1+x+1 是不可约多项式是不可约多项式 1/2/202315公钥密码公钥密码一些素数200 以内的素数以内的素数:2 3 5 7 11 13 17 19 23 29 31 37 41 43 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 47 53 59 61 67 71 73 79 83 89 97 101 1

8、03 107 109 113 127 131 137 139 149 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 151 157 163 167 173 179 181 191 193 197 199 197 199 1/2/202316公钥密码公钥密码素数分解(PrimeFactorisationPrimeFactorisation)把把整数整数n写成素数的乘积写成素数的乘积分解整数要比乘法困难分解整数要比乘法困难整数整数 n n的素数分解是把它写素数的乘积的素数分解是把它写素数的乘积 eg.

9、91=7 13;3600=291=7 13;3600=24 4 3 32 2 5 52 2 公式公式8.1小节小节 任意整数的表示方法任意整数的表示方法.*1/2/202317公钥密码公钥密码整数互素整数整数 a,ba,b 互素是指互素是指 它们没有除它们没有除1之外的之外的其它因子其它因子 GCD(a,b)=18 与与15 互素互素 8的因子的因子1,2,4,8 15的因子的因子 1,3,5,15 1 是唯一的公因子是唯一的公因子 1/2/202318公钥密码公钥密码模运算同余同余(congruence)for a b mod na b mod n 如果如果a,b 除以除以n,余数相同余数相

10、同eg.100 34 mod 11100 34 mod 11 b b 叫做叫做a模模n的剩余的剩余 通常通常 0=0=b=n-1b=n-1 eg.-12mod7 -5mod7 2mod7 9mod7-12mod7 -5mod7 2mod7 9mod7 可以进行整数运算可以进行整数运算 1/2/202319公钥密码公钥密码模运算举例-21-20-19-18-17-16 15-21-20-19-18-17-16 15-14-13-12 -11-10 -9 -8-14-13-12 -11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 -7 -6 -5 -4 -3 -2 -1 0 1 2

11、 3 4 5 6 7 8 9 10 11 12 13 7 8 9 10 11 12 13 14 15 16 17 18 19 20 14 15 16 17 18 19 20 21 22 23 24 25 26 27 21 22 23 24 25 26 27 28 29 30 31 32 33 34 28 29 30 31 32 33 34 1/2/202320公钥密码公钥密码模算术运算加法a+b mod na+b mod n 减法a-b mod n=a+(-b)mod na-b mod n=a+(-b)mod n 1/2/202321公钥密码公钥密码运算法则类似于正常算术运算类似于正常算术运算

12、:结合律:(a+b)+c=a+(b+c)mod na+b)+c=a+(b+c)mod n 交换 律分配律(a+b).c=(a.c)+(b.c)mod na+b).c=(a.c)+(b.c)mod n 加法单位元乘法单位元0+0+w=w mod nw=w mod n 1 1w=w mod nw=w mod n 乘法运算类同乘法运算类同 1/2/202322公钥密码公钥密码模运算一个有用的性质(a mod n)+(b mod n)mod n=(a+b)mod n(a mod n)*(b mod n)mod n=(a*b)mod n求模运算下的乘方求模运算下的乘方?1/2/202323公钥密码公钥密

13、码费马定理和欧拉定理费马定理：费马定理：8.2.1欧拉定理：欧拉定理：8.2.3 1/2/202324公钥密码公钥密码素数检测算法方程方程x2 1(mod p)的解不是的解不是1或者或者-1则则n不是素数。不是素数。概率检测算法。概率检测算法。1/2/202325公钥密码公钥密码欧几里德算法寻找两个整数的最大公因子。寻找两个整数的最大公因子。辗转相除法。辗转相除法。可以参见高中课本。可以参见高中课本。1/2/202326公钥密码公钥密码中国剩余定理设设m1,m2,mk是两两互素的正整数，即是两两互素的正整数，即（mi,mj）=1,i!=j,i,j=1,2,k则同余方程组则同余方程组xb1 mo

14、d m1 xb2 mod m2 xbk mod mk模模m1,m2,mk有唯一解有唯一解即在模即在模m1,m2,mk的意义下，存在唯一的的意义下，存在唯一的x，满足满足 xbi mod m1,m2,mk i=1,2,k 1/2/202327公钥密码公钥密码中国剩余定理-一个有用的推论如果：如果：Gcd(a,b)=1则存在则存在s,t 使得使得(s,t可能是负数可能是负数)1=s*a+t*b为什么？为什么？因为因为1=1 mod a 1=1 mod b 所以：所以：1=s*a+t*b 1/2/202328公钥密码公钥密码离散对数阶阶 am 1 mod n指数指数 (以某个数为底以某个数为底)本原

15、根本原根离散对数（注意是在有限域中是困难问题。离散对数（注意是在有限域中是困难问题。*）1/2/202329公钥密码公钥密码公钥算法Diffie和Hellman开创性的论文为密码学带来新的方法和挑战。RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的（见Communitions of the ACM.Vol.21.No.2.Feb.1978,PP.120-126)该算法的数学基础是初等数论中的Euler（欧拉)定理，并建立在大整数因子的困难性之上。RSA是最早的公钥体制的挑战响应者，也是最受广泛接受和实现的公钥体制。1/2/202330公钥密码公钥密码公钥算法密码

16、体制描述如下：密码体制描述如下：n首先，明文空间P，密文空间C=Zn.(分组是小于或等于log2n的整数).n密钥的生成 选择p,q，p,q为互素数，计算n=p*q,(n)=(p-1)(q-1)选择整数e 使(n),e)=1,1e(n),计算d,使d e-1 mod (n),公钥KU=e,n;私钥KR=d,n。1/2/202331公钥密码公钥密码公钥算法密码体制描述如下：密码体制描述如下：n加密(用e,n)明文：Mn 密文：C=Me(mod n).n解密(用d,n)密文：C 明文：M=Cd（mod n)1/2/202332公钥密码公钥密码公钥算法成立的理由成立的理由因选择d，e使得d e-1

17、mod (n),有：ed 1 mod (n),根据Euler定理的推论：给定满足n=pq的两个素数p和q，以及满足0Mn的整数M，有：Med M mod n。现在：C=Me mod n M=Cd mod n (Me)d mod n Med mod n M mod n 1/2/202333公钥密码公钥密码公钥算法例子例子1.选素数p=17和q11，得n=187，(n)=1610160；2.选择e=7使其与(n)160互素且小于(n)，求得私钥d=e-1 23(mod 160)；3.公开n=187和e=7.公钥KU=7，187，私钥KR=23，187；4.现要发送明文88，计算：C=887(mod

18、 187)=115.收到密文11后，用私钥d23进行解密：M=1123(mod 187)=88 1/2/202334公钥密码公钥密码公钥算法的安全性的安全性n强力攻击n数学攻击（两个素数乘机的因子分解）（猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！）是否等价n定时攻击w利用测定RSA解密进行的时间来估计解密指数d，然后再精确出d的值,比较玄 1/2/202335公钥密码公钥密码公钥算法密码体制的参数选择密码体制的参数选择nn的确定（p,q必须是强素数）n建议选择p和q大约是100位的十进制素数。模n的长度要求至少是512比特。EDI攻击标准使用的RSA算法中规

19、定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC 9796中规定n的长度位512比特。(现1024和2048(本世纪中)1/2/202336公钥密码公钥密码公钥算法密码体制的参数选择密码体制的参数选择ne的选择（EDI国际标准中规定 e2161，ISO/IEC9796中甚至允许取e3,e为小整数时运算快，但存在问题。）nd的选择（d要大于n1/4）1/2/202337公钥密码公钥密码公钥算法注意的问题 共模攻击：整个系统使用相同的，互共模攻击：整个系统使用相同的，互素的素的e1和和e2。y1=xe1 y2=xe2则攻击者知道则攻击者知道e1,e2,n

20、,y1,y2根据中国剩余定理推论：根据中国剩余定理推论：存在存在s,t 使使t*e1+s*e2=1(注意是相等注意是相等)y1t*y2s=x mod n 1/2/202338公钥密码公钥密码公钥算法注意的问题 低加密指数攻击：使用相同较小的低加密指数攻击：使用相同较小的eY1=x3 mod n1Y2=x3 mod n2Y3=x3 mod n3n1,n2,n3一般互素，一般互素，由中国剩余定理可求：由中国剩余定理可求：Y=x3 mod(n1*n2*n3)x3n1*n2*n3，则则x为为Y开三次方。开三次方。1/2/202339公钥密码公钥密码公钥算法的实现 选用选用e=3,17,65537等，为

21、什么？等，为什么？*硬件实现速度一般是硬件实现速度一般是DES的的1/100。软件实现的速度一般是软件实现的速度一般是DES的的1/10。已经能够实现在智能卡中。1/2/202340公钥密码公钥密码密钥管理-公钥公布公开密钥的分配公开密钥的分配n公开发布公开发布 (图图10.1)n公开可访问目录公开可访问目录(图图10.2)n公钥授权公钥授权n公钥证书公钥证书n公钥的前提：公开自己的密钥公钥的前提：公开自己的密钥n难点：不能轻易接受其他人的公钥难点：不能轻易接受其他人的公钥n特点：关键不在于加密，而是认证特点：关键不在于加密，而是认证 1/2/202341公钥密码公钥密码密钥管理-公钥公布公钥

22、授权公钥授权公开密钥管理机构AliceBob 1/2/202342公钥密码公钥密码密钥管理-公钥公布问题：问题：只能从管理机构获得公钥。只能从管理机构获得公钥。容易产生容易产生DOS攻击的情况。攻击的情况。管理机构如何得到管理机构如何得到A的公钥？的公钥？A如何得到管理机构的公钥？如何得到管理机构的公钥？1/2/202343公钥密码公钥密码密钥管理-公钥公布公开密钥证书公开密钥证书公开密钥管理机构AliceBob 1/2/202344公钥密码公钥密码密钥管理-公钥公布这种方法更为现实一点。这种方法更为现实一点。问题：问题：A如何得到如何得到CA的公钥？的公钥？密钥丢失后，如何挂失？密钥丢失后，

23、如何挂失？1/2/202345公钥密码公钥密码密钥管理-加密密钥分配用公开密钥加密进行秘密密钥分配用公开密钥加密进行秘密密钥分配n简单的秘密密钥分配，如何共享对称加密密简单的秘密密钥分配，如何共享对称加密密钥钥KsAliceBob 1/2/202346公钥密码公钥密码密钥管理-加密密钥分配插入攻击插入攻击(这个例子说明没有建立信任基这个例子说明没有建立信任基础的情况下，难以保障安全础的情况下，难以保障安全)EveAliceBob 1/2/202347公钥密码公钥密码密钥管理-加密密钥分配具有保密和鉴别能力的秘密密钥分配具有保密和鉴别能力的秘密密钥分配AliceBob 1/2/202348公钥密

24、码公钥密码密钥管理-加密密钥分配Diffie-Hellman密钥交换密钥交换n基于求离散对数困难问题（基于求离散对数困难问题（DLog Problem），），本原根本原根，3是是7的本原根的本原根。n没有身份鉴别的功能。没有身份鉴别的功能。n不需要事先共享任何信息。不需要事先共享任何信息。1/2/202349公钥密码公钥密码密钥管理-加密密钥分配Diffie-Hellman密钥交换密钥交换产生：随机的XA q;计算：计算：产生：随机的XB q;计算：计算：YAYB用户A用户B 1/2/202350公钥密码公钥密码小结小结公钥密码体制的基本概念公钥密码体制的基本概念n公钥密码的描述，与常规密码的区别公钥密码的描述，与常规密码的区别公钥算法公钥算法*密钥管理和密钥交换密钥管理和密钥交换DiffieDiffie-hellmanhellman密钥交换密钥交换*1/2/202351公钥密码公钥密码 1/2/202352公钥密码公钥密码