Einwegfunktion und Schlüsseltausch

One-way functions and key exchange

Informatik Klasse 10 14 Aufgaben
InformatikKryptologiePrimzahlenZahlentheorieKomplexitätExponenten

Die Lernenden vergleichen Hin- und Rückweg: zwei Primzahlen multiplizieren gegen eine Zahl durch Probedivision zerlegen, auf der Uhr potenzieren (Rest beim Teilen) gegen den Exponenten zurückfinden. Damit spielen sie den Schlüsseltausch nach Diffie & Hellman (1976) durch: Wer alles mithört, hat trotzdem das gemeinsame Geheimnis nicht. Räumt drei Vorstellungen aus: Verschlüsseln sei Buchstabenersetzen mit vorher vereinbartem Schlüssel, doppelt so viele Stellen hießen doppelt so viel Arbeit, und eine Einwegfunktion sei gar nicht umkehrbar statt nur zu aufwendig. Bereitet Komplexität und praktische Grenzen (Klasse 12) vor.

Voraussetzungen (2)

Primzahlen und Primfaktorzerlegung
Klasse 5
›
Potenzen und Wurzeln
Klasse 9
›
Leicht
Multiple Choice #1 15s ▶ Testen

Welche Aufgabe ist mit einem gedruckten, nach Namen sortierten Telefonbuch schneller erledigt?

  • ● Zum Namen „Huber, Franziska" die Nummer finden
  • ○ Zur Nummer 47 13 92 den Namen finden
  • ○ Beide gleich schnell
Den Namen schlägt man wie im Wörterbuch nach – ein paar Mal blättern, fertig. Für den Rückweg von der Nummer zum Namen hilft die Sortierung nicht: Man muss Eintrag für Eintrag durchlesen. Beide Aufgaben verbinden dieselben Namen und Nummern – trotzdem ist nur eine Richtung leicht. So eine Einbahnstraße suchen Verschlüsselungsverfahren.
Wahr / Falsch #2 15s ▶ Testen

Zwei 100-stellige Primzahlen malzunehmen dauert genauso lange wie zwei 2-stellige.

✓ Falsch
Falsch. Schriftlich sind es 100 · 100 = 10 000 Einmaleins-Rechnungen statt 2 · 2 = 4. Für einen Rechner ist das trotzdem ein Augenblick. Die Einbahnstraße entsteht nicht, weil Malnehmen nichts kostet, sondern weil der Rückweg unvergleichlich viel mehr kostet.
Lückentext #3 20s ▶ Testen

Auf der 17er-Uhr zählt nur der Rest beim Teilen durch 17. 3⁴ = 81. Welche Zahl zeigt die 17er-Uhr für 81? ___

✓ Antwort: 13
81 = 4 · 17 + 13, also zeigt die Uhr 13. Wie bei der Uhrzeit: 27 Uhr ist 3 Uhr, weil volle Runden nicht zählen.
Multiple Choice #4 15s ▶ Testen

Welche Rechnung ist eine Einbahnstraße: hin leicht, zurück nur durch langes Probieren?

  • ● Zwei große Primzahlen malnehmen
  • ○ Eine Zahl verdoppeln
  • ○ Jeden Buchstaben um 3 im Alphabet verschieben
Das Produkt zurück in seine Primfaktoren zu zerlegen, verlangt unzählige Probedivisionen. Verdoppeln macht man durch Halbieren rückgängig, die Verschiebung durch Zurückschieben – beide Rückwege sind genauso leicht wie die Hinwege.
Wahr / Falsch #5 15s ▶ Testen

Ein Text ist mit einer Buchstabenverschiebung verschlüsselt, die Verschiebung ist geheim. Trotzdem kann man ihn in wenigen Minuten knacken.

✓ Wahr
Richtig. Es gibt nur 25 mögliche Verschiebungen – man probiert sie alle aus. Außerdem müssten sich Absender und Empfänger die Verschiebung vorher geheim sagen. Genau dieses Problem löst der Schlüsseltausch über die Uhr.
Mittel
Multiple Choice #1 20s ▶ Testen

391 soll durch Probedivision zerlegt werden. Bis zu welcher Zahl muss man höchstens probieren?

  • ● Bis 19
  • ○ Bis 195
  • ○ Bis 390
Hat 391 zwei Faktoren, ist einer höchstens √391 ≈ 19,8 – lägen beide über 19,8, käme beim Malnehmen mehr als 391 heraus. Tatsächlich ist 391 = 17 · 23. Bis zur Hälfte (195) oder bis 390 zu teilen ist viel zu viel Arbeit.
Multiple Choice #2 25s ▶ Testen

Ein Programm zerlegt eine 16-stellige Zahl durch Probedivision in etwa 1 Sekunde. Wie lange braucht es ungefähr für eine 24-stellige Zahl?

  • ● Etwa 3 Stunden
  • ○ Etwa 4 Minuten
  • ○ Etwa 1,5 Sekunden
Probiert wird bis zur Wurzel: bei 16 Stellen bis etwa 10⁸, bei 24 Stellen bis etwa 10¹². Das ist 10 000-mal so viel – 10 000 Sekunden, knapp 3 Stunden. 1,5 Sekunden rechnet so, als wüchse der Aufwand mit der Stellenzahl; 4 Minuten (2⁸ Sekunden) verdoppelt pro Stelle – auch das unterschätzt.
Multiple Choice #3 20s ▶ Testen

