Am 2. Dezember 2019 berichtete die Mailingliste für Zahlentheorien
nmbrthry@listserv.nodak.edu über die
Faktorisierung der RSA-240-Zahl (240 Dezimalstellen, 795 Bit). Dies ist eine neue Leistung in Kryptographie und Zahlentheorie und die nächste abgeschlossene Aufgabe aus der
RSA Factoring Challenge- Liste.
Hier ist die Anzahl und ihre Faktoren:
RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447
Basierend auf dem aktuellen Trend können Sie sich ungefähr vorstellen, wann RSA-1024 (309 Dezimalstellen) und RSA-2048 (617 Stellen) gehackt werden.
Bisherige Erfolge waren die
Faktorisierung einer 768-Bit-Zahl (232 Dezimalstellen) im Jahr 2009 und der
diskrete Logarithmus einer 768-Bit-Zahl im Jahr 2016 .
Viele Verschlüsselungsalgorithmen mit öffentlichem Schlüssel basieren auf extrem großen Zahlen, die aus zwei Primzahlen bestehen. Andere stützen sich auf die Schwierigkeit, einige diskrete logarithmische Probleme zu lösen. Bei ausreichend großen Schlüsseln ist keine Möglichkeit bekannt, eine solche Verschlüsselung zu knacken. Die Faktorisierung großer Zahlen und die Berechnung des diskreten Logarithmus zerstören die kryptografischen Garantien für eine gegebene Schlüsselgröße und zwingen die Benutzer, die Anzahl der Entropiebits beim Erzeugen eines Geheimnisses zu erhöhen.
Immer ausgefeiltere Chiffren knacken nach und nach, wenn die CPU-Leistung steigt und die Algorithmen verbessert werden.
Nach der Erfindung des GNFS-Algorithmus (General Number Field Sieve) in den frühen 90er-Jahren erschien auf dem Gebiet der Ganzzahlfaktorisierung nichts Revolutionäres, obwohl einige signifikante Optimierungen vorgenommen wurden. Beispielsweise konnten Forscher in den letzten Jahren die Phase der Suche nach einem geeigneten Polynom erheblich beschleunigen.
Die Faktorisierung von RSA-240 fällt ebenfalls aus dem Rahmen, da sie nicht nur durch die Erhöhung der Rechenleistung, sondern auch durch die Optimierung von Software und Algorithmen durchgeführt wurde. Um die Wirksamkeit der vorgenommenen Änderungen zu belegen, starteten die Forscher das Programm mit demselben Gerät, mit dem 2016 der diskrete 768-Bit-Logarithmus berechnet wurde. Sie fanden heraus, dass das Sieben einer 795-Bit-Zahlenmatrix 25% schneller ist als das Sieben einer 768-Bit-Zahlenmatrix ohne Optimierung.
Dieselbe Forschergruppe berechnete einen diskreten Logarithmus gleicher Größe. Zum ersten Mal in der Geschichte werden Datensätze für diskretes Logarming und Faktorisierung von Zahlen gleicher Größe zur selben Zeit und sogar auf derselben Hardware und Software eingestellt.
Dank der Optimierung von Algorithmen und Software konnte der diskrete Logarithmus einer 795-Bit-Zahl im Vergleich zum Logarithmus einer 768-Bit-Zahl ohne Optimierung auf derselben Hardware um 33% beschleunigt werden.
Theoretisch ist der Logarithmus einer 795-Bit-Zahl 2,25-mal komplizierter als eine 768-Bit-Zahl. Dies bedeutet, dass der Optimierungseffekt tatsächlich dreimal ist (2,25 × 1,33 = 3).
Beide Arten von Berechnungen wurden unter Verwendung des
Siebnummernfeldalgorithmus im Open-Source-
CADO-NFS- Programm durchgeführt. Zu den Optimierungen gehören eine verbesserte Parallelisierung und Speichernutzung sowie eine Menge Arbeit, um optimalere Berechnungsparameter zu finden (spezielle Software wurde zum Testen und Einordnen verschiedener Berechnungsparameter entwickelt).
Die Summe der Rechenzeit für beide neuen Datensätze beträgt ungefähr 4000 Jahre Betriebszeit der physischen Kerne von Intel Xeon Gold 6130-Prozessoren (mit einer Frequenz von 2,1 GHz), wenn dieser Prozessor als Referenz verwendet wird.
Eine grobe Aufteilung der Zeit in Faktorisierung und Logarithmus:
- Screening RSA-240: 800 Kernjahre
- RSA-240-Matrix: 100 Kernjahre
- Screening DLP-240: 2400 Kernjahre
- Matrix DLP-240: 700 Kernjahre
Der Erfolg wurde von einem Forscherteam unter der Leitung von Emmanuel Thomé, einem führenden Forscher am
französischen Nationalen Institut für Informatik und Angewandte Mathematik, gewürdigt .
Die Erfinder der RSA-Verschlüsselung haben RSA-
Nummern aller Größen bis RSA-2048 veröffentlicht. Jeder kann versuchen, sie zu hacken.
Basierend auf dem aktuellen Trend können Sie berechnen, wann RSA-1024 (309 Zeichen) und RSA-2048 (617 Zeichen) gehackt werden. Wenn Sie den Zeitplan extrapolieren, erhalten Sie ungefähr 2031 bzw. 2073. Wir sehen jedoch, dass die Optimierung von Software und Algorithmen diesen Begriff erheblich näher bringen kann. Vielleicht wird RSA-2048 zu unseren Lebzeiten gehackt.
In der Praxis empfiehlt der RSA die Verwendung der minimalen RSA-Schlüsselgröße von 2048 oder 4096 Bit.
Der Entwicklung von Quantencomputern nach zu urteilen, werden sie nicht so schnell an das Brechen von Schlüsseln dieser Größe herankommen, obwohl es schwierig ist, hier etwas vorherzusagen. 2012 hat
der Shore-Algorithmus die
Faktorisierung von 21 (3 × 7), fünf Entropiebits, bewältigt. Diese Zahl ist seit langem ein Rekord für die Quantenfaktorisierung, aber im Jahr 2018 wurde die Faktorisierung des Produkts der Primzahlen
4088459 auf IBM 5- und 16-Qubit-Prozessoren demonstriert, was bereits 22 Bit entspricht.
