公钥密码学与RSA(PPT-38)

1、Chapter 9 公钥密码学与公钥密码学与RSA 2022-2-4西安电子科技大学计算机学院2n传统密码体制只使用一个密钥传统密码体制只使用一个密钥n收发双方共享这个单一的密钥收发双方共享这个单一的密钥n密钥是对称的，双方是对等的；密钥是对称的，双方是对等的；n因此，不能确保接收方伪造信息，并声因此，不能确保接收方伪造信息，并声称是该信息是发送方发送的称是该信息是发送方发送的2022-2-4西安电子科技大学计算机学院32022-2-4西安电子科技大学计算机学院4公钥密码体制公钥密码体制n密码学发展历史中最伟大的一次革命密码学发展历史中最伟大的一次革命n采用两个密钥：一个公钥，一个私钥采用两个

2、密钥：一个公钥，一个私钥n参与方不对等，所以是非对称的；参与方不对等，所以是非对称的；n基于数论中的结论基于数论中的结论n是私钥密码的补充而不是代替是私钥密码的补充而不是代替2022-2-4西安电子科技大学计算机学院5为什么需要公钥密码为什么需要公钥密码?n两个考虑：两个考虑：q密钥分配密钥分配 - KDCq数字签名数字签名n公认该发明属于公认该发明属于Stanford Uni 的的Whitfield Diffie 和和 Martin Hellman ，于，于1976年。年。nNew Directions in Cryptography, IEEE Trans. Information The

3、ory, IT-22, pp644-654, Nov 1976 nJames Ellis (UK CESG) 在在1970年曾提出此概念年曾提出此概念2022-2-4西安电子科技大学计算机学院6公钥密码体制公钥密码体制n公钥公钥/双钥双钥/非对称非对称 密码都是指使用两个密钥密码都是指使用两个密钥: q公钥：公钥：可以对任何人公开的密钥，用于加密消息可以对任何人公开的密钥，用于加密消息或验证签名。或验证签名。 q私钥：私钥：只能由接收者私存，用于解密消息或签名。只能由接收者私存，用于解密消息或签名。n非对称非对称q用于加密消息或验证签名的人不能进行消息的用于加密消息或验证签名的人不能进行消息的

4、解密解密或或消息的签名。消息的签名。2022-2-4西安电子科技大学计算机学院7公钥密码体制公钥密码体制2022-2-4西安电子科技大学计算机学院82022-2-4西安电子科技大学计算机学院9公钥密码体制特点公钥密码体制特点n公钥密码算法依赖于公钥密码算法依赖于:q仅仅知道算法和加密密钥，推导解密密钥计算仅仅知道算法和加密密钥，推导解密密钥计算上是不可行的上是不可行的q已知加解密密钥时，进行加解密运算计算上是已知加解密密钥时，进行加解密运算计算上是容易的容易的q两个密钥中的任何一个都可以用来加密，而另两个密钥中的任何一个都可以用来加密，而另一个用来解密。一个用来解密。2022-2-4西安电子科

5、技大学计算机学院10公钥密码体制特点公钥密码体制特点公钥密码算法应该满足的条件公钥密码算法应该满足的条件:q产生一对密钥（公、私钥对）在计算上是容易的；产生一对密钥（公、私钥对）在计算上是容易的；q已知公钥和要加密的消息，发送方产生相应的密文已知公钥和要加密的消息，发送方产生相应的密文在计算上容易的；在计算上容易的；q接收方使用其私钥对接收的密文解密以恢复明文在接收方使用其私钥对接收的密文解密以恢复明文在计算上是容易的；计算上是容易的；q已知公钥时，攻击者要确定私钥在计算上不可行的；已知公钥时，攻击者要确定私钥在计算上不可行的；q已知公钥和密文，攻击者要恢复明文在计算上不可已知公钥和密文，攻击

6、者要恢复明文在计算上不可行的；行的；q加密和解密函数的顺序可以交换（有用但非必要）。加密和解密函数的顺序可以交换（有用但非必要）。2022-2-4西安电子科技大学计算机学院11单向陷门函数单向陷门函数n单向陷门函数：单向陷门函数：q若若k和和X已知，则容易计算已知，则容易计算 Y = fk(X).q若若k和和Y已知，则容易计算已知，则容易计算X = fk-1(Y).q若若Y已知但已知但k未知，则计算出未知，则计算出X = fk-1(Y)是不可行的是不可行的.n寻找合适的单向陷门函数是公钥密码体制应用的关键寻找合适的单向陷门函数是公钥密码体制应用的关键n单向陷门函数举例：单向陷门函数举例：q离散

