现代密码学理论与实践 第9章 公钥密码学与RSA Fourth Edition by William Stallings Slides by 杨寿保 syang@ustc.edu.cn http://staff.ustc.edu.cn/~syang 2012年10月 2019/1/16 现代密码学理论与实践-09

本章要点 非对称密码是一种密码体制，其加密算法和解密算法使用不同的密钥，一个是公钥，一个是私钥。非对称密码也称为公钥密码。 非对称密码用两个密钥中的一个以及加密算法将明文转换为密文，用另一个密钥以及解密算法从密文恢复出明文。 非对称密码可以用来保密、认证或者两者兼而有之。 应用最广泛的公钥密码体制是RSA，破解RSA的困难，是基于分解大合数素因子的困难。 2019/1/16 现代密码学理论与实践-09

9.1 公开密钥密码体制的基本原理 对称密码体制的问题 非对称密码体制的基本特点 加密能力与解密能力是捆绑在一起的 密钥更换、传递和交换需要可靠信道，密钥分发困难 如有N用户，则需要C=N(N-1)/2个密钥，n=1000时，C(1000, 2)≈500000, 密钥管理困难 无法满足不相识的人之间通信的保密要求 不能实现数字签名 非对称密码体制的基本特点 加密能力与解密能力是分开的 密钥分发简单 需要保存的密钥量大大减少，N个用户只需要N个密钥 可满足不相识的人之间保密通信 可以实现数字签名 2019/1/16 现代密码学理论与实践-09

公开密钥密码体制 公钥算法依赖于一个加密密钥和一个与之相关的不同的解密密钥，算法有如下特点： 公钥密码体制的组成 仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的 两个密钥的任何一个都可用来加密，另一个用来解密 公钥密码体制的组成 明文：算法的输入，可读信息或数据 加密算法：对明文进行各种转换 公钥和私钥：算法的输入，分别用于加密和解密 密文：算法的输出，依赖于明文和密钥 解密算法：根据密文和密钥，还原明文 2019/1/16 现代密码学理论与实践-09

公钥算法的主要步骤 每个用户产生密钥，用来加密和解密消息 每个用户将其中一个密钥(公钥)存于公开的寄存器或其他可访问的文件中，另一密钥私有，每个用户可以拥有若干其他用户的公钥 若Bob要发消息给Alice，则要用Alice的公钥对消息加密 Alice收到消息后，用其私钥对消息解密，由于只有Alice知道其自身的私钥，所以其他的接收者均不能解密消息 需要认证时示证方用自己的私钥加密消息(签名) 验证方用示证方的公钥解密消息(验证)，如果结果证实公钥与示证方的私钥相吻合，则可以确认示证方确为合法的用户(认证) 加密和认证可以结合起来，同时实现保密性和认证 2019/1/16 现代密码学理论与实践-09

公开密钥加密过程 2019/1/16 现代密码学理论与实践-09

公开密钥认证过程 2019/1/16 现代密码学理论与实践-09

常规和公开密钥加密的重要特征 2019/1/16 现代密码学理论与实践-09

公开密钥密码系统：保密性 C = KUb(M) M = KRb(C) 2019/1/16 现代密码学理论与实践-09

公开密钥密码系统：认证 S = KRa(M) M = KUa(S) 2019/1/16 现代密码学理论与实践-09

公开密钥密码系统：保密和认证 C = KRa(KUb(M)) M = KRb(KUa(C)) 2019/1/16 现代密码学理论与实践-09

公钥密码体制的应用 加密/解密：发送方用接收方的公钥对消息加密 数字签名：发送方用其私钥对消息签名，可以对整体消息签名或对消息的摘要签名 密钥交换：通信双方交换会话密钥 2019/1/16 现代密码学理论与实践-09

对公开密钥密码编码系统的要求 产生一对密钥(公钥ke和私钥kd)在计算上是容易的 不难计算C=E(ke, m)和m=D(kd, C) 不知道kd，即使知道ke, E, D及C，计算m也不可行 对明文m, E(ke, m)有定义，且D(kd, E(ke, m))=m 对密文C, D(kd, C)有定义，且E(ke, D(kd, C))=C 加密变换和解密变换可以互换顺序, 即D(E(m))=E(D(m)) 1976年，Whitfield Diffie和Martin Hellman提出这样的设想：每个用户A有一加密密钥ka，不同于解密密钥ka’，可将加密密钥ka公开，ka’保密，要求ka的公开不影响ka’的安全。若B要向A秘密发送明文m，可查A的公开密钥ka，加密得密文C=Eka(m) A收到C后用只有A才拥有的解密密钥ka’对C进行解密得m=Dka’(C). 实用方案的发展依赖于单向陷井函数 2019/1/16 现代密码学理论与实践-09

