Home > Kryptographie > Asymmetrische Kryptographie > RSA

Kryptographie

10.1 Das Verfahren RSA

Die Sicherheit von RSA liegt in der Schwierigkeit begründet, (sehr) große Zahlen zu faktorisieren. Diese großen Zahlen sind Produkte zweier Primzahlen p und q, d. h. n = pq. Man geht davon aus, dass es schwer ist, aus gegebenem n p und q zu berechnen.

• 
• Schlüsselerzeugung
• Der euklidsiche Algorithmus
• Ver- und Entschlüsselung
• Ein Beispiel
• Beweis von RSA
• Diskussion von RSA

Schlüsselerzeugung

Zunächst muss ein öffentlicher und privater Schlüssel (Schlüsselpaar) erzeugt werden. Dies kann z. B. durch eine Schlüsselvergabestelle erfolgen. Diese wählt zufällig zwei große Primzahlen p und q:

n = pq

Dann wird Phi(n) (Symbol: Φ) berechnet. Dies dient der Berechnung der Anzahl der teilerfremden Zahlen zu n; z. B. ist Phi(15) = 8, da 1, 2, 4, 7, 8, 11, 13 und 14 keine gemeinsamen Teiler mit 15 haben (die 1 zählt man auch dazu). Da eine Primzahl nur durch 1 und sich selbst teilbar ist, sind alle Zahlen, die unterhalb von ihr liegen, zu ihr teilerfremd. D. h.: Phi(p) = p − 1 bzw. Phi(q) = q − 1. Folglich gilt für Phi(n):

Phi(n) = (p − 1)(q − 1)

Schließlich bestimmen wir zwei Zahlen e und d so, dass

ed mod Phi(n) = 1

gilt. Das bedeutet, e und d heben sich auf, genauso wie 4 und 1/4 bezüglich Multiplikation (4 · 1/4 = 1). Man sagt auch, d ist der Kehrwert von e modulo Phi(n).

e und n bilden nun den öffentlichen Schlüssel und d und n den privaten Schlüssel. Es ist nicht nötig, dass die Teilnehmer die Parameter p und q erfahren; am besten sollten p und q nach der Berechnung von e, d und n vernichtet werden, da sie praktisch nicht mehr benötigt werden und nur einen unnötigen Risikofaktor darstellen (denn wer p und q kennt, kennt auch n, und die Sicherheit des Systems wäre dahin).

Wie wählt man d und e? Zunächst sucht man sich eine beliebige Zahl e, die teilerfremd zu Phi(n) ist; das kann z. B. eine Primzahl sein, die größer als Phi(n) ist. Für e wurde beispielsweise die vierte Fermat-Zahl F₄ (2²⁴ + 1 = 2¹⁶ + 1 = 65537) vorgeschlagen, da Berechnungen mit dieser Zahl relativ einfach sind. Die Bestimmung von d (d. h. dem Kehrwert oder modularem Invers) ist ziemlich schwer; sie erfordert mehr oder weniger komplizierte Verfahren. d kann z. B. mit Hilfe des euklidischen Algorithmus berechnet werden.

Der euklidische Algorithmus

a = 105, b = 1001
1001 mod 105 = 56 (1001 = 9 · 105 + 56)
105 mod 56 = 49 (105 = 1 · 56 + 49)
56 mod 49 = 7 (56 = 1 · 49 + 7)
49 mod 7 = 0 (49 = 7 · 7)

Der ggT von 105 und 1001 ist demnach 7. Man könnte den Algorithmus auch folgendermaßen beschreiben:

r₀ = a
r₁ = b
r₀ = q₁ · r₁ + r₂
r₁ = q₂ · r₂ + r₃
r₂ = q₃ · r₃ + r₄
...
r_{n − 2} = q_{n − 1} · r_{n − 1} + r_n
r_{n − 1} = q_n · r_n

Diese Darstellung entspricht den oben in Klammern durchgeführten Berechnungen. r_n ist der größte gemeinsame Teiler.

Auf dem Computer geht's noch einfacher. Hier ein Beispiel in C:

int a, b;
/* Lese zwei Zahlen a und b ein */
while (b != 0)
{
  int r = a % b;
  a = b;
  b = r;
}
/* Gebe a als ggT aus */

Der größte gemeinsame Teiler kann auch als Summe von zwei Produkten dargestellt werden (Vielfachsummendarstellung); dies ist für unsere Zwecke von großer Wichtigkeit:

