 |
Whitfield Diffie ist einer der engagiertesten
Kryptographen seiner Generation. Schon sein bloßer Anblick erweckt einen
verblüffenden und etwas widersprüchlichen Eindruck. Sein tadelloser Anzug
sagt uns, dass er die neunziger Jahren überwiegend im Dienst einer der großen
amerikanischen Computerfirmen verbracht hat - seine gegenwärtige
Stellenbezeichnung bei Sun Microsystems lautet Distinguished Engineer, man
könnte sagen, ein Programmentwickler mit herausragenden Verdiensten. Sein
schulterlanges Haar und sein langer weißer Bart jedoch verraten, dass sein
Herz immer noch in den Sixties schlägt. Einen großen Teil seiner Zeit
verbringt er vor einer Workstation, doch er sieht aus, als würde er sich in
einem Bombayer Ashram genauso wohl fühlen. Diffie ist sich bewusst, dass
seine Kleidung und seine Persönlichkeit andere durchaus beeindrucken können:
»Die Leute halten mich immer für größer, als ich wirklich bin. Man sagt mir,
das sei der Doppler-Effekt.«
Whithfield
Diffie
Diffie wurde 1944 geboren und verbrachte den größten Teil
seiner Kindheit im New Yorker Stadtteil Queens. Als Kind schon fesselte ihn
die Mathematik, er las alles querbeet, vom Handbuch mathematischer Tabellen
für die Gummi-Industrie bis zu G. H. Hardys Course of Pure Mathematics.
Später dann studierte er am Massachusetts Institute of Technology (MIT), Als
das ARPAnet noch in den Kinderschuhen steckte, war Diffie weitsichtig genug,
die kommende Datenautobahn und die digitale Revolution vorherzusagen. Eines
Tages würden auch ganz gewöhnliche Leute Computer besitzen, und diese
Computer würden über die Telefonleitungen miteinander verbunden sein. Wenn
diese Menschen sich dann elektronische Briefe schickten, überlegte Diffie,
sollten sie das Recht haben, ihre Mitteilungen zu verschlüsseln und ihr
Privatleben zu schützen. Die Verschlüsselung setzte jedoch den sicheren
Austausch von Schlüsseln voraus. Wenn die Regierungen und großen Unternehmen
schon Schwierigkeiten damit hatten, würde es für das breite Publikum
unmöglich sein, und damit würde ihm letztlich das Recht auf Privatsphäre
verwehrt.
Diffie stellte sich zwei Fremde vor, die sich via Internet begegnen, und
fragte sich, wie sie verschlüsselte Botschaften austauschen konnten.
Außerdem dachte er über die Lage eines Menschen nach, der über das Internet
eine Ware bestellen will. Wie war es möglich, dass dieser Kunde eine E-Mail
mit den verschlüsselten Daten seiner Kreditkarte auf eine Weise verschickte,
dass nur der Internet-Händler sie entschlüsseln konnte? In beiden Fällen
brauchten die beiden Parteien allem Anschein nach einen gemeinsamen
Schlüssel, doch wie sollten sie ihre Schlüssel auf sicherem Weg austauschen?
Die Zahl der beiläufigen Kontakte und die Zahl der spontanen E-Mails im
breiten Publikum würde gewaltig sein, und dies bedeutete, dass eine
Verteilung von Schlüsseln wie bisher praktisch unmöglich sein würde. Diffie
befürchtete, dieses Hindernis würde der Masse der Anwender das Recht auf
ihre digitale Privatsphäre verwehren, und er vernarrte sich in den Gedanken,
es müsse eine Lösung für dieses Problem zu finden sein.
Im Jahr 1974 besuchte Diffie, der ruhelose Kryptograph, das Thomas J.
Watson-Forschungszentrum von IBM, wo er zu einem Vortrag eingeladen war. Er
sprach über verschiedene Strategien, das Problem der Schlüsselverteilung
anzugehen, und stimmte nur widerwillig einem halbstündigen Treffen später am
Nachmittag zu. Am Ende des Gesprächs war Hellman klar, dass Diffie der
sachkundigste Mensch war, den er je getroffen hatte. Der Eindruck beruhte
auf Gegenseitigkeit. Hellman erinnert sich: »Ich hatte meiner Frau
versprochen, nach Hause zu kommen und auf die Kinder aufzupassen, also nahm
ich ihn mit, und wir aßen gemeinsam zu Abend. Gegen zwölf brach er auf. Vom
Typ her sind wir sehr unterschiedlich - er ist eher ein Mann der Gegenkultur
-, doch der Zusammenprall unserer Persönlichkeiten war letztlich sehr
produktiv. Für mich war es wie ein Schwall frischer Luft. Es war sehr schwer
gewesen, in einem Vakuum zu arbeiten.«
Da Hellman keine großen Mittel zur Verfügung hatte, konnte er seinen neuen
Seelenverwandten nicht als Forschungskraft einstellen. Statt dessen schrieb
sich Diffie als Doktorand an der Universität ein. Hellman und Diffie
arbeiteten von nun an zusammen und suchten mit aller Kraft nach einer
Alternative zum mühseligen physischen Transport der Schlüssel über weite
Entfernungen. Nach kurzer Zeit stieß Ralph Merkle zu den beiden. Merkle war
ein intellektueller Emigrant, aus einer anderen Forschergruppe geflohen,
weil der zuständige Professor kein Verständnis hatte für den absurden Traum
von einer Lösung des Problems der Schlüsselverteilung. Hellman erinnert
sich:
Ralph war wie wir bereit, ein Narr zu sein. Und wenn es darum geht, in der
Forschung etwas wirklich Neues zu entwickeln, gelangt man nur an die Spitze
der Meute, wenn man ein Narr ist, weil nur Narren es immer wieder probieren.
Du hast Idee Nummer 1, du bist begeistert, und sie ist ein Flop. Dann hast
du Idee Nummer 2, du bist begeistert, und sie ist ein Flop. Irgendwann hast
du Idee Nummer 99, du bist aus dem Häuschen, und sie floppt. Nur ein Narr
wäre von der hundertsten Idee begeistert, aber vielleicht brauchst du
hundert Ideen, bis sich eine auszahlt. Wenn du nicht närrisch genug bist,
ständig begeistert zu sein, hast du nicht die Motivation, nicht die Kraft,
um es durchzuhalten. Gott belohnt die Narren.
Das ganze Problem der Schlüsselverteilung ist eine klassische Paradoxie.
Wenn ein Mensch einem anderen eine geheime Nachricht am Telefon übermitteln
will, muss er sie verschlüsseln. Dazu braucht er einen Schlüssel, der selbst
wiederum ein Geheimnis ist, und so ergibt sich das Problem, diesen geheimen
Schlüssel dem Empfänger zu übermitteln, damit die geheime Botschaft gesendet
werden kann. Kurz, wenn zwei Menschen sich ein Geheimnis (eine
verschlüsselte Botschaft) mitteilen wollen, müssen sie sich zuvor bereits
ein Geheimnis (den Schlüssel) mitgeteilt haben.
Beim Nachdenken über das Problem der Schlüsselverteilung hilft es, sich drei
Personen vorzustellen, Alice, Bob und Eve, wie sie in der kryptographischen
Diskussion genannt werden. In der Standardsituation will Alice Bob eine
Mitteilung schicken, oder umgekehrt, und Eve versucht, diese Nachricht zu
belauschen und aufzuzeichnen. Wenn Alice private Mitteilungen an Bob
schickt, wird sie jede dieser Botschaften zuvor chiffrieren, und jedes mal
verwendet sie einen anderen Schlüssel. Alice muss sich ständig mit dem
Problem herumschlagen, wie sie Bob die Schlüssel auf sicherem Wege
übermitteln soll, damit er ihre Mitteilungen lesen kann. Eine Möglichkeit
wäre, dass Alice und Bob sich einmal in der Woche treffen und genug
Schlüssel für die Mitteilungen der nächsten sieben Tage austauschen. Die
persönliche Schlüsselübergabe ist natürlich eine sichere, allerdings
aufwendige Lösung, und wenn Alice oder Bob krank wird, funktioniert sie
nicht mehr. Alice und Bob könnten auch Kuriere beauftragen, ein weniger
sicheres und teureres Verfahren, doch zumindest hätten sie ihren
Arbeitsaufwand verringert. So oder so, um den Austausch der Schlüssel kommen
sie offenbar nicht herum. Zwei Jahrtausende lang galt dies als Axiom der
Kryptographie - als unbestreitbare Wahrheit. Diffie und Hellman jedoch
kannten ein Gedankenexperiment, das diesem Axiom zu widersprechen schien.
Stellen wir uns vor, Alice und Bob lebten in einem Land, in dem der
Postdienst völlig korrumpiert ist und die Postboten jede ungeschützte
Mitteilung lesen. Eines Tages will Alice Bob eine sehr persönliche Nachricht
schicken. Sie legt sie in eine kleine eiserne Kiste, klappt sie zu und
sichert sie mit einem Vorhängeschloss. Sie gibt die Kiste zur Post und
behält den Schlüssel für das Vorhängeschloss. Wenn Bob die Kiste bekommt,
kann er sie nicht öffnen, weil er den Schlüssel nicht hat. Alice überlegt
vielleicht, den Schlüssel in eine zweite Kiste zu stecken, sie ebenfalls mit
einem Vorhängeschloss zu verschließen und an Bob zu schicken, doch ohne den
Schlüssel zum zweiten Schloss kann er die zweite Kiste nicht öffnen, also
kommt er auch nicht an den Schlüssel für die erste Kiste heran. Die einzige
Möglichkeit, das Problem zu umgehen, besteht offenbar darin, dass Alice eine
Kopie ihres Schlüssels, einen Nachschlüssel, anfertigt und ihn Bob, wenn sie
sich das nächste Mal zum Kaffee treffen, im voraus überreicht. Bis hierher
ist das alte Problem nur mit neuen Worten beschrieben. Die Vermeidung der
Schlüsselverteilung scheint logisch unmöglich: Wenn Alice ihren Brief in
eine Kiste schließt, die nur Bob öffnen kann, muss sie ihm einen
Nachschlüssel geben. Oder, in kryptographischen Begriffen, wenn Alice eine
Botschaft so verschlüsseln will, dass nur Bob sie entschlüsseln kann, muss
sie ihm eine Kopie des Schlüssels geben. Der Schlüsselaustausch ist ein
unvermeidlicher Teiltier Verschlüsselung - oder etwa nicht?
Stellen wir uns nun die folgende Situation vor. Wie zuvor will Alice eine
höchst persönliche Mitteilung an Bob schicken. Wiederum legt sie ihre
Nachricht in die Eisenkiste, sichert sie mit einem Vorhängeschloss und
schickt sie an Bob. Sobald die Kiste angekommen ist, fügt Bob sein eigenes
Vorhängeschloss hinzu und schickt die Kiste an Alice zurück. Sie entfernt
ihr Schloss, so dass jetzt nur noch Bobs Schloss die Kiste sichert. Dann
schickt sie die Kiste an Bob zurück. Der entscheidende Unterschied ist nun:
Bob kann die Kiste öffnen, weil sie nur mit seinem eigenen Vorhängeschloss
gesichert ist, dessen Schlüssel er allein besitzt.
Diese kleine Geschichte hat es in sich. Sie zeigt, dass eine geheime
Mitteilung auf sichere Weise übermittelt werden kann, ohne dass die beiden
Beteiligten einen Schlüssel austauschen müssen. Zum ersten Mal schöpfen wir
den Verdacht, dass ein Schlüsselaustausch in der Kryptographie nicht
unbedingt notwendig ist. Wir können die Geschichte unter dem Gesichtspunkt
der Verschlüsselung umformulieren: Alice verschlüsselt ihre Botschaft an Bob
mit ihrem eigenen Schlüssel, Bob verschlüsselt sie zusätzlich mit seinem
Schlüssel und schickt sie zurück. Wenn Alice die doppelt verschlüsselte
Nachricht erhält, entfernt sie ihre eigene Verschlüsselung und schickt die
Nachricht an Bob zurück, der seine Verschlüsselung entfernen und die
Nachricht lesen kann.
Dem Anschein nach ist das Problem der Schlüsselverteilung damit gelöst, denn
bei der doppelten Verschlüsselung ist ein Schlüsselaustausch unnötig.
Allerdings hat dieses Verfahren, bei dem Alice verschlüsselt, Bob
verschlüsselt, Alice entschlüsselt und Bob entschlüsselt, einen
entscheidenden Nachteil. Das Problem besteht in der Reihenfolge, in der
Verschlüsselungen und Entschlüsselungen vorgenommen werden. Im allgemeinen
ist diese Reihenfolge von entscheidender Bedeutung und muss dem Grundsatz
»die letzte muss die erste sein« gehorchen: Die letzte Verschlüsselung
sollte die erste sein, die wieder rückgängig gemacht wird. Im obigen
Beispiel führt Bob die letzte Verschlüsselung aus, deshalb müsste er sie
auch als erste rückgängig machen. Doch Alice entfernte die ihre zuerst,
danach kam Bob. Wie wichtig die Reihenfolge ist, begreifen wir am besten,
wenn wir uns eine ganz alltägliche Handlung ansehen. Morgens ziehen wir
zuerst unsere Socken und dann unsere Schuhe an, und abends ziehen wir die
Schuhe aus, bevor wir die Socken ausziehen - die Socken können wir unmöglich
vor den Schuhen ausziehen. Das Beispiel mit den Vorhängeschlössern leuchtet
insofern ein, als sie in beliebiger Reihenfolge angebracht und wieder
entfernt werden können, doch für die meisten Chiffriersysteme ist die
Reihenfolge von Verschlüsselung und Entschlüsselung entscheidend. Hier gilt
unbedingt die Grundregel »die letzte muss die erste sein«.
Zwar würde das Verfahren mit den doppelt verschlossenen Kisten in der
wirklichen Welt der Kryptographie nicht funktionieren, doch es ermutigte
Diffie und Hellman auf ihrer Suche nach einer brauchbaren Methode, das
Problem der Schlüsselverteilung zu umgehen. 1975 hatte Diffie schließlich
eine brillante Idee. Er weiß noch gut, wie der Gedanke ihm plötzlich einfiel
und dann beinahe wieder verschwand. »Ich ging nach unten, um mir eine Cola
zu holen, und dabei vergaß ich die Idee fast wieder. Ich wusste nur noch,
dass ich über etwas Interessantes nachgedacht hatte, aber nicht mehr, was es
genau war. Dann kam es mit einem richtigen Adrenalinschub zurück. Zum ersten
Mal während dieser ganzen Kryptographiearbeit war mir klar, dass ich etwas
wirklich Wertvolles entdeckt hatte. Alles, was ich auf diesem Gebiet bis
dahin herausgefunden hatte, kam mir vor wie unbedeutender technischer
Kleinkram.« Es war Nachmittag, und er musste ein paar Stunden warten, bis
Mary, seine Frau, nach Hause kam. »Whit stand schon an der Tür«, erinnert
sie sich. »Er müsse mir etwas sagen, meinte er und machte dabei ein
komisches Gesicht. Ich ging rein, und er sagte:
»Setz dich bitte, ich möchte mit dir reden. Ich glaube, ich hab eine
große Entdeckung gemacht - ich weiß, dass ich bei dieser Sache der erste
bin. Für einen Augenblick stand die Welt still. Ich kam mir vor wie in einem
Hollywood-Film.«
Diffie hatte ein neues Verschlüsselungsverfahren entwickelt, das mit einem
so genannten asymmetrischen Schlüssel arbeitete. Alle bisher dargestellten
Verschlüsselungstechniken sind symmetrisch, das heißt, die Entschlüsselung
ist einfach die Umkehr der Verschlüsselung. Die Enigma beispielsweise
verwendet einen bestimmten Schlüssel, um eine Meldung zu chiffrieren, und
der Empfänger stellt auf seiner identischen Maschine denselben Schlüssel
ein, um sie zu dechiffrieren. Sender und Empfänger haben das gleiche Wissen
und benutzen denselben Schlüssel zur Ver- und Entschlüsselung - ihre
Beziehung ist symmetrisch. Bei einem asymmetrischen Schlüsselsystem hingegen
sind, wie der Name schon sagt, Verschlüsselungs-Schlüssel und
Entschlüsselungs-Schlüssel nicht identisch. Beim asymmetrischen Verfahren
kann Alice zwar, wenn sie den Chiffrier-Schlüssel kennt, eine Botschaft
verschlüsseln, diese Botschaft jedoch nicht wieder entschlüsseln. Dazu
braucht sie Zugang zum Dechiffrier-Schlüssel. Diese Unterscheidung zwischen
Chiffrier-Schlüssel und Dechiffrier-Schlüssel ist das Kennzeichen der
asymmetrischen Verschlüsselung.
An diesem Punkt sollte gesagt werden, das Diffie zwar den Begriff einer
asymmetrischen Verschlüsselung entwickelt hatte, doch noch kein konkretes
Beispiel dafür besaß. Allerdings war schon der bloße Begriff einer
asymmetrischen Verschlüsselung revolutionär. Wenn die Kryptographen eine
echte, funktionierende asymmetrische Verschlüsselung finden konnten, ein
System, das Diffies Anforderungen erfüllte, dann würde dies die Lage von
Alice und Bob grundlegend verändern. Alice könnte dann ihr eigenes
Schlüsselpaar herstellen: einen Chiffrier-Schlüssel und einen
Dechiffrier-Schlüssel. Wenn wir davon ausgehen, dass die asymmetrische
Chiffre computergestützt ist, dann ist Alices Chiffrier-Schlüssel eine Zahl
und ihr Dechiffrier-Schlüssel eine andere Zahl. Alice hält ihren
Dechiffrier-Schlüssel geheim, weshalb er als privater Schlüssel bezeichnet
wird. Hingegen veröffentlicht sie ihren ChiffrierSchlüssel und stellt ihn
allen zur Verfügung, weshalb er als öffentlicher Schlüssel bezeichnet wird.
Wenn Bob Alice eine Mitteilung schicken will, sucht er einfach ihren
öffentlichen Schlüssel heraus, den er in einem Verzeichnis, ähnlich einem
Telefonregister, aufbewahrt. Dann verwendet Bob Alices öffentlichen
Schlüssel, um die Mitteilung zu chiffrieren. Er schickt sie an Alice, und
wenn die Mitteilung angekommen ist, kann Alice sie mit ihrem privaten
Schlüssel dechiffrieren. Wenn Charlie, Sophie oder Edward verschlüsselte
Mitteilungen an Alice schicken wollen, können sie ebenfalls ihren
öffentlichen Schlüssel ihren öffentlichen Schlüssel keineswegs auf sicherem
Weg Bob überbringen, im Gegenteil: sie kann ihn, wenn sie will, allen andern
zur Verfügung stellen. Sie will ja, dass alle Welt ihren öffentlichen
Schlüssel kennt, damit es allen freisteht, ihr verschlüsselte Nachrichten zu
schicken. Doch selbst wenn Gott und die Welt Alices öffentlichen Schlüssel
kennen, kann niemand, auch Eve nicht, irgendeine damit verschlüsselte
Nachricht dechiffrieren, weil der öffentliche Schlüssel dazu nicht taugt.
Daher kann nicht einmal Bob, sobald er mit Alices öffentlichem Schlüssel
eine Nachricht chiffriert hat, diese wieder entschlüsseln. Das kann nur
Alice mit ihrem privaten Schlüssel.
Dieses Verfahren ist das genaue Gegenteil der herkömmlichen symmetrischen
Verschlüsselung, bei der Alice einigen Aufwand treiben muss, um den
Schlüssel auf sicherem Wege Bob zu überbringen. Bei einer symmetrischen
Verschlüsselung sind Chiffrier- und Dechiffrier-Schlüssel identisch, daher
müssen Alice und Bob scharf darauf achten, ihn nicht in Eves Hände fallen zu
lassen. Das ist der Kern des Schlüsselverteilungsproblems.
Wenn wir zu dem Vergleich mit dem Vorhängeschloss zurückkehren, kann man
sich die asymmetrische Kryptographie wie folgt vorstellen. Jeder kann ein
Vorhängeschloss einschnappen lassen, doch nur der Besitzer des Schlüssels
kann es wieder öffnen. Das Verschließen (Verschlüsselung) ist einfach, alle
können es tun, doch das Öffnen (Entschlüsselung) ist einzig dem Besitzer des
Schlüssels vorbehalten. Das schlichte Wissen, wie man das Vorhängeschloss
zuschnappen lässt, bedeutet nicht, dass man es auch öffnen kann. Stellen wir
uns weiter vor, dass Alice ein Vorhängeschloss mit Schlüssel bastelt. Sie
behält den Schlüssel, stellt jedoch Tausende von identischen
Vorhängeschlössern her und verteilt sie an Postämter in aller Herren Länder.
Wenn Bob ihr eine Nachricht schicken will, legt er sie in eine Kiste, geht
zum nächsten Postamt, verlangt ein »Vorhängeschloss Alice« und verschließt
damit seine Kiste. Jetzt kann er sie nicht mehr öffnen, doch wenn sie bei
Alice ankommt, kann sie die Kiste mit ihrem, dem einzigen Schlüssel,
aufmachen. Der öffentliche Schlüssel ist vergleichbar mit dem
Vorhängeschloss, das man zuschnappen lässt, denn jeder hat Zugang zu den
Vorhängeschlössern und kann damit seine Nachricht in eine Kiste schließen.
Der private Schlüssel ist vergleichbar mit dem Schlüssel zum
Vorhängeschloss, denn nur Alice besitzt ihn, nur sie kann das
Vorhängeschloss öffnen, und nur sie hat Zugang zur Mitteilung in der Kiste.
Das Verfahren erscheint simpel, wenn man es anhand von Vorhängeschlössern
erklärt, doch es ist keineswegs einfach, eine mathematische Funktion zu
finden, die für diese Aufgabe geeignet ist und in ein brauchbares
kryptographisches Verfahren eingebaut werden kann. Um die großartige Idee
einer asymmetrischen Verschlüsselung in eine praktische Neuerung zu
verwandeln, musste eine geeignete mathematische Funktion gefunden werden,
die als mathematisches Vorhängeschloss taugt. Eine Funktion ist eine
mathematische Regel, die jede Zahl in eine andere verwandelt. Zum Beispiel
ist »verdoppeln« eine Funktion, weil dabei die Zahl 3 in 6 verwandelt wird
oder die Zahl 9 in 18. Auch alle Formen der computergestützten
Verschlüsselung können wir als Funktionen betrachten, weil sie eine Zahl
(den Klartext) in eine andere (den Geheimtext) verwandeln.
Die meisten mathematischen Funktionen lassen sich als umkehrbar bezeichnen,
weil sie genauso leicht in der einen wie in der anderen Richtung auszuführen
sind. »Verdoppeln« zum Beispiel ist eine umkehrbare Funktion, weil es leicht
ist, eine Zahl zu verdoppeln und damit eine neue Zahl zu erhalten, und
genauso leicht, diese Funktion umzukehren und von der neuen Zahl wieder zur
Ausgangszahl zu gelangen. Wenn wir beispielsweise wissen, dass das Ergebnis
einer Verdopplung 26 ist, dann ist es einfach, die Funktion umzukehren und
darauf zu schließen, dass die ursprüngliche Zahl 13 lautete. Den Begriff der
umkehrbaren Funktion versteht man am einfachsten, wenn man an alltägliche
Handlungen denkt. Einen Lichtschalter zu drehen ist eine Funktion, weil
damit eine Glühbirne in eine brennende Glühbirne verwandelt wird. Es handelt
sich um eine umkehrbare Funktion, denn wenn der Schalter gedreht ist, kann
er auch einfach wieder zurückgedreht werden, und damit kehrt die Glühbirne
in ihren Ausgangszustand zurück.
Diffie und Hellman jedoch interessierten sich nicht für umkehrbare
Funktionen. Ihre Aufmerksamkeit galt allein den Einwegfunktionen. Wie der
Name schon sagt, ist eine Einwegfunktion leicht auszuführen, doch sehr
schwer wieder umzukehren. Dies lässt sich wiederum mit einem alltäglichen
Beispiel erläutern. Gelbe und blaue Farbe zu grüner Farbe vermischen ist
eine Einwegfunktion, weil es leicht ist, die Farbe zu mischen, aber
unmöglich, sie wieder zu entmischen. Eine andere Einwegfunktion ist das
Zerschlagen eines Hühnereis, weil es leicht ist, das Ei in die Pfanne zu
hauen, jedoch unmöglich, es in seinen alten Zustand zurückzuversetzen.
Vorhängeschlösser sind ebenfalls in der Wirklichkeit vorkommende Beispiele
für Einwegfunktionen, weil man sie leicht verschließen, aber schwer wieder
öffnen kann. Diffies Idee beruhte auf einer Art mathematischem
Vorhängeschloss, und deshalb richtete die Stanforder Arbeitsgruppe aus Diffie,
Hellman und Merkle ihr Augenmerk auf die Untersuchung von Einwegfunktionen.
Die Modul-Arithmetik, in Schulen manchmal auch Uhren-Arithmetik genannt, ist
ein Gebiet der Mathematik, auf dem sich reichlich Einwegfunktionen finden.
In der Modul-Arithmetik werden endliche Gruppen von Zahlen untersucht, die
auf einer Schleife angeordnet sind, ähnlich wie die Ziffern einer Uhr.
Abbildung 46 zeigt beispielsweise eine Uhr für modulo 7 (oder mod 7), die
nur 7 Zahlen von 0 bis 6 besitzt. Um die Aufgabe 2+3 zu lösen, beginnen wir
bei 2, gehen drei Schritte im Kreis und landen bei 5, erhalten also dieselbe
Antwort wie in der üblichen Arithmetik. Um 2+6 zu lösen, beginnen wir bei 2
und gehen sechs Schritte im Kreis, doch diesmal überschreiten wir die 0 und
landen bei 1, was wir in der normalen Arithmetik nicht erhalten würden. Die
Rechnungen können wie folgt dargestellt werden:
2 +3 = 5 (mod 7) und 2+6 =1 (mod 7) Die Modul-Arithmetik ist relativ
einfach, und tatsächlich betreiben wir sie jeden Tag, wenn wir über die Zeit
reden. Wenn es jetzt 9 Uhr ist und wir in 8 Stunden eine Verabredung haben,
können wir sagen, das Treffen ist um 5 Uhr. Wir haben im
Martin
Hellman |
