Primzahlen sind merkwürdig. Sie lassen sich nur durch sich selbst und durch eins teilen. Und wir kennen nicht einmal alle. Doch sie bilden die Basis für eine der wichtigsten Codierungs-Techniken im Internet: die RSA-Methode. Die Tarntechnik des amerikanischen Unternehmens RSA Security findet sich in jedem Browser und maskiert beispielsweise Kreditkartennummern. Sie ist auch Teil der Codierungssoftware Pretty Good Privacy (PGP), mit der sich E-Mails chiffrieren lassen. Auch digitale Unterschriften werden mit dem RSA-Algorithmus generiert.
Der Aufstieg des Kryptoverfahrens begann Mitte der 1970er-Jahre, als RSA eine schwerwiegende Schwäche herkömmlicher Verschlüsselungstechniken ausmerzte. Bis dahin mussten sich Absender und Adressat vor dem Austausch geheimer Nachrichten auf einen Chiffrierschlüssel einigen. Übeltäter konnten diese notwendige Klartext-Kommunikation verfolgen und den Code ergattern. Weil zum Ver- und Entschlüsseln derselbe Schlüssel gebraucht wird, heißen solche Verfahren symmetrisch.
RSA wird asymmetrisch genannt, weil es zwei unterschiedliche Schlüssel benutzt. Das Verfahren basiert auf zwei zufällig ausgewählten Primzahlen, die miteinander multipliziert werden. Das Ergebnis wird als öffentlicher Schlüssel (public key) zugänglich gemacht. Mit ihm kann jeder Post chiffrieren, deren Inhalt nur dem Empfänger bekannt werden soll. Aufdröseln lassen sich die Mitteilungen nur mit dem passenden privaten Schlüssel (private key), der sich ebenfalls aus dem Primzahl-Produkt ableitet. Die Primzahlen selbst werden nach dem Erstellen der Schlüssel verworfen.
Bedrohung durch handelsübliche Rechner
Zum Geheimcode wird RSA, weil sich die beiden Primfaktoren nur mit immensem Zeitaufwand aus dem öffentlichen Schlüssel wieder errechnen lassen. Zwar ist es mathematisch anspruchslos festzustellen, welche Teiler eine Zahl hat. Doch es gibt bis heute keinen einfachen Test, der zeigt, ob eine Zahl prim ist. Die bekannten Algorithmen werden für große Zahlen extrem zeitaufwändig. Dabei schnellt der Rechenaufwand für die Faktorisierung, die Zerlegung in die ursprünglichen Primzahlen, mit jedem zusätzlichen Bit in der Chiffrelänge rapide nach oben. Allein an diesem Zeitargument hängt allerdings auch die Sicherheit. "Wir verwenden Datenverschlüsselungs-Methoden, deren Sicherheit nicht bewiesen ist", warnt Axel Schenzle von der Münchner Ludwig-Maximilians-Universität: "Letztlich stützt sie sich auf die begrenzte Rechnerleistung existierender Computer."
Auf Dauer gibt es keinen sicheren Schlüssel, doch dieses Thema scheint in deutschen Firmen tabu. In der Wissenschaftsgemeinde wird dagegen fleißig und öffentlich über Codierung und Decodierung von Nachrichten diskutiert. Um dieses Know-how für sich zu nutzen, veranstaltet RSA Security für Wissenschaftler einen steten Wettbewerb. Auf ihrer Homepage findet sich eine Liste mit RSA-Zahlen, für die es noch keine Zerlegung in die anfänglichen Primzahlen gibt. Wer eine findet, erhält einen Geldpreis: je länger der Schlüssel, desto höher der Betrag.
Um den 48-Bit-Schlüssel zu decouvrieren, musste Germano Caronni von der ETH Zürich 1997 noch 300 Enthusiasten mit 5000 Computern zusammenbringen. Zum Millenniumswechsel knackte ein schwedisches Kryptologen-Team um Fredrik Almgren den RSA-Code mit 512 Bit. 70 Jahre Rechenzeit hätte ein Computer mit den bisher bekannten Berechnungsmethoden benötigt. Doch die Stockholmer Forscher setzten nicht nur auf die schiere Rechenkraft von Elektronengehirnen. Um das Rätsel zu lösen, ersannen sie ein neues, schnelles Rechenverfahren. Der ausgebuffte Algorithmus präsentierte schon nach wenigen Wochen das Ergebnis.
576 Bit nur ein bisschen sicher
Ende letzten Jahres zerlegte Jens Franke von der Bonner Universität die Chiffre mit 576 Bit: ein Weltrekord. Das Preisgeld: 10 000 US-Dollar. "Unser Rekord ist der erste dieser Art, bei dem ein Netzwerk handelsüblicher Linux-Rechner zum Einsatz kam", so Mathematiker Franke. Beteiligt an der Rekordleistung waren das Centrum voor Wiskunde en Informatica in den Niederlanden, das Bundesamt für Sicherheit für Informationstechnik sowie das Bonner Institut für Numerische Simulation. Die heute verwendeten RSA-Schlüssel sind meist 1024 Bit lang. "Das heißt, als Binärzahl aus Nullen und Einsen geschrieben hätten sie 1024 Ziffern", erklärt Marc Alexander Schweitzer vom Institut für Numerische Simulation.
Peter Shor aus den Forschungslabors von AT & T hat jedoch schon vor ein paar Jahren ein Rechenverfahren vorgestellt, das eine Zerlegung in Faktoren genauso schnell erledigt wie die Multiplikation. Dabei nutzt der amerikanische Mathematiker die Fähigkeit der Quantenbits, sich unterschiedliche Zustände merken und dadurch parallel abarbeiten zu können.
Faktorieren so schnell wie Multiplizieren
Allerdings funktioniert Shors Methode nur auf Quantencomputern, von denen es bislang lediglich Prototypen gibt. Isaac Chuang von IBM baute 2001 einen kleinen Versuchs-Quantenrechner, mit dem er die Tauglichkeit des Shorschen Quantenparallelismus überprüfte. Der Q-Computer schaffte mit sieben Quantenbits aus Fluoratomen bereits die korrekte Zerlegung der Zahl 15. Das klingt noch nicht wirklich bedrohlich. Dennoch: "Es gibt keinen Grund anzunehmen, dass der dramatische Fortschritt der letzten 20 Jahre schon an seinem Ende angelangt sei", warnt Johannes Buchmann, Mathematiker an der Technischen Hochschule Darmstadt.
In Ermangelung von Quantencomputern versuchen die Bonner Mathematiker erst einmal, mit herkömmlicher Technik den nächsten Code zu knacken. Sie visieren als Nächstes RSA-640 an. Im Laufe des Jahres, hoffen sie, können sie die Zahl tranchieren. Wie lange es braucht, um RSA-2048, die größte durch RSA Security veröffentlichte Zahl, zu faktorisieren, kann derzeit nicht einmal vermutet werden. Dem Sieger winkt dann allerdings das erkleckliche Sümmchen von 200 000 US-Dollar.