d = xa + yb

Um x und y zu berechnen, müssen wir die oben aufgeführte euklidische Gleichungskette von unten nach oben durchgehen; dies nennt man auch den erweiterten euklidischen Algorithmus.

Und so sieht das mit unserem Beispiel 105 und 1001 aus:

d = 7 = 56 − 1 · 49
= 56 - 1 · (105 − 1 · 56)
= (−1) · 105 + (1 + 1 · 1) · 56
= 2 · (1001 − 9 · 105) − 1 · 105
= 2 · 1001 − (2 · 9 + 1) · 105
= 2 · 1001 − 19 · 105

Sie sehen also, dass die Gleichungskette soweit umgeformt wurde, bis die Darstellung der Art x · a und y · b, also x · 1001 bzw. y · 105, war. So konnten wir x = 2 und y = −19 berechnen.

Sind a und b zueinander teilerfremd, d. h. ihr größter gemeinsamer Teiler ist 1, dann gibt es eine ganze Zahl c mit der Eigenschaft

b · c mod a = 1

Man sagt in diesem Fall, dass b modulo a invertierbar ist. Warum ist das so? Nun, da a und b teilerfremd ist, gilt

xa + yb = d = 1

Da xa ein Vielfaches von a ist, ist xa modulo a 0 – es lässt sich ohne Rest durch a teilen. c ist also gleich y.

Jetzt wissen wir auch, wie wir mit Hilfe des willkürlich gewählten e und des bekannten Phi(n) die Zahl d berechnen können. Wie wir bereits gesehen haben, soll gelten:

ed mod Phi(n) = 1 oder anders ausgedrückt:
x · Phi(n) + y · e = 1

y (bzw. c) stellt das gesuchte d dar.

Neben dieser Berechnung nach dem euklidischen Algorithmus existiert noch eine weitere Berechnungsart, die auf dem Satz von Euler beruht, allerdings nicht immer funktioniert. Im Folgenden dazu mehr.

Ver- und Entschlüsselung

Um eine beliebige Nachricht m zu verschlüsseln, die kleiner oder gleich n ist, führen wir folgende Berechnung durch:

c = m^e mod n

Das heißt, m (die Nachricht) wird mit e potenziert, und der Rest, der sich bei der Division durch n ergibt, bildet den Chiffretext oder Geheimtext c. Wenn n beispielsweise 512 Bit lang ist, muss m kleiner oder gleich 512 Bit lang sein.

Um den Geheimtext wieder umzuwandeln, berechnet der Empfänger:

m = c^d mod n

Damit das Verfahren reibungslos über die Bühne gehen kann, muss gewährleistet sein, dass sich e und d "aufheben" (siehe auch Schlüsselerzeugung):

e · d mod (p−1)(q−1) = 1

Ein Beispiel

So, jetzt mal ein kleines Beispiel zur Verschlüsselung mit RSA. Wir wählen zunächst zwei Primzahlen p und q, sagen wir jetzt einfach 7 und 13 (normalerweise sollten diese Zahlen mehrere hundert Stellen haben, aber das ist hier ja schwer möglich; Sie können die Schritte am Taschenrechner mitverfolgen). Das bedeutet für p, q und n:

p = 7
q = 13
n = 7 · 13 = 91
Phi(n) = (7 − 1) · (13 − 1) = 6 · 12 = 72

Jetzt müssen wir noch e und d bestimmen. Für e wählen wir eine zu Phi(n) teilerfremde Zahl > Phi(n), z. B. 77. Mit Hilfe des erweiterten euklidischen Algorithmus berechnen wir d = 29. Das heißt:

e = 77
d = 29

Diese Zahlen genügen der Anforderung

ed mod Phi(n) = 1
(77 · 29) mod 72 = 1

Wir kennen also

n = 91
Phi(n) = 72
e = 77
d = 29

Der öffentliche Schlüssel besteht aus e und n, der private aus d und n.

So, und nun möchten wir gerne die Nachricht m = 10 (m muss kleiner oder gleich n, also 91, sein!) verschlüsseln. Also berechnen wir

c = 10⁷⁷ mod 91
c = 82

Der Geheimtext lautet demzufolge 82. Jetzt lassen Sie uns mal sehen, ob wir auch wieder den ursprünglichen Klartext erhalten:

m' = 82²⁹ mod 91
m' = 10
m' = m

Sehen Sie, es hat geklappt! So sieht das Ganze in der Praxis natürlich nicht aus. Da geht's etwas komplizierter zu, schon allein wegen der großen Zahlen.

Beweis von RSA

Wir behaupten: Der RSA-Algorithmus arbeitet korrekt, d. h.: m' = m. Diese Tatsache können wir auch beweisen. Dazu muss ich Ihnen jedoch kurz den Satz von Euler vorstellen. Dieser ist eine Verallgemeinerung des kleinen Satzes von Fermat, der lautet:

Ist n prim und m kein Vielfaches von n, so gilt:

mⁿ⁻¹ mod n = 1

Bei der Eulerschen Verallgemeinerung dieses Satzes gilt:

m^Phi(n) mod n = 1

für die teilerfremden natürlichen Zahlen m und n. Besonders für den RSA-Algorithmus ist der Fall von Bedeutung, in dem n das Produkt der beiden Primzahlen p und q ist:

m^{(p−1)(q−1)} mod pq = 1

Der Beweis von RSA erfolgt in mehreren Schritten. Zunächst machen wir uns klar, dass

c = m^e mod n
m' = c^d mod n = (m^e)^d mod n = m^ed mod n

ist. Die Dechiffrierfunktion von RSA arbeitet genau dann korrekt, wenn

m^ed mod n = m

für alle natürlichen Zahlen m gilt.

1. Schritt. Es gilt:

m^ed mod p − m mod p = 0
(m^ed − m) mod p = 0

Warum ist das so? Wir erinnern uns, dass e und d so gewählt wurden, dass

ed mod Phi(n) = 1

gilt. Daher gibt es auch eine Zahl k mit

ed = 1 + k · Phi(n)

Zur Erläuterung: Durch eine Modulo-Operation erhält man ja nur den Rest, der bei der Division durch eine Zahl anfällt. In diesem Fall ist der Rest 1; addiert man zu diesem Rest das Produkt der Zahlen k und Phi(n), erhält man das Produkt von e und d. Nun wollen wir den Satz von Euler anwenden; dieser erfordert jedoch, dass m und p teilerfremd sind. Dies ist selbstverständlich nicht immer der Fall. Wenn m und p nicht teilerfremd sind, ist p notwendigerweise eine Teiler von m. Das bedeutet:

m mod p = 0

Wenn p ein Teiler von m ist, ist p auch ein Teiler von m^ed. Also gilt:

(m^ed − m) mod p = 0

da p sowohl m^ed als auch m teilt. Wir folgern daraus: Wenn ggT(m, p) ungleich 1 ist, gilt unsere Behauptung in diesem Spezialfall. Wenn m und p teilerfremd sind, besagt der Satz von Euler:

m^Phi(p) mod p = 1

Für Phi(p) = p − 1 ergibt sich nun:

m^ed mod p = m^1+k·Phi(n)
= m · m^k·Phi(n) mod p
= m · m^{k·(p−1)(q−1)} mod p
= m · (m^p−1)^k·q−1 mod p

Zur Erläuterung: Wir haben also ein bisschen umgestellt, so dass wir nun den Satz von Euler direkt auf m^p−1 anwenden können (es ist durchaus erlaubt, innerhalb dieser Klammer eine Modulo-Operation durchzuführen):

= m · (m^p−1 mod p)^k·q−1 mod p
= m · 1^k·(q−1) mod p
= m mod p

Unsere zu Anfang gestellte Behauptung gilt also für alle natürlichen Zahlen m, gleich, ob ggT(m, p) gleich oder ungleich 1 ist.

2. Schritt. Nun erfolgt die Beweisführung für q; da dieser Schritt analog zu Schritt 1 verläuft, sei hier auf eine ausführliche Darstellung verzichtet. Nun fassen wir diese beiden Schritte zusammen.

3. Schritt. Da die beiden Primzahlen p und q die Zahl

z = m^ed − m

teilen (was wir in den beiden vorherigen Schritten bewiesen haben), teilt auch ihr Produkt n die Zahl z. Also gilt:

m^ed mod pq = m
m^ed mod n = m

Somit haben wir die Aussage des Satzes bewiesen: Der Dechiffrieralgorithmus arbeitet korrekt.

