Wiener Attack

引言

又到了每周四的没有碧蓝航线玩好无聊时间，维纳攻击的脚本自己曾经写过，但是遇到大整数的时候会发生错误，前天拜读了z2333大佬的维纳攻击详解之后，正好今天无事，找来那两篇论文，再推导一遍，重新整理了一下，突然解决了之前的bug（doge）。

以下内容默认掌握一定RSA基础及相关数论知识。

Wiener Attack简介（太长不看版）

我们从RSA的私钥开始
$$
ed-1=k\varphi(n)
$$
变形
$$
\frac{e}{\varphi(n)}-\frac{k}{d}=\frac{1}{d\varphi(n)}
$$
考虑到$\varphi(n)=(p-1)(q-1)\approx pq=n$）
$$
\mid \frac{e}{n}-\frac{k}{d} \mid=\frac{1}{d\varphi(n)}
$$
$d\phi(n)$是一个很大的数，所以不难由上式得到$\frac{e}{n}$接近$\frac{k}{d}$

为啥要这么写呢，因为$e$和$n$是我们是知道的，所以我们计算出$\frac{e}{n}$后，$\frac{k}{d}$怎么出来呢，计算$\frac{e}{n}$的连分数展开，依次算出这个分数每一个渐进分数，由于$\frac{e}{n}$接近$\frac{k}{d}$，$wiener$证明了，该攻击能精确的覆盖$\frac{k}{d}$，前提是$d<\frac{1}{3}n^{\frac{1}{4}}$。

最终我们能算出$\phi(n)$从而最构造如下二次方程
$$
x^2-(p+q)x+pq=x^2-(n-\varphi(n)+1)x+n=0
$$
最终解得两根$p、q$。

推导

维纳攻击基本原理

维纳攻击通常被描述成如下形式

如果$p<q<2p,e<n,d<\frac{1}{3}n^\frac{1}{4}，$那么$d$是$\frac{e}{n}$连分数展开的一个分母。

从如下最基本的式子开始
$$
ed\equiv 1\ (mod\ \varphi(n))
$$
则$\exists k\in Z,st\ ed-k\varphi(n)=1$。现在$\varphi(n)\approx n$隐含$\frac{k}{d}\approx\frac{e}{n}$。更精确些，我们有$n-3\sqrt{n}<\varphi(n)<n$以及
$$
\mid \frac{k}{d}-\frac{e}{n} \mid <\frac{3k}{d\sqrt{n}} <\frac{1}{2d^2}(*)
$$
先证$n-3\sqrt{n}<\varphi(n)<n$。不等式的右边显然成立，左边可化简成
$$
pq-3\sqrt{pq}<pq-(p+q)+1
$$

$$
\iff p-3\sqrt{pq}+q<1
$$

$$
\iff \frac{p}{q}-3\sqrt{\frac{p}{q}}+1<\frac{1}{q}
$$

令$t=\frac{p}{q}<\in(\frac{1}{2},1)$,
$$
\iff (t-\frac{3}{2})^2 (\in(\frac{1}{4},1))< \frac{5}{4}+\frac{1}{q}
$$
再看$(*)$式
$$
\mid \frac{k}{d}-\frac{e}{n} \mid = \mid \frac{k}{d}-\frac{e}{\varphi(n)}\frac{\varphi(n)}{n}\mid
$$
利用
$$
\frac{e}{\varphi(n)}-\frac{k}{d}=\frac{1}{d\varphi(n)}
$$
有
$$
\mid \frac{k}{d}-\frac{e}{n} \mid = \mid \frac{k}{d}-(\frac{k}{d}+\frac{1}{d\varphi(n)})\frac{\varphi(n)}{n}\ \mid=\mid \frac{k}{d}(1-\frac{\varphi(n)}{n}-\frac{1}{kn}) \mid
$$
而由$n-3\sqrt{n}<\varphi(n)<n$知$1-\frac{3}{\sqrt{n}}<\frac{\varphi(n)}{n}<1$，从而
$$
\mid \frac{k}{d}-\frac{e}{n} \mid < \mid \frac{k}{d}\frac{3}{\sqrt{n}} \mid =\frac{3k}{d\sqrt{n}}
$$
由$RSA$原理知，$ed=k\varphi(n)+1>k\varphi(n)$且$e<\varphi(n)$，从而$k<d<\frac{1}{3}n^{\frac{1}{4}}$，故
$$
\mid \frac{k}{d}-\frac{e}{n} \mid <\frac{3k}{d\sqrt{n}} < \frac{1}{dn^{\frac{1}{4}}}<\frac{1}{2d^2}
$$
由勒让德理论$(Legendre’s\ theorem)$，若$|\alpha-\frac{a}{b}|<\frac{1}{2b^2}$，其中$\alpha $为分数，$a、b$为不互质的正整数，那么$\frac{a}{b}$为$\alpha$的一个收敛分数。

