6
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Which article? The Internet is a big place :) $\endgroup$ – Étienne Millon Mar 6 '18 at 15:10
  • $\begingroup$ I think it's the attack from this paper. $\endgroup$ – puzzlepalace Mar 6 '18 at 18:59
  • $\begingroup$ 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?) $\endgroup$ – Maarten Bodewes Mar 9 '18 at 15:35
7
$\begingroup$

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

| improve this answer | |
$\endgroup$

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.