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