Lattice world.

本文包含对 Coppersmith method - Coron Version 的论文笔记详解/翻译。

• Extending Wiener’s Attack
  • 前置知识
    • Wiener’s Approach
    • Guo’s Approach
  • Extension Approach
  • 统计数据
• Lattice Based Attack on Common Private Exponent RSA
  • Common Private Exponent RSA
  • Attack
• Coppersmith
  • 初探
  • Theorem 1 (Howgrave-Graham’s theorem)
    • Proof
  • Theorem 2
    • Proof
  • 全貌
  • Theorem 3 (Coppersmith)
    • Proof
  • Bivariate Integer Polynomials (Coron)
    • 初探
      • 证明
    • 引理
      • Lemma 1
      • Proof
      • Lemma 2
      • Proof
    • 全貌（证明）
      • Addition
    • Summarize
  • Multi-Variate Method
  • Some Applications of Coppersmith
    • Factor N=pq with Partial Knowledge of p
      • Theorem
        • Proof
    • Factor N=pq with Partial Knowledge of d
• Hastad’s Broadcast Attack on padded message
• Franklin-Reiter Related Message Attack
  • 攻击条件
  • 引理 (FR)
    • 证明
• Coppersmith’s Short Pad Attack
  • 证明
  • Some variant
• Factor the RSALib components

Extending Wiener’s Attack

前置知识

Wiener’s Approach

由于之前已经介绍过维纳攻击，这里就只提取最重要的方程式：

其中，$g$ 代表 $gcd((p-1),(q-1))$，$s$ 代表 $1-p-q$。

Guo’s Approach

该方法针对 2 或 3 个方程式，其中 $e_i$ 较大，$d_i$ 相近且较小。

对于两个方程式的情况，我们有如下关系：

对第一个式子乘上 $k_2$，第二个式子乘上 $k_1$ 然后相减，我们得到：

两边同除 $k_2d_1e_2$，得到：

假设 $e_i$ 极大，接近 $N$；而 $g$ 极小。那么 $d_i,k_i$ 较小且接近，设其上限为 $N^{\alpha}$ 那么这就意味着右侧大概在 $N^{-(1+\alpha)}$ 左右。那么，根据 $Poincare$ 定理可知，当 $2(k_2d_1)^2<N^{1+\alpha}$，即可由 $e_1\over e_2$ 的渐近连分数求出 ${k_1d_2\over k_2d_1}$。（也即 $\alpha = {1\over 3} - \epsilon,\epsilon>0$）

但是这里有两个问题需要指出：

• 单纯地知道 $k_id_j$，并不能让我们知道 $k_i$ 或 $d_j$。
• $gcd({k_id_j\over k_jd_i})>1$

Guo 假设第二个问题不存在，这样的几率在 ${6\over \pi^2}\approx 0.61$ 左右。对于第一个问题，他认为要么可以分解 $k_id_j$，要么存在第三个方程式，使得 $k_i=gcd(k_id_j,k_id_k)$。据统计，这样的概率大约在 $({6\over \pi^2})^3\approx 0.23$ 左右。

Extension Approach

需要说明的是，该启发式方法的上限仅在多次实践中得到验证，但在理论上的证明仍有所欠缺。

简要说一下，后面发现有人通过 多元 coppersmith 的方法改进本法并提升了界限，本文中暂未提及。

简单来说，当 $n$ 从 $1\Rightarrow ∞$ 时，$\alpha$ 大概是这样变化的：${1\over 4},{5\over 14},{2\over 5},{15\over 34},{29\over 62},…,1-\epsilon$。（启发式的上限）

如果使用 $LLL$ 进行规约，那么时间复杂度最大为 $O(2^{6n}n^3log^3N)$。所以该方法仅对少数的方程式有效。

下面介绍该方法：

• 设维纳攻击中的如下方程式为 $W_i$：
  • $d_ige_i-k_iN=g+k_is$
• 设 Guo’s Approach 中的如下方程式为 $G_{i,j}$：
  • $k_id_je_j-k_jd_ie_i=k_i-k_j$

我们假设，其中的 $d_i,k_i$ 上限为 $d^{\alpha_n}$，$g$ 很小，$s$ 约为 $N^{1\over 2}$。

接下来以已知两个公钥的情况为例：

我们列出以下三个方程式，即 $W_1,G_{1,2},W_1W_2$：

对第一个式子乘上 $k_2$，第二个式子乘上 $g$，我们可以构造以下向量与格基：

