Methode in Camp 4

Schlüsselaustausch

Um eine Nachricht zu verschlüsseln und zu entschlüsseln, brauchen Sender und Empfänger denselben Schlüssel. Dieser ist meistens eine Zahl. Sie müssen den Schlüssel aber geheim austauschen können,ohne dass jemand anderes ihn erfährt. Um eine Zahl geheim auszutauschen, werden Berechnungen mit Primzahlen durchgeführt, die beim Knacken zu lange dauern würden.

Kurz: Schlüssel müssen geheim ausgetauscht werden. Dafür werden Berechnungen mit Primzahlen genutzt.

Modulo-Rechnung

Der geheime Schlüsselaustausch erfordert oft einige Berechnungen beim Sender und beim Empfänger. Modulo ist eine Rechenoperation wie die Addition oder Multiplikation. Sie wird für zahlreiche Schlüsselaustausch-Verfahren benötigt. In diesem ersten Teil wirst du Lernen, wie man damit rechnet.

Mit Modulo (kurz: mod) wird der Rest einer Division bezeichnet.

Beispiel

Jeder von uns benutzt fast täglich die Modulo-Rechnung. Die kommt nämlich bei der Berechnung der Uhrzeit vor. Wir sagen zu der Uhrzeit 15:00 Uhr meistens 3 Uhr (nachmittags). Das ist die Modulo-Rechnung mit der Zahl 12:

15 mod 12 = 3
da 15 : 12 = 1, 3 bleibt übrig.
Das heißt, dass der Zeiger 1-mal durchlief und bei 3 stehen bleibt.

Natürlich rechnet man nicht immer mod 12. 12 kann durch jede ganze Zahl ersetzt werden. Bei den meisten Verschlüsselungsverfahren kommen keine negativen Zahlen vor, das macht es etwas einfacher.

Weitere Beispiele

19 mod 5 = 4
da 19 : 5 = 3, 4 bleibt übrig.

10 mod 4 = 2
da 10 : 4 = 2, 2 bleibt übrig.

14 mod 7 = 0
da 14 : 7 = 2, 0 bleibt übrig.

Aufgabe

Berechne wie in den Beispielen und notiere das Ergebnis.

a) 25 mod 7 = ___
b) 90 mod 11 = ___
c) 23 mod 8 = ___
d) 10 mod 3 = ___
e) 42 mod 4 = ___
f) 107 mod 25 = ___
g) 2450 mod 43 = ___

Diffie-Hellman Algorithmus

Lange galt es als unmöglich, öffentlichen (also für jeden mithörbar) einen geheimen Schlüssel auszutauschen. Aber 1976 wurde von Martin Hellman, Whitfield Diffie und Ralph Merkle der Diffie-Hellman-Algorithmus entwickelt. Er ermöglicht die Vereinbarung eines gemeinsamen Schlüssels über eine öffentliche Verbindung.

Zwei Beteiligte - nennen wir sie Alice und Bob - können damit einen geheimen Schlüssel vereinbaren, obwohl sie sich offen darüber austauschen. Eine dritte Beteiligte - nennen wir sie Eve - erfährt den Schlüssel dabei nicht.

Der Algorithmus

Es werden mehrere Zahlen benötigt:

- eine Primzahl p (2, 3, 5, 7, 11, 13, 17, ...)
- eine natürliche Zahl g (1, 2, 3, 4, 5, 6, ...)
- eine Zahl a von Alice
- ein Ergebnis A von Alice
- eine Zahl b von Bob
- ein Ergebnis B von Bob
- den geheimen Schlüssel K

(Die folgenden Berechnungen sind unten in der Tabelle mathematisch dargestellt.)

Alice und Bob vereinbaren zu Beginn öffentlich eine Primzahl p und eine natürliche Zahl g. Dabei muss g kleiner sein als p.

Zum Berechnen von A bzw. B wählt Alice eine Zahl a, die nur sie kennt, und Bob wählt eine Zahl b, die nur er kennt. A und B werden öffentlich ausgetauscht.

Eve kennt also p, g, A und B, aber nicht a und b. Den geheimen Schlüssel K können Alice und Bob berechnen, Eve nicht.

Alice (privat)	Eve (öffentlich)	Bob (privat)
	p und g mit g < p
Wähle a mit a < p Berechne A = ga mod p		Wähle b mit a < p Berechne B = gb mod p
	Alice gibt Bob A Bob gibt Alice B
Berechne K = Ba mod p		Berechne K = Ab mod p
Kennt K	Kennt K nicht	Kennt K

Beispiel

Alice (privat)	Eve (öffentlich)	Bob (privat)
	p und g mit g < p p = 13, g = 4
Wähle a mit a < p a = 3 Berechne A = ga mod p A = 43 mod 13 = 64 mod 13 = 12		Wähle b mit a < p b = 5 Berechne B = gb mod p B = 45 mod 13 = 1024 mod 13 = 10
	Alice gibt Bob A Bob gibt Alice B A = 12, B = 10
Berechne K = Ba mod p K = 103 mod 13 = 1000 mod 13 = 12		Berechne K = Ab mod p K = 125 mod 13 = 248832 mod 13 = 12
Kennt K K = 12	Kennt K nicht	Kennt K K = 12

Der von Alice und Bob berechnete geheime Schlüssel in diesem Beispiel ist 12. Um den Schlüssel zu finden, müsste Eve nur alle Zahlen ausprobieren, die kleiner als p, hier also 13, sind. Das wäre einfach. Normalerweise sind die Zahlen aber so groß, dass es auch mit den schnellsten Computern fast unmöglich ist, den Schlüssel durch Ausprobieren zu finden.

Aufgabe

Bildet eine Dreier- oder Vierergruppe und spielt den Diffie-Hellman-Algorithmus durch. Eine/r von euch ist Alice, eine/r Bob und der oder die Dritte ist Eve (zu Viert ist Eve doppelt besetzt).

Alice und Bob tauschen den Schlüssel aus und Eve versucht den Schlüssel herauszufinden, um die geheime Nachricht lesen zu können.

Führt den Algorithmus mit p = 11 und g = 3 ein paar mal mit verschiedenen Rollen aus.

Notiert euer Ergebnis. Hat Eve den Schlüssel herausgefunden?