Как я факторизовал RSA‑ключи центра сертификации… из 90-х

В последнее время меня всерьез стала беспокоить безопасность RSA. Криптография RSA держится на сложности факторизации большого полупростого числа, но какое именно число можно считать достаточно «большим» — вопрос интересный. Web PKI отказалась от 1024-битного RSA больше десяти лет назад, и хотя я не знаю никого, кто факторизовал бы ключ такого размера, это вполне по силам какому‑нибудь правительству или другой организации с большим количеством машин. Буквально пару дней назад кто‑то факторизовал 862-битный ключ RSA-260 в рамках конкурса RSA Factoring Challenge. Это самая крупная факторизация, о которой я слышал. Сегодня во всем мире используют RSA с длиной ключа минимум 2048 бит, но и это скоро устареет из‑за риска, который представляют квантовые компьютеры в будущем.

И вот я подумал: небольшие ключи RSA можно факторизовать даже на скромном персональном компьютере. А в ранние годы Web PKI не было ни стандартов, ни минимальных требований. Netscape реализовала поддержку SSL в 1994 году, IE — вскоре после. Это все еще была эпоха экспортных ограничений на криптографию. Найдутся ли ключи, достаточно маленькие, чтобы я мог их факторизовать? Если что я не руководствуюсь ничем, кроме простого интереса.

Спойлер: конечно, да, но сначала нужно найти ключ, который мы будем взламывать.

К счастью, корневые сертификаты поставлялись вместе с установщиками браузеров, и на archive.org есть архивы и Internet Explorer, и Netscape. Архивы неполные, но должны дать неплохое покрытие старых корневых сертификатов. Я скачал обе коллекции и поручил Claude Code извлечь все корневые сертификаты. Я выложил сгенерированную Claude веб‑страницу со всеми этими старинными корневыми сертификатами здесь. Я не проводил тщательной проверки вывода LLM, но выглядит вполне правдоподобно.

С помощью фильтров на этом сайте мы можем найти маленькие ключи, которые использовались для SSL.

Ага! Цель найдена. В марте 1999 года Netscape 4.51 поставлялся с 512-битным RSA доверенным для SSL, и еще одним — для S/MIME. Оба корневых сертификата принадлежали давно почившему канадскому удостоверяющему центру E‑Certify.

Позже в том же году был факторизован 512-битный RSA-155, так что даже для своей эпохи он был слишком слабым и, вероятно, не должен был поставляться вообще.

512-битные корневые сертификаты от E‑Certify были удалены Netscape в 2002 году. К сожалению, Internet Explorer, судя по всему, никогда не поставлял 512-битные корневые сертификаты для SSL, так что веселье ограничится Netscape и относительно небольшим периодом времени.

Факторизация публичных ключей из корневых сертификатов даст мне два простых числа, необходимых для восстановления приватного ключа. Я запустил CADO‑NFS на своем персональном компьютере с Ryzen 9 5950X: факторизация E‑Certify RSA 512 Gold Server для SSL заняла 32 часа, а E‑Certify RSA 512 Gold Client — еще 29 часов. Полученные приватные ключи приведены ниже.

После того как вы установите CADO‑NFS по инструкции, запустить его несложно. Нужно извлечь из сертификата модуль, который будем факторизовать. Это делается с помощью пары строк на Python:

from cryptography import x509
f = open("gold-server.pem", "rb").read()
pubkey = x509.load_pem_x509_certificate(f).public_key()
print(pubkey.public_numbers().n)

Полученное значение N передается в CADO‑NFS, примерно так:

./cado-nfs.py $N -t 32 --workdir /data/cert1

Если вы каким‑то чудом используете Netscape 4.51 с часами, выставленными до истечения срока действия корневых сертификатов E‑Certify (16 октября 2003 года), вы можете использовать эти приватные ключи для выпуска сертификатов. Под эту категорию подпадает ноль людей на планете… кроме виртуалки, которую я сам настроил.

Проверка того, что выпущенные сертификаты заработают в Netscape 4.51, сама по себе оказалась приключением: TLS‑функционал у Netscape 4.51 и любого современного TLS‑стека не пересекаются вообще. Так что пришлось снова звать на помощь Claude Code, чтобы тот написал нам ретро TLS‑сервер на Go. Сайт публично доступен по адресу e‑certify.fly.dev — можете посетить его с помощью своей копии Netscape. В любом другом современном браузере он просто не загрузится.

А если хотите попробовать поднять собственный сайт на этих старых ключах — все ключи и инструменты лежат в репозитории https://github.com/mcpherrinm/ancientroots. Или сделайте что‑нибудь похуже: например, MitM для SSL всех тех пользователей Netscape 4.51, у которых часы выставлены на 25 лет назад…