为了使 Target Vector(TV) 的大小 与 $det(L)$ 容易估测，我们设 $M_1=N{1\over 2},M_2=N^{1+\alpha_2}$。然后构造如下矩阵：

我们得到：$\Arrowvert TV’\Arrowvert < 2N^{1+2\alpha_2}$

根据闵可夫斯基定理，我们知道，要使 $TV$ 是该格的一个 $SVP$，那么需要满足：

其中 $c_2$ 是某个（较小的）系数。那么我们可以得到：当 $\alpha_2<{5\over 14}-\epsilon’$ 时，我们得到目标向量 $TV’$，从而可以分解 $N$。

在这里提一下三个公钥的矩阵构造：

目标向量：

统计数据

这里给出一些统计数据：

Lattice Based Attack on Common Private Exponent RSA

Common Private Exponent RSA

FROM Cryptanalysis of RSA and Its Variants

A series public keys share the same small private exponent d and have similarly sized modulus.

Like this:

Attack

Of course $k_i<d$ which is similar as $e_i<\phi (N_i)$ (or we have another method to attack)

Here we set $s_i = (p + q - 1)$, so $\phi (N_i) = N_i - s_i$

And we label them so that $N_1<N_2<…<N_r<2N_1$

and we assume all $N_i$ is balanced (It’s ok for pbits = qbits) so that $s_i<3N_I^{1\over 2}\le 3N_r^{1\over 2}$

We set $d<N_r ^ {\delta_r}$. If $\delta_r < {1\over 2} - {1\over {2(r+1) } } - log_{N_r}(6)$, then all of them can be factored in time polynomial in $(log(N_r)$ and $r)$

Let $M=\lfloor N_r ^ {1\over 2}\rfloor$ and we got a series of equations:

and this system of r + 1 equations can be written as the vector-matrix equation $x_r B _r=v_r$, where:

Since $N_i\le N_r < 2N_1,k_i<d<N_r^{\delta _r}$ and $s_i<3N_r^{1\over 2}$, it follows that the target vector satisfies $\Arrowvert v_r \Arrowvert <\sqrt{1+9r}N_r^{ {1\over 2} +\delta _r }$

And $vol(L)=\arrowvert det(B_r) \arrowvert$, apparently satisfies $vol(L)>( {N_r\over 2} )^{r+{1\over 2} }$

From Minkowski’s bound, a necessary condition for the target vector to be SVP is given by $\Arrowvert v_r \Arrowvert <\sqrt{r+1} vol(L)^{1\over{r+1} }$, and it can be given by $\sqrt{1+9r}N_r^{ {1\over 2} +\delta _r }<\sqrt{r+1} ( {N_r\over 2} )^{r+{1\over 2}\over {r+1} }$ ,

or more simply for r >= 1, $N_r^{ {1\over 2} +\delta _r }<c_r (N_r )^{r+{1\over 2}\over {r+1} }$ where $c_r=\sqrt{r+1\over {9r+1} } {1\over 2^{ ({r+{1\over 2}\over {r+1} } )} } > ({1\over 3})({1\over 2})={1\over 6}$

so that :

which means $\delta_r < {1\over 2}-{1\over {2(r+1)} }-log_{N_r} (6)$.

Then we regard $v_r$ as the SVP of $L$, from which we can get $d$ and compute $k_i$ and $s_i$ so that we can factor $N$.

And anyway Minkowski’s bound is very loose, so there’s still possibility that $v_r$ is not SVP.

Also we can use the method on the single public key but no better than Wiener.

Coppersmith

参考：https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch19.pdf

初探

假设我们有最高次数为 $d$ 的首一多项式 $F(x)=x^d+a_{d-1}x^{d-1}+…+a_1x+a_0$ ，那么问题是：找到所有满足 $F(x_0)\equiv 0\ (mod\ M)$ 的 $\arrowvert x_0 \arrowvert <M^{1\over d}$。

为什么要首一啊 待补充

• 如果并非首一多项式，但 $gcd(a_d,M) = 1$，那么可以求逆元来使其首一。
• 若 $gcd(a_d,M) > 1$，那么可以将 $F(x)\ mod\ M$ 分解为两个同余式来解决。

若 $F(x’) = 0\ over\ Z$ ，使用牛顿迭代一类的方法即可得到 $x’$；而如果 $F(x)$ 的系数都够小，$F(x_0) = 0\ over\ Z$ 就很有可能成立。

而 Coppersmith 的思想就是，以 $F(x)$ 为根源，利用多个 $G_i(x)$ 构造一个系数足够小的 $G(x)$（解同为 $x_0$），从而获得 $x_0$。

