Einwegfunktion und Schlüsseltausch
Welche Aufgabe ist mit einem gedruckten, nach Namen sortierten Telefonbuch schneller erledigt?
Erklärung: 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.
391 soll durch Probedivision zerlegt werden. Bis zu welcher Zahl muss man höchstens probieren?
Erklärung: 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.
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?
Erklärung: 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.
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?
Erklärung: 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.
Zwei 100-stellige Primzahlen malzunehmen dauert genauso lange wie zwei 2-stellige.
Erklärung: 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.
Auf der 17er-Uhr zählt nur der Rest beim Teilen durch 17. 3⁴ = 81. Welche Zahl zeigt die 17er-Uhr für 81? ___
Erklärung: 81 = 4 · 17 + 13, also zeigt die Uhr 13. Wie bei der Uhrzeit: 27 Uhr ist 3 Uhr, weil volle Runden nicht zählen.
Auf der 17er-Uhr gilt 3ˣ = 13. Wie findet man x am sichersten?
Erklärung: 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.
Wie viele Malrechnungen braucht man mindestens für 3¹⁰²⁴, wenn man immer das letzte Ergebnis quadriert (3, 3², 3⁴, 3⁸ …)?
Erklärung: 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.
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?
Erklärung: 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.
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?
Erklärung: 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.
Eine Uhr hat 10¹² Zahlen. Ein Rechner probiert eine Milliarde Exponenten pro Sekunde. Er findet die Geheimzahl spätestens nach etwa 17 Minuten.
Erklärung: 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.
Welche Rechnung ist eine Einbahnstraße: hin leicht, zurück nur durch langes Probieren?
Erklärung: 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.
Ein Text ist mit einer Buchstabenverschiebung verschlüsselt, die Verschiebung ist geheim. Trotzdem kann man ihn in wenigen Minuten knacken.
Erklärung: 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.
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?
Erklärung: 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.