Whitfield Diffie and Martin Hellman Dr. Diffie is currently a Distinguished Engineer at Sun Microsystems and Professor Hellman is a Professor Emeritus of Electrical Engineering at Stanford University British Intelligent agency also discovered public key cryptography in early 1970’s, due to confidential reason, their work was no known to public until 1990’s. WHITFIELD DIFFIE MARTIN HELLMAN 2019/1/16 现代密码学理论与实践-09

公钥密码的分析 公钥密码易受穷举攻击，解决方法是使用长密钥；同时为了便于实现加密和解密，又希望密钥足够短，目前仅限于密钥管理和签名。 找出一种从给定的公钥计算出私钥是第二种攻击方法，尚未在数学上证明对一特定公钥算法这种攻击是不可行的，因此包括RSA在内的任何算法都是值得怀疑的。 穷举消息攻击是第三种攻击形式，攻击者用公钥对所有可能的消息加密，并与传送的密文匹配，从而解密任何消息；抵抗的方法是在要发送的消息后附加随机数。 2019/1/16 现代密码学理论与实践-09

9.2 RSA算法 概述 1977年，Rivest、Shamir、Adleman提出的非对称密码体制，是基于大合数的素因子分解问题的困难性。1994年4月一个小组通过Internet合作，8个月时间成功分解129位的数，大约428比特；1999年分解155位合数，最新的记录是2005年5月分解200位十进制数。 RSA专利于2000年9月20日到期。 2019/1/16 现代密码学理论与实践-09

R-S-A Ron Rivest, Adi Shamir, Len Adleman Rivest: professor in MIT Shamir: a founder of a security company in Isreal Adleman: a professor in USC (Left to Right: Ron Rivest, Adi Shamir, Len Adleman) 2019/1/16 现代密码学理论与实践-09

RSA密码体制基本原理 算法流程 随机选择两个秘密大素数p和q； 计算公开模数n=p*q； 选择一个与φ(n)互素的数，作为e或d； 用Euclid算法计算模φ(n)的乘法逆元素，即根据 ed mod φ(n)=1, 求d或e； 加密：C = Me mod n 解密：M= Cd mod n = (Me mod n)d mod n = M 这里，φ(n)为欧拉商数, 即集合(1, 2, ..., n-1)中与n互素的数的个数。 2019/1/16 现代密码学理论与实践-09

2019/1/16 现代密码学理论与实践-09

2019/1/16 现代密码学理论与实践-09

一个例子 p=17,q=11,n=pq=17x11=187, φ(n)=(p-1)(q-1) =16x10=160 选择e=7, gcd(7,160)=1, 23x7=161, 所以d=23 公钥KU={7,187}, 私钥KR={23,187}, M=88 加密计算C=887 mod 187 887 mod 187 =[(884mod187)x882mod187)x881mod187)]mod187 881mod187=88 882mod187=7744mod187=77 884mod187=59969536mod187=132 887mod187=(88x77x132)mod187=894432mod187=11 解密计算M=1123 mod 187 = 88 2019/1/16 现代密码学理论与实践-09

RSA密码体制基本原理 RSA算法满足公开密钥加密的要求, 必须符合下列条件： 几个关系 有可能找到e, d, n的值, 使得对所有M<n有 Med mod n = M 对于所有M<n的值, 要计算Me和Cd是相对容易的 在给定e和n时, 计算d是不可行的 几个关系 φ(n) = φ(pq)=φ(p)φ(q)=(p-1)(q-1), p,q 是素数 ed mod φ(n)=1, ed = kφ(n)+1, 即ed mod φ(n) =1, d=e-1 mod φ(n) 2019/1/16 现代密码学理论与实践-09

