密码学sec-chap06.07.ppt

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

2、44-654,2020/9/15,公钥密码,4,公钥密码体制基本概念(Cont.),三个误解 1、更安全？ 2、对称加密过时了？ 3、密钥分配简单了？,2020/9/15,公钥密码,5,公钥密码体制基本概念(Cont.),两个动因 1、密钥管理 2、”数字签名”,2020/9/15,公钥密码,6,双钥体制（公钥体制）,系统中，加密密钥称公开密钥（public Key） 可以公开发布（电话号码注册）；而解密密 钥称私人密钥（private key,简称私钥）。 加密：图9.2 M=D(E(M,pub-key),private-key) 认证：图9.3 M=E(D(M,private-key),p

3、ub-key),2020/9/15,公钥密码,7,双钥体制（公钥体制）,同时实现加密和认证(A-B) 图9.4 C: A发给B的密文 c=E(E(m,private-key-A),pub-key-B) m：B恢复出的明文 m=D(D(c,private-key-B),pub-key-A) 和对称加密有何不同之处？,2020/9/15,公钥密码,8,对称加密和公钥加密,2020/9/15,公钥密码,9,公钥密码体制基本概念(Cont.),单向函数 是满足下列条件的函数f： (1)给定x，计算y=f(x)是容易的； (2)给定y, 计算x使y=f(x)是困难的。 (所谓计算x=f-1(Y)困难是指

4、计算上相当复杂，已无实际意义。),2020/9/15,公钥密码,10,公钥密码体制基本概念(Cont.),陷门单向函数 满足以上（1），（2）和 （3）存在，已知 时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。 称为陷门信息。,2020/9/15,公钥密码,11,公钥密码体制基本概念(Cont.),用于公钥体制的陷门单向函数 离散对数问题 大数分解 二次剩余问题 多项式求根,2020/9/15,公钥密码,12,公钥密码体制基本概念(Cont.),公钥体制的应用 加密解密 数字签名 密钥交换 某些算法适合所有的三种应用，而有些可能只适用于这些应用的一种或两种。,2020/9

5、/15,公钥密码,13,常用数学基础,素数 （质数） 模运算 费马定理（小）和欧拉定理 素数检测 欧几里德算法 中国剩余定理 离散对数,2020/9/15,公钥密码,14,整除,对整数 b!=0 及 a , 如果存在整数 m 使得 a=mb,称 b 整除 a, 也称b是a的因子 记作 b|a 例 1,2,3,4,6,8,12,24 整除 24,2020/9/15,公钥密码,15,素数与不可约多项式,素数: 只有因子 1 和自身 1 是一个平凡素数 例 2,3,5,7 是素数, 4,6,8,9,10 不是 素多项式或不可约多项式irreducible: 不可写成其他因式的乘积 x2+x = （x

6、）（ x+1） 是非不可约多项式; x3+x+1 是不可约多项式,2020/9/15,公钥密码,16,一些素数,200 以内的素数: 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 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199,2020/9/15,公钥密码,17,素数分解(PrimeFactorisation),把整数n写成素数的乘积 分解整数要比乘法困难 整数 n的素数分解是把它

7、写素数的乘积 eg. 91 = 7 13 ; 3600 = 24 32 52 公式8.1小节 任意整数的表示方法.*,2020/9/15,公钥密码,18,整数互素,整数 a, b 互素是指 它们没有除1之外的其它因子 GCD(a,b)=1 8 与15 互素 8的因子1,2,4,8 15的因子 1,3,5,15 1 是唯一的公因子,2020/9/15,公钥密码,19,模运算,同余( congruence) for a b mod n 如果a,b 除以n,余数相同 eg. 100 34 mod 11 b 叫做a模n的剩余 通常 0=b=n-1 eg. -12mod7 -5mod7 2mod7 9m

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

9、运算: 结合律: (a+b)+c = a+(b+c) mod n 交换 律 分配律 (a+b).c = (a.c)+(b.c) mod n 加法单位元乘法单位元 0+w = w mod n 1w = w mod n 乘法运算类同,2020/9/15,公钥密码,23,模运算一个有用的性质,(a mod n)+(b mod n) mod n=(a+b) mod n (a mod n)*(b mod n) mod n=(a*b) mod n 求模运算下的乘方?,2020/9/15,公钥密码,24,费马定理和欧拉定理,费马定理：8.2.1 欧拉定理： 8.2.3,2020/9/15,公钥密码,25,素

10、数检测算法,方程x2 1 (mod p)的解不是1或者-1则n不是素数。 概率检测算法。,2020/9/15,公钥密码,26,欧几里德算法,寻找两个整数的最大公因子。 辗转相除法。 可以参见高中课本。,2020/9/15,公钥密码,27,中国剩余定理,设m1,m2,mk是两两互素的正整数，即 （mi,mj）=1, i!=j, i,j=1,2,k 则同余方程组xb1 mod m1 xb2 mod m2 xbk mod mk 模m1,m2,mk有唯一解 即在模m1,m2,mk的意义下，存在唯一的x，满足 xbi mod m1,m2,mk i=1,2,k,2020/9/15,公钥密码,28,中国剩余

