RSA: Unterschied zwischen den Versionen
Der Seiteninhalt wurde durch einen anderen Text ersetzt: „'''RSA''' ('''Rivest–Shamir–Adleman''') ist ein asymmetrisches kryptographisches Verfahren, das sowohl zum Verschlüsseln als auch zum digitalen Signieren verwendet werden kann. Es verwendet ein Schlüsselpaar, bestehend aus einem privaten Schlüssel, der zum Entschlüsselung#Entschlüsselung in der Kryptologie|Entschlü…“ Markierung: Ersetzt |
Keine Bearbeitungszusammenfassung |
||
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
'''RSA''' ('''Rivest–Shamir–Adleman''') ist ein [[Asymmetrisches Kryptosystem|asymmetrisches kryptographisches Verfahren]], das sowohl zum [[Verschlüsselung|Verschlüsseln]] als auch zum [[Digitale Signatur|digitalen Signieren]] verwendet werden kann. Es verwendet ein Schlüsselpaar, bestehend aus einem privaten [[Schlüssel (Kryptologie)|Schlüssel]], der zum [[Entschlüsselung#Entschlüsselung in der Kryptologie|Entschlüsseln]] oder Signieren von Daten verwendet wird, und einem öffentlichen Schlüssel, mit dem man verschlüsselt oder Signaturen prüft. Der private Schlüssel wird geheim gehalten und kann nicht mit realistischem Aufwand aus dem öffentlichen Schlüssel berechnet werden. | '''RSA''' ('''Rivest–Shamir–Adleman''') ist ein [[Asymmetrisches Kryptosystem|asymmetrisches kryptographisches Verfahren]], das sowohl zum [[Verschlüsselung|Verschlüsseln]] als auch zum [[Digitale Signatur|digitalen Signieren]] verwendet werden kann. Es verwendet ein Schlüsselpaar, bestehend aus einem privaten [[Schlüssel (Kryptologie)|Schlüssel]], der zum [[Entschlüsselung#Entschlüsselung in der Kryptologie|Entschlüsseln]] oder Signieren von Daten verwendet wird, und einem öffentlichen Schlüssel, mit dem man verschlüsselt oder Signaturen prüft. Der private Schlüssel wird geheim gehalten und kann nicht mit realistischem Aufwand aus dem öffentlichen Schlüssel berechnet werden. | ||
== Verfahren == | |||
Das Verfahren ist mit dem [[Rabin-Verschlüsselungsverfahren]] verwandt. Da es deterministisch arbeitet, ist es unter Umständen für bestimmte Angriffe anfällig. In der Praxis wird RSA daher mit dem [[Optimal Asymmetric Encryption Padding]] kombiniert. | |||
=== Einwegfunktionen === | |||
[[Einwegfunktion]] | |||
[[Funktion (Mathematik)|Funktionen]], bei denen eine Richtung leicht, die andere (Umkehrfunktion) schwierig zu berechnen ist, bezeichnet man als ''[[Einwegfunktion]]en'' ([[Englische Sprache|engl.]] ''one-way function''). Beispielsweise ist nach aktuellem Wissensstand die [[Faktorisierungsverfahren|Faktorisierung]] einer großen Zahl, also ihre Zerlegung in ihre Primfaktoren, sehr aufwändig, während das Erzeugen einer Zahl durch [[Multiplikation]] von Primzahlen recht einfach und schnell möglich ist. Spezielle Einwegfunktionen sind [[Einwegfunktion#Einwegfunktionen mit Falltür (Trapdoor-Einwegfunktionen)|Falltürfunktionen]] (engl. ''trapdoor one-way function''), die mit Hilfe einer Zusatzinformation auch rückwärts leicht zu berechnen sind. | |||
Die Verschlüsselung und die Signatur mit RSA basieren auf einer Einwegpermutation mit Falltür (engl. ''trapdoor one-way permutation'', kurz ''TOWP''), einer Falltürfunktion, die gleichzeitig [[Bijektive Funktion|bijektiv]], also eine [[Permutation]], ist. Die Einwegeigenschaft begründet, warum die Entschlüsselung (bzw. das Signieren) ohne den geheimen Schlüssel (die Falltür) schwierig ist. | |||
=== Erzeugung des öffentlichen und privaten Schlüssels === | |||
Die Schlüssel bestehen aus den drei Zahlen <math>e, d</math> und <math>N</math>. Man nennt <math>N</math> den ''RSA-[[Division mit Rest#Modulo|Modul]]'', <math>e</math> den ''Verschlüsselungsexponenten'' und <math>d</math> den ''Entschlüsselungsexponenten''. Das [[Tupel|Zahlenpaar]] <math>(e,N)</math> bildet den [[Öffentlicher Schlüssel|öffentlichen Schlüssel]] (public key) und das Paar <math>(d,N)</math> den [[Geheimer Schlüssel|privaten Schlüssel]] (private key). Diese Zahlen werden durch das folgende Verfahren erzeugt: | |||
# Wähle zufällig und [[Stochastisch unabhängige Ereignisse|stochastisch unabhängig]] zwei [[Primzahl]]en <math>p \neq q</math>. Diese sollen die gleiche Größenordnung haben, aber nicht zu dicht beieinander liegen, sodass der folgende Rahmen ungefähr eingehalten wird: <math>0{,}1<|\log_2 p -\log_2 q|<30</math>. (In der Praxis erzeugt man dazu solange Zahlen der gewünschten Länge und führt mit diesen anschließend einen [[Primzahltest]] durch, bis man zwei Primzahlen gefunden hat.) | |||
# Berechne den RSA-[[Division mit Rest#Modulo|Modul]] | |||
#: <math>N = p \cdot q</math> | |||
# Berechne die [[Eulersche φ-Funktion#Berechnung|Eulersche φ-Funktion]] von <math>N</math> | |||
#:<math>\varphi(N) = (p-1) \cdot (q-1)</math> | |||
# Wähle eine zu <math>\varphi(N)</math> [[Teilerfremdheit|teilerfremde]] Zahl <math>e</math>, für die gilt <math>1 < e < \varphi(N)-1</math>. | |||
# Berechne den Entschlüsselungsexponenten <math>d</math> als [[Inverses Element#Multiplikativ Inverses|multiplikativ Inverses]] von <math>e</math> bezüglich des [[Division mit Rest|Moduls]] <math>\varphi(N)</math>, was mit dem [[Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus]] erfolgen kann. Es soll also die [[Kongruenz (Zahlentheorie)|Kongruenz]] gelten: | |||
#: <math>e \cdot d \equiv 1\pmod{\varphi(N)}</math> | |||
Die Zahlen <math>p</math>, <math>q</math> und <math>\varphi(N)</math> werden nicht mehr benötigt und können nach der Schlüsselerstellung gelöscht werden. Es ist jedoch relativ einfach, diese Werte aus <math>e</math>, <math>d</math> und <math>N</math> zu rekonstruieren. <math>p, q, \varphi(N)</math> und <math>d</math> müssen geheim gehalten werden. | |||
Da die [[Primzahltest]]s inzwischen ausreichend schnell sind, wählt man heutzutage zuerst einen kleinen Exponenten <math>e</math> mit <math>2^{16} < e < 2^{64}</math> und verwirft bei der Erzeugung die Primzahlen <math>p, q</math>, für die <math>p-1, q-1</math> nicht teilerfremd zu <math>e</math> sind. Die Wahl eines <math>e</math> kleiner als die [[Fermat-Zahl]] <math>F_4 = 2^{16}+1 = 65537</math> kann zu Angriffsmöglichkeiten führen, etwa in Form des von [[Johan Håstad]] publizierten „Broadcast“-Angriffs, bei dem der Versand einer Nachricht an mehrere Empfänger zu einer Dechiffrierung über den [[Chinesischer Restsatz|chinesischen Restsatz]] führen kann. | |||
Wenn <math>d</math> weniger als ein Viertel der Bits des RSA-Moduls hat, kann <math>d</math> – sofern nicht bestimmte Zusatzbedingungen erfüllt sind – mit einem auf [[Kettenbruch|Kettenbrüchen]] aufbauenden Verfahren effizient ermittelt werden. Bei der Wahl eines Exponenten <math>e</math> kleiner als <math>2^{64}</math> ist diese Möglichkeit jedoch ausgeschlossen. | |||
==== Beispiel ==== | |||
# Wir wählen den Exponenten <math>e = 23</math>. | |||
# Wir wählen <math>p = 11</math> und <math>q = 13</math> für die beiden Primzahlen. Die Zahlen <math>p-1 = 10</math> und <math>q-1 = 12</math> sind teilerfremd zum Exponenten <math>e = 23</math>. | |||
# Der RSA-Modul ist <math>N = p \cdot q = 143</math>. Damit bilden <math>e = 23</math> und <math>N = 143</math> den öffentlichen Schlüssel. | |||
# Die eulersche [[Phi|φ]]-Funktion hat den Wert <math>\varphi(N) = \varphi(143) = (p-1)(q-1) = 120</math>. | |||
# [[Prime Restklassengruppe|Berechnung der Inversen]] zu <math>e</math> modulo <math>\varphi(N)</math>:<br />Es gilt: <math> e \cdot d + k \cdot \varphi(N) = 1 = \operatorname{ggT}(e,\varphi(N))</math>,<br />im konkreten Beispiel: <math>23 \cdot d + k \cdot 120 = 1 = \operatorname{ggT}(23,120)</math>.<br />Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Faktoren <math>d=47</math> und <math>k=-9</math>, und somit ist <math>d = 47</math> der private Schlüssel, während <math>k</math> nicht weiter benötigt wird. | |||
=== Verschlüsseln von Nachrichten === | |||
[[Datei:Verschlüsselung (asymmetrisches Kryptosystem) Schema.svg|mini|Verschlüsselung]] | |||
Um eine Nachricht <math>m</math> zu verschlüsseln, verwendet der Absender die Formel | |||
:<math>c \equiv m^e\pmod N</math> | |||
und erhält so aus der [[Klartext (Kryptographie)|Nachricht]] <math>m</math> den [[Geheimtext]] <math>c</math>. Die Zahl <math>m</math> muss dabei kleiner sein als der RSA-Modul <math>N</math>. | |||
==== Beispiel ==== | |||
Es soll die Zahl 7 verschlüsselt werden. Der Sender benutzt den veröffentlichten Schlüssel des Empfängers <math>N = 143</math>, <math>e = 23</math> und rechnet | |||
:<math>2 \equiv 7^{23}\pmod{143}</math> | |||
Das [[Geheimtext|Chiffrat]] ist also <math>c = 2</math>. | |||
=== Entschlüsseln von Nachrichten === | |||
[[Datei:Entschlüsselung (symmetrisches und asymmetrisches Kryptosystem) Schema.svg|mini|Entschlüsselung]] | |||
Der Geheimtext <math>c</math> kann durch [[modulare Exponentiation]] wieder zum Klartext <math>m</math> entschlüsselt werden. Der Empfänger benutzt die Formel | |||
:<math>m \equiv c^d\pmod N</math> | |||
mit dem nur ihm bekannten Wert <math>d</math> sowie <math>N</math>. | |||
==== Beispiel ==== | |||
Für gegebenes <math>c = 2</math> wird berechnet | |||
:<math>7 \equiv 2^{47}\pmod{143}</math> | |||
Der Klartext ist also <math>m = 7</math>. | |||
=== Signieren von Nachrichten === | |||
Um eine Nachricht <math>m</math> zu signieren, wird vom Sender auf die Nachricht die RSA-Funktion mit dem eigenen privaten Schlüssel <math>d</math> angewandt. Zum Prüfen wendet der Empfänger auf die Signatur <math>m^d \bmod\ N</math> mit Hilfe des öffentlichen Schlüssels des Senders <math>e</math> die Umkehrfunktion an und vergleicht diese mit der zusätzlich übermittelten unverschlüsselten Nachricht <math>m</math>. Wenn beide übereinstimmen, ist die Signatur gültig und der Empfänger kann sicher sein, dass derjenige, der das Dokument signiert hat, auch den privaten Schlüssel besitzt und dass niemand seit der Signierung das Dokument geändert hat. Es wird also die [[Integrität (Informationssicherheit)|Integrität]] und [[Authentizität]] garantiert, vorausgesetzt, der private Schlüssel ist wirklich geheim geblieben. | |||
Aufgrund der [[Homomorphismus|Homomorphieeigenschaft]] von RSA ist dieses Signaturverfahren jedoch ungeeignet. Liegen zwei Signaturen <math>m_1^d</math>, <math>m_2^d</math> vor, so kann ein Angreifer daraus durch Multiplizieren die Signatur der Nachricht <math>m_1m_2</math> berechnen. Sogar aus nur einer Signatur <math>m^d</math> kann ein Angreifer beliebig viele Nachrichten-Signatur-Paare erzeugen: <math>(m\cdot c^e,m^d\cdot c)</math> ist ein solches Paar für beliebige <math>c</math>. | |||
Dieses Problem kann umgangen werden, indem nicht die Nachricht selbst signiert wird. Stattdessen wird mit einer zusätzlich zum Signaturverfahren spezifizierten kollisionsresistenten [[Hashfunktion]] <math>H</math> der Hash-Wert <math>H(m)</math> der Nachricht <math>m</math> berechnet. Dieser wird mit dem privaten Schlüssel signiert, um die eigentliche Signatur zu erhalten. Der Empfänger kann die so erhaltene Signatur mit dem öffentlichen Schlüssel verifizieren und erhält dabei einen Wert <math>h'</math>. Diesen vergleicht er mit dem von ihm selbst gebildeten Hashwert <math>H(m)</math> der ihm vorliegenden Nachricht <math>m</math>. Wenn beide Werte <math>H(m)=h'</math> übereinstimmen, kann mit hoher Wahrscheinlichkeit davon ausgegangen werden, dass die Nachricht fehlerfrei übertragen wurde und nicht gefälscht ist. Auch diese Modifikation erfüllt allerdings nicht die modernen Sicherheitsanforderungen, daher werden Verfahren wie RSA-[[Probabilistic Signature Scheme|PSS]] verwendet, um mit RSA zu signieren. | |||
{{Siehe auch|Elektronische Unterschrift|Full-Domain-Hash}} | |||
=== RSA mit dem Chinesischen Restsatz === | |||
Mit Hilfe des [[Chinesischer Restsatz|Chinesischen Restsatzes]] können Nachrichten effizienter entschlüsselt oder signiert werden. | |||
Weil der Modul <math>N</math> sehr groß ist, sind auch die im Rechner verwendeten Bitdarstellungen der Zahlen sehr lang. | |||
Der Chinesische Restsatz erlaubt es, die Berechnungen statt in einer [[Gruppe (Mathematik)|Gruppe]] der Größe <math>N</math> gleichzeitig in den zwei kleineren Gruppen der Größe <math>p</math> und <math>q</math> auszuführen und das Ergebnis danach wieder zusammenzusetzen. | |||
Da hier die Zahlen wesentlich kleiner sind, ist diese Berechnung insgesamt schneller. | |||
Diese Variante wird nach der englischen Bezeichnung des Chinesischen Restsatzes CRT (Chinese remainder theorem) auch CRT-RSA genannt. | |||
Der private Schlüssel besteht dann im Gegensatz zu dem, was im Rest dieses Artikels angenommen wird, aus folgenden Komponenten: | |||
* <math>N</math>, der ''RSA-Modul'', | |||
* <math>d</math>, der ''Entschlüsselungsexponent'', | |||
* <math>p</math>, die ''erste Primzahl,'' | |||
* <math>q</math>, die ''zweite Primzahl'' (ungleich p), | |||
* <math>d_p = d \bmod (p-1)</math>, häufig ''dmp1'' genannt, | |||
* <math>d_q = d \bmod (q-1)</math>, häufig ''dmq1'' genannt und | |||
* <math>q_{Inv} = q^{-1} \bmod p</math>, häufig ''iqmp'' genannt. | |||
Eine Nachricht <math>m</math> wird dann wie folgt signiert: | |||
* <math>m_1 = m^{d_p} \bmod p</math> | |||
* <math>m_2 = m^{d_q} \bmod q</math> | |||
* <math>s = (q_{Inv}(m_1-m_2) \bmod p)q + m_2</math> | |||
Aus der letzten Gleichung sieht man sofort, dass <math>s \bmod q = m_2</math> und <math>s \bmod p = q_{Inv}q(m_1-m_2) + m_2 \bmod p = m_1</math>. | |||
Die Signatur <math>s</math> stimmt also sowohl <math>\bmod p</math> als auch <math>\bmod q</math> mit <math>m^d</math> überein, daher ist nach dem Chinesischen Restsatz <math>s = m^d \bmod N</math>. (Bemerkung: Die Identität <math>s = m^d \bmod p</math> sieht man so: Modulo p gilt <math>s = m^{d_p}=m^{d+k(p-1)}=m^d (m^{p-1})^k=m^d</math>. Die letzte Identität folgt aus dem [[Kleiner fermatscher Satz|kleinen fermatschen Satz]]. Analog erhält man <math>s = m^d \bmod q</math>.) | |||
=== RSA ist kein Primzahltest === | |||
Wenn <math>p \neq q</math> [[Primzahl]]en sind, funktioniert das RSA-Verfahren. Umgekehrt kann aber aus dem funktionierenden RSA-Verfahren nicht geschlossen werden, dass der Modul <math>N</math> das Produkt zweier Primzahlen <math>p</math> und <math>q</math> ist, denn mit [[Carmichael-Zahl]]en funktioniert das Verfahren auch. | |||
[[Kategorie:Kryptografie/Algorithmus]] |
Aktuelle Version vom 28. April 2024, 11:31 Uhr
RSA (Rivest–Shamir–Adleman) ist ein asymmetrisches kryptographisches Verfahren, das sowohl zum Verschlüsseln als auch zum digitalen Signieren verwendet werden kann. Es verwendet ein Schlüsselpaar, bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten verwendet wird, und einem öffentlichen Schlüssel, mit dem man verschlüsselt oder Signaturen prüft. Der private Schlüssel wird geheim gehalten und kann nicht mit realistischem Aufwand aus dem öffentlichen Schlüssel berechnet werden.
Verfahren
Das Verfahren ist mit dem Rabin-Verschlüsselungsverfahren verwandt. Da es deterministisch arbeitet, ist es unter Umständen für bestimmte Angriffe anfällig. In der Praxis wird RSA daher mit dem Optimal Asymmetric Encryption Padding kombiniert.
Einwegfunktionen
Einwegfunktion Funktionen, bei denen eine Richtung leicht, die andere (Umkehrfunktion) schwierig zu berechnen ist, bezeichnet man als Einwegfunktionen (engl. one-way function). Beispielsweise ist nach aktuellem Wissensstand die Faktorisierung einer großen Zahl, also ihre Zerlegung in ihre Primfaktoren, sehr aufwändig, während das Erzeugen einer Zahl durch Multiplikation von Primzahlen recht einfach und schnell möglich ist. Spezielle Einwegfunktionen sind Falltürfunktionen (engl. trapdoor one-way function), die mit Hilfe einer Zusatzinformation auch rückwärts leicht zu berechnen sind.
Die Verschlüsselung und die Signatur mit RSA basieren auf einer Einwegpermutation mit Falltür (engl. trapdoor one-way permutation, kurz TOWP), einer Falltürfunktion, die gleichzeitig bijektiv, also eine Permutation, ist. Die Einwegeigenschaft begründet, warum die Entschlüsselung (bzw. das Signieren) ohne den geheimen Schlüssel (die Falltür) schwierig ist.
Erzeugung des öffentlichen und privaten Schlüssels
Die Schlüssel bestehen aus den drei Zahlen und . Man nennt den RSA-Modul, den Verschlüsselungsexponenten und den Entschlüsselungsexponenten. Das Zahlenpaar bildet den öffentlichen Schlüssel (public key) und das Paar den privaten Schlüssel (private key). Diese Zahlen werden durch das folgende Verfahren erzeugt:
- Wähle zufällig und stochastisch unabhängig zwei Primzahlen . Diese sollen die gleiche Größenordnung haben, aber nicht zu dicht beieinander liegen, sodass der folgende Rahmen ungefähr eingehalten wird: . (In der Praxis erzeugt man dazu solange Zahlen der gewünschten Länge und führt mit diesen anschließend einen Primzahltest durch, bis man zwei Primzahlen gefunden hat.)
- Berechne den RSA-Modul
- Berechne die Eulersche φ-Funktion von
- Wähle eine zu teilerfremde Zahl , für die gilt .
- Berechne den Entschlüsselungsexponenten als multiplikativ Inverses von bezüglich des Moduls , was mit dem erweiterten euklidischen Algorithmus erfolgen kann. Es soll also die Kongruenz gelten:
Die Zahlen , und werden nicht mehr benötigt und können nach der Schlüsselerstellung gelöscht werden. Es ist jedoch relativ einfach, diese Werte aus , und zu rekonstruieren. und müssen geheim gehalten werden.
Da die Primzahltests inzwischen ausreichend schnell sind, wählt man heutzutage zuerst einen kleinen Exponenten mit und verwirft bei der Erzeugung die Primzahlen , für die nicht teilerfremd zu sind. Die Wahl eines kleiner als die Fermat-Zahl kann zu Angriffsmöglichkeiten führen, etwa in Form des von Johan Håstad publizierten „Broadcast“-Angriffs, bei dem der Versand einer Nachricht an mehrere Empfänger zu einer Dechiffrierung über den chinesischen Restsatz führen kann.
Wenn weniger als ein Viertel der Bits des RSA-Moduls hat, kann – sofern nicht bestimmte Zusatzbedingungen erfüllt sind – mit einem auf Kettenbrüchen aufbauenden Verfahren effizient ermittelt werden. Bei der Wahl eines Exponenten kleiner als ist diese Möglichkeit jedoch ausgeschlossen.
Beispiel
- Wir wählen den Exponenten .
- Wir wählen und für die beiden Primzahlen. Die Zahlen und sind teilerfremd zum Exponenten .
- Der RSA-Modul ist . Damit bilden und den öffentlichen Schlüssel.
- Die eulersche φ-Funktion hat den Wert .
- Berechnung der Inversen zu modulo :
Es gilt: ,
im konkreten Beispiel: .
Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Faktoren und , und somit ist der private Schlüssel, während nicht weiter benötigt wird.
Verschlüsseln von Nachrichten
Um eine Nachricht zu verschlüsseln, verwendet der Absender die Formel
und erhält so aus der Nachricht den Geheimtext . Die Zahl muss dabei kleiner sein als der RSA-Modul .
Beispiel
Es soll die Zahl 7 verschlüsselt werden. Der Sender benutzt den veröffentlichten Schlüssel des Empfängers , und rechnet
Das Chiffrat ist also .
Entschlüsseln von Nachrichten
Der Geheimtext kann durch modulare Exponentiation wieder zum Klartext entschlüsselt werden. Der Empfänger benutzt die Formel
mit dem nur ihm bekannten Wert sowie .
Beispiel
Für gegebenes wird berechnet
Der Klartext ist also .
Signieren von Nachrichten
Um eine Nachricht zu signieren, wird vom Sender auf die Nachricht die RSA-Funktion mit dem eigenen privaten Schlüssel angewandt. Zum Prüfen wendet der Empfänger auf die Signatur mit Hilfe des öffentlichen Schlüssels des Senders die Umkehrfunktion an und vergleicht diese mit der zusätzlich übermittelten unverschlüsselten Nachricht . Wenn beide übereinstimmen, ist die Signatur gültig und der Empfänger kann sicher sein, dass derjenige, der das Dokument signiert hat, auch den privaten Schlüssel besitzt und dass niemand seit der Signierung das Dokument geändert hat. Es wird also die Integrität und Authentizität garantiert, vorausgesetzt, der private Schlüssel ist wirklich geheim geblieben. Aufgrund der Homomorphieeigenschaft von RSA ist dieses Signaturverfahren jedoch ungeeignet. Liegen zwei Signaturen , vor, so kann ein Angreifer daraus durch Multiplizieren die Signatur der Nachricht berechnen. Sogar aus nur einer Signatur kann ein Angreifer beliebig viele Nachrichten-Signatur-Paare erzeugen: ist ein solches Paar für beliebige .
Dieses Problem kann umgangen werden, indem nicht die Nachricht selbst signiert wird. Stattdessen wird mit einer zusätzlich zum Signaturverfahren spezifizierten kollisionsresistenten Hashfunktion der Hash-Wert der Nachricht berechnet. Dieser wird mit dem privaten Schlüssel signiert, um die eigentliche Signatur zu erhalten. Der Empfänger kann die so erhaltene Signatur mit dem öffentlichen Schlüssel verifizieren und erhält dabei einen Wert . Diesen vergleicht er mit dem von ihm selbst gebildeten Hashwert der ihm vorliegenden Nachricht . Wenn beide Werte übereinstimmen, kann mit hoher Wahrscheinlichkeit davon ausgegangen werden, dass die Nachricht fehlerfrei übertragen wurde und nicht gefälscht ist. Auch diese Modifikation erfüllt allerdings nicht die modernen Sicherheitsanforderungen, daher werden Verfahren wie RSA-PSS verwendet, um mit RSA zu signieren.
RSA mit dem Chinesischen Restsatz
Mit Hilfe des Chinesischen Restsatzes können Nachrichten effizienter entschlüsselt oder signiert werden. Weil der Modul sehr groß ist, sind auch die im Rechner verwendeten Bitdarstellungen der Zahlen sehr lang. Der Chinesische Restsatz erlaubt es, die Berechnungen statt in einer Gruppe der Größe gleichzeitig in den zwei kleineren Gruppen der Größe und auszuführen und das Ergebnis danach wieder zusammenzusetzen. Da hier die Zahlen wesentlich kleiner sind, ist diese Berechnung insgesamt schneller. Diese Variante wird nach der englischen Bezeichnung des Chinesischen Restsatzes CRT (Chinese remainder theorem) auch CRT-RSA genannt.
Der private Schlüssel besteht dann im Gegensatz zu dem, was im Rest dieses Artikels angenommen wird, aus folgenden Komponenten:
- , der RSA-Modul,
- , der Entschlüsselungsexponent,
- , die erste Primzahl,
- , die zweite Primzahl (ungleich p),
- , häufig dmp1 genannt,
- , häufig dmq1 genannt und
- , häufig iqmp genannt.
Eine Nachricht wird dann wie folgt signiert:
Aus der letzten Gleichung sieht man sofort, dass und . Die Signatur stimmt also sowohl als auch mit überein, daher ist nach dem Chinesischen Restsatz . (Bemerkung: Die Identität sieht man so: Modulo p gilt . Die letzte Identität folgt aus dem kleinen fermatschen Satz. Analog erhält man .)
RSA ist kein Primzahltest
Wenn Primzahlen sind, funktioniert das RSA-Verfahren. Umgekehrt kann aber aus dem funktionierenden RSA-Verfahren nicht geschlossen werden, dass der Modul das Produkt zweier Primzahlen und ist, denn mit Carmichael-Zahlen funktioniert das Verfahren auch.