《网络安全-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算法,实现和安全分析,