RSA: Continued Fractions — The Wiener Attack

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

0xf6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdbc1

With the 184 keys that were factored, they found that 103 keys shared the same prime numbers. In order to detect these repetitive patterns, we can define that these primes are close to:

and where a/b is a small fraction and m defines the number of bits in the prime number. This can also be the case for the RSA modulus and when two prime numbers with repeated patterns are multiplied together. We can use a continued fraction to detect the forms.

Rather than go into the details of the method, here is the code derived from [3] [here]:

# Code based on https://github.com/google/paranoid_crypto
import gmpy2
import random
import sys

def DivmodRounded(a: int, b: int):

  d= (b + 1) // 2
  x, y = divmod(a + d, b)
  return x, y

def ContinuedFraction(a: int, b: int):

  res = []
  r, s, t, u = 1, 0, 0, 1
  # loop invariant: fraction = r*x + s / t*x + u
  # where x is the remainder of the continued fraction
  while b:
    q, rem = divmod(a, b)
    a, b = b, rem
    r, s = r * q + s, r
    t, u = t * q + u, t
    res.append((q, r, t))
  return res

def CheckContinuedFraction(n: int, bound: int):
 
  m = 2**n.bit_length()
  cf = ContinuedFraction(n, m)
  x = 2**(n.bit_length() // 2)
  for quot, _, v in cf:
    r, c = DivmodRounded(n * v, x)
    a, b = DivmodRounded(r, x)
    if a and c and gmpy2.is_square(b * b - 4 * a * c):
      t = gmpy2.sqrt(b * b - 4 * a * c)
      for rt in (t, -t):
        p = gmpy2.gcd(n, 2 * a * x + b + rt)
        if 1 < p < n:
          return False, [p, n // p]
    if quot >= bound:
      # There is a large coefficient in the continued fraction of n and m,
      # but no factorization was found.
      return False, []
  return True, []

nsize=512

p = 0xfa157ca157ca157ca157ca157ca1647
q = 0xc1acb1acb1acb1acb1acb1acb1342bb

if (len(sys.argv)>1):
    p=int(sys.argv[1],16)
if (len(sys.argv)>2):
    q=int(sys.argv[2],16)

n=p*q

print(f"p={hex(p)}")  
print(f"q={hex(q)}") 
print(f"n={hex(n)}")

m = 2**18

rtn=CheckContinuedFraction(n,m)
if (rtn[0]==False):
 print("Key is weak")
else:
 print("Key is not weak")

A sample run is [here]:

p=0xc92424922492924992494924492424922492924992494924492424922492924992494924492424922492924992494924492424922492924992494924492424e5

q=0xf6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdb6ddb6d6db66db6b6dbb6dbdbc1

n=0xc1f57977f43e9f591e0aec689a1ed248672ede0b32f154e612482b18da1f1cbd47d7bd638a7183e94d0f5b6f5cbe25e1029adcb9bfff9a2171a48e5e7ac4361b6c67d6366db997833976343c3977978458d32f05c14cdb6bc68758d243ecc6884923829b53971a202f065e0ad0fa29cae0a6db6e1a1ff58d58d0d0fa6db6b7a5

Key is weak

Conclusions

Dan Bernstein’s paper in 2013 caused a great wave of interest, and where so-called randomly generated prime numbers were proven to be not to random. The Paranoid Crypt library does a great job of detecting these vulnerable keys. you can try here:

https://asecuritysite.com/rsa/rsa_03

References

[1] Wiener, M. J. (1990). Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information theory, 36(3), 553–558.

[2] Bernstein, D. J., Chang, Y. A., Cheng, C. M., Chou, L. P., Heninger, N., Lange, T., & Someren, N. V. (2013, December). Factoring RSA keys from certified smart cards: Coppersmith in the wild. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 341–360). Springer, Berlin, Heidelberg.

[3] Binarbosa, Pedro and Bleichenbacher, Daniel, Paranoid Cryptography, https://github.com/google/paranoid_crypto