Zahlentheoretische Grundlagen der Kryptografie

Elliptische Kurven

 aufwärts

Wir betrachten elliptische Kurven zunächst in der Ebene des reelle Zahlen2. Für die krypto­grafische Anwendung wird später der Körper reelle Zahlen durch den endlichen Körper ganze Zahlenn ersetzt.1) Die hier gewählte Darstellung lehnt sich an [SSP 08] an.

Definition:  Eine elliptische Kurve ist eine Menge von Punkten (x, y) in der Ebene, die folgender Gleichung genügen:

E  =  { (x, y)  |  y2  =  x3 + ax + b }  vereinigt  {u}

Die Parameter a und b sind reelle Zahlen. Der Punkt u ist ein unendlich ferner Punkt.

In Bild 1 ist eine typische elliptische Kurve in der Gegend rund um den Nullpunkt des Koordinaten­systems dargestellt.

Verknüpfung von Punkten von E

Auf der Menge E der Punkte einer elliptischen Kurve wird in folgender Weise eine Verknüpfung definiert. Zwei Punkte p und q werden verknüpft, indem eine Gerade g durch p und q gelegt wird. Diese Gerade schneidet die Kurve E in einem dritten Punkt s. Dieser Punkt s wird an der x-Achse gespiegelt, der hierdurch entstehende Punkt r ist das Ergebnis der Verknüpfung:

p • q  =  r

Man beachte, dass r wieder ein Punkt der Kurve ist, weil diese symmetrisch zur x-Achse verläuft (Bild 1).

 

Bild 1: Schnittpunkte einer Geraden mit einer elliptischen Kurve
Bild 1: Schnittpunkte einer Geraden mit einer elliptischen Kurve

Einige Sonderfälle sind zu betrachten.

Wenn p = q ist, so ist die Gerade durch p und q die Tangente an die Kurve E im Punkt p. Bei Tangenten zählt der Berührpunkt als Zweifach­punkt, so dass die Gerade und die Kurve auch in diesem Fall drei Punkte gemeinsam haben. Bei der Tangente durch einen Wendepunkt der Kurve zählt der Wendepunkt sogar als Dreifach­punkt.

Wenn einer der Punkte der unendlich ferne Punkt u ist, so ist das Ergebnis der Verknüpfung der andere Punkt. D.h. es gilt für alle Punkte p Element E

p • u  =  u • p  =  p

Wenn die Punkte p und q an der x-Achse gespiegelt zueinander liegen, so verläuft die Gerade g parallel zur y-Achse. Dann ist der dritte Schnittpunkt s der unendlich ferne Punkt u. Der unendlich ferne Punkt u, an der x-Achse gespiegelt, ergibt wiederum den unendlich fernen Punkt u.

Gruppenstruktur von E

Die Menge E bildet zusammen mit der oben definierten Verknüpfung  •  eine abelsche Gruppe.

Die Verknüpfung ist also assoziativ. Das neutrale Element der Gruppe ist der unendlich ferne Punkt u. Jeder Punkt p hat ein inverses Element p-1, dies ist der an der x-Achse gespiegelte Punkt, denn es gilt p • p-1 = u. Und schließlich ist die Verknüpfung sogar kommutativ, denn die Gerade durch p und q ist gleich der Geraden durch q und p, der dritte Schnittpunkt s ist somit derselbe.

Berechnung des Schnittpunktes s

Wir setzen zunächst der Einfachheit halber voraus, dass keiner der angegebenen Sonderfälle vorliegt, d.h. wir setzen voraus, dass die x-Koordinaten der beiden Punkte p und q verschieden sind.

Eine Gerade g ist die Menge aller Punkte (x, y), die der Geraden­gleichung y = mx + c genügen:

g  =  { (x, y)  |  y = mx + c }

Hierbei ist m die Steigung der Geraden, c ist der y-Achsen­abschnitt.

Die Schnitt­punkte der Geraden g mit der elliptischen Kurve E liegen im Durchschnitt der ent­sprechenden Punktmengen; für die Schnitt­punkte gelten also jeweils beide Gleichungen. Durch Einsetzen von

y  = mx + c

in die Gleichung von E ergibt sich

(mx + c)2  =  x3 + ax + b

bzw. aus­multipliziert und geordnet

-x3 + m2x2 + (2mc – a)x + c2 – b  =  0

Zwei der Lösungen dieser Gleichung sind bekannt, nämlich xp und xq, die x-Koordinaten der Punkte p und q. Gesucht ist xs, die x-Koordinate des dritten Schnitt­punktes s.

Allgemein gilt für die drei Nullstellen xp, xq und xs eines Polynoms 3. Grades

d(x – xp)(x – xq)(x – xs)  =  0

Durch Aus­multiplizieren und Koeffizientenvergleich mit der obigen Gleichung ergibt sich

d = -1   und

m2  =  xp + xq + xs

Somit gilt für die x-Koordinate des dritten Schnitt­punktes s

xs  =  m2 – xp – xq

Die Steigung m der Geraden lässt sich mithilfe der beiden Punkte p und q berechnen:

m  =  
yp – yq
xp – xq

Mithilfe der Formel für die Steigung lässt sich auch die y-Koordinate des Punktes s bestimmen:

ys  =  m(xs – xp) + yp

Sonderfälle

Wenn die Punkte p und q an der x-Achse gespiegelt zueinander liegen, d.h. wenn die x-Koordinaten gleich sind und die y-Koordinaten zueinander negativ sind, so verläuft die Gerade g durch p und q parallel zur y-Achse. Der dritte Schnittpunkt mit der elliptischen Kurve ist dann der unendlich ferne Punkt u.

