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 ∈ {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 = p·q ö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 ∈ ℕ₀

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. Diese Vorbereitungen sind nur einmalig zu treffen.

Danach können beliebige Sender B eine Nachricht m verschlüsseln und an A als Empfänger schicken. Nur A kann mithilfe seines privaten Schlüssels d die verschlüsselte Nachricht c wieder entschlüsseln. 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: Erzeugen der Schlüssel sowie Ver- und Entschlüsseln mit dem RSA-Verfahren

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 Beispiele für Verfahren zur Faktorisierung von zusammengesetzten Zahlen folgen anschließend noch die Algorithmem Quadratisches Sieb und p-1-Methode.

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 (siehe Äquivalenz zwischen Faktorisierung von n und Berechnung von φ(n)). Dieses ist nach heutiger Kenntnis zu rechenaufwendig. Auch direkt die e-te Wurzel aus c zu berechnen (modulo n) ist zu rechenaufwendig.

Dies gilt jedoch nur "im Allgemeinen". In speziellen Fällen sind andere Angriffe möglich.

p-1-Faktorisierung

Die Zahl n ist das Produkt zweier Primzahlen p und q. Weder p-1 noch q-1 dürfen aus zu kleinen Primfaktorpotenzen zusammengesetzt sein. Denn ansonsten lässt sich n mit der p-1-Methode von Pollard faktorisieren.

Low Exponent Attack

In der Frühzeit des RSA-Verfahrens wurde empfohlen, aus Gründen einer effizienten Verschlüsselung einfach den Exponenten e=3 zu wählen. Dies ist jedoch unsicher.

Angenommen, derselbe Klartext m wird an 3 verschiedene Empfänger geschickt, deren öffentliche Schlüssel (n, e) folgendermaßen lauten: (n₀, 3), (n₁, 3) und (n₂, 3), und die entsprechenden Geheimtexte c₀, c₁ und c₂ werden abgefangen. Dann lässt sich mithilfe des chinesischen Restsatzes der Klartext m berechnen.

Denn es gilt

m³ ≡ c₀ (mod n₀)
m³ ≡ c₁ (mod n₁)
m³ ≡ c₂ (mod n₂)

Der chinesische Restsatz liefert dann eine eindeutige Lösung modulo n₀·n₁·n₂ für m³. Durch Ziehen der dritten Wurzel ergibt sich der Klartext m.

Das Verfahren funktioniert entsprechend auch für andere kleine Exponenten e=5, e=7 usw. Ist jedoch der Exponent e groß, z.B. e=2¹⁶+1, so müssten entsprechend viele Geheimtexte, die den gleichen verschlüsselten Klartext m darstellen, abgefangen werden. Eine entsprechende Implementierung findet sich unter Low-Exponent-Angriff.

Aufgabe 1: Ein Klartext m wird mit folgenden öffentlichen Schlüsseln (n, e) verschlüsselt: (1357, 3), (1363, 3), (697, 3). Die entsprechenden Geheimtexte c sind 106, 953 und 101. Tragen Sie die drei Moduln 1357, 1363 und 697 sowie die drei Reste 106, 953 und 101 in das Berechnungsformular unten auf der Seite Chinesischer Restsatz ein und ermitteln Sie auf diese Weise m³. Ziehen Sie mit einem Taschenrechner die dritte Wurzel und berechnen Sie so den Klartext m ²).

Anhand eines Zahlenbeispiels mit kleinen Zahlen lässt sich der Ablauf der Berechnungen der RSA-Verschlüsselung 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.

Lesenswert ist der Originalartikel

[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)

Ansonsten findet sich das RSA-Verfahren in jedem Fachbuch über Kryptografie, so beispielsweise in

[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)

[Ert 12] W. Ertel: Angewandte Kryptographie. 4. Auflage, Hanser (2012)

[KK 10] C. Karpfinger, H. Kiechle: Kryptologie. Vieweg+Teubner (2010)

[PP 10] C. Paar, J. Pelzl: Understanding Crytography. Springer (2010)

[Schm 16] K. Schmeh: Kryptografie. 6. Auflage, dpunkt (2016)

[SSP 08] J. Swoboda, S. Spitz, M. Pramateftakis: Kryptographie und IT-Sicherheit. Vieweg+Teubner (2008)

[Lan 18] H.W. Lang: Kryptografie für Dummies. Wiley (2018)

[Weitere Informationen]

¹) Die Funktion mod liefert den Rest bei ganzzahliger Division

²) Die Lösung m=339 ist richtig.

Weiter mit: [Diffie-Hellman-Schlüsselvereinbarung] oder [up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 12.06.1997 Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden