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:
0xc92424922492924992494924492424922492924992494924492424922492924992494924492424922492924992494924492424922492924992494924492424e50xf6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6d…