RSA的攻与防（一）
RSA加密算法是一种非对称加密算法，1977年由麻省理工学院的三位密码学家和计算机科学家共同发明。RSA公钥加密算法和加密系统提供了数据保密和签名验证功能，在互联网中得到广泛使用。从诞生时起，RSA就开始成为现代密码学的一个主要研究对象。许多密码分析学家和信息安全专家一直在研究其可能的理论缺陷和技术漏洞，以保障实际应用中的安全性和可靠性。
幸运的是，历经40多年的广泛研究和现实应用的考验，虽然发现了不少精巧的攻击手段，总体上RSA是安全的。这些攻击手段都是利用RSA的不当使用或软硬件实现中脆弱性，并不能动摇其加密算法的安全性根基。另一方面，对这些攻击手段的研究表明，实现一个安全而牢固的RSA应用并不是一个简单的任务。实际上，密码学和网络安全软硬件工程实践中的一个共识就是：不要试图从头开始实现RSA！1 恰当的方案，是使用现有的、久经测试并有可靠维护的库或API，去实现RSA算法和协议的应用。
这里将常见的攻击RSA的手段、攻击所基于的数学机理和相应的防护措施做一个简要的调研。参考前文，开始我们先复习一下RSA的工作机制和流程：
- 选择两个大的素数 \(p\) 和 \(q\)，计算 \(N=pq\)
- 计算 \(N\) 的卡迈克尔函数 \(\lambda(N)\)
- 当 \(p\) 和 \(q\) 都为素数时，通常 \(\lambda(pq)=\mathrm{lcm}(p − 1, q − 1)\)
- \(\mathrm{lcm}\) 是求最小公倍数的函数，可以用欧几里得算法得出
- 选择一个小于 \(\lambda(N)\) 且与之互素的数 \(e\)，并求得 \(e\) 关于 \(\lambda(N)\) 的模逆元 \(d\equiv e^{-1}\pmod {\lambda(N)}\)
- 模逆元的定义是，找到 \(d\) 使得 \((d⋅e)\bmod\lambda(N)=1\)
- 模逆元可以用扩展的欧几里得算法得出
- \(\pmb{(N,e)}\) 是公钥，\(\pmb{(N,d)}\) 是私钥
- 公钥公开，私钥必须密藏
- 销毁所有 \(p,q,\lambda(N)\) 的记录
- 发送方先按照双方约定好的编码格式将消息转化为一个小于\(N\)的正整数\(m\)，然后使用接收方的公钥计算出密文\(c\)，计算公式是 \(\pmb{c\equiv m^e\pmod N}\)
- 接收方收到密文后，使用自己的私钥计算出明文\(m\)，计算公式是 \(\pmb{m\equiv c^d\pmod N}\)，然后解码成原始消息
- 使用私钥加密的消息也可以由公钥解密，即如果 \(\pmb{s\equiv m^d\pmod N}\)，则 \(\pmb{m\equiv s^e\pmod N}\)。这就是所支持的数字签名功能
注意，原始的RSA论文里第二步和第三步采用 \(N\) 的欧拉函数 \(\varphi(N)\)。这两个函数之间的关系是： \[\varphi(N)=\lambda(N)⋅\mathrm{gcd}(p-1,q-1)\] 这里 \(\mathrm{gcd}\) 为最大公约数函数。使用 \(\lambda(N)\) 可以求得最小可用的私钥指数 \(d\)，有利于高效的解密和签名运算。无论是使用欧拉函数还是卡迈克尔函数，遵循以上流程的实现常常被称为“教科书RSA”。
教科书RSA是不安全的，有许多简单而有效的攻击手段。在详细讨论教科书RSA的安全漏洞之前，有必要审视一下人所共知的首要攻击方法 — 大数分解！
大数分解
RSA加密算法安全性的理论基石，就是大数素因数分解问题。如果能从已知的\(N\)里面分离出 \(p\) 和 \(q\)，就可以马上推导出私钥指数\(d\)，从而完全破解RSA。大数分解是公认的计算难题，已知最好的渐近线运行时间算法是普通数域筛选法 (General Number Field Sieve，简写GNFS)，其时间复杂度是\({\displaystyle \exp \left(\left(c+o(1)\right)(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}\right)}\)，这里常数 \(c = 4/\sqrt[3]{9}\)，\(\displaystyle \exp\)为自然常数 (2.718) 的幂函数。
对于给定的大数，精确地估计应用GNFS算法的实际复杂度是困难的。但是依据启发式的复杂性经验估计，我们可以粗略看出计算时间复杂性的增长趋势：
- 对于1024比特的大数，有两个各约500比特的素因数，分解需要 \(2^{70}\) 数量级的基本运算操作
- 对于2048比特的大数，有两个各约1000比特的素因数，分解需要 \(2^{90}\) 数量级的基本运算操作，比1024比特数慢一百万倍
计算机软硬件技术的飞速发展，让许多过去看似不可能的任务成为现实。查询RSA大数分解挑战网站公布的最新纪录，2020二月法国计算数学家保罗·齐默尔曼 (Paul Zimmermann) 领导的团队成功分解了250位十进制数字 (829比特) 的大数 RSA-250：
1 | RSA-250 = 6413528947707158027879019017057738908482501474294344720811685963202453234463 |
齐默尔曼发布的通告表示，以英特尔 Xeon Gold 6130 主频 2.1GHz 的处理器为参照，完成这一任务总的计算时间约为2700处理器核年 (core-year)。这一数字好像很大，但在当今集群计算、网格计算和云计算普及到大众的时代，拥有强大财力支持的组织机构将计算时间缩减到以小时乃至分钟计并非天方夜谭。作为例子，去免费开源数学软件系统 SageMath 的在线工具网站，输入以下前5行Sage Python代码：
1 | p=random_prime(2**120) |
在几分钟之内就得到了结果，一个72位十进制数字 (240比特) 的大数被分解出来了。要知道，在1977年的RSA论文里，提到分解一个75位十进制数字大约需要104天。人类的技术进步是如此惊人！
当攻方的矛越来越锋利时，守方的盾就必须越来越厚重。所以，1024比特RSA已经不安全，应用系统不应该使用少于2048比特的公钥 \(N\)值。而当需要高安全性时，选择4096比特RSA。
初级攻击
虽然大数分解是所有人都知道的攻击方方式，但是在RSA的应用中常见的一些低级错误所造成的安全漏洞，使得使用简单的攻击手段就可以得逞，下面对一些典型的初级攻击方式加以说明。
在RSA的发展初期，基于当时计算能力的落后，找寻大的素数需要不少时间。因此，一些系统实现试图共用模数\(N\)。想法是只生成一组\((p,q)\)，然后所有的用户使用同样的\(N=pq\)值，由大家都信任的中心机构为每个用户 \(i\) 分配密钥对\((e_i,d_i)\)，只要各自的私钥 \(d_i\)保存好就不会出问题。很不幸，这是一个灾难性的错误！这种实现方案有两个巨大的安全漏洞：
用户 \(i\) 可以用自己的密钥对\((e_i,d_i)\)分解出\(N\)。无论\(d\)是使用欧拉函数\(\varphi(N)\)还是卡迈克尔函数\(\lambda(N)\)生成的，都有很快地从给定的\(d\)推导出素因数\(p\)和\(q\)的算法2。而一旦知晓了\(p\)和\(q\)，用户 \(i\) 可以用任何其他用户的公钥\((N,e_j)\)计算出其私钥\(d_j\)。至此，所有其他用户对用户 \(i\) 毫无秘密可言。
即使所有用户都没有知识和技能去分解\(N\)，或者“好心”地不去了解其他用户的私钥，黑客还是可以实施共模攻击破解用户的消息。设定两个用户爱丽丝和鲍勃的公钥分别为\(e_1\)和\(e_2\)，而且\(e_1\)和\(e_2\)恰好互素 (这是非常可能的)，那么根据裴蜀定理 (Bézout's identity)，窃听者伊芙可以找到 \(s\) 和 \(t\) 满足：\[e_{1}s+e_{2}t=\mathrm{gcd}(e_1,e_2)=1\]这时如果有人给爱丽丝和鲍勃发出同样的消息\(m\)，伊芙记录两段密文\(c_1\)和\(c_2\)后，执行下面的运算就可以解密出\(m\)：\[c_1^s⋅c_2^t\equiv(m^{e_1})^s⋅(m^{e_2})^t\equiv m^{e_{1}s+e_{2}t}\equiv m\pmod N\]对应的Python函数代码如下：
这里调用了gmpy23两个库函数：gcdext()实现扩展的欧几里得算法，invert()求模逆元。注意，Python的指数函数pow()支持模幂运算，但是指数不可为负数。因为\(s\)或\(t\)必然有一个为负数，所以要先调用invert()将\(c_1\)或\(c_2\)转化为对应的模逆元，再将负数取反求模幂。比如上面第7、8行就实现了\(c_1^s=(c_1^{-1})^{-s}\bmod N\)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def common_modulus(e1, e2, N, c1, c2):
# 调用扩展的欧几里得算法函数
g, s, t = gymp2.gcdext(e1, e2)
assert g == 1
if s < 0:
# 求c1的模逆元
re = int(gmpy2.invert(c1, N))
c1 = pow(re, s*(-1), N)
c2 = pow(c2, t, N)
else:
# t为负数, 求c2的模逆元
re = int(gmpy2.invert(c2, N))
c2 = pow(re, t*(-1), N)
c1 = pow(c1, a, N)
return (c1*c2) % N
共用模数\(N\)被证明是不安全的，那么只重复使用\(p\)或\(q\)可以吗？这样似乎避免了共模攻击又保证每个用户的公钥\(N\)值唯一。大错特错了！这是一个更糟糕的主意！攻击者拿到所有用户的公开\(N\)值，只要两两组合\((N_1,N_2)\)执行欧几里得算法 (辗转相除法) 求解最大公约数，求解成功就得到一个素因数\(p\)，再简单地用除法就得出另一个素因数\(q\)。有了\(p\)和\(q\)，攻击者就可以马上算出用户的私钥\(d\)。这就是模不互素攻击。
应用教科书RSA时，如果公钥指数\(e\)和明文\(m\)都很小，乃至\(c=m^e<N\)，直接对密文\(c\)开\(e\)次方即可得到明文\(m\)。即使\(m^e>N\)但不是足够大，则因为 \(m^e=c+k⋅N\)，可以循环尝试小的\(k\)值进行暴力开方破解。下面是Python例程：
这里调用了gmpy2库函数iroot()，以求得\(e\)次方根。1
2
3
4
5
6
7
8
9
10def crack_small(c, e, N, repeat)
times = 0
msg = 0
for k in range(repeat):
m, is_exact = gmpy2.iroot(c + times, e)
if is_exact and pow(m, e, N) == c:
msg = int(m)
break
times += N
return msg教科书RSA是确定性的，意即同样的明文\(m\)总是生成同样的密文\(c\)。这就使密码本攻击成为可能：攻击者预先计算出全部或部分的 \(m\to c\) 对照表保存，然后搜索截获的密文匹配即可。确定性也意味着教科书RSA不是语义安全的，密文会泄露明文的某些信息。密文重复出现，表明发送方在重复发送相同的消息。
教科书RSA具有延展性 (malleable)，对密文进行特定形式的代数运算，结果会反映到解密的明文中。比如有两段明文 \(m_1\)和 \(m_2\)，加密后产生 \(c_1=m_1^e\bmod N\) 和 \(c_2=m_2^e\bmod N\)，那么 \((c_1⋅c_2)\) 解密会得到什么？看如下等式： \[(c_1⋅c_2)^d\equiv m_1^{ed}⋅m_2^{ed}\equiv m_1⋅m_2\pmod N\] 所以两段密文的乘积解密后得到的明文，等于两段明文的乘积。这一特性对一般的RSA加密系统是有害的，它为选择密文攻击 (chosen-ciphertext attack) 提供了机会。下面举例两种攻击场景：
设想有一个RSA解密机可以用内部保存的私钥\((N,d)\)解密消息。基于安全考虑，解密机会拒绝同样的密文重复输入。攻击者马文发现一段密文\(c\)，直接输入到解密机被拒绝，因为密文\(c\)以前被解密过。马文找到一种办法破解。他自己准备一段明文\(r\)，用公钥\((N,e)\)加密生成新的密文\(c'={r^e}c\bmod N\)，然后将密文\(c'\)输入到解密机。解密机没有解过这一段新的密文，所以不会拒绝。解密的结果是\[m'\equiv (c')^d\equiv r^{ed}c^d\equiv rm\pmod N\]现在马文有了\(m'\)，他用公式 \(m\equiv m'r^{-1}\pmod N\)就可以计算出\(m\)。
假设马文想让鲍勃在一段消息\(m\)上签名，但是鲍勃在看过消息内容后拒绝了。马文可以使用称为盲签名4的攻击手段可以达成他的目标。他挑选一段随机的消息\(r\)，生成 \(m'={r^e}m\bmod N\)，然后把\(m'\)拿给鲍勃签名。鲍勃可能觉得\(m'\)无关紧要，就签了。鲍勃签名的结果是 \(s'=(m')^d\bmod N\)。现在马文用公式 \(s=s'r^{-1}\bmod N\) 就拿到了鲍勃对原来消息\(m\)的签名。为什么？原因是\[s^e\equiv (s')^er^{-e}\equiv (m')^{ed}r^{-e}\equiv m'r^{-e}\equiv m\pmod N\]
以上这些绝非完整的初级攻击方法清单，但已经可以说明问题了。在实际RSA应用中，我们必须非常小心，应该做到：
- 单独给每个用户生成唯一的公钥模数\(N\)，防止共模攻击
- 不可重复使用素因数生成公钥模数\(N\)，杜绝模不互素攻击
对于教科书RSA的确定性和延展性缺陷，及可能的暴力开方破解漏洞，可采用随机元素填充 (padding with random elements) 方法防护，其机理是：
- 填充可确保被加密的消息数值比特数接近\(N\)，同时不使用小的\(e\)值，让暴力开方破解失效
- 随机填充使得同样的明文产生不一样的密文，保障语义安全性，使得密码本攻击成为不可能
- 随机填充也能防止共模攻击，因为被加密的消息不同，依据裴蜀定理的攻击无效
- 严格格式定义的填充破坏了延展性，降低了选择密文攻击可能性。比如填充后开头几个字节必须为给定值，那对相应的密文进行代数运算后，解密出的数据极大可能不符合预定的格式，这就瓦解了选择密文攻击
低公钥指数攻击
使用小的公钥指数是危险的，在不填充或不当填充的情况下，即使暴力开方破解不能成功，也还有一些高级的攻击手段。
广播攻击
由瑞典理论计算科学家约翰·霍斯塔德5发现，因此也被称为霍斯塔德广播攻击。考虑这样一种简化的场景，假设爱丽丝需要发送同一条消息\(m\)给鲍伯、卡罗尔和戴夫。三位接收者的公钥分别为\((N_1,3)\)、\((N_2,3)\)和\((N_3,3)\)，即公钥指数都为3，公钥模数各不相同。消息不填充，爱丽丝直接用其他三人的公钥加密并发出三段密文\(c_1,c_2,c_3\)： \[\begin{cases} c_1=m^3\bmod N_1\\ c_2=m^3\bmod N_2\\ c_3=m^3\bmod N_3 \end{cases}\] 这时伊芙偷偷记下三段密文，标记\(M=m^3\)，如果她可以恢复\(M\)，开三次方根自然就得到明文\(m\)。显然这里共模攻击不成立，我们也可以假设模数两两互素，否则使用模不互素攻击分解模数就可以了。那么伊芙有办法算出\(M\)吗？答案是肯定的。
实际上，这里求解\(M\)的等同问题是：已知某个数分别除以三个数的余数，而且这三个数两两互素，有没有有效的算法解出这个数？这个有效的算法就是中国余数定理！
中国余数定理给出了一元线性同余方程组有解的准则以及求解方法。对于以下的一元线性同余方程组 (注意不要与上面描述攻击场景的数学符号混淆)： \[(S) : \quad \left\{ \begin{matrix} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \vdots \qquad\qquad\qquad \\ x \equiv a_n \pmod {m_n} \end {matrix} \right.\] 假设整数\(m_1,m_2,\ldots,m_n\)其中任两数互素，则对任意的整数\(a_1,a_2,\ldots,a_n\)，方程组\((S)\)有解，并且通解可以用如下四步构造： \[\begin{align} M &= m_1 \times m_2 \times \cdots \times m_n = \prod_{i=1}^n m_i \tag{1}\label{eq1}\\ M_i &= M/m_i, \; \; \forall i \in \{1, 2, \cdots , n\}\tag{2}\label{eq2}\\ t_i M_i &\equiv 1\pmod {m_i}, \; \; \forall i \in \{1, 2, \cdots , n\}\tag{3}\label{eq3}\\ x &=kM+\sum_{i=1}^n a_i t_i M_i\tag{4}\label{eq4} \end{align}\] 以上最后一行 (4) 式给出了方程组的通解形式。在模\(M\)的意义下，唯一解为 \(\sum_{i=1}^n a_i t_i M_i \bmod M\)。
试试用中国剩余定理解出本文开头的“物不知其数”问题
首先将变量符号与数值对应： \[m_1=3,a_1=2;\quad m_2=5,a_2=3;\quad m_3=7,a_3=2\] 然后算出\(M=3\times5\times7=105\)，进而推导出： \[\begin{align} M_1 &=M/m_1=105/3=35,\quad t_1=35^{-1}\bmod 3 = 2\\ M_2 &=M/m_2=105/5=21,\quad t_2=21^{-1}\bmod 5 = 1\\ M_3 &=M/m_3=105/7=15,\quad t_3=15^{-1}\bmod 7 = 1\\ \end{align}\] 最后带入通解公式： \[x=k⋅105+(2⋅35⋅2+3⋅21⋅1+2⋅15⋅1)=k⋅105+233\] 所以在模105内的最小正整数解为 \(233\bmod 105=23\)。
明朝数学家程大位在《算法统宗》中，将宋朝数学家秦九韶记载在《数书九章》中的解法编成易于上口的《孙子歌诀》：三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知。
这里我们必须佩服中国古人的智慧，在没有现代数学符号系统的条件下，能够推导总结出如此巧妙的解法，为人类贡献了一个重要的数学定理。
所以伊芙只要套用中国余数定理的解法，算出\(M\)，然后求得其立方根就得到了明文\(m\)，攻击成功。更一般地，设定接收者的数目为\(k\)，如果全部接收者使用同样的\(e\)，那么只要\(k\ge e\)，这种广播攻击都是可行的。
霍斯塔德还进一步证明，即便使用填充来预防广播攻击，如果填充方案产生的消息相互之间有线性关系，比如用公式\(m_i=i2^b+m\) (\(b\)为\(m\)的比特数)生成发给接收者 \(i\) 的消息，那么只要\(k>e\)，广播攻击仍然可以恢复明文\(m\)。这种情况下的广播攻击还是基于中国余数定理，但具体的破解方法有赖于线性关系的信息。
总结以上的分析，为了避免广播攻击，我们必须使用大一些的公钥指数\(e\)，同时应用随机填充。现在通用的公钥指数\(e\)为65537 (\(2^{16}+1\))，可以兼顾消息加密或签名验证运算的效率和安全性。
最后，给出仿真广播攻击的Python例程：
1 | def solve_crt(ai: list, mi: list): |
程序使用了两种方法仿真广播攻击。一种调用通用的中国余数定理求解函数solve_crt()，再将结果开立方根；另一种调用专门的针对公钥指数\(e=3\)的广播攻击函数rsa_broadcast_attack()，直接输出破解的明文数值。这两个函数内部实现都是基于中国余数定理的通解公式，输出结果应该完全一致。破解的明文数值再输入到uint_to_bytes()函数，转换成字节数组与原文quote比较。注意，程序中使用了RSA类生成的对象模拟接收者鲍伯、卡罗尔和戴夫，鉴于篇幅所限RSA类的实现代码这里省略了。
下篇：RSA的攻与防（二）
美国计算机科学家和安全技术专家加里·麦格劳（Gary McGraw）对软件开发者的一句著名忠告是 “never roll your own cryptography”↩︎
RSA原始论文（第IX节C部分）就提到了由已知 \(d\) 分解 \(N\)的米勒算法。这一算法同样适用于由卡迈克尔函数\(\lambda(N)\)生成的 \(d\)。↩︎
gmpy2是一个用C语言写的Python扩展模块，支持多精度算术。↩︎
在一些特殊情况下，盲签名可用来有效地保护隐私。比如电子选举和数字现金应用中，签名者和消息作者可以是不同的。↩︎
约翰·霍斯塔德（Johan Håstad），瑞典理论计算科学家，皇家理工学院教授，美国数学学会（AMS）和计算机协会（ACM）双会士。↩︎