in a secure RSA implementation we usually fix the public exponent $e$ to be some odd value, usually $3$ or $2^{16} + 1$, and we compute $d$ such that $ed \equiv 1 \mod \phi$, this implies that $d$ would be 'big' compared to $e$, but what if instead of this, we fixed $d$ first and then computed $e$, for example in this python code:

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long

FLAG = b"crypto{?????????????????????????}"

m = bytes_to_long(FLAG)

def get_huge_RSA():
    p = getPrime(1024)
    q = getPrime(1024)
    N = p*q
    phi = (p-1)*(q-1)
    while True:
        d = getPrime(256)
        e = pow(d,-1,phi)
        if e.bit_length() == N.bit_length():
            break
    return N,e


N, e = get_huge_RSA()
c = pow(m, e, N)

print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')

first thing we notice in this code is that $d \le N^{\frac{1}{8}}$ and how unusually close value of $e$ is to $N$, It turns out this code is crackable[^1] using Wiener's attack! Wiener's attack states that:

Wiener's Theorem: In an RSA cryptosystem, if we know that $d < \frac{1}{3} N^{\frac{1}{3}}$ then we can efficiently retrieve $d$ only using $(N, e)$

Let's define 'efficiently' as running under 1 second in any modern computer, the method we'll state has a complexity $O(\log N)$ which should satisfy that even for RSA-4096

Wiener's attack relies mainly on "Legendre's theorem" which states that:

Legendre's Theorem: every fraction $\frac{p}{q}$ such that $p$ and $q$ are coprime which satisfies the inequality $|\alpha−\frac{p}{q}|<​\frac{1}{2q^2}$ is convergent to $\alpha$, in other words $\frac{p}{q}$ exists in the continued fraction of $\alpha$.

This is a really powerful claim, enough of the bargling and let's get into the math now!

by definition we have $$ed \equiv 1 \mod \phi$$$$\implies ed - 1 = k\phi$$ for some $k \in \mathbb{Z}$, now divide both sides by $d\phi$: $$\frac{e}{\phi} - \frac{1}{d\phi} = \frac{k}{d} \implies \Big| \frac{e}{\phi} - \frac{k}{d} \Big| = \frac{1}{d\phi}$$ we have $p+q-1 < 3\sqrt{N}$ hence $| N - \phi | < 3\sqrt{N}$, notice that t'ill now we dont know $phi$, so let's take $N \cong \phi$: $$\Big| \frac{e}{N} - \frac{k}{d} \Big| = \Big| \frac{ed - k\phi - kN+k\phi}{Nd} \Big| = \Big| \frac{1 - k(N - \phi)}{Nd} \Big| < \frac{3k}{d\sqrt{N}}$$ and since we have $k < d < \frac{1}{3}N^{1/4}$: $$\frac{3k}{d\sqrt{N}} < \frac{1}{dN^{\frac{1}{4}}} < \frac{1}{2d^2}$$ since $2d < N^{\frac{1}{4}}$ implies $\frac{1}{2d} > \frac{1}{N^{\frac{1}{4}}}$, and by Legendre's Theorem, it's satisfactory to find the continued fraction of $\frac{e}{N}$ and do a check if $d$ works or not.

This completes the proof of Wiener's attack, now let's get to implementation!