Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
jvdsn
GitHub Repository: jvdsn/crypto-attacks
 Path: blob/master/attacks/rsa/extended_wiener_attack.py
2589 views
1
import os

2
import sys

3


4
from sage.all import RR

5
from sage.all import ZZ

6
from sage.all import continued_fraction

7


8
path = os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(os.path.abspath(__file__)))))

9
if sys.path[1] != path:

10
    sys.path.insert(1, path)

11


12
from attacks.factorization import known_phi

13


14


15
def attack(n, e, max_s=20000, max_r=100, max_t=100):

16
    """

17
    Recovers the prime factors if the private exponent is too small.

18
    More information: Dujella A., "Continued fractions and RSA with small secret exponent"

19
    :param n: the modulus

20
    :param e: the public exponent

21
    :param max_s: the amount of s values to try (default: 20000)

22
    :param max_r: the amount of r values to try for each s value (default: 100)

23
    :param max_t: the amount of t values to try for each s value (default: 100)

24
    :return: a tuple containing the prime factors and the private exponent, or None if the private exponent was not found

25
    """

26
    i_n = ZZ(n)

27
    i_e = ZZ(e)

28
    threshold = i_e / i_n + (RR(2.122) * i_e) / (i_n * i_n.sqrt())

29
    convergents = continued_fraction(i_e / i_n).convergents()

30
    for i in range(1, len(convergents) - 2, 2):

31
        if convergents[i + 2] < threshold < convergents[i]:

32
            m = i

33
            break

34
    else:

35
        return None

36


37
    for s in range(max_s):

38
        for r in range(max_r):

39
            k = r * convergents[m + 1].numerator() + s * convergents[m + 1].numerator()

40
            d = r * convergents[m + 1].denominator() + s * convergents[m + 1].denominator()

41
            if pow(pow(2, e, n), d, n) != 2:

42
                continue

43


44
            phi = (e * d - 1) // k

45
            factors = known_phi.factorize(n, phi)

46
            if factors:

47
                return *factors, int(d)

48


49
        for t in range(max_t):

50
            k = s * convergents[m + 2].numerator() - t * convergents[m + 1].numerator()

51
            d = s * convergents[m + 2].denominator() - t * convergents[m + 1].denominator()

52
            if pow(pow(2, e, n), d, n) != 2:

53
                continue

54


55
            phi = (e * d - 1) // k

56
            factors = known_phi.factorize(n, phi)

57
            if factors:

58
                return *factors, int(d)

59


60