Punktezählen auf elliptischen Kurven

Elektrotechnik Studienarbeiten (März 2007 - Dezember 2007) crypt

Betreuer

Michael Naehrig,

Abstract

Kryptographische Anwendungen, die auf dem Problem des diskreten Logarithmus in Punktgruppen elliptischer Kurven Über endlichen Körpern beruhen, erfordern die Kenntnis der Gruppenordnung, d.h. der Anzahl der Punkte auf einer gegebenen elliptischen Kurve. Zur Lösung dieses Problems gibt es einerseits Verfahren, mit denen sich zu vorgegebener Gruppenordnung Parameter einer Kurve konstruieren lassen, die die gewünschte Anzahl von Punkten enthält. Andererseits existieren Algorithmen zur Berechnung der Gruppenordnung bei gegebener Kurvengleichung, sogenannte Punktezählalgorithmen. Ziel dieser Studienarbeit ist die Implementation einer Variante des Punktezählalgorithmus von Schoof in C++. Der Schoof-Algorithmus bestimmt die Gruppenordnung, indem er diese zunächst modulo einer Reihe kleiner Primzahlen berechnet. Mit dem Chinesischen Restsatz kann dann auf die Anzahl der Punkte auf der Kurve geschlossen werden. Die Bearbeitung dieser Studienarbeit umfasst die folgenden Punkte: - Nutzung der GMP Library zur Verwendung beliebig großer Zahlen, - Arithmetik in endlichen Körpern beliebiger Größe unter Verwendung von GMP, - Test, ob vorgegebene Parameter eine elliptische Kurve beschreiben, - Test, ob ein vorgegebener Punkt auf der Kurve liegt, - Implementierung des Gruppengesetzes: Punktaddition, Punktvervielfachung (Double and Add- Methode), - Implementierung einer Variante des Schoof-Algorithmus zur Bestimmung der Anzahl der Punkte auf der Kurve, - Dokumentation des Programms in LaTEX.