Das Gebiet, welches wir uns nun näher beschäftigt, ist die Ellipic Curve Cryptography (ECC) - eine weitere Möglichkeit, Public-Key-Kryptoverfahren zu erzeugen.
Warum eine augenscheinlich komplizierte mathematische Struktur einführen, wenn doch RSA und DSA langjährig erprobte und offenbar sichere Public Key Verfahren sind?
Eine Antwort auf diese Frage enthält typischerweise folgende Aspekte:
(Folie 1)
Die Situation Anfang der 1990er Jahre ist oben rechts beschrieben. In dieser Zeit wurden elliptische Kurven für die Kryptographie vorgeschlagen (Victor Miller, Neal Koblitz)
Wir schauen für eine Weile auf die reelle Ebene mit einem gewöhnlichen zweidimensionalen (x,y)-beschrifteten Koordinatensystem. Vorgegeben ist eine Gleichung der Form oben rechts
y^2 = x^3 + ax + b.
Hierbei sind a und b vom späteren Nutzer (eines Kryptosystems) frei wählbare aber ab diesem Zeitpunkt feste Parameter (des Kryptosystems).
Beispielsweise entsteht mit a=b=1 die Gleichung y^2 = x^3 + x + 1.
Nun kann man im Koordinatensystem alle die Punkte (x,y) markieren, die diese Gleichung erfüllen. Wegen y^2 ist das Bild offenbar symmetrisch, da für einen solchen Punkt (x,y) auch der Punkt (x,-y) die Gleichung erfüllt.
Damit hätten wir schon einmal eine Menge von Objekten, die hierdurch beschrieben werden. Das ist noch nicht die komplette Menge, es fehlt noch ein Element, dazu aber später.
{ (x,y) | y^2 = x^3 + ax + b }
Wie soll man mit den Punkten (x,y) rechnen? Der natürliche Ansatz schlägt fehl!
Würde man (x1,y1) + (x2,y2) wie in der Vektorrechnung als (x1+x2,y1+y2) definieren, hätte man mit (x1+x2,y1+y2) fast immer einen Punkt, der nicht auf der Kurve liegt. Also muss es anders gehen.
Wir nennen P1=(x1,y1), P2=(x2,y2) und bilden P3=P1+P2 wie folgt:
Mit dieser Operation "+" wird die Menge der Punkte eine Gruppe, wenn man ein neutrales Element künstlich hinzufügt. Der Punkt O (siehe unten auf der Folie) lässt einen Punkt P unverändert (P+O=P). Der zu P inverse Punkt (-P) ist an der x-Achse gespiegelt und man definiert P+(-P)=O.
Also ist die Menge der Punkte E wie folgt gegeben
E = { (x,y) | y^2 = x^3 + ax + b } ∪ { O }
Eine Lücke gilt es nun noch zu schließen: was passiert bei P + P? Aus der Gerade durch zwei Punkte wird die Tangente an die Kurve, mit einer Erinnerung an Differenzenquotienten, Grenzwerte und Ableitungen liegen Sie hier genau richtig.
Links unten sehen Sie die aus diesen Zusammenhängen entstehenden Formeln. Wir nennen die Steigung der Geraden g wie üblich m. Dann ist
g(x) = mx + d
für ein geeignetes d (das sonst gewohnte b ist leider schon als Parameter der Kurve verbraucht...).
Nun transportieren wir das vorhin gesehene Setting in die diskrete Welt modulo p. Strukturell sind die Restklassen mod p wie die reellen Zahlen ein Körper, daher folgen die Grundrechenarten den gleichen Gesetzen. Die Anschauung ist allerdings nicht mehr gegeben, die Gerade g(x) etwa lässt sich nicht mehr "sehen".
Das Objekt unseres Interesses ist nun also eine elliptische Kurve
E = { (x,y) | y^2 = x^3 + ax + b mod p } ∪ { O }
Da es hier höchstens p^2 Punkte (x,y) geben kann, ist die Kurve also endlich, in der Tat werden wir die Anzahl der Punkte noch weiter eingrenzen können.
Wir werden uns mit folgenden algorithmischen Problemen auseinandersetzen:
Wir schließen ab mit einem Beispiel mod 7.
Die Kurve y^2 = x^3 + x + 4 mod 7 hat 10 Punkte, die man durch Ausfüllen einer Wertetabelle und Auszählung aller Möglichkeiten bestimmen kann. Es empfiehlt sich, eine Liste von allen y^2-Werten parat zu haben. Hier gibt es dann jeweils ±y als Möglichkeiten.
Exemplarisch werden drei Punktadditionen vorgeführt.