Attack on RSA with Low Public Exponent

作者简介：Xor0v0，硕士在读，零知识证明小白，目前在做一些circom开发和zk审计，密码学爱好者，打过一些web2/3 CTF，最近对zkHACK产生兴趣。欢迎各位大佬一起交流学习。

RSA 公钥加密系统自1977年被提出至今，目前仍然在很多领域被广泛使用，许多研究人员致力于找到其安全漏洞来攻克它。

在此期间，很多高明的攻击方法被提出。但至少在目前（2024初），在保证选取足够安全的加密参数情况下，RSA的加密强度仍然是现代电脑无法攻破的。

本小节，我们介绍其中一种高明的攻击方法，它源于 Hastad ，后由 Coppersmith 改良，当 RSA 使用一个小公共指数 $r$ 时，攻击容易被实现。攻击思路基于找到低次多项式的一个小的根的算法，这个算法又需要使用 LLL 算法。这种寻找根的算法本身非常有意思，也用于其他攻击 RSA 系统的算法中。

1. RSA Review

让我们回顾一下 RSA 最简单的加密版本，同时也最能体现密码学和数学的高明之处的加密算法。该算法基于大数分解难题假设。

令 $N=pq$， 其中 $p,q$ 是同等规模的大质数。令 $r,s$ 是满足 $rs\equiv 1(\mathrm{mod}\phi (N))$ ，其中 $\phi (N)=(p-1)(q-1)$ 是乘法群 ${\mathbb{Z}}_N^{\ast }$ 的阶。

我们称 $N$ 为 RSA 模数， $r$ 为公共指数。 $(N,r)$ 对是公钥，用于加密信息。 $(N,s)$ 对是私钥，只有拥有私钥的人才能解密信息。给定要加密的信息为整数 $m\in {\mathbb{Z}}_N^{\ast }$，为了对 $m$ 加密，需要计算 $c\equiv m^r(\mathrm{mod}N)$ 。为了对 $c$ 解密，需要计算 $m\equiv c^s(\mathrm{mod}N)$ 。算法的正确性可由欧拉定理证明。

2. Low Public Exponent RSA

在许多实际应用场景中，加密过程是在算力受限设备上进行的，因此将 $m$ 计算到高次是非常消耗电量、时间的。因此有人尝试简化加密过程，把公共指数 $r$ 设置为很小的数，比如 $r=3$。如此一来，加密过程简化很多，只需要计算 $m^3$ ，使用两次乘法即可。

乍一看，在不知道 $N$ 的因数分解的情况下，好像没办法恢复出密文。然而，正如本文所要介绍的，存在一些高明的攻击手段。

首先我们回顾一下中国剩余定理（CRT）：给定 $b$ 个等式 $x\equiv a_i(\mathrm{mod}{p}_i)$ ，其中 $p_i$ 互素。则存在唯一的 $x(\mathrm{mod}{p}_1\cdot p_2\dots p_r)$ ，并且可以高效的找到这个 $x$ 。

回到低指数加密场景中，假设 A 现在要发送 B、C、D 同样的信息 $m$ ，用各自的公钥分别加密，为： $c_B\equiv m^3(\mathrm{mod}{N}_B),c_C\equiv m^3(\mathrm{mod}{N}_C),c_D\equiv m^3(\mathrm{mod}{N}_D)$ 。那么这种情况下，可以很容易恢复明文 $m$ 。

不失一般性，我们假设这三个模数都是互素的（如果不互素，则可以找到公因子，然后直接恢复明文），攻击者可以由中国剩余定理计算一个值 $x\equiv m^3(\mathrm{mod}{N}_B\cdot N_C\cdot N_D)$ 。由于 $m<N_B,N_C,N_D$ 成立，则 $m^3<N_B{N}_C{N}_D$ 成立。那么我们计算的 $x=m^3$，最后我们对 $x$ 开三次方即可。

上述攻击成功的前提是若干次加密都是使用同样的明文，那么如果给每个人发送的消息都不一样呢？考虑如下解决方案：每个人除了公私钥，还有一个唯一的 ID 号，现在 A 对 B、C、D 发送的加密消息变更为： $c_B\equiv (m+2^{k}I{D}_B{)}^3(\mathrm{mod}{N}_B),c_C\equiv (m+2^{k}I{D}_C{)}^3(\mathrm{mod}{N}_C),c_D\equiv (m+2^{k}I{D}_D{)}^3(\mathrm{mod}{N}_D)$ 。其中 $k$ 是消息 $m$ 的比特长度。这种方式下，攻击者就不能通过上述中国剩余定理进行攻击了。

3. Coppersmith’ Method

事实上，对于上述修改方案，我们可以采用一个更一般的攻击方法，这需要使用到 Coppersmith’ Method。

