《密码编码学与网络安全第五版向金海06公钥密码学与rsa》由会员分享，可在线阅读，更多相关《密码编码学与网络安全第五版向金海06公钥密码学与rsa（38页珍藏版）》请在金锄头文库上搜索。
1、Chapter9Chapter9 公钥密码学与公钥密码学与RSARSA密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院29.1 公公钥密密码体制的基本原理体制的基本原理n传统密密码体制只使用一个密体制只使用一个密钥n收收发双方共享双方共享这个个单一的密一的密钥n密密钥是是对称的，双方是称的，双方是对等的；等的；n因此，不能确保接收方因此，不能确保接收方伪造信息，并声造信息，并声称是称是该信息是信息是发送方送方发送的送的密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院3 对称密称密码体制的缺陷体制
2、的缺陷 密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院4公公钥密密码体制体制n密密码学学发展展历史中最史中最伟大的一次革命大的一次革命n采用两个密采用两个密钥：一个公：一个公钥，一个私，一个私钥n参与方不参与方不对等，所以是非等，所以是非对称的；称的；n基于数基于数论中的中的结论n是私是私钥密密码的的补充而不是代替充而不是代替密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院5为什么需要公什么需要公钥密密码?n两个考两个考虑：q密密钥分配分配 - KDCq数字数字签名名n公公认该发明明属属于于S
3、tanford Uni 的的Whitfield Diffie 和和 Martin Hellman ，于，于1976年。年。nNew Directions in Cryptography, IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976 nJames Ellis (UK CESG) 在在1970年曾提出此概念年曾提出此概念密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院6公公钥密密码体制体制n公公钥/双双钥/非非对称称密密码都是指使用两个密都是指使用两个密钥:q公公钥：可以可以
4、对任何人公开的密任何人公开的密钥，用于加密消息，用于加密消息或或验证签名。名。q私私钥：只能由接收者私存，用于解密消息或只能由接收者私存，用于解密消息或签名。名。n非非对称称q用于加密消息或用于加密消息或验证签名的人不能名的人不能进行消息的解密或行消息的解密或消息的消息的签名。名。密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院7公公钥密密码体制体制密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院8密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院
5、9公公钥密密码体制特点体制特点n公公钥密密码算法依算法依赖于于:q仅仅知道算法和加密密知道算法和加密密钥，推，推导解密密解密密钥计算算上是不可行的上是不可行的q已知加解密密已知加解密密钥时，进行加解密运算行加解密运算计算上是算上是容易的容易的q两个密两个密钥中的任何一个都可以用来加密，而另中的任何一个都可以用来加密，而另一个用来解密。一个用来解密。密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院10公公钥密密码体制特点体制特点公公钥密密码算法算法应该满足的条件足的条件:q产生一生一对密密钥（公、私（公、私钥对）在）在计算上是容易的；算上是容易的
6、；q已知公已知公钥和要加密的消息，和要加密的消息，发送方送方产生相生相应的密文的密文在在计算上容易的；算上容易的；q接收方使用其私接收方使用其私钥对接收的密文解密以恢复明文在接收的密文解密以恢复明文在计算上是容易的；算上是容易的；q已知公已知公钥时，攻，攻击者要确定私者要确定私钥在在计算上不可行的；算上不可行的；q已知公已知公钥和密文，攻和密文，攻击者要恢复明文在者要恢复明文在计算上不可算上不可行的；行的；q加密和解密函数的加密和解密函数的顺序可以交序可以交换（有用但非必要）。（有用但非必要）。密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院1
7、1单向陷向陷门函数函数n单向陷向陷门函数：函数：q若若k和和X已知，已知，则容易容易计算算 Y = fk(X).q若若k和和Y已知，已知，则容易容易计算算X = fk-1(Y).q若若Y已知但已知但k未知，未知，则计算出算出X = fk-1(Y)是不可行的是不可行的.n寻找合适的找合适的单向陷向陷门函数是公函数是公钥密密码体制体制应用的关用的关键n单向陷向陷门函数函数举例：例：q离散离散对数数q大整数分解大整数分解q背包背包问题密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院12公公钥密密码体制：保密性和体制：保密性和认证密码编码学与网络安全（
8、第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院13公公钥算法分算法分类nPublic-Key Distribution Schemes (PKDS) q用于交换秘密信息(依赖于双方主体) q常用于对称加密算法的密钥nPublic Key Encryption (PKE) q用于加密任何消息 q任何人可以用公钥加密消息 q私钥的拥有者可以解密消息 q任何公钥加密方案能够用于密钥分配方案PKDS q许多公钥加密方案也是数字签名方案nSignature Schemes q用于生成对某消息的数字签名q私钥的拥有者生成数字签名q任何人可以用公钥验证签名 密码编码学与网络安全
9、（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院14公公钥密密码体制的体制的应用用n分分为三三类:q加密加密/解密解密(提供保密性提供保密性)q数字数字签名名(提供提供认证)q密密钥交交换(会会话密密钥)n一些算法可用于上述三一些算法可用于上述三类，而有些只适用用，而有些只适用用于其中一于其中一类或两或两类。密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院15密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院16公公钥密密码体制安全性分析体制安全性分析n一一样存在存在
10、穷举攻攻击n但所使用的密但所使用的密钥一般都非常大一般都非常大 ( 512bits ) n安全性基于安全性基于容易容易（加解密）和（加解密）和困困难（破（破译）之）之间巨大的差巨大的差别n许多算法没有得到多算法没有得到证明是安全的。（包括明是安全的。（包括RSA） n需要采用一些特需要采用一些特别大的数字大的数字n与私与私钥密密码体制相比，速度慢。体制相比，速度慢。密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院17RSARSAn1977由由MIT的的Rivest, Shamir 和和 Adleman发明明n已知的且被广泛使用的公已知的且被广泛
11、使用的公钥密密码方案方案n有限域中的乘方运算有限域中的乘方运算q乘方运算需要乘方运算需要 O(log n)3) 操作操作 (容易的容易的) n使用一些大的整数使用一些大的整数 (例如例如. 1024 bits)n安全性基于大数的素因子分解的困安全性基于大数的素因子分解的困难性性q素因子分解需要素因子分解需要 O(e log n log log n) 操作操作 (困困难的的) 密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院18密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院19密码编码学与网络安
12、全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院20RSARSA密密钥的建立的建立n每一个用每一个用户通通过以下方法以下方法产生一个公生一个公钥/私私钥对: 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保密私保密私钥:
13、PR = d, n 密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院21RSA 的使用的使用n为了加密消息了加密消息M，发送方送方:q获得接收方的公得接收方的公钥 PU = e, n q计算算: C = Me mod n, 其中其中 0 M nn为了解密密文了解密密文C，接收者，接收者:q使用自己的私使用自己的私钥 PR = d, n q计算算: M = Cd mod n n消息消息M一定要比模数一定要比模数 n小小 (如果需要的如果需要的话，可以可以进行分行分组)密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华
14、中农业大学信息学院22RSA的工作原理的工作原理nEuler定理定理:qa(n) mod n 1 其中其中(a, n) = 1nRSA中中:qn = p.qq(n) = (p-1) (q-1) q仔仔细地地选择 e 和和 d 使得使得 mod (n) 下，两者互逆下，两者互逆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 密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院23RSA
15、举例例 密密钥的建立的建立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.确定确定 d: d e = 1 mod 160 且且 d 160 d = 23 因因为 23 x 7=161= 10x160+16.公公钥 PU = 7, 187 7.私私钥 PR = 23, 187 密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院24RSA 举例例 加
16、密加密/加密加密n明文消息明文消息 M = 88 ( 注意注意88 187)n加密加密:C = 887 mod 187 11 n解密解密:M = 1123 mod 187 88 密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院25幂 运运 算算n可以用平方和乘法运算可以用平方和乘法运算nN 次方，只需要次方，只需要 O(log2 n) 次乘法运算次乘法运算q如如. 75 = 74.71 = 3.7 = 10 mod 11q如如. 3129 = 3128.31 = 5.3 = 4 mod 11密码编码学与网络安全（第五版）向金海06-公钥密码学与
17、rsa2024/7/20华中农业大学信息学院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 密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院27密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院28加密的效率加密的效率n加密要加密要计算算 e 次方次方幂n若若 e 较小小, 计算将很快算将很快q通常通常
18、选择 e = 65537 (216-1)q或或选择 e = 3 或或 e = 17n但若但若 e太小太小 (如如 e = 3)将易受到攻将易受到攻击q用中国剩余定理用中国剩余定理n必必须确保确保(e, (n) = 1密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院29解密的效率解密的效率n解密解密计算算d次方次方幂q看起来很大，否看起来很大，否则不安全不安全n用用中中国国剩剩余余定定理理分分别计算算mod p和和mod q，则可以得到所希望的答案可以得到所希望的答案q比直接快比直接快约4倍倍n只只有有知知道道p和和q及及私私钥的的接接收收者者可
19、可以以直直接接采采用用这个技个技术进行行计算算密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院30RSARSA密密钥的的产生生nRSA的用的用户必必须:q随机确定两个素数随机确定两个素数 p, q q选择e或或d，并求出另一个，并求出另一个n素数素数 p, q 一定不能从一定不能从n = p . q轻易得到易得到q意味着数要足意味着数要足够大大q典型地用猜典型地用猜测或可能性或可能性测试n指数指数e, d 是互逆的是互逆的密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院31RSARSA安全性分析
20、安全性分析n攻攻击RSA可能的方法有可能的方法有:q穷举搜索搜索 (对于于给定的数字定的数字规模是不可行的模是不可行的)q数数学学攻攻击 (基基于于计算算(n)的的困困难性性, 模模n的的因因子子分分解解的困的困难性性)q计时攻攻击 (基于解密的运行情况基于解密的运行情况)q选择密文攻密文攻击(RSA的已知特性的已知特性)密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院33分解因子分解因子问题n数学攻数学攻击的三种形式的三种形式:q分解分解 n = p.q, 计算算(n) 从而得到从而得到 dq直接确定直接确定 (n) 并并计算算 dq直接直接
21、寻找找d n对于因子分解于因子分解问题q很多年来很多年来进展很慢展很慢n用用“Lattice Sieve” (LS),算算法法，最最好好的的是是分分解解了了200位位十十进制数制数(663 bit) q最大的改最大的改进就是就是对改改进算法的改良算法的改良n QS to GHFS to LSq当前假当前假设1024-2048bit RSA 是安全的是安全的n确保确保 p, q 有相似的大小并有相似的大小并满足其它足其它约束束密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院34密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/
22、7/20华中农业大学信息学院35计 时 攻攻 击n20世世纪90年代由年代由Paul Kocher提出提出n探探测操作中的操作中的时间变化化qeg. multiplying by small vs large number qor IFs varying which instructions executedn基于所耗基于所耗时间的大小，的大小，对操作数的大小操作数的大小进行猜行猜测nRSA exploits time taken in exponentiationnCountermeasures(解决解决办法法)quse constant exponentiation time（不（不变的的
23、 幂运算运算时间）qadd random delays（随机（随机时延）延）qblind values used in calculations（隐蔽）蔽）密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院36选择密文攻密文攻击nRSA 对于于选择密文来密文来说是易受攻是易受攻击的的q攻攻击者者选择密文并得到相密文并得到相应明文明文q选择密文可密文可给密密码分析者探分析者探测RSA的特性提供信息的特性提供信息qoptimal asymmetric encryption padding (OAEP).密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院37小小 结q公公钥密密码的原理的原理n两个密两个密钥：公：公钥/私私钥n单向陷向陷门函数函数qRSA算法，算法，实现和安全分析和安全分析密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa2024/7/20华中农业大学信息学院38第第9 9章作章作业n思考思考题：9.1 9.3 9.6n习 题： 9.2.a 9.2.b 9.3 9.4密码编码学与网络安全（第五版）向金海06-公钥密码学与rsa
