Wiener Attack 笔记

连分数

连分数形式

令 .

将有理数转换为连分数

直到 .

通过观察可以得到：

将连分数转换为有理数

可以从中得到下面的关系：

连分数算法

是 $f$ 的一个较小的估计值。

如果 $\delta$ 足够小，那么 $f$ 的分子和分母可以通过下面的方式找到：

3. 测试 $f=\frac{n_i}{d_i}$ 是否成立.

成功条件

对于 $\delta$ 大小的影响：

$\delta =1-\frac{f^{\prime}}{f}$ .

根据 $m$ 的大小分为四种情况：

1. $m=0$ :

2. $m=1$ :

3. $m$ 是偶数且 $m\geq2$ :

4. $m$ 是奇数且 $m\geq3$ :

连分数算法在 RSA 的使用

令 $G=GCD(p-1,q-1)$ .

$$ ed=\frac{K}{G}\cdot (p-1)(q-1)+1 $$

令 .

测试猜想的 $k$, $dg$ 是否正确：

假设 $ed>N$ ，那么 $k>g$ .

$\frac{N-(p-1)(q-1)+1}{2}=\frac{p+q}{2}$ ，如果 $(p-1)(q-1)$ 为 0 或是奇数，那么猜想错误。

$\big(\frac{p+q}{2}\big)^2-N=\big(\frac{p-q}{2}\big)^2$ ，如果 $\big(\frac{p-q}{2}\big)^2$ 是完全平方数，那么猜想正确。

在没有防止连分数攻击的情况下，可以期望 $g$ 比较小， $k<dg$ 。在这种情况下 $d$ 的位数约为 $N$ 的 $\frac 1 4$ ，在多项式时间内可以找到这样的 $d$ 。

流程

1. 计算
2. 猜测 $\frac{k}{dg}$
3. 猜测 $edg = e\cdot dg$
4. 猜测 $(p-1)(q-1)=\lfloor \frac{edg}{k} \rfloor$
5. 猜测 $g\equiv edg\pmod k$
6. 猜测 $\frac{p+q}{2}$
7. 猜测 $\big(\frac{p-q}{2}\big)^2$
8. 计算 $d$

一轮中止之后，开始新的一轮，直到得到 $d$ 。

防止连分数攻击

1. 增大 $k$ 。必须增大 $e$ ，可以通过给 $e$ 增加 $LCM(p-1,q-1)$ 的倍数实现。 $e>(pq)^{\frac{3}{2}}$ 时，无法进行连分数攻击。

2. 增大 $g$ 。增大 $GCD(p-1,q-1)$ ，但是在特定条件下可以找到 $g$ 或 $g$ 的因数。

改进

1. 允许寻找 $d$ 的时候略微超过 $kdg<\frac{N}{\frac 3 2(p+q)}$ .

2. 使用对 $(p-1)(q-1)$ 更加接近的估计替换 $N$ :

可以使用 $\lfloor (\sqrt N-1)^2\rfloor$ ，那么 $kdg<\frac 2 3\big(\frac{\sqrt N-1}{\sqrt p-\sqrt q}\big)^2$ .

3. 在多个 $\frac{k}{dg}$ 的猜想上使用算法。（？）

4. 试图寻找 $g$ 或 $g$ 的因数：

假设 $t$ 是 $g$ 的一个未知的因数。

$t\big(\frac{e}{N} \big)$ 是 $\frac{k}{d(\frac{g}{t})}$ 的一个较小的估计。

如果 $g$ 或 $g$ 的所有质因数很大，那么将难以计算 $g$ 的因数。然而， $g$ 过大将导致 $\frac{p-1}{g}$ 和 $\frac{q-1}{g}$ 很小，可以通过查找 $\frac{p-1}{g}$ 和 $\frac{q-1}{g}$ 来寻找 $g$ 的可能值。

一些废话

这篇论文还比较容易看懂，至少对于我来说比网上写的总结好懂一些。

因为翻译水平比较一般，所以可能会有一股机翻味（？）。