扩展维纳攻击
Last updated
Last updated
扩展维纳攻击来自，相关题目在CTF中已经出现了，例如2020羊城杯的Simple，但都是一些模板题，这里将详细分析原论文中提出的方法以及分析方式，写明扩展维纳攻击原理以及在文末给出了一些开放问题欢迎讨论。
维纳Wiener提出了一种关于私钥过小时对$N$进行分解的一种方式。并给出了证明当
满足时(还应满足$q < p < 2q$，因这里及后文主要是对私钥进行探讨，故忽略这类条件)一定能够分解$N$。
以下为原论文中对于Wiener's Approach的部分描述，部分内容有删减，其实这里也就是维纳攻击的证明，所以要想更详细了解请再看维纳攻击的原理，这里我们主要后面要用到这里的式1。方法如下
已知
这里$\lambda(N) = lcm(p-1, q-1) = \varphi(N) / g$，令$s = 1-p-q$则有
将两边同时除以$dgN$则有
我们知道这里有$e \approx N, s \approx N^{1/2}$，所以有$k/(dg)\approx 1$。则我们可以知道等式右边约等于$N^{-1/2}$。我们都知道当
时则$a/b$是一个$x$连分数近似（连分数定理Continued Fractions）
所以当
时有$k/dg$是$e/N$的连分数近似，即能通过连分数展开覆盖。
注意这里前面所说的范围和后面的范围并不矛盾
这里对一些参数的值的近似并不严格，所以和维纳攻击的严格范围有出入，具体细节可参考维纳攻击的证明。
郭针对不止一个$e$的情况进行研究，但是郭只研究了两个以及三个$e$的情况，上上节一样，这里我们还是使用原文内容翻译+解释的写法。对于两个$e$的情况，我们可以考虑
简单化简可以得到下式子
两边同时除以$k_2d_1e_2$
设$d_i < N^\alpha$，则等式右边约等于$N^{-(1+\alpha)}$
则当
时$k_1d_2/(k_2d_1)$是$e_1/e_2$的连分数近似。当$k_2$和$d_1$最多为$N^\alpha$而且$g$很小时，得到
然而即使我们得到了$(k_1d_2)/(k_2d_1)$还是无法分解$N$，原文后面还讨论了郭的提议，尝试对$k_1d_2$进行分解，这里不再讲解。
上述部分内容截至目前（2021/10）网络上已经有很多博文进行了讲解了分析，但是对于具体扩展维纳攻击的原理以及格构造或者是更高维的推广都没有给出。这里我将详细的对原论文内容进行翻译以及讲解。
为了将分析扩展到$n$个加密指数$e_i$（解密指数$d_i$很小），我们同时使用维纳和郭的方法，我们将关系
记为维纳等式$W_i$，同样我们可以得到关系
记为郭等式$G_{i,j}$。
我们假设$d_i$和$k_i$都小于$N^{\alpha_n}$，且$g$很小，$s \approx N^{1/2}$。可以注意到$W_i$和$G_i$的右侧非常小，实际上分别最多为$N^{1/2 + \alpha}$和$N^\alpha$。
最后，我们考虑复合关系式比如$W_uG_{v,w}$，显然大小为$N^{1/2 + 2\alpha}$。
原文中这里是定义了两个关系式以及指出了他们的大小范围，这个范围很重要也容容易分析处理，之后我们所做的其实就是使用这两个式子的不同复合关系去构造一个格，然后通过求其基向量得到$d_1g/k_1$，从而可以算得$\varphi(N)$并可以进一步的对$N$进行分解。
其实到这里原理分析已经结束，关于格的构造其实也并不复杂，但是核心是这里的复合关系的选取，以及对于最后$\alpha$大小的分析。
我们选取关系$W_1, G_{1,2},W_1W_2$,这样便有
我们对第一个关系式乘上$k_2$，这样左边便全是由$d_1d_2g^2, d_1gk_2, d_2gk_1$和$k_1k_2$构成，这样我们便可以用已知内容构造格将上述式子转化为矩阵运算
等式右边向量的大小为$N^{2\alpha_2}, N^{1/2+2\alpha_2}, N^{\alpha_2}, N^{1+2\alpha_2}$,为了让大小相等，我们可以考虑构造一个D矩阵。
最终我们构造的矩阵为
这样向量$b = \begin{pmatrix} k_1k_2&d_1gk_2&d_2gk_1&d_1d_2g^2 \end{pmatrix}$便有
这也就是为什么前面需要构造$D$矩阵的原因，给定$D$矩阵后，我们可以得到一个上界，这样问题可以转化为类SVP问题。
那么这里的b向量其实我们使用格基规约算法例如LLL便可以得到基向量$b$，然后我们求解$b_2/b_1$即得到$d_1g/k_1$
之后我们就可以得到
我们假设这些格中最短向量长度为$\Delta^{1/4-\epsilon}$，其中$\Delta = det(L_2) = N^{13/2 + \alpha_2}$。如果这些格是随机的，我们甚至几乎可以肯定没有格点比闵可夫斯基界（Minkowski's bound）$2\Delta^{1/4}$，所以$bL_2$是最短向量当
对于一些小的$c_2$，如果有
则我们可以通过格基规约找到向量$b$。
上述内容是原文中给出的当两个小解密指数是进行的攻击细节，并且分析了$\alpha$的大小关系。
对于三个指数的情况我们额外选取$G_{1, 3}, W_1G_{2, 3}, W_2G_{1,3}$
这样我们的向量b为
L_3 = \left(\begin{array}{rrrrrrrr} 1 & -N & 0 & N^{2} & 0 & 0 & 0 & -N^{3} \ 0 & e_{1} & -e_{1} & -N e_{1} & -e_{1} & 0 & N e_{1} & N^{2} e_{1} \ 0 & 0 & e_{2} & -N e_{2} & 0 & N e_{2} & 0 & N^{2} e_{2} \ 0 & 0 & 0 & e_{1} e_{2} & 0 & -e_{1} e_{2} & -e_{1} e_{2} & -N e_{1} e_{2} \ 0 & 0 & 0 & 0 & e_{3} & -N e_{3} & -N e_{3} & N^{2} e_{3} \ 0 & 0 & 0 & 0 & 0 & e_{1} e_{3} & 0 & -N e_{1} e_{3} \ 0 & 0 & 0 & 0 & 0 & 0 & e_{2} e_{3} & -N e_{2} e_{3} \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & e_{1} e_{2} e_{3} \end{array}\right)
D = diag(\begin{array}{r} N^{\frac{3}{2}}&N&N^{a + \frac{3}{2}}&\sqrt{N}&N^{a + \frac{3}{2}}&N^{a + 1}&N^{a + 1}&1\end{array})
\Vert bL_2 \Vert < \sqrt{8}N^{3/2+2\alpha_3}
额外选取$G_{1, 4}, W_1G_{2, 4}, G_{1, 2}G_{3,4}, G_{1, 3}G_{2, 4}, W_1W_2G_{3, 4}, W_1W_3G_{2, 4}, W_2W_3G_{1, 4}, W_1W_2W_3W_4$进行构造。不再翻译。
扩展维纳攻击结合上述三个例子已经详细的阐明了方法细节，但是其中没有讲解如何选取复合关系。其实在原文的附录中给出了复合关系的选取，以及给出了$\alpha_n$的表达式。
在原文附录部分，考虑$n$个指数$e_i$，这样则有$2^n$个不同的量$h_j$（一个表达式$e_i$的个数），这样我们的$L_n$在乘上$D$之前，矩阵$L_n$的行列式为$N^{n2^{n-1}}$
这样最后一个关系$W_1W_2\dots W_n$最大为$N^{n/2 + n\alpha_n}$，这样我们便知道了任意情况的最大界值，我们只需要让其他值增加到这么多即可（即构造$D$矩阵）
引入了新的关系式
其中$i_1,\dots,i_u,j_1,\dots,j_u,l_1,\dots,l_v$都不同，那么这里最多会有$u + 2v$个指数$e_i$，则我们的关系$R_{u,v}$最多为$N^{u/2 + (u+v)\alpha_n}$，同时注意我要需要所有系数的大小大致相同，所以我们在某些等式乘上$k_i$，使得关系$R_{u, v} = N^{u/2 + (n-v)\alpha_n}$。
最后我们再计算所有的大小与最大大小$N^{n/2 + n\alpha_n}$的差值，构造矩阵$D$。
这样我们便完成了矩阵$D$的构造，同时设矩阵$D$里面指数的乘积为$\beta_n = x+y\alpha_n$，这样有
则有
对于小$c_n$，有
所以我们要想让$\alpha_n$更大就需要让$x$和$y$更大，这意味着我们要选取更多的$v$和更小的$u$。比如在$n=2$的情况我们选取$W_1, G_{1, 2}, W_1W_2$而不是$W_1, W_2, W_1W_2$因为前者$\beta_2 = 5/2 + \alpha$而后者$\beta_2 = 2$。
到这里，其实已经讲清楚了扩展维纳攻击的整个流程，如何选择复合关系，如何构造格，如何构造矩阵$D$以及如何求解。在原文的文末也给出了$n\le 5$时候的选择关系表。
这里我也给出$n\le8$的选择关系以及$n=6$时候构造的矩阵以供验证自己是否能够编写出选择关系式的逻辑代码。
对于现在扩展维纳的问题都是$n=2$或者是$n=3$时候的模板题，对于更高维的情况，可以编写自动化的脚本来完整自动选择关系、自动构造格等步骤，比如上述内容就是自动生成的。但是对于$n$每增加1，矩阵则是指数倍增加，因为这是一个$2^n * 2^n$的矩阵，这时候直接调用sagemath中的LLL()变得非常缓慢，大约$n=8$的情况已经运行不出来了，我曾尝试寻找LLL在CUDA上的并行算法或是一些其他优化方案实现，但是都是找到了论文没有给出源码的情况。
考虑到不是每个人都需要深入研究扩展维纳攻击，这里还是给出$n=2$时候的EXP以供使用
如果您对这方面有所研究或者有什么更好的优化方法，欢迎联系我（）一起进行更加深入的探讨。
