RSA-Code gefährdet

Kein Schutz durch Primzahlen

05. April 2004
Von Nikolaus Deussen
Im vergangenen Dezember gelang es Bonner Mathematikern, einen weiteren RSA-Schlüssel zu dechiffrieren. Zwar gerät dadurch die Sicherheit im Web noch nicht ins Wanken. Spätestens jedoch, wenn Quantencomputer Realität werden, hat RSA ausgedient.

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 SecuritySecurity 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. Alles zu Security auf CIO.de

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.