Photo by Filip Szalbot on Unsplash

RSA: Continued Fractions — The Wiener Attack

In 1990, Michael Wiener defined a crack on RSA which involved a short decryption exponent and which used continued fractions [1]:

For this, we can create a continued fraction for an RSA modulus and use a power of two. In 2013, Bernstein et al factored a number of RSA keys from a database of over two million keys used in the Tawainese Citizen Identity database:

The research team found that many of the prime numbers found had a repetitive pattern [2]:

Two examples of strange looking prime numbers that were found were:

0xc92424922492924992494924492424922492924992494924492424922492924992494924492424922492924992494924492424922492924992494924492424e5
0xf6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6d…