RSA attack with continued fractions (Wieners attack) I found an article on the internet about an RSA attack with continued fractions.

Given are the following numbers:


$n = 205320043521075746592613$ 
$e = 70760135995620281241019$   
$\frac{e}{n}=[0;2,1,9,6,54,5911,1,5,1,1,...]$


The method says that if $d&lt;n^{\frac{1}{4}}$, then $\frac{e}{n}$ is an approxiation of $\frac{k}{d}$ 

In an example of these method, they take $\frac{k}{d}=[0;2,1,9,6,54]$. 

They say that they stop the continued fraction before 5911, because it's a big number. Can someone please explain me why?
Let $n=pq$ be an RSA modulus.  Let also $e$ be the public exponent and $d = e^{-1} \bmod (p-1)(q-1)$ the matching private exponent.  

From $ed \equiv 1 \pmod{(p-1)(q-1)}$, there exists some integer $k$ such that $$ed = 1 + k(p-1)(q-1) = 1 + k(n-p-q+1) \iff kn-ed=k(p+q-1)-1$$  Dividing through by $dn$ yields 
$$\frac{k}{d}-\frac{e}{n} = \frac{k}{d}\Bigl(\frac1{q}+\frac1{p}-\frac1{n}\Bigr) - \frac1{dn}$$ 

Furthermore, we have the following theorem.

Theorem   If $|\frac{a}{b}-x| &lt; \frac1{2b^2}$ then $\frac{a}{b}$ is a continued fraction approximant for $x$.

So, if the condition of the previous theorem is fulfilled then $k/d$
is a continued approximant for $e/n$. Since $e/n$ is public and since continued fractions can easily be computed, it is possible to find the secret
exponent $d$ (again provided that the condition of the theorem is satisfied).  

In particular, assuming $p \sim q \sim \sqrt{n}$ and $e \sim n$, the condition of the theorem is satisfied for a private exponent $d$ of order up to $n^{1/4}$.

Proof. First, we note that if $e \sim n$ then $k \sim d$.  Moreover, we have
$$\Bigl|\frac{k}{d}-\frac{e}{n}\Bigr| \le \frac{k+1}{dn}+\frac{k}{d}\Bigl(\frac1{p}+\frac1{q}\Bigr) \sim \frac1{n} + \frac1{\sqrt{n}} \sim \frac1{\sqrt{n}}$$

Therefore $|\frac{k}{d}-\frac{e}{n}| &lt; \frac1{2d^2}$ if $d$ is of order at most $n^{1/4}$.



Back to your example, the continued fraction development of $e/n$ is $[0,2,1,9,6,54, 5911, \dots]$. Hence, the successive convergents for $e/n$ are
$$\frac{0}{1}, \frac{1}{2}, \frac{1}{3}, \frac{10}{29}, \frac{61}{177}, \frac{3304}{9587}, \frac{19530005}{56668934}, \dots$$

Provided that the conditions of Wiener's attack are met (i.e., $d$ of order up to $n^{1/4}$), we know that $k/d$ is among them.  Actually, you can check that $d = 9587$ is the corresponding private exponent. 

In this example, we also have $n^{1/4} \approx 674144$ and $56668934 \gg 674144$.