Singh 1 und Singh 2

Die beiden Aufgaben Singh 1 und Singh 2 bilden die Teile eines Ganzen. Es geht darum, das Verschlüsselungsverfahren von Diffie-Hellman-Merkle zu verstehen, das diese drei Mathematiker 1976 vorstellten und das eine der Grundlagen der heute im Internet verwendeten Verschlüsselungsverfahren ist. Das Verfahren hat Simon Singh in seinem Buch: "Geheime Botschaften. Die Kunst der Verschlüsselung von der Antike bis in die Zeiten des Internet ( dtv, 2006)" an einem Beispiel illustriert. In unserer Gruppe haben wir darüber hinaus das Ziel, das Verfahren zu verstehen, und den Weg dazu haben wir in zwei Etappen aufgeteilt.

An mathematischen Grundlagen wird nur ein wenig Stoff aus der Klassenstufe 8 benötigt. Vorausgesetzt wird neben dem Rechnen mit natürlichen Zahlen das Potenzgesetz (xA)B = xA•B , wobei es hier genügt, wenn x, A, B natürliche Zahlen sind.
Zum Beispiel ist (23)2 = 26 = 64 ( In der Tat ist ja 82= 64).

Wir betrachten in den beiden Aufgaben eine Funktion, die wir in der Form schreiben
y = 7xmod11 ( x ist eine natürliche Zahl).
Gemeint ist damit folgende Zuordnung : Bilde mit der gegebenen Zahl x die Potenz 7x und rechne sodann den Rest aus, der sich bei Division durch 11 ergibt. So wird z.B. der Zahl x = 1 die Zahl y = 7 zugeordnet, der Zahl x = 2 die Zahl 5 (denn 49 = 4•11 + 5).


Singh 1

Die erste Aufgabe besteht darin, eine kleine Wertetabelle zu erstellen.
Berechne – ohne Taschenrechner - die Funktionswerte für die folgenden x-Werte: 1,2,3,4,5,8,12,16,19,32,38,76.


Lege Dir erst ein Werkzeug zurecht, das in folgendem Satz besteht: Den Elferrest eines Produktes zweier Zahlen kann ich erhalten, indem ich die Elferreste der beiden Zahlen miteinander multipliziere und den Elferrest dieses Produktes ermittele. ( Kurz: Das Produkt zweier Zahlen und das Produkt ihrer Elferreste haben denselben Elferrest). Versuche, diesen Satz zu beweisen.


Wir beweisen den genannten Satz.

Seien u, v zwei natürliche Zahlen, und seien u11 und v11 deren Elferreste. Dann gibt es zwei natürliche Zahlen a und b mit u = a•11 + u11 und v = b•11 + v11

Damit gilt. u•v = (a•11 + u11)( b•11 + v11) = a•b•11•11 + a•v11•11 + u11•b•11 + u11•v11

Die Produkte uv und u11v11 unterscheiden sich nur um ein Vielfaches von 11; sie haben deshalb denselben Elferrest. Dieser Satz ist ein mächtiges Hilfsmittel, da das zweite Produkt sehr viel kleiner als das erste sein kann.

Die ersten beiden Wertepaare haben wir schon: (1 | 7) und ( 2 | 5)

73 = 7271 ; demnach hat 73 denselben Elferrest wie 5•7 = 35, und der ist 2.

74 = 7371; der Elferrest von 74 ist gleich dem von 2•7, und der ist 3.

75 = 7471; der Elferrest von 75 ist gleich dem von 3•7, und der ist 10

78 = (74)2; der Elferrest von 78 ist gleich dem von 32, und der ist 9

712 = (74)3; der Elferrest von 712 ist gleich dem von 33, und der ist 5

716 = (78)2 ; der Elferrest von 716 ist gleich dem von 92, und der ist 4

719 = 7374712; der Elferrest von 719 ist gleich dem von 2•3•5=30, und der ist 8

732 = (712)2•78; der gesuchte Elferrest ist gleich dem von 52•9, der wiederum gleich dem von 3•9, und der ist 5.

Und jetzt ein bisschen fachsprachlich korrekt: 738=719719 ≡ 64mod11 ≡ 9mod11

Das Zeichen a ≡ bmod11 heißt "a ist kongruent b modulo 11" und bedeutet, dass die zwei Zahlen a und b denselben Elferrest haben.

Und 776 hat denselben Elferrest wie 81, und der ist 4.

X

1

2

3

4

5

8

12

19

32

38

76

16

Y

7

5

2

3

10

9

5

8

5

9

4

4

Das Zahlenpaar (16| 4) habe ich an den Schluss gestellt, um auf etwas sehr Wichtiges aufmerksam zu machen: Unsere Funktion ist nicht injektiv, d.h. verschiedene x- Werte können denselben y-Wert haben. Und das bedeutet, dass die Funktion nicht umkehrbar ist!

Es gibt sogar unendlich viele x-Werte, welche den y-Wert 4 haben, und Gleiches gilt für alle Elemente des Wertebereiches! Damit ist es unmöglich, aus einem gegebenen y-Wert den zugrunde gelegten x-Wert zu erraten!! Das wird sich später als entscheidend herausstellen.

Und wenn Du jetzt das folgende Schema verstehst, dann ist die Aufgabe Singh 2 nur noch ein kleiner Spaziergang.

Gegeben sind zwei natürliche Zahlen A und B. Die Elferreste von 7A und 7B bezeichnen wir mit α bzw. β

Was geschieht, wenn wir jetzt βA und αB bilden und dann deren Elferreste bestimmen?

Eine kleine Erläuterung dazu: β ist der Elferrest von 7B. Und so hat die Potenz βA denselben Elferrest wie (7B)A ; Entsprechendes gilt für α, den Elferrest von 7A

Beachte bitte, dass A und B nicht die Seiten wechseln: A bleibt links, B bleibt rechts.

Singh 2

Raphael und Georg werden gebeten, sich jeder eine natürliche Zahl zu merken und diese nicht preiszugeben.
Raphael hat sich die Zahl A = 5, Georg hat sich die Zahl B = 3 gemerkt.

Sie führen nun folgende Rechenoperationen aus.

  • Raphael: α= 7Amod11,   Georg: β = 7Bmod 11 ( Jeder berechnet den Elferrest der Potenz 7x, wobei x die Zahl ist, die er sich gemerkt hat).
  • Sie tauschen die Ergebnisse α und β aus.
  • Raphael: sR = βA mod 11,   Georg: sG = αB mod 11.

Welches Ergebnis erhalten Raphael und Georg?

Torsten wird über den gesamten Rechenweg informiert, und er erfährt sogar die Werte von α und β. Das heißt, ihm ist alles bekannt, bis auf die Zahlen A und B, die jeweils nur Raphael bzw. Georg wissen ( Nicht vergessen: Auch Raphael und Georg kennen jeweils nur ihre Zahl A bzw. B, nicht die des Partners).

Wieso hat Torsten trotz dieser Informationen keine reelle Chance, das Ergebnis der Rechnung herauszufinden?


α = 73mod 11 = 7271mod 11 = 5•7 mod 11 = 2

β = 75mod 11 = 7372mod 11 = 2•5 mod 11 = 10

sR = 25mod 11 = 10
sG = 103mod 11 = (100•10)mod 11 = (1•10)mod 11 = 10

Beide erhalten dasselbe Ergebnis, was ja nach dem Schema aus der Aufgabe Singh 1 so sein muss. Da es unendlich viele Potenzen mit der Basis 7 gibt, deren Elferrest 2 bzw. 10 ist, hat Torsten keine Chance, die Zahlen A und B zu erraten, und er kann damit die weitere Rechnung nicht durchführen.

Verallgemeinern wir ein wenig das Problem.

Wir hätten an der Stelle der Zahlen 7 und 11 auch andere, vor allem viel größere wählen können. An dem Schema hätte sich nichts geändert und auch nicht daran, dass der „Spion“ Torsten trotz vollständiger Kenntnis des Rechenwegs und der Zwischenergebnisse keine Chance hat, das Ergebnis der Rechnung herauszufinden.

Das Ergebnis der Rechnung könnte als Schlüssel dienen, einen Geheimtext in Klartext zu übertragen.

Bis 1976 hatte man das Problem, dass Sender und Empfänger einer Geheimnachricht den gleichen, vollständigen Schlüssel kennen mussten. Sie mussten sich also vorab über den Schlüssel informieren. Da auch diese Information im Prinzip abgehört werden konnte, musste auch der Schlüssel wiederum verschlüsselt übertragen werden, womit aber das Problem von vorne losging.

Nach der hier vorgestellten Idee Hellman’s ist das nicht mehr nötig. Sender und Empfänger haben jeweils einen eigenen Schlüssel ( Die Zahlen A und B). Jeder von beiden kennt nur die Hälfte des Schlüssels ( seine eigene Zahl), und eine Verständigung darüber ist nicht mehr nötig. Insbesondere kann keiner der beiden den vollständigen Schlüssel verraten.

Der Spion kann alles mithören, auch den Austausch der Zwischenergebnisse. Er hat keine Chance zur Entschlüsselung.
Eine Revolution in der Entwicklung der Geheimsprachen!