I am researching Wiener's attack on the RSA cryptosystem. The theorem, found here beginning on page 4, is as follows:
Let $N=pq$ with $q < p < 2q$. Let $d < \frac{1}{3}N^\frac{1}{4}$. Given $(e, N)$ with $ed = 1\bmod\varphi({N})$, a malicious attacker can efficiently recover $d$.
I am stuck near the very end of the proof:
$\left|\frac{e}{N} - \frac{k}{d}\right| \leq \frac{1}{d\sqrt[4]{N}} < \frac{1}{2d^2}$.
This is followed by the statement "This is a classic approximation relation. The number of fractions $\frac{k}{d}$ with $d
I don't understand what is meant by classic approximation relation, nor where the bound $log_2 N$, comes from. Could anyone help?
Answer
By Legendre's theorem in Diophantine approximations, if $|\alpha - \frac{k}{d}|< \frac{1}{2d^2}$, then $k/d$ has to be a convergent $p_m/q_m$ of continued fraction expansion of $\alpha$. Since the denominators $q_m$ grow exponentially ($q_m \geq F_m$, where $F_m$ is $m$-th Fibonacci number), there are less then $\log_2 N$ convergents (i.e. candidates for $k/d$) with $k
No comments:
Post a Comment