Eine der Fragen aus der Einführung war die nach der Anzahl der Punkte einer elliptischen Kurve E mod p. Dies ist kryptographisch wichtig, weil dies die Anzahl der möglichen Schlüssel darstellt. Es wäre fatal, wenn man mit Parametern a, b, p starten würde, die Kurve
E: y^2 = x^3 + ax + b mod p
als Struktur deklariert und diese Gleichung nur sehr wenige Lösungen hätte. Dann hätte es der Angreifer eines Kryptosystems einfach, er müsste nur diese wenigen möglichen Fälle durchgehen.
(Folie 1)
Wenn Sie sich dieser Frage experimentell nähern wollen und es ist lehrreich, das zu tun, dann habe ich wieder eine altbekannte Empfehlung für Sie: Programmieren Sie!
Für kleine Beispiele ist es vollkommen egal, wie gut Sie eine Lösung programmieren können. Das Ergebnis ist das Entscheidende: bei gegebenem a, b, p, wieviele Punkte hat die Kurve E?
Ganz simpel können Sie x und y variieren und prüfen, ob der Punkt auf der Kurve liegt.
for x = 0 to p-1 do
for y = 0 to p-1 do
if y*y mod p = x*x*x+a*x+b mod p then
count = count + 1
fi
od
od
count = count + 1 // warum? siehe unten...
Sie können Ihren Code drastisch beschleunigen, indem Sie sich
alle Quadrate y*y mod p in einem boolean-Array als a[y*y mod p]=true
merken. Und für jedes x mit a[x*x*x+a*x+b mod p]==true, den
counter erhöhen.
Wenn Sie das gemacht haben, auch die erste Version reicht schon dafür aus, können Sie die Beispiele auf der Folie nachrechnen.
Wenn Sie einen Punkt zuwenig haben, liegt es daran, dass Sie den Punkt O vergessen haben, dieser hat keine Koordinaten (x,y), sondern muss extra ergänzt werden.
Mit diesen und weiteren Experimenten können Sie feststellen, dass die Anzahl der Punkte, geschrieben |E|, sehr in der Nähe von p liegt. Der Satz von Hasse gibt das Intervall genau an. Jede dort mögliche Punktanzahl wird auch von mindestens einer elliptischen Kurve erreicht.
(Folie 2)
Um für eine gegebene Kurve einen Punkt bestimmen zu können, kann man in
E: y^2 = x^3 + ax + b mod p
entweder y wählen und daraus x bestimmen oder x wählen und daraus y bestimmen. Kubische Gleichungen sind komplizierter, man zerlegt das Polynom in Linearfaktoren.
Daher ist der zweite Weg der bessere, wähle x, rechne die rechte Seite aus, z.B. z = x^3 + ax + b mod p und bestimme eine Lösung für
y^2 = z mod p,
d.h. ziehe die Quadratwurzel.
Ein Teilproblem ist noch nachzuliefern: woher wissen wir, dass es eine Quadratwurzel gibt? Von vorneherein wissen wir es nicht. Genau wie in den reellen Zahlen gibt es Werte mit Quadratwurzel, etwa z=2 und y sei die Quadratwurzel von 2. Und in den reellen Zahlen hat z=-2 keine Quadratwurzel. Die reellen Zahlen haben einen entscheidenden Vorteil: man sieht am Minuszeichen, dass keine Quadratwurzel existiert.
Bei Zahlen mod p kann man es nicht direkt sehen, aber es gibt einen indirekten Weg:
Dies beschreibt der auf der Folie angegebene Test, dieser wird anhand von Beispielen ausgeführt.
(Folie 3)
Wenn die Primzahl p zur Klasse der Zahlen = 3 mod 4 gehört, dann ist die Berechnung einer Quadratwurzel in einer Formel leicht zu bewerkstelligen. (Überlegen Sie sich ein paar solcher Primzahlen, eine ist z.B. 103.)
Ab jetzt gehen wir davon aus, dass y^2 = z mod p eine Lösung hat. Sollte es keine Lösung haben, dann ist dies durch z^((p-1)/2) mod p = p-1 sofort erkennbar.
Die Formel hierfür ist y=z^((p+1)/4) mod p .
Dass dies eine Lösung ist, stellt man durch Quadrieren dieses y unmittelbar fest.
Im Falle p = 5 mod 8 gibt es ein zweistufiges Verfahren.
Zunächst wird y=z^((p+3)/8) mod p als Lösung ausprobiert. Dies ist in einem gewissen Sinne fast eine Lösung. Entweder ist y^2 = z mod p, dann ist man fertig. Oder es ist y^2 = -z mod p, und man muss dieses überflüssige Minuszeichen gewissermaßen noch herausoperieren. Der Trick ist, y leicht zu verändern, mit einem Multiplikator, sagen wir u, sodass u^2 = -1 mod p. Stellen wir uns für einen Moment vor, das funktioniert, dann haben wir (uy)^2 = (-1)*(-z) = z mod p. Also wie kommt man auf ein solches u? Das steht im roten Text auf der Folie.
(Folie 4)
Wir schauen uns die Situation für p mod 8 an.
Der einfache Fall p = 3 mod 4 bedeutet entweder p = 3 mod 8 oder p = 7 mod 8.
Der zusätzlich gelöste Fall war p = 5 mod 8. Die geraden Reste p = 0, 2, 4, oder 6 mod 8 kommen für Primzahlen nicht in Frage (die eine Ausnahme Primzahl =2 können wir ignorieren, kryptographisch relevante Primzahlen beginnen bei elliptischen Kurven oberhalb von 200 Bits).
Für den einzig übriggebliebenen Fall gibt es eine Erweiterung des Verfahrens von p = 5 mod 8, ein probabilistischer Polynomzeitalgorithmus von Tonelli/Shanks. Wer hier die Verbindung zu theoretischer Informatik und ihren Komplexitätsklassen herstellen möchte, kann unter probabilistischen Turingmaschinen weiter in abstrakte Rechenmodelle hinabsteigen ...
(Folie 5)
wir sehen die Verfahren an drei Beispielen illustriert: