Few years ago I wrote a brief paper regarding the RSA protocol 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 under certain conditions1 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\). Was it too quick? Take a look at the paper below (or watch it in fullscreen mode), it will satisfy any doubts and show you some Wolfram Mathematica code.

  1. The sufficient condition for the attack to be effective lies in the private exponent \(d\), simply called small private exponent.↩︎