RSA密码体制基本原理 定理：给定ed mod φ(n) =1, m∈[0, n-1], gcd(m, n)=1, 则： (me mod n )d mod n = med mod n = m 证明：∵ ed mod φ(n) = 1 ∴ ed = kφ(n)+1，对某些整数k ∴ med mod n = mkφ(n)+1 mod n = m(mkφ(n) mod n) mod n ∵mkφ(n) mod n = (mφ(n) mod n)k mod n = 1k mod n = 1 ∴med mod n = (m* 1) mod n = m 2019/1/16 现代密码学理论与实践-09

RSA密码体制基本原理 RSA方案概述 素数 p, q, 私有，选择 n=pq, 公开，计算出 e, gcd(φ(n), e) = 1; 1 < e < φ(n), 公开，选择 d=e-1 mod φ(n), 私有，计算出 RSA实现方面的考虑 加密与解密 模运算特性之一 [(a mod n) x (b mod n)] mod n = (a x b) mod n 指数运算的效率问题 2019/1/16 现代密码学理论与实践-09

计算ab mod n的算法和快速取模指数算法 2019/1/16 现代密码学理论与实践-09

密钥的产生和检验素数 确定两个素数p和q，选择e或d并计算另外一个 检验素数 例：p = 5, q = 7, n = 35, φ(n)=24 随机选一个整数a < n 完成随机素数性检验，如果n没有通过检验，则另选n 如果n通过了足够多次的检验，则接受n，否则另选 例：p = 5, q = 7, n = 35, φ(n)=24 选d = 11，则e = inv(11, 24) = 11，M = 2 C = me mod n = 211 mod 35 = 18 M = Cd mod n = 1811 mod 35 = 2 2019/1/16 现代密码学理论与实践-09

RSA的安全性 RSA的安全性 有三种可能的对RSA的攻击方法 强行攻击：尝试所有可能的密钥 数学攻击：对两个素数乘积的因子分解(FAC问题) 计时攻击：依赖于解密算法的运行时间 选择密文攻击：利用了RSA算法的性质 RSA的安全性问题依赖于大合数的素因子分解，即factorization problem (FAC)，FAC的计算复杂性为T=exp((ln(n)ln(ln(n)))1/2)，同DLP问题。 2019/1/16 现代密码学理论与实践-09

p和q应满足下列约束条件： P和q的长度应仅相差几位，p和q都应约在1075到10100之间 (p-1)和(q-1)都应有一个大的素因子 GCD(p-1, q-1)应该较小 另外，已经证明，若e<n且d<n1/4，则d很容易确定 2019/1/16 现代密码学理论与实践-09

2019/1/16 现代密码学理论与实践-09

针对RSA的计时攻击 计时攻击 可能的解决办法 类似通过观察他人转动保险柜拨号盘的时间长短来猜测密码 不变的幂运行时间，可能会降低性能 在求幂运算中加入随机延时 隐蔽：在执行幂运算之前先将密文乘上一个随机数 RSA数据安全算法，用私钥实现操作M=Cd mod n的过程如下 产生0－n-1之间的秘密随机数r 计算C’=C(re) mod n, e是公开的指数 计算M’=(C’)d mod n 计算M=M’r -1 mod n, 其中r -1是r模n的乘法逆元，根据 redmod n=r，可以证明结论是正确的 2019/1/16 现代密码学理论与实践-09

几种不同复杂性的算法的代价 2019/1/16 现代密码学理论与实践-09

选择密文攻击和最佳非对称加密填充 基本的RSA算法容易受选择密文攻击(CCA) 利用CCA攻击RSA的一个简单例子利用了RSA如下的性质： E(PU, M1) x E(PU, M2)=E(PU, [M1 x M2]) 2019/1/16 现代密码学理论与实践-09

CCA攻击RSA 利用CCA攻击，可以如下方式解密C=Me mod n 注意： 因此，Y = (2M) mod n，由此可以得到M 计算 X=(C x 2e) mod n 将X作为选择明文提交，并收到Y=Xd mod n 注意： X = (C mod n) x (2e mod n) = (Me mod n) x (2e mod n) = (2M)e mod n 因此，Y = (2M) mod n，由此可以得到M 为防止这种简单攻击，RSA在加密之前对明文进行随机填充 2019/1/16 现代密码学理论与实践-09

第9章习题 第四版： 2, 3, 4, 11, 15, 16 Due day: Nov. 6, 2012 2019/1/16 现代密码学理论与实践-09