How to Factor a 1990s Certificate Authority's 512-Bit Keys

The security of RSA rests on the difficulty of factoring a large semiprime, but the meaning of “large” shifts over time. The web's public-key infrastructure abandoned 1024-bit keys more than a decade ago; today at least 2048 bits is considered the standard, and on the horizon looms the threat of quantum computers. Matthew McPherrin set himself an easier question: were there still keys out there weak enough to be factored on an ordinary desktop PC? And, of course, the answer turned out to be yes.

In the early years of the web PKI there were neither standards nor minimum requirements: Netscape added SSL support in 1994, back in the era of export restrictions on cryptography. Root certificates were shipped directly inside browser installers at the time, and their archives (for Internet Explorer and Netscape) are still sitting on archive.org. The author downloaded both collections and, handing off the job of extracting the roots to Claude Code, put together a catalog of vintage certificate authorities.

The Victim — E-Certify

A target was found quickly. In March 1999, Netscape 4.51 shipped with two 512-bit root certificates from the now-defunct Canadian authority E-Certify — one for SSL, the other for S/MIME. Before the end of that same year, the 512-bit RSA-155 key was publicly factored, so this choice of key length was already weak by the standards of its own day. E-Certify's roots were removed from Netscape in 2002.

To recover the private keys, all you need is to factor the public key from the certificate into its two prime factors. McPherrin ran CADO-NFS on his desktop with a Ryzen 9 5950X: the server certificate factored in 32 hours, the client one in another 29. He published the resulting keys openly.

Who Is at Risk

The practical danger is close to zero. The keys can only be used by running Netscape 4.51 with the system clock set back to a date before the roots expired (October 16, 2003) — a description that fits no one on the planet except a virtual machine the author spun up specially. Verifying that the issued certificates actually worked turned into an adventure of its own: Netscape 4.51 and any modern TLS stack share not a single feature, so it was necessary (again with the help of Claude Code) to write an old-fashioned TLS server in Go. The demo site e-certify.fly.dev is publicly available, but it won't open in any modern browser.

As a bonus, the author mentions a 512-bit code-signing authority from Internet Explorer 3.02 — the “Test VeriSign Commercial Software Publisher CA,” which Steve Weis factored on a GPU cluster in about an hour. The project's repository also holds other test 512-bit keys from that era, which the author offers to anyone who wants to factor them themselves. The final touch: SSL Labs, according to the author, gives his archaic test site top marks.

Source: Hacker News