Hyperelliptische Kurve

Eine hyperelliptische Kurve ist eine algebraische Kurve, das heißt, eine Menge von Punkten aus einem Körper, die eine Polynomgleichung sowie einige Nebenbedingungen erfüllen.

Sie werden ähnlich konstruiert wie elliptische Kurven. Hyperelliptische Kurven spielen in der Kryptographie im Gegensatz zu diesen noch keine allzu große, jedoch zunehmende Rolle. Ihre Eigenschaften sind noch nicht weitgehend genug erforscht, um deren gesteigerte Nutzbarkeit für die Kryptographie abschätzen zu können. Zudem ist die Rechnung in hyperelliptischen Kurven komplizierter als in elliptischen Kurven, so dass deren derzeitige praktische Anwendung noch nicht nützlich erscheint.

Die hyperelliptische Kurve $y^{2}=x(x+1)(x-3)(x+2)(x-2)$

Definition

Eine hyperelliptische Kurve ist die Lösung eines Polynoms

$y^{2}=f(x)$,

wobei $f(x)$ ein Polynom vom Grad $n>4$ mit $n$ paarweise verschiedenen Wurzeln ist. Bei den ähnlich konstruierten elliptischen Kurven ist dagegen $n=3$.

Das Geschlecht $g$ wird durch den Grad des Polynoms bestimmt, für $n=2g+1$ oder $n=2g+2$ hat sie das Geschlecht $g$. Daraus folgt, dass das Geschlecht $g>1$ ist (der Fall $g=1$ entspricht elliptischen Kurven). Der Fall $2g+1$ heißt imaginäre hyperelliptische Kurve, der Fall $2g+2$ reelle hyperelliptische Kurve. Häufig werden sie für ungeraden Grad $n$ definiert, da der benachbarte gerade Fall $n+1$ auf den Fall $n$ reduziert werden kann.

Die Kurve hat in dieser Form einen singulären Punkt im Unendlichen, der durch Übergang zu einem nicht-singulären Modell in der birationalen Geometrie vermieden wird.

Neben der Betrachtung über den reellen und komplexen Zahlen werden sie auch über endlichen Körpern und den rationalen Zahlen im Rahmen der Zahlentheorie betrachtet. Da das Geschlecht größer 1 ist, haben sie nur endlich viele Punkte über den rationalen Zahlen (Vermutung von Mordell/Satz von Faltings).

Der Funktionenkörper einer hyperelliptischen Kurve (der Körper der hyperelliptischen Funktionen) ist eine quadratische Erweiterung des Körpers der rationalen Funktionen.

Hyperelliptische Kurven über einem endlichen Körper

Hier wird eine etwas andere Definition benutzt. Dabei werden auch elliptische Kurven als Kurven vom Geschlecht g=1 mit betrachtet, was sonst nicht üblich ist.

Sei $\mathbb {F} _{q}$ (wobei $q$ eine Primzahlpotenz) ein endlicher Körper und sei ${\overline {\mathbb {F} }}_{q}$ der algebraische Abschluss von $\mathbb {F} _{q}$. Eine hyperelliptische Kurve $C$ mit Geschlecht $g$ über $\mathbb {F} _{q}$ $(g\geq 1)$ ist eine Gleichung der Form

$C$: $y^{2}+h(x)y=f(x)$ in $\mathbb {F} _{q}[x,y]$.

Außerdem gibt es keine Lösung $(x,y)\in {\overline {\mathbb {F} }}_{q}\times {\overline {\mathbb {F} }}_{q}$, welche die Gleichungen

$y^{2}+h(x)y=f(x)$,

$2y+h(x)=0$ (partielle Ableitung nach $y$),

$h'(x)y-f'(x)=0$ (partielle Ableitung nach $x$)

erfüllt (das heißt, es werden nur nicht-singuläre Lösungen betrachtet).

Außerdem werden hyperelliptische Kurven in zwei Modelle unterschieden:

Imaginäres Modell: $f$ ist normiert und vom Grad $2g+1$ und $h(u)$ vom Grad höchstens $g$

Reales Modell: $h=0$ oder $h$ ist normiert und vom Grad $g+1$. Wenn $q$ ungerade ist, dann ist $f$ normiert und vom Grad $2g+2$. Wenn $q$ gerade ist, dann ist $f$ entweder vom Grad kleiner gleich $2g+1$ oder vom Grad $2g+2$ und der führende Koeffizient von $f$ ist von der Form $x^{2}+x$ für ein $x\in \mathbb {F} _{q}\setminus \{0\}$.

Eine hyperelliptische Involution eines Punktes $P=(x,y)$ wird als $-P=(x,-y-h(x))$ definiert. Punkte, die dabei invariant sind, heißen Weierstraß-Punkte.

Konstruktion einer Gruppe auf hyperelliptischen Kurven

Vorbemerkungen

