RSA (Rivest-Shamir-Adleman): Funktionsweise, Schlüssel & Sicherheit

RSA erklärt: Funktionsweise, Erstellung öffentlicher & privater Schlüssel, Sicherheit gegen Primfaktorzerlegung und praktische Tipps für sicheren Einsatz.

Autor: Leandro Alegsa

11-03-2026 22:23

RSA (Rivest-Shamir-Adleman) ist ein Algorithmus, der von modernen Computern zur Ver- und Entschlüsselung von Nachrichten verwendet wird. Es ist ein asymmetrischer kryptographischer Algorithmus. Asymmetrisch bedeutet, dass es zwei verschiedene Schlüssel gibt. Dies wird auch als Kryptographie mit öffentlichem Schlüssel bezeichnet, da einer der Schlüssel an jeden weitergegeben werden kann. Der andere Schlüssel muss privat gehalten werden. Der Algorithmus beruht auf der Tatsache, dass es schwierig ist, die Faktoren einer großen zusammengesetzten Zahl zu finden: Wenn die Faktoren Primzahlen sind, nennt man das Problem Primfaktorzerlegung. Es handelt sich auch um einen Schlüsselpaar-Generator (öffentlicher und privater Schlüssel).

Funktionsweise — grober Überblick

RSA beruht auf einfachen mathematischen Operationen mit großen ganzen Zahlen (Multiplikation, Potenzen modulo n) kombiniert mit dem praktischen Schwierigkeitsgrad, aus dem Produkt zweier großer Primzahlen wieder die Primfaktoren zu bestimmen. Die wichtigsten Schritte sind:

Erzeugung von zwei großen Zufallsprimzahlen p und q.
Berechnung des Moduls n = p · q, das Teil des öffentlichen Schlüssels ist.
Bildung eines Exponenten e (öffentlich) und seines modularen Inversen d (privat), so dass e·d ≡ 1 (mod φ(n)), wobei φ(n) = (p−1)(q−1) die Eulersche Phi-Funktion ist.
Verschlüsselung eines Klartextes m durch c ≡ m^e mod n und Entschlüsselung durch m ≡ c^d mod n.

Schlüsselgenerierung — detaillierter

Wähle zwei unabhängige große Primzahlen p und q (gleich große Bitlänge empfohlen) und berechne n = p·q.
Berechne φ(n) = (p − 1)(q − 1).
Wähle einen öffentlichen Exponenten e mit 1 < e < φ(n) und gcd(e, φ(n)) = 1. Häufiger Standardwert ist e = 65537 (schnell und sicher in den meisten Fällen).
Berechne den privaten Exponenten d als das multiplikative Inverse von e modulo φ(n): d ≡ e⁻¹ (mod φ(n)).
Der öffentliche Schlüssel ist (n, e); der private Schlüssel ist (n, d) — in der Praxis werden aber zusätzlich p, q, dp = d mod (p−1), dq = d mod (q−1) und qinv = q⁻¹ mod p gespeichert, um Entschlüsselung mit dem chinesischen Restsatz (CRT) deutlich zu beschleunigen.

Verschlüsselung, Entschlüsselung und Signaturen

Verschlüsselung: c = m^e mod n, wobei m der Klartext (als Zahl) und c der Chiffretext ist. Wichtig: m muss 0 ≤ m < n sein; in der Praxis nutzt man Padding und/oder hybrid Verfahren (siehe unten).
Entschlüsselung: m = c^d mod n.
Digitale Signatur: Signieren geschieht analog zur Entschlüsselung: s = H(m)^d mod n (H = Hashfunktion plus Padding). Verifizieren: H(m) ?= s^e mod n.

Padding und sichere Verwendung

Textbuch-RSA (direkt m^e mod n) ist unsicher. Deshalb gibt es standardisierte Padding-Schemata:

OAEP (Optimal Asymmetric Encryption Padding) für sichere Verschlüsselung — verhindert malleability und chosen-ciphertext-Angriffe.
PSS (Probabilistic Signature Scheme) für sichere Signaturen — empfohlen gegenüber einfachen Hash-then-RSA-Methoden.

In der Praxis wird RSA meist nicht zum direkten Verschlüsseln großer Daten benutzt. Stattdessen wird ein symmetrischer Sitzungsschlüssel (z. B. für AES) erzeugt, dieser mit RSA verschlüsselt und die eigentlichen Daten mit dem schnellen symmetrischen Algorithmus verschlüsselt (hybrides Verschlüsselungsverfahren).

Sicherheit — Bedrohungen und Grenzen

