Kryptografische Protokolle

RSA-Verschlüsselung

Das RSA-Verfahren ist nach seinen Urhebern Rivest, Shamir und Adleman [RSA 78] benannt. Es handelt sich um ein asymmetrisches Verschlüsselungsverfahren: Der Sender verschlüsselt den Klartext m mit dem öffentlichen Schlüssel (public key) e des Empfängers; der Empfänger entschlüsselt das Ergebnis, den Geheimtext c, mit seinem zugehörigen privaten Schlüssel (private key) d.

Asymmetrische Verfahren beruhen auf dem Begriff der Einbahnfunktion oder Einwegfunktion (one way function) – hier realisiert dadurch, dass es leicht ist, c = m^e mod n zu berechnen, aber praktisch unmöglich, die Umkehrfunktion zu berechnen. Nur durch Kenntnis einer Hintertür (trapdoor) d lässt sich die Funktion wieder umkehren, d.h. der Geheimtext c wieder entschlüsseln.

Der Klartext wird als Binärzahl m Element {0, ..., n-1} aufgefasst. Ist der Klartext zu lang, so wird er in mehrere Stücke zerlegt, die jeweils für sich verschlüsselt werden.

Es sind

`n`		öffentliche Zahl
`e`		öffentlicher Schlüssel des Empfängers
`d`		privater Schlüssel des Empfängers
`m` < `n`		Klartext
`c`		Geheimtext

Zur Verschlüsselung berechnet der Sender

c = m^e mod n

und erhält damit den Geheimtext c. ¹)

Die Zahl n ist das Produkt von zwei verschiedenen Primzahlen p und q, diese sind geheim. Wie können p und q geheim sein, wenn doch n = pq öffentlich bekannt ist? Dies beruht nur darauf, dass die Primfaktorzerlegung von n zu rechenaufwendig ist, da n sehr groß ist (z.B. 512 Bit lang).

Für die Zahl e muss gelten

ggt(e, φ(n)) = 1

Hierbei ist

φ(n) = (p-1)(q-1)

die Anzahl der zu n teilerfremden Zahlen, die kleiner als n sind.

Der Empfänger hat als privaten Schlüssel eine Zahl d mit

d·e mod φ(n) = 1 , d.h.

d·e = k·φ(n) + 1 für irgendein k Element natürliche Zahlen ₀

Ist n = pq, so gilt nach einem Satz von Euler für alle Zahlen m mit m < n und alle natürlichen Zahlen k :

m^k·φ(n)+1 mod n = m

Zur Entschlüsselung berechnet der Empfänger

`c`^d mod `n`		= `m`^d·e mod `n`
		= `m`^{k·φ(n) + 1} mod `n`
		= `m`

und erhält damit den Klartext m.

Das folgende Bild 1 zeigt die Abfolge der Berechnungen und Datenübermittlungen. A erzeugt zunächst die Zahl n sowie den öffentlichen Schlüssel e und den zugehörigen privaten Schlüssel d und veröffentlicht n und e.

Von diesem Zeitpunkt an kann ein beliebiger Sender B einen Klartext m verschlüsseln und an A als Empfänger schicken. Nur A kann mithilfe seines privaten Schlüssels d den Geheimtext c wieder entschlüsseln und den Klartext m zurückgewinnen. Ein Dritter C kennt zwar n und e, kann aber dennoch c nicht entschlüsseln (außer mit undurchführbar hohem Aufwand).

A	C	B

Schlüssel erzeugen
wählt Primzahlen `p` und `q`
berechnet `n` = `p`·`q` und φ(`n`) = (`p`-1)·(`q`-1)
wählt `e` mit ggt(`e`, φ(`n`)) = 1
berechnet `d` mit `d`·`e` mod φ(`n`) = 1

Schlüssel veröffentlichen
	`n`, `e`
		Verschlüsseln
		berechnet `c` = `m`^e mod `n`

Entschlüsseln
berechnet `m` = `c`^d mod `n`

Bild 1: Verschlüsseln und Entschlüsseln mit dem RSA-Verfahren

Um RSA zu knacken, müsste ein unbefugter Dritter versuchen, den privaten Schlüssel d aus dem öffentlichen Schlüssel e zu berechnen oder φ(n) irgendwie zu bestimmen. Es lässt sich zeigen, dass beides mindestens so schwer ist, wie die Primfaktorzerlegung n = p·q zu berechnen. Dieses ist nach heutiger Kenntnis zu rechenaufwendig. Auch direkt die e-te Wurzel aus c zu berechnen (modulo n) ist zu rechenaufwendig.

Für das Verständnis der Korrektheit und Effizienz des RSA-Verfahrens werden einige zahlentheoretische Grundlagen und Berechnungsverfahren gebraucht.

Zu diesen Berechnungsverfahren gehört ein Algorithmus für die modulare Exponentiation (um etwa m^e mod n zu berechnen), der erweiterte euklidische Algorithmus (um einen privaten Schlüssel d mit d·e mod φ(n) = 1 zu berechnen) sowie ein Algorithmus zur Berechnung von großen Primzahlen (um p und q zu erhalten). Als Beispiel für ein Verfahren zur Faktorisierung einer zusammengesetzten Zahl folgt anschließend noch der Algorithmus Quadratisches Sieb.

Anhand eines Zahlenbeispiels mit kleinen Zahlen lässt sich der Ablauf der Berechnungen noch einmal nachvollziehen.

Schlüssel erzeugen

Der Empfänger A veröffentlicht als öffentlichen Schlüssel zwei Zahlen n und e. Hierbei ist n das Produkt von zwei verschiedenen Primzahlen p und q:

p:

q:

n:

φ(n):

Für e wählt A eine Zahl mit ggt(e, φ(n)) = 1:

e:

Hieraus ergibt sich der private Schlüssel d mit d·e mod φ(n) = 1:

d:

Als öffentlichen Schlüssel veröffentlicht A also (n, e) = (55, 3); den privaten Schlüssel d hält A geheim.

Verschlüsseln

Der Sender B möchte eine Nachricht m an A schicken:

m:

und berechnet c = m^e mod n:

c:

Somit sendet B den Geheimtext c = 9 an A.

Entschlüsseln

Der Empfänger A berechnet m = c^d mod n:

m:

und erhält somit den Klartext m = 4 zurück.


[BNS 05]	A. Beutelspacher, H.B. Neumann, T. Schwarzpaul: Kryptografie in Theorie und Praxis. Vieweg (2005)
[Bu 00]	J.A. Buchmann: Introduction to Cryptography. Springer (2000)
[RSA 78]	R.L. Rivest, A. Shamir, L.M. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21, 2, 120-126 (1978)

[Lan 06]	H.W. Lang: Algorithmen in Java. 2. Auflage, Oldenbourg (2006) Das RSA-Verfahren finden Sie auch in meinem Buch über Algorithmen. Weitere Themen des Buches: Sortieren, Textsuche, Parsen und Übersetzen, Graphenalgorithmen, Arithmetik, Codierung, parallele Sortieralgorithmen. [Weitere Informationen] [Bestellen]