Lattice world.

# Extending Wiener’s Attack

## 前置知识

### Wiener’s Approach

$d_ige_i-k_iN=g+k_is$

### Guo’s Approach

$e_1d_1g-k_1(p-1)(q-1)=g\\ e_2d_2g-k_2(p-1)(q-1)=g$

$k_2d_1e_1-k_1d_2e_2=k_2-k_1$

${e_1\over e_2} - {k_1d_2\over k_2d_1} = {k_2-k_1\over k_2d_1e_2}$

• 单纯地知道 $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

• 设维纳攻击中的如下方程式为 $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_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)$

$\Arrowvert TV'\Arrowvert < 2N^{1+2\alpha_2}<({1\over c_2})(N^{ {13\over 2} +\alpha_2})^{1\over 4}$

# 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 not better than Wiener.

# Coppersmith

## 初探

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

## Theorem 1 (Howgrave-Graham’s theorem)

### Proof

\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}

## Theorem 2

### Proof

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 就成立，也即该定理中的条件。

## 全貌

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

## Theorem 3 (Coppersmith)

### Proof

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

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

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

### 初探

#### 证明

$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\\ (q_{ij}(x_0,y_0) = 0 \ mod\ n)$

### 引理

#### Lemma 1

$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.

### 全貌（证明）

$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)$

• 使得在整数域上， $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$

就这儿没懂！

这个条件的来源：令 $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$。

（易证满足条件2则满足条件1）

（易知每一项中都有 $XY$，故在实际中可以对 $(XY)^{-k}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^{(\omega-1)/4}·det(L)^{1/\omega}<2^{-\omega}·(XY)^k·W$

$\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}$

$\alpha \ge {2\over 3\delta} - {2\over 3·(k+1)}\\ \beta \le {4k^2\over \delta} + 13· \delta$

• 若 $p(0,0)=0$，那么可表示 $p(x,y)=x·a(x)+y·b(x,y)$，其中 $a(x)$ 的次数最高为 $\delta - 1$ 次。由代数基本定理知，其最多有 $\delta - 1$ 个根，那么 $a(i,0),0<i\le \delta$ 中至少有一个非零解。所以我们可以用 $p^(x,y)=p(x+i,y)$ 替换掉原本的多项式，最后 $x_0=x_0^-i$。
• 生成两素数 $X<X’<2X,Y<Y’<2Y,p(0,0)\nmid X’,p(0,0)\nmid Y’$ 代替 $X,Y$。

## Some Applications of Coppersmith

### Factor N=pq with Partial Knowledge of p

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

### Factor N=pq with Partial Knowledge of d

Based on Factor N=pq with Partial Knowledge of p

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

## 引理 (FR)

### 证明

$g_1(x) = f(x)^e - C_1\ (mod\ N)\\ g_2(x) = x^e - C_2\ (mod\ N)$

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

Also with small $e$.

## Some variant

（$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)

• 这里应把 $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’ 尽可能大。关键如下两式。此处不再赘述论文中的寻找方法。