Grundlage der Sicherheit: Schwierigkeit der Faktorisierung großer Zahlen. Die beste klassische Methode ist der General Number Field Sieve (GNFS) mit subexponentieller Laufzeit; deshalb müssen RSA-Moduli ausreichend groß sein.
Empfohlene Schlüsselgrößen (Stand 2020er Jahre und abhängig von gewünschter Lebensdauer): mindestens 2048 Bit; für langfristigen Schutz oft 3072 Bit oder 4096 Bit. 1024 Bit gilt heute als unsicher.
Quantencomputer: Mit ausreichend großen, fehlerkorrigierten Quantenrechnern würde Shor’s Algorithmus Faktorisierung in polynomieller Zeit ermöglichen — RSA wäre dann gebrochen. Deshalb arbeitet man an post-quantensicheren Alternativen.
Implementationsangriffe: Seitenkanalangriffe (Timing, Power, EM), Padding-Oracle-Angriffe (z. B. Bleichenbacher-Attacke) und fehlerhafte Zufallszahlengeneratoren sind häufigere praktische Schwachstellen als die Mathematik selbst.
Sichere Implementierungsempfehlungen: konstante Zeit, Schutz gegen Seitenkanäle, sichere Randomquelle für Primzahlerzeugung, Prüfung auf gleiche p=q, sichere Entsorgung privater Schlüssel.

Praktische Empfehlungen

Verwende aktuelle Bibliotheken (OpenSSL, libsodium, BouncyCastle etc.) und vertraue bewährten Implementierungen statt Eigenbau.
Nutze standardisierte Padding-Schemata: OAEP für Verschlüsselung und PSS für Signaturen.
Verwende RSA hauptsächlich für Schlüsselvereinbarung (hybride Verfahren), nicht für große Datenmengen.
Sichere Aufbewahrung des privaten Schlüssels (Hardware-Sicherheitsmodule, TPMs, Smartcards) und Schutz vor Seitenkanalangriffen.
Wähle ausreichend große Schlüssel (mind. 2048 Bit) und plane für die Migration zu post-quantensicheren Algorithmen, falls Langzeitsicherheit erforderlich ist.

Häufige Anwendungen

SSL/TLS (Aushandlung von Sitzungsschlüsseln), obwohl immer mehr Verbindungen auf elliptische Kurven (ECDHE) oder PQ-Verfahren umsteigen.
S/MIME, PGP (E-Mail-Verschlüsselung und Signatur) — oft kombiniert mit Hybridverschlüsselung.
Code-Signierung, Authentifizierung und digitale Zertifikate (PKI).

Kurzbeispiel (vereinfachte Darstellung)

Angenommen p = 61, q = 53 → n = 3233, φ(n) = 3120. Wähle e = 17 (gcd(17,3120)=1). Dann berechne d = 2753 (17·2753 ≡ 1 mod 3120).
Verschlüssele m = 65: c = 65¹⁷ mod 3233 = 2790. Entschlüssele: m = 2790²⁷⁵³ mod 3233 = 65.

Hinweis: Das obige Beispiel dient nur zur Illustration mit sehr kleinen Zahlen. In der Praxis verwendet man Primzahlen mit Hunderten bis Tausenden Bits Länge.

Fazit

RSA ist ein grundlegender, weit verbreiteter asymmetrischer Algorithmus, dessen Sicherheit auf der Schwierigkeit der Faktorisierung großer Zahlen beruht. Richtig eingesetzt (ausreichende Schlüssellänge, sicheres Padding, bewährte Implementationen und Schutz gegen Seitenkanäle) ist RSA weiterhin sicher für viele Anwendungen. Langfristig werden jedoch post-quantensichere Algorithmen wichtig werden, sobald Quantenhardware praktisch genug ist.

Nachricht verschlüsseln

Alice gibt ihren öffentlichen Schlüssel ( n {\displaystyle n\,} $n\,$ & e {\displaystyle e\,} ) an $e\,$ Bob und hält ihren privaten Schlüssel geheim. Bob möchte Nachricht M an Alice senden.

Zuerst verwandelt er M in eine Zahl m {\Darstellungsstil m} kleiner als n {\Darstellungsstil n}, indem er ein vereinbartes reversibles Protokoll verwendet, das als Padding-Schema bekannt ist. Dann berechnet er den $c\,$ entsprechenden Chiffretext c {\Darstellungsstil c\,}:

c = m e mod n {\darstellungsstil c=m^{e}\mod {n}} $c=m^{e}\mod {n}$

Dies kann mit der Methode der Potenzierung durch Quadrierung schnell erreicht werden. Bob sendet dann c {\Anzeigestil c\,} $c\,$ an Alice.