Coppersmith’ Method的作用：设存在一个模多项式 $F(x)\equiv x^3+x+123(\mathrm{mod}M)$ 。如果该模多项式的根为 $x_0$ ，即 $F(x_0)\equiv 0(\mathrm{mod}M)$ ，且根足够小。那么就可以用 Coppersmith’ Method 去找这个小根。

首先，如果知道 $M$ 的因式分解，那么这个问题是容易解决的，只需要分别在素因子的子群下解模多项式，然后用一个中国剩余定理即可。另外，如果我们能够找到一个解满足 $x^2\equiv q(\mathrm{mod}M)$ ，并且这个 $x$ 不等于 $\pm 1(\mathrm{mod}M)$ ，那么可以用欧几里得算法将模数分解。因此，我们不寄希望于有一个有效算法对于所有这样的同余式都能找到解，否则也就意味着大数分解难题可以破解了。

既然不能对所有的模多项式都能找到解，那么找到解的条件是什么呢？结论是：对于次数（degree）为 $d$ 的多项式 $F(x)$ ，如果 $x_0$ 满足 $F(x_0)\equiv 0(\mathrm{mod}M)$ 且 $|x_0|<\frac{1}{2}{M}^{\frac{1}{d}-ϵ}$ ，那么这个解可以在多项式时间内找到。

First step

不失一般性，设 $d$ 模 $M$ 多项式为首一多项式： $F(x)\equiv x^d+a_{d-1}{x}^{d-1}+\cdots +a_0(\mathrm{mod}M)$ （得到首一多项式很简单，只需要对多项式乘以 $a_d^{-1}(\mathrm{mod}M)$。而如果 $a_d^{-1}(\mathrm{mod}M)$ 不存在，则我们找到了 $M$ 的一个因子，这个同余式可以拆成同余式组，使用中国剩余定理即可）。假设存在一个整数 $x_0$ 满足 $F(x_0)\equiv 0(\mathrm{mod}M)$ 且 $|x_0|<M^{\frac{1}{d}}$ ，我们的任务就是找到这个 $x_0$ 。

我们想：如果存在另一个多项式 $G(x)$ 的根也是 $x_0$ ，且它的系数很小，那我们就可以通过求根公式或者牛顿迭代法将 $x_0$ 求出。而Coppersmith’ Method 算法核心思路就是把 $F(x)$ 通过一系列变换规约成 $G(x)$。【注意 $G(x)$ 不是模多项式】

Example 1

设 $M=17\ast 19=323,F(x)=x^3+33x+215$，我们想找到一个小根满足 $F(x)\equiv 0(\mathrm{mod}M)$ 。【这里 $x_0=3$，但在整数域下 $F(3)\ne 0$】

我们可以找到 $G(x)=9F(x)-M\cdot (x+6)=9x^2-26x-3$ 满足 $G(3)=0$ ，这个解可以用求根公式得到。

ok，这就是 Coppersmith’ Method 的核心思想。

接下来是讨论 $x_0$ 的界的问题（多小的根算小根？）以及提高界的手法。

我们定义 $X$ 为这个 $|x_0|$ 的上界，然后我们把 $F(X)$ 用向量的形式表示： $b_F=(a_0,a_{1}X,\dots ,a_d{X}^d)$

Howgrave-Gramham 定理

给定模多项式 $F(x)$，模数为 $M$，根的上界为 $X$ ， $F(X)$ 的向量表示为 $b_F$ ，满足 $F(x_0)\equiv 0(\mathrm{mod}M)$ 。那么，当 $||b_F||<\frac{M}{\sqrt{d+1}}$ 时，有 $F(x_0)=0$ 。

Proof:

根据柯西不等式有： $({\sum }_{i=1}^n{x}_i{y}_i{)}^2\le ({\sum }_{i=1}^n{x}_i^2)({\sum }_{i=1}^n{y}_i^2)$ ，当 $y_i=1,x_i\ge 0,1\le i\le n$ 时，柯西不等式变形为： ${\sum }_{i=1}^n{x}_i\le \sqrt{n{\sum }_{i=1}^n{x}_i^2}=\sqrt{n}||(x_1,\dots ,x_n)||$ 。

我们首先把 $F(x_0)$ 表示为 ${\sum }_{i=0}^d{a}_i{x}_0^i$ ，可得到不等式： $|F(x_0)|=|{\sum }_{i=0}^d{a}_i{x}_0^i|\le {\sum }_{i=0}^d|a_i||x_0{|}^i$ 。

把 $x_0$ 的上界代入有： $|F(x_0)|\le {\sum }_{i=0}^d|a_i||x_0{|}^i\le {\sum }_{i=0}^d|a_i||X{|}^i$ 。

