Wiener's Attack Ride(维纳攻击法驾驭)
背景
在刷BUU的时候碰到了[羊城杯 2020]RRRRRRRSA运用了连分数求解，而Wiener's Attack（维纳攻击法）也是利用连分数来求解。但是网上的文章总是停留在对Wiener's Attack的应用层面（在碰到这道题之前，我对Wiener's Attack的运用也只停留在抄代码的层面），并没有对其中的具体步骤进行证明和推导
本文试图深挖其中的原理，并对其中的步骤进行较为完整的证明和解释
关于RSA密码体系
关于RSA的介绍网上多的是，这里不再赘述\(^{[1]}\) 
不知道RSA的话，就更别说Wiener's Attack了
Wiener's Attack简介（Wiener's theorem）\(^{[2]}\)
模数\(N=pq\)，其中\(q<p<2q\)
若\(d<\dfrac{1}{3}N^{\frac{1}{4}}\) 时，给定公钥\((N,e)\)，且\(ed \equiv 1\space mod \space \lambda (N)\)，
\(\lambda (N) = lcm(p-1,q-1)=\dfrac{(p-1)(q-1)}{G} = \dfrac{\varphi(N)}{G}\)，其中\(G=gcd(p-1, q-1)\)
那么可以有效地得到公钥指数\(d\)
这里与我们常见的RSA加密不同的是使用了\(\lambda (N)\)而非\(\varphi (N)\)，两者就差了个整数\(G\)，其实是差不多的，在以下的Wiener's Attack原理和证明中可以看出
Wiener's Attack原理
设\(\lambda (N) = lcm(p-1,q-1)=\dfrac{(p-1)(q-1)}{G} = \dfrac{\varphi(N)}{G}\)，其中\(G=gcd(p-1, q-1)\)
因为 \[ ed \equiv 1\space mod \space \lambda (N) \] 所以\(\exists K\in \mathbb{Z}\)，\(s.t.\) \[ ed = K\lambda (N) +1 = \dfrac{K}{G}(p-1)(q-1) + 1 \] 令\(k = \dfrac{K}{gcd(K,G)}\)，\(g = \dfrac{G}{gcd(K,G)}\)，代入上式得： \[ ed = \dfrac{k}{g}(p-1)(q-1) + 1 = \dfrac{k}{g} \varphi (N) + 1 \] 上式两段同时除以\(dN\)，可得： \[ \dfrac{e}{N} = \dfrac{k}{dg} \dfrac{\varphi (N)}{N} + \dfrac{1}{dN} \cdots\cdots(*) \] 由于\(p,q\)是大整数，所以可以认为\(\varphi (N) \approx N\)，$ $，有 \[ \dfrac{e}{N} = \dfrac{k}{dg}(1-\delta) \approx \dfrac{k}{dg} \] 其中，\(\delta = \dfrac{p+q-1-\frac{g}{k}}{pq} \approx 0\)
等式左侧包含了已知的公钥信息，通过对其进行连分数展开，再对每一项求渐进分数，可以得到\(k,dg\)
再将结果代入\((*)\)式，即可求得\(\varphi (N)\)，然后就可以进行解密RSA了
如果要求\(p,q\)，由于已知\(N=pq\)，\(\varphi (N) = (p-1)(q-1)=pq-(p+q)+1\)，练习韦达定理，可以构造一元二次方程\(x^{2} - (p+q)x + pq = x^{2} - (N - \varphi (N) +1)x + N = 0\)，解出两根即为\(p,q\)
Wiener's theorem的证明
此部分用于说明：在Wiener's theorem给定的条件下，为什么使用连分数可以求解
设\(\lambda (N) = lcm(p-1,q-1)=\dfrac{(p-1)(q-1)}{G} = \dfrac{\varphi(N)}{G}\)，其中\(G=gcd(p-1, q-1)\geq 1\)
因为 \[ ed \equiv 1\space mod \space \lambda (N) \] 所以\(\exists K\in \mathbb{Z}\)，\(s.t.\) \[ ed = K\lambda (N) +1 = K\dfrac{\varphi (N)}{G} + 1 \] 等式两边同除以\(d\lambda (N)\)可得： \[ \left| \dfrac{e}{\lambda (N)} - \dfrac{K}{d} \right| = \dfrac{1}{d\lambda (N)} \] 两边再同除\(G\)可得： \[ \left| \dfrac{e}{\varphi (N)} - \dfrac{K}{Gd} \right| = \dfrac{1}{d\varphi (N)}\cdots \cdots (**) \] 从上述推导可知，\(\dfrac{K}{Gd}\approx \dfrac{e}{\varphi (N)}\)，由于\(\varphi (N) \approx N\)，在计算的时候是可以近似替换的
因为\(q<p<2q\)，\(N=pq\)
所以\(N>\dfrac{p^2}{2}\)，故\(p<\sqrt{2N}\)
又\(N>q^2\)，故\(q<\sqrt{N}\)
因此\(p+q-1<(1+\sqrt{2})\sqrt{N}-1<3\sqrt{N}\)
又 \[ \varphi (N) = (p-1)(q-1) =N-(p+q-1) \] 故 \[ |N-\varphi (N)| = p+q-1 < 3\sqrt{N} \] 在\((**)\)式中，用\(N\)替换\(\varphi (N)\)可得： \[ \begin{split} \left| \dfrac{e}{N} - \dfrac{K}{Gd} \right| &= \left| \dfrac{edG-KN}{NGd} \right|\\ &= \left| \dfrac{edG-K\varphi (N)-KN + K\varphi (N)}{NGd} \right|\\ &= \left| \dfrac{G - K(N-\varphi(N))}{NGd} \right|\\ &= \left| \dfrac{1 - \frac{K}{G}(N-\varphi(N))}{Nd} \right|\\ \end{split} \] 由于 \[ ed = K\lambda (N) +1 = \dfrac{K}{G}\varphi (N) + 1 \] 又\(e,d,\varphi (N) \in \mathbb{N^*}\)，所以\(\dfrac{K}{G}\in \mathbb{N^*}\)，即有\(\dfrac{K}{G} \geq 1\)
而\(N-\varphi (N) = p+q-1 > 1\)
于是有 \[ \frac{K}{G}(N-\varphi(N)) > 1 \] 故 \[ \begin{split} \left| \dfrac{e}{N} - \dfrac{K}{Gd} \right| &= \left| \dfrac{\frac{K}{G}(N-\varphi(N)) - 1}{Nd} \right| = \dfrac{\frac{K}{G}(N-\varphi(N)) - 1}{Nd}\\ &< \left| \dfrac{K(N-\varphi(N))}{NGd} \right|\\ &< \left| \dfrac{3K\sqrt{N}}{NGd} \right| = \dfrac{3K}{Gd\sqrt{N}} \leq \dfrac{3K}{d\sqrt{N}} \end{split} \] 因为\(ed = K\lambda (N) +1\)，所以\(ed > K\lambda (N)\)
又根据RSA加密原理，\(e<\varphi (N) \leq \lambda (N)\)
故\(K\lambda (N)<ed<\lambda (N)d\)
于是有\(K\lambda (N)<\lambda (N)d\)
故\(K<d<\dfrac{1}{3}N^{\frac{1}{4}}\)
所以 \[ \left| \dfrac{e}{N} - \dfrac{K}{Gd} \right| < \dfrac{3K}{d\sqrt{N}} < \dfrac{1}{dN^{\frac{1}{4}}} \] 又因为\(2d<3d<N^{\frac{1}{4}}\)
所以\(\dfrac{1}{2d}>\dfrac{1}{N^{\frac{1}{4}}}\)
于是 \[ \left| \dfrac{e}{N} - \dfrac{\frac{K}{G}}{d} \right| < \dfrac{1}{dN^{\frac{1}{4}}} < \dfrac{1}{2d^2} \] 根据Legendre’s theorem\(^{[3]}\)，若\(\left| x-\dfrac{a}{b} \right| < \dfrac{1}{2b^2}\)，其中\(x\)为分数，\(a,b\)为不互质的正整数，那么\(\dfrac{a}{b}\)必为\(x\)的一个收敛分数
至于为什么（这也是很多文章没有给出的地方），将在下一部分给出较为详细的解释
关于连分数的解释
在很多介绍Wiener's Attack的文章中，忽略了关于连分数的解释，或者说为什么通过进行连分数展开，再对每一项求渐进分数，就可以得到\(d\)
为此，笔者查阅了一些文献，下面给出大致证明
首先，什么是连分数？
定义一（连分数）\(^{[4]}\)
一个有理数可以化成如下形式： \[ a_0+\frac{1}{a_1 + \frac{1}{a_2+\frac{1}{\cdots+\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 \mathbb{Z}\)，\(a_1,a_2,\cdots,a_n\in \mathbb{N^*}\)，且\(a_n>1\)\(^{[5]}\)
无限不循环小数，例如\(\pi,\sqrt{2}\)等也可以化成连分数形式，但不在本文讨论范围内，感兴趣的可以自行查阅
定理一
任何一个有理数与其连分数形式是一一对应的
证明：对于任意一个有理数\(\dfrac{b_0}{r_0}\)，且\((b_0,r_0)=1\)，可以写出 \[ \begin{split} 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 \end{split} \] 由于\(r_i\)严格单调递减，所以必定存在\(n\in \mathbb{N^*}\)，\(s.t.\) \[ r_{n-1}=a_nr_n \] 其中，\(r_i\in \mathbb{N^*}\)，\(\forall i=1,2,\cdots ,n\)
所以有 \[ \begin{split} \dfrac{b_0}{r_0} &= a_0 + \dfrac{r_1}{r_0} = a_0 + \dfrac{1}{\frac{r_1}{r_0}}\\ &= a_0 + \dfrac{1}{a_1 + \frac{1}{\frac{r_2}{r_1}}\\}\\ &=\cdots \\ &= [a_0;a_1,a_2,\cdots,a_n] \end{split} \] 上述推导说明有理数和其连分数形式是一一对应的