Zwei 6-stellige Zahlen schriftlich zu multiplizieren braucht 36 Einmaleins-Rechnungen (jede Ziffer mal jede Ziffer). Wie viele sind es bei zwei 12-stelligen Zahlen?

  • ● 144
  • ○ 72
  • ○ rund 1 000 000
12 · 12 = 144: viermal so viel Arbeit für doppelt so viele Stellen. Das wächst (72 wäre zu wenig), aber zahm – beim Zerlegen wären es tausendmal so viele Divisionen. Malnehmen ist also nicht „ein Schritt", aber es bleibt leicht.
Multiple Choice #4 20s ▶ Testen

Auf der 17er-Uhr gilt 3ˣ = 13. Wie findet man x am sichersten?

  • ● 3¹, 3², 3³ … der Reihe nach ausrechnen, bis 13 herauskommt
  • ○ 13 durch 3 teilen
  • ○ Die Wurzel aus 13 ziehen
Auf der Uhr gibt es keine Umkehrrechnung wie beim normalen Rechnen: 3, 9, 10, 13 – also x = 4. Teilen oder Wurzelziehen gehören zu anderen Rechnungen und helfen hier nicht. Auf einer riesigen Uhr hieße das: Millionen und mehr Versuche.
Multiple Choice #5 20s ▶ Testen

Wie viele Malrechnungen braucht man mindestens für 3¹⁰²⁴, wenn man immer das letzte Ergebnis quadriert (3, 3², 3⁴, 3⁸ …)?

  • ● 10
  • ○ 1 023
  • ○ 512
1 024 = 2¹⁰: Zehnmal quadrieren führt von 3¹ nach 3¹⁰²⁴. Einzeln malnehmen bräuchte 1 023 Schritte; 512 halbiert nur einmal. Darum ist der Hinweg auf der Uhr schnell, auch bei riesigen Exponenten.
Multiple Choice #6 30s ▶ Testen

Lea und Tom nutzen die 19er-Uhr und die Zahl 2. Lea wählt geheim 5 und sendet 2⁵ = 13, Tom wählt geheim 8 und sendet 2⁸ = 9 (beides auf der Uhr). Lea rechnet 9⁵ auf der Uhr. Welche Zahl erhält sie?

  • ● 16
  • ○ 3
  • ○ 13
9² = 81 zeigt auf der 19er-Uhr 5, 9⁴ also 5² = 25, das ist 6, und 9⁵ = 6 · 9 = 54, das ist 16. Tom rechnet 13⁸ und kommt ebenfalls auf 16, denn beides ist 2⁴⁰. 3 wäre 13 · 9 – das kann jeder Mithörer rechnen. 13 ist nur Leas eigene gesendete Zahl.
Multiple Choice #7 25s ▶ Testen

Mira hört beim Schlüsseltausch von Lea und Tom alles mit: die 19er-Uhr, die Zahl 2 sowie die gesendeten Zahlen 13 und 9. Was müsste sie herausfinden, um das gemeinsame Geheimnis zu berechnen?

  • ● Für welches x auf der 19er-Uhr 2ˣ = 13 gilt
  • ○ Was 13 · 9 auf der 19er-Uhr ergibt
  • ○ Was 13⁹ auf der 19er-Uhr ergibt
Das Geheimnis entsteht erst, wenn eine gesendete Zahl hoch eine Geheimzahl gerechnet wird. Mira kennt keine der Geheimzahlen – sie muss also eine davon zurückfinden: 2¹, 2², 2³ … durchprobieren, bis 13 herauskommt. Die beiden gesendeten Zahlen miteinander zu verrechnen, ergibt 3 bzw. 18 – nicht das Geheimnis.
Wahr / Falsch #8 20s ▶ Testen

Eine Uhr hat 10¹² Zahlen. Ein Rechner probiert eine Milliarde Exponenten pro Sekunde. Er findet die Geheimzahl spätestens nach etwa 17 Minuten.

✓ Wahr
Richtig. 10¹² mögliche Exponenten durch 10⁹ pro Sekunde sind 1 000 Sekunden, also knapp 17 Minuten. Eine Einwegfunktion ist nicht unumkehrbar – ihr Rückweg kostet nur Zeit, die mit der Größe der Uhr wächst. Darum nutzen echte Verfahren Uhren mit Hunderten von Stellen.
Multiple Choice #9 25s ▶ Testen

Ein Rechner schafft eine Billion (10¹²) Probedivisionen pro Sekunde. Wie lange braucht er ungefähr, um eine 60-stellige Zahl aus zwei 30-stelligen Primzahlen zu zerlegen?

  • ● Milliarden von Jahren
  • ○ Wenige Minuten
  • ○ Etwa ein Jahr
Er probiert ungerade Zahlen bis zum kleineren Faktor, einer 30-stelligen Primzahl: 5 · 10²⁸ bis 5 · 10²⁹ Probeteiler. Bei 10¹² pro Sekunde sind das 5 · 10¹⁶ bis 5 · 10¹⁷ Sekunden – rund 1,6 bis 16 Milliarden Jahre. Wenige Minuten bräuchte er für eine 30-stellige Zahl; doppelt so viele Stellen heißen hier nicht doppelt, sondern billiardenfach so viel Arbeit.