Wiener's Attack——连分数如何攻破低解密指数RSA-先知社区

维纳攻击

在 CTF 的 RSA 题目中，维纳攻击（Wiener's Attack）是一种经常会遇到的攻击方式，尤其是使用较小的私钥指数d的时候。大多数情况我们都是直接用脚本，但并没有深入了解其中的原理，只是停留在表面，这里就简单的介绍一下维纳攻击（Wiener's Attack）的基本原理。

简单描述就是，当私钥d足够小时，公钥e和模数n的比值可以通过连分数逼近的方法找到私钥d。再具体点来说，就是通过连分数逼近的方法，对 e/n进行连分数展开来逐步逼近真实的私钥。通过这种方法，攻击者能够恢复出满足RSA方程的有效私钥d。所以在介绍原理之前我们要先了解一些连分数的概念

连分数

连分数是一种特殊的分数表示方法，它将一个实数（包括有理数和无理数）表示为一系列整数的序列。这个序列通过递归的方式定义，每个整数都表示原数在减去前一个整数（或整数序列表示的分数）后的“剩余”部分。

具体来说，对于任何一个有理数a，我们可以将其转换为以下形式：

记为于是我们就将a的连分数记为：a=[a0,a1,a2,…,an]，就相当于用另一种方式表示a。

连分数不仅在理论数学中有深厚的基础，还在许多实际应用中发挥着重要作用。例如，它们可以用于逼近无理数，提供精确的近似值，并在数论、数值计算和信号处理等领域被广泛应用。连分数的结构使得它们在计算中具有高度的灵活性和有效性，能够以相对简单的方式表示复杂的数值，从而帮助人们更好地理解和利用这些数字。

收敛分数

收敛分数（也称为分数连分数收敛或连分数逼近）是利用连分数表示法逐步逼近某个实数的过程。具体而言，收敛分数由连分数的前几项构成，旨在提供某个实数的近似值。

设有理数 a=[a0;a1,a2,…,an]a = [a_0; a_1, a_2, \ldots, a_n]a=[a0;a1,a2,…,an]，其收敛分数包括以下几项：

●

[a0]

●

[a0,a1]

●

[a0,a1,a2]

●

……

●

[a0,a1,a2,…,an]

简单来说，收敛分数的计算过程就是把连分数中某一项后面的所有项舍去，从而得到一个a的近似值。随着保留的项数逐渐增多，收敛分数会越来越接近原始数a，这就是它被称为“收敛分数”的原因。

收敛分数不仅在理论上具有重要意义，在实际应用中也非常有用。它们可以为复杂的数值提供高效的近似方法，尤其是对无理数的逼近。通过简单的整数运算，收敛分数使得这些数值的获取变得更加方便。随着项数的增加，收敛分数能够以越来越高的精度表示目标数值，展示了连分数的强大能力和灵活性，因此在数论、计算数学以及信号处理等领域得到了广泛应用。

代码实现：

连分数定理（

Legendre's theorem

）

如果存在 a∈Q，且 p,q∈Z满足以下不等式：