RSA-Wiener-Attack实现

​ 先介绍一下连分数：连分数（continued fraction）是特殊繁分数。如果a0，a1，a2，…an，…都是整数，则将分别称为无限连分数和有限连分数。可简记为a0 ，a1，a2，…，an，…和a0，a1，a2，…，an。一般一个有限连分数表示一个有理数，一个无限连分数表示一个无理数。如果a0，a1，a2，…，an，…都是实数，可将上述形式连分数分别叫无限连分数和有限连分数 。近代数学的计算需要，还可将连分数中的a0，a1 ，a2，…，an，…取成以x为变元的多项式。在近代计算数学中它常与某些微分方程式差分方程有关，与某些递推关系有关的函数构造的应用相联系。

​ 研究连分数的动机源于想要有实数在“数学上纯粹”的表示。这里的a0 可以是任意整数，其它ai 都是 {0, 1, 2, …, 9} 的一个元素。在这种表示中，例如数 π 被表示为整数序列 {3, 1, 4, 1, 5, 9, 2, …}。这种小数表示有些问题。例如，在这种情况下使用常数 10 是因为我们使用了 10进制系统。我们还可以使用 8进制或 2 进制系统。另一个问题是很多有理数在这个系统内缺乏有限表示。例如，数 1/3 被表示为无限序列 {0, 3, 3, 3, 3, ….}。连分数表示法是避免了实数表示的这两个问题。让我们考虑如何描述一个数如 415/93，约为 4.4624。近似为 4，而实际上比 4 多一点，约为 4 + 1/2。但是在分母中的 2 是不准确的；更准确的分母是比 2 多一点，约为 2 + 1/6，所以 415/93 近似为 4 + 1/(2 + 1/6)。但是在分母中的 6 是不准确的；更准确分母是比 6 多一点，实际是 6+1/7。所以 415/93 实际上是 4+1/(2+1/(6+1/7))。这样才准确 。去掉表达式 4 + 1/(2 + 1/(6 + 1/7)) 中的冗余部分可得到简略记号 [4; 2, 6, 7]。

​ 维纳攻击的原理已经在上篇讲的很详细，这里直接给出攻击实现的代码：

def continuedFra(x, y): #不断生成连分数的项
    cF = []
    while y:
        cF += [x // y]
        x, y = y, x % y
    return cF
def Simplify(ctnf): #化简
    numerator = 0
    denominator = 1
    for x in ctnf[::-1]: #注意这里是倒叙遍历
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator) #把连分数分成分子和算出来的分母
def getit(c):
    cf=[]
    for i in range(1,len(c)):
        cf.append(Simplify(c[:i])) #各个阶段的连分数的分子和分母
    return cf #得到一串连分数

def wienerAttack(e, n):
    cf=continuedFra(e,n)
    for (k,d) in getit(cf):#遍历得到的连分数，令分子分母分别是k，d
        if d == 0:
            continue
        if type((e*d-1)/k)== int: #必须满足phi(n)为整数
            return d
#注意这里的d还不一定是私钥，可以利用d和k的值以及phi(n)与p，q的关系列出一元二次方程，放入sage求解，若可求出p，q则无误
    print('not find!')

​ 当通过维纳攻击找到d，p，q的值时，整个密码也就被破解了。