我们可以考虑 $d+1$ 个 $G_i(x)=Mx^i\ for\ i \in [0,d)$ 和 $F(x)$。（它们都有根 $x_0$）

那么我们可以构造如下格基，且 $det(L) = M^dX^{ {d(d+1)}\over 2 }$：

那么所要构造的多项式 $G(x)$ ，其系数就对应该格基规约后获得的 SVP 的各项系数。

Theorem 1 (Howgrave-Graham’s theorem)

我们将 $F(x)$ 用向量表示，那么 $b_F=(a_0,a_1X,a_2X^2,…,a_dX^d)$，用 $M$ 代表模数，设 $X$ 为 $\arrowvert x_0 \arrowvert$ 的一个上限，其中 $F(x_0)\equiv 0\ (mod\ M)$。

若 $\Arrowvert b_F \Arrowvert < {M\over \sqrt{d+1} }$，那么 $F(x_0) = 0$。

（即：有一 $k$ 个单项式组成的 $h(x,y)$，且 $h(x_0,y_0)\equiv 0\ mod\ n,\mid x_0\mid, \mid y_0\mid \le X,Y$，则若 $\Arrowvert h(xX,yY)\Arrowvert < {n\over \sqrt{k} }$，则 $h(x,y)=0\ in\ ZZ$）

Proof

由柯西不等式，$(\Sigma_{i=1}^n x_iy_i)^2 \le (\Sigma_{i=1}^n x^2)(\Sigma_{i=1}^n y^2)$，那么我们设 $x_i \ge 0$ 、$y_i=1$，则有：$\Sigma_{i=1}^n x_i \le \sqrt{n\Sigma_{i=1}^n x_i^2}$。

那么：

又 $F(x_0)\equiv 0\ (mod\ M)$，故 $F(x_0) = 0$。

Theorem 2

设 $c_1(d)=2^{-{1\over 2} }(d+1)^{-{1\over d} }$，如果 $X<c_1(d)M^{2\over d(d+1) }$，那么所有满足 $\arrowvert x_0 \arrowvert \le X$ 的 $x_0$ 都满足 $G(x_0)=0\ over\ Z$。

Proof

我们知道 $\Arrowvert SVP_1\Arrowvert \le 2^{ {n-1\over 4} }det(L)^{1\over n}=2^{d\over 4}M^{ {d\over d+1} }X^{d\over 2}$。

由 Theorem 1 可知，只要 $2^{d\over 4}M^{ {d\over d+1} }X^{d\over 2} < {M\over \sqrt{d+1} }$，即 $\sqrt{d+1}·2^{d\over 4}X^{d\over 2}< M^{1\over {d+1} }$，那么 Theorem 2 就成立，也即该定理中的条件。

以上的限制都是对 $X$ 的近似限制，在某些情况下，不满足这样的条件，也可能找到这样的解。

全貌

尽管上面提到的定理很强大了，但 Coppersmith 仍能扩展其范围。

观察 Theorem 2 中给出的限制条件，易知，对于该式：$2^{d\over 4}M^{ {d\over d+1} }X^{d\over 2} < {M\over \sqrt{d+1} }$，要使 $X$ 的范围更大，那么有两种策略：

• 通过增加矩阵中的行数从而增加维度 n（这些行对 $det(L)$ 的贡献需要小于 $M$）
• 通过所谓的 ”x-shift“ 多项式 $xF(x),x^2F(x),…,x^kF(x)$ 增大右侧的 $M$

Theorem 3 (Coppersmith)

令 $\epsilon \in (0,min(0.18,{1\over d}))$；$F(x)$ 是度为 $d$，且存在 $F(x_0) = 0\ (mod\ M)$, $\arrowvert x_0 \arrowvert < {1\over 2} M^{ {1\over d} - \epsilon}$ 的多项式。那么 $x_0$ 可以在关于 $d,{1\over \epsilon},log(M)$ 的多项式时间复杂度（$O(({1\over \epsilon})^9log^3M)$）内被找到。

Proof

令 $h>1$ 是取决于 $d$ 和 $\epsilon$ 的一个整数。决定式为 $h ={ {d-1\over d\epsilon}+1 \over d} \approx {1\over d\epsilon} $（见后）

考虑多项式 $G_{i,j}(x)=M^{h-1-j}F(x)^jx^i,0\le i < d ,0\le j<h$（注意到 $G_{i,j}(x_0)\equiv 0\ (mod\ M^{h-1})$）

那么格基的维数为 $dh$，$det(L)=M^{(h-1)hd\over 2}X^{(dh-1)dh\over 2}$

规约后可以得到 $\Arrowvert SVP\Arrowvert < 2^{(dh-1)\over 4}det(L)^{1\over dh}=2^{dh-1\over 4}M^{h-1\over 2}X^{dh-1\over 2}$

该向量对应一个度数为 $dh-1$ 的多项式 $G(x)$，且 $G(x_0)\equiv 0\ (mod\ M^{h-1})$，那么若其范数小于 ${M^{h-1}\over \sqrt{dh} }$，则有 $G(x_0)=0\ over\ Z$。

也即：$\sqrt{dh} 2^{dh-1\over 4}M^{h-1\over 2}X^{dh-1\over 2}<M^{h-1}$；

整理一下，得到：$\sqrt{dh} 2^{dh-1\over 4}X^{dh-1\over 2}<M^{h-1\over 2}$。

这个式子太复杂了，我们再整理一下：$c(d,h)X<M^{h-1\over dh-1}$

• 其中 $c(d,h)=(\sqrt{dh} 2^{dh-1\over 4})^{2\over dh-1}=\sqrt{2}(dh)^{1\over dh-1}$

又：M 的幂次 ${h-1\over dh-1}={1\over d} - {d-1\over d(dh-1)}$，由设定条件， $\epsilon ={d-1\over d(dh-1)}$，于是可以得到：

$h ={ {d-1\over d\epsilon}+1 \over d} \approx {1\over d\epsilon} $

注意： $dh=1+{d-1\over d\epsilon}$，所以 $c(d,h)=\sqrt{2}(1+{d-1\over d\epsilon })^{d\epsilon \over d-1}$；当 $\epsilon \Rightarrow0$，$c(d,h)$ 收敛于 $\sqrt{2}$ ；当 $\epsilon \Rightarrow 0.18$，$c(d,h)$ 仍小于 2。故满足 $c(d,h)X<M^{h-1\over dh-1}$ 也即设定条件。

