In 1643 Pierre de Fermat described a factorization algorithm in a letter that works well for composite numbers that are the product of two "close" primes

Modulus N

Exponent e

N = p * q

p, q: secret prime numbers

N = p * q

N = (a+b)(a-b)

a: Middle between p, q

b: Distance of p, q to middle

N = (a+b)(a-b)

N = a^2 - b^2

b^2 = a^2 - N

*If* the difference between the two primes p, q is small then a is close to the square root of N

We can make guesses for a, starting with the rounded square root of N

b^2 = a^2 - N

If b^2 is a square then we found the right a (and can calculate b, and from that p, q)

Can we break real RSA keys with this?

This algorithm is widely known in the literature, but to my knowledge no attacks against production RSA keys have been described

I checked large sets of public RSA keys for vulnerable ones

155 self-signed TLS certificates in Internet-wide TLS scans

(Most with very similar common names, so likely same source)

Tracing back the IPs via Censys I could access some web interfaces and learned they were created by Fujifilm printers

Printers use Rambus Safezone cryptographic module

17 keys in publicly trusted TLS certificates in Certificate Transparency logs

I tried to contact all owners of the corresponding domain names, in two cases I learned they were created by Canon printers

Certificates, as far as they were still valid, were reported to the responsible certificate authorities and revoked

Some certificate authorities have implemented checks for this vulnerability to prevent new certificates from being issued

All vulnerabilities have been disclosed to the affected hardware and software vendors, all have published or plan to publish software updates

All vulnerable certificates where created in 2020 or later

(That's probably the reason noone has found this before)

No vulnerable SSH keys found

No vulnerable DNSSEC keys found

(But only small collection checked)

4 PGP keys found, but they all looked like test keys

How does this happen?

Idea 1: Neighboring primes

We can imagine a flawed RSA key generation algorithm like this:

- Create random number X
- Search for next prime after X and use it as p
- Search for next prime after p and use it as q

This would create p, q with a small difference (thousands or less) - factoring N is easy

Idea 2: Static bits

- Create two random primes, but with all the upper bits set to the same value

(seems less likely to happen by accident)

All TLS keys found were neighboring primes

What does "close" prime mean?

With a 2048 bit RSA key the primes are 1024 bit. With 100 rounds of Fermat factorization we can break primes with a difference up to 517 bit.

If roughly the upper half of the bits of the two primes are identical we can break it

Some RSA implementations create keys that can be broken with Fermat's factorization algorithm

However this is not a widespread flaw

It is worth looking for well-known flaws in large sets of cryptographic keys