Deutsch
Menü

Was ist RSA-Kryptosystem?

Ein 1977 von Rivest, Shamir und Adleman entwickeltes Public-Key-Verfahren. Das Produkt n zweier großer Primzahlen p und q und der öffentliche Exponent e bilden den öffentlichen Schlüssel, ein d mit e × d ≡ 1 (mod (p − 1)(q − 1)) den privaten Schlüssel. Verschlüsselt wird mit c = m^e mod n, entschlüsselt mit m = c^d mod n. Die Sicherheit beruht auf der Schwierigkeit, n zu faktorisieren; RSA eignet sich sowohl für Verschlüsselung als auch für Signaturen. In der Praxis wird es mit einem Padding mit Zufallsanteil wie OAEP oder PSS kombiniert.

Japanische Bezeichnung: RSA暗号

„RSA-Kryptosystem“ kommt in 10 Übungsfragen aus 2 Themen vor, z. B. Grundlagen und Anwendungen der Kryptografie, Hardware für Quantencomputer.

Fachgebiet: Grundlagen und Anwendungen der Kryptografie

Beispiel mit kleinen Zahlen

Mit p = 5 und q = 11 ist n = 55 und (p − 1)(q − 1) = 40. Mit e = 3 gilt 3 × 27 = 81 ≡ 1 (mod 40), also d = 27. Der Klartext m = 7 wird zu 7³ = 343 ≡ 13 (mod 55) verschlüsselt, und die Berechnung von 13^27 mod 55 ergibt wieder 7.

Schlüssellänge und Sicherheit

In der Tabelle von NIST SP 800-57 gilt ein n mit 2048 Bit als Richtwert für eine Sicherheit von 112 Bit, eines mit 3072 Bit als Richtwert für 128 Bit. Bei gleicher Sicherheit sind viel längere Schlüssel und Signaturen nötig als bei der Elliptische-Kurven-Kryptografie, und auch Schlüsselerzeugung und Signaturberechnung sind aufwendiger. Als öffentlicher Exponent wird häufig 65537 (2^16 + 1) verwendet, mit dem sich schnell rechnen lässt.

Wandel des Einsatzes

Im früheren TLS war ein Schlüsselaustausch verbreitet, bei dem der Client selbst erzeugtes Schlüsselmaterial mit dem öffentlichen RSA-Schlüssel des Servers verschlüsselt sendete; weil er keine Forward Secrecy bietet, wurde er in TLS 1.3 abgeschafft. Heute wird RSA hauptsächlich für Signaturen von Zertifikaten und Software verwendet. Sobald große Quantencomputer Wirklichkeit werden, bricht der Shor-Algorithmus RSA; daher läuft die Umstellung auf Post-Quanten-Kryptografie.

Jetzt üben: Fragen zu RSA-Kryptosystem

Die Funktionsweise von RSA wird mit kleinen Zahlen nachvollzogen. Aus den Primzahlen p = 5 und q = 11 wird n = pq gebildet, und der öffentliche Exponent ist e = 3. Mit φ(n) = (p − 1)(q − 1): Welcher private Exponent d (0 < d < φ(n)) erfüllt e × d ≡ 1 (mod φ(n))?

  1. A5
  2. B27
  3. C37
Antwort und Erläuterung anzeigen

Antwort: B. 27

n = 5 × 11 = 55 und φ(n) = 4 × 10 = 40. Gesucht ist ein d, für das 3 × d bei Division durch 40 den Rest 1 lässt: 3 × 27 = 81 = 2 × 40 + 1, also d = 27. Der öffentliche Schlüssel ist (n, e) = (55, 3), der private Schlüssel d = 27; die Sicherheit beruht darauf, dass man ohne p und q den Wert φ(n) nicht kennt und d nicht bestimmen kann. Beim realen RSA sind p und q jeweils große Primzahlen mit über 1000 Bit, und für e wird häufig 65537 verwendet.

Bei RSA sei der öffentliche Schlüssel n = 55, e = 3. Wie lautet der Geheimtext c, wenn der Klartext m = 7 mit c = m^e mod n verschlüsselt wird?

  1. A13
  2. B21
  3. C23