Nachricht entschlüsseln

Alice kann m {\Anzeigestil m\,} $m\,$ von c {\Anzeigestil c\,} wiederherstellen $c\,$ , indem sie ihren privaten Schlüssel d {\Anzeigestil d\,} $d\,$ im folgenden Verfahren verwendet:

m = c d mod n {\Anzeigestil m=c^{d}{\bmod {n}}} $m=c^{d}{\bmod {n}}$

Bei einem m {\Darstellungsstil m\,} $m\,$ kann sie die ursprünglichen unterschiedlichen Primzahlen wiederherstellen, indem sie das chinesische Restsatz-Theorem auf diese beiden Kongruenzen anwendet

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}} $m^{ed}\equiv m{\bmod {pq}}$ .

Also,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} $c^{d}\equiv m{\bmod {n}}$ .

Ein funktionierendes Beispiel

Hier ist ein Beispiel für RSA-Verschlüsselung und -Entschlüsselung. Die hier verwendeten Parameter sind künstlich klein, aber Sie können auch OpenSSL verwenden, um ein echtes Schlüsselpaar zu erzeugen und zu untersuchen.

Wählen Sie zwei zufällige Primzahlen.
p = 61 {\Darstellungsstil p=61} $p=61$ und q = 53 ; {\Darstellungsstil q=53;} $q=53;$ Berechnen n = p q {\Anzeigestil n=pq\,} $n=pq\,$
n = 61 ∗ 53 = 3233 {\Anzeigestil n=61*53=3233} $n=61*53=3233$
Berechnen Sie den Totienten ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\darstellungsstil \phi (n)=(p-1)(q-1)\,} $\phi (n)=(p-1)(q-1)\,$
: ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120} $\phi (n)=(61-1)(53-1)=3120$
Wählen Sie e > 1 {\darstellungsstil e>1} coprime $e>1$ bis 3120
: e = 17 {\darstellungsstil e=17} $e=17$
Wählen Sie d {\displaystyle d\,} $d\,$ um d e mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\bmod {\phi (n)}}\equiv 1\,} $de{\bmod {\phi (n)}}\equiv 1\,$
d = 2753 {\Anzeigestil d=2753} $d=2753$
: 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\darstellungsart 17*2753=46801=1+15*3120} $17*2753=46801=1+15*3120$ .

Der öffentliche Schlüssel lautet ( n = 3233 {\Anzeigestil n=3233} $n=3233$ , e = 17 {\Anzeigestil e=17} $e=17$ ). Für eine aufgefüllte Nachricht m {\displaystyle m\,} $m\,$ $c=m^{e}{\bmod {n}}$ wird die Verschlüsselungsfunktion c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}}}:

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}}233\,} $c=m^{17}{\bmod {3}}233\,$

Der private Schlüssel lautet ( n = 3233 {\Anzeigestil n=3233} $n=3233$ , d = 2753 {\Anzeigestil d=2753} $d=2753$ ). Die Entschlüsselungsfunktion m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}}} $m=c^{d}{\bmod {n}}$ wird zu ( m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}}:

m = c 2753 mod 3 233 {\darstellungsstil m=c^{2753}{\bmod {3}}}233\,} $m=c^{2753}{\bmod {3}}233\,$

Zum
Beispiel, um m = 123 zu verschlüsseln {\Anzeigestil m=123} $m=123$ berechnen wir

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855} $c=123^{17}{\bmod {3}}233=855$

So entschlüsseln Sie c = 855 {\Darstellungsstil c=855} $c=855$ berechnen wir

m = 855 2753 mod 3 233 = 123 {\Anzeigestil m=855^{2753}{\bmod {3}}}233=123} $m=855^{2753}{\bmod {3}}233=123$

Beide dieser Berechnungen können effizient mit dem Quadrat-und-vielfach-Algorithmus für modulare Potenzierung berechnet werden [de].

Ableitung der RSA-Gleichung aus dem Euler'schen Satz

Die RSA lässt sich leicht mit Hilfe des Euler-Theorems und der Euler-Totientenfunktion ableiten.

Beginnend mit dem Eulerschen Satz,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}} $m^{\phi (n)}\equiv 1{\pmod {n}}$

müssen wir zeigen, dass die Entschlüsselung einer verschlüsselten Nachricht mit dem richtigen Schlüssel die ursprüngliche Nachricht ergibt. Bei einer aufgefüllten Nachricht m wird der Geheimtext c berechnet durch

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}} $c\equiv m^{e}{\pmod {n}}$

In den Entschlüsselungsalgorithmus haben wir

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}} $c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}$

