《网络安全-09：公钥密码学rsa资料》由会员分享，可在线阅读，更多相关《网络安全-09：公钥密码学rsa资料（34页珍藏版）》请在金锄头文库上搜索。
1、Chapter 9 公钥密码学RSA,密码编码学与网络安全,2019/9/17,2,为什么需要公钥密码?,1）对称密码体制的密钥分配问题：通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现； 2）对称密码体制的密钥管理问题：在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目是非常大 。 3）对称密码体制没有签名功能：当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B。,2019/9/17,3,公钥密码体制,密码学发展历史中最伟大的一次革命 公认该发明属于Stanford Un
2、i 的Whitfield Diffie 和 Martin Hellman ，于1976年。 “New Directions in Cryptography“, IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976 James Ellis (UK CESG) 在1970年曾提出此概念 基于数论中的结论,公钥密码体制,公钥/双钥/非对称 密码都是指使用两个密钥: 公钥：可以对任何人公开的密钥，用于加密消息或验证签名。 私钥：只能由接收者私存，用于解密消息或签名。 非对称 用于加密消息或验证签名的密钥不能进行解密消息的或消息的签名。,2
3、019/9/17,5,2019/9/17,6,公钥密码体制的应用,分为三类: 加密/解密 (提供保密性) 数字签名 (提供认证) 密钥交换 (会话密钥) 一些算法可用于上述三类，而有些只适用用于其中一类或两类。,2019/9/17,7,DSS：美国数字签名标准,2019/9/17,8,公钥密码体制的应用,是私钥密码的补充而不是代替 三种误解： 比传统密码更安全； 传统密码已过时； 公钥密码分配非常简单。,2019/9/17,9,公钥密码体制的应用：保密性,2019/9/17,10,公钥密码体制的应用：认证,2019/9/17,11,公钥密码体制的应用：保密性和认证,2019/9/17,12,公
4、钥密码的要求,公私钥对产生在计算上容易； 加密在计算上容易； 解密在计算上容易； 已知公钥，求私钥在计算上不可行； 已知公钥和密文，恢复明文计算上不可性。 加密和解密函数的顺序可以交换（附加条件）,2019/9/17,13,单向陷门函数,单向陷门函数： 若k和X已知，则容易计算 Y = fk(X). 若k和Y已知，则容易计算X = fk-1(Y). 若Y已知但k未知，则计算出X = fk-1(Y)是不可行的. 寻找合适的单向陷门函数是公钥密码体制应用的关键 单向陷门函数举例： 离散对数 大整数分解,2019/9/17,14,公钥密码体制安全性分析,一样存在穷举攻击 从安全性考虑，使用的密钥一般
5、都非常大 ( 512bits ) 为了便于实现加解密，密钥又必须足够短。 公钥密码目前仅限与密钥管理和签名中。 另外一种攻击方法：从给定的公钥计算出私钥的方法。 到目前为止，还未在数学上证明对一特定公钥算法这种攻击是不可行的。（包括RSA） 公钥体制特有的攻击 穷举消息攻击,2019/9/17,15,9.2 RSA,1977由MIT的Rivest, Shamir 和 Adleman发明 已知的且被广泛使用的公钥密码方案 有限域中的乘方运算 乘方运算需要 O(log n)3) 操作 (容易的) 使用一些大的整数 (例如. 1024 bits) 安全性基于大数的素因子分解的困难性 素因子分解需要
6、O(e log n log log n) 操作 (困难的),2019/9/17,16,2019/9/17,17,2019/9/17,18,RSA 密钥的建立,每一个用户通过以下方法产生一个公钥/私钥对: 随机地选择两个大的素数 p, q 计算方案中的模数 n = p.q (n) = (p-1) (q-1) 随机地选择一个加密密钥e 满足 1 e (n), gcd (e, (n) = 1 求解下面的方程，以得到解密密钥d e.d 1 mod (n) and 0 d n 公开公钥: PU = e, n 保密私钥: PR = d, n,2019/9/17,19,RSA 的使用,为了加密消息M，发送方
7、: 获得接收方的公钥 PU = e, n 计算: C = Me mod n, 其中 0 M n 为了解密密文C，接收者: 使用自己的私钥 PR = d, n 计算: M = Cd mod n 消息M一定要比模数 n小 (如果需要的话，可以进行分组),2019/9/17,20,RSA的工作原理,Euler定理: a(n) mod n 1 其中(a, n) = 1 RSA中: n = p.q (n) = (p-1) (q-1) 仔细地选择 e 和 d 使得 mod (n) 下，两者互逆 因此存在某个整数k，使得e.d = 1 + k.(n) 成立 所以 : Cd = Me.d = M1+k.(n)
8、 = M1.(M(n)k M1.(1)k = M1 = M mod n,2019/9/17,21,RSA 举例 密钥的建立,选择素数: p = 17 选择 e = 7 确定 d: d e = 1 mod 160 且 d 160 d = 23 因为 23 x 7=161= 10x160+1 公钥 PU = 7, 187 私钥 PR = 23, 187 ,2019/9/17,22,RSA 举例 加密/加密,明文消息 M = 88 ( 注意88 187) 加密: C = 887 mod 187 11 解密: M = 1123 mod 187 88,2019/9/17,23,幂 运 算,可以用平方和乘
9、法运算 N 次方，只需要 O(log2 n) 次乘法运算 如. 75 = 74.71 = 3.7 = 10 mod 11 如. 3129 = 3128.31 = 5.3 = 4 mod 11,2019/9/17,24,幂 运 算,long PowerMod(int a, int b, int k) long tmp = a; long ret = 1; while (b) if (b ,2019/9/17,25,2019/9/17,26,加密的效率,加密要计算 e 次方幂 若 e 较小, 计算将很快 通常选择 e = 65537 (216+1) 或选择 e = 3 或 e = 17 但若 e太
10、小 (如 e = 3)将易受到攻击 用中国剩余定理 解决方法：M随机填充一个唯一的伪随机比特串 必须确保gcd(e, (n) = 1,2019/9/17,27,解密的效率,解密计算d次方幂 d的值太小容易遭受穷举攻击和其他形式的攻击。 用中国剩余定理分别计算mod p和mod q，则可以得到所希望的答案 比直接快约4倍 只有知道p和q及私钥的接收者可以直接采用这个技术进行计算,2019/9/17,28,RSA 密钥的产生,RSA的用户必须: 随机确定两个素数 p, q 选择e或d，并求出另一个 素数 p, q 一定不能从n = p . q轻易得到 意味着数要足够大 典型地用猜测或可能性测试（M
11、iller-Rabin） 指数e, d 是互逆的 （欧几里得扩展算法）,2019/9/17,29,RSA 安全性分析,攻击RSA可能的方法有: 穷举搜索 (对于给定的数字规模是不可行的) 数学攻击 (基于计算(n)的困难性, 模n的因子分解的困难性) 计时攻击 (基于解密的运行情况) 选择密文攻击(RSA的已知特性),2019/9/17,30,分解因子问题,数学攻击的三种形式: 分解 n = p.q, 计算(n) 从而得到 d 直接确定 (n) 并计算 d （等价于因子分解n） 直接寻找d （至少和因子分解问题一样费时） 对于因子分解问题 很多年来进展很慢 用“Lattice Sieve” (
12、LS),算法，最好的是分解了200位十进制数(663 bit) 最大的改进就是对改进算法的改良 QS to GHFS to LS 当前假设1024-2048bit RSA 是安全的 确保 p, q 有相似的大小并满足其它约束,2019/9/17,31,MIPS：一台每秒执行百万条指令的处理器运行1年 1GHz的奔腾机约等于一台250MIPs,2019/9/17,32,RSA系统安全性与系统的参数,RSA系统安全性与系统的参数有很大关系，X.931标准, ISO/IEC 14752对此提出以下几点： p和q的长度应仅差几位。 （p-1）和（ q-1）都应有大的素因子； gcd(p-1, q-1)
13、应该小；,2019/9/17,33,计 时 攻 击,20世纪90年代由Paul Kocher提出 类似于窃贼通过观察他人转动保险柜拨号盘的时间长短来猜测密码。 探测操作中的时间变化 eg. multiplying by small vs large number 基于所耗时间的大小，对操作数的大小进行猜测 Countermeasures(解决办法) use constant exponentiation time（不变的 幂运算时间） add random delays（随机时延） blind values used in calculations（隐蔽）,2019/9/17,34,选择密文攻击,RSA 对于选择密文（CCA）来说是易受攻击的 攻击者选择密文并得到相应明文 选择密文可给密码分析者探测RSA的特性提供信息 C=Me mod n X=C* 2e mod n 对策： 采用最优非对称加密填充(OAEP).的程序对明文进行修改。,2019/9/17,35,小 结,公钥密码的原理 两个密钥：公钥/私钥 单向陷门函数 RSA算法，实现和安全分析,
