Skip to main content
deleted 85 characters in body
Source Link
import gmpy2

def solve_rsa_primes(s: int, m: int) -> tuple:
    """ Solve RSA prime numbers (p, q) from the quadratic equation
    p^2 - s * p + m = 0 with the formula p = s/2 +/- sqrt((s/2)^2 - m)

    Parameters:
        s - sum of primes (p + q)
        m - product of primes (p * q)
    Return: (p, q)
    """
    
    half_s = s >> 1
    tmp = gmpy2.isqrt(half_s ** 2 - m)
    return int(half_s + tmp), int(half_s - tmp)

def wiener_attack(n: int, e: int) -> (int, int, int):
    """ Wiener's Attack on RSA public key cryptosystem
    Paramaters:
        N - RSA modulus N = p*q
        e - RSA public exponent
    Return:
        A tuple of (p, q, d)
        p, q - the two prime factors of RSA modulus N
        d - RSA private exponent
    """

    cfe = cf_expansion(e, n) # Convert e/n into a continued fraction
    cvg = cf_convergent(cfe) # Get all of its convergents

    for k, d in cvg:
        # Check if k and d meet the requirements
        if k == 0 or d % 2 == 0 or (e * d) % k != 1:
            continue

        # assume ed ≡ 1 (mod ϕ(n))
        phi = (e * d - 1) // k 
        p, q = solve_rsa_primes(n - phi + 1, n)
        if n == p * q:
            return d

    return None

N = int(
    '22836858353287668091920368816286415778103964252589'\
    '28295130420474999022996621982166664596581454018899'\
    '48429922376560732622754871538043874356270300826321'\
    '16650572564937978011181394388679265524940467869924'\
    '85473650038355720409426235584833584188449224331698'\
    '63569900296911605460645581176522325967221393273906'\
    '69673188457131381644120787783215342848744792830245'\
    '01805598140668893320307200136190794138325132168722'\
    '14217943474001731747822701596634040292342194986951'\
    '94551646668806852454006312372413658692027515557841'\
    '41440661232146905186431357112566536770669381756925'\
    '38179415478954522854711968599279014482060579354284'\
    '55238863726089083')

e = int(
    '17160819308904585327789016134897914235762203050367'\
    '34632679585567058963995675965428034906637374660531'\
    '64750599687461192166424505919293706011293378320096'\
    '43372382766547546926535697752805239918767190684796'\
    '26509298669049485976118315666126871681847641670872'\
    '58895073919139366379901867664076540531765577090231'\
    '67209821832859747419658344363466584895316847817524'\
    '24703257392651850823517297420382138943770358904660'\
    '59442300191228592937251734592732623207324742303631'\
    '32436274414264865868028527840102483762414082363751'\
    '87208612632105886502393648156776330236987329249988'\
    '11429508256124902530957499338336903951924035916501'\
    '53661610070010419')

d = wiener_attack(N, e)
assert not d is None, "Wiener's attack failed!"
print("d =", d)

new_b = int(gmpy2.root(N, 4)/gmpy2.root(18, 4))
print("new_b =", new_b)
assert d <= new_b

old_b = int(gmpy2.root(N, 4)/3)
print("old_b =", old_b)
assert d > old_b
import gmpy2

def solve_rsa_primes(s: int, m: int) -> tuple:
    """ Solve RSA prime numbers (p, q) from the quadratic equation
    p^2 - s * p + m = 0 with the formula p = s/2 +/- sqrt((s/2)^2 - m)

    Parameters:
        s - sum of primes (p + q)
        m - product of primes (p * q)
    Return: (p, q)
    """
    
    half_s = s >> 1
    tmp = gmpy2.isqrt(half_s ** 2 - m)
    return int(half_s + tmp), int(half_s - tmp)

def wiener_attack(n: int, e: int) -> (int, int, int):
    """ Wiener's Attack on RSA public key cryptosystem
    Paramaters:
        N - RSA modulus N = p*q
        e - RSA public exponent
    Return:
        A tuple of (p, q, d)
        p, q - the two prime factors of RSA modulus N
        d - RSA private exponent
    """

    cfe = cf_expansion(e, n) # Convert e/n into a continued fraction
    cvg = cf_convergent(cfe) # Get all of its convergents

    for k, d in cvg:
        # Check if k and d meet the requirements
        if k == 0 or d % 2 == 0 or (e * d) % k != 1:
            continue

        # assume ed ≡ 1 (mod ϕ(n))
        phi = (e * d - 1) // k 
        p, q = solve_rsa_primes(n - phi + 1, n)
        if n == p * q:
            return d

    return None

