4
$\begingroup$

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!

$\endgroup$
  • $\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 Dec 27 '15 at 11:19
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think that is true $\endgroup$ – Masoud Eskandari Jan 11 '16 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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