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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.