Wiener's attack

Wiener's attack, named after cryptologist Michael J. Wiener, is a type of cryptographic attack against the RSA cryptosystem. The attack uses continued fraction representation to expose the private key ${\displaystyle d}$ when ${\displaystyle d}$ is small.

Background on RSA

Main article: RSA (algorithm)

The RSA system is a public key cryptosystem, described as follows. Two large primes ${\displaystyle p,q}$ are chosen and the product ${\displaystyle N=pq}$, known as the modulus, is computed. The Euler totient of ${\displaystyle N}$ is calculated as ${\displaystyle \varphi (N)=(p-1)(q-1)}$. An integer ${\displaystyle e}$, called the public exponent, is chosen, and an integer ${\displaystyle d}$ satisfying ${\displaystyle ed\equiv 1\ ({\text{mod }}\varphi (N))}$ is found by use of the Euclidean algorithm.

The public key consists of the pair ${\displaystyle \langle N,e\rangle }$, while the private key is the integer ${\displaystyle d}$. Encryption of a message, encoded as an integer ${\displaystyle m}$, is performed by taking ${\displaystyle c\equiv m^{e}\ ({\text{mod }}N)}$, while decryption of ciphertext ${\displaystyle c}$ is performed by taking ${\displaystyle m\equiv c^{d}\ ({\text{mod }}N)}$. The prime factorization of ${\displaystyle N}$ is also private and may be included in the private key for a more efficient decryption algorithm.

A possible attack on this system involves either directly finding ${\displaystyle d}$ given ${\displaystyle N}$, or factorizing ${\displaystyle N}$ first and then computing ${\displaystyle d}$ as before using the Euclidean algorithm. Note that it is possible to factorize ${\displaystyle N}$ with the knowledge of any one of ${\displaystyle p,q}$ or ${\displaystyle \varphi (N)}$.

Small private key

For performance reasons, one might decide to use a small value of ${\displaystyle d}$ in order to speed up decryption. However, Wiener's attack shows that choosing a small value for ${\displaystyle d}$ will result in an insecure system in which an attacker can recover all secret information, i.e., break the RSA system. This break is based on Wiener's theorem, which holds for small values of ${\displaystyle d}$. Wiener has proved that the attacker may efficiently find ${\displaystyle d}$ when ${\displaystyle d<{\frac {1}{3}}N^{1/4}}$. ^[1]

Wiener's paper also presented some countermeasures against his attack that allow fast decryption. Two techniques are described as follows.

Choosing large public key: Replace ${\displaystyle e}$ by ${\displaystyle e'}$, where ${\displaystyle e'=e+k\varphi (N)}$ for some large integer ${\displaystyle k}$. When ${\displaystyle e'}$ is large enough, for example ${\displaystyle e'>N^{3/2}}$, Wiener's attack cannot be applied regardless of how small ${\displaystyle d}$ is.

Using the Chinese remainder theorem : A more efficient decryption algorithm, known as CRT-RSA, may be performed by using the primes ${\displaystyle p,q}$ as the moduli during decryption instead of ${\displaystyle N}$.

Suppose one chooses ${\displaystyle d}$ such that both ${\displaystyle d_{p}\equiv d\ ({\text{mod }}p-1)}$ and ${\displaystyle d_{q}\equiv d\ ({\text{mod }}q-1)}$ are small but ${\displaystyle d}$ itself is not, then a fast decryption of the ciphertext ${\displaystyle c}$ is performed as follows:

1. First compute ${\displaystyle m_{p}=c^{d_{p}}\ ({\text{mod }}p),m_{q}\equiv c^{d_{q}}\ ({\text{mod }}q)}$.
2. Use the Chinese remainder theorem to compute the unique value of ${\displaystyle 0\leq m<N}$ that satisfies ${\displaystyle m\equiv m_{p}\ ({\text{mod }}p)}$ and ${\displaystyle m\equiv m_{q}\ ({\text{mod }}q)}$. The resulting ${\displaystyle m}$ satisfies ${\displaystyle m\equiv c^{d}\ ({\text{mod }}N)}$. The point is that Wiener's attack does not apply here because the value of ${\displaystyle d{\text{ mod }}\varphi (N)}$ can be large. ^[1]

See also: RSA (algorithm) § Using the Chinese remainder algorithm

How the attack works

Since ${\displaystyle ed\equiv 1\ ({\text{mod }}\varphi (N))}$, there exists an integer ${\displaystyle k}$ such that

${\displaystyle ed=k(p-1)(q-1)+1.}$

Dividing by ${\displaystyle Nd=pqd}$ gives

