crypto4c-ch09-公钥密码学和RSA.ppt

1、第9章 公钥密码学和RSA,9.1 公钥密码体制的基本原理 公钥密码体制的基本概念 公钥密码体制的应用 对公钥密码的要求 9.2 RSA算法,密码学的重要进步,从Rotor到DES 都是基于代换和置换等初等方法 密码学的新方向 Whitfield Diffie, Hellman 1976 提出了公钥密码算法的概念和思路 提出了数字签名问题 提出了DH密钥交换协议,澄清误解,公钥算法更安全 不能简单比较 传统对称算法已经过时 事实上，现在使用的是混合密码体制 公钥体制避免了传统KDC带来的麻烦 事实上，证书体制有其优点但绝非简单 公钥算法就是RSA RSA只是当前最重要的公钥算法,9.1 公钥密

2、码体制的基本原理,公钥算法的思路的提出本身就是一个进步。遵从公钥体制能够简化密钥管理，能够实现数字签名等安全特性。 和DES等对称算法不同，公钥体制的形式和结构导致公钥算法必须使用某种数学结构，而不能再使用代换和置换等初等方法。 从形式上看，公钥算法将比对称算法更简洁和易于理解。,公钥密码算法的思路,对称算法的缺陷 为事先获得密钥，需另外的安全信道或KDC 不能满足签名的需求 公钥算法（6个组成部分） 密钥 K （Kd，Ke），Kd即私钥 Ke即公钥 加密：E（P，Ke） C 解密：D（C，Kd） P 要求从Ke Kd 理论上能够 实际上因需要计算量太大因而难以实施,公钥算法参数建立,每个用户

3、生成密钥对(Ke、Kd) Ke或Kd是一个数(大数) 而不是随机比特（对称算法中） Ke需要公开 Kd得自己秘密保留（本地产生，不需要传输） (公钥 public key 私钥private key 密钥 secret key) 公钥的发布 从Ke推导Kd的困难性使Ke不怕被公开 公钥Ke要在专门机构（CA）登记,一个有趣的问题,有人提出一种方法，可用来确认你的密钥是否与另一人的相同。你首先产生一个与密钥等长的随机二进制串P，并将其与密钥K1异或，然后把结果C发给另一人。对方将收到的二进制串C与自己的密钥K2异或，再将结果P发回给你。你将P与P进行核对，就可以知道两个密钥K1和K2是否相同，在

4、整个过程中没有发送真正的密钥。 这种方法中有一个缺点，你看出来了吗？ 攻击者可以截获传输的信息C和P，当两个密钥K1和K2相同时，C = PK1，P = CK2 = CK1 = P，则攻击者得到 K1 = K2 = CP。,公钥算法加密,加密（如果有人要给用户A发送消息P） 他先获得该用户的公钥Ke 加密C = E（P，Ke） 传输 解密D（C，Kd）= P 除非拥有Kd，像用户A，否则不能解密 * 一般用于传输会话密钥（和签名及认证）,公钥算法用来加密概念图示,公钥算法用来加密图示,公钥,私钥,公钥算法用来认证,如果你(Bob)已经公布自己的公钥Ke，则他人可鉴别你发出的消息（及你的身份）

5、对于消息P，使用你的私钥加密 C = E（P，Kd） 他人可把密文C用你的公钥解密 D（C，Ke）= P 可以确信P必然是由你加密成C的，因为加密需要的私钥只有你有。,公钥算法用来认证概念图示,公钥算法用来认证图示,公钥,私钥,公钥算法用来认证,如果你有用户A的公钥Ke，则可鉴别A的身份 取随机秘密消息P加密 C = E（P，Ke） 把密文C交给所谓的”A”，请A来解密 除非”A”拥有Kd，否则不能解开 D（C，Kd）P 比较A解出的明文P是否正确 如果A能正确解密，则”A”是所声称的A,消息来源鉴别和数字签名,假设使用加解密操作对称的算法如RSA 对消息H签名（整条消息或部分）： S = S

6、ig(H，Kd) 接收方对消息H验证： Ver(C，Ke) ?= H 消息H必然是Kd的持有人签署的,结合使用加密和签名,有消息要发给对方，要署名且保密传递 发送方：先用自己的私钥签名 发送方：再用对方的公钥加密 发送 接收方：先用自己的私钥解密 接收方：再用对方的公钥验证签名是否有效,有何缺点？,一个有趣的案例,兄弟俩为设计简单又安全的协议而争论不休。哥哥提出如下双方通信协议：假设用户A要将消息M发送给用户B，传输的消息形式为（发送方的标识，消息正文，接收方的标识）。 1、A将(A, E(PUb, M, A), B)发送给B。 2、B发送应答(B, E(PUa, M, B), A)给A。 弟

