计算机系统信息安全:公开密钥密码学

本章讲述公开密钥密码学即非对称密码学的基本内容。首先讲述了其定义和基本概念,其次详细讲述了非对称密码学中背包密码算法、RSA密码算法、EIGamal密码算法和椭圆曲线密码算法及其相关的信息安全数学基础知识如欧拉定理、离散对数的基本概念等。
展开查看详情

1.第2章 公开密钥密码学 南京大学计算机系黄皓教授 2011年10月10日

2. 参考文献 1. Wenbo Mao(毛文波),现代密码学理论与实践,电子 工业出版社,2004年7月。 2. 周玉洁,冯登国,公开密钥密码算法及其快速实现, 国防工业出版社,2002年9月。 3. D. Hankerson, A. Menezes, S. Vanstone, 椭圆曲线 密码学导论,电子工业出版社,2005年8月第1版。 4. Bruce Chneier, 应用密码学,机械工业出版社, 2000年1月。 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第2页/共74页

3. 内容 1. 公开密钥密码体制的基本概念 2. RSA密码算法 3. 离散对数的基本概念 4. ElGamal密码算法 5. 椭圆曲线密码算法 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第3页/共74页

4.1. 公开密钥密码体制的基本概念 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第4页/共74页

5. 公开密码体制的提出  1976年W. Diffie, M. Hellman, Multiuser cryptographic techniques. In Proceedings of AFIPS 1976 NCC, pages 109-112. 提出了解密密钥和加密密钥不同、加密密钥可 以公开的密码体制的可能性和思路。  R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of ACM, 21(2):120126, 1978. 提出了利用整数分解问题的困难性 设计的一个公开密码算法,称为RSA算法。 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第5页/共74页

6. 公开密钥算法的特点  加密功能  <KU,KR>是一对密钥;<pUblic, pRivate>  E(KU, M) = Y  E(KR, Y)=M,  E(KU, Y)≠M 加密者不必保密KU,接受者可以将自己的公钥公布在目录服务器上。  签名功能  E(KR, M) = Y,  E(KU, Y)=M,  没有KR寻找Y,使得E(KU, Y)=M是计算不可能的。 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第6页/共74页

7. 单向陷门函数  对于每一个给定的k,f: x→f(k, x)是一一对应函数。  给定x和k,计算y=f(k,x)是容易的; 反之,给定y和k ,计算x是困难的问题。  存在陷门信息d(k)=k’及函数g(k’,y),当y=f(k,x)时,x=g(d(k), y)。  陷门信息d(k)使得计算f(k,x)的逆变得容易起来。  加密密钥k就不用保密了,甚至像电话本那样公布:  给某人发一封密件,只要“密钥本”里面找到他的“加密密钥”,用它来 加密文件就不用担心其他人窃取机密了。 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第7页/共74页

8. 2. 背包密码算法 M.E.Hellman, An Mathematics of Public-key Cryptography, Scientific American, v241, n8, Aug. 1979, pp146-157. 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第8页/共74页

9. 背包密码算法  给定{M1, M2, …… ,Mn}和S,  求bi, i=1,2, …, n, 满足: S=b1*M1 + b2*M2+ ……+bn*Mn bi=0或1, i=1,2, …, n  例:{1, 5, 6, 11, 14, 20}  明文:1 1 1 0 0 1  背包:1 5 6 11 14 20  密文:1+5+6+20=32 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第9页/共74页

10. 超递增背包  { 1,3,6,13,27,52}  每一个数都比前面的数的总和大。超递增背包问题是容易问题  超递增背包问题是一个容易解的问题。 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第10页/共74页

11. 背包密码算法  {m1,m2, …, mk}: 超递增 ={ 1,3,6,13,27,52}  N 与m1, ,m2, …, mk互素。  M > m1+m2+…+mk  N与M互素  m1*N mod M =M1  m2*N mod M =M2 ………………………..  mk*N mod M =Mk  {M1,M2, …, Mk}:是一般背包问题(难解的)。 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第11页/共74页

12. 背包密码算法  明文:b1 b2 … bk  密文:b1*M1+…+bk*Mk  解密  求N’使的 N*N’ =1 mod M (有解,因为N与M互素。)  (b1*M1+…+bk*Mk mod M)*N’ = b1*m1*N*N’+…+bk*mk*N*N’ mod M = b1*m1+……+bk*mk mod M 是易解的背包问题。  关键的陷门信息:N。  密码学家 Shamir 和 Zippel发现了变换中的缺陷,可以从普通的背 包问题中重构出超递增背包问题。[ W. Patarin, Mathematical Cryptography for Computer Scientists and Mathematicians, Totowa, N.J., Rowman & Littlefield, 1987.] 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第12页/共74页

13.3. RSA公开密钥算法

14. 素数  素数:只能被1和它本身整除的自然数;否则为合数。  每个合数都可以唯一地分解出素数因子  6 = 2 ·3  999999 = 3·3·3·7·11·13·37  27641 = 131·121 从2 开始试验每一个小于等于 27641 的素数。 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第14页/共74页

15. 素因子分解的速度  整数n的十进制位数因子分解的运算次数所需计 算时间(每微秒一次) 50 1.4x1010 3.9小时 75 9.0x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年 500 1.3x1039 4.2x1025年 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第15页/共74页

16. 费马小定理  如果p是素数,a 与p互素,则 ap-1 = 1 mod p 如果1 ≤i<j ≤p-1, i • a mod p = j • a mod p 则 存在1 ≤k≤p-1,满足 k • a = 0 mod p  a | p, 得出矛盾。 { a mod p, 2a mod p, …, (p-1)a mod p} 是{1,2, …, p-1}的一个排列。 (a mod p) (2a mod p) …[ (p-1)a mod p] =(p-1)! mod p ap-1 (p-1)!=(p-1)! mod p ap-1 = 1 mod p 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第16页/共74页

17. 欧拉函数  φ(n):小于n,但与n互素的正整数的个数。  p是素数,则φ(p)=p-1。  p, q是素数,则φ(pq)=(p-1)(q-1)。 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第17页/共74页

18. 欧拉定理 欧拉定理: 如果a与n是互素的,则a (n) ≡1 (mod n)  如果a与n是互素,则 a•b=a •c (mod n) 推出:b=c ( mod n)  设S={x1, x2, ……, x (n) }是所有小于n且与n是互素的整数的集合。  因为a• xi=a •xj (mod n ), 则有 xi=xj (mod n ),  {a•x1 (mod n ), a•x2 (mod n ), ……, a•x (n) (mod n )}=S  (n)  (n)  a  x (m od n )   x (m od n ) i 1 i i 1 i  (n)  (n) a  (n)   xi (mod n )   xi (mod n ) i 1 i 1 a (n) ≡1 (mod n) 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第18页/共74页

19. RSA 公开密钥密码算法  M是明文,n是一个大数  加密:C = Me mod n  解密:M = Cd mod n =Med mod n  条件:  能找到e,d,n使得对所有的M,当M<n时, M ed=M mod n  对所有的M,计算Me 和Cd 的容易的。  给定e、n,推导 d 是困难的。 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第19页/共74页

20. RSA 公开密钥密码算法(续)  p、q是素数 秘密地选择  n = p q, 公开n  选择e: e与(n)是互素的; 公开选择  计算d, 使得e• d=1 mod (n); 秘密地计算 即:e • d=1 +s•(n); 根据欧拉定理的推广 对于任意的m, 0 < m < n, m ed = m s (n)+1 ≡m (mod n) 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第20页/共74页

21. 欧拉定理的推广  如果p, q是素数,n=pq, 则 对于任意的m, 0< m < n, m (n) ≡1 (mod n) 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第21页/共74页

22. 欧拉定理的推广 若n=pq是两个素数因子的乘积,X限制在加密与解密所要求的集合 {0,1,…,n-1}之中,则对于任何明文X 有X m(n)+1 ≡X (mod n) 证明:  X=0的情况显然是成立的。  下面要证明X>0的情况也是成立的:  若X不是与n=pq互素的,则X必须包括p或者q作为一个因子。设p为X的因子, 对于某些正整数c,有关系式X=cp。  由于X限于集合{0,1,…,n-1}之中,且n=pq,从而可知X必定是与q互素的,否 则X将包含q作为一个因子,在这种情况下X将越出n-1。  由欧拉定理有X (q) ≡1 (mod q),其中(q)=q-1,  但 X m(p-1)(q) ≡ 1 m(p-1) ≡1 (mod q),对于任何整数m都成立,并且(p-1) (q)=(p-1)(q-1)= (n),因此有 X m(n) ≡ 1 (mod q),或对于某些整数t,有 1= X m(n) +tq  用X=cp分别乘以等式的两端,得  X= X m(q)+1 +(tq)(cp)  = X m(q)+1 +tcn  因此 X m(q)+1 ≡X (mod n)  对于q为X的一个因子的情况,同理可证。 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第22页/共74页

23. 例 例:  n=15, p=3, q=5, (n)=8  生成密钥对:令e=3, 则d=3, ( d e = 1 mod (n) )  加密: 设M=7, C=7e mod n =73 mod 15= 13  解密: M= Cd mod n = 133 mod 15 = 7 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第23页/共74页

24. 问题  如何计算 me mod n  如何判定一个给定的整数是素数?  如何找到足够大的素数p和q ? 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第24页/共74页

25. 如何计算 me mod n  e= 2 bi 0 i d:=1; 2 i for i=k downto 0  m =m e bi 0 mod n d:=d*d mod n =  m 2 mod n i if bi = 1 then bi 0 d:=d*a mod n  (m 2 mod n) i = return d bi  0 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第25页/共74页

26. 大素数生成— 素数的分布  存在无穷多个素数  假设已知有k个素数p1, p2, …, pk;  考虑 n = p1·p2· …·pk+1  要么存在 p | n,这时p≠p1, …, p≠pk  要么n也是素数 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第26页/共74页

27. 大素数生成— 素数的分布  设x>0,记π(x)为不大于x的素数的个数,则:  ( x) ln x lim 1 x  x x  ( x)  ln x 长度为t 位的数共有2t  2t 1 个,所以一个长度为t位的随机数为素数的概率为  2t 2t 1  t t 1 t 2   t 1  /(2  2 )   ln 2 t ln 2  (t  1)t ln 2 例如:一个长度为256位的随机数为素数的概率为 254  0.011 255  256  ln 2 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第27页/共74页

28. 基于费马小定理的素性检测 I. 随机选取一个奇数n II. 随机选取一个整数a, a<n III. a n-1≠ 1 mod n, 则n不是素数,转I IV. 如果多次通过检测就接受n是素数,否则转II。 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第28页/共74页

29. 其它素性检测算法  Solovay-Strassen算法  Miller-Rabin算法  Mesenne算法  基于椭圆曲线的素性检测  裴定一,祝跃飞,算法数论,科学出版社,2002年9月第一版。  周玉洁,冯登国,公开密钥密码算法及其快速实现,国防工业出版 社,2002年9月 2011/12/5 南京大学计算机系《计算机信息安全》讲义 第29页/共74页