Die Zahl für heute: 4.500
Ich habe in der Computerzeitschrift ct einen Beitrag über Kryptographie und deren Sicherheit gelesen. Dabei ging es auch um die Möglichkeit der Entschlüsselung eines kodierten Textes. Das verbreitete RSA-Verfahren basiert auf Primzahlen. Es werden bei der Verschlüsselung zwei s e h r große 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 der ct’ kam ein Kasten aus der Originalpublikation des Verfahrens 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. Als Beispiel: ein 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 als Basis für die Geschwindigkeit des Computers schließen lässt. Später im Beitrag wurde gesagt, dass ein nicht mehr ganz taufrischer heutiger PC (Ryzen 2400G) dafür sechs Tage braucht, wenn er nicht „Brute Force“ nutzt sondern eine spezielle Technik, sogar „nur“ drei Stunden.
Immerhin: 6 Tage zu 74 Jahre, das ist eine Geschwindigkeitssteigerung um den Faktor 4.500. Klingt erst mal toll, relativiert sich aber, wenn man weiß, dass seitdem über 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 x86-Serie und den Speicherchips war der Verdopplungszeitraum über die Jahrzehnte gemittelt 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. Die Korrelation war auch lange Zeit so. Es ist, da der Ausdruck ja inzwischen durch Corona allgemein bekannt ist, ein Exponentielles Wachstum.
Der Faktor 4.500 entspricht, wenn man sie auf Zweierpotenzen umrechnet, etwas mehr als 12 Verdopplungszyklen (212 = 4.096, 213 = 8.192). Das entspricht einer Verdopplung alle 4 Jahre und dies liegt weit unter dem Moorschen Gesetz. Das Moorsche Gesetz legt selbst ergibt bei 24 Monaten für eine Verdopplung in den 50 Jahren insgesamt 25 Verdopplungszyklen. Diese entsprechen dem Faktor 32 Millionen. 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 und der Litographiemethode ab. Die Die-Größe 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. Kurz 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 0,5 bis 0,74 MHz. Der aktuelle Ryzen 5950X wird in 7 Nanometer Technologie gefertigt und erreicht 3.400 MHz im normalen Modus und 4.900 im Turbo Modus, wenn nicht alle Kerne laufen. Das führt zu folgender Tabelle der Steigerungen:
| Parameter | Intel 4004 | Ryzen 5950X | Steigerung |
|---|---|---|---|
| Transistoren pro Die: | 2.250 | 19.200.000.000 | 8.533.333 |
| Taktfrequenz [MHz]: | 0,74 | 3.400 / 4.900 | 4594 / 6621 |
| Strukturbreite Lithografie: | 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 beim Entschlüsseln 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. Daneben vergleicht man natürlich nicht mit dem Intel 4004 sondern einem Computer der 1 Million Operationen schafft. Das war damals eines der schnelleren Modelle der IBM 360 Serie. Bei der x86 Serie entspricht dies der Geschwindigkeit eines 80286, aber der erschien 1982, also hat man die Geschwindigkeit seit 1982 und nicht 1970 um den Faktor 4.500 gesteigert.
Dieser Faktor passt auf den ersten Blick zur Steigerung der Taktfrequenz gegenüber dem Intel 4004. Doch die sagt heute eigentlich nicht mehr viel über die Geschwindigkeit aus. Die Taktfrequenz stieg bis etwa 2003 rasant, bis Intel beim Pentium 4 Extreme eine Spitzentaktfrequenz von 3,82 GHz erreichte, dann aber die Abwärme nicht mehr in den Griff bekam. Die Architektur auf der die heutigen Core-Mikroarchitektur 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 seit dem Pentium 4 Jahren nur eine geringe Zunahme ist – in den vorherigen 17 Jahren stieg sie von 16 MHz beim 80386 auf 3.830 MHz. Die 3.830 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 andere 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 in der Lithografietechnologie also 1428² mehr. Mit der Steigerung der Elementzahl um den Faktor 8,5 Millionen ist hier sogar die Steigerung überproportional groß (erwartet: 1.428² entsprechend etwa 2,04 Millionen). Das liegt an der größeren Die-Größe des Ryzen 5950X, die sich auch im Preis niederschlägt, der obige Ryzen-Prozessor kostete bei Einführung im Handel 799 Dollar. Der Intel 4004 kostete 60 Dollar 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. Bei den heutigen PC liefert die Spitzenperformance die AVX-Befehle, die in einer Operation gleich vier bzw. bei den neuesten Prozessoren sogar acht 74 Bit Zahlen addieren und multiplizieren, was acht bzw. 16 Operationen pro Takt entspricht. Bei ganzen Zahlen kommen sie aber nicht über eine Operation/Takt und Kern heraus.
Die zweite 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-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, worauf sich die Operationenzahl bezieht – MIPS (Millionen Operationen per Second) eines Computers – dann benötigt aber jede Rechenoperation aufgrund der Ladebefehle mehrere elementare Maschinenbefehle / 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 drei 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.