RSA – Rivest-Shamir-Adleman

Abkürzung: RSA

Benannt ist es nach Rivest, Shamir und Adleman, die es 1977 veröffentlichten. RSA war das erste praktisch brauchbare Public-Key-Verfahren, das sowohl verschlüsseln als auch signieren kann, und hat die Sicherung des Internets über drei Jahrzehnte getragen. Heute wird es verdrängt — nicht weil es gebrochen wäre, sondern weil elliptische Kurven dasselbe mit kürzeren Schlüsseln leisten.

Wie der Schlüssel entsteht

Die Erzeugung läuft in vier Schritten:

1. Zwei große Primzahlen p und q werden zufällig gewählt.
2. Ihr Produkt n = p · q ist der Modul und bestimmt die Schlüssellänge. Von einem 2048-Bit-Schlüssel zu sprechen heißt: n ist 2048 Bit lang.
3. Ein öffentlicher Exponent e wird festgelegt, fast immer 65537.
4. Der private Exponent d wird so berechnet, dass er die Wirkung von e umkehrt. Das setzt die Kenntnis von p und q voraus.

Der Public Key besteht aus n und e, der Private Key im Kern aus d. Entscheidend ist der letzte Schritt: Wer p und q kennt, berechnet d in Millisekunden. Wer nur n hat, müsste es zuerst faktorisieren — und daran scheitert der Angriff.

Dass n beide Primzahlen enthält, erklärt auch, warum die Erzeugung der sicherheitskritische Moment ist: Ein schlechter Zufallszahlengenerator kompromittiert den Schlüssel dauerhaft, und zwar bevor er je benutzt wurde.

Verschlüsseln und Signieren sind nicht dasselbe

Beide Operationen nutzen dasselbe Schlüsselpaar, aber mit vertauschten Rollen:

Die verbreitete Kurzformel „eine Signatur ist eine Verschlüsselung mit dem privaten Schlüssel" ist zwar anschaulich, aber in der Sache falsch: Die beiden Fälle verwenden unterschiedliche und nicht austauschbare Auffüllverfahren. Signiert wird außerdem nicht die Nachricht, sondern ihr Hashwert — siehe SHA-256.

Padding ist kein Beiwerk

Die reine Rechenoperation ist unsicher. Sie ist deterministisch, dieselbe Nachricht ergibt also stets denselben Geheimtext, und sie hat mathematische Eigenschaften, die sich ausnutzen lassen. Deshalb wird jede Nachricht vor der Rechnung nach einem festen Schema aufgefüllt — und die Wahl dieses Schemas entscheidet über die Sicherheit:

Dass das kein theoretischer Punkt ist, zeigt eine Angriffsfamilie, die 1998 von Daniel Bleichenbacher eröffnet wurde. Sie nutzt aus, dass ein Server durch Fehlermeldungen oder Laufzeitunterschiede verrät, ob das Padding eines eingereichten Geheimtextes gültig war. Aus vielen solcher Einzelauskünfte lässt sich der Klartext rekonstruieren.

Der Angriff ist seither mehrfach zurückgekehrt, weil die Gegenmaßnahmen schwer korrekt umzusetzen sind — 2017 unter dem Namen ROBOT in den Produkten mehrerer großer Hersteller.

Schlüssellängen

1024 Bit gelten als überholt, ab 2048 Bit beginnt der heute vertretbare Bereich. Teil 1 der Technischen Richtlinie BSI TR-02102 nennt 3000 Bit als Mindestlänge für neue Anwendungen mit längerem Verwendungszeitraum.

Die Längen wachsen unverhältnismäßig: Für das Sicherheitsniveau von AES-256 bräuchte RSA über 15.000 Bit. Das ist der eigentliche Grund für den Rückzug des Verfahrens — nicht ein Bruch, sondern die schlechte Skalierung. Eine elliptische Kurve erreicht dasselbe mit 512 Bit.

Spürbar wird das beim Signieren und Entschlüsseln, also den Operationen mit d, die ein Vielfaches der Rechenzeit der Gegenrichtung brauchen. Auf einem Webserver trifft das genau die Seite, die unter Last steht.

Wo RSA heute noch steht

In TLS hat sich die Rolle grundlegend verschoben. Bis TLS 1.2 konnte RSA den Sitzungsschlüssel direkt übertragen — der Client verschlüsselte ihn mit dem öffentlichen Schlüssel aus dem Serverzertifikat. Dieses Verfahren hat einen schwerwiegenden Nachteil: Wer den privaten Serverschlüssel später erlangt, kann aufgezeichneten Verkehr rückwirkend entschlüsseln.

TLS 1.3 hat es deshalb vollständig entfernt. Die Schlüsseleinigung läuft ausschließlich über Diffie-Hellman, womit Perfect Forward Secrecy nicht mehr optional ist. RSA bleibt dort nur noch als Signaturverfahren, mit dem sich der Server ausweist.

Verbreitet ist RSA weiterhin bei Serverzertifikaten, in SSH-Schlüsseln, bei S/MIME und OpenPGP sowie überall, wo lange Produktlebenszyklen einen Wechsel verzögern. Bei Neueinrichtungen ist eine elliptische Kurve die naheliegendere Wahl.

Fehlerbilder aus der Praxis

Gebrochen wurde RSA nie durch Faktorisierung eines ordentlich erzeugten Schlüssels — wohl aber durch Fehler bei der Erzeugung:

Fehlende Entropie. Reihenuntersuchungen öffentlicher Schlüssel haben wiederholt gezeigt, dass eingebettete Geräte ohne Entropiequelle beim ersten Start dieselben oder überlappende Primzahlen wählen. Teilen zwei Schlüssel einen Faktor, lassen sich beide sofort brechen.

Der Debian-Fehler 2008. Eine Änderung am Zufallszahlengenerator von OpenSSL reduzierte den Schlüsselraum auf wenige zehntausend Möglichkeiten. Alle in diesem Zeitraum erzeugten Schlüssel ließen sich vollständig durchprobieren und mussten ausgetauscht werden.

ROCA 2017. Eine fehlerhafte Primzahlerzeugung in weit verbreiteten Sicherheitschips erlaubte es, den privaten Schlüssel aus dem öffentlichen zu berechnen. Betroffen waren auch Ausweisdokumente.

Das Muster ist in allen drei Fällen dasselbe: Nicht die Mathematik gab nach, sondern die Erzeugung.

Der Quantenrechner

RSA ist von der Entwicklung besonders unmittelbar betroffen. Der Shor-Algorithmus faktorisiert effizient; eine Vergrößerung der Schlüssellänge hilft dagegen nicht, weil sich der Aufwand des Angriffs nicht entsprechend erhöht.

Für vertrauliche Übertragung ist das die drängendere Baustelle, weil heute aufgezeichneter Verkehr später entschlüsselt werden kann. Bei Signaturen ist die Frist großzügiger: Eine Signatur, die zum Zeitpunkt ihrer Prüfung gültig war, verliert ihren Wert nicht rückwirkend. Siehe Post-Quantum-Kryptografie.