Im folgenden wiederholen wir einige Themen, die vom letzten Jahrgang als Fragen in die Wiederholungsstunde eingingen.
(Folie 1)
Sie müssen testen können, ob eine Zahl g mod p ein Erzeuger ist. Dies ist relevant, weil dadurch die Anzahl der Schlüssel maximal wird. Es kommt in praktisch allen Kryptosystemen vor, bei denen das Problem des diskreten Logarithmus die Basis für die Sicherheit darstellt.
(Folien 2+3)
Am besten, Sie versuchen das gegebene Problem 3^x=24 mod 31 zunächst selbst zu lösen. Die Faktoren von 31-1=2*3*5 lassen es zu, dass die Teilprobleme durch Ausprobieren gelöst werden können. Danach kennen Sie durch drei Gleichungen
x mod 2 x mod 3 x mod 5
Die ersten beiden ergeben x mod 6 und diese Lösung zusammen mit x mod 5 ergibt x mod 30.
(Folie 4)
Das Quadratwurzel-Problem ist relevant, wenn es um die Berechnung eines Punkts auf einer elliptischen Kurve geht. Die Grundgleichung
y^2 = x^3 + a*x + b
wird bei der Bestimmung eines zufälligen Punkts mit einer zufälligen x-Koordinate benutzt. Die rechte Seite wird ausgerechnet (wir nennen sie z) und es stellt sich die Frage, ob z ein Quadrat ist. Dies wird mit der angegebenen Formel geprüft.
Falls nein, muss ein neues x gewählt werden. Falls ja, ist die Quadratwurzel von z der gesuchte Wert y und (x,y) ist ein Punkt auf E.
Wir wiederholen den schwierigsten in der Vorlesung behandelten Fall. Wenn Sie diesen beherrschen, beherrschen Sie vermutlich alle auftretenden Fälle (außer es ist p=1 mod 8).
Am besten, Sie versuchen wieder y^2=10 mod 13 separat zu lösen und vergleichen Ihre Lösung mit dem Lösungsweg auf der Folie.
(Folie 6)
Die vorhin wiederholte Methode ist nicht die einzige Methode, um eine elliptische Kurve mit zufälligem Punkt zu erzeugen. Man kann auch mit dem Punkt beginnen und daraus die Kurve erzeugen. Auf dieser Folie benutzt man zwei vorgegebene Punkte, um eine Kurve zu finden, die beide Punkte enthält. Die Parameter a und b sind somit die unbekannten Variablen der Gleichung, während man mit gegebenen Punkten (x1,y1), (x2,y2) durch Einsetzen in die Kurvengleichung zwei Gleichungen mit zwei Variablen a, b erhält. Diese sind nun einfach mit einschlägigen Verfahren lösbar z.B. beide Gleichungen nach b umstellen und gleichsetzen.
Ist nur ein Punkt gegeben, erhält man eine Gleichung in a und b, d.h. man kann eine Variable frei wählen und daraus die andere ausrechnen.
(Folie 7)
Eine Frage aus der Wiederholungsstunde befasste sich mit der Signatur von Nachrichten. Ich habe den Sinn der Hashverfahren wiederholt. Das Hashverfahren wird sowohl beim Sender als auch beim Empfänger angewandt. Ausführlich ist dieser Vorgang an vielen Stellen beschrieben, etwa hier. Der verlinkte Artikel enthält zugleich eine Illustration mit OpenSSL.