Extended Wiener Attack DRAFT

  import os
import sys

from sage.all import RR
from sage.all import ZZ
from sage.all import continued_fraction

from math import gcd
from math import isqrt
from random import randrange

from sage.all import is_prime


def factorize(N, phi):
    s = N + 1 - phi
    d = s ** 2 - 4 * N
    p = int(s - isqrt(d)) // 2
    q = int(s + isqrt(d)) // 2
    return p, q if p * q == N else None



def attack(n, e, max_s=20000, max_r=100, max_t=100):
    i_n = ZZ(n)
    i_e = ZZ(e)
    threshold = i_e / i_n + (RR(2.122) * i_e) / (i_n * i_n.sqrt())
    convergents = continued_fraction(i_e / i_n).convergents()
    for i in range(1, len(convergents) - 2, 2):
        if convergents[i + 2] < threshold < convergents[i]:
            m = i
            break
    else:
        return None

    for s in range(max_s):
        for r in range(max_r):
            k = r * convergents[m + 1].numerator() + s * convergents[m + 1].numerator()
            d = r * convergents[m + 1].denominator() + s * convergents[m + 1].denominator()
            if pow(pow(2, e, n), d, n) != 2:
                continue

            phi = (e * d - 1) // k
            factors = known_phi.factorize(n, phi)
            if factors:
                return *factors, int(d)

        for t in range(max_t):
            k = s * convergents[m + 2].numerator() - t * convergents[m + 1].numerator()
            d = s * convergents[m + 2].denominator() - t * convergents[m + 1].denominator()
            if pow(pow(2, e, n), d, n) != 2:
                continue

            phi = (e * d - 1) // k
            factors = known_phi.factorize(n, phi)
            if factors:
                return *factors, int(d)