Here's the Wiener's attack as I understand it.

Suppose $n=pq$ with $q < p < 2q$, and $d < n^{1/4}/3$ where $ed=k\phi(n)+1$ and $e < \phi(n)$.

$$\begin{align*} n-\phi(n) &=n-(p-1)(q-1)\\ &= n-(n-p-q+1) \\ &= p+q-1 \\ &< 2q+q-1\\ &=3q-1 \\ &< 3\sqrt{n} \end{align*}$$

and $e<\phi(n)\implies ke < k\phi(n) =ed -1 < ed \implies k<d<n^{1/4}/3$.

Therefore, $$\begin{align*} \left|\frac{e}{n}-\frac{k}{d}\right| &= \left|\frac{ed-kn}{nd}\right|\\ &=\left|\frac{de-k\phi(n)-(kn+k\phi(n))}{nd}\right|\\ &= \left|\frac{1-k(n-\phi(n))}{nd}\right|\\ &\le \frac{3k\sqrt{n}}{nd} \\ &\le \frac{3(n^{1/4}/3)\sqrt{n}}{nd} = \frac{1}{dn^{1/4}}\\ &< \frac{1}{2d^2}. \end{align*}$$

The last inequality (by some theorem about continued fraction) and $gcd(d,k)=1$ imply that $\frac{k}{d}$ is a convergent in simple continued fraction of $\frac{e}{n}$.

Why does $e>n^{3/2}$ imply that $k/d$ is not a convergent in simple continued fraction of $e/n$? Or why does such an $e$ prevent Wiener's attack?

It suffices to show that $|e/n-k/d| > 1/d^2$.

Thank you!

  • $\begingroup$ Note that if $e>n$ then $e>\phi(N)$ and $k < n^{1/4}/3$ doesn't hold. So you can't replace $k$ by $n^{1/4}/3$ in the second last inequality. But I'm not an expert in continued fractions or in Weiner attack. $\endgroup$
    – Ruggero
    Commented Dec 27, 2015 at 11:19

1 Answer 1


In Wiener's attack $k$ is a small number ($k<d$). If we set $e^{'}=e+t\phi(n)$ for some large $t$ then $e^{'}$ can be used in place of $e$ for message encryption.Also the k became a big number and we can't using of Wiener's attack.For more detail you can see "Twenty Years of Attacks on the RSA Cryptosystem".

  • $\begingroup$ I think that is true $\endgroup$ Commented Jan 11, 2016 at 11:49

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.