Antwort und Erläuterung anzeigen

Antwort: A. 13

7³ = 343 und 343 = 6 × 55 + 13, also c = 13. Der zu diesem öffentlichen Schlüssel gehörende private Exponent ist d = 27 (p = 5, q = 11, φ(n) = 40 und 3 × 27 ≡ 1); berechnet man 13^27 mod 55, erhält man den ursprünglichen Klartext 7 zurück. Verschlüsseln kann man allein mit dem öffentlichen Schlüssel, zum Entschlüsseln wird jedoch d benötigt.

Häufige Fragen

Warum müssen p und q geheim bleiben?

Wer p und q kennt, kann (p − 1)(q − 1) berechnen und aus dem öffentlichen e den Wert d bestimmen. Da n öffentlich ist, beruht die Sicherheit auf der Schwierigkeit, n zu faktorisieren.

Warum werden Dateien nicht direkt mit RSA verschlüsselt?

Mit RSA lassen sich auf einmal nur Zahlen verschlüsseln, die kleiner als n sind, und die Berechnung ist viel aufwendiger als bei symmetrischer Verschlüsselung. In der Praxis wird ein hybrides Verfahren verwendet: Die Datei wird mit symmetrischer Verschlüsselung wie AES verschlüsselt, und nur der symmetrische Schlüssel wird mit dem öffentlichen Schlüssel geschützt.

„RSA-Kryptosystem“ in den Erläuterungen

Fragen mit „RSA-Kryptosystem“ (10)

  1. Die Funktionsweise von RSA wird mit kleinen Zahlen nachvollzogen. Aus den Primzahlen p = 5 und q = 11 wird n = pq gebildet, und der öffentliche Exponent ist e = 3. Mit φ(n) = (p − 1)(q − 1): Welcher private Exponent d (0 < d < φ(n)) erfüllt e × d ≡ 1 (mod φ(n))?
  2. Bei RSA sei der öffentliche Schlüssel n = 55, e = 3. Wie lautet der Geheimtext c, wenn der Klartext m = 7 mit c = m^e mod n verschlüsselt wird?
  3. Was ist das Problem, wenn Lehrbuch-RSA (der Klartext m wird unverändert als c = m^e mod n verschlüsselt) ohne Padding in realer Kommunikation verwendet wird?
  4. Welche Kombination aus RSA-Schlüssellänge (Bitzahl von n) und Schlüssellänge der Elliptische-Kurven-Kryptografie gilt in der Tabelle von NIST SP 800-57 als Richtwert für eine Sicherheit, wie sie die symmetrische Verschlüsselung mit 128 Bit (AES-128) bietet?
  5. Bei welchen Verschlüsselungsverfahren wird erwartet, dass ihre Sicherheit durch den Shor-Algorithmus ernsthaft untergraben wird, sobald große fehlertolerante Quantencomputer gebaut sind?
  6. Welche Aussage beschreibt Post-Quanten-Kryptografie (PQC) richtig?
  7. Welches Schlüsselaustauschverfahren bietet bei TLS die Eigenschaft, dass zuvor aufgezeichnete Kommunikation auch dann nicht entschlüsselt werden kann, wenn der private Schlüssel des Serverzertifikats später abfließt (Forward Secrecy)?
  8. Was hat sich in TLS 1.3 (RFC 8446) gegenüber TLS 1.2 geändert?
  9. Welche Kombination gibt an, was die Cipher Suite TLS_AES_128_GCM_SHA256 von TLS 1.3 festlegt?
  10. Welche Maßnahme im Systementwurf erhöht die Krypto-Agilität (die Eigenschaft, kryptografische Verfahren leicht austauschen zu können)?

Verwandte Begriffe

TLS (Transport Layer Security) Modulo-Operation Elliptische-Kurven-Kryptografie Diffie-Hellman-Schlüsselaustausch Symmetrische Verschlüsselung (Secret-Key-Verfahren) Shor-Algorithmus AES Post-Quanten-Kryptografie (PQC) Hashfunktion Forward Secrecy

Zur Glossarübersicht