何大可 彭代渊 唐小虎 何明星 梅其祥 现代密码学-第4章公钥密码体制-20091110

1,现代密码学,21世纪高等学校计算机规划教材,Modern Cryptography,彭代渊 信息科学与技术学院 dypengswjtu.edu.cn 2009.9-2010.1,作 者：何大可 彭代渊 唐小虎 何明星 梅其祥 出版社：人民邮电出版社,2,现代密码学 Modern Cryptography,彭代渊 信息科学与技术学院 dypengswjtu.edu.cn 2009年11月,第4章 公钥密码体制,3,4.1 公钥密码体制概述 4.2 RSA公钥密码体制 4.3 离散对数公钥密码体制,第4章 公钥密码体制,4,4.1 公钥密码体制概述,私钥密码体制的局限性 密钥量大：n个用户相互通信,需用个n(n-1)/2密钥. 应用范围小：不易实现数字签名 公钥密码体制思想的产生 1976年, 斯坦福大学的博士生W.Diffie和其导师M.E.Hellman提出了公钥密码的新思想 W. Diffie and M. E. Hellman, New direction in cryptography, IEEE Trans. on Information Theory, 1976, IT-22.(6), pp.644-654. 1978年, Merkle和Hellman联合提出了基于组合数学中“背包问题”的公钥密码体制(MH背包公钥密码体制). 不久被攻破.,5,4.1 公钥密码体制概述,公钥密码体制( PKC: public key cryptosystem)原理 密钥K=(PK, SK): 加密密钥PK公开; 解密密钥SK保密. 在计算上由PK推出SK是困难的. 加密算法EPk: c=EPk(m) 解密算法DSk满足: m=DPk(c) DSK(EPK(x)=x.,6,4.1 公钥密码体制概述,公钥密码体制的要求 用户：产生密钥对K=(PK, SK)在计算上是可行的 发送方：已知公钥与明文，产生密文是容易的 接收方：利用私钥解密密文在计算上是可行的 攻击者：利用公钥求解私钥在计算上是不可行的 攻击者：已知公钥与密文，在不知道私钥的情况下，恢复明文在计算上是不可行的,7,4.1 公钥密码体制概述 4.2 RSA公钥密码体制 4.3 离散对数公钥密码体制,第4章 公钥密码体制,8,4.2 RSA密码体制,1978年, R. Rivest, A. Shamir, L. Adleman提出RSA密码体制 R. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystem, Comm. ACM 21(2) (1978), pp.120-126. 基于大合数因式分解的困难性 安全, 易懂. 可用于加密与数字签名. ISO, ITU, SWIFT把RSA选为加密标准; Internet的E-Mail的保密系统GPG, 国际VISA和MASTER组织的电子商务协议(SET协议)都将RSA作为传送会话密钥和数字签名的标准.,9,4.2 RSA密码体制,10,4.2 RSA密码体制,RSA密码体制算法 密钥生成算法 (1) 选取两个大素数 p, q (2) 计算n= pq, (n)=(p-1)(q-1) (3) 随机选取e: 1e(n)，与(n)互素 (4) 根据欧几里德算法计算e的逆 d=e1: 1e(n)，ed 1 mod (n). (5) 公钥: PK=(n, e), 私钥: SK=(p, q , d).,11,4.2 RSA密码体制,RSA密码体制算法 加密算法: 消息m: 0mn， 密文 c=EPK(m)=me (mod n),解密算法: 密文c: 0cn， 明文 m=DSK(c)=cd (mod n),12,4.2 RSA密码体制,RSA密码体制算法 解密算法的正确性,13,4.2 RSA密码体制,例4.1 设p=11, q=13. 令 n=1113=143 , (n)=(p-1)(q-1)=(11-1)(13-1)=120, 取公钥: PK=(n, e)=(143, e=17)， 计算: d=e-1=17-1=113 (mod 120) (因为: 17113=1921=16120+1). 私钥: SK=(p, q , d) =(11, 13, 113). 对于明文: m=24, 密文: c=EPK(m)=2417=7 (mod 143). 对于密文: c=7, 解密: m=DSK(c)=7113=24 (mod 143 ).,14,4.2 RSA密码体制,RSA密码算法的实现 模幂算法: me (mod n)(高效算法：平方乘算法),15,4.2 RSA密码体制,RSA密码算法的实现 模幂算法: me (mod n)(高效算法：平方乘算法),例4.2 设p=17, q=11，有n=1711=187 , (n)=(p-1)(q-1)=1610=160, 取公钥:e=7，计算私钥:d =23. 明文: m=88, 计算密文: c=887 (mod 187).,16,4.2 RSA密码体制,例4.2 设p=17, q=11，有n=1711=187 , (n)=(p-1)(q-1)=1610=160, 取公钥:e=7，计算私钥:d =23. 明文: m=88, 计算密文: c=887 =11 (mod 187). 对于密文: c=11, 解密: m=1123=7 (mod 187 ).,17,4.2 RSA密码体制,Zn上的运算: 设x和y的二进制表示分别有k和l位(k l). x+y: O(k) x-y: O(k) xy: O(kl) x/y: O(l(k-l) gcd(x, y): O(k3) (Euclidean算法) Zn上的模n运算:设n的二进制表示有k, 0m1, m2n-1. m1+m2 (mod n): O(k) m1-m2 (mod n): O(k) m1m2 (mod n): O(k2) (m1) -1 (mod n): O(k3) (m1)c (mod n): O(k2 logc) (平方-乘算法).,RSA密码算法的实现,18,对RSA的攻击,攻击方法1 ：分解n 已知n= pq (n)=(p-1)(q-1) a=b-1 mod (n). 分解n的最新水平: 二进制表示有512位. n应为1024, 2048位.,攻击方法2：直接计算(n) 已知(n) e=d-1 mod (n). 计算(n)并不比分解n容易. 设 pq=n, (p-1)(q-1)=(n) p2-(n -(n)+1)p+n=0 求出p, q=n/p 求出n=pq. 例: 设n=84773093, (n)=84754668 p2-18426p+84773093=0 p=9539, q=n/p=8887 n=84773093=95398887.,19,对RSA的攻击,攻击方法3：共模攻击 如果两个用户A与B使用相同的模n，设A与B的解密密钥分别为dA与dB, 加密密钥分别为eA与eB.对明文m加密的两个密文:,攻击者可以恢复明文m！,20,对RSA的攻击,攻击方法4：选择密文攻击 (RSA密码不能抵抗！) 假设攻击者获得了公钥(n, e), 截获到密文c1. 设明文为m1，有,攻击者选取一个消息m，计算,攻击者想办法让解密者对c2进行解密，从而获得的明文m2.,攻击者就可以计算出明文m1 ！,21,对RSA的攻击,攻击方法5：解密指数法 如果私钥d已知, 则可能分解n. 即计算d并不比分解n容易. 如果私钥d 被泄漏, 不能只更换公钥 e, 必须更换模n.,攻击方法6：低解密指数攻击法 当解密指数dn0.5,22,RSA的安全参数,p和q要足够大: n=pq 为1024位, 或2048位. p和q应为强素数(strong prime). 如果素数p 满足以下条件, 则称为强素数. (1) p -1有大素数因子r; (2) p+1有大素数因子s; (3) r-1有大素数因子t. 例如: 理想的强素数为: r=2t+1; p=2r+1=4t+3; p=2s-1.,23,RSA的安全参数,| p-q|要大. 如果| p-q|较小, 则(p+q)/2n1/2, (p-q)/2)2= (p+q)/2)2-n. 可求出p和q. 例: 对于n=164009, 有n1/2 405. 令 (p+q)/2=405, (p-q)/2)2=4052-n=16 p+q=810, p-q=8 p=409, q=401 164009=409401.,24,RSA的安全参数,p -1和q -1的最大公因子要小 设攻击者截获到密文 y1=xe mod n 迭代加密: yi=yi-1e=xeee mod n (i=2,3,4,) 如果有i使得: di =1 mod (n), 则有: yi=x mod n 因此, 如果i很小, 则容易求得明文x. 由Euler定理和di =1 mod (n), 可得 i=(n)=(p-1)(q-1)=D(p-1)(q-1)/(D), 其中D=gcd(p-1, q-1). 当D小时, (D)就小, 从而i大.,25,RSA的安全参数,p -1和q -1的最大公因子要小 设p和q是理想的强素数, 即 p=2a+1, q=2b+1 (a, b为奇素数) D=2, (D)=1, i=2(a-1)(b-1). 例: 设p=17, q=11, n=187, d=7, D=gcd(p-1, q-1)=gcd(16, 10)=2. 对x=123,有 y1=1237=183 mod 187 y2=y17=1837=72 mod 187 y3=y27=727=30 mod 187 y4=y37=307=123 (=x) mod 187.,26,RSA的安全参数,加密指数d 的选择 为使加密速度快, 应使e的二进制表示中, 1的个数尽量小, 但不能太小. 可取: e=3, 216+1=65537 (在二进制表示中只有2个1). 解密指数d的选择 在d的二进制表示中, 1的个数尽量小,但不能太小. 3dn1/4.,27,4.1 公钥密码体制概述 4.2 RSA公钥密码体制 4.3 离散对数公钥密码体制 4.3.1 ElGamal密码系统 4.3.2 椭圆曲线密码系统,第4章 公钥密码体制,28,4.3.1 ElGamal密码系统,循环群 设(G,*)是一个有限群, |G|= n,e是G的单位元. 如果存在 aG，使得a, a2,an=e互不相同,即 G=a, a2,an, 则称a是G的一个本原元（生成元）. (G,*)称为循环群。 有限域 设p是一个素数, Fp=GF(p)= 0,1,2, p-1. 在GF(p)中, 加法与乘法按 mod (p) 进行, 则GF(p)称为一个有限域。 GF(p)的本原元 设Fp*=GF(p)*= 1,2, p-1, aGF(p)*, 如果a, a2, ap-1 =1互不相同,即 GF(p)*=a, a2,ap-1, 则称a是GF(p)的一个本原元. (Fp*, *)是一个循环群。,29,4.3.1 ElGamal密码系统,例： 对于GF(5)=0,1,2,3,4, 有GF(5)*=1,2,3,4， 2, 22=4, 23=3, 24=1 GF(5)*=1,2,3,4=24,2, 23, 22, 4是GF(5)的本原元. 但是：4, 42=1 4不是GF(