RSA (Schritt-für-Schritt)
Das verbreitetste moderne asymmetrische Verfahren RSADieses Modul demonstriert schrittweise die Ver- und Entschlüsselung mit dem RSA-Verfahren. Der Sender verwendet dabei zum Verschlüsseln den öffentlichen Schlüssel des Empfängers; der Empfänger verwendet zum Entschlüsseln seinen zugehörigen privaten Schlüssel.
Primzahlen
Die Sicherheit von RSA basiert darauf, dass es zwar einfach ist, das Produkt n zweier großer Primzahlen p und q zu berechnen. Es ist jedoch sehr schwer, nur aus dem Produkt n die beiden Primzahlen zu bestimmen, die das Produkt ergeben. Dieses Zerlegen nennt man auch das Faktorisieren von n.
Als Ausgangspunkt für RSA wählt man zwei Primzahlen p und q.
Damit der Algorithmus funktioniert, müssen die beiden Primzahlen verschieden sein.
Öffentlicher Schlüssel
Das Produkt n wird im RSA-Verfahren auch Modulus genannt.
n = p × q = ( bit)
Zur Demonstration beginnen wir mit kleinen Primzahlen. Um die Faktorisierung schwierig zu gestalten, müssen die Primzahlen viel größer gewählt werden. Aktuell werden für eine sichere Kommunikation Werte von n mit mehreren tausend Binärstellen verwendet.
Der öffentliche Schlüssel besteht neben dem Modulus n noch aus einem Exponenten e.
Dieses e kann sogar vorab gewählt werden und für alle Teilnehmer gleich sein.
Geheimer Schlüssel
RSA benutzt für die Berechnung des geheimen Schlüssels die Eulersche φ-Funktion von n. Diese ist definiert als
φ(n) = (p − 1) × (q − 1) =
Hier wird ausgenutzt, dass p und q verschieden sind. Andernfalls würde sich die φ-Funktion anders berechnen.
Wichtig ist für RSA, dass der Wert der φ-Funktion teilerfremd zu e ist (der größte gemeinsame Teiler also 1 ist).
ggT(e, φ(n)) =
Um den Wert von φ(n) zu bestimmen, reicht es nicht aus n zu kennen. Nur mit der Kenntnis von p und q kann man φ(n) effizient bestimmen.
Der geheime Schlüssel besteht aus einem d mit der Eigenschaft, dass e × d − 1 ein Vielfaches von φ(n) ist.
In Formeln ausgedrückt, muss gelten:
e × d = 1 (mod φ(n))
Dabei ist mit dem mod-Ausdruck die Gleichheit bezüglich einer Restklasse gemeint. Es ist genau dann x =y (mod z), wenn es ein ganzzahliges a gibt mit x − y = z × a.
Für die gewählten Werte von p, q und e ergibt sich d als:
d =
Dieses d kann immer bestimmt werden, wenn e mit der oben beschriebenen Einschränkung gewählt wurde – bspw. mit dem Erweiterten Euklidischen Algorithmus.
Ver- und Entschlüsseln
Grundsätzlich werden bei diesem Verfahren keine Texte, sondern nur Zahlen ver- und entschlüsselt, die zwischen 0 und n − 1 liegen.
Um eine Nachricht m mit dem öffentlichen Schlüssel (n, e) zu verschlüsseln, wird
m' := me (mod n)
berechnet.
Das Entschlüsseln mit dem privaten Schlüssel (n, d) erfolgt analog mit
m'' := (m')d (mod n).
Damit ist
m'' = me × d (mod n).
RSA nutzt die Eigenschaft aus, dass
xa = xb (mod n)
wenn
a = b (mod φ(n))
e und d wurden passend gewählt, dass
m'' = m.
Die Reihenfolge spielt keine Rolle. Man könnte auch erst eine Nachricht mit dem privaten Schlüssel potenzieren, und das Ergebnis dann mit dem öffentlichen Schlüssel potenzieren – das verwendet man bei RSA-Signaturen.
Nachrichten
In den folgenden zwei Textboxen 'Klartext' und 'Geheimtext' können Sie sehen, wie das Ver- und Entschlüsseln für konkrete Eingaben (Zahlen) funktioniert.
Verwendete Bibliothek
Diese Seite verwendet für die Rechnung mit großen Zahlen die Bibliothek BigInteger.js.
Dadurch kann man auch in JavaScript mit beliebig großen Zahlen rechnen, also auch solchen, die real bei RSA-Anwendungen verwendet werden.
Hier ist zu Lernzwecken RSA in Reinform ("Textbook-RSA") implementiert. In der Realität wird vor der Verschlüsselungsoperation gepadded und es wird Hybridverschlüsselung eingesetzt: Mit RSA verschlüsselt man beispielsweise den Sessionkey, der dann als symmetrischer Schlüssel für die eigentlichen Daten benutzt wird.
Die Sicherheit von RSA beruht darauf, dass es nach heutigem Stand nicht möglich ist, das Produkt von zwei großen Primzahlen in einer sinnvollen Zeit zu faktorisieren. Dies ist jedoch nur eine begründete Annahme, aber keine gesicherte Erkenntnis: Es ist bisher lediglich noch kein schnelles Verfahren bekannt. Wir wissen nicht, ob die Faktorisierung mindestens so schwer ist wie andere schwere Probleme, ob sie also NP-vollständig ist.
Anmerkung: Eine visuelle Darstellung von RSA finden Sie im Plugin RSA visuell und mehr.
Beispiel-Eingaben
Als Eingabe kann eine oder mehrere natürliche Zahlen verwendet werden die nicht größer als der Modulus werden dürfen. Wenn der Modulus größer als 255 ist, kann auch Text direkt eingegeben werden. Dieser wird in Bytes mit der UTF-8 Codierung umgewandelt. Es werden so viele Bytes wie möglich als dreistellige Dezimalzahlen zu Eingabezahlen zusammengefasst.
a) Wenn die Parameterp=11, q=13, n=143, e=23 und d=47 gegeben sind, können die drei Zahlen 6, 13, 111 als Klartext eingegeben werden. Das Plugin errechnet direkt als Geheimtext die Zahlen 128, 52, 67. Umgekehrt können auch mehrere Zahlen als Geheimtext eingegeben werden. Der Pfeil dreht sich nach oben und die entschlüsselten Zahlen werden als Klartext angezeigt.
b) Wenn der Modulus größer als 255 ist, erscheint ein zusätzliches Eingabe-Feld "Klartext (als Text eingeben)". Zeichen, die in dieses Feld eingegeben werden, werden in Zahlen umgewandelt, die im Klartext erscheinen. Auch beim Entschlüsseln wird der erzeugte Klartext in reinen Text umgewandelt, wenn die Codierung valide ist.
Angriff mit Quantencomputern
Prinzip-bedingt kann ein Quantencomputer mit hinreichend vielen verschränkten Quanten-Bits (Qubits) eine Faktorisierung schnell durchführen, da er parallel jeden möglichen Faktor gleichzeitig ausprobieren kann. Bisher gibt es jedoch keinen bekannten Quantencomputer, der eine auch nur annähernd große Rechenkapazität hat. Damit bleiben effektive Quantencomputer momentan ein Mythos, der wohl auch in den nächsten Jahren noch nicht serienreif werden wird. Es kann jedoch sein, dass die Faktorisierung in 20 Jahren gelöst ist und RSA damit seine Sicherheit verliert.
Größe der Primfaktoren
Je größer die verwendeten Primfaktoren sind, desto länger benötigen aktuelle Algorithmen und desto mehr Qubits werden in zukünftigen Quantencomputern benötigt. Momentan sollte das Produkt (der Modulus) aus mindestens 4096 Binärstellen bestehen, um sicher zu sein.
Wiederverwendung von Primzahlen
Primzahlen dürfen nicht wiederverwendet werden! Wenn man zwei Produkte aus je zwei Primzahlen hat und weiß, dass eine der verwendeten Primzahlen die gleiche ist, dann kann diese sog. Shared Prime mit dem Euklidischen Algorithmus schnell ermittelt werden. Und durch Division der Produkte durch diese "shared" Primzahl erhält man jeweils die andere Primzahl.
Frühe Implementierungen von RSA haben diesen Fehler begangen, um die Zeit für das aufwändige Finden einer Primzahl zu reduzieren. Auch auf Ressourcen-beschränkten Geräten kam es in neuerer Zeit aufgrund von mangelndem Zufall dazu. Aktuelle Implementierungen sollten diesen Fehler nicht mehr begehen.
Wahl der Primzahlen
Grundsätzlich müssen die Primzahlen zufällig genug ausgewählt werden. Wenn für eine n-bit Zahl nur n/2-bit Zahlen herangezogen werden, reduziert das den Suchraum für Angreifer erheblich. Es darf aber auch keine der beiden Primzahlen zu klein sein, um bei einem Brute-Force-Angriff mit allen Primzahlen nicht zu einem frühen Treffer zu kommen. Eine geschickte Wahl zwischen beiden Extremen ist notwendig und nicht trivial. Die beiden Primzahlen sollten also nicht zu nah beieinander liegen, aber auch nicht zu weit auseinander.
Weitere RSA-Implementierungen im Browser
https://www.cs.drexel.edu/~jpopyack/Courses/CSP/Fa17/notes/10.1_Cryptography/RSAWorksheetv4e.html
Hier sieht der Nutzer ebenfalls, wie (N, e, d) gewählt werden kann und wie Textnachrichten in Zahlen ersetzt werden.
Hier kann man die Nachricht als Text eingeben (es wird angenommen, dass der Benutzer N, e und d schon gewählt hat).
Beide Implementierungen sind aus 2012, nur in Englisch, benutzen keine Langzahl-Arithmetik-Bibliothek (sondern pures Java Script), und sehen didaktisch sehr gut aus.