Blady, Guido:

Punktezählalgorithmen für den Hecke-Operator und Anwendungen auf Modulkurven vor Geschlecht 4

Duisburg, Essen (2007), IV, 117 S.
Dissertation / Fach: Mathematik
Fakultät für Mathematik
Frey, Gerhard (Doktorvater, Betreuerin)
Stichtenoth, Henning (GutachterIn)
Dissertation
Abstract:
Der Einsatz der Public-Key Kryptografie zur elektronischen Signatur und Verschlüsselung ist aus unserer heutigen, vernetzten Welt nicht mehr wegzudenken. Aufgrund der niedrigen Schlüssellängen erhalten Kryptosysteme, die auf Jacobischen von Kurven basieren, erhöhte Aufmerksamkeit und werden im Fall elliptischer Kurven bereits in Mobiltelefonen, Reisepässen und in vielen anderen Bereichen eingesetzt.

Will man ein Kryptosystem auf Jacobischen von Kurven aufbauen, ist es wichtig, dass die Gruppenordnung der k-rationalen Punkte der Jacobischen über dem endlichen Körper k einen großen Primfaktor enthält. Das diskrete Logarithmusproblem kann sonst mit Hilfe des chinesischen Restsatzes zu schnell gelöst werden, was das Kryptosystem unbrauchbar machen würde. Wir benötigen also Methoden zur Bestimmung der k-rationalen Punkte der Jacobischen einer Kurve. Für Kurven von Geschlecht 1 bis 3 und hyperelliptische Kurven von Geschlecht 4 gibt es zahlreiche effiziente Methoden, deren Ansatz entscheidend von der Charakteristik p des Grundkörpers k beeinflußt wird.

Diese Methoden lassen sich leider nicht auf großes p und nichthyperelliptische Kurven von Geschlecht 4 übertragen. Wir stellen in dieser Arbeit einen Algorithmus zur Bestimmung der IF_p-rationalen Punkte der Jacobischen von allgemeinen Modulkurven vor, der auf der Berechnung des Hecke-Operators T_p basiert und mit seiner linearen Komplexität in Zeit- und Speicheraufwand gerade für die zahlreichen nichthyperelliptische Modulkurven von Geschlecht 4 effizient ist. Wegen des Index-Calculus Angriffs von C. Diem gelten Kurven von Geschlecht 4 erst ab 172-Bit großer Gruppenordnung als sicher. Wir zeigen in expliziten Beispielen, dass unser Algorithmus in dieser Grössenordnung praktikabel ist. Der Algorithmus ist voll parallelisierbar und in allen Eingabegrößen simultanisierbar.

C. Paar, J. Pelzl und T. Wollinger schlagen hyperelliptische Kurven von Geschlecht 4 über Körpern mit 32-Bit für die Implementation von Kryptosystemen für ARM Prozessoren vor. Unser Algorithmus kann Beispiele dafür leicht berechnen und daher fügen wir dieser Arbeit im Anhang eine ganze Reihe davon hinzu.