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.
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?