11、定理-一个有用的推论,如果：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,2020/9/15,公钥密码,29,离散对数,阶 am 1 mod n 指数 (以某个数为底) 本原根 离散对数（注意是在有限域中是困难问题。*）,2020/9/15,公钥密码,30,公钥算法,Diffie和Hellman开创性的论文为密码学带来新的方法和挑战。 RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的（见Communitions of the ACM. Vol.21

12、.No.2. Feb. 1978, PP.120-126)该算法的数学基础是初等数论中的Euler（欧拉)定理，并建立在大整数因子的困难性之上。RSA是最早的公钥体制的挑战响应者，也是最受广泛接受和实现的公钥体制。,2020/9/15,公钥密码,31,公钥算法,密码体制描述如下： 首先，明文空间P，密文空间C=Zn.(分组是小于或等于log2n的整数). 密钥的生成 选择p,q，p,q为互素数，计算n=p*q, (n)=(p-1)(q-1) 选择整数e 使( (n),e)=1,1e (n), 计算d,使de-1 mod (n), 公钥KU=e,n;私钥KR=d,n。,2020/9/15,公钥密

13、码,32,公钥算法,密码体制描述如下： 加密 (用e,n)明文：Mn 密文：C=Me(mod n). 解密 (用d,n) 密文：C 明文：M=Cd（mod n),2020/9/15,公钥密码,33,公钥算法,成立的理由 因选择d，e使得de-1 mod (n), 有： ed1 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,2020/9/15,公钥密码,34,公钥算法,例子 1. 选素数

14、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 187)=11 5. 收到密文11后，用私钥d23进行解密： M=1123 (mod 187)=88,2020/9/15,公钥密码,35,公钥算法,的安全性 强力攻击 数学攻击（两个素数乘机的因子分解） （猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！）是否等价 定时攻击

15、利用测定RSA解密进行的时间来估计解密指数d，然后再精确出d的值 ,比较玄,2020/9/15,公钥密码,36,公钥算法,密码体制的参数选择 n的确定（p,q必须是强素数） 建议选择p和q大约是100位的十进制素数。 模n的长度要求至少是512比特。EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC 9796中规定n的长度位512比特。(现1024和2048(本世纪中),2020/9/15,公钥密码,37,公钥算法,密码体制的参数选择 e的选择（EDI国际标准中规定 e2161，ISO/IEC9796中甚至允许取e3,

16、 e为小整数时运算快，但存在问题。） d的选择（d要大于n1/4）,2020/9/15,公钥密码,38,公钥算法注意的问题,共模攻击：整个系统使用相同的，互素的e1和e2。 y1=xe1 y2=xe2 则攻击者知道e1,e2,n,y1,y2 根据中国剩余定理推论： 存在s,t 使t*e1+s*e2=1 (注意是相等) y1t*y2s=x mod n,2020/9/15,公钥密码,39,公钥算法注意的问题,低加密指数攻击：使用相同较小的e Y1=x3 mod n1 Y2=x3 mod n2 Y3=x3 mod n3 n1,n2,n3一般互素， 由中国剩余定理可求： Y=x3 mod (n1*n2

17、*n3) x3n1*n2*n3，则x为Y开三次方。,2020/9/15,公钥密码,40,公钥算法的实现,选用e=3,17,65537等，为什么？* 硬件实现速度一般是DES的1/100。 软件实现的速度一般是DES的1/10。 已经能够实现在智能卡中。,2020/9/15,公钥密码,41,密钥管理-公钥公布,公开密钥的分配 公开发布 (图10.1) 公开可访问目录 (图10.2) 公钥授权 公钥证书 公钥的前提：公开自己的密钥 难点：不能轻易接受其他人的公钥 特点：关键不在于加密，而是认证,2020/9/15,公钥密码,42,密钥管理-公钥公布,公钥授权,2020/9/15,公钥密码,43,密

18、钥管理-公钥公布,问题： 只能从管理机构获得公钥。 容易产生DOS攻击的情况。 管理机构如何得到A的公钥？ A如何得到管理机构的公钥？,2020/9/15,公钥密码,44,密钥管理-公钥公布,公开密钥证书,2020/9/15,公钥密码,45,密钥管理-公钥公布,这种方法更为现实一点。 问题： A如何得到CA的公钥？ 密钥丢失后，如何挂失？,2020/9/15,公钥密码,46,密钥管理-加密密钥分配,用公开密钥加密进行秘密密钥分配 简单的秘密密钥分配，如何共享对称加密密钥Ks,2020/9/15,公钥密码,47,密钥管理-加密密钥分配,插入攻击(这个例子说明没有建立信任基础的情况下，难以保障安全),2020/9/15,公钥密码,48,密钥管理-加密密钥分配,具有保密和