以下为勒让德理论的证明。

勒让德理论

在证明前首先证明两个定理

定理1

连分数提供了实数$\alpha$和整数序列$a_0,a_1,\cdots,(a_i\geq1,i>0)$之间的一一映射。整数序列终止当且仅当$\alpha$是一个有理数，此时$\alpha=[a_0;a_1,\cdots,a_n],a_n>1$。

连分数表示为以下形式
$$
a_0 + \frac {1}{a_1 + \frac {1}{a_2 + \frac {1}{… + \frac {1}{a_n}}}}
$$
通常也写成$a_0+\frac{1}{a_1+}\frac{1}{a_2+}\cdots\frac{1}{a_n}$或者$[a_0;a_1,a_2,\cdots,a_n]$。其中$a_0 \in Z$，$a_1,\cdots,a_n$是正整数，通常认为$a_n>1$。显然任何有限连分数都表示一个有理数。相反地，如果$(b_0,r_0)=1$那么由辗转相除法可以得到
$$
b_0=a_0r_0+r_1,\ \ 0\leq r_1<r_0
$$

$$
r_0=a_1r_1+r_2,\ \ 0\leq r_2<r_1
$$

$$
r_1=a_2r_2+r_3,\ \ 0\leq r_3<r_2
$$

$$
\cdots
$$

上述过程必定在有限步终止于
$$
r_{n-1}=a_nr_n
$$
现在
$$
\begin{aligned}
\frac{b_0}{r_0}
&= a_0+\frac{r_1}{r_0}=a_0+\frac{1}{\frac{r_0}{r_1}}\newline
&= a_0+\frac{a_1}{\frac{r_2}{r_1}}\newline
&= [a_0;a_1,a_2,\cdots,a_n]
\end{aligned}
$$
这个过程表明了有理数$\frac{b_0}{r_0}$和有限序列$a_0,a_1,\cdots,a_n(a_1\geq1,\cdots,a_{n-1}\geq1,a_n>1)$之间一一对应的关系。

在证明无理数情形前，先证明两个引理

引理1

考虑
$$
p_{-2}=0,p_{-1}=1,p_m=a_mp_{m-1}+p_{m-2}\ \ (m\geq0)
$$

$$
q_{-2}=1,q_{-1}=0,q_m=a_mq_{m-1}+q_{m-2}\ \ (m\geq0)
$$

那么$p_m$和$q_m$是以$a_0,\cdots,a_m$为系数的多项式，它们具有如下关系
$$
p_mq_{m-1}-p_{m-1}q_m=(-1)^{m-1}\ \ (m\geq-1)
$$
以下用归纳法证明。对于$m=-1$和$m=0$显然成立，假设对$m-1$成立，那么
$$
\begin{aligned}
p_mq_{m-1}-p_{m-1}q_m
&= (a_mp_{m-1}+p_{m-2})q_{m-1}-p_{m-1}(a_mq_{m-1}+q_{m-2})\newline
&= -(p_{m-1}q_{m-2}-p_{m-2}q_{m-1})=-(-1)^{m-2}\newline
&= (-1)^{m-1}
\end{aligned}
$$

引理2

$$
[a_0;a_1,a_2,\cdots,a_m]=\frac{p_m}{q_m}\ \ (m\geq0)
$$

