Factoring the RSA keys of a Certificate Authority...from the 90s

[dyers eve]

An fun interesting article about factoring the RSA keys of an old CA.

https://mcpherrin.ca/2026/09/07/rsa.html

"I’ve been thinking about the security of RSA lately. RSA’s cryptography relies on the difficulty of factoring a large semiprime number, but what “large” means is an interesting question. The Web PKI deprecated 1024-bit RSA over a decade ago, and while I don’t know of anyone factoring a key of that size, it’s within the realm of possibility for a government or other organization with a large number of computers. Just a few days ago, someone factored the 862-bit RSA-260 key from the RSA factoring challenge. That’s the largest factorization I’m aware of. Today, the world uses RSA of at least 2048 bits, but even that will be deprecated soon with the risk of quantum computers in the future.

This led me to wonder: small RSA keys can be factored on even a modest desktop computer. And in the early days of the Web PKI, there were no standards, and no minimum requirements. Netscape shipped SSL support in 1994, and IE shortly afterwards. This was still the era of export restrictions on cryptography. Are there any keys small enough that I can factor? I don’t have any good reason to do that, but it seems like fun.

The spoiler is of course, yes, but first we need to find a key to crack.

Fortunately, root certificates were shipped with browser installers, and there are archives of both Internet Explorer and Netscape on archive.org. The archives aren’t comprehensive, but they should provide good coverage of old root CAs. I downloaded both collections and set Claude Code on extracting all the roots. I’ve hosted a Claude-generated webpage with all those old-timey, ancient roots. While I haven’t verified this LLM output is entirely trustworthy, it looks pretty plausible."

[chants]

Since you dont realize it, factoring RSA512 with a general number field sieve GNFS or even a quadratic sieve is not particularly challenging and a good library implementing those or even an LLM can do this very trivially. So its cool but not impressive. Factoring a modulus more than 862 bits is another story.

[WhoCares]

The following one is also interesting, though a little bit old.


The website is https://factorable.net. It showcases one of the more famous large-scale RSA key-cracking studies in cryptography, based on something called Batch GCD.

The discovery was made in 2012, when two independent research teams published their findings almost simultaneously:

The paper “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices”

This was published by researchers from the University of Michigan and the University of California, including Nadia Heninger and J. Alex Halderman. They scanned the entire IPv4 address space, collected tens of millions of TLS/SSL certificates and SSH keys, and set up Factorable.net to publish their findings.

The title “Ps and Qs” is a nice double entendre. In English, “mind your Ps and Qs” is an expression meaning to be careful about your behavior or what you say. Here, it also refers to the two prime factors, p and q, that make up an RSA key.

The paper “Ron was wrong, Whit is right”

This was published around the same time by a group led by renowned cryptographer Arjen Lenstra. “Ron” refers to Ron Rivest, one of the inventors of RSA, while “Whit” refers to Whitfield Diffie, one of the inventors of the Diffie-Hellman key exchange.

The paper pointed out that, because of flaws in how keys were generated on real-world devices, RSA could actually be more vulnerable to catastrophic attacks than DH key exchange in some environments.

The vulnerability and how the attack works

RSA relies on the fact that factoring a sufficiently large integer is computationally hard. An RSA public key contains a huge integer N, which is the product of two secret prime numbers: N = p × q. Normally, knowing only N isn't enough to recover p and q with practical amounts of computing power.

The problem was that a lot of real-world embedded devices — routers, firewalls, IoT devices, and so on — generated their cryptographic keys automatically the first time they were powered on.

Right after boot, however, the device's pseudorandom number generator (PRNG) often didn't have enough “entropy.” In other words, it simply didn't have enough unpredictable input to produce genuinely independent random numbers.

And that's where things went badly wrong.

Two devices on opposite sides of the world could end up with very similar random states and, by sheer chance, generate exactly the same prime p, while generating different primes q1 and q2.

Suppose an attacker collected the public keys from both devices:

N1 = p × q1
N2 = p × q2

At this point, there is no need to factor either of those huge numbers directly.

Just compute their greatest common divisor:

GCD(N1, N2) = p

GCD is extremely fast to compute, and the researchers used an algorithm called Batch GCD to do this efficiently across a huge collection of keys.

If the result isn't 1, you've found a shared prime factor p. From there, getting q1 and q2 is just a matter of division, and the attacker can immediately reconstruct the private keys.

That's the really nasty part of the attack: the computational cost is tiny compared with actually factoring an RSA modulus.

Using this technique, the researchers were able to recover the private keys of tens of thousands of real-world devices on the Internet.

[dyers eve]

Originally Posted by WhoCares

The following one is also interesting, though a little bit old.


The website is https://factorable.net. It showcases one of the more famous large-scale RSA key-cracking studies in cryptography, based on something called Batch GCD.

Excellent example!

It is both historically grounded and technically incisive, and it captures a subtle but crucial point: the catastrophe was not in RSA’s algebra, but in the entropy architecture surrounding its deployment.
Batch GCD was therefore less a “break” in the classical sense than a large-scale correlation detector, exposing how many supposedly independent moduli were actually generated from insufficiently differentiated randomness.

That distinction matters. RSA’s security reduces to the intractability of factoring N=pq, but if two devices emit moduli sharing a prime, then the problem collapses immediately under gcd?(N1,N2).

Similarly, weak ECDSA nonce generation can leak a signing key from a single reused scalar, and flawed DRBG seeding can render entire keyspaces statistically redundant.

The deeper pattern is that cryptographic primitives are rarely defeated by abstract number theory. They are defeated by implementation drift, boot-time entropy depletion, or concurrency bugs that silently violate independence assumptions.

So the study is historically famous not merely because it found weak RSA keys, but because it demonstrated a more general epistemic lesson: at internet scale, security failures are often emergent properties of systems engineering, not isolated cryptanalytic exploits.