${\displaystyle {\frac {e}{N}}={\frac {k}{d}}(1-\delta )}$, where ${\displaystyle \delta ={\frac {p+q-1-{\frac {1}{k}}}{pq}}}$ is small.

Importantly, the fraction ${\displaystyle e/N}$ consists of public data and is approximated by the fraction ${\displaystyle k/d}$ consisting of private data. Wiener's attack exploits this fact by using the continued fraction expansion of ${\displaystyle e/N}$ to generate fractions close to ${\displaystyle e/N}$, known as convergents, and guessing ${\displaystyle k}$ and ${\displaystyle d}$ to be the numerator and denominator of these approximating fractions. Note that the continued fraction for a rational number appears as a byproduct of the Euclidean algorithm and may be computed quickly. When the denominator ${\displaystyle d}$ is small enough relative to ${\displaystyle N}$, the fraction ${\displaystyle k/d}$ is guaranteed to be one of these convergents.

The guess can be checked by using ${\displaystyle k}$ and ${\displaystyle d}$ to compute ${\displaystyle \varphi (N)=(ed-1)/k}$ and then checking if this guess for ${\displaystyle \varphi (N)}$ factorizes ${\displaystyle N}$ by solving the quadratic equation

${\displaystyle x^{2}-(N-\varphi (N)+1)x+N=0.}$

Wiener's theorem

Let ${\displaystyle N=pq}$ with ${\displaystyle q<p<2q}$, and let ${\displaystyle d<{\frac {1}{3}}N^{1/4}}$.

Given ${\displaystyle \langle N,e\rangle }$ with ${\displaystyle ed\equiv 1\ ({\text{mod }}\varphi (N))}$, the attacker can efficiently recover ${\displaystyle d}$. ^{[1] [2]}

Example

Suppose that the public keys are ${\displaystyle \langle N,e\rangle =\langle 90581,17993\rangle }$. The attack should determine ${\displaystyle d}$. By using Wiener's theorem and continued fractions to approximate ${\displaystyle d}$, first we try to find the continued fractions expansion of ${\textstyle {\frac {e}{N}}}$. Note that this algorithm finds fractions in their lowest terms. We know that

${\displaystyle {\frac {e}{N}}={\frac {17993}{90581}}={\cfrac {1}{5+{\cfrac {1}{29+\dots +{\cfrac {1}{3}}}}}}=\left[0,5,29,4,1,3,2,4,3\right]}$

According to the continued fractions expansion of ${\textstyle {\frac {e}{N}}}$, all convergents ${\textstyle {\frac {k}{d}}}$ are

${\displaystyle {\frac {k}{d}}=0,{\frac {1}{5}},{\frac {29}{146}},{\frac {117}{589}},{\frac {146}{735}},{\frac {555}{2794}},{\frac {1256}{6323}},{\frac {5579}{28086}},{\frac {17993}{90581}}.}$

We can verify that the first convergent does not produce a factorization of N. However, the convergent ${\textstyle {\frac {1}{5}}}$ yields

${\displaystyle \varphi (N)={\frac {ed-1}{k}}={\frac {17993\times 5-1}{1}}=89964}$

Now, if we solve the equation

${\displaystyle x^{2}-\left(N-\varphi (N)+1\right)x+N=0}$

${\displaystyle x^{2}-618x+90581=0,}$

then we find the roots which are ${\displaystyle x=379;\ 239}$. Therefore we have found the factorization

${\displaystyle N=90581=379\times 239=p\times q}$.

Notice that, for the modulus ${\displaystyle N=90581}$, Wiener's theorem will work if

${\displaystyle d<{\frac {1}{3}}N^{1/4}\approx 5.7828}$.

Proof of Wiener's theorem

The proof is based on approximations using continued fractions. ^[1]

Since ${\displaystyle ed\equiv 1\ ({\text{mod }}\varphi (N))}$ there exists a ${\displaystyle k}$ such that ${\displaystyle ed=k\varphi (N)+1}$. Therefore

${\displaystyle \left|{\frac {e}{\varphi (N)}}-{\frac {k}{d}}\right\vert =\left|{\frac {ed-k\varphi (N)}{d\varphi (N)}}\right|={\frac {1}{d\varphi (N)}}}$.

Hence, ${\displaystyle k/d}$ is an approximation of ${\displaystyle e/\varphi (N)}$. Although the attacker does not know ${\displaystyle \varphi (N)}$, they may use ${\displaystyle N}$ to approximate it.

To see this, note the hypothesis ${\displaystyle q<p<2q}$ implies ${\displaystyle N=pq>q^{2}}$, and so