Die Ausführungen dieses Beweises stammen zum großen Teil aus dem Buch "Kryptologie" von Albrecht Beutelspacher.

Diskussion von RSA

RSA stützt seine gesamte Sicherheit darauf, dass aus dem Modulus n und dem öffentlichen Schlüssel e keine Rückschlüsse auf den geheimen Schlüssel d gezogen werden können und dass die Faktorisierung von n (d. h. die Zerlegung von n in die Primzahlfaktoren p und q) so schwierig bleibt wie sie heute ist. Unglücklicherweise kann man jedoch nicht einmal beweisen, dass es sich bei der Faktorisierung von n um ein solch komplexes Problem handelt (man nimmt allerdings an, dass es so ist).

Wie bereits gesagt, benötigt man für RSA lange Schlüssel. Das sind nicht etwa Zahlen im Milliarden- oder Billionen-Bereich, sondern riesengroße Zahlen mit mehreren hundert Stellen. Das Problem ist, dass a) die Rechenleistung stark ansteigt und b) man neue Möglichkeiten zur Faktorisierung der Zahlen finden könnte. Das beste Verfahren für Zahlen mit mehr als ca. 110 Stellen ist momentan das allgemeine Zahlkörpersieb (siehe Tabelle). Die Schwere dieses Problems wird dann deutlich, wenn man sich einmal vor Augen hält, welche Aussagen über die Faktorisierung gemacht wurden. 1977 sagte Ron Rivest, die Faktorisierung einer 125-stelligen Zahl dauere 40 Billiarden Jahre. 17 Jahre später, 1994, wurde eine 129-stellige Zahl faktorisiert! Das zeigt nur, wie schwer es ist, auch nur annähernd genaue Aussagen zu treffen. Auf jeden Fall kann man wohl mit Gewissheit sagen, dass 512-Bit-Schlüssel schon längst nicht mehr ausreichen. 1024 Bit sollten das absolute Minimum sein. Wenn ich Ihnen allerdings einen Tipp geben darf, so sollten Sie mindestens 2048 Bit verwenden, um noch über einen längeren Zeitraum Ihren Schlüssel verwenden zu können.

Einige Verfahren zum Faktorisieren großer Zahlen

Empfohlene Längen für öffentliche Schlüssel (in Bit; Stand: 1994)

Zu obiger Tabelle: Derartige Voraussagen sind natürlich zu einem gewissen Grad immer unsinnig, da bahnbrechende technologische Fortschritte nicht berücksichtigt werden können. Wer weiß schon, wie weit wir im Jahre 2020 oder 2045 ist? Betrachtet man jedoch die Entwicklung der letzten Jahrzehnte, so können Sie grundsätzlich davon ausgehen, dass sich die Rechenleistung alle zehn Jahre verdoppelt. Die folgende Tabelle von Bruce Schneier gibt Voraussagen zur Faktorisierung für die nächsten Jahrzehnte:

Längerfristige Voraussagen zur Faktorisierung

Ich allerdings halte diese Schätzungen für ausgesprochen pessimistisch und frage mich, ob 32768-Bit-Schlüssel (!) jemals geknackt werden können. Zieht man jedoch mögliche revolutionäre Entwicklungen in der Technik in Betracht (z. B. Quantencomputer), könnten sich diese Voraussagen durchaus als realistisch erweisen.

Neben den hier vorgestellten Angriffen gegen RSA gibt es noch einige weitere Methoden, die das Faktorisierungsproblem untergraben können. Da wäre z. B. ein Chosen-Ciphertext-Angriff, bei dem der Angreifer Alices Nachricht an Bob abfängt (und ähnliche Szenarien). Mit Hilfe bestimmter Operationen (und der Unterstützung von Alice, wenn sie des Vorgangs nicht gewahr wird) kann es dem Angreifer gelingen, die verschlüsselte Nachricht zu entschlüsseln.

Zudem erwies sich RSA als anfällig für Angriffe auf Systeme, die immer dasselbe Modul n verwenden, aber unterschiedliche e und d. Dies funktioniert leider nicht, da ein Angreifer unter Kenntnis von n, e₁, e₂, c₁ und c₂ (diese Zahlen sind ja öffentlich und nicht geheim!) der geheimen Nachricht m habhaft werden kann. Eine Gruppe von Benutzern sollte daher niemals einen gleichen Wert für n benutzen.

