 | | | | | |||||||
| | | | | |||||||
| |
| | | |||||||
| | | | | |||||||
| | | | |
|
RSA ist einer der frühesten Algorithmen, die öffentliche Schlüssel verwenden. Der RSA-Algorithmus gilt seitdem als der einzige weitverbreitete und implementierte Ansatz der Verschlüsselung mit öffentlichen Schlüsseln.
Ein nichtmathematisches Beispiel (nach Alfred Beutelspacher)
Vergleichbar ist dieser Algorithmus mit dem Kochen einer geheimen Suppe
durch zwei Köche A und B. Beide benutzen die gleiche bekannte Ausgangssuppe.
Beide Köche haben jeweils geheime Gewürze. Sogar A kennt die
Gewürze von B nicht und umgekehrt. Jeder nimmt zum Beispiel die Hälfte
der Ausgangssuppe und fügt seine geheimen Gewürze dazu. Die halbfertigen
Suppen werden jetzt ausgetauscht. Sie sind also öffentlich, d. h.
jeder könnte sie probieren. Jetzt versetzt B die von A erhaltene Suppe
mit seinem Gewürz und A fügt der Suppe von B sein Gewürz
hinzu. Nun haben beide die gleiche Suppe mit der richtigen Menge an Gewürzen.
RSA ist eine Verschlüsselungstechnik, bei der Klartext und verschlüsselter
Text ganze Zahlen zwischen 0 und n-1 für ein beliebiges n sind. Bei
langen Nachrichten wird der Text in einzelne Blöcke aufgeteilt. Jeder
dieser Blocks hat eine Länge von log2n Bit.
Der öffentliche und der dazugehörige geheime Schlüssel
sind Funktionsergebnisse einer Funktion über große Primzahlen
(wobei ,,groß" hier mindestens 100 bis 200 Stellen bedeutet). Es
wird angenommen, daß es ebenso aufwendig ist, aus dem verschlüsselten
Text mit Hilfe des öffentlichen Schlüssels den Klartext zu gewinnen,
wie die Zerlegung eines Produkts großer Primzahlen zu finden. Um
die zwei Schlüssel, den geheimen und den öffentlichen, zu berechnen,
nimmt man zwei große Primzahlen p und q, die etwa gleich viele Stellen
haben sollten, da dies die Sicherheit erhöht.
Damit berechnet man das Produkt n=p·q und Æ(n)=(p-1)·(q-1).
Nun wählt man eine Zahl e, die anschließend zur Verschlüsselung verwendet wird. Der größte gemeinsame Teiler von e und Æ(n) sollte 1 sein ( ggT(e, Æ(n))=1 ) .
Damit berechnet man den Schlüssel d, der später zur Entschlüsselung verwendet wird:
e·d=1 mod Æ(n) , d=e-1 · mod Æ(n)
Für d und n gilt auch, dass ihr größter gemeinsamer Teiler 1 ist (ggT(n,e)=1).
Das Zahlenpaar (e,n) bildet den öffentlichen Schlüssel, (d,n)
ist der geheime. Die Primzahlen p und q werden nun nicht mehr benötigt
und sollten gelöscht, aber auf keinen Fall veröffentlicht werden.
Zur Sicherheit von RSA
Die Sicherheit dieses Algorithmus liegt in der Größe der verwendeten Schlüssel. Um aus dem öffentlichen Schlüssel den geheimen zu berechnen, muß man n in seine Primfaktoren zerlegen. Bei einer Zahl wie 91 mag das noch sehr einfach erscheinen, allerdings wird das bei 2091 (=51·41) schon schwieriger und bei RSA-Schlüsseln mit 200-stelliger Zahl n scheint das unmöglich zu sein.
Damit n geheim bleibt, müssen natürlich auch p und q geheim bleiben. Diese zwei Zahlen können nach der Berechnung des Schlüssels auch gelöscht werden.
Darin liegt aber auch der Nachteil von RSA. Je größer n ist,
desto länger ist der verwendete Schlüssel. Die Ver- und Entschlüsselung
dauert dadurch lange. Im Vergleich zu IDEA benötigt eine Ver- und
Entschlüsselung mit RSA etwa tausendmal soviel Zeit. Welche Schlüssellänge
allerdings hundertprozentige Sicherheit bietet, ist schwer zu sagen.
|
