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

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页