Schneller entschlüsseln

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.