Dipl.-Inform. Carsten Eilers

RSA ist ein asymmetrisches Verschlüsselungsverfahren, dass auch als Signatursystem eingesetzt werden kann. Es wurde nach den Initialen der Nachnamen seiner Erfinder Ronald L. Rivest, Adi Shamir und Leonard Adleman benannt, die das Verfahren 1978 im Paper "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" (PDF) vorstellten.

Der RSA-Algorithmus ist sehr einfach. Seine Sicherheit basiert auf der so genannten Faktorisierungsannahme: Es gibt keinen effizienten Algorithmus, um eine gegebene große Zahl in ihre Primfaktoren zu zerlegen.

Die Schlüsselerzeugung

1. Wähle zufällig und stochastisch unabhängig zwei Primzahlen p und q, p≠q
2. Berechne n = p * q und φ(n) = (p-1) * (q-1) (φ ist die Eulersche φ-Funktion)
3. Wähle eine Zahl c, für die gilt 1 < c < φ(n), die teilerfremd zu φ(n) ist (d.h. der größte gemeinsame Teiler ggT(c,φ(n)) = 1)
4. Berechne d aus p, q und c als multiplikatives Inverses von c modulo φ(n), also c * d ≡ 1 mod φ(n).
   Dazu wird der erweiterte euklidische Algorithmus verwendet.

Der öffentliche Schlüssel (Public Key) besteht aus c und n, der private Schlüssel (Private Key) aus d und n. Meist werden auch die Faktoren p und q gespeichert, da sie bei der Entschlüsselung verwendet werden können.

Ein Zahlenbeispiel:

1. Wir wählen p=3 und q=11
2. n = p * q = 3 * 11 = 33, φ(n) = (p-1) * (q-1) = (3-1) * (11-1) = 2 * 10 = 20
3. c muss teilerfremd zu 20 sein, wir wählen willkürlich 7.
4. Berechnung der Inversen:
   

   Es gilt	c * d ≡ 1 mod φ(n),
   also	7 * d ≡ 1 mod 20

   Wie man in diesem Fall mit bloßen Auge sieht, ist d=3.

Der öffentliche Schlüssel besteht also aus c=7 und n=33, der geheime Schlüssel aus d=3 und n=33.

RSA als Verschlüsselungssystem

Klartexte werden als Zahlen m, 0 ≤ m ≤ n, dargestellt. Zu lange Klartexte müssen ggf. in passende Blöcke aufgespalten werden.

Die Verschlüsselung erfolgt durch modulare Exponentiation mit c, für den Klartextblock m also durch die Berechnung von
m^c mod n.

Die Entschlüsselung erfolgt durch modulare Exponentiation mit d, für den Geheimtextblock m^c also durch die Berechnung von
(m^c)^d mod n = m.

Abb. 1: Das RSA-Verfahren als Verschlüsselungssystem (Klick für großes Bild)

Im Zahlenbeispiel:

Verschlüsselt werden soll m=25, der öffentliche Schlüssel ist c=7 und n=33:

Geheimtext = 25⁷ mod 33 = 6103515625 mod 33 = 31

Entschlüsselt wird mit dem geheimen Schlüssel d=3 und n=33:

Klartext = 31³ mod 33 = 29791 mod 33 = 25

RSA als digitales Signatursystem

Die Bezeichnungen von oben werden umbenannt: Aus c wird t, aus d wird s.

Das Signieren geschieht durch modulare Exponentiation mit s, für den Klartextblock m also durch die Berechnung von
m^s mod n.

Das Testen erfolgt durch modulare Exponentiation der Unterschrift mit t und anschließendem Vergleich des Ergebnisses mit dem dazu gehörenden Textblock. Für den Klartextblock m mit der Signatur m^s also durch
(m^s)^t mod n = m ?

Abb. 2: Das RSA-Verfahren als digitales Signatursystem (Klick für großes Bild)

Im Zahlenbeispiel:

Signiert werden soll m=25, der geheimen Schlüssel ist s=3 und n=33:

Signatur = 25³ mod 33 = 15625 mod 33 = 16

Geprüft wird die Signatur mit dem öffentlichen Schlüssel t=7 und n=33:

Prüfwert = 16⁷ mod 33 = 268435456 mod 33 = 25=m - die Signatur ist korrekt

Die tatsächliche Anwendung ist natürlich etwas komplizierter als diese beiden kleinen Beispiele (wann verschlüsselt oder signiert man schon reine Zahlen?), aber das ist für das Verständnis der aktuellen Forschungsergebnisse egal. Welche Auswirkungen die haben, erfahren Sie in der nächsten Folge.

Carsten Eilers

Übersicht über alle Artikel zum Thema

RSA und die schwachen Schlüssel, Teil 1: Einführung in RSA

RSA und die schwachen Schlüssel, Teil 2: Die Schlüssel

RSA und die schwachen Schlüssel, Teil 3: Die Gefahren