Interessant in der Kryptographie sind die Punktmengen, die die Gleichung erfüllen und gleichzeitig in einem endlichen Körper sind (und die Nebenbedingungen der Definition erfüllen). Um die Kurve im Sinne der Kryptographie zu nutzen, muss eine algebraische Struktur, also eine Vorschrift, um auf diesen Punkten rechnen zu können, definiert werden – in diesem Fall handelt es sich um eine Gruppe. Zudem muss die algebraische Struktur derart beschaffen sein, dass sich in ihr zwar effizient rechnen lässt, jedoch unter gewissen Vorkehrungen die Umkehrung von Rechenoperationen nur sehr ineffizient, unter der Kenntnis von gewissen Zusatzinformationen jedoch (sog. Schlüsseln) wiederum effizient auszuführen ist (die Konstruktion sog. Trapdoor-One-Way-Funktionen muss möglich sein). Dies geschieht über das im Allgemeinen schwierige Problem, den diskreten Logarithmus in der Gruppe zu berechnen. Gegeben sind ein Gruppenelement $g$ und $g^{a}$ (die Gruppe ist hier multiplikativ geschrieben). Dann besteht das Problem des Angreifers darin, $a$ zu finden (den „Logarithmus“).

Abgrenzung zu elliptischen Kurven

Im Gegensatz zu elliptischen Kurven, die eine direkte Konstruktion einer Gruppe auf ihren Punkten erlaubt (Tangenten-Sekanten-Konstruktion), ist dies bei einer hyperelliptischen Kurve nicht möglich, da zum Beispiel eine Gerade hier mehr als drei Schnittpunkte (jeweils mit Vielfachheit gezählt und der Punkt im Unendlichen wird auch berücksichtigt) mit der Kurve hat. Man definiert hier formale Summen von Punkten, sog. Divisoren. Die Äquivalenzklasse der (im Folgenden noch zu definierenden) Gruppe der Divisoren vom Grad 0 modulo der Hauptdivisoren wird die Jacobische der hyperelliptischen Kurve genannt. Auf der Jacobischen ist dann die Definition einer Gruppe mit den gewünschten Eigenschaften möglich.

Grundlegende Definitionen / Anmerkungen

Punkte im projektiven Raum

Wie bereits in der ersten Definition bemerkt, handelt es sich bei Punkten auf der Kurve C entweder um Paare von Zahlen, die die Gleichung der Kurve erfüllen oder um den Punkt im Unendlichen. Im Gegensatz dazu heißen die Paare von Zahlen, die die Gleichung erfüllen, auch endliche Punkte. Der Punkt im Unendlichen wird eingeführt, da die Kurve im projektiven Raum interpretiert wird. Es handelt sich um einen Kunstgriff, um die später zu definierenden Vielfachheiten von Schnittstellen von Punkten der Kurve mit rationalen Funktionen, die die Kurve schneiden, auszugleichen. Dies wird später im Artikel noch genauer gefasst.

Heuristik / Idee zur Konstruktion

Bezugnehmend auf den letzten Unterabschnitt soll kurz heuristisch die Idee der Konstruktion dargestellt werden. Damit wird auch die Idee des eben erwähnten Kunstgriffes deutlich werden. Einem endlichen Punkt P der Kurve C soll eine Zahl (Ordnung) zugeordnet werden, die zudem von einer rationalen Funktion abhängt, die die Kurve in P schneidet. Die Ordnung gibt dann an, in welcher Vielfachheit die rationale Funktion die Kurve C schneidet. Geometrisch wäre ein Schnitt der Vielfachheit 1 der „klassische“ Schnitt, also wo die Funktionen (Kurve und rationale Funktion) sich nicht aneinander „anschmiegen“; Vielfachheit 2 wäre ein tangentialer Schnitt etc. Die rationale Funktion schneidet die Kurve jedoch evtl. noch in anderen Punkten. Diesen kann dann weiter eine Vielfachheit zugeordnet werden. Die übrigen erhalten die Vielfachheit 0. Der Punkt im Unendlichen erhält dann die Vielfachheit, die der Summe der Vielfachheiten der endlichen Punkte entspricht. Damit ist die Gesamtsumme gleich 0 (Pole wie hier im Unendlichen erhalten negatives Vorzeichen und einen Betrag entsprechend der Polordnung). Die rationale Funktion schneidet damit die Gerade im Unendlichen (s. Projektive Geometrie) in ebendieser Vielfachheit. Die formale Summe dieser Punkte wird als Divisor bezeichnet. Die Menge der Divisoren, deren Summe der Vielfachheiten (inklusive des Punkts im Unendlichen) sich zu 0 ergibt, ist eine Untergruppe der Gesamtmenge der Divisoren (mit einer geeignet zu definierenden Verknüpfung) und wird mit $\mathbb {D} ^{0}$ bezeichnet. Die Untergruppe von Hauptdivisoren, denen sich gemäß der obigen Konstruktion eine rationale Funktion zuordnen lässt (Divisor einer rationalen Funktion auf der Riemannschen Fläche der hyperelliptischen Kurve), sei $\mathbb {P}$. Auf der Äquivalenzklasse $\mathbb {D} ^{0}/\mathbb {P}$ (genannt die Jacobi-Varietät von C) lässt sich nun wiederum eine Verknüpfung definieren, die die Addition auf der hyperelliptischen Kurve ermöglicht.

Literatur

• Cohen, Henry und Frey, Gerhard: Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall, Taylor & Francis Group 2006
• Koblitz, Neal: Algebraic Aspects of Cryptography, Algorithms an Computation in Mathematics, Springer 1997

Weblinks

• Menezes, An elementary introduction to hyperelliptic curves, University of Waterloo (PDF; 284 kB)
• Hyperelliptic Curve, Mathworld