RSA-Verfahren
Voraussetzung: Primzahlen
- zwei verschiedene, geheime Primzahlen
- RSA-Modul, das Produkt p · q, öffentlich
- Eulersche φ-Funktion von n, hier (p − 1)(q − 1), geheim
- öffentlicher Exponent, teilerfremd zu φ(n)
- privater Exponent, Inverses von e modulo φ(n)
- Klartext als Zahl von 0 bis n − 1
- Geheimtext, ebenfalls eine Zahl von 0 bis n − 1
Beim RSA-Verfahren verschlüsselt man mit c = mᵉ mod n und entschlüsselt mit m = cᵈ mod n, wobei e·d ≡ 1 modulo φ(n) gilt.
Erklärung
RSA ist ein asymmetrisches Verschlüsselungsverfahren: Jeder darf mit dem öffentlichen Schlüssel verschlüsseln, entschlüsseln kann nur, wer den privaten Schlüssel kennt.
Schlüsselerzeugung:
- Zwei große, verschiedene Primzahlen und wählen und bilden.
- berechnen.
- Einen Exponenten mit und wählen (in der Praxis meist ).
- als Inverses von modulo mit dem erweiterten euklidischen Algorithmus bestimmen.
Öffentlich sind und ; geheim bleiben , , und . Die Potenzen berechnet man mit schnellem modularem Potenzieren.
Warum es funktioniert: Wegen für eine ganze Zahl gilt
Für folgt das direkt aus dem Satz von Euler. Mit dem chinesischen Restsatz zeigt man, dass es auch für die übrigen gilt, weil quadratfrei ist.
Sicherheit: Wer in und zerlegen kann, berechnet und damit . Für große (heute mindestens 2048 Bit) ist kein effizientes Verfahren dafür bekannt. Das reine „Lehrbuch-RSA“ aus der Formel ist trotzdem unsicher, weil gleiche Klartexte gleiche Geheimtexte ergeben; in der Praxis wird der Klartext vorher zufällig aufgefüllt (Padding).
Signieren funktioniert umgekehrt: Die Signatur ist , jeder prüft mit .
Beispiele
Schlüssel: , , also und . Gewählt wird , denn . Erweiterter euklidischer Algorithmus:
Also , Probe: .
Verschlüsseln von :
Entschlüsseln: Wegen ist
Der Klartext ist zurück. Auch , das nicht zu teilerfremd ist, wird korrekt zurückgewonnen.
Signieren von : . Prüfung: .
Typische Fehler
- modulo statt modulo bestimmen. Die Bedingung lautet .
- setzen. Das gilt nur für Primzahlen; für ist , im Beispiel , nicht .
- nicht teilerfremd zu wählen. Für und gibt es kein Inverses .
- Klartexte verschlüsseln. Sie lassen sich nicht eindeutig zurückgewinnen, weil nur der Rest modulo übrig bleibt.