| |
In der modernen Kryptographie spielt die modulare Arithmetik eine sehr wichtige Rolle. Jedesmal wenn du etwas über das Internet bestellst, werden deine Daten mit RSA codiert, einer Verschlüsselungsmethode, die auf den Eigenschaften von Primzahlen und der modularen Arithmetik basiert. Um das Prinzip zu erklären, schauen wir uns das alte Problem der Schlüsselverteilung an.
Willst du jemandem eine geheime Botschaft senden, so muss diese Person einen Schlüssel haben um deine Nachricht lesen zu können. Du könntest ihr den Schlüssel natürlich persönlich überbringen, aber das ist nicht immer möglich. So wird es zum Beispiel für Banken zu aufwendig, Schlüssel verteilen zu lassen. Früher wurde das wirklich über Personen gemacht, heute wäre es aber zu schwierig, so viele verlässliche Leute zu finden. Und wie teuer das wäre!
Im Jahr 1976 fand Martin Hellman zusammen mit seinen Kollegen Whitfield Diffie und Ralph Merkle einen Weg, um Schlüssel auf telefonischem Weg zu verteilen. Zwei Personen können ganz normal das Telefon benützen, und kein heimlicher Lauscher wird nachher den Schlüssel kennen.
Um zu verstehen wie das funktioniert, schauen wir uns zuerst einmal das folgende Gesetz an:
Probier es mal mit ein paar Zahlen aus, und du wirst schnell sehen, dass es funktioniert. Nimmst du zum Beispiel x=2, a=2 and b=3, so bekommst du: (22)3=43=64=82=(23)2
Hellman und seine Kollegen benützten dieses Prinzip für das Schlüsselaustauschproblem. Zuerst einmal entscheiden sich zwei Personen A und B für eine Basis (x). Dann wählen beide eine geheime Zahl, die Zahlen a und b. Jeder berechnet nun x hoch seine geheime Zahl. Die Person A wird also xa und die Person B wird xb bekommen. Sie tauschen nun ihre Resultate aus und nehmen das Resultat des anderen als Basis für eine neue Berechnung mit ihrer Geheimzahl. Nun hat also die Person A (xb)a und die Person B hat (xa)b. Wie wir vorhin sahen, haben nun beide das selbe Resultat, obwohl sie die Geheimzahl des anderen nicht kennen.
Wenn alles genau so ginge wie oben beschrieben, so wäre es für einen Mithörer sehr leicht, die Schlüsselzahl herauszufinden. Nicht aber, wenn das ganze über modulare Arithmetik läuft!
A und B einigen sich also nicht nur auf eine Basiszahl sondern auch noch auf einen Modulus. Ihre Berechnungen führen sie nun nach der gleichen Gesetzmässigkeit aus, diesmal aber innerhalb der modularen Arithmetik.
A muss nun also xa mod y berechnen und B berechnet xb mod y. Sie tauschen ihre Resultate aus und A berchnet (xb mod y)a mod y, während B (xa mod y)b mod y berechnet. Sie bekommen natürlich wieder dasselbe Resultat, aber diesmal ist es egal, wer auch immer mithört. Überlegen wir mal, was ein Lauscher herausfinden könnte.
Nehmen wir an, A und B einigen sich auf die Basis 6 und den Modulus 11. Sie sage sich das über die Telefonleitung, die wir abzapfen. Nun machen beide ihre Berechnungen und übermitteln sich ihre Resultate, nämlich 5 für A und 1 für B. Wir wissen nun also, dass A folgende Rechnung gelöst hat: 6a mod 11 = 5, und die von B ist 6b mod 11 = 1. Wie können wir nun a oder b berechnen? Das ist viel schwieriger als es vielleicht zuerst Aussieht. Die einzige Möglichkeit, die uns bleibt, ist alle möglichen Zahlen auszuprobieren, bis wir eine finden, mit der die Gleichung aufgeht. Das ist möglich bei so kleinen Zahlen wie in unserem Beispiel, wird aber nahezu unmöglich, wenn wirklich grosse Zahlen benutzt werden. Es gibt dann so viele Möglichkeiten, dass ein heutiger Computer den Code nicht knacken kann.
Funktionen wie Modulus y nennt man Einwegfunktionen, weil es für A zwar leicht ist 48234 mod 50 = 34 zu berechnen (wenigstens mit einer Rechenmaschine), aber sehr schwierig den Wert von a zu finden in 48a mod 50 = 34. Im Gegensatz zu dieser Art von Funktion gibt es Funktionen, die eine Umkehrfunktion haben; zum Beispiel für die Addition die Subtraktion, zum Quadrieren das Wurzelziehen. Würde A 5²=25 berechnen, so könnte man das a in a²=25 leicht berechnen als √25=5.
