Paranoid Cryptography: Factoring RSA keys from certified smart cards: Coppersmith in the wild

Paranoid Cryptography: Factoring RSA keys from certified smart cards: Coppersmith in the wild

I’ve been reviewing the Pariod Cryptography site [3], and trying to understand the methods that are used to detect a range of threats. One that is outlined is a short decryption exponent in RSA and which uses continued fractions. This was defined in 1990, Michael Wiener [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 that 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.

Code

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

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

The Paranoid Cryptography site is great in getting you thinking about the types of tests that you might apply to your code.

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, here.