THE GARDEN

Wiener's Attack (Continued Fractions, Small Private Exponent)

Updated 19 Sep 2026

• •

  What it is

  • •

    If an RSA private exponent $d$ is unusually small relative to the modulus — specifically $d < \frac{1}{3}N^{1/4}$ — the fraction $e/N$ turns out to be extremely close to $k/d$ for some integer $k$, close enough that $k/d$ shows up as one of the convergents of the continued-fraction expansion of $e/N$. Continued fractions have only $O(\log N)$ convergents, and each is cheap to test (reconstruct a candidate $\phi(N)$ from it, then check whether the resulting quadratic for $p,q$ has integer roots multiplying back to $N$) — so trying all of them efficiently finds the correct $d$ without ever touching the factorization directly.

• •

  When to apply

  • •

    An RSA implementation deliberately (or accidentally) picks a small $d$ first for speed, then derives $e = d^{-1} \bmod \phi(N)$ — producing a huge, "random-looking" $e$ that gives no obvious hint by itself, but the smallness of $d$ is exactly what this attack targets, using only the public $(N,e)$.

• •

  Math

  • •

    $ed=1+k \phi(N)$ for some integer $k < d$. Since $\phi(N) \approx N$, $\frac{e}{N} \approx \frac{k}{d}$​, and this approximation is tight enough (given $d$ small) that $k/d$ is guaranteed to appear among $e/N$'s continued-fraction convergents.

• •

  Worked example

  • •

    Take $N=90581$, $e=17993$, and $d=5$. Since $90581=239\cdot379$, $\varphi(N)=89964$ and $ed=89965=1+\varphi(N)$. Continued fractions of $e/N$ include $1/5$, and testing $d=5$ yields the exact factorization. The classic guarantee needs balanced primes and roughly $d<N^{1/4}/3$.

• •

  Python

  • •

    def continued_fraction(num, den):
        cf = []
        while den:
            cf.append(num // den)
            num, den = den, num % den
        return cf
    
    def convergents(cf):
        convs, h0, h1, k0, k1 = [], 0, 1, 1, 0
        for a in cf:
            h0, h1 = h1, a*h1 + h0
            k0, k1 = k1, a*k1 + k0
            convs.append((h1, k1))
        return convs
    
    for k, d in convergents(continued_fraction(e, N)):
        if k == 0 or (e*d - 1) % k: continue
        phi = (e*d - 1) // k
        b = N - phi + 1
        disc = b*b - 4*N
        if disc < 0: continue
        sq = isqrt(disc)
        if sq*sq == disc and (b+sq) % 2 == 0:
            p, q = (b+sq)//2, (b-sq)//2
            if p*q == N:
                break   # d is the recovered private exponent
    

• •

  SageMath

  • •

    Sage's continued_fraction(e/N) and .convergents() do the bookkeeping for you, but the core search loop is identical either way — this isn't a case where Sage changes the approach, just tidies the syntax.

• •

  Related

  • •

    RSA (Textbook Construction)

  • •

    Boneh-Durfee Attack (Lattice Attack on Small RSA Private Exponent)

• •

  Cards

  • •

    What condition on d makes Wiener's attack succeed?

    • •

      d < (1/3)·N^(1/4) — d unusually small relative to the modulus.

  • •

    Why does the continued-fraction expansion of e/N reveal k/d specifically?

    • •

      Because ed = 1 + kφ(N), and φ(N) ≈ N, so e/N ≈ k/d closely enough (given d is small) to be one of the finitely many convergents of e/N's continued fraction.

◌ Explore connections in Graph view