Deutsch
Menü

RSA vs. Elliptische-Kurven-Kryptografie vs. PQC: Schlüssel, Tempo, Quantenresistenz

Alle drei sind Public-Key-Kryptografie und werden zum Teilen von Schlüsseln (Schlüsselaustausch oder Schlüsselkapselung) und für digitale Signaturen verwendet. RSA beruht auf der Schwierigkeit, große Zahlen zu faktorisieren, Elliptische-Kurven-Kryptografie auf der Schwierigkeit des diskreten Logarithmusproblems auf elliptischen Kurven; bei gleicher Sicherheit braucht Elliptische-Kurven-Kryptografie viel kürzere Schlüssel als RSA. Beide würden jedoch durch den Shor-Algorithmus gebrochen, sobald ein großer fehlertoleranter Quantencomputer existiert. Post-Quanten-Kryptografie beruht auf Problemen wie Gitterproblemen, die vermutlich auch für Quantencomputer schwer sind; im August 2024 veröffentlichte das US-amerikanische NIST Standards, darunter den Schlüsselkapselungsmechanismus ML-KEM (FIPS 203) und das Signaturverfahren ML-DSA (FIPS 204). Ihr Hauptnachteil sind große Schlüssel und Signaturen.

MerkmalRSAElliptische-Kurven-KryptografiePost-Quanten-Kryptografie (ML-KEM, ML-DSA)
Zugrunde liegendes schweres ProblemFaktorisierung großer ZahlenDas diskrete Logarithmusproblem auf elliptischen KurvenBei ML-KEM und ML-DSA Gitterprobleme (etwa Module-LWE, das Zurückgewinnen eines Geheimnisses aus linearen Gleichungen mit kleinen hinzugefügten Fehlern); es gibt auch SLH-DSA (FIPS 205), ein Signaturverfahren, das nur auf Hashfunktionen beruht
Schlüsselgröße (Richtwert)In der Tabelle von NIST SP 800-57 ist der Richtwert für 128-Bit-Sicherheit ein n mit 3072 Bit (384 Byte); 2048 Bit entsprechen 112-Bit-SicherheitIn derselben Tabelle ist der Richtwert für 128-Bit-Sicherheit 256 Bit; beim X25519-Schlüsselaustausch ist der gesendete öffentliche Wert 32 Byte großEin öffentlicher Schlüssel (Kapselungsschlüssel) von ML-KEM-768 ist 1.184 Byte groß, weit mehr als die 32 Byte von X25519
Größe von Chiffretext und SignaturChiffretexte und Signaturen sind so lang wie n (384 Byte bei 3072 Bit)Eine ECDSA-Signatur (P-256) besteht aus zwei 256-Bit-Werten r und s, also 64 Byte (je nach Kodierung etwas mehr)Ein Chiffretext von ML-KEM-768 hat 1.088 Byte, eine Signatur von ML-DSA-65 umfasst 3.309 Byte
GeschwindigkeitDa der öffentliche Exponent klein sein kann (etwa 65537), sind Verschlüsselung und Signaturprüfung schnell; Entschlüsselung, Signieren und Schlüsselerzeugung sind aufwendigSchlüsselerzeugung und Signieren sind bei gleicher Sicherheit viel schneller als bei RSA; die Signaturprüfung ist oft langsamer als bei RSADie Berechnung von ML-KEM ist leichtgewichtig und gilt als nicht langsamer als ein Schlüsselaustausch mit elliptischen Kurven; die Größe der gesendeten Daten ist meist das größere Problem als die Rechenzeit
QuantenresistenzKeine: Der Shor-Algorithmus bricht es auf einem großen fehlertoleranten QuantencomputerKeine: Der Shor-Algorithmus löst auch das diskrete Logarithmusproblem, daher wird sie wie RSA gebrochenGilt als auch mit Quantencomputern schwer effizient lösbar (bewiesen ist das nicht)
Standardisierung1977 erfunden; in der Praxis mit randomisiertem Padding verwendet, etwa OAEP für Verschlüsselung und PSS für SignaturenKurven wie P-256 sowie X25519 und Ed25519 auf Basis von Curve25519 sind weit verbreitetIm August 2024 von NIST als FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) und FIPS 205 (SLH-DSA) veröffentlicht
Heutige typische AnwendungenMitte der 2020er-Jahre vor allem Zertifikate und Software-Signaturen; TLS 1.3 hat den Schlüsselaustausch abgeschafft, bei dem mit RSA verschlüsseltes Schlüsselmaterial gesendet wirdMitte der 2020er-Jahre die tragende Säule des TLS-Schlüsselaustauschs (ECDHE); außerdem ECDSA- und EdDSA-Signaturen sowie ressourcenbeschränkte Geräte wie Smartcards und eingebettete SystemeSeit 2025 wird in TLS 1.3 ein hybrider Schlüsselaustausch in Kombination mit X25519 (etwa X25519MLKEM768) eingesetzt; die Migration der Signaturen folgt nach dem Schlüsselaustausch
MigrationZiel der Migration zur Post-Quanten-Kryptografie; die Herausforderung ist der Austausch von Signaturen, etwa in Zertifikaten und beim Code-SigningZiel der Migration; in der Übergangszeit dient sie als eine Hälfte des hybriden Schlüsselaustauschs mit ML-KEM und liefert die Sicherheit gegenüber klassischen ComputernVorerst erfolgt die Migration schrittweise mit hybriden Verfahren, die sie mit herkömmlicher Kryptografie kombinieren; Designs, die Algorithmen später leicht austauschbar machen (Krypto-Agilität), werden betont
Hinweise zur ImplementierungNiemals Lehrbuch-RSA ohne Padding verwenden; die Schlüsselerzeugung braucht hochwertige ZufallszahlenWird der Zufallswert pro Signatur (Nonce) wiederverwendet oder ist er verzerrt, können Angreifer den privaten Schlüssel zurückgewinnen; empfangene Punkte müssen zudem darauf geprüft werden, ob sie auf der richtigen Kurve liegenBei großen Schlüsseln und Signaturen müssen die Auswirkungen auf Paketgrößen und speicherbeschränkte Geräte geprüft werden; auf Fehler in neuen Implementierungen und auf Seitenkanalangriffe achten

Die Zahlenwerte sind typische Größenordnungen und variieren je nach Prozessgeneration und Produkt.

Wann welche Variante?

RSA
Wenn Kompatibilität mit bestehenden Zertifikaten und Systemen nötig ist. Die schnelle Prüfung passt zu Anwendungen mit vielen Prüfern, aber ein Plan für die Migration zur Post-Quanten-Kryptografie ist erforderlich.
Elliptische-Kurven-Kryptografie
Wenn neue Systeme heute Schlüsselaustausch und Signaturen mit kurzen Schlüsseln und kleinen Daten brauchen. Passt auch zu Smartcards und eingebetteten Geräten. Den Übergang zu hybriden Verfahren planen, um auf Quantencomputer vorbereitet zu sein.
Post-Quanten-Kryptografie (ML-KEM, ML-DSA)
Beim Schutz von Daten, die lange geheim bleiben müssen. Zur Vorbereitung auf „Harvest now, decrypt later“, bei dem heute aufgezeichnete Chiffretexte in Zukunft entschlüsselt werden, zuerst beim Schlüsselaustausch in einem hybriden Verfahren einführen.

Häufige Fragen

Warum braucht Elliptische-Kurven-Kryptografie kürzere Schlüssel als RSA?

Weil die besten bekannten Angriffe unterschiedlich viel kosten. Für die Faktorisierung gibt es Verfahren, die viel schneller als Brute Force sind, daher müssen RSA-Schlüssel recht lang sein. Beim diskreten Logarithmusproblem auf elliptischen Kurven brauchen selbst die besten bekannten Angriffe einen Aufwand in der Größenordnung der halben Schlüssellänge in Bit, sodass der Schlüssel nur etwa doppelt so lang wie das Sicherheitsniveau sein muss. In der Tabelle von NIST SP 800-57 ist der Richtwert für 128-Bit-Sicherheit 3072 Bit bei RSA gegenüber 256 Bit bei Elliptische-Kurven-Kryptografie.

Warum jetzt migrieren, wenn es noch keine Quantencomputer gibt?

Weil heute abgefangene und gespeicherte Chiffretexte von künftigen Quantencomputern entschlüsselt werden könnten (Harvest now, decrypt later). Zudem dauert der Austausch von Kryptografie über Software, Geräte und Zertifikatsinfrastruktur viele Jahre. Deshalb beginnt die Migration mit dem Schlüsselaustausch, der Daten transportiert, die lange geheim bleiben müssen.

Brechen Quantencomputer auch symmetrische Verfahren wie AES?

Sie sind kein Ziel des Shor-Algorithmus. Nach der einfachen Faustregel, dass der Grover-Algorithmus die Schlüsselsuche quadratisch beschleunigt, halbiert sich das Sicherheitsniveau in Bit; dem lässt sich begegnen, indem man dort, wo langfristige Sicherheit nötig ist, AES-256 wählt. Ersetzt werden muss vor allem Public-Key-Kryptografie wie RSA und Elliptische-Kurven-Kryptografie.

Was ist ein hybrides Verfahren?

Ein Verfahren, das herkömmliche Kryptografie und Post-Quanten-Kryptografie gleichzeitig einsetzt und die Ergebnisse kombiniert. Beim Schlüsselaustausch fließen die gemeinsamen Geheimnisse von X25519 und ML-KEM beide in die Schlüsselableitung ein, sodass der resultierende Schlüssel geschützt bleibt, solange eines der beiden sicher ist. Post-Quanten-Verfahren sind neu, und Implementierungsfehler oder neue Angriffe lassen sich noch nicht ganz ausschließen; das hybride Vorgehen dient daher als Absicherung in der Übergangszeit.

Verständnis prüfen

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?

  1. ARSA etwa 128 Bit, Elliptische-Kurven-Kryptografie etwa 128 Bit
  2. BRSA etwa 2048 Bit, Elliptische-Kurven-Kryptografie etwa 128 Bit
  3. CRSA etwa 3072 Bit, Elliptische-Kurven-Kryptografie etwa 256 Bit
Antwort und Erläuterung anzeigen

Antwort: C. RSA etwa 3072 Bit, Elliptische-Kurven-Kryptografie etwa 256 Bit

Public-Key-Kryptografie braucht für dieselbe Sicherheit längere Schlüssel als die symmetrische Verschlüsselung. In der Tabelle von NIST SP 800-57 Part 1 gelten als Richtwerte für eine Sicherheit von 128 Bit bei RSA 3072 Bit und bei der Elliptische-Kurven-Kryptografie 256 bis 383 Bit. Da der beste bekannte Angriff auf die Elliptische-Kurven-Kryptografie einen Aufwand in der Größenordnung der halben Schlüssellänge in Bit erfordert, genügt eine Schlüssellänge von etwa dem Doppelten der Sicherheit in Bit, sodass mit viel kürzeren Schlüsseln als bei RSA dieselbe Sicherheit erreicht wird. 2048 Bit bei RSA entsprechen einem Richtwert von 112 Bit.

Welche Zuordnung der im August 2024 vom US-amerikanischen NIST veröffentlichten Standards der Post-Quanten-Kryptografie zu ihrer Art ist richtig?

  1. AML-KEM (FIPS 203) ist ein gitterbasiertes Signaturverfahren, ML-DSA (FIPS 204) ein hashbasierter Schlüsselkapselungsmechanismus und SLH-DSA (FIPS 205) eine symmetrische Verschlüsselung
  2. BML-KEM (FIPS 203), ML-DSA (FIPS 204) und SLH-DSA (FIPS 205) sind alle Signaturverfahren mit kurzen Schlüsseln, die auf Problemen über elliptischen Kurven beruhen
  3. CML-KEM (FIPS 203) ist ein gitterbasierter Schlüsselkapselungsmechanismus, ML-DSA (FIPS 204) ein gitterbasiertes Signaturverfahren und SLH-DSA (FIPS 205) ein hashbasiertes Signaturverfahren
Antwort und Erläuterung anzeigen

Antwort: C. ML-KEM (FIPS 203) ist ein gitterbasierter Schlüsselkapselungsmechanismus, ML-DSA (FIPS 204) ein gitterbasiertes Signaturverfahren und SLH-DSA (FIPS 205) ein hashbasiertes Signaturverfahren

Am 13. August 2024 veröffentlichte das NIST drei FIPS als erste Standards der Post-Quanten-Kryptografie. ML-KEM nach FIPS 203 (ursprünglicher Name CRYSTALS-Kyber) ist ein Schlüsselkapselungsmechanismus zum Austausch von Schlüsseln, ML-DSA nach FIPS 204 (CRYSTALS-Dilithium) und SLH-DSA nach FIPS 205 (SPHINCS+) sind Verfahren für die digitale Signatur. ML-KEM und ML-DSA beruhen auf der Schwierigkeit von Gitterproblemen (etwa dem Module-LWE-Problem, bei dem ein Geheimnis aus einem linearen Gleichungssystem mit kleinen hinzugefügten Fehlern zu bestimmen ist). SLH-DSA stützt sich nur auf die Sicherheit einer Hashfunktion; die Signaturen sind daher groß und langsam, doch es dient als Absicherung, falls bei den Gitterproblemen Schwachstellen gefunden werden.

Welche Aussage beschreibt den Gedanken des hybriden Schlüsselaustauschs richtig, der während der Umstellung auf Post-Quanten-Kryptografie X25519 (Diffie-Hellman-Schlüsselaustausch mit elliptischen Kurven) und ML-KEM kombiniert?

  1. ADie gemeinsamen Geheimnisse beider Verfahren fließen beide in die Schlüsselableitung ein, sodass der erzeugte Schlüssel sicher ist, solange eines der beiden Verfahren sicher ist
  2. BVon den beiden Verfahren wird nur das gemeinsame Geheimnis desjenigen verwendet, das im Handshake zuerst fertig ist; das andere wird verworfen
  3. CML-KEM wird erst verwendet, wenn Quantencomputer Wirklichkeit werden; beide Verfahren werden bereitgehalten, damit dann automatisch umgeschaltet wird
Antwort und Erläuterung anzeigen

Antwort: A. Die gemeinsamen Geheimnisse beider Verfahren fließen beide in die Schlüsselableitung ein, sodass der erzeugte Schlüssel sicher ist, solange eines der beiden Verfahren sicher ist

ML-KEM ist ein neues Verfahren, bei dem sich die Gefahr von Implementierungsfehlern oder neu entdeckten Angriffen noch nicht ausreichend ausschließen lässt. X25519 dagegen ist zwar gegenüber Quantencomputern schwach, hat aber eine lange Erfolgsbilanz bei der Sicherheit gegenüber klassischen Computern. Beim hybriden Schlüsselaustausch werden beide gemeinsamen Geheimnisse verkettet in die Schlüsselableitungsfunktion gegeben, sodass ein Angreifer beide Verfahren brechen muss, um den Schlüssel zu erhalten; damit wird auch verhindert, dass heute aufgezeichnete Kommunikation von künftigen Quantencomputern entschlüsselt wird. Stand 2025 wird diese Kombination (etwa X25519MLKEM768) in TLS 1.3 zunehmend eingesetzt.

  1. Bei welchen Verschlüsselungsverfahren wird erwartet, dass ihre Sicherheit durch den Shor-Algorithmus ernsthaft untergraben wird, sobald große fehlertolerante Quantencomputer gebaut sind?
  2. Was ist der zutreffendste Grund, die Umstellung auf Post-Quanten-Kryptografie zu beschleunigen, obwohl es große Quantencomputer noch nicht gibt?
  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?

Übungsfragen zu Grundlagen und Anwendungen der Kryptografie

Wichtige Begriffe erklärt

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.
Elliptische-Kurven-Kryptografie
Sammelbegriff für Public-Key-Verfahren, die Punktoperationen auf elliptischen Kurven über endlichen Körpern nutzen. Ihre Sicherheit beruht auf der Schwierigkeit, aus dem Punkt kG, dem geheimen ganzzahligen k-fachen eines Kurvenpunkts G, den Wert k zu bestimmen (diskretes Logarithmusproblem auf elliptischen Kurven). Bei gleicher Sicherheit genügen viel kürzere Schlüssel als bei RSA; als Richtwert gilt ein 256-Bit-Schlüssel als ebenso sicher (entsprechend 128 Bit) wie 3072 Bit bei RSA. Verwendet wird sie für den Schlüsselaustausch mit ECDH und ECDHE sowie für Signaturen mit ECDSA und EdDSA; verbreitete Kurven sind etwa P-256 und Curve25519. Da der Shor-Algorithmus sie bricht, ist sie Gegenstand der Umstellung auf Post-Quanten-Kryptografie.
Post-Quanten-Kryptografie (PQC)
Kryptografie, die ihre Sicherheit auf mathematische Probleme stützt, die vermutlich auch für Quantencomputer nicht effizient lösbar sind, etwa Gitterprobleme und Hashfunktionen. Sie läuft auf herkömmlichen Computern und dient als Ersatz für RSA und Elliptische-Kurven-Kryptografie, die der Shor-Algorithmus brechen kann.
ML-KEM
Ein gitterbasierter Schlüsselkapselungsmechanismus (KEM), den das US-amerikanische NIST im August 2024 als FIPS 203 standardisiert hat. Der Name steht für Module-Lattice-Based Key-Encapsulation Mechanism; Grundlage ist CRYSTALS-Kyber. Die Sicherheit beruht auf der Schwierigkeit des Module-LWE-Problems, bei dem ein Geheimnis aus einem linearen Gleichungssystem mit kleinen hinzugefügten Fehlern zu bestimmen ist und das vermutlich auch Quantencomputer nicht effizient lösen können. Es gibt drei Parametersätze: ML-KEM-512, ML-KEM-768 und ML-KEM-1024. Eingesetzt wird es etwa in TLS, um den ECDHE-Schlüsselaustausch zu ersetzen oder mit ihm kombiniert zu werden.
Shor-Algorithmus
Quantenalgorithmus, der die Faktorisierung großer ganzer Zahlen und das diskrete Logarithmusproblem in Polynomialzeit löst, indem er mit der Quanten-Fourier-Transformation Perioden bestimmt. Peter Shor veröffentlichte ihn 1994. Er kann RSA und Elliptische-Kurven-Kryptografie brechen, doch seine Ausführung erfordert einen großen fehlertoleranten Quantencomputer.
Diffie-Hellman-Schlüsselaustausch
Ein Verfahren, mit dem zwei Parteien allein über einen öffentlichen Kanal ein gemeinsames Geheimnis erzeugen; 1976 von Diffie und Hellman veröffentlicht. Eine Primzahl p und ein Generator g werden veröffentlicht; A und B bilden aus ihren geheimen Werten a und b die Werte g^a mod p und g^b mod p, senden sie einander und potenzieren jeweils den Wert des Gegenübers mit dem eigenen geheimen Wert, sodass beide dasselbe g^(ab) mod p erhalten. Die Sicherheit beruht auf der Schwierigkeit des diskreten Logarithmusproblems. Die Variante auf elliptischen Kurven heißt ECDH, Varianten mit Einmalwerten für jede Verbindung heißen DHE und ECDHE; letztere bieten Forward Secrecy. Da das Verfahren das Gegenüber nicht prüft, wird es mit Signaturen oder Zertifikaten kombiniert, um Man-in-the-Middle-Angriffe zu verhindern.
Krypto-Agilität
Die Eigenschaft, kryptografische Algorithmen oder Schlüssellängen, die unsicher geworden sind, ohne großen Umbau des Systems gegen andere Verfahren austauschen zu können. Sie wird erhöht, indem man ein Verzeichnis (Inventar) führt, wo welche Kryptografie eingesetzt wird, Algorithmen über Einstellungen oder Protokollaushandlung wählbar macht und Algorithmuskennungen in Datenformate aufnimmt. Sie gewinnt bei der Ablösung von MD5, SHA-1 und RSA mit kurzen Schlüsseln sowie bei der Umstellung auf Post-Quanten-Kryptografie an Bedeutung.
Public-Key-Kryptografie (asymmetrische Verschlüsselung)
Kryptografisches Verfahren, das zum Verschlüsseln und Entschlüsseln ein zusammengehöriges Paar verschiedener Schlüssel verwendet: einen öffentlichen und einen privaten Schlüssel. Der öffentliche Schlüssel darf allen bekannt sein, den privaten besitzt nur sein Inhaber. Die Schlüsselverteilung wird einfach, doch die Berechnung ist aufwendig; zur Verschlüsselung der eigentlichen Daten wird sie daher mit symmetrischer Verschlüsselung kombiniert. Typische Beispiele sind RSA und Elliptische-Kurven-Kryptografie.

Verwandte Vergleiche