N = int(
    '22836858353287668091920368816286415778103964252589'\
    '28295130420474999022996621982166664596581454018899'\
    '48429922376560732622754871538043874356270300826321'\
    '16650572564937978011181394388679265524940467869924'\
    '85473650038355720409426235584833584188449224331698'\
    '63569900296911605460645581176522325967221393273906'\
    '69673188457131381644120787783215342848744792830245'\
    '01805598140668893320307200136190794138325132168722'\
    '14217943474001731747822701596634040292342194986951'\
    '94551646668806852454006312372413658692027515557841'\
    '41440661232146905186431357112566536770669381756925'\
    '38179415478954522854711968599279014482060579354284'\
    '55238863726089083')

e = int(
    '17160819308904585327789016134897914235762203050367'\
    '34632679585567058963995675965428034906637374660531'\
    '64750599687461192166424505919293706011293378320096'\
    '43372382766547546926535697752805239918767190684796'\
    '26509298669049485976118315666126871681847641670872'\
    '58895073919139366379901867664076540531765577090231'\
    '67209821832859747419658344363466584895316847817524'\
    '24703257392651850823517297420382138943770358904660'\
    '59442300191228592937251734592732623207324742303631'\
    '32436274414264865868028527840102483762414082363751'\
    '87208612632105886502393648156776330236987329249988'\
    '11429508256124902530957499338336903951924035916501'\
    '53661610070010419')

d = wiener_attack(N, e)
assert not d is None, "Wiener's attack failed!"
print("d =", d)

new_b = int(gmpy2.root(N, 4)/gmpy2.root(18, 4))
print("new_b =", new_b)
assert d <= new_b

old_b = int(gmpy2.root(N, 4)/3)
print("old_b =", old_b)
assert d > old_b
import gmpy2

def solve_rsa_primes(s: int, m: int) -> tuple:
    """ Solve RSA prime numbers (p, q) from the quadratic equation
    p^2 - s * p + m = 0 with the formula p = s/2 +/- sqrt((s/2)^2 - m)

    Parameters:
        s - sum of primes (p + q)
        m - product of primes (p * q)
    Return: (p, q)
    """
    
    half_s = s >> 1
    tmp = gmpy2.isqrt(half_s ** 2 - m)
    return int(half_s + tmp), int(half_s - tmp)

def wiener_attack(n: int, e: int) -> (int, int, int):
    """ Wiener's Attack on RSA public key cryptosystem
    Paramaters:
        N - RSA modulus N = p*q
        e - RSA public exponent
    Return:
        d - RSA private exponent
    """

    cfe = cf_expansion(e, n) # Convert e/n into a continued fraction
    cvg = cf_convergent(cfe) # Get all of its convergents

    for k, d in cvg:
        # Check if k and d meet the requirements
        if k == 0 or d % 2 == 0 or (e * d) % k != 1:
            continue

        # assume ed ≡ 1 (mod ϕ(n))
        phi = (e * d - 1) // k 
        p, q = solve_rsa_primes(n - phi + 1, n)
        if n == p * q:
            return d

    return None

N = int(
    '22836858353287668091920368816286415778103964252589'\
    '28295130420474999022996621982166664596581454018899'\
    '48429922376560732622754871538043874356270300826321'\
    '16650572564937978011181394388679265524940467869924'\
    '85473650038355720409426235584833584188449224331698'\
    '63569900296911605460645581176522325967221393273906'\
    '69673188457131381644120787783215342848744792830245'\
    '01805598140668893320307200136190794138325132168722'\
    '14217943474001731747822701596634040292342194986951'\
    '94551646668806852454006312372413658692027515557841'\
    '41440661232146905186431357112566536770669381756925'\
    '38179415478954522854711968599279014482060579354284'\
    '55238863726089083')

e = int(
    '17160819308904585327789016134897914235762203050367'\
    '34632679585567058963995675965428034906637374660531'\
    '64750599687461192166424505919293706011293378320096'\
    '43372382766547546926535697752805239918767190684796'\
    '26509298669049485976118315666126871681847641670872'\
    '58895073919139366379901867664076540531765577090231'\
    '67209821832859747419658344363466584895316847817524'\
    '24703257392651850823517297420382138943770358904660'\
    '59442300191228592937251734592732623207324742303631'\
    '32436274414264865868028527840102483762414082363751'\
    '87208612632105886502393648156776330236987329249988'\
    '11429508256124902530957499338336903951924035916501'\
    '53661610070010419')

d = wiener_attack(N, e)
assert not d is None, "Wiener's attack failed!"
print("d =", d)

new_b = int(gmpy2.root(N, 4)/gmpy2.root(18, 4))
print("new_b =", new_b)
assert d <= new_b

old_b = int(gmpy2.root(N, 4)/3)
print("old_b =", old_b)
assert d > old_b
added 7 characters in body
Source Link

I found this recent paper The Wiener Attack on RSA Revisited: A Quest for the Exact Bound, which reported a new bound $d\le \frac 1 {\sqrt[n]{18}} N^\frac 1 4$$d\le \frac 1 {\sqrt[4]{18}} N^\frac 1 4$. Is this well accepted in the cryptanalysis research community?

I found this recent paper The Wiener Attack on RSA Revisited: A Quest for the Exact Bound, which reported a new bound $d\le \frac 1 {\sqrt[n]{18}} N^\frac 1 4$. Is this well accepted in the cryptanalysis research community?

I found this recent paper The Wiener Attack on RSA Revisited: A Quest for the Exact Bound, which reported a new bound $d\le \frac 1 {\sqrt[4]{18}} N^\frac 1 4$. Is this well accepted in the cryptanalysis research community?

Became Hot Network Question
Source Link

Is this new bound for Wiener Attack well accepted?

I found this recent paper The Wiener Attack on RSA Revisited: A Quest for the Exact Bound, which reported a new bound $d\le \frac 1 {\sqrt[n]{18}} N^\frac 1 4$. Is this well accepted in the cryptanalysis research community?

With a Python script, I personally verified the d revealed from the given (N,e) in Section 4 (page 392~395) of this paper, it worked indeed. The interesting thing is that even though this d was generated with $\lambda(N)=LCM(p-1,q-1)$, the Wiener Attack function could successfully reveal this d with the assumption of $ed = 1 \pmod {\phi(N)}$. How does this work?

import gmpy2

def solve_rsa_primes(s: int, m: int) -> tuple:
    """ Solve RSA prime numbers (p, q) from the quadratic equation
    p^2 - s * p + m = 0 with the formula p = s/2 +/- sqrt((s/2)^2 - m)

    Parameters:
        s - sum of primes (p + q)
        m - product of primes (p * q)
    Return: (p, q)
    """
    
    half_s = s >> 1
    tmp = gmpy2.isqrt(half_s ** 2 - m)
    return int(half_s + tmp), int(half_s - tmp)

def wiener_attack(n: int, e: int) -> (int, int, int):
    """ Wiener's Attack on RSA public key cryptosystem
    Paramaters:
        N - RSA modulus N = p*q
        e - RSA public exponent
    Return:
        A tuple of (p, q, d)
        p, q - the two prime factors of RSA modulus N
        d - RSA private exponent
    """

    cfe = cf_expansion(e, n) # Convert e/n into a continued fraction
    cvg = cf_convergent(cfe) # Get all of its convergents

    for k, d in cvg:
        # Check if k and d meet the requirements
        if k == 0 or d % 2 == 0 or (e * d) % k != 1:
            continue

        # assume ed ≡ 1 (mod ϕ(n))
        phi = (e * d - 1) // k 
        p, q = solve_rsa_primes(n - phi + 1, n)
        if n == p * q:
            return d

    return None

N = int(
    '22836858353287668091920368816286415778103964252589'\
    '28295130420474999022996621982166664596581454018899'\
    '48429922376560732622754871538043874356270300826321'\
    '16650572564937978011181394388679265524940467869924'\
    '85473650038355720409426235584833584188449224331698'\
    '63569900296911605460645581176522325967221393273906'\
    '69673188457131381644120787783215342848744792830245'\
    '01805598140668893320307200136190794138325132168722'\
    '14217943474001731747822701596634040292342194986951'\
    '94551646668806852454006312372413658692027515557841'\
    '41440661232146905186431357112566536770669381756925'\
    '38179415478954522854711968599279014482060579354284'\
    '55238863726089083')

e = int(
    '17160819308904585327789016134897914235762203050367'\
    '34632679585567058963995675965428034906637374660531'\
    '64750599687461192166424505919293706011293378320096'\
    '43372382766547546926535697752805239918767190684796'\
    '26509298669049485976118315666126871681847641670872'\
    '58895073919139366379901867664076540531765577090231'\
    '67209821832859747419658344363466584895316847817524'\
    '24703257392651850823517297420382138943770358904660'\
    '59442300191228592937251734592732623207324742303631'\
    '32436274414264865868028527840102483762414082363751'\
    '87208612632105886502393648156776330236987329249988'\
    '11429508256124902530957499338336903951924035916501'\
    '53661610070010419')

d = wiener_attack(N, e)
assert not d is None, "Wiener's attack failed!"
print("d =", d)

new_b = int(gmpy2.root(N, 4)/gmpy2.root(18, 4))
print("new_b =", new_b)
assert d <= new_b

old_b = int(gmpy2.root(N, 4)/3)
print("old_b =", old_b)
assert d > old_b