Hyperelliptische Kurve

spezielle algebraische Varietät

Eine hyperelliptische Kurve ist eine algebraische Varietät, 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

DefinitionBearbeiten

Eine hyperelliptische Kurve ist die Lösung eines Polynoms

 ,

wobei   ein Polynom vom Grad   mit   paarweise verschiedenen Wurzeln ist. Bei den ähnlich konstruierten elliptischen Kurven ist dagegen  .

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

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örperBearbeiten

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

Sei   (wobei   eine Primzahlpotenz) ein endlicher Körper und sei   der algebraische Abschluss von  . Eine hyperelliptische Kurve   mit Geschlecht   über     ist eine Gleichung der Form

 :   in  .

Außerdem gibt es keine Lösung  , welche die Gleichungen

 ,
  (partielle Ableitung nach  ),
  (partielle Ableitung nach  )

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:   ist normiert und vom Grad   und   vom Grad höchstens  

Reales Modell:   oder   ist normiert und vom Grad  . Wenn   ungerade ist, dann ist   normiert und vom Grad  . Wenn   gerade ist, dann ist   entweder vom Grad kleiner gleich   oder vom Grad   und der führende Koeffizient von   ist von der Form   für ein  .

Eine hyperelliptische Involution eines Punktes   wird als   definiert. Punkte, die dabei invariant sind, heißen Weierstraß-Punkte.

Konstruktion einer Gruppe auf Hyperelliptischen KurvenBearbeiten

VorbemerkungenBearbeiten

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   und   (die Gruppe ist hier multiplikativ geschrieben). Dann besteht das Problem des Angreifers darin,   zu finden (den „Logarithmus“).

Abgrenzung zu elliptischen KurvenBearbeiten

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 / AnmerkungenBearbeiten

Punkte im projektiven RaumBearbeiten

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 KonstruktionBearbeiten

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   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  . Auf der Äquivalenzklasse   (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.

LiteraturBearbeiten

  • 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

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  1. Hyper-elliptic curve, Encyclopedia of Mathematics, Springer
  2. Sylvain Duquesne, Tanja Lange, Arithmetic of hyperelliptic curves, Kapitel 14 in Cohen, Frey, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall, Taylor & Francis Group 2006, S. 303ff