RSA-Verfahren
Arbeitsgrundlage: Krypto Skript 22 - RSA.docx
a) Konstruktion der Schlüssel
- Schritt 1: Nimm zwei (sehr, sehr große) Primzahlen p und q.
Der öffentliche Schlüssel wird verteilt, der private geheim gehalten. Wer den privaten Schlüssel besitzt, kann Nachrichten empfangen.
- Schritt 2: Bilde das RSA-Modul N = p · q.
- Schritt 3: Bestimme φ(N) = φ(p · q) = φ(p) · φ(q) = (p − 1) · (q − 1) (eulersche φ-Funktion)
- Schritt 4: Wähle eine Zahl e mit 1 < e < φ(N) und ggT(e, φ(N)) = 1.
Jetzt bilden (e, N) den öffentlichen Schlüssel. Geheim bleiben p, q und φ(N).
- Schritt 5: Modulo φ(N) gerechnet hat e ein Inverses. Bestimme d mit e · d ≡ 1 (mod φ(N)) über den erweiterten euklidischen Algorithmus.
Jetzt bilden (d, N) den privaten Schlüssel.
b) Ver- und Entschlüsselung
Der Klartext wird blockweise in Zahlen umgewandelt.
| Verschlüsselung | c = me mod N |
|---|---|
| Entschlüsselung | m = cd mod N |
Details zur blockweisen Verschlüsselung folgen in einem späteren Kapitel. Wichtig ist schon jetzt: Jede Zahl m muss kleiner als N sein.
Exkursion: Beweis der Funktionalität
c) RSA-Beispiel
Konstruiert Schritt für Schritt ein Schlüsselpaar zu den beiden Primzahlen p = 7 und q = 11. Jede Lücke wird einzeln geprüft; die nächste erscheint erst, wenn die aktuelle stimmt. Das ? neben einer Lücke zeigt die Berechnungsvorschrift.
Schlüsselpaar zu p = 7 und q = 11 bestimmen
Die Zahl e ist im Kurs auf 13 festgelegt: Trage bei Schritt 4 eine zu φ(N) teilerfremde Zahl ein und rechne anschließend mit e = 13 weiter.
Ausprobieren: der Rechner zum eben bestimmten Schlüsselpaar
Trage k und N selbst ein – zum Verschlüsseln den öffentlichen Schlüssel (e, N), zum Entschlüsseln den privaten (d, N). Verschlüssle eine Zahl, stelle dann auf Entschlüsseln um, übertrage das Ergebnis und sieh nach, ob die Ausgangszahl wieder herauskommt.
| Zahl | Rechnung | Ergebnis |
|---|
Merke
Der öffentliche Schlüssel e und der private Schlüssel d stehen zwar in einem mathematischen Zusammenhang, lassen sich ohne Kenntnis von p, q oder φ(N) aber nicht in annehmbarer Zeit gegenseitig berechnen.
Weitere Aufgaben
Aufgabe 1: Schlüssel zu p = 53 und q = 97
Zwei Teilnehmer legen sich auf die Primzahlen p = 53 und q = 97 fest. Wählt e möglichst klein, berechnet d und verschlüsselt anschließend den Geheimcode 3539.
Aufgabe 2: Den geheimen Schlüssel aus dem öffentlichen berechnen
Ein Bote eines Geheimdienstes entdeckt als öffentlichen Schlüssel einer geheimen Nachricht N = 21 und e = 5. Wie lautet der geheime Schlüssel d?
Rechner für Aufgabe 3
Stelle auf Entschlüsseln und trage dein d aus Aufgabe 2 und N = 21 ein. Der Rechner nimmt immer nur eine Zahl: Entschlüssle die vier Geheimzahlen nacheinander und trage die Ergebnisse unten in die Lücke ein.
| Zahl | Rechnung | Ergebnis |
|---|
Aufgabe 3: Den Code entschlüsseln
Ein verschlüsselter Code lautet 1 11 12 16. Wie lautet der Originalcode, wenn wie in Aufgabe 2 verschlüsselt wurde? Verwende N = 21 und dein d aus Aufgabe 2.
Aufgabe 4: Der Bote fängt kurze Zeit später eine weitere Nachricht ab. e wurde wieder als e = 5 gewählt, N ist diesmal jedoch N = 1062646162893167618721054113099. Bestimmen Sie den privaten Schlüssel d und erläutern Sie an diesem Beispiel die Sicherheit des RSA-Verfahrens.