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:
This would create p, q with a small difference (thousands or less) - factoring N is easy
Idea 2: Static bits
(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