7、对数离散对数q大整数分解大整数分解q背包问题背包问题2022-2-4西安电子科技大学计算机学院12公钥密码体制：保密性和认证公钥密码体制：保密性和认证2022-2-4西安电子科技大学计算机学院13公钥算法分类公钥算法分类nPublic-Key Distribution Schemes (PKDS) q用于交换秘密信息(依赖于双方主体) q常用于对称加密算法的密钥nPublic Key Encryption (PKE) q用于加密任何消息 q任何人可以用公钥加密消息 q私钥的拥有者可以解密消息 q任何公钥加密方案能够用于密钥分配方案PKDS q许多公钥加密方案也是数字签名方案nSignature

8、 Schemes q用于生成对某消息的数字签名q私钥的拥有者生成数字签名q任何人可以用公钥验证签名 2022-2-4西安电子科技大学计算机学院14公钥密码体制的应用公钥密码体制的应用n分为三类分为三类:q加密加密/解密解密 (提供保密性提供保密性)q数字签名数字签名 (提供认证提供认证)q密钥交换密钥交换 (会话密钥会话密钥)n一些算法可用于上述三类，而有些只适用一些算法可用于上述三类，而有些只适用用于其中一类或两类。用于其中一类或两类。2022-2-4西安电子科技大学计算机学院152022-2-4西安电子科技大学计算机学院16公钥密码体制安全性分析公钥密码体制安全性分析n一样存在穷举攻击一样

9、存在穷举攻击n但所使用的密钥一般都非常大但所使用的密钥一般都非常大 ( 512bits ) n安全性基于安全性基于容易容易（加解密）和（加解密）和困难困难（破译）之间（破译）之间巨大的差别巨大的差别n许多算法没有得到证明是安全的。（包括许多算法没有得到证明是安全的。（包括RSA） n需要采用一些特别大的数字需要采用一些特别大的数字n与私钥密码体制相比，速度慢。与私钥密码体制相比，速度慢。2022-2-4西安电子科技大学计算机学院17RSAn1977由由MIT的的Rivest, Shamir 和和 Adleman发明发明n已知的且被广泛使用的公钥密码方案已知的且被广泛使用的公钥密码方案n有限域中

10、的乘方运算有限域中的乘方运算q乘方运算需要乘方运算需要 O(log n)3) 操作操作 (容易的容易的) n使用一些大的整数使用一些大的整数 (例如例如. 1024 bits)n安全性基于大数的素因子分解的困难性安全性基于大数的素因子分解的困难性q素因子分解需要素因子分解需要 O(e log n log log n) 操作操作 (困难的困难的) 2022-2-4西安电子科技大学计算机学院182022-2-4西安电子科技大学计算机学院192022-2-4西安电子科技大学计算机学院20RSA 密钥的建立密钥的建立n每一个用户通过以下方法产生一个公钥每一个用户通过以下方法产生一个公钥/私钥对私钥对:

