Einstieg
Ein Schlüssel, den alle sehen dürfen?
Ausgangslage
Alice will Bob eine geheime Nachricht schicken. Die beiden haben sich nie getroffen und konnten nichts verabreden. Alles, was sie verschicken, kann Eve mitlesen.
Bob stellt seinen Schlüssel offen ins Internet. Kann Alices Nachricht trotzdem sicher bei ihm ankommen?
Ja – mit zwei verschiedenen Schlüsseln. Der öffentliche schließt nur zu, der private schließt auf. So arbeitet RSA, erfunden 1977.
Wie kann es so ein Schlüsselpaar geben?
Station 1 · Bild
Bob verschickt ein offenes Schloss
Auftrag: Klickt Schritt für Schritt weiter. Vermutet vorher: Wer kann die Kiste unterwegs öffnen?
1/5
Wer kann die Kiste unterwegs öffnen?
Nur Bob. Zuschließen kann jeder, aufschließen nur, wer den Schlüssel hat.
öffentlicher Schlüssel = das offene Schloss. privater Schlüssel = Bobs Schlüssel.
Am Computer sind Schloss und Schlüssel Zahlen. Wie rechnet man damit?
Station 2 · Werkzeug
Rechnen mit Rest, wie auf der Uhr
Auftrag: Rechnet erst im Kopf, dann mit dem Rechner prüfen.
9 Uhr + 5 Stunden = 2 Uhr.
14 : 12 = 1 Rest 2
Kurz geschrieben:
14 mod 12 = 2
mod heißt: Teile und schreibe nur den Rest auf.
40 = 1 · 33 + 7
Was ist 17 mod 5?
17 = 3 · 5 + 2. Der Rest ist 2. Die 3 sagt, wie oft die 5 hineinpasst – die braucht man hier nicht.
Trick: Große Potenzen bleiben klein
Nach jedem Malnehmen gleich den Rest nehmen. Beispiel 73 mod 33:
| Schritt | rechnen | Rest mod 33 |
|---|---|---|
| 71 | 7 | 7 |
| 72 | 7 · 7 = 49 | 16 |
| 73 | 16 · 7 = 112 | 13 |
Station 3 · Bob
Bob baut sein Schlüsselpaar
Auftrag: Rechnet jeden Schritt erst selbst, dann aufdecken. Danach eigene Primzahlen wählen.
- ①Zwei Primzahlen malnehmen: n = 3 · 11 = 33öffentlich
- ②Hilfszahl: m = (3 − 1) · (11 − 1) = 20geheim
- ③e ohne gemeinsamen Teiler (außer 1) mit m: e = 3öffentlich
- ④d so, dass e · d mod m = 1: d = 7, denn 3 · 7 = 21 = 1 · 20 + 1privat
p, q und m braucht Bob danach nicht mehr. Er hält sie geheim oder löscht sie.
Eigene Primzahlen wählen
p und q verschieden, n größer als 26, damit jeder Buchstabe A = 1 … Z = 26 hineinpasst. Sonst passt die Tafel die andere Zahl an.
e auswählen
Die nächsten Stationen rechnen mit diesem Schlüssel. Zurück zum Beispiel: p = 3, q = 11, e = 3.
Station 4 · Alice
Alice verschlüsselt mit dem öffentlichen Schlüssel
Auftrag: Rechnet den ersten Buchstaben selbst. Vermutet: Was passiert mit den beiden E in GEHEIM?
Alice schickt nur die blauen Zahlen:
Was passiert mit den beiden E in GEHEIM?
Gleicher Buchstabe, gleiche Zahl. Buchstabe für Buchstabe ist RSA nur eine feste Ersetzung, wie bei Cäsar mit Buchstabenhäufigkeit zu knacken.
Echte Programme verschlüsseln darum eine einzige große Zahl mit Zufallsanteil, meist nur einen Schlüssel für AES.
Station 5 · Bob
Bob entschlüsselt mit dem privaten Schlüssel
Auftrag: Vermutet zuerst: Kann Eve mit dem öffentlichen e zurückrechnen? Dann beide Knöpfe ausprobieren.
Rechenweg für die erste Zahl
137 mod 33: siebenmal mit 13 malnehmen, nach jedem Schritt den Rest nehmen.
Warum klappt das?
e und d sind so gewählt, dass sie sich gegenseitig aufheben: Hochnehmen mit e, dann mit d, ergibt wieder die Zahl vom Anfang. Das gilt für jede Zahl kleiner als n. Der Beweis stützt sich auf einen Satz von Leonhard Euler (18. Jahrhundert).
Eve kennt n und e. Um d zu finden, bräuchte sie m – und dafür p und q.
Station 6 · Eve
Eve versucht, n zu zerlegen
Auftrag: Schätzt vor jedem Klick: Wie lange braucht der Rechner? Startet dann die Maschine.
Zerlege-Maschine: Sie probiert 2, 3, 5, 7, 9, … der Reihe nach, bis eine Zahl n ohne Rest teilt.
33
- Stellen
- 2
- Ergebnis
- –
- Versuche
- –
- Zeit
- –
Hat Eve p und q, hat sie alles
Aus 33 = 3 · 11 rechnet Eve m = 2 · 10 = 20 und daraus d = 7 – genau wie Bob in Station 3.
Bei kleinen Zahlen geht das sofort. Wie ändert sich die Zeit, wenn n mehr Stellen hat?
Diese Maschine ist absichtlich einfach. Es gibt viel schnellere Verfahren. Auch die werden mit jeder Stelle mehr langsamer, nur nicht so stark.
Station 7 · Größenordnung
Wie groß ist n bei echten Schlüsseln?
Auftrag: Entscheidet euch zuerst, dann auflösen und die Tabelle lesen.
| Stellen von n | Versuche mit der Maschine | Was man weiß |
|---|---|---|
| 2 | 2 | n = 33: sofort, im Kopf. |
| 16 | ≈ 25 Millionen | Station 6: höchstens Sekunden. |
| 40 | ≈ 1020 | Mit der Maschine Tausende Jahre, mit besseren Verfahren Sekunden. |
| 250 | ≈ 10125 | Rekord 2020 mit dem besten bekannten Verfahren: rund 2700 Kernjahre*. |
| 617 | ≈ 10308 | RSA mit 2048 Bit, weit verbreitet: nach heutigem Wissen nicht zu schaffen. |
| 925 | ≈ 10462 | 3072 Bit. Das BSI empfiehlt mindestens 3000 Bit. |
* ein Rechenkern 2700 Jahre lang, verteilt auf viele Rechner. Im September 2026 wurde auch die 260-stellige Prüfzahl RSA-260 zerlegt; wie, ist nicht veröffentlicht. Versuche für n aus zwei etwa gleich großen Primzahlen.
Ein n mit 12 Stellen braucht rund 185 000 Versuche. Wie viele braucht ein n mit 24 Stellen?
Eine Million Mal. Die Maschine probiert bis zur Wurzel von n. 12 Stellen mehr bei n sind 6 Stellen mehr bei der Wurzel: 106.
Dass es keinen schnellen Weg gibt, ist nicht bewiesen. Man kennt nur keinen.
Station 8 · Ausblick
Umgekehrt: die digitale Unterschrift
Auftrag: Woher weiß Alice, dass eine Nachricht wirklich von Bob kommt? Probiert Bobs Unterschrift und Eves Fälschung aus.
| Bob unterschreibt mit seinem privaten d | s = 77 mod 33 = 28 |
| Alle prüfen mit dem öffentlichen e | 283 mod 33 = 7 ✓ echt |
| Eve rät eine Unterschrift | – |
Ohne d kann Eve keine passende Unterschrift berechnen. Raten klappt nur zufällig – bei echten Schlüsseln praktisch nie.
So wird es benutzt
- Unterschrieben wird nicht der ganze Text, sondern sein Hashwert (Tafel Hashwerte).
- Software-Updates sind unterschrieben. Das Handy prüft vor dem Einspielen.
- Webseiten mit https zeigen ein Zertifikat: Eine Prüfstelle hat unterschrieben, dass dieses Schloss wirklich zur Seite gehört.
Das löst eine Lücke aus Station 1: Eve könnte Alice ihr eigenes Schloss schicken und behaupten, es sei Bobs. Ein Zertifikat verrät den Schwindel.
Station 9 · Ausblick
Knacken Quantencomputer RSA?
Auftrag: Lest die Schlagzeile. Stimmt sie? Entscheidet, dann auflösen.
„Quantencomputer knacken jetzt jede Verschlüsselung!“
Die Schlagzeile übertreibt. Die Gefahr ist echt, aber sie liegt in der Zukunft. Darum stellt man schon heute um.
1994 Ein Rechenweg auf Vorrat
Peter Shor zeigt: Ein großer Quantencomputer mit Fehlerkorrektur könnte n schnell zerlegen. Damit wären RSA-Schlüssel und RSA-Unterschriften unsicher.
heute Noch weit entfernt
Mit Shors Verfahren wurden auf echten Geräten nur winzige Zahlen wie 15 und 21 zerlegt, und nur mit Vorwissen über die Lösung. Eine Schätzung von 2025: Für 2048 Bit bräuchte man knapp eine Million Qubits und bis zu eine Woche Rechenzeit.
2024 Vorsorge
Neue Verfahren, die auch Quantencomputern standhalten sollen, sind genormt (NIST). Die Umstellung hat begonnen, weil Angreifer Daten heute speichern und später entschlüsseln könnten.
Abschluss
Check
Auftrag: Entscheidet euch bei jeder Frage zuerst, dann auflösen.
Was darf Bob veröffentlichen?
Nur n und e, das offene Schloss. Aus p, q oder m ließe sich d berechnen.
Eve hat n = 33 und e = 3. Was braucht sie, um d zu finden?
Mit 3 und 11 rechnet sie m = 20 und d = 7. Bei 617 Stellen findet sie die Zerlegung nicht.
Warum verschlüsseln echte Programme nicht Buchstabe für Buchstabe?
Wie bei Cäsar verrät die Häufigkeit die Buchstaben. Echt: eine große Zahl mit Zufallsanteil.