Wenn die Punkte p und q gleich sind, so ist die Gerade g die Tangente an die elliptische Kurve im Punkt p. Die Steigung m der Tangente ergibt sich aus den partiellen Ableitungen der Gleichung der elliptischen Kurve E im Punkt p:

m  =  
3xp2 + a
2yp
Formel für die Verknüpfung

Unter Berück­sichtigung der Sonderfälle ergibt sich somit folgende Berechnungs­vorschrift für die Verknüpfung zweier Punkte p und q der elliptischen Kurve E:

p • q  =   geschweifte Klammer
p    falls q = u
q    falls p = u
u    falls xp = xq   und   yp =  – yq
r    sonst mit   xr = m2 – xp – xq   und   yr = m(xp – xr) – yp

Zu beachten ist außerdem, dass die Steigung m der Geraden auf unter­schiedliche Weise berechnet wird, je nach dem, ob die Punkte p und q gleich oder verschieden sind.

Elliptische Kurven über endlichen Körpern

Alle gezeigten Berechnungen lassen sich statt im Körper reelle Zahlen der reellen Zahlen auch in anderen Körpern durchführen. In der Kryptografie wird der endliche Körper ganze Zahlenn verwendet, wobei n eine Primzahl mit n>3 ist. Der Körper ganze Zahlenn besteht aus den ganzen Zahlen {0, ..., n-1}, Addition und Multi­plikation werden modulo n durchgeführt.

Da ganze Zahlenn eine endliche Menge ist, besteht die elliptische Kurve als Teilmenge von ganze Zahlenn2 auch nur aus endlich vielen Punkten. Bild 2 zeigt die Punkte der elliptischen Kurve y2 = x3 – 2x + 3 über dem Körper ganze Zahlen23.

Elliptische Kurve über einem endlichen Körper
Bild 2: Elliptische Kurve über ganze Zahlen23

Die Punkte einer elliptischen Kurve über einem endlichen Körper bilden keine zusammen­hängende Linie. Dennoch bleibt die Anschaulich­keit der Verknüpfung von zwei Punkten p und q erhalten: Eine Gerade, die durch zwei Punkte der elliptischen Kurve gezogen wird, erreicht irgendwann einen dritten Punkt der elliptischen Kurve. Gegebenen­falls wird die Gerade, wenn sie das Bild am linken, rechten, oberen oder unteren Rand verlässt, am gegenüber liegenden Rand wieder herein­geführt. Dies ist durch die Modulo-Rechnung bedingt, denn z.B. lassen sich bei n = 23 die Ränder x = -11 und x = 12 miteinander identifizieren, da -11 kongruent 12  (mod 23) gilt.

Die Berechnungs­vorschrift für die Verknüpfung von Punkten bleibt ebenfalls gültig. Zu beachten ist nur, dass bei der Berechnung der Steigung m einer Tangente der Teilausdruck 2yp durch yp + yp ersetzt werden muss, da eine Multi­plikation der reellen Zahl 2 mit einem Element der Menge ganze Zahlenn nicht definiert ist. Ent­sprechendes gilt für den Teilausdruck 3xp2.

Anwendung in der Kryptografie

Wird ein Punkt g auf einer elliptischen Kurve E über ganze Zahlenn gewählt und v-mal mit sich selbst verknüpft, so lässt sich aus dem Ergebnis q = gv nicht auf v zurück­schließen (Problem des diskreten Logarithmus elliptischer Kurven – Elliptic Curve Discrete Logarithm Problem ECDLP). Voraus­setzung ist natürlich, dass die beteiligten Zahlen n und v sehr groß sind, so dass es zu lange dauert, die Lösung durch Ausprobieren heraus­zufinden.

Diese Tatsache wird beispiels­weise bei der Diffie-Hellman-Schlüssel­vereinbarung ausgenutzt.

Implementierung

In der Implementierung in der Programmier­sprache Python dient die Klasse EcPoint zur Darstellung von Punkten auf der elliptischen Kurve. Die Methode __mul__ dient zur Verknüpfung zweier Punkte; sie überschreibt den Operator *, so dass mit der Anweisung r = p*q das Ergebnis r der Verknüpfung zweier Punkte p und q berechnet wird. Die Methode __pow__ überschreibt den Exponentiations-Operator **; sie ist als schnelle Exponentiation mittels Square-and-Multiply implementiert.

Je nach dem, ob der Parameter a und die Koordinaten der Punkte der elliptischen Kurve als Elemente des Körpers reelle Zahlen der reellen Zahlen oder als Elemente eines Körpers ganze Zahlenn angegeben werden, rechnet das Programm mit den Rechen­operationen des ent­sprechenden Körpers.

Hierzu ist es erforderlich, eine Klasse ModInt zur Repräsentation von Elementen des Körpers ganze Zahlenn vorzusehen, in der die Rechen­operatoren +, -, * und / entsprechend definiert sind. Dies geschieht, indem mit Methoden __add__, __sub__, __mul__ und __div__ die ent­sprechenden Rechen­operatoren über­schrieben werden.

Diese Klassen EcPoint und ModInt finden sich in der Python-Implementierung.

Literatur

[SSP 08]J. Swoboda, S. Spitz, M. Pramateftakis: Kryptographie und IT-Sicherheit. Vieweg+Teubner (2008)

 


1)   Wenn n eine Primzahl ist, bildet die Menge ganze Zahlenn einen Körper. Üblich sind in diesem Fall auch die Bezeich­nungen Zahlenkörpern oder GF(n).

 

Weiter mit:  [Python-Implementierung]  oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 10.03.2011   Updated: 15.03.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik