Lattice world.
本文包含对 Coppersmith method - Coron Version 的论文笔记详解/翻译。
- Extending Wiener’s Attack
- Lattice Based Attack on Common Private Exponent RSA
- Coppersmith
- Hastad’s Broadcast Attack on padded message
- Franklin-Reiter Related Message Attack
- Coppersmith’s Short Pad Attack
- Factor the RSALib components
Extending Wiener’s Attack
前置知识
Wiener’s Approach
由于之前已经介绍过维纳攻击,这里就只提取最重要的方程式:
\[d_ige_i-k_iN=g+k_is\]其中,$g$ 代表 $gcd((p-1),(q-1))$,$s$ 代表 $1-p-q$。
Guo’s Approach
该方法针对 2 或 3 个方程式,其中 $e_i$ 较大,$d_i$ 相近且较小。
对于两个方程式的情况,我们有如下关系:
\[e_1d_1g-k_1(p-1)(q-1)=g\\ e_2d_2g-k_2(p-1)(q-1)=g\]对第一个式子乘上 $k_2$,第二个式子乘上 $k_1$ 然后相减,我们得到:
\[k_2d_1e_1-k_1d_2e_2=k_2-k_1\]两边同除 $k_2d_1e_2$,得到:
\[{e_1\over e_2} - {k_1d_2\over k_2d_1} = {k_2-k_1\over 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$:
\[d_1ge_1-k_1N=g+k_1s\\ k_1d_2e_2-k_2d_1e_1=k_1-k_2\\ d_1d_2g^2e_1e_2-d_1gk_2e_1N-d_2gk_1e_2N+k_1k_2N^2=(g+k_1s)(g+k_2s)\]对第一个式子乘上 $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$,那么需要满足:
\[\Arrowvert TV'\Arrowvert < 2N^{1+2\alpha_2}<({1\over c_2})(N^{ {13\over 2} +\alpha_2})^{1\over 4}\]其中 $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:
\[e_1d=1+k_1\phi (N_1)\\ e_2d=1+k_2\phi (N_2)\\ ...\\ e_rd=1+k_r\phi (N_r)\\\]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:
\[dM=dM\\ e_1d-N_1k_1=1-k_1s_1\\ e_2d-N_2k_2=1-k_2s_2\\ ...\\ e_rd-N_rk_r=1-k_rs_r\\\]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 :
\[N_r^{ {1\over 2} + \delta _r }< N_r ^ { {r + {1 \over 2 } \over r+1 }-log_{N_r} (6) }\]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}$。
那么:
\[\begin{align} \arrowvert F(x_0)\arrowvert &= \arrowvert \Sigma_{i=0}^d a_ix_0^i \arrowvert\\ &\le \Sigma_{i=0}^d \arrowvert a_i \arrowvert \arrowvert x_0 \arrowvert ^i\\ &\le \Sigma_{i=0}^d \arrowvert a_i \arrowvert X ^i\\ &\le \sqrt{d+1} \Arrowvert b_F \Arrowvert (柯西)\\ &< \sqrt{d+1} {M\over \sqrt{d+1} } = M \end{align}\]又 $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)$),然后定义多项式:
\[q_{00}(x,y)=a^{-1}p(x,y)\ mod\ n=1+b'x+c'y+d'xy\\ q_{10}=nx\\ q_{01}=ny\\ q_{11}=nxy\\ (s.t.\ q_{ij}(x_0,y_0) = 0 \ mod\ n)\]那么根据以上,可以构造格子:
其中 $\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)$ 的倍数。我们令:
\[q(x,y)=p_{00}^{-1}·p(x,y)\ mod\ n=1+\sum\limits_{(i,j)\ne (0,0) }a_{ij}x^iy^j\\ q_{ij}(x,y)=x^iy^jX^{k-i}Y^{k-j}q(x,y)\ for\ (i,j) \in [0,k]^2 \\ q_{ij}(x,y)=x^iy^jn\ for\ (i,j)\in [0,\delta + k]^2 \backslash [0,k]^2\\ (q_{ij}(x_0,y_0) = 0\ mod\ n)\]令 $\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)$:
\[\prod\limits_{0\le i,j \le k}(XY)^k=(XY)^{k(k+1)^2}\\ \prod\limits_{(i,j)\in [0,\delta + k]^2 \backslash [0,k]^2}X^iY^jn=(XY)^{ {(\delta+k)(\delta+k+1)^2\over 2} - {k(k+1)^2\over 2} }n^{\delta(\delta+2k+2)}\\ so:\ det(L)=(XY)^{ {(\delta+k)(\delta+k+1)^2+k(k+1)^2\over 2} }n^{\delta(\delta+2k+2)}\\]由闵可夫斯基界和上面的条件2,只要满足以下不等式即可:
\[2^{(\omega-1)/4}·det(L)^{1/\omega}<2^{-\omega}·(XY)^k·W\]结合 $n$ 的范围可知:$XY<2^{-\beta}W^{\omega}$,其中:
\[\alpha= {2(k+1)^2\over (\delta + k)(\delta+k+1)^2-k(k+1)^2}\\ \beta={5\over 2}·{(\delta+k+1)^4+(\delta+k+1)^2\over (\delta+k)(\delta+k+1)^2 - k(k+1)^2}\]对于 $\delta \ge 1 ,k \ge 0$,有:
\[\alpha \ge {2\over 3\delta} - {2\over 3·(k+1)}\\ \beta \le {4k^2\over \delta} + 13· \delta\]令 $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$
-
使用 CRT 计算出 $T_i$ 满足 $T_i\equiv 1\ (mod\ n_i),T_i\equiv 0\ (mod\ n_j)(i \ne j)$
- 计算多项式 $g=\Sigma T_i * g_i$,其中多项式 $g_i= (a_ix+b_i)^e - c_i$
- 将 $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$ 是下列多项式的根:
\[g_1(x) = f(x)^e - C_1\ (mod\ N)\\ g_2(x) = x^e - C_2\ (mod\ N)\]那么:$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’ 尽可能大。关键如下两式。此处不再赘述论文中的寻找方法。