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} \] 上述推导说明有理数和其连分数形式是一一对应的
其次，什么是收敛分数？
定义二（收敛分数）
设有理数\(a=[a_0;a_1,a_2,\cdots,a_n]\)，则其收敛分数为\([a_0],[a_0;a_1],\cdots [a_0;a_1,a_2,\cdots,a_{n-1}],[a_0;a_1,a_2,\cdots,a_n]\)
通俗地讲，就是把连分数从某一项开始，后面的扔掉，得到\(a\)的一个近似值
由定理一可知，对于有理数，其收敛分数的个数的有限的，并且越来越逼近\(a\)
引理一
设 \[ \begin{split} p_{-2}&=0,p_{-1}&=1,p_m = a_m p_{m-1}+p_{m-2}\space (m\geq0)\\ q_{-2}&=1,q_{-1}&=0,q_m = a_m q_{m-1}+q_{m-2}\space (m\geq0) \end{split} \] 则 \(p_m q_{m-1} - p_{m-1}q_m = (-1)^{m-1}(m\geq -1)\)
证明：用数学归纳法
当\(m=-1\)或\(m=0\)时，显然成立
假设当\(m=k-1\)，\(\forall k\in \mathbb{N}\)时也成立，即\(p_{k-1} q_{k-2} - p_{k-2}q_{k-1} = (-1)^{k-2}(k\geq 0)\)
那么 \[ \begin{split} p_k q_{k-1} - p_{k-1}q_k &= (a_k p_{k-1}+p_{k-2})q_{k-1} - p_{k-1}(a_k q_{k-1}+q_{k-2})\\ &= -(p_{k-1} q_{k-2} - p_{k-2}q_{k-1})\\ &= -(-1)^{k-2} = (-1)^{k-1} \end{split} \] 所以，当\(m=k\)时也成立
证毕
引理二
\[ [a_0;a_1,a_2,\cdots,a_m] = \frac{p_m}{q_m}\space (m\geq 0) \]
证明：用数学归纳法
当\(m=0\)时，易证
假设当\(m=k-1\)，\(\forall k\in \mathbb{N^*}\)时也成立，即\([a_0;a_1,a_2,\cdots,a_{k-1}] = \dfrac{p_{k-1}}{q_{k-1}}\space (k\geq 1)\)
那么 \[ \begin{split} [a_0;a_1,a_2,\cdots,a_{k}] &= [a_0;a_1,a_2,\cdots,a_{k-1}+\frac{1}{a_k}] \\ &= \dfrac{(a_{k-1} + \frac{1}{a_k})p_{k-2}+p_{k-3}}{(a_{k-1} + \frac{1}{a_k})q_{k-2}+q_{k-3}}\\ &= \dfrac{(a_k a_{k-1} + 1)p_{k-2}+a_k p_{k-3}}{(a_k a_{k-1} + 1)q_{k-2}+a_k q_{k-3}}\\ &= \dfrac{a_k(a_{k-1}p_{k-2} + p_{k-3})+p_{k-2}}{a_k(a_{k-1}q_{k-2} + q_{k-3})+q_{k-2}}\\ &= \dfrac{a_k p_{k-1}+p_{k-2}}{a_k q_{k-1}+q_{k-2}}\\ &= \dfrac{p_k}{q_k} \end{split} \] （这里把\([a_0;a_1,a_2,\cdots,a_{k}]\)等价为\([a_0;a_1,a_2,\cdots,a_{k-1}+\frac{1}{a_k}]\)，相当于把\(k\)阶的连分数，视作\(k-1\)阶，这样就可以应用假设了）
所以，当\(m=k\)时也成立
证毕
引理三
规定：\(||\theta|| = \displaystyle\min_{n\in \mathbb{Z}}|\theta - n|\)，\(\theta \in \mathbb{R}\)
设\(\alpha = [a_0;a_1,a_2,\cdots,a_{n+1}]\)，其中\(n\in \mathbb{N^*}\)，\(a_i\geq 1\)，\(1\leq i \leq n+1\)则\(||q_i \alpha||\)严格单调递减，且\(||q_1 \alpha|| > ||q_2 \alpha|| > \cdots >||q_n \alpha|| > ||q_{n+1} \alpha||=0\)
证明：由连分数的定义， \[ \begin{split} [a_0;a_1,a_2,\cdots,a_n] &= a_0 + [a_1;a_2,a_3,\cdots,a_n]\\ &= a_0 + a_1 + [a_2;a_3,a_4,\cdots,a_n]\\ &= \cdots\\ &= a_0 + a_1 +\cdots + [a_n]\\ &= a_0 + \sum\limits_{i=1}^{n}([a_i;a_{i+1},a_{i+2},\cdots,a_{n}] - [a_{i-1};a_{i},a_{i+1},\cdots,a_{n}]) \end{split} \] 根据引理二，\([a_0;a_1,a_2,\cdots,a_{i}] = \dfrac{p_i}{q_i}\)，\(\forall i\in \{2, 3, \cdots ,n+1\}\)
故 \[ \begin{split} \dfrac{p_n}{q_n} &= a_0 + \sum\limits_{i=1}^{n}(\dfrac{p_i}{q_i} - \dfrac{p_{i-1}}{q_{i-1}})\\ &= a_0 + \sum\limits_{i=1}^{n}\dfrac{p_i q_{i-1} - p_{i-1}q_i}{q_i q_{i-1}} \end{split} \] 又根据引理一，\(p_i q_{i-1} - p_{i-1}q_i = (-1)^{i-1}\)
故 \[ \begin{split} \dfrac{p_n}{q_n}&= a_0 + \sum\limits_{i=1}^{n}\dfrac{p_i q_{i-1} - p_{i-1}q_i}{q_i q_{i-1}}\\ &= a_0 + \sum\limits_{i=1}^{n}\dfrac{(-1)^{i-1}}{q_i q_{i-1}} \end{split} \] 又因为\(\alpha = \dfrac{p_{n+1}}{q_{n+1}} = \dfrac{a_{n+1}p_n + p_{n-1}}{a_{n+1}q_n + q_{n-1}}\)
于是 \[ \alpha - \dfrac{p_n}{q_n} = \dfrac{q_n p_{n-1} - p_n q_{n-1}}{(a_{n+1}q_n + q_{n-1})q_n} = \dfrac{(-1)^{n}}{(a_{n+1}q_n + q_{n-1})q_n} = \dfrac{(-1)^{n}}{q_n q_{n+1}}\cdots\cdots(***) \] 由于\(a_{n+1},q_n,q_{n-1}\geq 1\)，所以\(\left| \dfrac{(-1)^{n}}{a_{n+1}q_n + q_{n-1}} \right| \leq \dfrac{1}{2}\)
因此 \[ ||q_n \alpha|| = |q_n \alpha - p_n| = \dfrac{1}{a_{n+1}q_n + q_{n-1}} \] 因为\(a_i\geq 1\)，\(1\leq i \leq n+1\)
所以 \[ \begin{split} a_{n+1}q_n + q_{n-1} &\geq q_n + q_{n-1} \\ &= a_n q_{n-1} + q_{n-2} + q_{n-1}\\ &= (a_n +1)q_{n-1} + q_{n-2} \\ &> a_n q_{n-1} + q_{n-2} \end{split} \] 所以，\(a_{i+1}q_i + q_{i-1}\)严格单调递增
因此，\(||q_i \alpha||\)严格单调递减
又\(\alpha = \dfrac{p_{n+1}}{q_{n+1}}\)，故\(\alpha q_{n+1} = p_{n+1} \in \mathbb{Z}\)
于是，\(||\alpha q_{n+1}|| = |\alpha q_{n+1} - p_{n+1}| = 0\)
证毕
定理二
由引理三，\(||q_1 \alpha|| > ||q_2 \alpha|| > \cdots >||q_n \alpha|| > ||q_{n+1} \alpha||=0\)，则当\(0<q<q_n\)时，\(||q \alpha||\geq ||q_{n-1} \alpha||\)，其中\(n\in \mathbb{N^{*}}\)
证明：我们先证明一个引理：
当\(0<q<q_n\)时，对于正整数\(q,p\)，总\(\exists x,y \in \mathbb{Z}\)，\(s.t.\) \[ \begin{cases} q = q_n x + q_{n-1}y\\ p = p_n x + p_{n-1}y \end{cases} \] 也可以化成矩阵形式： \[ \begin{pmatrix} q\\ p \end{pmatrix} = \begin{pmatrix} q_n & q_{n-1}\\ p_n & p_{n-1} \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} \] 由于 \[ \begin{vmatrix} q_n & q_{n-1}\\ p_n & p_{n-1} \end{vmatrix} =p_{n-1}q_n - p_n q_{n-1}= (-1)^{n} \] 所以，$ \[\begin{pmatrix}q \\ p\end{pmatrix}\] \[\begin{pmatrix}x \\ y\end{pmatrix}\]$
亦即，该映射为双射
引理得证
①当\(x=0\)时，则\(q\alpha - p = y(q_{n-1}\alpha - p_{n-1})\)，所以\(|q\alpha - p| = |y||q_{n-1}\alpha - p_{n-1}| = |y|||q_{n-1}\alpha|| \geq ||q_{n-1}\alpha||\)
②当\(y=0\)时，则\(q=q_n x \geq q_n\)与假设矛盾，排除
③当\(x,y\)均不为\(0\) 时，
因为\(q = q_n x + q_{n-1}y < q_{n}\)
又\(q, q_n, q_{n-1} \in \mathbb{N^*}\)
所以\(x,y\)异号
由\((***)\)式可得， \[ \begin{cases} q_n \alpha - p_n = \dfrac{(-1)^n}{a_{n+1}q_n + q_{n-1}}\\ q_{n-1} \alpha - p_{n-1} = \dfrac{(-1)^{n-1}}{a_{n}q_{n-1} + q_{n-2}} \end{cases} \] 因此，\(q_n \alpha - p_n\)与\(q_{n-1} \alpha - p_{n-1}\)也异号
所以，\((q_n \alpha - p_n)x\)与\((q_{n-1} \alpha - p_n)y\)同号
于是， \[ \begin{split} |q\alpha - p| &= |(q_n \alpha - p_n)x - (q_{n-1} \alpha - p_n)y|\\ &= |x||q_n \alpha - p_n| + |y||q_{n-1} \alpha - p_n|\\ &= |x|||q_n \alpha|| + |y|||q_{n-1} \alpha|| \geq ||q_n \alpha|| \end{split} \] 综上所述，
当\(0<q<q_n\)时，\(||q \alpha||\geq ||q_{n-1} \alpha||\)
证毕
经过以上"铺垫"，终于到了我们要讲的核心部分Legendre’s theorem
定理三（Legendre’s theorem）
若\(|\alpha - \dfrac{p}{q}| < \dfrac{1}{2q^2}\)且\((p,q)=1\)，则\(q = q_k\)，\(k \in \{1, 2, \cdots n+1\}\)
证明：选择一个\(n\)，满足\(q_n \leq q < q_{n+1}\)
因为\(pq_n - qp_n = q(\alpha q_n - p_n)-q_n(q\alpha - p)\)
由三角不等式可得： \[ \begin{split} |pq_n - qp_n| &\leq |q||\alpha q_n - p_n|+|q_n||q\alpha - p|\\ &\leq q||q_n \alpha||+q_n||q\alpha|| \end{split} \] 又由定理二可知，\(||q \alpha||\geq ||q_{n-1} \alpha||\)
所以 \[ |pq_n - qp_n| \leq 2q||q\alpha|| = 2q^2 \left|\alpha-\frac{p}{q} \right| < 1 \] 而\(p,q_n, q,p_n \in \mathbb{N}\)
于是，\(pq_n - qp_n = 0\)，即\(\dfrac{p}{q} = \dfrac{p_n}{q_n}\)
又因为\((p_n, q_n) = (p,q) = 1\)
所以有\(p = p_n\)
证毕
关于此定理的范围，事实上可以进一步拓展，本文不再拓展，感兴趣的可以自行查阅
参考文献
[1] D001UM3. CTF中RSA题型解题思路及技巧 [DB/OL]. Reebuf; 2018 Feb 20, 15:00:31.Available from:https://www.freebuf.com/articles/others-articles/161475.html
[2] Wikipedia contributors. Wiener's attack [DB/OL]. Wikipedia, The Free Encyclopedia; 2021 Apr 30, 15:51 UTC [cited 2021 Aug 17]. Available from: https://en.wikipedia.org/w/index.php?title=Wiener%27s_attack&oldid=1020703748.
[3] Andrej Dujella. Continud Fractions And RSA With Small Secret Exponent[DB/OL]. Arxiv; 2004 Feb. Available from:https://arxiv.org/pdf/cs/0402052.pdf
[4] 维基百科编者. 连分数[G/OL]. 维基百科, 2021(20210502)[2021-05-02]. https://zh.wikipedia.org/w/index.php?title=%E8%BF%9E%E5%88%86%E6%95%B0&oldid=65444935.
[5] Unknown. Continud Fractions[DB/OL]. Unkown. Available from:http://personal.psu.edu/rcv4/677C02.pdf
结语
终于肝完了 