根据之前柯西不等式的变形有：

$$\sum _{i=0}^d|a_i||x_0{|}^i\le \sum _{i=0}^d|a_i||X{|}^i\le \sqrt{d+1}||b_F||$$

因此当 $||b_F||<\frac{M}{\sqrt{d+1}}$ 时，有 $|F(x_0)|<M$ 。

于是有： $-M<F(x_0)<M$ 。又因为： $F(x_0)\equiv 0(\mathrm{mod}M)$ ，因此 $F(x_0)=0$。

这个定理（简称 HG 定理）对于估计根的界非常重要！！

之前 example 1 中 $G(x)$ 是直接给出的，下面介绍一下 G(x) 到底该怎么找？首先考虑 $d$ 个多项式 $G_i(x)=M{x}^i(0\le i<d)$ ，还有 $F(x)$ 。显然它们均有解 $x=x_0(\mathrm{mod}M)$ ，因此我们对其进行线性组合之后它们仍然有解 $x=x_0(\mathrm{mod}M)$ 。

谈到线性组合，那么就很容易联想到矩阵，我们讲这些式子的系数向量组合写成矩阵：

$$L=\left(\begin{array}{ccccc}M& 0& \dots & 0& 0\\ 0& mX& \dots & 0& 0\\ ⋮& ⋮& \ddots & \dots & \dots \\ 0& 0& \dots & M{X}^{d-1}& 0\\ a_0& a_{1}X& \dots & a_{d-1}{X}^{d-1}& X^d\end{array}\right)$$

其中 $X$ 是 $x_0$ 取值的上界。

由于是下三角矩阵，则矩阵的行列式为： $\det L=M^d{X}^{d(d+1)/2}$ 。

我们对这个矩阵利用 LLL 算法进行格基规约，设规约后的第一行行向量为： $b^{\prime }$ 。根据 LLL 算法第一个性质有： $b^{\prime }$ 满足 $||b^{\prime }||\le 2^{\frac{n-1}{4}}\det (L{)}^{\frac{1}{n}}$ 。因此 $||b^{\prime }||\le 2^{\frac{d}{4}}{M}^{\frac{d}{d+1}}{X}^{\frac{d}{2}}$ 。

为了满足 HG 定理，使得规约之后的向量（ $G(x)$ 的系数）“足够小”，使得我们可以很快的求出根，故要求 $2^{\frac{d}{4}}{M}^{\frac{d}{d+1}}{X}^{\frac{d}{2}}<\frac{M}{\sqrt{d+1}}$ ，移项之后有： $2^{\frac{d}{4}}\sqrt{d+1}{X}^{\frac{d}{2}}<M^{\frac{1}{d+1}}$ 。如果 $d=2$ ，则 $X\approx M^{1/3}$ ；如果 $d=3$ ，则 $X\approx M^{1/6}$ 。

至此我们大致有了 $X$ 的取值范围，但还没达到前面给出的结论 $M^{\frac{1}{d}-ϵ}$ 的程度。因此格子还有继续优化的空间。

Example 2

设 $M=10001$ ，多项式 $F(x)=x^3+10x^2+5000x-222$ 。【这里根 $x_0=4$ ，因此满足 $x_0<M^{\frac{1}{6}}$】

这里我们初步构想 $X=10$ ，则构造格子：

$$L=\left(\begin{array}{cccc}M& 0& 0& 0\\ 0& MX& 0& 0\\ 0& 0& M{X}^2& 0\\ -222& 5000X& 10X^2& X^3\end{array}\right)$$

利用 LLL 格基规约之后，我们得到第一行向量为： $(444,10,-2000,-2000)$ ，消去 $X$ 我们得到最终的系数 $(444,1,-20,-2)$ ，在对这个多项式采用牛顿迭代法求根即可。

from sage.rings.polynomial.refine_root import refine_root
M = 10001
X = 10
L = matrix(ZZ, 4, 4)
for i in range(3):
    L[i, i] = M * X ^ i
L[3, 0] = -222
L[3, 1] = 50000
L[3, 2] = 1000
L[3, 3] = 1000

v = L.LLL()[0]
# print(v)

p = 0
x = polygen(ZZ)
for i, coef in enumerate(v):
    p += (coef / X ^ i) * x ^ i
    
ans = p.roots()
# [(4, 1)]

最终得到的结果就是我们预想的 $x_0=4$ 。

Full Coppersmith Method

回顾一下 Example 2，即使以 $M^{\frac{1}{6}}$ 来计算边界，那么应该在 $4.3$ 左右，那么为什么我们取 $X=10$ 也能计算出正确结果？而且，如果把 $d=3$ 代入 $2^{\frac{d}{4}}\sqrt{d+1}{X}^{\frac{d}{2}}<M^{\frac{1}{d+1}}$ ，那么 X 的边界值应该在 $2.07$ 左右。所以为什么我们能得到正确结果呢？