Wir wollen zeigen, dass dieser Wert auch kongruent zu m ist. Die Werte von e und d wurden zur Sättigung gewählt,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}} $ed\equiv 1{\pmod {\phi (n)}}$

Das heißt, es existiert eine ganze Zahl k, so dass

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1} $ed=k\times \phi (n)+1$

Nun ersetzen wir in die verschlüsselte und dann entschlüsselte Nachricht,

m e d ≡ m k k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\Anzeigestil {\begin{ausgerichtet}m^{ed}&\äquivalent m^{k\phi (n)+1}\\&\äquivalent m\mal m^{k\phi (n)}\\&\äquivalent m\mal \links (m^{\phi (n)}\rechts)^{k}{\pmod {n}\end{ausgerichtet}} ${\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}$

Wir wenden das Eulersche Theorem an und erzielen das Ergebnis.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}} $m\times (1)^{k}\equiv m{\pmod {n}}$

Polsterungen

Wenn RSA in der Praxis verwendet wird, muss es mit einer Form von Füllschema kombiniert werden, so dass keine Werte von M zu unsicheren Chiffriertexten führen. Die Verwendung von RSA ohne Füllung kann einige Probleme verursachen:

Die Werte m = 0 oder m = 1 ergeben aufgrund der Eigenschaften der Potenzierung immer Chiffretexte, die gleich 0 bzw. 1 sind.
Bei der Verschlüsselung mit kleinen Verschlüsselungsexponenten (z.B. e = 3) und kleinen Werten von m kann das (nichtmodulare) Ergebnis von m e {\Darstellungsstil m^{e}} $m^{e}$ strikt kleiner sein als der Modulus n. In diesem Fall können Chiffriertexte leicht entschlüsselt werden, indem die eth-Wurzel des Chiffriertextes ohne Rücksicht auf den Modulus genommen wird.
Die RSA-Verschlüsselung ist ein deterministischer Verschlüsselungsalgorithmus. Er hat keine Zufallskomponente. Daher kann ein Angreifer einen ausgewählten Klartextangriff gegen das Kryptosystem erfolgreich starten. Er kann ein Wörterbuch erstellen, indem er wahrscheinliche Klartexte unter dem öffentlichen Schlüssel verschlüsselt und die resultierenden Chiffriertexte speichert. Der Angreifer kann dann den Kommunikationskanal beobachten. Sobald sie Chiffriertexte sehen, die mit denen in ihrem Wörterbuch übereinstimmen, können die Angreifer dann dieses Wörterbuch benutzen, um den Inhalt der Nachricht zu erfahren.

In der Praxis können die ersten beiden Probleme auftreten, wenn kurze ASCII-Nachrichten gesendet werden. In solchen Nachrichten kann m die Verkettung eines oder mehrerer ASCII-kodierter Zeichen sein. Eine Nachricht, die aus einem einzelnen ASCII-NUL-Zeichen (dessen numerischer Wert 0 ist) besteht, würde als m = 0 kodiert werden, was einen Chiffriertext von 0 ergibt, unabhängig davon, welche Werte von e und N verwendet werden. Ebenso würde ein einzelnes ASCII SOH (dessen numerischer Wert 1 ist) immer einen Chiffriertext von 1 ergeben. Bei Systemen, die konventionell kleine Werte von e verwenden, wie z.B. 3, wären alle ASCII-Einzelzeichen-Nachrichten, die nach diesem Schema kodiert werden, unsicher, da das größte m einen Wert von 255 hätte und 2553 kleiner als jeder vernünftige Modulus ist. Solche Klartexte könnten wiederhergestellt werden, indem man einfach die Würfelwurzel des Chiffriertextes nimmt.

Um diese Probleme zu vermeiden, betten praktische RSA-Implementierungen typischerweise irgendeine Form von strukturiertem, randomisiertem Auffüllen in den Wert m ein, bevor er verschlüsselt wird. Dieses Auffüllen stellt sicher, dass m nicht in den Bereich unsicherer Klartexte fällt und dass eine gegebene Nachricht, sobald sie aufgefüllt ist, zu einem aus einer großen Anzahl verschiedener möglicher Chiffriertexte verschlüsselt wird. Die letztgenannte Eigenschaft kann die Kosten eines Wörterbuchangriffs über die Möglichkeiten eines vernünftigen Angreifers hinaus erhöhen.