对$m=0$来说是显然的，假设对$m-1$成立，那么
$$
\begin{aligned}
\left[a_0;a_1,a_2,\cdots,a_m\right]
&= \left[a_0;a_1,\cdots,a_{m-1}+\frac{1}{a_m}\right]\newline
&= \frac{p_{m-1}^{‘}}{q_{m-1}^{‘}}\newline
&= \frac{(a_m-1+\frac{1}{a_m})p_{m-2}+p_{m-3}}{(a_m-1+\frac{1}{a_m})q_{m-2}+q_{m-3}}\newline
&= \frac{a_{m}(a_{m-1}p_{m-2}+p_{m-3})+p_{m-2}}{a_{m}(a_{m-1}q_{m-2}+q_{m-3})+q_{m-2}}\newline
&= \frac{a_mp_{m-1}+p_{m-2}}{a_mq_{m-1}+q_{m-2}}\newline
&= \frac{p_m}{q_m}
\end{aligned}
$$
其中，$p_{m-1}^{‘}$和$q_{m-1}^{‘}$以$a_0,a_1,\cdots,a_{m-2},a_{m-1}+\frac{1}{a_m}$为多项式系数。

假设$\alpha$是一个无理数。令$a_0=[\alpha],\alpha=a_0+\frac{1}{\alpha_1}$，那么$\alpha_1>1$；令$a_1=[\alpha_1],\alpha_1=a_1+\frac{1}{\alpha_2}$，重复上述过程，我们得到$\alpha=[a_0;a_1,a_2,\cdots,a_{n-1},\alpha_n]$，这里定义了整数序列$a_0,a_1>0,a_2>0,\cdots$，实数序列$\alpha_1,\alpha_2,\cdots>1$，以及相应的整数$p_n,q_n$。下证$\frac{p_n}{q_n}\rightarrow\alpha$

首先观察
$$
\begin{aligned}
\frac{p_n}{q_n}
&= a_0+\sum_{m=1}^{n}\left(\frac{p_m}{q_m}-\frac{p_{m-1}}{q_{m-1}}\right)\newline
&= a_0+\sum_{m-1}^{n}\frac{(-1)^{m-1}}{q_{m-1}q_m}
\end{aligned}
$$
$q_i>0(i\geq1)$并且严格单调递增$(q_m-q_{m-1}=(a_m-1)q_m-1+q_{m-2}>0)$，因此$q_i\rightarrow \infin$（事实上$q_i\geq f_i$，$f_i$为斐波那契数列，这由递推式易知，从而$q_i> c^i,c>1$）。因此，由莱布尼茨判别法知级数收敛，从而$\frac{p_n}{q_n}$收敛。并且
$$
\alpha=\frac{p_{n+1}}{q_{n+1}}=\frac{\alpha_{n+1}p_n+p_{n-1}}{\alpha_{n+1}q_n+q_{n-1}}
$$
因此
$$
\alpha-\frac{p_n}{q_n}=\frac{q_np_{n-1}-p_nq_{n-1}}{q_n(\alpha_{n+1}q_n+q_{n-1})}=\frac{(-1)^n}{q_n(\alpha_{n+1}q_n+q_{n-1})}
$$
由上可知$\alpha$收敛，即$\lim_{n\rightarrow \infin} p_n/q_n=\alpha$，写成
$$
\alpha=\alpha=[a_0;a_1,a_2,\cdots].
$$
相反地，对于整数序列，反过去构造即对应一个无理数。

综上证毕

定理2

$||q_1\alpha||>||q_2\alpha||>\cdots,$当$0<q<q_n,$有$||q\alpha||\geq||q_{n-1}\alpha||$

首先记号$||\theta||=\underset{n\in \mathbb{Z}}{min}|\theta-n|,\theta\in R$

由
$$
\alpha-\frac{p_n}{q_n}=\frac{q_np_{n-1}-p_nq_{n-1}}{q_n(\alpha_{n+1}q_n+q_{n-1})}=\frac{(-1)^n}{q_n(\alpha_{n+1}q_n+q_{n-1})}
$$
得
$$
||q_n\alpha||=|q_n\alpha-p_n|=\frac{1}{\alpha_{n+1}q_n+q_{n-1}}
$$
$||q_n\alpha||$单调递减等价于$\alpha_{n+1}q_n+q_{n-1}$单调递增
$$
\alpha_{n+1}q_n+q_{n-1}\geq q_n+q_{n-1}=a_nq_{n-1}+q_{n-2}+q_{n-1}=(a_n+1)q_{n-1}+q_{n-2}>\alpha_nq_{n-1}+q_{n-2}
$$
前半部分证毕。