Auch existieren Angriffe gegen RSA mit kleinen Verschlüsselungs-Exponenten. Wird ein kleiner Wert für e gewählt, erhöht sich im Allgemeinen die Geschwindigkeit von RSA. Dies kann aber auch unvorteilhaft sein und Angriffe auf das System ermöglichen. Unter Kenntnis von e(e + 1)/2 linear abhängigen Nachrichten gibt es einen Angriff; bei weniger Nachrichten gibt es kein Problem. Sind die Nachrichten identisch, so genügen bereits e Nachrichten. Derartige Probleme lassen sich jedoch leicht umgehen, indem man die Nachricht mit unabhängigen Zufallswerten auffüllt, wie es viele RSA-Implementationen vormachen (z. B. PGP).

Des Weiteren wäre noch erwähnenswert, dass es in der Praxis – mal wieder – noch komplizierter aussieht. Zum Beispiel sollten die Primzahlen gewissen Anforderungen genügen, sonst wird der Algorithmus anfällig für Angriffe. Zudem ist das RSA-Kryptosystem nicht so einfach zu implementieren wie symmetrische Algorithmen wie DES oder RC4. Unbemerkt könnten sich also irgendwo Fehler einschleichen. Außerdem ist RSA so langsam, dass es sich kaum lohnt, die Klartexte damit zu verschlüsseln. Man zieht es daher vor, den Schlüssel, der dem Chiffrieren des Klartextes mit Hilfe eines symmetrischen Verfahrens dient, mit RSA zu verschlüsseln. So macht es z. B. PGP. Und noch ein Problem, bevor ich es vergesse: Natürlich muss man geeignete Primzahlen suchen, schließlich müssen bzw. sollten sie zufällig gewählt sein. Das heißt nicht, dass man eine zufällige Zahl aus der Menge der möglichen Zahlen herausgreift und dann versucht, diese zu faktorisieren – nein, das dauerte entschieden zu lang. Man benutzt statt dessen statistische Verfahren, um festzustellen, ob eine Zahl prim ist oder nicht. Wenn man diese Verfahren oft genug bei den Primzahl-Kandidaten durchführt, wird die Wahrscheinlichkeit immer größer, dass die Zahl prim ist. Da man diese Aussage aber trotzdem nicht mit 100%-iger Wahrscheinlichkeit zu treffen vermag, nennt man diese Zahlen, die statistischen Verfahren entstammen, auch Pseudoprimzahlen. Der Vorteil ist hierbei die Tatsache, dass die Frage "Ist n prim?" wesentlich leichter beantwortet werden kann als die Frage "Was sind die Faktoren von n?" – und genau daher rührt die Sicherheit von RSA! Ich kann schnell und einfach Primzahlen finden und deren Produkt bilden; viel schwerer ist es dagegen, anhand des Produktes herauszufinden, wie die Faktoren dieser Zahl lauten.

Machen Sie sich also bloß keine Sorgen wegen der Primzahlen:

1. Es gibt ausreichend viele Primzahlen der Länge 512 Bit. Die Anzahl der Primzahlen (10¹⁵¹) übersteigt die Anzahl der Atome im Universum (schätzungsweise 10⁸⁰) bei weitem.
2. Die Wahrscheinlichkeit, dass zwei Leute zufällig dieselbe Primzahl der Länge 512 Bit wählen, ist praktisch gleich null. Mit anderen Worten: Das wird nicht passieren.
3. Es ist physikalisch nicht möglich, eine Datenbank mit allen möglichen Primzahlen der Länge 512 Bit anzulegen.

Dies alles sollte man bei der Implementierung von RSA beachten, denn sonst könnte das gesamte Gerüst in sich zusammenbrechen und leicht gebrochen werden. Wenn Sie Programme einsetzen, die RSA benutzen, sollten Sie sicherstellen, dass dieses Programm vertrauenswürdig ist. PGP (wenigstens die Version 2.6.3i) gilt als sicher, da schon lange von allerlei Programmierern sorgfältig auf Fehler geprüft.

Zum Abschluss dieses Kapitels möchte ich noch auf die Anleitung RSA in 7 Schritten (engl.) hinweisen, die Ende Juli in der Newsgroup sci.crypt gepostet wurde.

Zurück

nach oben

Übersicht

Weiter

Letzte Änderung: 27.03.2002
© 2002 by Christian Thöing