Schneller entschlüsseln

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.