${\displaystyle N-\varphi (N)=p+q-1<3q-1<3{\sqrt {N}}}$.

Also, ${\displaystyle N-\varphi (N)>0}$ for ${\displaystyle N>1}$.

The above estimate lets us approximate ${\displaystyle ed=k\varphi (N)+1}$ by ${\displaystyle kN+1}$ (relative to ${\displaystyle k}$):

${\displaystyle |ed-(kN+1)|=|(k\varphi (N)+1)-(kN+1)|=|k(\varphi (N)-N)|<3k{\sqrt {N}}}$.

In fact, because ${\displaystyle N-\varphi (N)\geq 1}$, we can approximate ${\displaystyle ed}$ by ${\displaystyle kN}$ (relative to ${\displaystyle k}$):

${\displaystyle |ed-kN|=|1-k(N-\varphi (N))|=k(N-\varphi (N))-1<k(N-\varphi (N))<3k{\sqrt {N}}}$.

Therefore,

${\displaystyle {\begin{aligned}\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert &=\left\vert {\frac {ed-kN}{Nd}}\right\vert \\&<{\frac {3k{\sqrt {N}}}{Nd}}={\frac {3k}{d{\sqrt {N}}}}\end{aligned}}}$

Now, since ${\displaystyle e<\varphi (N)}$,

${\displaystyle k={\frac {ed-1}{\varphi (N)}}<{\frac {ed}{\varphi (N)}}<d<{\frac {1}{3}}N^{1/4}.}$

Therefore,

${\displaystyle \left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert <{\frac {3k}{d{\sqrt {N}}}}<{\frac {1}{dN^{1/4}}}<{\frac {1}{2d^{2}}}}$

where the last inequality uses ${\displaystyle 2d<N^{1/4}}$ from the assumption on ${\displaystyle d}$.

Now in general, if ${\textstyle |x-{\frac {a}{b}}|<{\frac {1}{2b^{2}}}}$, then ${\textstyle {\frac {a}{b}}}$ is a convergent of ${\displaystyle x}$, so ${\displaystyle k/d}$ appears among the convergents of ${\displaystyle e/N}$. We may guess ${\displaystyle k}$ and ${\displaystyle d}$ to be the numerator and denominator of these convergents respectively, and verify if they are correct by computing ${\displaystyle \varphi (N)}$ and attempting to factorize ${\displaystyle N}$ with these guesses. Eventually one such guess (of which there are ${\displaystyle O(\log N)}$ of them ^[1.1] ) will be correct.

Python implementation

The following is a minimal implementation of Wiener's attack in Python, given a vulnerable system with public key ${\displaystyle \langle N,e\rangle }$, based on an online implementation ^[3] .

importmath# Convergents of num/den as fractionsdefconvergents(num,den):# The Euclidean algorithm gives the denominators, then compute convergentsni,di=(0,1),(1,0)whileden!=0:div=num//dennum,den=den,num%denni=(ni[1],div*ni[1]+ni[0])di=(di[1],div*di[1]+di[0])yield(ni[1],di[1])# Factorizes N when successfuldefwiener(N,e):fork_guess,d_guessinconvergents(e,N):ifk_guess==0:continuephi_guess=(e*d_guess-1)//k_guess# Solve the quadraticcoeff=N-phi_guess+1disc=coeff*coeff-4*Nifcoeff<=0orcoeff>=N+1ordisc<0:continueroot_disc=math.isqrt(disc)ifroot_disc*root_disc!=disc:continuereturn((coeff+root_disc)//2,(coeff-root_disc)//2)returnNone

References

1. Boneh, Dan. "Twenty years of attacks on the RSA cryptosystem" (PDF). Notices of the American Mathematical Society . 46 (2): 203–213.
   1. Proof of Theorem 2
2. Wiener, Michael J. (1990). "Cryptanalysis of short RSA secret exponents". IEEE Transactions on Information Theory. 36 (3). IEEE: 553–558. Bibcode:1990ITIT...36..553W. doi:10.1109/18.54902.
3. Kedmi, Sagi. "Crypto Classics: Wiener's RSA Attack". Sagi Kedmi. Retrieved 1 November 2026.

Further reading

• Coppersmith, Don (1996). Low-Exponent RSA with Related Messages. Springer-Verlag Berlin Heidelberg.

• Dujella, Andrej (2004). "Continued fractions and RSA with small secret exponent". arXiv: cs/0402052 .
• Python Implementation of Wiener's Attack.
• R. Stinson, Douglas (2002). Cryptography Theory and Practice (2e ed.). A CRC Press Company. pp. 200–204. ISBN   1-58488-206-9.