RSA-Verschlüsselung zum Ausprobieren

Wähle zwei Primzahlen, gib eine Nachricht ein und beobachte, wie RSA sie verschlüsselt und wieder entschlüsselt.

Rechenbeispiel — RSA-Verschlüsselung zum Ausprobieren

Privater Schlüssel (n, d)	1783

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — RSA-Verschlüsselung zum Ausprobieren

RSA ist eine Operation, zweimal verwendet. Verschlüsseln ist m^e mod n, Entschlüsseln c^d mod n — dieselbe modulare Exponentiation mit einem anderen Exponenten. Der Kniff besteht darin, das Paar so zu wählen, dass zweimalige Anwendung die Nachricht zurückgibt, während einer der Exponenten nichts über den anderen verrät. Alles, was das Feld druckt, ist die Suche nach diesem Paar. 1978 von Rivest, Shamir und Adleman veröffentlicht — und, wie erst mit der Freigabe durch die GCHQ 1997 bekannt wurde, vier Jahre zuvor von Clifford Cocks gefunden und in einer Schublade belassen.

Was die einzelnen Symbole bedeuten

n: der Modul, p·q. Öffentlich. Geheim sind seine Faktoren, nicht die Zahl selbst.
φ(n): die eulersche Phi-Funktion, (p−1)(q−1). Das Feld kann sie drucken, weil ihm p und q gegeben wurden; ein Angreifer mit nur n kann es nicht, und von n auf φ zu kommen ist so schwer wie das Faktorisieren.
e: der öffentliche Exponent. Jede zu φ(n) teilerfremde Zahl taugt — deshalb ändert er sich, wenn du eine Primzahl änderst.
d: der private Exponent, e⁻¹ mod φ(n). Ein einziges modulares Inverses — sofort berechnet, wenn du φ kennst, und das ganze Spiel, wenn nicht.

Woher die Formel kommt

Multipliziere die Primzahlen: n = p·q. Bei den Standardwerten 61 · 53 = 3233. Diese Zahl wird veröffentlicht. 61 und 53 aus 3233 zurückzugewinnen dauert von Hand einen Augenblick, und genau deshalb heißt das hier ehrlicherweise Spielzeug.
Berechne φ(n) = (p−1)(q−1) = 60 · 52 = 3120. Das ist der Angelpunkt des ganzen Verfahrens: n ist öffentlich, φ(n) nicht, und der einzige bekannte Weg vom einen zum anderen führt über die Faktorisierung.
Wähle e teilerfremd zu φ(n) und löse e·d ≡ 1 (mod φ(n)) nach d. Das Feld zeigt 7⁻¹ mod 3120 = 1783. Beachte, was dieser Schritt nicht ist: er ist nicht schwer. Bei bekanntem φ ist es ein einziges modulares Inverses. Die Geheimhaltung von d beruht vollständig auf der Geheimhaltung von φ.
Warum der Rundlauf klappt: nach Konstruktion ist e·d = 1 + kφ(n), also m^ed = m^1+kφ(n) ≡ m (mod n) — der Satz von Euler. Entschlüsseln ist keine getrennt erfundene Umkehroperation; es ist dieselbe Exponentiation mit dem Exponenten, der die erste rückgängig macht.

So liest du, was du siehst

Die Zeile, die es zu beobachten lohnt, ist e, denn sie ist keine Konstante. Bei den Standardprimzahlen steht dort 7; ändere p auf 67, und es wird 5. Der Grund steht in der Zeile darüber: e muss teilerfremd zu φ(n) sein, und φ ging von 3120 auf 3432. Vergleiche dann die beiden Exponenten auf dem Bildschirm — e = 7 gegen d = 1783. Der öffentliche ist winzig, der private nicht, und beides ist kein Zufall: e wird absichtlich klein gewählt, damit das Verschlüsseln billig ist, und d ist eben das, was das Inverse hergibt. Die letzte Zeile ist der Beweis, dass es funktioniert hat: m′ = 42, die Zahl, die du eingetippt hast.

Setzt voraus: Dass die Nachricht eine Zahl kleiner als n ist. Bei n = 3233 gibt es oberhalb von 3232 nichts zu verschlüsseln — deshalb verschlüsselt echtes RSA nie direkt eine Nachricht, sondern einen aufgefüllten symmetrischen Schlüssel von ein paar hundert Bit und überlässt den eigentlichen Text einem schnelleren Verfahren. Vorausgesetzt wird außerdem p ≠ q und dass du nie eine Primzahl in einem zweiten Modul wiederverwendest: zwei Module mit gemeinsamem Faktor sind beide durch einen einzigen größten gemeinsamen Teiler gebrochen.
Versagt, wenn: Du kannst diese Seite brechen, ohne irgendetwas zu faktorisieren. Setze p = 67, q = 53 und die Nachricht auf 3. Das Feld wählt e = 5 und druckt als Geheimtext 243 — und das ist schlicht 3⁵. Weil 3⁵ kleiner ist als n = 3551, hat die modulare Reduktion nie stattgefunden: der Geheimtext ist eine gewöhnliche Potenz, und die fünfte Wurzel aus 243 ist 3. Kein Schlüssel, kein Faktorisieren, Nachricht zurück. Probiere m = 5, und du erhältst 3125, also 5⁵; bei m = 8 übersteigt die Potenz endlich n, und der Geheimtext wird zu einem nutzlosen 809. Das ist kein Fehler dieser Seite — es ist der Grund, warum niemand eine nackte Zahl verschlüsselt. Echtes RSA füllt die Nachricht zuerst mit strukturiertem Zufall auf, was RFC 8017 festlegt und was aus einer Exponentiation erst ein Kryptosystem macht.

Der private Schlüssel wird abgeleitet, nicht gewählt 🖖

Sieh zu, wie das Panel d aufbaut. Mit den voreingestellten Primzahlen zeigt es φ(n) = 60 · 52 = 3120, weicht dann auf e = 7 aus – sein bevorzugtes 65537 ist hier größer als φ selbst – und berechnet schließlich d ≡ 7⁻¹ mod 3120 = 1783. Dieser letzte Schritt ist eine einzige modulare Inverse, auf jeder Maschine sofort erledigt. An d selbst ist nichts geheim: Es fällt direkt aus φ(n), und φ(n) fällt direkt aus p und q. RSA verbirgt also nicht den privaten Exponenten, sondern die Faktorisierung. Hier ist n = 3233, was ein Laptop zerlegt, bevor du diesen Satz zu Ende liest; ein RSA-2048-Modul hat 617 Dezimalstellen, und alle Schritte auf dem Bildschirm sind sonst dieselben.

Das Schloss, das nur du öffnest 🖖

RSA gibt jedem ein offenes Vorhängeschloss (deinen öffentlichen Schlüssel), das man um eine Nachricht zuschnappen lassen kann, aber nur dein privater Schlüssel öffnet es wieder. Weil Verschließen und Öffnen verschiedene Schlüssel nutzen, kannst du den öffentlichen für alle sichtbar veröffentlichen, ohne zu verraten, wie man entschlüsselt. Dieses Werkzeug lässt dich den ganzen Zyklus mit winzigen Primzahlen durchspielen; echte Systeme nutzen dieselben Schritte mit Zahlen von Hunderten Stellen.

Verschlüsselung rückwärts ist eine Signatur 🖖

Dieselbe RSA-Operation, in umgekehrter Richtung ausgeführt, beweist, wer eine Nachricht gesendet hat, statt sie zu verbergen. Wenn du eine Nachricht mit deinem privaten Schlüssel „entschlüsselst", kann sie jeder mit deinem öffentlichen Schlüssel wieder „verschlüsseln", um zu prüfen, dass sie wirklich von dir stammt - das ist eine digitale Signatur. So treibt eine einzige Rechnung sowohl Vertraulichkeit als auch Authentifizierung an, nur indem man tauscht, welcher Schlüssel zuerst kommt.

Aufgaben vollständig gelöst

Ein RSA-Schlüsselpaar für p = 61 und q = 53 5 Schritte
Erzeugen Sie das RSA-Schlüsselpaar für p = 61 und q = 53, und verschlüsseln Sie m = 42. Jede nachstehende Zahl ergibt sich aus diesen dreien, einschließlich des öffentlichen Exponenten.
1. Der Modul wird veröffentlicht und der Totient verworfen, doch beide sind nur eine Multiplikation von den Primzahlen entfernt. φ(n) zählt die ganzen Zahlen unterhalb von n, die teilerfremd zu n sind, was für ein Produkt zweier verschiedener Primzahlen (p − 1)(q − 1) ist.
  
  $n = 61 \cdot 53 = 3233, ϕ (n) = (61 - 1) (53 - 1) = 60 \cdot 52 = 3120$
2. Der öffentliche Exponent muss modulo φ invertierbar sein, was bedeutet, dass er teilerfremd zu φ ist. Faktorisieren wir φ, scheiden die kleinen Kandidaten aus, sodass 7 als kleinster verfügbarer ungerader Exponent übrig bleibt. Reale Schlüssel verwenden 65537, aber das ist größer als dieses φ, weshalb das Werkzeug auf die kleinste teilerfremde Zahl zurückgreift.
  
  $3120 = 2^{4} \cdot 3 \cdot 5 \cdot 13 ⟹ g cd (3, ϕ) = 3, g cd (5, ϕ) = 5, g cd (7, ϕ) = 1 ⟹ e = 7$
3. Das Invertieren von 7 modulo 3120 ist der erweiterte euklidische Algorithmus und nichts weiter. Drei Divisionen führen zu einem Rest von 1, und das Rückwärtsauflösen derselben drei Zeilen schreibt diese 1 als Kombination von 3120 und 7.
  
  $3120 = 445 \cdot 7 + 5, 7 = 1 \cdot 5 + 2, 5 = 2 \cdot 2 + 1 ⟹ 1 = 3 \cdot 3120 - 1337 \cdot 7$
4. Der Koeffizient von 7 in dieser Kombination ist negativ, und ein negatives Inverses wird positiv gemacht, indem man den Modul einmal addiert. Die Verschlüsselung ist dann eine einzige modulare Exponentiation, die durch zweimaliges Quadrieren anstatt durch siebenmaliges Multiplizieren von 42 mit sich selbst durchgeführt wird.
  
  $d \equiv - 1337 \equiv 1783 (mod 3120), c = 4 2^{4} \cdot 4 2^{2} \cdot 42 = 1550 \cdot 1764 \cdot 42 \equiv 240 (mod 3233)$
5. Die Entschlüsselung muss niemals durch Brute-Force überprüft werden, und bei realistischen Schlüssellängen wäre dies auch gar nicht möglich. Die beiden Exponenten wurden so konstruiert, dass ihr Produkt um eins größer als ein Vielfaches von φ ist, und der Satz von Euler schließt dies für jedes zu n teilerfremde m ab — was auf 42 zutrifft.
  
  $e d = 7 \cdot 1783 = 12481 = 4 \cdot 3120 + 1 ⟹ c^{d} \equiv m^{e d} = m (m^{ϕ})^{4} \equiv m = 42$
Antwort

Das Werkzeug gibt n = 3233, φ = 3120, d = 1783 und c = 240 aus und bestätigt, dass 240 wieder zu 42 entschlüsselt wird. Der merkenswerte Teil ist, was φ eigentlich ist. Es ist kein zweites Geheimnis, das neben p und q steht — es ist dasselbe Geheimnis, nur anders geschrieben. Gegeben n und φ erhält man p + q = n − φ + 1 = 114 und pq = 3233, eine quadratische Gleichung, deren Diskriminante eine perfekte Quadratzahl ist, und sie liefert in einer einzigen Zeile 61 und 53 zurück. Ein Schlüsselgenerator, der φ preisgibt, hat also die Faktorisierung genauso vollständig preisgegeben, als hätte er die Primzahlen ausgegeben. Deshalb wird φ einmal berechnet, zur Bestimmung von d verwendet und danach verworfen.

$p + q = n - ϕ + 1 = 114, pq = 3233 ⟹ x^{2} - 114 x + 3233 = 0 ⟹ x = 61, 53$
Faktorisierung von 3233 in 61 × 53 zur Überwindung der RSA-Sicherheit 6 Schritte
Die Tafel zerlegt 3233 in 61 × 53, noch bevor du die Seite zu Ende gelesen hast. Genau diese Zerlegung ist die gesamte Sicherheit von RSA, anscheinend im Handumdrehen gebrochen. Rechne aus, was dasselbe Problem eine Schlüsselgröße weiter unmöglich macht.
1. Die beiden Zahlen, bei denen die Tafel beginnt: der Modul und die Totientenfunktion, die aus den beiden Primzahlen folgt.
  
  $n = 61 \times 53 = 3233, ϕ (n) = 60 \times 52 = 3120$
2. Ein Angreifer braucht nur eine Tatsache: die kleinere Primzahl kann die Wurzel des Moduls nicht überschreiten. Alles Größere bräuchte einen Partner, der kleiner ist als es selbst.
  
  $p \leq n ⟹ 3233 = 56.86, π (56) = 16$
3. Die Suche läuft also über die Primzahlen bis 56, und davon gibt es sechzehn. Die sechzehnte ist 53. Sechzehn Divisionen sind keine Sicherheit, das ist ein Rundungsfehler.
  
  $53 < 56.86 \in {2, 3, 5, \dots, 53} ⟹ k \leq 16$
4. Setze nun einen Modul ein, den tatsächlich jemand benutzt. 2048 Bit heißt n nahe 2²⁰⁴⁸, und die Wurzel daraus ist 2¹⁰²⁴, etwa 10³⁰⁸.
  
  $n \approx 2^{2048} ⟹ n = 2^{1024} \approx 1 0^{308}$
5. Rechne den Preis aus. Bei einer Milliarde Probedivisionen pro Sekunde sind das 10²⁹⁹ Sekunden — gegen ein Universum von rund 4 × 10¹⁷ Sekunden.
  
  $\frac{1 0 ^{308}}{1 0 ^{9} s ^{- 1}} = 1 0^{299} s \approx 1 0^{291} yr$
6. Zeit ist für eine Zahl dieser Größe die falsche Einheit; vergleiche sie lieber mit etwas Physischem.
  
  $1 0^{308} ⋙ 1 0^{80}$
Antwort

Sechzehn Divisionen gegenüber 10³⁰⁸. Da 10³⁰⁸ das 10²²⁸-Fache der Anzahl der Atome im beobachtbaren Universum ist, könntest du den Zähler nicht einmal speichern. Entscheidend ist eher die Form als die Größe: Der Aufwand des Angreifers wächst mit √n, während der Schlüssel mit log n wächst. Jeweils zwei zusätzliche Bits im Schlüssel verdoppeln also den Aufwand für das Knacken und kosten den Verteidiger zwei Bits. Diese Asymmetrie ist der Kern der Sache. Dass das Werkzeug sofort eine Antwort liefert, ist kein Fehler in der Demonstration – es ist die Demonstration, denn 3233 zeigt, wie ein Modul aussieht, wenn der Asymmetrie kein Raum zum Wirken gegeben wurde.

$16 ⟷ 1 0^{308}; O (n), n = 2^{2048}$

Quellen (4)

The idea RSA is an instance of — public keys, two years earlier: W. Diffie & M. Hellman, "New directions in cryptography." IEEE Transactions on Information Theory 22(6), 644–654, 1976.
What real RSA wraps round the message, and why the bare exponentiation on this page is not a cryptosystem: K. Moriarty (Ed.), B. Kaliski, J. Jonsson & A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2." RFC 8017, November 2016 — RSAES-OAEP in §7.1.
The scheme the tool walks through, including e·d ≡ 1 mod φ(n): R. L. Rivest, A. Shamir and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems." Communications of the ACM 21(2), 120–126, 1978.
Why the security rests on factoring rather than on hiding d: A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, §8.2. CRC Press, 1996. ISBN 978-0-8493-8523-0.

Vom 42Math-Team · Aktualisiert 2026-08-17

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

p=61, q=53 - p=61, q=53: klassisches Lehrbuch-RSA
Kleine Primzahlen - p=7, q=11: winzige Primzahlen, leicht nachzuvollziehen
Größere Primzahlen - p=101, q=103: größerer Schlüsselraum
Lehrbuchbeispiel - p=17, q=19: Lehrbuchaufgabe