Standards wie PKCS wurden sorgfältig entwickelt, um Nachrichten vor der RSA-Verschlüsselung sicher aufzufüllen. Da diese Schemata den Klartext m mit einer gewissen Anzahl von zusätzlichen Bits auffüllen, muss die Größe der nicht aufgefüllten Nachricht M etwas kleiner sein. RSA-Polsterungsschemata müssen sorgfältig entworfen werden, um ausgeklügelte Angriffe zu verhindern. Dies kann durch eine vorhersehbare Nachrichtenstruktur erleichtert werden. Frühe Versionen des PKCS-Standards verwendeten Ad-hoc-Konstruktionen, die sich später als anfällig für einen praktisch adaptiv gewählten Chiffretextangriff erwiesen. Moderne Konstruktionen verwenden sichere Techniken wie das Optimal Asymmetric Encryption Padding (OAEP), um Nachrichten zu schützen und gleichzeitig diese Angriffe zu verhindern. Der PKCS-Standard verfügt auch über Verarbeitungsschemata, die zusätzliche Sicherheit für RSA-Signaturen bieten sollen, z.B. das Probabilistische Signaturschema für RSA (RSA-PSS).

Signieren von Nachrichten

Angenommen, Alice verwendet Bobs öffentlichen Schlüssel, um ihm eine verschlüsselte Nachricht zu senden. In der Nachricht kann sie behaupten, Alice zu sein, aber Bob hat keine Möglichkeit, zu überprüfen, ob die Nachricht tatsächlich von Alice stammt, da jeder Bobs öffentlichen Schlüssel verwenden kann, um ihm verschlüsselte Nachrichten zu senden. Um also die Herkunft einer Nachricht zu verifizieren, kann RSA auch zum Signieren einer Nachricht verwendet werden.

Angenommen, Alice möchte Bob eine unterschriebene Nachricht schicken. Sie erzeugt einen Hash-Wert der Nachricht, erhöht ihn auf die Potenz von d mod n (genau wie beim Entschlüsseln einer Nachricht) und hängt ihn als "Signatur" an die Nachricht an. Wenn Bob die signierte Nachricht empfängt, setzt er die Signatur in die Potenz von e mod n (genau wie beim Verschlüsseln einer Nachricht) und vergleicht den resultierenden Hash-Wert mit dem tatsächlichen Hash-Wert der Nachricht. Wenn beide übereinstimmen, weiß er, dass der Verfasser der Nachricht im Besitz von Alices geheimem Schlüssel war und dass die Nachricht seitdem nicht mehr manipuliert wurde.

Beachten Sie, dass sichere Auffüllschemata wie RSA-PSS für die Sicherheit der Nachrichtensignierung ebenso wichtig sind wie für die Nachrichtenverschlüsselung, und dass niemals derselbe Schlüssel sowohl für Verschlüsselungs- als auch für Signierzwecke verwendet werden sollte.

Fragen und Antworten

F: Was ist RSA?

A: RSA (Rivest-Shamir-Adleman) ist ein Algorithmus, der von modernen Computern verwendet wird, um Nachrichten zu ver- und entschlüsseln. Es handelt sich um einen asymmetrischen kryptographischen Algorithmus.

F: Was bedeutet asymmetrisch?

A: Asymmetrisch bedeutet, dass es zwei verschiedene Schlüssel gibt - einen öffentlichen Schlüssel und einen privaten Schlüssel.

F: Was ist die Grundlage des RSA-Algorithmus?

A: Der Algorithmus basiert auf der Tatsache, dass es schwierig ist, die Faktoren einer großen zusammengesetzten Zahl zu finden - wenn die Faktoren Primzahlen sind, wird dieses Problem Primfaktorisierung genannt.

F: Wie funktioniert RSA?

A: RSA besteht aus einem öffentlichen Schlüssel und einem privaten Schlüssel. Der öffentliche Schlüssel kann jedem bekannt sein - er wird zur Verschlüsselung von Nachrichten verwendet. Nachrichten, die mit dem öffentlichen Schlüssel verschlüsselt wurden, können nur mit dem privaten Schlüssel entschlüsselt werden, der geheim gehalten werden muss. Die Berechnung des privaten Schlüssels anhand des öffentlichen Schlüssels ist sehr schwierig.

F: Gibt es eine andere Bezeichnung für diese Art der Kryptographie?

A: Diese Art der Kryptographie wird auch als Public-Key-Kryptographie bezeichnet, da einer der Schlüssel an jeden weitergegeben werden kann, während der andere geheim gehalten wird.

F: Wird bei RSA ein Schlüsselpaar erzeugt?

A: Ja, RSA generiert ein Schlüsselpaar - einen öffentlichen und einen privaten Schlüssel -, die für die Verschlüsselung bzw. Entschlüsselung verwendet werden.

Suche in der Enzyklopädie