7、弟认为该协议不够简单，存在一些冗余，可简化为： 1、A将(A, E(PUb, M), B)发送给B。 2、B发送应答(B, E(PUa, M), A)给A。 弟弟的协议确实比较简单，但不如哥哥的协议安全，容易受到某种形式的攻击。若攻击者X也是该网络中的用户，有自己的公钥PUx，并能截获A，B之间传输的信息，则攻击者可以通过某个过程得到A发给B的消息M。他是如何做到的？,公钥密码体制的应用,加密/解密：如RSA，椭圆曲线密码 数字签名：如RSA，椭圆曲线密码，DSS 密钥交换：如RSA，DH,构造公钥算法的考虑,对称算法 代换 置换 基于某些数学特性 从公钥推导私钥理论可能，但计算困难 (从私钥

8、到公钥容易) 单向函数(one-way function),对公钥算法的要求,公钥算法应满足以下条件： 产生密钥对在计算上容易 使用公钥加密在计算上容易 使用私钥解密在计算上容易 已知公钥确定私钥在计算上不可行 已知公钥和密文恢复明文在计算上不可行 加密和解密对称,单向函数,单向函数 单向陷门函数 单向散列函数,单向函数,单向性 单向函数 函数值计算很容易：已知x，很容易计算y = f(x) 逆计算是不可行的：已知y，很难计算x = f-1(y) 困难程度 举例 打碎/拼接、平方/开方、乘法/分解 * 单向函数是否存在 尚无严格的数学证明,单向陷门函数,单向陷门函数 如果知道某个陷门(秘诀)，

9、就能容易恢复x （陷门即为私钥） 举例 魔方的置乱/恢复 如果有口诀，就能很快恢复 加密/解密,单向散列函数,单向散列函数 h = H(m)，其中 m 任意长度，h 定长 有的散列函数并不满足单向(抗冲突)性质 密码学上用的散列函数都是指单向散列函数 抗冲突性质 给定h，找 m 满足 H(m)=h 很难 给定m，找 m 满足 H(m)=H(m) 很难 直接找 m1和m2 满足 H(m1)=H(m2) 很难 举例 MD5、SHA1,9.2 RSA算法,作者 1977年，R, S, A Ron Rivest Adi Shamir Len Adleman 基本参数 分组密码算法 基于整数乘法 明/密

10、文分组以及公/私钥被看作小于n的整数 加/解密是模幂运算,RSA 加解密,加密 明文分组M作为整数须小于n C = Me mod n 解密 M = Cd mod n = Med mod n 满足条件 存在e, d, n，使得 M = Med mod n 成立； 计算 Me mod n 和 Cd mod n 是容易的； 由 e, n 确定 d 是不可行的。,ed 1 mod(n),RSA算法参数建立,找素数 选取两个大素数p和q 计算模数n和欧拉函数(n) n = pq (n) = (p-1)(q-1) 找 ed 1 mod(n) 选取数e，用扩展的欧几里德算法求数d 发布 发布(e, n)，这

11、是公钥 ke d保密，(d, n)是私钥 kd,RSA 计算实例,选 p7，q17 则 npq119 且(n)(p-1)(q-1)61696 取 e5 则 d77 (57738549611 mod 96) 公钥（5，119），私钥（77，119） 加密 M19 则 CMe mod n = 195 mod 119 = 66 解密 C66 MCd mod n = 6677 mod 11919,ab mod n 模幂运算,97221 mod 2003（都在模2003意义下） 97221 = 97128+64+16+8+4+1 = 97128 9764 9716 978 974 971 依次计算971

12、、 972、 974、 978、 9716 97128,快速模幂算法,计算 f = ab mod n f = 1; c = 0 For each bit of b = bkbk-1b0 f = (ff) mod n; c = 2c if bi = 1 then f = (fa) mod n; c = c+1 End For,快速模幂算法举例,计算 f = 7560 mod 561 560 表示为 1000110000 f = (ff) mod n; c = 2c if bi = 1 then f = (fa) mod n; c = c+1,快速模幂算法举例,计算 f = 7560 mod 56

13、1 560 表示为 1000110000 f = (ff) mod n; c = 2c if bi = 1 then f = (fa) mod n; c = c+1,快速模幂算法举例,计算 f = 7560 mod 561 560 表示为 1000110000 f = (ff) mod n; c = 2c if bi = 1 then f = (fa) mod n; c = c+1,快速模幂算法举例,计算 f = 7560 mod 561 560 表示为 1000110000 f = (ff) mod n; c = 2c if bi = 1 then f = (fa) mod n; c = c