11、 q随机地选择两个大的素数随机地选择两个大的素数 p, q q计算方案中的模数计算方案中的模数 n = p.qn (n) = (p-1) (q-1) q随机地选择一个加密密钥随机地选择一个加密密钥en满足满足 1 e (n), (e, (n) = 1 q求解下面的方程，以得到解密密钥求解下面的方程，以得到解密密钥d ne.d 1 mod (n) and 0 d n q公开公钥公开公钥: PU = e, n q保密私钥保密私钥: PR = d, n 2022-2-4西安电子科技大学计算机学院21RSA 的使用的使用n为了加密消息为了加密消息M，发送方，发送方:q获得接收方的公钥获得接收方的公钥

12、PU = e, n q计算计算: C = Me mod n, 其中其中 0 M nn为了解密密文为了解密密文C，接收者，接收者:q使用自己的私钥使用自己的私钥 PR = d, n q计算计算: M = Cd mod n n消息消息M一定要比模数一定要比模数 n小小 (如果需要的话，如果需要的话，可以进行分组可以进行分组)2022-2-4西安电子科技大学计算机学院22RSA的工作原理的工作原理nEuler定理定理:qa(n) mod n 1 其中其中(a, n) = 1nRSA中中:qn = p.qq(n) = (p-1) (q-1) q仔细地选择仔细地选择 e 和和 d 使得使得 mod (n

13、) 下，两者互逆下，两者互逆q因此存在某个整数因此存在某个整数k，使得，使得e.d = 1 + k.(n) 成立成立n所以所以 :Cd = Me.d = M1+k.(n) = M1.(M(n)k M1.(1)k = M1 = M mod n 2022-2-4西安电子科技大学计算机学院23RSA 举例举例 密钥的建立密钥的建立1.选择素数选择素数: p = 17 & q = 112.计算计算 n = p q =17 x 11 = 1873.计算计算 (n) = (p1) (q-1) = 16 x 10 = 1604.选择选择 e: gcd(e, 160) = 1; 选择选择 e = 75

14、.确定确定 d: d e = 1 mod 160 且且 d 160 d = 23 因为因为 23 x 7=161= 10 x160+16.公钥公钥 PU = 7, 187 7.私钥私钥 PR = 23, 187 2022-2-4西安电子科技大学计算机学院24RSA 举例举例 加密加密/加密加密n明文消息明文消息 M = 88 ( 注意注意88 187)n加密加密:C = 887 mod 187 11 n解密解密:M = 1123 mod 187 88 2022-2-4西安电子科技大学计算机学院25幂幂 运运 算算n可以用平方和乘法运算可以用平方和乘法运算nN 次方，只需要次方，只需要 O(lo

15、g2 n) 次乘法运算次乘法运算q如如. 75 = 74.71 = 3.7 = 10 mod 11q如如. 3129 = 3128.31 = 5.3 = 4 mod 112022-2-4西安电子科技大学计算机学院26幂幂 运运 算算c = 0; f = 1for i = k downto 0 do c = 2 x c f = (f x f) mod n if bi = 1 then c = c + 1 f = (f x a) mod n return f 2022-2-4西安电子科技大学计算机学院272022-2-4西安电子科技大学计算机学院28加密的效率加密的效率n加密要计算加密要计算 e

16、次方幂次方幂n若若 e 较小较小, 计算将很快计算将很快q通常选择通常选择 e = 65537 (216-1)q或选择或选择 e = 3 或或 e = 17n但若但若 e太小太小 (如如 e = 3)将易受到攻击将易受到攻击q用中国剩余定理用中国剩余定理n必须确保必须确保(e, (n) = 12022-2-4西安电子科技大学计算机学院29解密的效率解密的效率n解密计算解密计算d次方幂次方幂q看起来很大，否则不安全看起来很大，否则不安全n用中国剩余定理分别计算用中国剩余定理分别计算mod p和和mod q，则可以得到所希望的答案则可以得到所希望的答案q比直接快约比直接快约4倍倍n只有知道只有知道

17、p和和q及私钥的接收者可以直接采及私钥的接收者可以直接采用这个技术进行计算用这个技术进行计算2022-2-4西安电子科技大学计算机学院30RSA 密钥的产生密钥的产生nRSA的用户必须的用户必须:q随机确定两个素数随机确定两个素数 p, q q选择选择e或或d，并求出另一个，并求出另一个n素数素数 p, q 一定不能从一定不能从n = p . q轻易得到轻易得到q意味着数要足够大意味着数要足够大q典型地用猜测或可能性测试典型地用猜测或可能性测试n指数指数e, d 是互逆的是互逆的2022-2-4西安电子科技大学计算机学院31RSA 安全性分析安全性分析n攻击攻击RSA可能的方法有可能的方法有:

18、q穷举搜索穷举搜索 (对于给定的数字规模是不可行的对于给定的数字规模是不可行的)q数学攻击数学攻击 (基于计算基于计算(n)的困难性的困难性, 模模n的因子分解的因子分解的困难性的困难性)q计时攻击计时攻击 (基于解密的运行情况基于解密的运行情况)q选择密文攻击选择密文攻击(RSA的已知特性的已知特性)2022-2-4西安电子科技大学计算机学院32RSA系统安全性与系统的参数系统安全性与系统的参数nRSA系统安全性与系统的参数有很大关系，系统安全性与系统的参数有很大关系，X.931标准标准, ISO/IEC 14752对此提出以下几点：对此提出以下几点：q如果公钥如果公钥e是奇数，是奇数，e应

19、与应与p-1，q-1互质；互质；q如果公钥如果公钥e是偶数，是偶数，e必须与必须与(p-1)/2, (q-1)/2互质，且互质，且 pq mod 8不成立；不成立；q模数的长应该为模数的长应该为1024 + 256x，x = 0, 1 ；q质数质数p，q 应通过质数检测，使出错的概率小于应通过质数检测，使出错的概率小于 ；qp-1, q-1, p+1, q+1应有大质数因子；应有大质数因子；qgcd(p-1, q-1)应该小；应该小；qp/q不应靠近两个小整数比值，且；不应靠近两个小整数比值，且；q|p-q|应有大质数因子。应有大质数因子。 2022-2-4西安电子科技大学计算机学院33分解因

20、子问题分解因子问题n数学攻击的三种形式数学攻击的三种形式:q分解分解 n = p.q, 计算计算(n) 从而得到从而得到 dq直接确定直接确定 (n) 并计算并计算 dq直接寻找直接寻找d n对于因子分解问题对于因子分解问题q很多年来进展很慢很多年来进展很慢n用用“Lattice Sieve” (LS),算法，算法，最好的是分解了最好的是分解了200位十进位十进制数制数(663 bit) q最大的改进就是对改进算法的改良最大的改进就是对改进算法的改良n QS to GHFS to LSq当前假设当前假设1024-2048bit RSA 是安全的是安全的n确保确保 p, q 有相似的大小并满足其它约束有相似的大小并满足其它约束2022-2-4西安电子科技大学计算机学院342022-2-4西安电子科技大学计算机学院35计计 时时 攻攻 击击n20世纪世纪90年代由年代由Paul Kocher提出提出n探测操作中的时间变化探测操作中的时间变化qeg. mul