4
$\begingroup$

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?

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:
        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
$\endgroup$
1

1 Answer 1

4
$\begingroup$

Is this $\frac 1{\sqrt[4]{18}}N^\frac1 4$ bound well accepted in the cryptanalysis research community?

I see no reason why there would be a doubt. However, the exact bound for Wiener's attack is not the subject of much scrutiny by the cryptanalysis research community, because:

  • Dan Boneh & Glenn Durfee's Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$ (in proceedings of Eurocrypt 1999) factors $N$ for $d$ significantly larger that Wiener's attack can, making Wiener's attack interesting only by it's relative simplicity.
  • Practice must use $d$ comfortably above these thresholds for security reasons. Thus it can only give a modest speed advantage compared to using the CRT method for the RSA private key operation, and then only if using this method, where essentially it lowers $d_p$ and $d_q$ (and, for two moduli of about equal size, makes $d_p=d_q$, which is far from reassuring from a security standpoint).
  • Practice uses small $e$ because it is widely considered safe and leads to fast public key operation, which is desirable. It follows $d$ is with practical certainty far above Wiener's $N^{0.25}$ and Boneh & Durfee's $N^{0.292}$ bound (unless we use a modulus with at least 4 prime factors and have these factors exactly one above some multiple of a large prime, with the later at least worrying from a security standpoint).

This does not answer the "how does this work" part of the Q.

$\endgroup$
4
  • $\begingroup$ Do you have answer to my 2nd question regarding using $\phi(N)$ to solve it but d was actually generated by $\lambda(N)$ ? $\endgroup$
    – Zixi Sean
    Nov 9, 2023 at 19:03
  • $\begingroup$ If it was used a small $d$ (which again, is never the case in practice), it would be $e$ that's generated from $d$ as $d^{-1}\bmodλ(N)$ or $d^{-1}\bmodϕ(N)$, not $d$ generated from $e$. With probability like $1/3$, $ϕ$ and $λ$ yield the same $e$, which would be a first reason why Wiener's attack works. That occurs because $ϕ(N)=gλ(N)$ with $g=\gcd(p-1,q-1)$ typically small (often $2$, $4$, $6$). I'm totally ready to believe Wiener's attack works more often than that, but sorry, I have no clear explanation of why. $\endgroup$
    – fgrieu
    Nov 9, 2023 at 22:00
  • $\begingroup$ "With probability like 1/3, ϕand λ yield the same 𝑒" - so in this case, we would get ed = 1 (mod ϕ) and ed = 1 (mod λ) , right? - where did this 1/3 come from? Any mathmatical proof? $\endgroup$
    – Zixi Sean
    Nov 9, 2023 at 22:50
  • 1
    $\begingroup$ For the lowest positive such $e$, yes. My $1/3$ estimate is derived from simulation over 1000 tests. We could find it mathematically. 1) Estimate the distribution of $g=\gcd(p-1,q-1)$ for large random primes $p$ and $q$ about the same size with $\gcd(p-1,d)=1=\gcd(q-1,d)$ for predetermined random odd $d$. $g=2$ is most common, followed by $4$ and $6$. 2) For given $g$, the probability that the values derived using $ϕ$ and $λ$ are equal is next to $1/g$. We sum these over the aforementioned distribution to find (a good estimate of) the probability that $ϕ$ and $λ$ yield the same $𝑒$. $\endgroup$
    – fgrieu
    Nov 10, 2023 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.