# 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[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


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.

• Do you have answer to my 2nd question regarding using $\phi(N)$ to solve it but d was actually generated by $\lambda(N)$ ? Commented Nov 9, 2023 at 19:03
• 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.
– fgrieu
Commented Nov 9, 2023 at 22:00
• "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? Commented Nov 9, 2023 at 22:50
• 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 $𝑒$.
– fgrieu
Commented Nov 10, 2023 at 8:01