Let `N` be the characteristic of the base ring this polynomial
  is defined over: ``N = self.base_ring().characteristic()``.
  This method returns small roots of this polynomial modulo some
  factor `b` of `N` with the constraint that `b >= N^\beta`.
  Small in this context means that if `x` is a root of `f`
  modulo `b` then `|x| < X`. This `X` is either provided by the
  user or the maximum `X` is chosen such that this algorithm
  terminates in polynomial time. If `X` is chosen automatically
  it is `X = ceil(1/2 N^{\beta^2/\delta - \epsilon})`.
  The algorithm may also return some roots which are larger than `X`.
  'This algorithm' in this context means Coppersmith's algorithm for finding
  small roots using the LLL algorithm. The implementation of this algorithm
  follows Alexander May's PhD thesis referenced below.
  INPUT:
  - ``X`` -- an absolute bound for the root (default: see above)
  - ``beta`` -- compute a root mod `b` where `b` is a factor of `N` and `b
    \ge N^\beta`. (Default: 1.0, so `b = N`.)
  - ``epsilon`` -- the parameter `\epsilon` described above. (Default: `\beta/8`)
  - ``**kwds`` -- passed through to method :meth:`Matrix_integer_dense.LLL()

Bivariate Integer Polynomials (Coron)

Finding Small Roots of Bivariate Integer Polynomial Equations Revisited

对于整数域上的不可约多项式 $p(x,y)$ ，设 $\delta$ 为 $deg_{max(x,y)}(p(x,y))$，定义$W=max{\arrowvert p_{ij}\arrowvert X^i Y^j}$，$p(x_0,y_0) = 0,\mid x_0 \mid \le X, \mid y_0 \mid \le Y$。

若 $XY<W^{2\over 3\sigma}$，就可以在 $pol(log(W),2^ \sigma)$ 时间复杂度内得到 $(x_0,y_0)\in {\cal Z}^2$ 。

如果 $\delta$ 为 $xy$ 的总最大指数，那么界限为 $XY<W^{1\over \sigma}$。

初探

设不可约多项式 $p(x,y)=a+bx+cy+dxy,a\ne 0,d\ne 0$，其根为 $(x_0,y_0)$。设根的界限为 $X,Y$、$W=\Arrowvert p(xX,yY) \Arrowvert_\infty$，则 $XY< {1\over 16}W^{1\over2}$ 时，根可在多项式时间内被求出。

证明

定义一个 $n\in [W,2W),gcd(n,a)=1$（可以这样生成 $n=W+((1-W)\ mod \mid a\mid)$），然后定义多项式：

那么根据以上，可以构造格子：

其中 $\omega = 4,det(L)=n^3(XY)^2$，那么设规约后得到的多项式为 $h(x,y)$，则 $\Arrowvert h(xX,yY)\Arrowvert \le 2·n^{3/4}(XY)^{1/2}$。由以上 Theorem 1 推得，$XY<{n^{1/2}\over 16}$，即 $\Arrowvert h(xX,yY)\Arrowvert < n/2$，$h(x_0,y_0) = 0\ in\ Z$。由于 $n\ge W$，$XY< {W^{1/2}\over 16}$ 即可。

得到 $h(x,y)$ 后，由于 $\Arrowvert h(xX,yY)\Arrowvert < n/2 < W = \Arrowvert p(xX,yY)\Arrowvert_\infty \le \Arrowvert p(xX,yY)\Arrowvert$，故 $h(x,y)$ 不可能是 $p(x,y)$ 的倍数，又因为 $p(x,y)$ 是不可约的：

那么 $Q(x)=Res_y(h(x,y),p(x,y))$ 就给出了一个非零整数多项式，其中 $Q(x_0)=0$。找到 $x_0$ 后代入原式找到 $y_0$ 即可。

引理

Lemma 1

对于多项式 $h(x)=\sum_i h_ix^i$，我们定义 $\Arrowvert h \Arrowvert ^2 = \sum_i \arrowvert h_i\arrowvert^2$。

$a(x,y),b(x,y)$ 为两个整数域上的非零多项式，x、y 的最高次数为 d。如果 $a(x,y) \mid b(x,y) $，那么，对于 $a(x,y),b(x,y)$ 的系数： $\Arrowvert b \Arrowvert \ge 2^{-(d+1)^2}·\Arrowvert a\Arrowvert_\infty$。

Proof

M. Mignotte, An inequality about factors of polynomials. Math Comp. 28, 1153- 1157, 1974.

来源于 Mignotte 的定理：已知两个整数域上的非零多项式 $f(x),g(x)$ ，若 $deg(f) \le k,f \mid g$，那么 $\Arrowvert g \Arrowvert \ge 2^{-k}·\Arrowvert f \Arrowvert_\infty$。令 $f(x)=a(x,x^{d+1})$，我们有 $deg(f)\le (d+2)d \le (d+1)^2$ 且 $f(x),a(x,y)$ 的各项系数相同。相似地，令 $g(x)=b(x,x^{d+1})$，那么满足 $f(x)\mid g(x)$，由以上定理知引理1成立。

Lemma 2

令 $a(x,y),b(x,y)$ 为 Lemma 1 中所定义的多项式。假设 $a(0,0)\ne 0$ 且有非零整数 $r,r\mid b(x,y),gcd(r,a(0,0))=1$。那么 $r·a(x,y)\mid b(x,y)$ 且 $\Arrowvert b \Arrowvert \ge 2^{-(d+1)^2}·\mid r\mid ·\Arrowvert a\Arrowvert_\infty$

Proof

令 $\lambda(x,y)$ 满足 $a(x,y)·\lambda(x,y)=b(x,y)$，我们将证明 $r\mid \lambda(x,y)$，那么引理2成立。采用反证法：令 $\lambda_{ij} $ 是 $\lambda(x,y)$ 中不被 $r$ 整除的 $x^iy^j$ 项系数，且接下来取按 $ij$ 排列的最小字典序项。那么我们有 $b_{ij}\equiv 0 \equiv \lambda_{ij} · a(0,0)-\sum\limits_{0,0\le i’,j’< i,j}\lambda_{i’,j’}·a_{i’,j’}\ (mod\ r)$。由前设，$r\mid \forall \lambda_{i’,j’}$，那么 $\sum\limits_{0,0\le i’,j’< i,j}\lambda_{i-i’,j-j’}·a(i’,j’)\equiv 0\ (mod\ r)$，又 $gcd(r,a(0,0))=1,r\nmid \lambda_{ij}$，上式不成立，故矛盾。

全貌（证明）

令 $p(x,y) = \sum\limits_{0\le i,j \le \delta}p_{ij}x^i y^j$，$W=\Arrowvert p(xX,yY) \Arrowvert_\infty$。假设 $p_{00}\ne 0, gcd(p(0,0),XY)=1$。

我们选择一个自然数 $k$，令 $\omega = (\delta + k + 1)^2$、

生成 $u$ 满足 $\sqrt{\omega}·2^{-\omega}·W\le u < 2W,gcd(p_{00},u)=1$，如上所言，我们也可以选择 $u=W+((1-W)\ mod \mid p_{00} \mid)$，

我们令 $n=u·(XY)^k$，则有：$gcd(p_{00},n)=1,\sqrt{\omega}·2^{-\omega}·(XY)^k·W\le n < 2·(XY)^k·W$。

为求结式，我们在此也要找到一个多项式 $h(x,y)$，满足 $h(x_0,y_0)=0$，且不是 $p(x,y)$ 的倍数。我们令：

令 $\widetilde {q}{ij}(x,y)=q{ij}(xX,yY)\ \ ((XY)^k \mid \widetilde {q}_{ij}(x,y))$，设 $h(x,y)$ 为规约后得到的式子，则 $(XY)^k\mid h(xX,yY)$ 且它对 $x,y$ 分别的最高次数为 $(\delta + k)$，也就是说，其单项式项数最多为 $\omega$。

正如在初探中所提到的，我们找到的 $h(xX,yY)$ 应当足够小，有以下两个原因：

• 使得在整数域上， $h(x,y)=0$ 。

  ​ 当 $\Arrowvert h(xX,yY)\Arrowvert < {n\over \sqrt{\omega} }$ 即可满足。

• 使得 $p(x,y)\nmid h(x,y)$。

  ​ 由 Lemma 2 知：$\Arrowvert h(xX,yY)\Arrowvert < 2^{-\omega}·(XY)^k·W$，（？）故可得到 $h(xX,yY)\nmid p(xX,yY)$，从而 $h(x,y)\nmid p(x,y)$。

  就这儿没懂，强烈怀疑大小符号反了，而且后面的不等式怎么证明。

  • 这个条件的来源：令 $a(x,y)=p(xX,yY),b(x,y)=h(xX,yY)\ and\ r = (XY)^k$；且 $a(0,0)=p_{00}\ne 0,gcd(a(0,0),(XY)^k)=1$。

    （由 $n$ 的定义，易知满足条件2则满足条件1）

那么，我们用 $\widetilde {q}_{ij}(x,y)$ 构造格基并规约即可，拿到 $h(x,y)$ 后，又因为 $p(x,y)$ 不可约，故 $Q(x)=Resultant_y(h(x,y),p(x,y))$，解得 $x_0$，代回原式解得 $y_0$。

以下是维度为 $\omega=(\delta+k+1)^2$ 的示例，其中，$\delta=k=1$：

（易知每一项中都有 $XY$，故在实际中可以对 $(XY)^{-k}L$ 进行规约，以加快效率）

界限证明：

计算 $det(L)$：

由闵可夫斯基界和上面的条件2，只要满足以下不等式即可：

结合 $n$ 的范围可知：$XY<2^{-\beta}W^{\omega}$，其中：

对于 $\delta \ge 1 ,k \ge 0$，有：

令 $k=\lfloor {1\over \epsilon} \rfloor$，我们得到： $XY<W^{ {2\over 3\delta}-\epsilon}·2^{-13\delta-{4\over \delta·\epsilon^2} }$。证毕。

对于 $\delta$ 为 $xy$ 总最高次数的界限，此处不予证明，有兴趣者可看原文附录。这里只介绍有区别的地方：对于 $q_{ij}(x,y)=x^iy^jX^{k-i}Y^{K-j}q(x,y),0\le i+j\le k$，对于 $q_{ij}(x,y)=x^iy^jn,k<i+j\le k+\delta$。这样一来，格基维度则为 $\omega = (k+\delta + 1)(k+\delta + 2)/2$。

该方法比之 Coppersmith 的界限 $XY<W^{ {2\over 3\delta}-\epsilon}·2^{-13\delta }$ 稍有减弱，同时也不再是 $O(pol(logW,\delta,1/\epsilon))$ 的复杂度，而是 $O(pol(logW,\delta),exp(1/\epsilon))$ 的复杂度。但在极限情况下，两者复杂度是一样的。

Addition

如果以上多项式不满足 $p(0,0)\ne 0,gcd(p(0,0),XY)=1$，则有：

• 若 $p(0,0)=0$，我们可以用一个 $p^(x,y),p^(0,0)\ne 0$ 代替之。

  可表示 $p(x,y)=x·a(x)+y·b(x,y)$，其中 $a(x)$ 的次数最高为 $\delta - 1$ 次。由代数基本定理知，其最多有 $\delta - 1$ 个根，那么 $a(i)\ne 0,0<i\le \delta$ 中至少有一个满足，那么 $p(i,0)\ne 0$；所以我们可以用 $p^(x,y)=p(x+i,y)$ 替换掉原本的多项式，最后 $x_0=x_0^-i$。

• 若 $gcd(p(0,0),XY)\ne 1$：

  我们生成两素数 $X<X’<2X,Y<Y’<2Y,p(0,0)\nmid X’,p(0,0)\nmid Y’$ 代替 $X,Y$。

  （recursive prime generation alg）

Summarize

其实 Coron 的整数域上规约法与 Coppersmith 对模域上的多项式进行规约的方法本质是一致的（规约多项式以期小系数满足柯西不等式，从而启发式地得到整数域上的其他线性无关多项式，进行结式），只不过 Coron 单设了一个 $n=(XY)^k$（因为设定了每一行都能整除之，如此，规约前后的多项式都能满足目标解成立），而后者直接以 $mod^k$ 作为一个格基中的模了。同时他们两人选取的 shift 多项式也是有所不同的，总的来说，我还没有搜到过（也没细致去搜过）对这些方法的通用分析。

Multi-Variate Method

由于和 Bivariate one 类似，此处仅提供 Coron 原话：

Some Applications of Coppersmith

Factor N=pq with Partial Knowledge of p

Coppersmith 最初提出的方案须通过双变量，但这里描述一个更简易的单变量方法。

Theorem

令 $N = pq,p<q<2p$，$0<\epsilon<{1\over 4}$，假设已知 $\widetilde p \in N$ 使得 $\mid p-\widetilde p\mid < {1\over 2 \sqrt 2}N^{1/4 - \epsilon}$。那么我们能够在 $exp(log(N),{1\over \epsilon})$ 内分解 $N$。（Simplified version）

Proof

设 $F(x)=(x+\widetilde p)$，知 $\sqrt {N\over 2} \le p \le \sqrt N$，令 $X=\lfloor {1\over 2 \sqrt 2}N^{1/4 - \epsilon} \rfloor$。

令 $k=2h,h\ge 4 \in Z$，构造 $k+1$ 个多项式 $N^h,N^{h-1}F(x),…,F(x)^h,xF(x)^h,…,x^{k-h}F(x)^h$，这些多项式在 $p^h$ 模域下都同余 0。将它们的系数用向量表示，并构建格子。得到 $det(L) = N^{h(h+1)/2}X^{k(k+1)/2}$。规约后，若满足 Theorem 1，则 SVP 代表的式子就在整数域上等于零。由于 $p>({N\over 2})^{1\over 2}$，在 $k\ge 6$ 时我们有 $(k+1)^{1\over k} \le \sqrt 2$，故整理后得到 $X<{1\over 2\sqrt 2}N^{ {1\over 4}-{1\over 8h+4} } $ 即可。故 $h\ge max{4,{1\over 4\epsilon} }$ 为充分条件。

Factor N=pq with Partial Knowledge of d

Based on Factor N=pq with Partial Knowledge of p

Hastad’s Broadcast Attack on padded message

用于解决 $(a_im+b_i)^e\equiv c_i\ (mod\ n_i)$，给定 $a_i,b_i,c_i,n_i$

1. 使用 CRT 计算出 $T_i$ 满足 $T_i\equiv 1\ (mod\ n_i),T_i\equiv 0\ (mod\ n_j)(i \ne j)$

2. 计算多项式 $g=\Sigma T_i * g_i$，其中多项式 $g_i= (a_ix+b_i)^e - c_i$
3. 将 $g$ 化为首一多项式并寻找 $PolynomialRing(Zmod(\Pi n_i))$ 内的根，即为 $m$。

Franklin-Reiter Related Message Attack

攻击条件

已知 $<N,e,C_1,C_2,f(x)>$ with small $e$。

引理 (FR)

这里为了简单起见，以 $e=3$ 的情况进行说明：

设 $M_1\ne M_2 \in Z_N^*$，对于 $b\ne 0$ 的线性多项式 $f(x)=ax+b$ 满足 $M_1=f(M_2)\ (mod\ N)$。那么我们可以在 $logN,e$ 的平方时间内计算出 $M_1,M_2$。

证明

我们知道，$M_2$ 是下列多项式的根：

那么：$x-M_2$ 整除以上多项式，也就是说，可以求出 $gcd(g_1,g_2)\ mod\ N$，若其为线性的，则可找到 $M_2$。

《综述》中写到，当 $e=3$，其必定线性。对于 $e>3$，其几乎总是线性的。但也有罕见的情况会导致攻击失败。

Coppersmith’s Short Pad Attack

Also with small $e$.

当 $padding$ 长度 $m\in (0,\lfloor {Nbits()\over e^2} \rfloor)$ 时，且 $Mbits\le n-m$。定义 $M_1=2^mM+r_1,M_2=2^mM+r_2,r_{1,2}\in [0,2^m)$，那么如果知道 $<N,e,C_1,C_2>$，我们就可以算出 $M$。

它这里说的 M 应该就是一个 common padding 的样子， r1,2 才指的是 x, x+y。总之不用管它。

证明

定义 $g_1(x,y)=x^e-C_1,g_2(x,y)=(x+y)^e-C_2\ (mod\ N)$，当 $y = r_2-r_1$，知其有相同根 $M_1$。也即，$y=r_2-r_1 $ 是结式 $h(y)=Res_x(g_1,g_2)\ (mod\ N)$ 的一个小根。而 $h(y)$ 的最高次数小于 $N^{1\over e^2 }$，则若 $y< N^{1\over e^2 }$，那么使用 $Coppersmith$ 求出该小根以后，我们就可以利用上面的 $FR$ 攻击求出 $M_2$，进而拿到 $M$。

Some variant

我们有 $M_{1,2} = \text{prefix}{1,2} \Arrowvert \text{secret} \Arrowvert \text{padding}{1,2}$ with small $e$, $\text{prefix}$ and the length of $M$.

那么在构造 $g_1,g_2$ 的时候，我们就应将 $\text{prefix}_{1,2}$ 的差异补齐后再进行攻击。

（$g_2(x,y)=(x+y+\Delta )^e-C_2\ (mod\ N)$，其中 $\Delta$ 是前缀的差异）

Factor the RSALib components

https://github.com/brunoproduit/roca/blob/master/src/

The Return of Coppersmith’s Attack:Practical Factorization of Widely Used RSA Moduli (ROCA)

由 RSALib 生成的模数，其因子形如： $p=kM+(65537^a\ mod\ M)$（p, q* 大小相近）

其中，对于给定位数的 RSA，primes 的区别仅在于未知的 k, a ，而 $M = P_n# =\Pi_{i=1}^n P_i=23···P_n$， 在 Nbits 不同时，n 也会改变（有一个固定的取值），且 M 的大小和 primes 是差不多的，这就导致了 *k 的大小较小。而由于有个底数，我们自然无法确定 a 的大小。

但，我们知道，$N=(kM+65537^a\ mod\ M) * (lM+ 65537^b\ mod\ M)$，那么，$N\equiv 65537^{a+b}\equiv 65537^c\ (mod\ M)$，我们知道 M 是小素数乘积，故 $\phi(M)$ 必然也是小素数幂乘积，我们可以通过 Pohlig-Hellman（或言 CRT）来拿到 c，也即 a+b。

拿到了 c，就可以枚举了。假设我们枚举 $a\in { [ {c\over 2} ,{c+ord\over 2} ]}$，其中 $ord$ 指 $ord_M(65537)$。

设 $f(x)=xM+65537^a\ mod\ M\ (mod\ N)$，这便是 N 的一个因子。使用 Coppersmith partial p 一类的方法即可求得 x，那么 $p = f(x)$。

• 这里应把 $f(x)$ 化为首一多项式，也即 $f(x)=x+(M^{-1}\ mod\ N)(65537^a\ mod\ M)\ (mod\ N)$，若如此，同时 $(\beta,X)=(0.5,2N^\beta/M )$。
• 显然 M 非常大，枚举上限几乎不可达。但我们之前说过 M 的大小和 primes 差不多，那么，我们就可以找到一个 $M’\arrowvert M$，既减小 ord 的范围，又满足 coppersmith 的条件（$log_2(M) > {log_2(N)\over 4}$）。虽然增大了 k’ 的范围，但对 coppersmith 来说都是小事。这样一来，问题就变得比较可解了。

exp 和 参考论文 都在上方的链接中。不过要找到 success rate 尽可能高、running time 尽可能短的，还是得调整参数。对于 M’，按贪心方法来即可，总之是在保证 ord(M’) 尽可能小的同时，使得 M’ 尽可能大。关键如下两式。此处不再赘述论文中的寻找方法。