Modularithmetik
|
Die Modularithmetik ist ein Gebiet der Zahlentheorie welches sich mit endlichen Gruppen
von Zahlen beschäftigt, die in einer Schleife angeordnet sind.
Hierbei treten viele Einwegfunktionen auf.
Diese Einwegfunktionen resultieren aus der Eigenschaft der Modulo-Funktion.
Eine Modulo-Funktion liefert den Rest einer Division zweier beliebiger Zahlen.
Folgendes Beispiel erklärt die Modularithmetik etwas genauer.
Um in der Modularithmetik 2+3 (mod 7) auszurechnen wird in einem Schleifensystem mit 7
Zahlen (hier die Uhrdarstellung) bei der Zahl 2 begonnen und 3 Schritte weiter gegangen.
Man landet bei der Zahl 5 und die 5 ist dann das Ergebnis von 2+3 Modulo 7.
Wenn man jedoch das Ergebnis von 2+6 Modulo 7 erhalten möchte,
verfährt man wie beim Beispiel zuvor, erhält aber eine Zahl
- nämlich die 1 - , die in der normalen Arithmetik eine 8 sein müsste.
Das Ergebnis lautet somit für 2+6 (mod 7) = 1. Oder anders gesprochen 2 + 6 = 1
für Modulo 7.
|
Ein weiteres Beispiel ist die normale Uhrzeit.
Wenn jemand um 19 Uhr eine Verabredung 13 Stunden später vereinbart, dann weiß er, dass der Treffpunkt um 8 Uhr ist und nicht um 32 Uhr.
Das besondere an diesen Modulfunktionen ist nun, dass sie sich unstetig verhalten.
Das hat dann zur Folge, dass sie zu Einwegfunktionen werden.
Dieses Phänomen trifft z.B. für das modulare Potenzieren zu.
Die Wertetabelle verdeutlicht dieses Phänomen.
Setzt man für x verschiedene Werte ein, so erkennt man für 3x eine Stetigkeit, während die Funktion 3x(mod 7) nicht stetig ist.
Aus der Kenntnis des Funktionswertes f(x)=6 und des Modulo-Operators p=7 kann man den Exponenten x=3 nur durch Ausprobieren aller möglichen Werte ermitteln. Für große Werte von Basis und Exponenten ist die Berechnung des diskreten Logarithmus nicht möglich.
Mit Hilfe dieses Phänomens und der gefundenen Einwegfunktion, erstellten Diffie und
Hellman ihre Schlüsselvereinbarung.
