RSA加密系统的20年
RSA加密系统的20年
原文：Twenty Years of Attacks on the RSA Cryptosystem
作者：Dan Boneh@Stanford University(dabo@cs.stanford.edu)
译者：Harper
参考链接：
背景介绍
RSA密码系统由Ron Rivest, Adi Shamir和Len Adleman发明，在1977年8月的《科学美国人》杂志上首次公布。密码系统最常用于提供隐私和确保数字数据的真实性。目前，RSA被部署在许多商业系统中。它被网络服务器和浏览器用来保护网络传输，它被用来确保电子邮件的私密性和真实性，它被用来保护远程登录会话，它是电子信用卡支付系统的核心。简而言之，RSA常用于需要考虑数字数据安全性的应用程序中。
RSA加密算法
我们遵循标准命名约定，使用Alice和Bob表示希望相互通信的两个通用方。我们使用Marvin来表示恶意的攻击者，希望窃听或篡改Alice和Bob之间的通信。
参数设置
- 两个质数\(p和q\)，再计算得到\(N = p*q\)
- 一个随机整数\(e\in (1, φ(N))\),再计算\(d \equiv e^{-1} \pmod{\varphi(N)}\)
- 公钥pk = <N,e>
- 私钥sk = <N,d>
参数生成方法
第一步，随机选择两个不相等的质数p和q。
Alice选择了61和53。（实际应用中，这两个质数越大，就越难破解。）
第二步，计算p和q的乘积N。
Alice就把61和53相乘。
N = 61×53 = 3233
N的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
第三步，计算N的欧拉函数φ(N)。
N是质数，则 φ(N)=N-1 N = p1 × p2 φ(N) = φ(p1p2) = φ(p1)φ(p2) => φ(N) = (p-1)(q-1)
Alice算出φ(3233)等于60×52，即3120。
第四步，随机选择一个整数e，条件是1< e < φ(N)，且e与φ(N) 互质。
Alice就在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）
第五步，计算e对于φ(N)的模反元素d。
所谓”模反元素”就是指有一个整数d，可以使得ed被φ(N)除的余数为1,故\(d \equiv e^{-1} \pmod{\varphi(N)}\)
ed ≡ 1 (mod φ(N))
这个式子等价于
ed - 1 = kφ(N)
于是，找到模反元素d，实质上就是对下面这个二元一次方程求解，使用拓展欧几里得算法即可
ex + φ(N)y = 1
第六步，将N和e封装成公钥，N和d封装成私钥。
在Alice的例子中，N=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。
实际应用中，公钥和私钥的数据都采用ASN.1格式表达。
加密
密文是一个整数m属于乘法群\(\mathbb{Z^*_{N}}\)，即\(m \in \mathbb{Z^*_{N}}\)
计算密文ciphertext简称c，需要用到公钥pk=<N,e>
\(c \equiv m*e \pmod{N}\)
Alice的公钥是 (3233, 17)，Bob的m假设是65，那么可以算出下面的等式：
65^17 ≡ 2790 (mod 3233)
于是，c等于2790，Bob就把2790发给了Alice。
参数生成的效率
RSA密钥对的生成方法是随机选取两个\(\cfrac{n}{2}\)位素数并将其相乘得到N。然后，对于给定的加密$ e < (N)\(，使用扩展欧氏算法计算\)d e^{-1} $。
由于素数集非常密集，因此可以快速生成一个随机的\(\cfrac{n}{2}\)位素数，方法是选取随机的\(\cfrac{n}{2}\)位整数并用概率素数检验(如Fermat素性检验法)来检验每个整数的素数。
总体来说，生成素数还是比较快的，openssl生成一个1024位的素数在毫秒级即可实现。
解密
Alice拿到Bob发来的2790以后，就用自己的私钥(3233, 2753) 进行解密。可以证明，下面的等式一定成立：
\(m \equiv c^d \pmod{N}\)
也就是说，c的d次方除以N的余数为m。现在，c等于2790，私钥是(3233, 2753)，那么，Alice算出
2790^2753 ≡ 65 (mod 3233)
因此，Alice知道了Bob加密前的原文就是65。
解密正确性的证明
这里需要使用Euler定理,即
如果正整数 n 和整数 a 互质，那么就有 \(a^{\varphi(n)}≡1\pmod{n})\) 其中欧拉函数 φ(n) 是「小于 n 的正整数中和 n 互质的数」的个数
下面进入正式的证明过程
\[ c^d \equiv (m^e)^d \equiv m^{ed} \\ \because e*d \equiv 1 \pmod{\varphi(N)} \\ \therefore e*d=k*\varphi(N)+1 \; where \; k \in \mathbf{Z} \\ \therefore m^{ed} \equiv m^{k*\varphi(N)+1} \equiv m^{k*\varphi(N)} *m \pmod{N} \\ with\;the \; help \; of \; Euler \;theorem:m^{\varphi(N)} \equiv1 \pmod{N}\\ so: \; m^{ed} \equiv m^{k*\varphi(N)+1} \equiv m^{k*\varphi(N)} *m \equiv 1*m\equiv m \pmod{N} \]
安全性分析
数学难题-大整数的素数分解
我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解N，这是极难做到的，因为至今为止大整数的素数分解依然是一个难题，所以RSA算法保证了通信安全
语义安全-semantic security
RSA不是一个语义安全的加密算法，所谓语义安全，我们不能从密文中获得任何关于明文的信息，比如一段话的第一个字母，一段话中某个数字出现的次数等等。
拿RSA举例，我们可以很简单的获得m在N上的雅各比符号
基本攻击
我们首先描述一些老的基本攻击，这些攻击说明了RSA的公然滥用情况。虽然存在许多这样的攻击，但我们仅举两个例子。
Common modulus-共模
为了避免为每个用户生成不同的模数\(N=p*q\)，人们可能希望一劳永逸地固定使用一个\(N\)，所有用户都使用相同的\(N\)。可信的中央机构可以向用户提供唯一的一对参数\(<e_i,d_i>\)，用户从其中生成公钥\(<N,e_i>\)和私钥\(<N,d_i>\)。
乍一看，这似乎行得通：为Alice准备的密文\(c = m^{e_a} \pmod{N}\)无法由Bob解密，因为Bob不知道\(d_a\)。但是，这是不正确的，由此产生的系统是不安全的。事实上，Bob可以使用他自己的指数\(<e_b,d_b>\)来分解模数\(N\)。一旦被分解，Bob就可以从她的公钥中计算出Alice的私钥。Simmons的这一观察结果表明，RSA模不应被一个以上的实体使用。
Blinding-盲化
设\(<N,d>\)是Bob的私钥，而\(<N,e>\)是相应的公钥。假设攻击者Marvin想要Bob的签名\(m^d_{Bob} \pmod{N} \in \mathbb{Z^{\ast}_N}\)。当然Bob不傻，他拒绝签署。但是Marvin可以尝试以下方法：他随机选择一个\(r \in \mathbb{Z^{\ast}_N}\)并设\(m' = r^e*m_{Bob}\)。然后他让Bob在随机消息\(m'\)上签名。Bob可能愿意在看上去没什么问题的上签名，但是回想一下\(S'=(m')^d \mod{N}\)，Marvin现在简单地计算\(S = S'/r\)就得到Bob在初始上的签名\(S\)。
事实上： \[ S^e = (S')^e/(r^e)=(M')^{ed}/r^e \equiv M'/r^e = M \pmod{N} \] 这种称为盲化的技术使Marvin能够在他选择的消息上获得有效的签名，方法是让Bob在随机的"盲化"消息上签名。Bob不知道他实际在签名的是什么消息。由于大多数签名方案在签名之前对消息应用"单向散列"算法，因此此种攻击倒不是一个严重的问题。尽管我们将盲化描述为一种攻击，但它实际上是实现匿名数字现金所需的一个有用属性(可以用来购买商品的现金，但不会透露购买者的身份）
Low Private Exponent-低解密指数攻击
理论
解密使用参数d，如果d非常小，那么可以用此方法进行解密。
Theorem 2 (M. Wiener) 令 \(N = pq\) ，这里 \(q < p < 2q\) . 如果$ d < 1/3 N^{1/4}$ 。 给定私钥对\(<N,e>\) ，这里\(e*d = 1 \mod{\varphi(N)}\) , Marvin 可以快速的复原参数 \(d\).
证明详见论文《TWENTY YEARS OF ATTACKS ON THE RSA CRYPTOSYSTEM》
最后给出结论： \[ \left| \cfrac{e} {N} - \cfrac{k} {d} \right| \le \cfrac{1} {dN^{1/4} } < \cfrac{1} {2d^2} \\ 这里k满足：k\varphi(N)-ed=1 \]
这是一个经典的逼近关系，两个分数在约束内非常逼近。首先\(k\varphi(N)-ed=1\),所以\(gcd(k,d)=1\)，即k和d互素，分数\(\cfrac{k} {d}\)是一个最简分数。虽然d很小，但也只是相对于N（1024bits）比较小，实际上d也有上百比特的长度，所以\(\cfrac{1} {2d^2}\)是一个很小的数，由上面的不等式得到\(\cfrac{e} {N}\)是很接近于\(\cfrac{k} {d}\)的。大致的思路就是在\(\cfrac{e}{N}\)附近寻找一个小数，把小数按照分数的形式展开，分母就是我们想要找的参数\(d\)，但实际上并没有这么简单(论文中使用连分数展开)。
由于通常都是1024位，因此\(d\)必须至少256位长才能避免这种攻击。这对于诸如"智能卡"之类的低功耗设备来说是不幸的，因为小就能节省大量能耗。 然而，并不是毫无办法。Wiener提出了许多能够实现快速解密并且不易受其攻击影响的技术
代码
使用python库owiener实现
1 | |
计算得到d的值为
1 | |
计算d的位数大概是254位,符合上面的分析，运算时间也是很快，用python基本秒出答案。
Low Private Exponent-低加密指数攻击
为了减少加密或签名验证时间，习惯上使用一个小的公共指数。 e 的最小可能值为3，但为了击败某些攻击，建议使用\(e = 2^{16} + 1 = 65537\)。当使用65537时，签名验证需要 17 次乘法，而使用随机 \(e < \varphi(N)\) 时大约需要 1000 次乘法。所以对使用小e的攻击连绵不绝。
Coppersmith理论
对低公共指数 RSA 最有效的攻击是基于 Coppersmith的一个定理。 Coppersmith 定理有很多应用，这里只介绍其中的一部分。想要破解RSA，实际上可以看成一个解决函数零点的问题： \[ x^e \equiv c \pmod{N} \] 解出这个函数，就是我们想要做的事情，后面关于多项式环的论述也都是基于这个思想。
前置定理
首先介绍一个理论：
Theorem 3 (Coppersmith) Let N be an integer and \(f \in \mathbb{Z}[x]\) be a monic polynomial of degree d. Set $X = N ^{ {d}- } $ for some \(\epsilon \ge 0\). Then, given $ < N , f > $ Marvin can effciently find all integers $| x_0 | < X $ satisfying $f (x_0 ) = 0 $. The running time is dominated by the time it takes to run the LLL algorithm on a lattice of dimension O (w ) with \(w = min(\frac{1} {\epsilon},log_2N )\).
该定理提供了一种算法，可以有效地找方程\(f(x) \equiv 0 \pmod{N}\) 的所有小于 $X = N^{} $的根
再给出一个引理：
首先我们定义范数的概念，给出多项式\(h(x)=\sum{a_ix^i} \in \mathbb{Z}\),定义范数\(\|h\|^2 = \sum{|a_i|^2}\)
Lemma 4 Let \(h(x) \in \mathbb{Z}\) be a polynomial of degree d and let X be a positive integer. Suppose $|h(xX )| < $ . If \(|x_0| < X\) satisfies \(h(x_0) = 0 \mod{N}\) , then \(h(x_0) = 0\) holds over the integers.
这个引理告诉我们：如果满足前置条件，\(f(x) \equiv 0 \pmod{N}\)的根，也是\(f(x)=0\)在整数域上的根，但实际上函数\(f(x)\)一般都没有这么小的范数能满足前置条件。我们可以构造一个函数\(h(x)=g(x)*f(x)\)，这个函数\(h(x)\)应该有比较小的范数来满足前置条件。这相当于一个问题，找到\(f(x),xf(x),x^2f(x),\dots,x^rf(x)\)的一个线性组合，这个线性组合就是函数\(h(x)\)，且有较低的范数。
解决方案
前面我们介绍过，想要找到函数\(h(x)\)，实际上就是找一个线性组合，Dan Boneh在论文中叙述了一个基于格中LLL算法的解决方案。大家可以细看论文(作者关于格的理论已经忘得差不多了)，以后咱再补充。
Hastad广播攻击
所谓广播，就是一个人把消息发给很多人，这里我们假设假设 Bob 希望将加密消息 M 发送给多个参与方 $P_1, P_2, ,P_K $。每一方都有自己的 RSA 密钥 \(pk=<N_i,e_i>\) 。我们假设 M 小于所有的\(N_i\) ，即\(M<min(N_1,N2, \dots , N_K)\)。为了发送 M，天真的Bob 使用每个公钥对其进行加密，并将第 i 个密文发送给 第i个参与方\(P_i\)。攻击者 Marvin 可以在 Bob 视线之外窃听连接并收集 k 个被传输的密文。
为了便于大家理解，我们举一个例子来说明：
我们假定所有公共指数\(e_i=3\)，如果参与方的个数\(K \ge 3\)那么marvin可以破解出明文M，事实上破解只需解下面一个方程即可： \[ \begin{equation} \begin{cases} C_1 \equiv M^3 \mod{N_1}\\ C_2 \equiv M^3 \mod{N_2}\\ C_3 \equiv M^3 \mod{N_3} \end{cases} \end{equation} \] 这里假定\(gcd(N_i,N_j)=1\)，即任意两个N之间互素，否则我们可以用\(N_i/N_j\)很简单的求出他们的公因子，从而复原出\(p和q\)，这个假定是有意义的。对于上面的方程，我们使用中国剩余定理(CRT)解出结果即为明文。