# Why $e>n^{3/2}$ prevents Wiener's attack

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!

• 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. – Ruggero Dec 27 '15 at 11:19

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".