文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载扩展维纳攻击是维纳Wiener连分数攻击在存在多个小解密指数场景下的一般化推广源自密码学论文《Extending Wieners Attack in the Presence of Many Decrypting Exponents》近年在 CTF 中以 2020 羊城杯「Simple」等题目形式出现。本文以 CTF-Wiki 中 扩展维纳攻击文档 为骨架逐条推导维纳/郭Guo两类前置方法的数学基础详细展开两个、三个乃至 n 个小解密指数场景下复合关系式的选取、格lattice与对角矩阵 D 的构造、α 上界分析并给出可直接运行的 n2 SageMath EXP读完后你不仅能复现模板题还能理解如何将攻击推广到更高维。背景从单私钥到多私钥的攻击演进RSA 的私钥 $d$ 是满足 $ed \equiv 1 \pmod{\varphi(N)}$ 的整数其中 $\varphi(N)(p-1)(q-1)$见 RSA 基本理论。当 $d$ 过小时攻击者可以利用维纳Wiener攻击在 私钥 d 相关攻击 一节中给出的经典条件是 $d\frac{1}{3}N^{\frac{1}{4}}$此时可通过连分数展开在多项式时间内恢复 $d$。相关现成工具有rsa-wiener-attack、owiener等。但现实中常出现更复杂的情形同一模数 $N$ 下存在多个加密指数 $e_i$每个对应的解密指数 $d_i$ 都很小。单私钥的维纳攻击不再适用而「扩展维纳攻击」正是为此设计——它同时结合了维纳的连分数思想和郭Guo对多指数场景的处理最终通过构造格并做 LLL 格基规约恢复出 $\varphi(N)$从而分解 $N$、还原明文。原理分析之一维纳的方法——连分数逼近的起点维纳给出的经典结论是当私钥满足$$ d \frac{1}{3}N^{\frac{1}{4}} $$严格证明还需 $q p 2q$本文因只关注私钥讨论故略去这类条件时一定可以分解 $N$。其证明思路是扩展维纳攻击的基石尤其是下文要反复使用的式 1。已知$$ ed - k\lambda(N) 1 $$其中 $\lambda(N) \mathrm{lcm}(p-1, q-1) \varphi(N) / g$令 $s 1-p-q$则可以得到$$ edg - kN g ks\tag{1} $$两边同时除以 $dgN$$$ \frac{e}{N} - \frac{k}{dg} \frac{gks}{dgN} \left(\frac{k}{dg}\right)\left(\frac{s}{N}\right) \frac{1}{dN} $$这里 $e \approx N$、$s \approx N^{1/2}$所以 $k/(dg)\approx 1$等式右边约等于 $N^{-1/2}$。根据连分数定理Continued Fractions当$$ |x - a/b| 1/(2b^2) $$时$a/b$ 是 $x$ 的一个连分数渐近近似。因此当$$ d \frac{\sqrt{2}}{2g}N^{\frac{1}{4}} $$时$k/dg$ 是 $e/N$ 的连分数近似即可以通过对 $e/N$ 做连分数展开覆盖到 $k/dg$。注意此处对参数取值的近似并不严格与维纳攻击的严格界 $\frac{1}{3}N^{1/4}$ 有出入具体细节可参考维纳攻击的完整证明。两个范围并不矛盾。格视角的衔接连分数本身与格基规约有着深刻联系——格基规约算法 一节指出LLL 算法可以找到满足 $\Vert b_1\Vert \leq 2^{\frac{n-1}{4}}(\det L)^{\frac{1}{n}}$ 的短向量其典型应用正是找到 n 个实数 $\alpha_i$ 的有理线性逼近这与维纳用连分数逼近 $e/N$ 的数学结构同源。扩展维纳攻击正是在更高维场景下把这种逼近问题改造成格上的最短向量问题SVP——格的基本定义与困难问题 中给出了 SVP 的形式化描述给定格 $L$ 及其基 $B$找到非零向量 $v$ 使得 $\Vert v\Vert \leq \Vert u\Vert$对所有非零格点 $u$ 成立。原理分析之二郭Guo的方法——两个解密指数郭针对不止一个 $e$ 的情况做了研究但只研究了两个和三个 $e$ 的情形。对两个 $e$ 的情况有$$ e_1d_1g - k_1(p-1)(q-1) g $$$$ e_2d_2g - k_2(p-1)(q-1) g $$简单化简可以得到$$ k_2d_1e_1 - k_1d_2e_2 k_2 - k_1\tag{2} $$两边同时除以 $k_2d_1e_2$$$ \frac{e_1}{e_2} - \frac{k_1d_2}{k_2d_1} \frac{k_2 - k_1}{k_2d_1e_2} $$设 $d_i N^\alpha$则等式右边约等于 $N^{-(1\alpha)}$。于是当$$ 2(k_2d_1)^2 N^{1\alpha} $$时$k_1d_2/(k_2d_1)$ 是 $e_1/e_2$ 的连分数近似。又因为 $k_2$ 与 $d_1$ 最多为 $N^\alpha$ 量级且 $g$ 很小时可以得到$$ \alpha 1/3 - \epsilon \quad (\epsilon 0) $$值得注意的是即使通过连分数得到了 $(k_1d_2)/(k_2d_1)$也仍然无法直接分解 $N$。原文后面还讨论了郭的提议——尝试对 $k_1d_2$ 进行分解此处不再展开。扩展维纳攻击两条核心关系式与复合构造思想将分析扩展到 $n$ 个加密指数 $e_i$解密指数 $d_i$ 都很小时需要同时使用维纳和郭的方法。把关系$$ d_ige_i - k_iN g k_is $$记为维纳等式$W_i$同样地把$$ k_id_je_j - k_jd_ie_i k_i - k_j $$记为郭等式$G_{i,j}$。假设 $d_i$ 和 $k_i$ 都小于 $N^{\alpha_n}$且 $g$ 很小、$s \approx N^{1/2}$。可以注意到$W_i$ 和 $G_{i,j}$ 的右侧非常小实际上分别最多为 $N^{1/2 \alpha_n}$ 和 $N^{\alpha_n}$考虑复合关系式如 $W_uG_{v,w}$其大小约为 $N^{1/2 2\alpha_n}$。这两个关系式的大小范围是后续一切分析的基础。整个攻击的流程是选取 $W_i$、$G_{i,j}$ 的若干复合关系这是核心难点用这些关系式构造一个格矩阵通过 LLL 等格基规约算法求出格中的短向量得到 $d_1g/k_1$由 $d_1g/k_1$ 计算 $\varphi(N)$进而分解 $N$。从源码结构看整个分析的关键并不在于格的构造本身构造并不复杂而在于复合关系的选取以及对最终 $\alpha_n$ 上界的分析。两个小解密指数的情况n2选取关系 $W_1, G_{1,2}, W_1W_2$展开如下$$ \begin{aligned} d_1ge_1 - k_1N gk_1s\ k_1d_2e_2 - k_2d_1e_1 k_1-k_2\ d_1d_2g^2e_1e_2 - d_1gk_2e_1N - d_2gk_1e_2N k_1k_2N^2 (gk_1s)(gk_2s) \end{aligned} $$对第一个关系式乘上 $k_2$左边便全由 $d_1d_2g^2, d_1gk_2, d_2gk_1, k_1k_2$ 构成于是可以用已知内容构造格将上述式子转化为矩阵运算$$ \begin{pmatrix} k_1k_2d_1gk_2d_2gk_1d_1d_2g^2 \end{pmatrix} \begin{pmatrix} 1-N0N^2\ e_1-e_1-e_1N\ e_2-e_2N\ e_1e_2 \end{pmatrix}\begin{pmatrix} k_1k_2k_2(gk_1s)g(k_1 - k_2)(gk_1s)(gk_2s) \end{pmatrix} $$等式右边向量各分量的大小分别为 $N^{2\alpha_2}, N^{1/22\alpha_2}, N^{\alpha_2}, N^{12\alpha_2}$。为了让各分量大小均衡这是后续 LLL 能否成功的关键构造对角矩阵 D$$ D \begin{pmatrix} N\ N^{1/2}\ N^{1\alpha_2}\ 1 \end{pmatrix} $$最终构造的格矩阵为$$ L_2 \begin{pmatrix} 1-N0N^2\ e_1-e_1-e_1N\ e_2-e_2N\ e_1e_2 \end{pmatrix} * D $$于是向量 $b \begin{pmatrix} k_1k_2d_1gk_2d_2gk_1d_1d_2g^2 \end{pmatrix}$ 满足$$ \Vert bL_2 \Vert 2N^{12\alpha_2} $$这正是构造 D 矩阵的原因给定 D 后我们得到了一个可控的上界问题被转化为类 SVP 问题——即 格中的最短向量问题SVPShortest Vector Problem的实例。使用 LLL 等格基规约算法即可得到基向量 $b$然后求解 $b_2/b_1$ 即可得到 $d_1g/k_1$$$ b_2/b_1 \frac{d_1gk_2}{k_1k_2} \frac{d_1g}{k_1} $$之后就可以得到$$ \varphi(N) \frac{edg}{k} - \frac{g}{k} \left\lfloor edg/k\right\rceil $$可攻击条件分析假设这些格中最短向量长度为 $\Delta^{1/4-\epsilon}$其中 $\Delta \det(L_2) N^{13/2 \alpha_2}$。如果格是随机的几乎可以肯定没有格点比闵可夫斯基界Minkowskis bound$2\Delta^{1/4}$ 更短所以 $bL_2$ 是最短向量当$$ N^{12\alpha_2} (1/c_2)\left(N^{13/2\alpha_2}\right)^{1/4} $$对某个小的常数 $c_2$ 成立即$$ \alpha_2 5/14 - \epsilon $$时可以通过格基规约找到向量 $b$。这就是两个小解密指数场景下的攻击条件。三个小解密指数的情况n3对三个指数额外选取 $G_{1,3}, W_1G_{2,3}, W_2G_{1,3}$此时目标向量 $B$ 为 8 个分量$$ B \begin{pmatrix} k_1k_2k_3d_1gk_2k_3k_1d_2gk_3d_1d_2g^2k_3k_1k_2d_3gk_1d_3gk_2d_3gd_1d_2d_3g^3 \end{pmatrix} $$构造格矩阵$$ 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 \mathrm{diag}\left(\begin{array}{r} N^{\frac{3}{2}}NN^{a \frac{3}{2}}\sqrt{N}N^{a \frac{3}{2}}N^{a 1}N^{a 1}1\end{array}\right) $$此处 $a$ 即 $\alpha_3$。类似地可以得到$$ \Vert bL_2 \Vert \sqrt{8}N^{3/22\alpha_3} $$则当$$ \alpha_3 2/5 - \epsilon $$时可以通过格基规约求出向量 $b$。三个指数的攻击上界从 $5/14 \approx 0.357$ 提升到了 $2/5 0.4$。四个及以上小解密指数的情况对四个指数额外选取 $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$ 进行构造思路与 n2、n3 完全一致只是复合关系更多、矩阵维度更高$2^4 \times 2^4$。一般化分析复合关系的选取与 $\alpha_n$ 上界公式上面的具体例子已经阐明了方法细节但没有讲解如何选取复合关系。其实在论文附录中给出了复合关系的选取规则以及 $\alpha_n$ 的表达式考虑 $n$ 个指数 $e_i$则存在 $2^n$ 个不同的量 $h_j$每个 $h_j$ 是若干 $e_i$ 的乘积——即表达式 $e_i$ 的个数不同这样格矩阵 $L_n$ 在乘上 $D$ 之前其行列式为 $N^{n2^{n-1}}$最后一个关系 $W_1W_2\dots W_n$ 最大为 $N^{n/2 n\alpha_n}$于是我们知道了任意情况的最大界值——只需要让其他值垫高到这个量级即可这正是构造 D 矩阵的目的。引入新的复合关系记号$$ R_{u,v} W_{i_1}\dots W_{i_u}G_{j_1, l_1}\dots G_{j_v, l_v} $$其中 $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 (uv)\alpha_n}$。同时需要所有系数大小大致相同所以会在某些等式上乘 $k_i$使得关系满足$$ R_{u, v} N^{u/2 (n-v)\alpha_n} $$最后计算所有关系的大小与最大大小 $N^{n/2 n\alpha_n}$ 的差值据此构造矩阵 $D$。设矩阵 $D$ 中指数乘积为 $\beta_n xy\alpha_n$则有$$ \det(L_n) \approx N^{n2^{n-1} x y\alpha_n} $$于是有$$ N^{n/2 n\alpha_n} (1/c_n)\left(N^{n2^{n-1} x y\alpha_n}\right)^{1/2^n} $$对小的 $c_n$ 成立时解得$$ \alpha_n \frac{x}{n2^n - y} - \epsilon $$所以要让 $\alpha_n$ 的上界更大就需要让 $x$ 和 $y$ 更大这意味要选取更多的 $v$更多 G 关系和更小的 $u$更少 W 关系。例如在 $n2$ 时应选取 $W_1, G_{1,2}, W_1W_2$ 而不是 $W_1, W_2, W_1W_2$前者的 $\beta_2 5/2 \alpha_2$而后者的 $\beta_2 2$。至此扩展维纳攻击的完整流程已经清晰如何选择复合关系 → 如何构造格 → 如何构造矩阵 D → 如何求解。论文文末给出了 $n\le 5$ 时的关系选择表CTF-Wiki 的作者进一步给出了 $n\le 8$ 的完整选择关系可作为验证自己是否编写出选择关系式逻辑代码的参考答案其中 $n1$ 到 $n8$ 的选择依次为每行形如W(i)、G(i,j)或其乘积最后一行为 $W_1W_2\cdots W_n$- W(1) G(1, 2) W(1)W(2) G(1, 3) W(1)G(2, 3) W(2)G(1, 3) W(1)W(2)W(3) G(1, 4) W(1)G(2, 4) G(1, 2)G(3, 4) G(1, 3)G(2, 4) W(1)W(2)G(3, 4) W(1)W(3)G(2, 4) W(2)W(3)G(1, 4) W(1)W(2)W(3)W(4) G(1, 5) W(1)G(2, 5) G(1, 2)G(3, 5) G(1, 3)G(2, 5) G(1, 4)G(2, 5) W(1)W(2)G(3, 5) W(1)G(2, 3)G(4, 5) W(1)G(2, 4)G(3, 5) W(2)G(1, 3)G(4, 5) W(2)G(1, 4)G(3, 5) W(3)G(1, 4)G(2, 5) W(1)W(2)W(3)G(4, 5) W(1)W(2)W(4)G(3, 5) W(1)W(3)W(4)G(2, 5) W(2)W(3)W(4)G(1, 5) W(1)W(2)W(3)W(4)W(5) G(1, 6) W(1)G(2, 6) G(1, 2)G(3, 6) G(1, 3)G(2, 6) G(1, 4)G(2, 6) G(1, 5)G(2, 6) W(1)W(2)G(3, 6) W(1)G(2, 3)G(4, 6) W(1)G(2, 4)G(3, 6) W(1)G(2, 5)G(3, 6) G(1, 2)W(3)G(4, 6) G(1, 2)G(3, 4)G(5, 6) G(1, 2)G(3, 5)G(4, 6) G(1, 3)G(2, 4)G(5, 6) G(1, 3)G(2, 5)G(4, 6) G(1, 4)G(2, 5)G(3, 6) W(1)W(2)W(3)G(4, 6) W(1)W(2)G(3, 4)G(5, 6) W(1)W(2)G(3, 5)G(4, 6) W(1)W(3)G(2, 4)G(5, 6) W(1)W(3)G(2, 5)G(4, 6) W(1)W(4)G(2, 5)G(3, 6) W(2)W(3)G(1, 4)G(5, 6) W(2)W(3)G(1, 5)G(4, 6) W(2)W(4)G(1, 5)G(3, 6) W(3)W(4)G(1, 5)G(2, 6) W(1)W(2)W(3)W(4)G(5, 6) W(1)W(2)W(3)W(5)G(4, 6) W(1)W(2)W(4)W(5)G(3, 6) W(1)W(3)W(4)W(5)G(2, 6) W(2)W(3)W(4)W(5)G(1, 6) W(1)W(2)W(3)W(4)W(5)W(6) G(1, 7) W(1)G(2, 7) G(1, 2)G(3, 7) G(1, 3)G(2, 7) G(1, 4)G(2, 7) G(1, 5)G(2, 7) G(1, 6)G(2, 7) W(1)W(2)G(3, 7) W(1)G(2, 3)G(4, 7) W(1)G(2, 4)G(3, 7) W(1)G(2, 5)G(3, 7) W(1)G(2, 6)G(3, 7) G(1, 2)W(3)G(4, 7) G(1, 2)G(3, 4)G(5, 7) G(1, 2)G(3, 5)G(4, 7) G(1, 2)G(3, 6)G(4, 7) G(1, 3)G(2, 4)G(5, 7) G(1, 3)G(2, 5)G(4, 7) G(1, 3)G(2, 6)G(4, 7) G(1, 4)G(2, 5)G(3, 7) G(1, 4)G(2, 6)G(3, 7) G(1, 5)G(2, 6)G(3, 7) W(1)W(2)W(3)G(4, 7) W(1)W(2)G(3, 4)G(5, 7) W(1)W(2)G(3, 5)G(4, 7) W(1)W(2)G(3, 6)G(4, 7) W(1)G(2, 3)W(4)G(5, 7) W(1)G(2, 3)G(4, 5)G(6, 7) W(1)G(2, 3)G(4, 6)G(5, 7) W(1)G(2, 4)G(3, 5)G(6, 7) W(1)G(2, 4)G(3, 6)G(5, 7) W(1)G(2, 5)G(3, 6)G(4, 7) W(2)G(1, 3)W(4)G(5, 7) W(2)G(1, 3)G(4, 5)G(6, 7) W(2)G(1, 3)G(4, 6)G(5, 7) W(2)G(1, 4)G(3, 5)G(6, 7) W(2)G(1, 4)G(3, 6)G(5, 7) W(2)G(1, 5)G(3, 6)G(4, 7) W(3)G(1, 4)G(2, 5)G(6, 7) W(3)G(1, 4)G(2, 6)G(5, 7) W(3)G(1, 5)G(2, 6)G(4, 7) W(4)G(1, 5)G(2, 6)G(3, 7) W(1)W(2)W(3)W(4)G(5, 7) W(1)W(2)W(3)G(4, 5)G(6, 7) W(1)W(2)W(3)G(4, 6)G(5, 7) W(1)W(2)W(4)G(3, 5)G(6, 7) W(1)W(2)W(4)G(3, 6)G(5, 7) W(1)W(2)W(5)G(3, 6)G(4, 7) W(1)W(3)W(4)G(2, 5)G(6, 7) W(1)W(3)W(4)G(2, 6)G(5, 7) W(1)W(3)W(5)G(2, 6)G(4, 7) W(1)W(4)W(5)G(2, 6)G(3, 7) W(2)W(3)W(4)G(1, 5)G(6, 7) W(2)W(3)W(4)G(1, 6)G(5, 7) W(2)W(3)W(5)G(1, 6)G(4, 7) W(2)W(4)W(5)G(1, 6)G(3, 7) W(3)W(4)W(5)G(1, 6)G(2, 7) W(1)W(2)W(3)W(4)W(5)G(6, 7) W(1)W(2)W(3)W(4)W(6)G(5, 7) W(1)W(2)W(3)W(5)W(6)G(4, 7) W(1)W(2)W(4)W(5)W(6)G(3, 7) W(1)W(3)W(4)W(5)W(6)G(2, 7) W(2)W(3)W(4)W(5)W(6)G(1, 7) W(1)W(2)W(3)W(4)W(5)W(6)W(7) G(1, 8) W(1)G(2, 8) G(1, 2)G(3, 8) G(1, 3)G(2, 8) G(1, 4)G(2, 8) G(1, 5)G(2, 8) G(1, 6)G(2, 8) G(1, 7)G(2, 8) W(1)W(2)G(3, 8) W(1)G(2, 3)G(4, 8) W(1)G(2, 4)G(3, 8) W(1)G(2, 5)G(3, 8) W(1)G(2, 6)G(3, 8) W(1)G(2, 7)G(3, 8) G(1, 2)W(3)G(4, 8) G(1, 2)G(3, 4)G(5, 8) G(1, 2)G(3, 5)G(4, 8) G(1, 2)G(3, 6)G(4, 8) G(1, 2)G(3, 7)G(4, 8) G(1, 3)G(2, 4)G(5, 8) G(1, 3)G(2, 5)G(4, 8) G(1, 3)G(2, 6)G(4, 8) G(1, 3)G(2, 7)G(4, 8) G(1, 4)G(2, 5)G(3, 8) G(1, 4)G(2, 6)G(3, 8) G(1, 4)G(2, 7)G(3, 8) G(1, 5)G(2, 6)G(3, 8) G(1, 5)G(2, 7)G(3, 8) G(1, 6)G(2, 7)G(3, 8) W(1)W(2)W(3)G(4, 8) W(1)W(2)G(3, 4)G(5, 8) W(1)W(2)G(3, 5)G(4, 8) W(1)W(2)G(3, 6)G(4, 8) W(1)W(2)G(3, 7)G(4, 8) W(1)G(2, 3)W(4)G(5, 8) W(1)G(2, 3)G(4, 5)G(6, 8) W(1)G(2, 3)G(4, 6)G(5, 8) W(1)G(2, 3)G(4, 7)G(5, 8) W(1)G(2, 4)G(3, 5)G(6, 8) W(1)G(2, 4)G(3, 6)G(5, 8) W(1)G(2, 4)G(3, 7)G(5, 8) W(1)G(2, 5)G(3, 6)G(4, 8) W(1)G(2, 5)G(3, 7)G(4, 8) W(1)G(2, 6)G(3, 7)G(4, 8) G(1, 2)W(3)W(4)G(5, 8) G(1, 2)W(3)G(4, 5)G(6, 8) G(1, 2)W(3)G(4, 6)G(5, 8) G(1, 2)W(3)G(4, 7)G(5, 8) G(1, 2)G(3, 4)W(5)G(6, 8) G(1, 2)G(3, 4)G(5, 6)G(7, 8) G(1, 2)G(3, 4)G(5, 7)G(6, 8) G(1, 2)G(3, 5)G(4, 6)G(7, 8) G(1, 2)G(3, 5)G(4, 7)G(6, 8) G(1, 2)G(3, 6)G(4, 7)G(5, 8) G(1, 3)G(2, 4)W(5)G(6, 8) G(1, 3)G(2, 4)G(5, 6)G(7, 8) G(1, 3)G(2, 4)G(5, 7)G(6, 8) G(1, 3)G(2, 5)G(4, 6)G(7, 8) G(1, 3)G(2, 5)G(4, 7)G(6, 8) G(1, 3)G(2, 6)G(4, 7)G(5, 8) G(1, 4)G(2, 5)G(3, 6)G(7, 8) G(1, 4)G(2, 5)G(3, 7)G(6, 8) G(1, 4)G(2, 6)G(3, 7)G(5, 8) G(1, 5)G(2, 6)G(3, 7)G(4, 8) W(1)W(2)W(3)W(4)G(5, 8) W(1)W(2)W(3)G(4, 5)G(6, 8) W(1)W(2)W(3)G(4, 6)G(5, 8) W(1)W(2)W(3)G(4, 7)G(5, 8) W(1)W(2)G(3, 4)W(5)G(6, 8) W(1)W(2)G(3, 4)G(5, 6)G(7, 8) W(1)W(2)G(3, 4)G(5, 7)G(6, 8) W(1)W(2)G(3, 5)G(4, 6)G(7, 8) W(1)W(2)G(3, 5)G(4, 7)G(6, 8) W(1)W(2)G(3, 6)G(4, 7)G(5, 8) W(1)W(3)G(2, 4)W(5)G(6, 8) W(1)W(3)G(2, 4)G(5, 6)G(7, 8) W(1)W(3)G(2, 4)G(5, 7)G(6, 8) W(1)W(3)G(2, 5)G(4, 6)G(7, 8) W(1)W(3)G(2, 5)G(4, 7)G(6, 8) W(1)W(3)G(2, 6)G(4, 7)G(5, 8) W(1)W(4)G(2, 5)G(3, 6)G(7, 8) W(1)W(4)G(2, 5)G(3, 7)G(6, 8) W(1)W(4)G(2, 6)G(3, 7)G(5, 8) W(1)W(5)G(2, 6)G(3, 7)G(4, 8) W(2)W(3)G(1, 4)W(5)G(6, 8) W(2)W(3)G(1, 4)G(5, 6)G(7, 8) W(2)W(3)G(1, 4)G(5, 7)G(6, 8) W(2)W(3)G(1, 5)G(4, 6)G(7, 8) W(2)W(3)G(1, 5)G(4, 7)G(6, 8) W(2)W(3)G(1, 6)G(4, 7)G(5, 8) W(2)W(4)G(1, 5)G(3, 6)G(7, 8) W(2)W(4)G(1, 5)G(3, 7)G(6, 8) W(2)W(4)G(1, 6)G(3, 7)G(5, 8) W(2)W(5)G(1, 6)G(3, 7)G(4, 8) W(3)W(4)G(1, 5)G(2, 6)G(7, 8) W(3)W(4)G(1, 5)G(2, 7)G(6, 8) W(3)W(4)G(1, 6)G(2, 7)G(5, 8) W(3)W(5)G(1, 6)G(2, 7)G(4, 8) W(4)W(5)G(1, 6)G(2, 7)G(3, 8) W(1)W(2)W(3)W(4)W(5)G(6, 8) W(1)W(2)W(3)W(4)G(5, 6)G(7, 8) W(1)W(2)W(3)W(4)G(5, 7)G(6, 8) W(1)W(2)W(3)W(5)G(4, 6)G(7, 8) W(1)W(2)W(3)W(5)G(4, 7)G(6, 8) W(1)W(2)W(3)W(6)G(4, 7)G(5, 8) W(1)W(2)W(4)W(5)G(3, 6)G(7, 8) W(1)W(2)W(4)W(5)G(3, 7)G(6, 8) W(1)W(2)W(4)W(6)G(3, 7)G(5, 8) W(1)W(2)W(5)W(6)G(3, 7)G(4, 8) W(1)W(3)W(4)W(5)G(2, 6)G(7, 8) W(1)W(3)W(4)W(5)G(2, 7)G(6, 8) W(1)W(3)W(4)W(6)G(2, 7)G(5, 8) W(1)W(3)W(5)W(6)G(2, 7)G(4, 8) W(1)W(4)W(5)W(6)G(2, 7)G(3, 8) W(2)W(3)W(4)W(5)G(1, 6)G(7, 8) W(2)W(3)W(4)W(5)G(1, 7)G(6, 8) W(2)W(3)W(4)W(6)G(1, 7)G(5, 8) W(2)W(3)W(5)W(6)G(1, 7)G(4, 8) W(2)W(4)W(5)W(6)G(1, 7)G(3, 8) W(3)W(4)W(5)W(6)G(1, 7)G(2, 8) W(1)W(2)W(3)W(4)W(5)W(6)G(7, 8) W(1)W(2)W(3)W(4)W(5)W(7)G(6, 8) W(1)W(2)W(3)W(4)W(6)W(7)G(5, 8) W(1)W(2)W(3)W(5)W(6)W(7)G(4, 8) W(1)W(2)W(4)W(5)W(6)W(7)G(3, 8) W(1)W(3)W(4)W(5)W(6)W(7)G(2, 8) W(2)W(3)W(4)W(5)W(6)W(7)G(1, 8) W(1)W(2)W(3)W(4)W(5)W(6)W(7)W(8)可以看到选择关系从 $n$ 到 $n1$ 时数量快速增长第 $n$ 组对应 $2^n$ 个不同的 $h_j$且每组都以 $G(1,n)$ 开头、以 $W_1W_2\cdots W_n$ 结尾中间按G 关系尽量多、W 关系尽量少的原则排列——这正是 $\alpha_n$ 上界 $\frac{x}{n2^n - y}$ 最大化的体现。对于 $n6$ 的情况作者还给出了构造出的 $64\times64$ 矩阵$2^6 \times 2^6$其生成完全遵循上述复合关系 → 格矩阵 $L_n$ → 对角矩阵 D的机械流程文档中该矩阵由脚本自动生成。其左上角 $8\times8$ 子块结构与 n3 时的 $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) $$后续各行则按 $e_4,e_5,e_6$ 的引入逐块扩展行向量的非零项只落在与该行对应 $h_j$ 的因子相关的列上非零项形如 $\pm N^t e_{i_1}\cdots e_{i_m}$$t$ 随列递增$D$ 矩阵的指数由 $R_{u,v}$ 与最大界 $N^{n/2n\alpha_n}$ 的差值逐列确定。你可以用这个规律编写脚本验证输出是否与文档一致。实战 EXPn2 场景的 SageMath 攻击脚本考虑到并非每位读者都需要深入钻研扩展维纳攻击的理论这里给出 $n2$ 时的可直接运行 EXPSageMath供 CTF 模板题直接套用e1 ... e2 ... N ... a 5/14 D diagonal_matrix(ZZ, [N, int(N^(1/2)), int(N^(1a)), 1]) M matrix(ZZ, [[1, -N, 0, N^2], [0, e1, -e1, -e1*N], [0, 0, e2, -e2*N], [0, 0, 0, e1*e2]])*D L M.LLL() t vector(ZZ, L[0]) x t * M^(-1) phi int(x[1]/x[0]*e1)脚本的执行逻辑与前面的推导一一对应D即对角矩阵 $\mathrm{diag}(N, N^{1/2}, N^{1\alpha_2}, 1)$其中 $\alpha_2 5/14$ 是 n2 时的攻击上界M为上三角矩阵乘D得到的格矩阵 $L_2$其行向量张成的格中$bL_2$ 是一个短向量M.LLL()执行格基规约LLL 算法的具体性质可参考 格基规约算法取规约后最短基向量tx t * M^(-1)把短向量还原回原始系数向量 $b (k_1k_2, d_1gk_2, d_2gk_1, d_1d_2g^2)$由于 $x_1/x_0 d_1g/k_1$而 $d_1e_1g/k_1 \varphi(N) g/k_1$因为 $d_1ge_1 - k_1N g k_1s$且 $Ns \varphi(N)$当 $g$ 很小、$k_1$ 较大时 $g/k_1 1$于是int(x[1]/x[0]*e1)取整即得到 $\varphi(N)$。得到 $\varphi(N)$ 后解一元二次方程 $X^2 - (N - \varphi(N) 1)X N 0$ 即可分解出 $p,q$随后用 $d e^{-1} \bmod \varphi(N)$ 完成解密。在使用时需注意适用前提题目必须满足 $d_i N^{\alpha_2}$即 $\alpha_2 5/14$且 $g$ 很小例如两个加密指数共用同一组 $(p,q)$$g$ 通常为 1 或 2且私钥位数为 $N$ 位数的约 $0.35$ 倍以下。开放问题与性能瓶颈目前 CTF 中出现的扩展维纳攻击题目几乎都是 $n2$ 或 $n3$ 的模板题。对更高维的情况可以编写自动化脚本来完整地自动选择关系、自动构造格上文中的 n≤8 选择关系表与 n6 矩阵正是自动生成的产物。然而存在明显的性能瓶颈矩阵规模随 n 指数级膨胀$n$ 每增加 1矩阵就是 $2^n \times 2^n$ 的规模翻倍增长LLL 规约极慢直接调用 SageMath 的LLL()变得非常缓慢大约 $n8$ 时已经无法在合理时间内运行出结果并行化方案缺代码作者曾尝试寻找 LLL 在 CUDA 上的并行算法或其他优化方案但找到的都是论文、没有开源实现可参考。如果你对这方面有研究或更好的优化方法欢迎与文档作者Xenny进一步深入探讨。参考本文依据 CTF-Wiki 中文仓库的 扩展维纳攻击文档 整理而成相关前置知识可继续阅读RSA 基本介绍RSA 密钥生成、加解密与正确性证明私钥 d 相关攻击d 泄露攻击、维纳攻击的经典条件与工具链格的基本定义与困难问题SVP、CVP 等形式化定义格基规约算法LLL 算法的性质与典型应用原文档 References 所列的扩展阅读资料还包括《Extending Wieners Attack in the Presence of Many Decrypting Exponents》扩展维纳攻击的原始论文收录于密码学会议论文集、《Factoring Polynomials with Rational Coefficients》LLL 算法奠基性论文、《并行 LLL 算法研究综述》以及《A Parallel Jacobi-Type Lattice Basis Reduction Algorithm》并行格基规约相关研究这些文献与仓库中的格论章节相互印证可作为深入阅读的指引。赞分享文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载相关推荐RSA 擴展維納攻擊Extending Wieners Attack原理與格構造深度解析RSA 擴展維納攻擊Extending Wieners Attack原理與格構造深度解析 擴展維納攻擊Extending Wieners Attack文档网络安全教程CTF-Wiki 密码学实战CTR 计数器模式原理剖析与 CTF 逆向攻击CTF Wiki 密码学实战CTR 计数器模式原理剖析与 CTF 逆向攻击 本文以 CTF Wiki 文档 docs/zh tw/docs/crypto/bl文档网络安全教程ctf-wiki 密码学专题Padding Oracle Attack 原理剖析与完整 CTF 实战利用ctf wiki 密码学专题Padding Oracle Attack 原理剖析与完整 CTF 实战利用 本文以 ctf wiki 密码学模块中的 Paddi文档网络安全教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考