Die Zahl für heute: 4500

Ich habe in der ct einen Beitrag über Kryptographie und deren Sicherheit gelesen. Dabei ging es auch um die Möglichkeit der Entschlüsselung. Das RSA-Verfahren basiert auf Primzahlen. Es werden bei der Verschlüsselung zwei Primzahlen miteinander multipliziert. Das Entschlüsseln ist deswegen so schwer, weil man aus dem Produkt nur durch Ausprobieren herausfinden kann, welche Primzahlen verwendet wurden. Dazu kommt der einfache Umstand, dass dabei etliche Primzahlen, die recht groß sind – und bei heutigen Rechnern nur mit speziellen Bibliotheken berechnet werden können, da sie viel größer als die normalen Zahlen mit 64 Bit Breite sind. Das reduziert auch die Geschwindigkeit.

Im Artikel kam ein Kasten aus der Originalpublikation von 1970, wo eine Tabelle mit den zu erwartenden Entschlüsselungszeiten abhängig von der Codelänge und der dazu benötigten Operationen mittels „Brute Force“, also einfaches Durchprobieren drinstand. Bei RSA-100 Code mit 100 Dezimalstellen (330 binäre Stellen) langen Primzahlen benötigt nach der Tabelle 74 Tage zum Entschlüsseln, was angesichts der 2,3 x 1015 Operationen auf 1 Million Operationen pro Sekunde schließen lässt. Später im Beitrag wurde gesagt, dass ein heutiger PC (Ryzen 2400G) dafür 6 Tage braucht, wenn er nicht Brute Froce nutz,t sondern eine spezielle Technik sogar „nur“ 3 Stunden.

Immerhin: 6 Tage zu 74 Jahre, das ist eine Geschwindigkeitssteigerung um den Faktor 4500. Klingt erst mal toll, relativiert sich aber, wenn man weiß, dass seitdem 50 Jahre vergangen sind.

Gordon Moore hat das nach ihm benannte „Moore‘sche Gesetz“ in den Sechzigern erstmals publiziert, dann aber noch mal korrigiert, weil die ursprüngliche Frist der Verdopplung zu kurz gewählt, war, anfangs 12 Monate, dann korrigiert auf 18. Das war noch optimistisch in der Intel Serie und den Speicherchips war der Verdopplungszeitraum über Jahrzehnte 24 bis 26 Monate. Nach dem Mooreschen Gesetz verdoppelt sich alle 12, 18 oder 24 Monate, je nach Gusto, die Zahl der Elemente auf einem Halbleiter. Daran gekoppelt ist dann auch ein Anwachsen der Leistung des Computers, typisch der Geschwindigkeit und des verfügbaren Speichers. Das ging auch lange Zeit in demselben Maße hoch. Es ist, da der Ausdruck ja inzwischen durch Corona allgemein bekannt ist ein Exponentielles Wachstum.

Der Faktor 4500 entspricht, wenn man ihn auf Zweierpotenzen umrechnet, etwas mehr als 12 Verdopplungszyklen (212 = 4096, 213 = 8192). Das liegt weit unter dem Moorschen Gesetz, und dies selbst bei 24 Monaten für eine Verdopplung 25 Verdopplungszyklen oder den Faktor 32 Millionen nahe legt. Also schaue ich mal genauer nach. Anders als die Geschwindigkeit eines Computers ist die Zahl der Transistoren genau angebbar. Wie viele es sind, hängt von der Größe eines „Die“, also der Chipgröße ab. Sie ist variabel und die Größe eines Die kann bei Serverprozessoren viel größer sein als bei Prozessoren für ein Smartphone. Wichtigster Wert für das Moorsche Gesetz ist aber die minimale Strukturbreite, die man bei der Fertigung umsetzen kann. Etwas nach der Vorhersage der Entschlüsselungszeiten für RSA kam Intels erster Prozessor heraus. Der Intel 4004 entstand in 10 Mikrometer Technologie und hatte 2.250 Transistoren. Die Taktfrequenz betrug MHz. Der aktuelle Ryzen 5950X wird in 7 Nanometer Technologie gefertigt

Intel 4004 Ryzen 5950X Steigerung
Transistoren 2.250 19.200.000.000 8.533.333
Taktfrequenz 0,74 3.400 / 4.900 4594 / 6621
Technologie 10.000 Nanometer 7 Nanometer 1.428
Kerne 1 16 16

Der Vergleich ist wegen der technologischen Veränderungen natürlich schwierig. Heute haben Prozessoren mehrere Kerne und können für einzelne per Turboboost die Taktfrequenz erhöhen. So was beherrschte der Intel 4004 natürlich nicht. Am größten ist die Steigerung bei der Transistorenzahl, die in knapp 50 Jahren (Erscheinungsdatum des Intel 4004 war der 15.11.1971) um den Faktor 8,5 Millionen hochging, immerhin eine Verdopplung alle 25,5 Monate. Passt noch gut zum Moorschen Gesetz, das aber in den letzten Jahren deutlich abflachte.

Warum ist ein heutiger PC aber dann nur 4500-mal schneller? Gut man muss berücksichtigen, das der Test-PC etwas älter war, ein Ryzen 2400G mit nur vier Kernen, 14 nm Technologie und maximal 3,6/3,9 GHz. Aber es sollte trotzdem schneller als nur Faktor 4500 gehen.

