Hyperelliptische Kurve

Eine hyperelliptische Kurve ist eine algebraische Varietät, d. h. eine Menge von Punkten aus einem Körper, die eine Polynomgleichung sowie einige Nebenbedingungen erfüllen. Elliptische Kurven sind spezielle hyperelliptische Kurven vom Geschlecht 1. Hyperelliptische Kurven spielen in der Kryptographie im Gegensatz zu elliptischen Kurven 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.

Definition

Sei $\mathbb{F}_{q}$ (mit q eine Primzahlpotenz) ein 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\geq1)$ ist eine Gleichung der Form

C: v² + h(u)v = f(u) in $\mathbb{F}[u,v]$

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

v² + h(u)v = f(u)

2v + h(u) = 0 partielle Ableitung nach v

h'(u)v − f'(u) = 0 partielle Ableitung nach u

erfüllt.

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 u² + u für eine $u\in\mathbb{F}_{q}:u\neq0$

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). Der Grund dafür liegt natürlich in der Endlichkeit des Rechners (Speicherplatz, Rechenzeit ist begrenzt). 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. Es wird sich um eine Gruppe handeln. 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 berechenbar ist - unter der Kenntnis von gewissen Zusatzinformationen jedoch (sog. Schlüsseln) wiederum effizient berechenbar ist (die Konstruktion sog. Trapdoor-One-Way-Funktionen muss möglich sein).

Abgrenzung zu elliptischen Kurven

Im Gegensatz zu elliptischen Kurven, die eine direkte Konstruktion einer Gruppe auf ihren Punkten erlaubt, ist dies bei einer hyperelliptischen Kurve nicht möglich. Man definiert hier formale Summen von Punkten, sog. Divisoren. Die Äquivalenzklasse der (noch 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, d.h. "ins Blaue hinein" ohne präzise Herleitung zunächst 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. 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 dem Punkt 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. Weiter gibt es eine Untergruppe von Divisoren, denen sich eine rationale Funktion zuordnen lässt, die besagten Divisor auf die oben beschriebene Weise konstruiert - nicht jede formale Summe von Punkten, also nicht jeder Divisor ist schließlich aus der o.g. Konstruktion heraus geboren. Diese Untergruppe wird mit $\mathbb{P}$, verbal die Gruppe der Hauptdivisoren bezeichnet. Auf der Äquivalenzklasse $\mathbb{D}^0/\mathbb{P}$ (genannt die Jacobische von C) lässt sich nun wiederum eine Verknüpfung definieren, die die Addition auf de 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