Cognition gab am 9. September bekannt, dass Forscher Eric Lu mit dem hauseigenen Coding-Agenten Devin die Faktorisierung von RSA-260 abgeschlossen hat – der aktuell größte öffentliche Rekord in der RSA-Faktorisierungs-Challenge. Der vorherige Rekord, RSA-250, stammt aus dem Februar 2020, also sechseinhalb Jahre zuvor.
RSA-260 ist eine 260-stellige Dezimalzahl, die in zwei 130-stellige Primzahlen zerlegt wurde. Der verwendete Algorithmus ist nicht neu: Das General Number Field Sieve (GNFS) ist seit den 1990er-Jahren der Standardweg zur Faktorisierung großer Zahlen. Die Änderung liegt auf der Implementierungsebene – der gesamte Ablauf wanderte von CPU-Clustern auf GPUs.
Wofür die 4900 GPU-Tage draufgingen
Cognition schlüsselt es so auf: Polynomauswahl 643 GPU-Tage, Gittersieben 3813 GPU-Tage, Lösen des linearen Gleichungssystems 467 GPU-Tage. Der Siebschritt verschlingt über drei Viertel der Rechenleistung – typisch für GNFS.
Das zentrale Werkzeug ist ein GPU-Gittersieb namens glas, neu geschrieben in CUDA, kombiniert mit einem angepassten CADO-NFS und einer GPU-optimierten Version des Block-Wiedemann-Algorithmus. Laut Cognition senkt diese Implementierung die Stückkosten des Siebens um rund eine Größenordnung.
CADO-NFS ist genau die Open-Source-Software, mit der das französische Team 2020 RSA-250 faktorisierte. Gleiche Codebasis, anderes Hardware-Backend – der Sechsjahresabstand zeigt sich in diesen beiden Zahlen.
Was Devin hier leistet, ist Ingenieursarbeit, keine mathematische Entdeckung: Codeoptimierung, Parameter-Tuning, Cluster-Verwaltung. Cognition beschreibt es in seinem Beitrag als einen „Softwareentwickler, der gut genug ist, um Probleme an der Schnittstelle von algorithmischer Zahlentheorie und GPU-Performance-Engineering zu lösen".
Auch der menschliche Anteil steht in den veröffentlichten Daten: 233 Sitzungen, 82.702 Wörter an Anweisungen. Im Schnitt über 300 Wörter pro Sitzung – etwa so viel wie die Kommentare eines Code-Reviews. Das ist kein unbeaufsichtigter Lauf, sondern ein Mensch mit einem Werkzeug, das durchgehend arbeiten kann, wodurch sich eine Aufgabe, die sonst ein Team über Monate koordiniert hätte, auf drei Wochen verdichtet.
Wie sieht die Hochrechnung aus
Cognition liefert gleich zwei Extrapolationen mit, beide ausdrücklich als grobe Schätzung zu aktuellen GPU-Preisen gekennzeichnet: RSA-1024 sei etwa 78-mal so schwer wie RSA-260, Kosten rund 30 Millionen US-Dollar; RSA-2048 sei 9,12 Billionen Mal so schwer, Kosten angegeben mit 3,77×10^16 US-Dollar.
Die erste Zahl verdient einen Moment Aufmerksamkeit. 30 Millionen US-Dollar sind eine Größenordnung, die sich staatliche Institutionen leisten können, ebenso große Unternehmen. RSA-1024 wird in Standards längst nicht mehr empfohlen, steckt aber noch in eingebetteten Geräten, alten Firmware-Signaturen und ein paar nicht mehr gepflegten Zertifikatsketten. Der rund milliardenfache Abstand zwischen beiden Zahlen ist der ganze Grund, warum 2048 Bit derzeit noch hält.
Zieht man die Rekordlinie länger: 1999 wurde RSA-155 mit einer öffentlichen Schätzung von rund 8000 MIPS-Jahren faktorisiert; Ende 2009 entsprach RSA-768 umgerechnet etwa 2000 Jahren auf einem Single-Core-2,2-GHz-Opteron; 2020 waren es bei RSA-250 2700 Kernjahre; diesmal sind es 13,5 GPU-Jahre. Die ersten drei Fortschritte kamen vor allem durch Moores Gesetz und algorithmisches Feintuning zustande, im Rhythmus von etwa einem Jahrzehnt. Beim diesjährigen Sprung fallen Hardware-Generationswechsel und die Frage, „wer diesen CUDA-Code schreibt", zusammen.
Was noch offen bleibt
Ob Paper und Code vollständig veröffentlicht werden und ob glas quelloffen wird, sagt die Ankündigung von Cognition nicht. Eine unabhängige Reproduktion durch Dritte steht noch aus – RSA-250 wurde damals von mehreren Teams gegenseitig anhand der Siebparameter verifiziert, für dieses Ergebnis liegen bislang nur die Daten einer Seite vor.
Das Faktorisierungsergebnis selbst lässt sich leicht prüfen – einfach die beiden Primzahlen multiplizieren. Schwer zu prüfen ist die Kostenrechnung: Welches GPU-Modell, welcher Stückpreis, ob gescheiterte Versuche in die 4900 GPU-Tage eingerechnet wurden – die Ankündigung schlüsselt das nicht einzeln auf. Was die 400.000-Dollar-Zahl für Sicherheitsbewertungen bedeutet, hängt genau von diesen Details ab.
Quellen: offizieller Tech-Blog von Cognition, RSA-250-Faktorisierungsankündigung auf caramba.loria.fr, CocoLoop; Angaben in GPU-Tagen und Kernjahren wurden unverändert aus den jeweiligen Ankündigungen übernommen, ohne einheitliche Umrechnung.