Kryptografie (5) : RSA

RSA ist ein asymmetrisches Verschlüsselungsverfahren. Das heißt, dass ein Benutzer ein Schlüsselpaar hat. Einmal einen Public-Key zum verschlüsseln und einen Private-Key zum entschlüsseln. Die beiden Schlüssel passen zueinander. Wird allerdings ein Schlüssel verloren, so muss ein neues Schlüsselpaar generiert werden, und die alten Nachrichten lassen sich nicht mehr ver- oder entschlüsseln, je nachdem welchen Key man verloren hat.

RSA (Rivest Shamir Adleman)

Das Verfahren trägt die ersten Buchstaben seiner Erfinder. Die Sicherheit von RSA basiert darauf, dass es schwer ist eine große Zahl zu faktorisieren, also in ihre Primfaktoren zu zerlegen. Weiterhin soll verhindert werden, dass man aus dem Public-Key (e,N) nicht so ohne weiteres auf den Private-Key (d,N) schließen kann. Es wird eine Schlüssellänge von mindestens 2048-bit, besser noch 4096-bit empfohlen. Es können also Zahlen dargestellt werden zwischen 0 und (2^4096)-1.

Mit der asymmetrischen Verschlüsselung sollen außerdem die "Man-In-The-Middle-Attacks" verhindert werden. Das heißt, es soll einer dritten Person nicht möglich sein die Kommunikation zwischen dem Sender und dem Empfänger zu belauschen. Was passiert aber wenn ein Angreifer die Public-Keys vom Sender und dem Empfänger abgreift? Nichts! Denn mit dem Public-Key kann man Nachrichten nur verschlüsseln und nicht entschlüsseln. Die dazugehörigen Private-Keys bleiben ja für immer auf der Sender- bzw. Empfängerseite. Zumindest sollte es das.
Ein Angreifer kann aber versuchen den Private-Key zu Brute-Forcen. Sowas kann extrem lange dauern. Lohnt sich also nicht. Das Generieren eines Schlüsselpaars kann zwischen Sekunden und Minuten dauern, je nachdem wie die Schlüsselstärke gewählt wird.

Formeln

Hier ein Überblick über die Verwendeten Formeln

Ein Rechenbeispiel

Gehen wir das Verfahren mal anhand eines praktischen Beispiels durch. Wir benötigen zuerst zwei (große) Primzahlen p und q. Nehmen wir mal p=7, q=11 also lautet unser N N=pq=77 (1). Nun brauchen wir eine natürliche Zahl e, die teilerfremd zu (p-1)(q-1), also 60 ist. Nehmen wir mal e=47 (2,3). Jetzt haben wir schon mal unseren Public-Key "berechnet".
Er lautet (e,N)=(47,77) (4). Jetzt beginnt der Spaß unseren Private-Key zu berechnen. Wir müssen aus 1=ed mod phi(N) (5) den Parameter d bestimmen. Also, setzen wir alle bekannten Werte ein, so ergibt dies: 1=47*d mod 60. Um d zu bestimmen wird der Erweiterte Euklidische Algorithmus angewendet. (Ich verzichte hier auf die genaue Berechnung, da dies den Beitrag sprengen würde). Das Ergbnis lautet d=23, und somit haben wir unseren Private-Key (d,N)=(23,77) (6). Da wir jetzt ein Schlüsselpaar haben, können wir unsere Nachrichten gemäß der asymmetrsichen Verschlüsselung ver- und entschlüsseln.

Für die Ver- und Entschlüsselung einer Nachricht m gibt es die beiden Formeln (7) und (8):
Zum Verschlüsseln gilt also im unseren Fall m^47 mod 77.
Zum Entschlüsseln gilt m^47*23 mod 77.