Dieser Faktor passt auf den ersten Blick zur Steigerung der Taktfrequenz. Doch die sagt heute eigentlich nicht mehr viel über die Geschwindigkeit aus. Die Taktfrequenz stieg bis etwa 2003 rasant, bis Intel beim Pentium 4 eine Spitzentaktfrequenz von 3,82 GHZ erreichte, dann aber die Abwärme nicht mehr in den Griff bekam. Die Architektur auf der die heutigen icore Serie basiert, setzte als Folge auf eine geringere Taktfrequenz mit weniger Abwärme. Seitdem sind die Taktfrequenzen kaum gestiegen. Spitze sind heute um die 5 GHz, was in 17 Jahren nur eine geringe Zunahme ist – in den vorherigen 17 Jahren stieg sie von 16 auf 3830 MHz. Die 3830 MHz Normalfrequenz, also ohne Turboboost übertreffen selbst heute nur die wenigsten Prozessoren. Daneben sollte die Kernanzahl eine Rolle spielen. Der Brute Force Algorithmus ist ja nichts anderes als Ausprobieren und da kann jeder Kern separat Zahlen ausprobieren, man muss nur den Zahlenbereich in n Teile unterteilen. Aussagekräftiger als Maß der Leistungssteigerung ist dagegen die Verringerung der Strukturbreite. Halbiert man die Strukturbreite, so sollten viermal so viele Elemente auf ein Die passen. Beim Faktor 1428 also 1428² mehr. Mit der Steigerung der Elementezahl um den Faktor 8,5 Millionen ist hier sogar die Steigerung überproportional groß (erwartet: 2,04 Millionen). Das liegt an der größeren Die-Größe die sich auch im Preis niederschlägt, der obige Ryzen-Prozessor kostete bei Einführung im Handel 799 Dollar. Der Intel 4004 kostete 60 Dolalr als Einzelexemplar, in größeren Stückzahlen 20 bis 30 Dollar. Der Ryzen 5950 ist übrigens durch coronabedingte Verknappung mit derzeit 1317 Euro extrem teuer.

Ich vermute die geringe Steigerung der Dekodierungsleistung liegt an dem Algorithmus. Er basiert auf dem Rechnen mit wirklich großen Zahlen. Bei RSA-100 mit 330 binären Ziffern. Da nützen die Rechenwerke der heutigen Prozessoren, die zwar festverdrahtet und schnell rechnen, nichts, da muss man jede Stelle einzeln per Software berechnen, in etwa so, wie dies auch der Mensch tut. Dann geht die Zahl der Operationen aber in die Knie. Denn anstatt (wie bei 64 Bit Zahlen) so 20 Stellen in einem Rutsch zu berechnen, ist es nur eine. Man rutscht auf das Niveau zurück, das früher als Prozessoren ohne eingebaute Fließkommarecheneinheiten hatten. Ein Intel 8080 konnte 160.000 8 Bit Ganzzahloperation pro Sekunde ausführen, bei der Berechnung von 32 Bit Fließkommawerten sank er auf 700 Operationen pro Sekunde.

Die zweiet Einschränkung ist der Computer, der für die Abschätzung, wahrscheinlich nach einem Lauf mit einem kleinen RSA-Schlüssel eingesetzt wurde. Denn die ct‘ hat mit einem PC verglichen. Einen PC gab es 1970 noch nicht. Damals gab es Minicomputer und Großcomputer. Ich vermute das für die Abschätzung ein Großcomputer genutzt wurde. Denn 1 Million Operationen pro Sekunde war damals viel. Der damals schnellste Rechner weltweit, eine Cyber 6600 errichte maximal 10 Millionen Operationen pro Sekunde, typisch eher 3 bis 5. So gesehen müsste man heute auch nicht mit einem PC mit einem Prozessor vergleichen, sondern den heute schnellsten Rechnern und die haben Zehntausende bis Hunderttausende dieser Prozessoren und nutzen noch GPUs zusätzlich. Entsprechend schneller sind sie. Auch offen ist warauf sich die Operationenzahl bezieht – MIPS eines Computers – dann benötigt aber jede Rechenoperation aufgrund der Ladebefehle mehrere Operationen oder ob sich dies gar auch Operationen pro Primzahl bezieht. Ich denke es sind Nettorechenoperationen gemeint, keine MIPS, denn der obige Ryzen 2400G erreicht nach der Tabelle so 4,4 Mrd. Operationen pro Sekunde, was bei vier Kernen und 3,5 GHz Normalfrequenz 3 Takte pro Operation sind.

Auf der anderen Seite wird man schon damals spezielle Hardware konstruieren können, die nur der Entschlüsselung dient und gerade diese eine Problemstellung sehr schnell lösen kann. Heute nutzen Bitcoin-Miner, die im Prinzip nichts anderes als diese Rechnungen tun, dafür spezialisierte ASIC-Bausteine oder eben Grafikkarten die viel mehr Kerne haben. Diese sind zwar nicht sehr ausgeklügelt, aber sie müssen ja eigentlich nur Zahlen in Primzahlfaktoren zerlegen.

Kleiner Trost am Rande: Für RSA-200, also einen doppelt so langen Schlüssel (550 binäre Stellen) braucht man nicht doppelt so lange, sondern nach der Tabelle rund 50 Millionen mal länger. (1,2 x 1023 Operationen) Das dürfte selbst heute noch ausreichend sicher sein, selbst wenn man optimierte Verfahren zur Entschlüsselung nutzt und 100.000 Prozessoren mit GPU-Beschleunigern. Eine Verlängerung auf 300 Stellen erhöht die Entschlüsselungsdauer nochmals um den Faktor von etwa 1 Million.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.