RSA-Chiffrierung
RSA steht für Rivest, Shamir und Adleman, die Entwickler des Algorithmus. Das Verfahren ist von der Firma RSA Data Security Inc. patentiert und darf nur mit Lizenz verwendet werden.
RSA ist ein sogenanntes "public key-Verfahren". Dies bedeutet, daß ein öffentlicher Schlüssel herausgegeben wird, mit dem alle Absender ihre Nachrichten verschlüsseln. Der Empfänger dieser Nachrichten besitzt einen eigenen zweiten Schlüssel, den privaten Schlüssel. Mit diesem ist es möglich, die Nachricht zu entschlüsseln. So kann zwar jeder eine Nachricht verschlüsseln, aber nur der Besitzer des privaten Schlüssels kann sie wieder entschlüsseln.
RSA basiert auf der Faktorisierung sehr großer Zahlen (über 300 Dezimalstellen). Aus zwei sehr großen Primzahlen p und q wird ein Produkt n berechnet, welches den ersten Teil öffentlichen Schlüssel darstellt:
n = pq
Sodann benötigen wir einen Exponenten e, welcher den zweiten Teil des öffentlichen Schlüssels darstellt. e ist für gewöhnlich 3, 17 oder 65537:
e = 3
Unser öffentlicher Schlüssel ist nun
k = (e, n)
Als nächstes muß der private Schlüssel von n ermittelt werden. Dies geschieht mit dem erweiterten Euklidischen Algorithmus (der hier nicht aufgeführt ist). Diesen privaten Schlüssel d erhalten wir also mit
d = f(n),
wobei f den Euklidischen Algorithmus durchführt und somit d ermittelt. Der private Schlüssel ist geheim und darf nur dem Empfänger der Nachricht bekannt sein.
Nachdem wir hiermit also die Schlüssel erzeugt haben, geht es ans Erzeugen des Geheimtextes mit
m ist dabei der in eine Zahl umgewandelte Klartext. Es gilt die Vorschrift
m < n
Die ursprüngliche Nachricht erhält der Empfänger durch
Schwachstellen: Wenn es dem Angreifer gelingt, den Schlüssel n in seine Primfaktoren p und q zu zerlegen, ist es ihm möglich, den privaten Schlüssel d zu berechnen. Heutige Computer sind nicht in der Lage, dies in akzeptabler Zeit zu erledigen, es sei denn, der Angreifer ist bereit, eine fünf- bis sechsstellige Summe für den Bau eines solchen Supercomputers zu investieren. Schnelle Computer sind aber nicht die Lösung zum Knacken von RSA, da es umso sicherer wird, je größer die Primzahlen sind. Wenn also die Faktorisiergeschwindigkeit zunimmt, wird einfach die Schlüssellänge erhöht, so daß der Geschwindigkeitsvorteil aufgehoben wird.
TR