Von: Dr. Klaus Plessner
Am besten lieber gleich mit 1024 Bit verschlüsseln, oder gar mit 2048 Bit. Warum denn knausern; jetzt, wo die Liberalisierung der Kryptoexportgesetze im Gange ist. So mag der Anwender denken, der auf die Sicherheit seiner E-Mails zu Recht Wert legt. Nur haben lange Schlüssel einen entscheidenden Haken. Der Aufwand für das Chiffrieren und Dechiffrieren mit dem Public-Key-Verfahren RSA wächst nämlich mit der dritten Potenz der Schlüssellänge. Das heißt zum Beispiel, dass ein 1024-Bit-Programm bei der Arbeit achtmal so lange braucht wie eine 512-Bit-Variante. Wohlgemerkt erhöhen sich dabei gleichzeitig die Kosten zum Knacken des Codes um ein Vielfaches und überfordern irgendwo zwischen 512 und 1024 Bit schon alle Konten der Welt zusammengenommen.
Dass künftig auch Anwender von vergleichsweise langsamen Rechnern wie Mobiltelefonen und PDAs ihre Daten chiffriert übers Internet schicken können, ohne beim Verpacken und Auspacken zu lange zu warten, ist die Botschaft einer gemeinsamen Kampagne von Compaq und RSA Security. Die Technik, die die Beschleunigung ermöglichen soll heißt "Multiprime" und stammt von Compaq. Während das von Ronald Rivest, Adi Shamir und Leonard Adleman begründete RSA-Verfahren die Paare aus öffentlichem und privatem Schüssel mit Hilfe jeweils zweier Primzahlen erzeugt, verwendet der hier besprochene Algorithmus drei oder mehr.
Rechnen in Raten
Die Compaq-Entwickler schlagen vor, für die öffentlichen Schlüssel relativ kleine Zahlen zu wählen und statt dessen die privaten Nummernfolgen zu verlängern. Gegenwärtig sind bei RSA-Programmen private und öffentliche Keys gleich groß, nämlich 1024 Bit. Künftig sollen die geheimen Zahlen circa 2048 duale Stellen erhalten, also im Bereich des Modulus liegen (siehe Kasten). Weil der Public-Key kodiert und der Private-Key dekodiert, würde somit die für das Dechiffrieren nötige Zeit zunehmen, während das Chiffrieren schneller ginge. Multiprime soll nun den Zeitaufwand beim Entziffern und beim Signieren verringern. Während RSA erlaubt, das Zurückrechnen auf den lesbaren Text in zwei Aufgaben zu zerlegen, gliedert die neue Methode das Problem in drei und mehr Teile, entsprechend der Zahl der von ihr benutzten Primfaktoren. Diese Teilaufgaben sind zusammen um so rascher zu erledigen, je größer ihre Anzahl. Zweitens lassen sie sich von parallel arbeitenden Prozessoren gleichzeitig lösen. Ein zweifacher Zeitgewinn also durch einen Trick, der schon bei RSA auftaucht, und jetzt lediglich verfeinert wurde.
Schon auf einem Ein-Prozessor-Rechner erhöht Multiprime die Performance, sagen die Begründer der Technik. Und sie liefern auch die genaue Formel dafür: n Primfaktoren beschleunigen die Arbeit im Vergleich zur klassischen Zweiervariante um den Faktor (n2)/4. Bei drei Primzahlen bedeutet das eine 2,25- fache Beschleunigung, mit vier geht es viermal und mit sechs neunmal so schnell. Durch eine Anpassung des Programmcodes lassen sich damit zum Beispiel Performance-Barrieren von Smartcardsystemen beseitigen, die künftig Mobilfunkgeräte absichern werden.
Ideal für Parallelrechner
Mehrprozessorsysteme tun sich noch leichter. Für den Fall, dass die Zahl der parallel arbeitenden CPUs gleich der Zahl der verwendeten Primfaktoren ist, haben Mathematiker folgende Formel herausgebracht: Der Performance-Zuwachs eines n-Primzahl-Verfahrens beträgt gegenüber der RSA-Methode auf nur einem Prozessor (n3)/4. Weil er nach der dritten Potenz zunimmt, wächst er also schneller als bei Multiprime auf Single-Prozessor-Rechnern und kommt beispielsweise bei einem Vierersystem einem Faktor 16 gleich. Der Effekt könnte die Leistung von VPN-Gateways (VPN = Virtual Private Network) erhöhen, die zur Verschlüsselung eine Steckkarte mit mehreren Koprozessoren verwenden.
Um ihre Theorie zu überprüfen, haben die Forscher von Compaq einen "Proliant-6000"-Server in Gang gesetzt, der mit vier 200-MHz-Intel-Pentium-Prozessoren arbeitet, 650 MByte Arbeitsspeicher beschreiben kann und einen Cache-Speicher von 512 KByte besitzt. Als Betriebssystem wählten sie Windows 2000. Das Ergebnis entsprach weitgehend den Vorhersagen. Das Diagramm zeigt einen Vergleich zwischen der traditionellen RSA-Methode und zwei Multiprime-Dekodierern. Die Hochachse repräsentiert die Zeit. Entlang der vertikalen Achse steht die Bit-Länge der Moduli, die gleich der Länge der privaten Schlüssel ist. Ein Zahlenbeispiel: Bei 2048 Bit (entspricht hinsichtlich der Sicherheit heutigen 1024-Bit-RSA-Schlüsseln) brauchte die RSA-Software "Bsafe" rund 220 ms im Unterschied zur Achterzerlegung (256-Bit-Primfaktoren) mit 20 ms. Compaq prüfte auch Verschlüsselungs-Hardware, nämlich die hauseigene PCI-Karte "AXL 200", die maximal 24 Primfaktoren verarbeitet. Der Gewinn im Vergleich zu RSA ohne Multiprime fällt geringer aus als bei den Software-Varianten; die Werte liegen bei 10 ms und 5 ms für 2048-Bit-Moduli und einer achtfachen Zerlegung (256-Bit-Multiprime). Zu mobilen Geräten haben Compaq und RSA noch keine Tests veröffentlicht. Dort liegen die Dekodierzeiten zum Teil im Sekundenbereich.
Schranken der Sicherheit
Entwickler von Verschlüsselungsalgorithmen kommen nicht daran vorbei, zu fragen, wie sicher ihre Verfahren sind. Es könnte ja der Aufwand zum Abhören einer RSA-gesicherten Kommunikation in dem Maß abnehmen, wie die Zahl der Primfaktoren zunimmt. Compaq hat genau das untersucht und festgestellt, dass in der Tat Vielfach-Multiprime-Algortithmen Hackern das Handwerk einfacher machen. Allerdings reduziert sich die Rechendauer der Spione erst ab einer Mindestanzahl von Primfaktoren. Zum Knacken aller simpleren Multiprime-Systeme brauchen sie genauso lange wie bei RSA. Die Sicherheitskalkulation schließt, dass Anwender der Multiprime-Methode mit der errechneten Mindestanzahl von Faktoren Zeit gewinnen, ohne dabei das Einbruchsrisiko zu vergrößern.
Die Tabelle links stellt den Modulus der empfohlenen Anzahl von Faktoren gegenüber, wobei sich zeigt, dass die heute übliche 2048-Bit-Verschlüsselung höchstens um einen Faktor 6,7 zu beschleunigen ist. Dennoch hat das Multiprime-Verfahren gegenüber der heutigen RSA-Methode nur Vorteile: Erstens ist es nicht teurer, weil es vergleichsweise wenig Änderungen im Source-Code benötigt. Zweitens ist es schneller. Selbst einen Faktor 6,7 darf man nicht vernachlässigen, denn jede Performance-Verbesserung ist wünschenswert. Und drittens dient es dem Marketing als Nahrung. Schließlich braucht man den Sicherheitsverlust ja nicht gerade zu betonen. (kpl)