C=CA, O=E-Certify, OU=RSA Gold Server, CN=E-Certify RSA 512 Gold Server
-----BEGIN CERTIFICATE-----
MIIByjCCAXSgAwIBAgIBATANBgkqhkiG9w0BAQQFADBjMQswCQYDVQQGEwJDQTES
MBAGA1UEChMJRS1DZXJ0aWZ5MRgwFgYDVQQLEw9SU0EgR29sZCBTZXJ2ZXIxJjAk
BgNVBAMTHUUtQ2VydGlmeSBSU0EgNTEyIEdvbGQgU2VydmVyMB4XDTk4MTAxNjEz
Mzc1M1oXDTAzMTAxNjEzMzc1M1owYzELMAkGA1UEBhMCQ0ExEjAQBgNVBAoTCUUt
Q2VydGlmeTEYMBYGA1UECxMPUlNBIEdvbGQgU2VydmVyMSYwJAYDVQQDEx1FLUNl
cnRpZnkgUlNBIDUxMiBHb2xkIFNlcnZlcjBcMA0GCSqGSIb3DQEBAQUAA0sAMEgC
QQDNVQ93Ev7zgNaJAR1Z7gCydU6mky1e/B4EbY1NsdtfsitU9cELqg5uRJDPA40n
CDPeOyil1lJ5N8hekcqJAkkXAgMBAAGjEzARMA8GA1UdEwEB/wQFMAMBAf8wDQYJ
KoZIhvcNAQEEBQADQQB09SV6OeeDEP8Je3DOLNZ24U98NHqIBTDyB4sRpDmNdHum
+3rm4AYtznBxG5hEShO89bcWi3yJtBITGuTRDnMq
-----END CERTIFICATE-----
-----BEGIN RSA PRIVATE KEY-----
MIIBOgIBAAJBAM1VD3cS/vOA1okBHVnuALJ1TqaTLV78HgRtjU2x21+yK1T1wQuq
Dm5EkM8DjScIM947KKXWUnk3yF6RyokCSRcCAwEAAQJAWZ2FOWf+A9K4T2VAJS69
+SU/pW3YwHrysuYJZN56K0Iz+Hqd1hBhCeJ3/T+/cvXq+ctD0x3uOxU1rDSeCoMO
KQIhAPdbc1wTm3twWDYi1iXmRBXz97MYxRFld/KFr8x5+tK9AiEA1IG09a+oVg6j
NMDj6GD7spaD4q9t1wk/Nyq/MTLPkmMCIEzzYjvuzZvlI0wUIlLAA8Zgk1pgBk6X
Jm2IMVyHRgRxAiEAjZKgCTHuVu7HgiSjcTPzW0X1NTckWSc66zjaSR+Ns/sCICxT
yXoTXWQCWL6BMpf2no7IlvoEnBIrED2Frq3PxlEA
-----END RSA PRIVATE KEY-----

C=CA, O=E-Certify, OU=RSA Gold Client, CN=E-Certify RSA 512 Gold Client
-----BEGIN CERTIFICATE-----
MIIByjCCAXSgAwIBAgIBAjANBgkqhkiG9w0BAQQFADBjMQswCQYDVQQGEwJDQTES
MBAGA1UEChMJRS1DZXJ0aWZ5MRgwFgYDVQQLEw9SU0EgR29sZCBDbGllbnQxJjAk
BgNVBAMTHUUtQ2VydGlmeSBSU0EgNTEyIEdvbGQgQ2xpZW50MB4XDTk4MTAxNjEz
MzQwOFoXDTAzMTAxNjEzMzQwOFowYzELMAkGA1UEBhMCQ0ExEjAQBgNVBAoTCUUt
Q2VydGlmeTEYMBYGA1UECxMPUlNBIEdvbGQgQ2xpZW50MSYwJAYDVQQDEx1FLUNl
cnRpZnkgUlNBIDUxMiBHb2xkIENsaWVudDBcMA0GCSqGSIb3DQEBAQUAA0sAMEgC
QQBwCcT1iYlNyKPywB/kffD8esiCzGYJxSnTXQjU6ej/XxnA+9yqjzAMPtqFd094
wM89Vsmz9YOWSO6Qn6wOAs45AgMBAAGjEzARMA8GA1UdEwEB/wQFMAMBAf8wDQYJ
KoZIhvcNAQEEBQADQQAdktdM5AzW+0o96eHCHwD3UfzxPvjKxPEjiI/QTn+njHt/
BEJb9yZatONRckglVc9v8P8Dy8HZGQD0+Pn0uxhW
-----END CERTIFICATE-----
-----BEGIN RSA PRIVATE KEY-----
MIIBOQIBAAJAcAnE9YmJTcij8sAf5H3w/HrIgsxmCcUp010I1Ono/18ZwPvcqo8w
DD7ahXdPeMDPPVbJs/WDlkjukJ+sDgLOOQIDAQABAkASXZeaxFPsm0I8zb+snfR9
/saVolnrqhVEH5EODdXy3nSm6fpdrsDwQDDg52biXjIUizQYdd3OourOn0/PyyiB
AiEAyW4gFFgM0dJ+Y//vrIyQutLeH/5c/Vq3Lbcxv7R908kCIQCOZAAv8OCG/2oH
yKaYj/EoxcFZ9csVh/kjicO/JIX+8QIhAMEzAkvhBDLALYAmvDCJBkxa8rhHFdPf
jbCodGwGZ2WZAiB//XmBnlZkYl/PoVfGmNRgHun+0AZ9UxzqCeJvBQiBMQIgHWlr
0Sh1a8K2pQP2ktgmL3RH5+1Qd2wLx/hhGWtwPvU=
-----END RSA PRIVATE KEY-----

В качестве бонуса Internet Explorer 3.02 поставлялся с удостоверяющим центром для подписи кода под названием OU=Test VeriSign Commercial Software Publisher CA. Точно не знаю, для чего он предназначен, но факторизуется так же легко. В репозитории ancient roots есть еще несколько похожих на тестовые 512-битных RSA‑ключей — попробуйте факторизовать что‑нибудь еще или придумать, как их можно применить!

Стив Вайс (Steve Weis) факторизовал этот ключ примерно за час на GPU‑кластере.

И напоследок: вот что SSL Labs думает о моем тестовом сайте: