RSA erklärt

Jedes Mal, wenn ein Browser ein Vorhängeschloss anzeigt, eine Nachricht signiert wird oder Software ein Update prüft, ist Public-Key-Kryptografie am Werk, und RSA ist ihre bekannteste Form. Die Idee dahinter: Der Schlüssel, der eine Nachricht verschließt, kann veröffentlicht werden, während der Schlüssel, der sie öffnet, privat bleibt. Bemerkenswerterweise beruht das ganze System auf Rechnen, wie es in der Schule gelehrt wird: Primzahlen, Multiplikation und Reste.

Die geheimen Primzahlen 61 und 53 ergeben den öffentlichen Modul 3233. Die Buchstaben von HELLO werden mit dem öffentlichen Exponenten 17 zu 3000, 28, 2726, 2726 und 1307, und der private Exponent 2753 macht aus 3000 wieder 72
Die geheimen Primzahlen 61 und 53 ergeben den öffentlichen Modul 3233. Die Buchstaben von HELLO werden mit dem öffentlichen Exponenten 17 zu 3000, 28, 2726, 2726 und 1307, und der private Exponent 2753 macht aus 3000 wieder 72

Das Problem, das RSA löst

Ältere Verschlüsselungen, von der Caesar-Verschiebung bis zum modernen AES, verwenden denselben Schlüssel zum Ver- und Entschlüsseln, also müssen beide Seiten zuerst im Geheimen einen gemeinsamen Schlüssel austauschen. Die Public-Key-Kryptografie macht diesen Schritt überflüssig. Jede Person hat zwei Schlüssel: einen öffentlichen Schlüssel, mit dem jeder Nachrichten an sie verschlüsseln darf, und einen privaten Schlüssel, den nur sie besitzt und der als einziger die Nachrichten entschlüsseln kann. Whitfield Diffie und Martin Hellman beschrieben die Idee 1976, und ein Jahr später fanden Ron Rivest, Adi Shamir und Leonard Adleman am MIT einen Weg, sie umzusetzen, der nach ihren Initialen RSA benannt wurde.

Martin Hellman (links) und Whitfield Diffie (rechts), 1977
Martin Hellman (links) und Whitfield Diffie (rechts), 1977

Die Schlüssel erzeugen

Wählen Sie zwei große Primzahlen p und q und multiplizieren Sie sie: n = p × q. Berechnen Sie φ(n) = (p − 1)(q − 1), die eulersche Phi-Funktion, die die zu n teilerfremden Zahlen unterhalb von n zählt. Wählen Sie einen öffentlichen Exponenten e, der zu φ(n) teilerfremd ist; 65537 ist die übliche Wahl. Bestimmen Sie dann den privaten Exponenten d so, dass e × d bei Division durch φ(n) den Rest 1 lässt. Der erweiterte euklidische Algorithmus erledigt das schnell. Der öffentliche Schlüssel ist das Paar (e, n); der private Schlüssel ist d. Mit p = 61 und q = 53 ergibt das n = 3233, φ(n) = 3120, e = 17 und d = 2753.

Verschlüsseln und Entschlüsseln

Eine Nachricht wird zuerst in eine Zahl m kleiner als n umgewandelt. Zum Verschlüsseln berechnet man c = mᵉ mod n, den Rest von mᵉ bei Division durch n. Zum Entschlüsseln berechnet man cᵈ mod n. Der Satz von Euler garantiert, dass sich so wieder m ergibt, denn e × d ist um 1 größer als ein Vielfaches von φ(n). Mit den Schlüsseln oben wird der Buchstabe A, Code 65, zu 65¹⁷ mod 3233 = 2790, und 2790²⁷⁵³ mod 3233 ergibt wieder 65. So große Potenzen werden nie ausgeschrieben: Wiederholtes Quadrieren berechnet sie mit einer Quadrierung pro Bit des Exponenten und nimmt bei jedem Schritt den Rest.

Digitale Signaturen

RSA funktioniert auch umgekehrt. Potenziert man eine Nachricht mit dem privaten Exponenten, s = mᵈ mod n, entsteht eine Signatur, die nur der Inhaber des Schlüssels erzeugen kann. Jeder kann sie mit dem öffentlichen Schlüssel prüfen: Ergibt sᵉ mod n wieder m, stammt die Nachricht vom Inhaber von d und wurde unterwegs nicht verändert. In der Praxis wird statt der Nachricht selbst ein kurzer Hashwert der Nachricht signiert. Solche Signaturen schützen Software-Updates, sichere Websites und elektronische Dokumente.

Warum es sicher ist

Jeder kann n und e sehen. Um d zu finden, braucht ein Angreifer φ(n), und um φ(n) zu finden, braucht er p und q, also läuft das Knacken von RSA auf das Faktorisieren von n hinaus. Zwei Primzahlen zu multiplizieren dauert für einen Computer den Bruchteil einer Mikrosekunde; das Produkt wieder in sie zu zerlegen gilt als extrem schwer. Die größte bisher faktorisierte RSA-Challenge-Zahl, RSA-250 im Jahr 2020, hat 829 Bit und erforderte etwa 2700 Jahre Rechenzeit. Heute verwendete Schlüssel haben mindestens 2048 Bit, etwa 617 Stellen.

Ein Geheimnis, zweimal entdeckt

1973, vier Jahre vor RSA, fand der britische Mathematiker Clifford Cocks dasselbe Verfahren, während er beim Nachrichtendienst GCHQ arbeitete, aufbauend auf einer Idee seines Kollegen James Ellis. Die Arbeit war geheim und wurde erst 1997 öffentlich gemacht. RSA selbst wurde 1983 in den Vereinigten Staaten patentiert; das Patent lief im September 2000 aus, zwei Wochen nachdem der Algorithmus zur freien Nutzung freigegeben worden war.

Ron Rivest, Adi Shamir und Len Adleman (von links nach rechts)
Ron Rivest, Adi Shamir und Len Adleman (von links nach rechts)

RSA in der Praxis

Echtes RSA verschlüsselt Text nie direkt. Die Nachricht wird mit einem Verfahren wie OAEP mit zufälligen Bytes aufgefüllt, sodass dieselbe Nachricht jedes Mal anders verschlüsselt wird und keine Muster durchsickern können. Weil RSA langsam ist, wird es meist dazu verwendet, einen kurzen Schlüssel für eine schnelle symmetrische Verschlüsselung wie AES auszutauschen oder zu schützen, oder zum Signieren. Ausreichend große Quantencomputer könnten n mit Shors Algorithmus von 1994 schnell faktorisieren, weshalb neue Post-Quanten-Verfahren parallel zu RSA eingeführt werden.

Selbst ausprobieren

Öffnen Sie die Demo zur RSA-Verschlüsselung, um Schlüssel aus eigenen oder zufälligen Primzahlen mit 2 bis 8 Stellen zu erzeugen, zu sehen, wie der erweiterte euklidische Algorithmus d Zeile für Zeile findet, eine Nachricht Zeichen für Zeichen zu verschlüsseln oder zu signieren und das wiederholte Quadrieren für jedes Zeichen zu verfolgen. Lassen Sie dann Eve n faktorisieren und beobachten Sie, wie die Zeit, die sie braucht, mit der Größe der Primzahlen wächst.

Häufig gestellte Fragen

Warum braucht RSA Primzahlen?

Weil sich φ(n) nur dann leicht berechnen lässt, wenn man weiß, wie n in Primzahlen zerfällt. Für n = p × q mit Primzahlen p und q ist φ(n) = (p − 1)(q − 1). Primzahlen machen n außerdem für seine Größe so schwer wie möglich zu faktorisieren, da es überhaupt keine kleinen Faktoren hat.

Warum ist e oft 65537?

65537 = 2¹⁶ + 1 ist eine Primzahl und hat binär nur zwei Einsen, sodass das Verschlüsseln damit nur 16 Quadrierungen und eine Multiplikation erfordert. Außerdem ist sie groß genug, um Schwächen sehr kleiner Exponenten wie 3 zu vermeiden.

Was ist der Unterschied zwischen RSA und Diffie–Hellman?

Mit Diffie–Hellman können sich zwei Personen über einen offenen Kanal auf einen gemeinsamen geheimen Schlüssel einigen; es verschlüsselt oder signiert selbst nichts. RSA verschlüsselt und signiert direkt mit einem Schlüsselpaar. Beide beruhen auf Problemen, die in eine Richtung leicht und in die andere schwer sind: der Faktorisierung bei RSA, dem diskreten Logarithmus bei Diffie–Hellman.

Lassen sich die Schlüssel der Demo für echte Verschlüsselung verwenden?

Nein. Ihre Primzahlen haben höchstens ein Dutzend Stellen, sodass sich jeder erzeugte Schlüssel in Sekunden oder schneller faktorisieren lässt, und sie verschlüsselt jedes Zeichen einzeln ohne Padding. Sie soll zeigen, wie RSA funktioniert, und ist nicht dafür gedacht, irgendetwas zu schützen.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Demo zur RSA-Verschlüsselung öffnen