14、+1,快速模幂算法举例,计算 f = 7560 mod 561 560 表示为 1000110000 f = (ff) mod n; c = 2c if bi = 1 then f = (fa) mod n; c = c+1,RSA 举例,若攻击者截获发给用户B的密文C = 10，用户B的公钥 e=5, n=35，那么明文M=？ 猜测 35 = 57，则(n)= 46 = 24 d = 5, (55 mod 24 = 1) M = 105 mod 35 = 5,RSA 实现考虑,选取较小的e（较大的d） e：3、17、65537 若指数太小，RSA易受攻击。如： 三个用户均用e = 3，则三个

15、公钥(3, n1), (3, n2), (3, n3)。用户A分别给这三个用户发送相同的消息M，则三条密文为 若n1, n2, n3两两互素，则利用中国剩余定理可以计算出 M3 mod (n1*n2*n3)，从而恢复明文M。,使用中国剩余定理加快运算,解密时需要计算 M = Cd mod n 定义一些中间结果 Vp = Cd mod p Vq = Cd mod q Xp = q(q-1 mod p) Xq = p(p-1 mod q) 利用CRT，得 M = (VpXp + VqXq) mod n Vp = Cd mod p = Cd mod p-1 mod p Vq = Cd mod q =

16、 Cd mod q-1 mod q 可加快约4倍,使用CRT加快运算举例,计算 M = 120523 mod 1813 1813 = 3749 Vp = 120523 mod 37 = 14 Vq = 120523 mod 49 = 32 Xp = 49(49-1 mod 37) = 4934 Xq = 37(37-1 mod 49) = 374 M = (VpXp + VqXq) mod n = (493414 + 37432) mod 1813 = 865,RSA 密钥产生,通信之前，每个用户产生一个密钥对 确定两个素数 p 和 q 选择 e 计算 d，或者选择 d 计算 e 素数 必须够

17、大，否则对手可能很快分解n 判定，试除法不可行 判定，采用Miller-Rabin概率测试方法,判定N可能是素数,RSA 案例,在RSA公钥密码体制中，每个用户都有一个公钥e，一个私钥d。假定用户B的私钥已泄密。B决定产生新的公钥和新的私钥，而不是产生新的模数。请问这样安全吗？,攻击 RSA 算法,穷举 穷举所有可能明文M，用e加密和C比较 穷举所有可能的私钥d 数学方法 分解n=pq，就可以计算(n)，就可从e求得d 不分解n，而直接求(n)，再求d 不求(n)，直接求d,分解里程碑,十/二进制 日期 MIPS年 方法 69/1983 二次筛法 106/1989. 100/332 April

18、 1991 7 . 110/365 April 1992 75 . 120/398 June 1993 830 . 129/428 April 1994 5000 . 130/431 April 1996 5000 一般数域筛法 140 Feb 1999 . 155Aug 1999 8400. 1601 Apr 2003 格筛法 174/576Dec 3,2003. 200/663 9 May 2005.,因子分解所需的MIPS年,抵抗因子分解,n如果有特殊结构，则较易被分解，因此： n要尽量大，当前1024位应该是安全的 p和q应该长度接近，比如都约512位 gcd(p-1, q-1)应该比

19、较小,计时攻击,攻击者可以统计解密时间来确定d 仅依赖密文 可攻击DH, RSA, DSS及其它密码系统 以模幂算法为例 f = (ff) mod n; c = 2c if bi = 1 then f = (fa) mod n; c = c+1 计时攻击从高位到低位，一位一位进行。对有些f和a的值，模乘运算f = (fa) mod n异常慢。通过观察执行时间，可猜测bi的值。,抵抗计时攻击,不变的幂运算时间 保证所有的幂运算在返回结果之前，执行时间都相同 随机延时 在求幂算法中加入随机延时，来迷惑攻击者 隐蔽 在执行幂运算之前先将密文乘上一个随机数，使攻击者不知道计算机正在处理的是密文的哪些位。,RSA公司使用隐蔽方法 产生秘密随机数 r 用随机数 r 把 C 掩盖为 C 把 C 用私钥 d 解密得到 M 将 M 乘以 r -1，即得 M 利用以上隐蔽方法，运算性能降低了,抵抗计时攻击,选择密文攻击与最佳非对称加密填充,攻击者选择一些密文，并利用被攻击者的私钥获得相应的明文 利用RSA的如下性质： 若要解密 C = Me mod n，则攻击者 计算 X = (C2e ) mod n 将X发给被攻击者，请他解密，获得 Y = Xd mod n 由于 X = (C2e ) mod n = (C mod n)(2e mod n) = (Me mod n)(