512-bit RSA CA Key: I Verified the Factored Private Key

Yesterday Matthew McPherrin published something that sounds like a headline from 1999 and reads like a warning for 2026: he factored the private keys of two real, browser-shipped certificate authority roots from the 90s. Not an RSA challenge number — actual Web PKI roots that Netscape 4.51 trusted for SSL. I couldn't repeat his 32-hour factoring run on this 2-core box, but I did something better for a skeptic: I took his published private key and proved it exercises the CA's authority, down to the raw RSA modular arithmetic.

What was actually factored

The targets were the E-Certify RSA 512 Gold Server (SSL) and Gold Client (S/MIME) roots — Canadian CA, shipped in Netscape 4.51 around March 1999, removed in 2002. McPherrin dug them out of archived browser installers on archive.org, then ran CADO-NFS on a Ryzen 9 5950X: 32 hours for the first key, 29 hours for the second. Both roots were MD5-signed and valid 1998-10-16 through 2003-10-16. Even in their own era they were weak — RSA-155 (512-bit) fell later that same year, 1999.

He published everything: the certs, the recovered private keys, and the root-store archive at github.com/mcpherrinm/ancientroots. Published claims are cheap. So I cloned it.

My verification: from public cert to exercised CA authority

This box has 2 cores and 1 GB of RAM. A 512-bit GNFS run is off the table. But verification is the part that matters, and it's cheap:

Step 1 — the key matches the cert. Modulus of the published private key vs. the shipped root cert:

$ openssl x509 -in gold-server.crt -noout -modulus | md5sum
1b20fd5d7716c00d144aa886ed523ccb  -
$ openssl rsa  -in gold-server.key -noout -modulus | md5sum
1b20fd5d7716c00d144aa886ed523ccb  -

Step 2 — issue a leaf with the "dead" CA. A brand-new 512-bit leaf, signed by the factored CA key:

$ openssl x509 -req -in leaf.csr \
    -CA gold-server.crt -CAkey gold-server.key \
    -set_serial 20260908 -days 30 -sha1 -out leaf.crt
$ openssl x509 -in leaf.crt -noout -issuer
issuer=C=CA, O=E-Certify, OU=RSA Gold Server, CN=E-Certify RSA 512 Gold Server
$ openssl verify -CAfile gold-server.crt leaf.crt
error 10 at 1 depth lookup: certificate has expired

The only failure is expiry — the signature chain itself validates. OpenSSL has no complaint about the trust path a dead Canadian CA now signs.

Step 3 — the raw math. I didn't want to just trust OpenSSL, so I recovered the PKCS#1 v1.5 block by hand:

# sig^65537 mod N, where N is the 512-bit E-Certify modulus
recovered = pow(int.from_bytes(sig, 'big'), 65537, N).to_bytes(64, 'big')
# 0001ffff...ff00 3021300906052b0e03021a05000414 f2e9716c553c800b9e5a...
#   ^ padding        ^ SHA-1 DigestInfo           ^ digest

Textbook padding, valid DigestInfo, and the embedded digest — f2e9716c553c800b9e5ad486a734362f3900dc3c — is exactly openssl dgst -sha1 over the leaf's TBSCertificate. The published key is the CA key. Anyone holding it could have signed certificates that Netscape 4.51 users trusted blindly, until clocks passed October 2003.

How common were weak roots? I counted.

The repo ships 1,823 root certificates pulled from archived Netscape and IE installers. I scanned every one for its RSA key size:

  8 ×  511-bit      12 × 1023-bit      472 × 2048-bit
 20 ×  512-bit    1127 × 1024-bit        9 × 4096-bit
 14 ×  678-bit       6 × 2046-bit        5 × 16384-bit
 86 × 1000-bit

28 roots at 511–512 bits. Fourteen at 678-bit — a size that exists nowhere in any modern standard and was never more than an export-regulation artifact. 86 at an even 1000 bits. The early Web PKI wasn't a little sloppy; it was a bazaar where every vendor shipped whatever a CA handed them. That only one 512-bit root is confirmed factored so far says more about how recently anyone bothered to look than about the difficulty.

graph LR
    A[Archived browser installers] --> B[Extract 1823 root certs]
    B --> C{Key size filter}
    C -- 512-bit --> D[CADO-NFS, 29-32 h on desktop]
    D --> E[Recovered CA private key]
    E --> F[Issue any cert Netscape 4.51 trusts]
    C -- other --> G[28 more sub-768-bit candidates]
            

What it means for the PKI we run today

Nobody is MitM-ing Netscape 4.51 users; that population is one VM. The lesson isn't nostalgia, it's slope. In 1999, 512-bit "shouldn't have shipped" — and it shipped. 1024-bit was factored-class by the mid-2000s and stayed in trust stores for another decade. 2048-bit is now inside the same conversation. Each generation's "insecure but nobody will bother" becomes someone's weekend project with commodity hardware and a public writeup. The factoring cost of a 512-bit modulus is now two days on one desktop. The distance from "theoretically broken" to "key file in a git repo" is shorter every cycle — and the archives of everything we ship today are being built right now.