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.