现假设$0<q<q_n$，首先证明一个引理

引理3

对$\forall$整数$p、q,$$\exists$整数$x、y$使得
$$
q=q_nx+q_{n-1}y,
$$

$$
p=p_nx+p_{n-1}y.
$$

注意到写成矩阵形式
$$
\left(
\begin{matrix}
q \newline
p
\end{matrix}
\right)
=
\left(
\begin{matrix}
q_n & q_{n-1} \newline
p_n & p_{n-1}
\end{matrix}
\right)
\left(
\begin{matrix}
x \newline
y
\end{matrix}
\right)
$$
系数矩阵行列式为$p_{n-1}q_n-p_nq_{n-1}=(-1)^n$，因此$p、q$为整数等价于$x、y$为整数。

①$x=0,$则$q\alpha-p=y(q_{n-1}\alpha-p_{n-1}),$从而$|q\alpha-p|=|y||q_{n-1}\alpha|\geq|q_{n-1}\alpha|$

②$y=0,$则$q=q_nx\geq q_n,$矛盾！

③$x,y\neq0$，由$0<q=q_nx+q_{n-1}y<q_n$易知$xy$异号。而$q_n\alpha-p_n=\frac{(-1)^n}{\alpha_{n+1}q_n+q_{n-1}}$,$q_{n-1}\alpha-p_{n-1}=\frac{(-1)^{n-1}}{\alpha_nq_{n-1}+q_{n-2}}$,因此$q_n\alpha-p_n$与$q_{n-1}\alpha-p_{n-1}$异号，从而$(q_n\alpha-p_n)x$与$(q_{n-1}\alpha-p_{n-1})y$同号。因此
$$
\begin{aligned}
||q\alpha||=|q\alpha-p|
&=|(q_n\alpha-p_n)x-(q_{n-1}\alpha-p_n)y|\newline
&=|(q_n\alpha-p_n)||x|+|(q_{n-1}\alpha-p_n)||y|\newline
&=||q_n\alpha|||x|+||q_{n-1}\alpha|||y|\geq||q_n\alpha||
\end{aligned}
$$
综上，证毕。

Legendre

若$|\alpha-\frac{p}{q}|<\frac{1}{2q^2}$，且$(p,q)=1$，那么$\exists n,st\ q_n=q$

选取$n，st\ q_n\leq q < q_{n+1}$，由于$pq_n-qp_n=q(\alpha q_n-p_n)-q_n(q\alpha-p)$，有三角不等式
$$
|pq_n-qp_n|\leq q||q_n\alpha||+q_n||q\alpha||
$$
由定理2知$||q_n\alpha||\leq||q\alpha||$，从而
$$
|pq_n-qp_n|\leq q||q\alpha||+q||q\alpha||=2q^2|\alpha-\frac{p}{q}|<1
$$
因此$pq_n-qp_n=0$，而$(p_n,q_n)=(p,q)=1$，因此$q=q_n$。证毕。

算法实现

简单分析可以知道维纳攻击的时间复杂度是$O(logn)$,关键就在于辗转相除法法那一步。

from gmpy2 import iroot

def continuedFraction(x, y):
    ret = []
    while y:
        ret.append(x // y)
        x, y = y, x % y
    return ret

def cal(fraction):
    list = fraction
    list.reverse()
    d = 0
    k = 1
    for x in list:
        d, k = k, x * k + d
    return (d, k)

def getFraction(x, y):
    fraction = continuedFraction(x, y)
    length = len(fraction)
    ret = []
    for i in range(1, length):
        ret.append(cal(fraction[0: i]))
    return ret

def solve(a, b, c):
    delta = iroot(b * b - 4 * a * c, 2)[0]
    return (-b + delta) // (2 * a), (-b - delta) // (2 * a)

def wienerAttack(e, n):
    ret = getFraction(e, n)
    for (d, k) in ret:
        if k == 0: continue
        if (e * d - 1) % k != 0: continue
        phi = (e * d - 1) // k
        p, q = solve(1, -(n - phi + 1), n)
        if p * q == n:
            print(d)
            return