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

Alice gibt ihren öffentlichen Schlüssel ( n {\displaystyle n\,} & e {\displaystyle e\,} ) an 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 entsprechenden Chiffretext c {\Darstellungsstil c\,}:

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

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

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

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

Bei einem m {\Darstellungsstil 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}}} .

Also,

c d ≡ m mod n {\displaystyle 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.

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

Der öffentliche Schlüssel lautet ( n = 3233 {\Anzeigestil n=3233} , e = 17 {\Anzeigestil e=17} ). Für eine aufgefüllte Nachricht m {\displaystyle m\,} 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\,}

Der private Schlüssel lautet ( n = 3233 {\Anzeigestil n=3233} , d = 2753 {\Anzeigestil d=2753} ). Die Entschlüsselungsfunktion m = c d mod n {\displaystyle 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\,}

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

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

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

m = 855 2753 mod 3 233 = 123 {\Anzeigestil 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].

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ü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}}}

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}}}}

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

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

e d = k × ϕ ( n ) + 1 {\displaystyle 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}}

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}}}}

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}} 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).

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.