# 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<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?

• Which article? The Internet is a big place :) – Étienne Millon Mar 6 '18 at 15:10
• I think it's the attack from this paper. – puzzlepalace Mar 6 '18 at 18:59
• Winston, could you please indicate if that is indeed the paper, and indicate if the supplied answer matches your expectations (e.g. by accepting the answer if you deem it correct?) – Maarten Bodewes Mar 9 '18 at 15:35

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| < \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}| < \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$.