Few years ago I wrote a brief paper regarding the RSA cryptosystem and the attack M.J. Wiener published in 1990. I tried to create a self-contained work, emphasising the power of playing with continued fractions using Legendre theorem. The attack states that when there is a small private exponent, the RSA module \(N\) could be factorized in \(\mathcal{O}\big(log_2(N)\big)\), let’s take a peak on how it works using an example.
There are three numbers you need to know when we talk about the RSA cryptosystem: the module \(N\) plus the exponents \(e\) and \(d\). So, given the public key \((e,N)\) of an RSA with a small private exponent \(d\)
\[(e,N) = (58549809,2447482909)\]
the expansion of \(\frac{e}{N}\) and its convergents will be
\[\frac{e}{N} = \bigl[\,0;\,41,\,1,\,4,\,23,\,\dots\,\bigr]\] \[\{ c_i \}_{i{\leq}15} = \biggl\{0,\,\frac{1}{41},\,\frac{1}{42},\,\frac{5}{209},\,\frac{116}{4849},\,\dots\biggr\}\]
Using the search algorithm derived from Wiener Theorem, we notice that the fourth convergent \(c_3{=}\frac{5}{209}\) is the right candidate \(\widetilde{\phi}\) for the Euler function \(\phi(N)\):
\[\biggl\lfloor \frac{e}{c_3} \biggr\rfloor = \biggl\lfloor \frac{58549809}{\frac{5}{209}} \biggr\rfloor = 2447382016\]
Now that we found a possible value for \(\phi\), we won: the two prime factors of the RSA module have to be \(60317\) and \(40577\). It was too quick, wasn’t it? Take a look at the paper here or in the window below, it will satisfy any doubts and show you some magic in Wolfram Mathematica.
I put some effort on the appearance too: all the work is written in \(\LaTeX\) with the Tufte-LaTeX package, plus few modifications here and there allowed me to squeeze all the content in about 20 pages.