Paranoid Cryptography: Fermat’s Theorem For Cracking RSA

Paranoid Cryptography: Fermat’s Theorem For Cracking RSA

Someone sent me a great GitHub link from Google. It is named Project Paranoid and allows developers to check for a range of cryptographic weaknesses [here]:

The library is created by two leading cryptographers: Pedro Barbosa and Daniel Bleichenbacher. So, let’s look at one of the examples.

Fermat’s factorization

Pierre de Fermat defined a factorization method which could factor prime number factors if these prime numbers were close to each other. In RSA, we use a modulus (N) and which is the multiplication of two prime numbers (p and q). If these prime numbers are close to each other, then N can be factorized, and the RSA methods can be easily broken.

In March 2022, it was discovered that a Rambus cryptographic module was selecting a prime number and then selecting another which was relatively close. These led to vulnerabilities in a number of printers which used Rambus module [here]:

It affected Fuji Xerox and Canon printers for the keys that generated a CSR (Certificate Signing Request).

Fermat’s method

In this case, we will use Fermat’s method to factorize a modulus and where the prime numbers are within 2¹⁰⁰ of each other. We will also try two random prime numbers and see if we can factorize. With Fermat’s factorization algorithm, we assume that two large prime numbers can be written as:

N=(a−b)(a+b)

We then have the first prime as a−b and the second one as a+b. If the prime numbers are close, the value of a will be close to the square root of N. We could thus guess the value of a from the square root of N and then increment the value of a and for each guess, we take:

b²=a²−N

If the result is then a square value, we have the right values for a and b, and compute:

p=a+b

and:

q=a−b

The basic algorithm is then [taken from [here]:

def FermatFactor(n: int, max_steps: int):
    if n % 2 == 0:
        return 2, n // 2

    a = gmpy2.isqrt(n)

    if a * a == n:
        return a, a

    a += 1  # ceil(sqrt(n))
    b2 = a * a - n

    for _ in range(max_steps):
        if gmpy2.is_square(b2):
            return a + gmpy2.isqrt(b2), a - gmpy2.isqrt(b2)

        b2 += a
        a += 1
        b2 += a
    return None

In this case, we use gmpy2 to compute the integer square roots, and return None if we cannot factorize the modulus.

Code

The following is an outline of the code [here]:

# Some code derived from https://github.com/google/paranoid_crypto/
import gmpy2
from gmpy2 import mpz, xmpz
import random
import sys

class RSAKey:
    def __init__(self): # constructor method
      e=bytearray(0)
      n=bytearray(0)  

def Int2Bytes(int_val: int):
    return int.to_bytes(int(int_val), (int_val.bit_length() + 7) // 8, 'big')

def Bytes2Int(bytes_val: bytes) -> int:
    return int.from_bytes(bytes_val, 'big')

def FermatFactor(n: int, max_steps: int):
    if n % 2 == 0:
        return 2, n // 2

    a = gmpy2.isqrt(n)

    if a * a == n:
        return a, a

    a += 1  # ceil(sqrt(n))
    b2 = a * a - n

    for _ in range(max_steps):
        if gmpy2.is_square(b2):
            return a + gmpy2.isqrt(b2), a - gmpy2.isqrt(b2)

    b2 += a
    a += 1
    b2 += a
    return None

nsize=512
rsa_key1=RSAKey()
max_steps = 2

if (len(sys.argv)>1):
	nsize=int(sys.argv[1])

print(f"Prime number size: {nsize} bits\n")
p = gmpy2.next_prime(random.getrandbits(nsize))
q = gmpy2.next_prime(p + 2**100)

rsa_key1.n=p * q 
print(f"== Try with p and q close to each other (within 2^100)==\n")
print(f"N={rsa_key1.n}")

result = FermatFactor(rsa_key1.n, max_steps)

try:
    if ((result[0] * result[1])==rsa_key1.n):
        print("Able to factor")
except:
    print("Success: Not able to factor")

p = gmpy2.next_prime(random.getrandbits(nsize))
q = gmpy2.next_prime(random.getrandbits(nsize))

rsa_key1.n=p * q 
print(f"\n== Try with p and q as random primes==\n")
print(f"N={rsa_key1.n}")
result = FermatFactor(rsa_key1.n, max_steps)
try:
    if ((result[0] * result[1])==rsa_key1.n):
        print("Able to factor")
except:
    print("Success: Not able to factor")

A sample run is [here]:

Prime number size: 1024 bits

== Try with p and q close to each other (within 2^100)==

N=8704309713329794391787624088108390166615849526057044757655516652810445455914313355842186472690420915893317060751453277778542906673834732917538129080446534899759462232344761961777709717348529328041820323137303783139690224592767828846152165399673670470727994987601110757086145476515673676804574894909120950870030110882550773368703788956669391140946224924453861287632727300274444819159716032656503839867275866813467907906743755263158792652129833239456645743597048914452179624531058777426167679242043718835427173969255560282059183112627328833413034912545460129076385894403425462913104262356751319381061567320897200070529
Able to factor

== Try with p and q as random primes==

N=2806536120217532769357004324632105544640202339383143017293712949521245614722233021581036516596071505250034801057287477157268160558698601789455741407795165358191639339558213929886161439925139061910830407043601191511045492966225905624106334993942778987072311536110374325366438290949898913469379076821547872825580262409268517753058270215937300766583709371380070288391119223969477986239799834024409957102030291794504709067491856986569899643167245375608838598471909576619845735607779704575879673411005592241759833515604191144488269194649614610246103730921220483235606158755534260032861437892169311214665093388070677322881
Success: Not able to factor

Conclusion

You must worry when such a novice mistake is created by an experienced team and used within commonly used products.

References

Barbosa, Pedro and Bleichenbacher, Daniel, Paranoid Crypto, Aug 2022, https://github.com/google/paranoid_crypto