因为其实这个边界值也并不是很严格，在推导得出这个值的时候本身就用了很多次不等式，再者，我们利用的LLL中的那个性质，我们取的是 LLL 算法规约出来的最坏的情况，而大多数情况得到的结果要比这值小许多。

回到不等式： $2^{\frac{d}{4}}{M}^{\frac{d}{d+1}}{X}^{\frac{d}{2}}<\frac{M}{\sqrt{d+1}}$ ，再往前还原是： $2^{\frac{n-1}{4}}{M}^{\frac{d}{n}}{X}^{\frac{d}{2}}<\frac{M}{\sqrt{n}}$ ，其中 $n$ 是格的维度。

观察这个不等式，我们发现，要增大 $X$ ，有两种方案：1. 增大 $n$ ；2. 增大 $M$ 。

针对第一种方案，我们称往格里增加的格的维度，而不增加 $M$ 的多项式为 x-shift polynomial。它们是 $xF(x),x^{2}F(x),\dots$ 。显然这些多项式的解都为 $x_0$ 。

第二种方案，可以增加 $F(x)$ 的幂次来增加 $M$ 。由于 $F(x_0)\equiv 0(\mathrm{mod}M)$ ，则有 $F^k(x_0)\equiv 0(\mathrm{mod}{M}^k)$ 。

在 Example 2 中，我们的格子的维度为 $n=4$ ，我们带入不等式 $2^{\frac{n-1}{4}}{M}^{\frac{d}{n}}{X}^{\frac{d}{2}}<\frac{M}{\sqrt{n}}$，得到 $X\approx 2/07$ 。现在我们往格子里添加 x-shift polynomials ，新的格子为：

$$L=\left(\begin{array}{cccccc}M& 0& 0& 0& 0& 0\\ 0& MX& 0& 0& 0& 0\\ 0& 0& M{X}^2& 0& 0& 0\\ -222& 5000X& 10X^2& X^3& 0& 0\\ 0& -222X& 5000X^2& 10X^3& X^4& 0\\ 0& 0& -222X^2& 5000X^3& 10X^4& X^5\end{array}\right)$$

现在格子的维度为 $6$，再代入不等式，我们得到 $X\approx 3.11$ 。确实增大了 $X$ 。

一个现成的结论是：当我们给格子增加 x-shift polynomials，可以使得 $X\approx M^{\frac{1}{2d-1}}$ 。那么如果当我们使用第二种方案继续增加 $X$ 呢？

Coppersmith 定理

设 $0<ϵ<\min \{0.18,\frac{1}{d}\}$ ， $F(x)$ 是 $d$ 次首一多项式，如果在有限域 $M$ 下，有一个或多个根满足 $|x_0|<\frac{1}{2}{M}^{\frac{1}{d}-ϵ}$ ，那么我们就可以在与 $d,\frac{1}{d},\log (M)$ 相关的多项式时间内找到它。

证明过程省略（如果实在没找到过程可以找我一起探讨）。现成的结论：Coppersmith’ Method 的大致时间复杂度为： $O((\frac{1}{ϵ}{)}^9\log (M{)}^3)$ 。

既然气氛烘托到这，那么出道趣味题让大家练练手吧!

设 $p=2^{30}+3,p=2^{32}+15,M=pq,F(x)=1942528644709637042+1234567890123456789x+987654321987654321x^2+x^3$ ，并且告诉我们 $x_0\le 2^{14}$。请解出 $x_0$。【不要用中国剩余定理，用构造格的方法。答案是：16384】

4. Attack

介绍 Coppersmith’ Method 这个寻小根算法之后，我们在来回到如果攻破改进之后低公共指数的 RSA 加密系统。

假设 $N_1,N_2,\dots ,N_k$ 是 $k$ 个互素的整数。设 $N_{min}=\min N_i$ ， $g_i\in {\mathbb{Z}}_{N_i}[x]$ 为最大阶为 $d$ 的多项式。假设存在唯一的 $M<M_{min}$ ，使得 $g_i(M)\equiv C_i(\mathrm{mod}{N}_i)$ 都成立。那么。如果 $k\ge d$ ，可以有效的从 $(N_i,g_i,C_i{)}_{i=1}^k$ 中找到 $M$ 。

其中 $g_i$ 就对应“改进后”的低公共指数的 $m+2^{k}ID$ 。它是一个低阶多项式，可以使用 coppersmith’ method 找到那个根 $m$。

不久我会单独整理一份 jupyter notebook 用于记录 RSA 加密系统中的那些“高明”的攻击技巧。