|
Diplomarbeit: |
|
Um den Ausführungen über meine Diplomarbeit besser folgen zu können, empfiehlt es sich vielleicht, sich zuvor einen kleinen Überblick über Kryptographie und elliptische Kurven zu verschaffen. Sie finden hier eine kurze Übersicht über Kryptographie und hier einige Tatsachen über elliptische Kurven. |
|
Meine Diplomarbeit habe ich bei Frau Priv.Doz. Dr. Annette Werner im Fachbereich Mathematik und Informatik der Westfälischen Wilhelms-Universität in Münster geschrieben. Dieser Arbeit ging ein halbjähriges Praktikum als Diplomand bei der IT-Services and Solutions GmbH in Köln voraus. Im Rahmen der Arbeit mit dem Titel Punkte zählen auf elliptischen Kurven - Der Schoof-Elkies-Atkin-Algorithmus habe ich mich mit Public-Key-Kryptographie beschäftigt, genauer gesagt mit Kryptographie mit elliptischen Kurven über endlichen Körpern. Damit elliptische Kurven für diese Zwecke gebraucht werden können, müssen sie gewissen Kriterien genügen, insbesondere muss ihre Punktezahl, die über einem endlichen Körper ebenfalls endlich ist, über einen sehr großen Primteiler verfügen. Um dies kontrollieren zu können, muss man die Punktezahl effektiv bestimmen können. Genau diese Aufgabe übernimmt der Algorithmus von Schoof, Elkies und Atkin, kurz SEA-Algorithmus genannt. In meiner Arbeit habe ich den Algorithmus genau untersucht und die Ergebnisse mittels eines Programms, in dem der SEA-Algorithmus implementiert ist, illustriert. |
|
Ausgangssituation: |
|
Nachdem ich während meines Praktikums umfangreiche Daten für eine spezielle Implementierung des SEA-Algorithmus sammeln konnte (diese stammt aus dem Miracl-Programmpaket, das als Freeware von Shamus Software / Irland bereitgestellt wird), war das Ziel meiner Arbeit einerseits eine genaue Beschreibung des dem SEA-Algorithmus zugrunde liegenden Schoof-Algorithmus und andererseits eine darauf aufbauende Behandlung der Verbesserungen im SEA-Algorithmus. Während der Schoof-Algorithmus für kryptographisch relevante Größenordnungen nicht mehr praktikabel ist, weist der SEA-Algorithmus entscheidende Vorteile in der Performance auf, so dass z.B. die angesprochene Implementierung von SEA selbst für Laien eine Möglichkeit bietet, kryptographisch starke elliptische Kurven zu erzeugen. |
|
Inhalt, Ergebnisse und Fazit: |
|
Obwohl die praktischen Aspekte meines Themas bei der bisherigen Beschreibung überwiegen, muss festgehalten werden, dass die Arbeit vorwiegend rein mathematischer Natur ist. Der erste Teil der Arbeit bildet zunächst eine Einführung in den Themenkomplex elliptischer Kurven über endlichen Körpern, in dem auf grundlegende Definitionen und Eigenschaften eingegangen wird. Den Schwerpunkt dieses Teiles bildet die Entwicklung des Satzes von Hasse, der eine bereits sehr genaue Abschätzung der Punktezahl einer elliptischen Kurve liefert. |
|
Im zweiten Teil wird der Schoof-Algorithmus genau beschrieben, wobei zuvor alle wichtigen Bausteine des Algorithmus entwickelt werden. Anschließend wird ein numerisches Beispiel zur Illustration des Algorithmus angeführt. Der dritte Teil mit der Behandlung des SEA-Algorithmus bildet den Kern der Arbeit, in dem explizit auf die Unterschiede und Verbesserungen zu Schoof eingegangen wird. Insbesondere die beiden hauptsächlichen Module, die so genannte Algorithmen von Atkin und von Elkies, werden vertieft untersucht. Im Verlauf dieses Themenkomplexes werden zusätzlich Aspekte elliptischer Kurven über den komplexen Zahlen studiert. |
|
In einem Anhang wird schließlich die Miracl-Implementierung von SEA im Zusammenhang zu den im dritten Teil entwickelten Ergebnissen beschrieben und ausführlich ein konkretes numerisches Beispiel dokumentiert. Darin ist es mir gelungen, die Punktezahl einer elliptischen Kurve über einem Grundkörper mit 91-stelliger Charakteristik zu bestimmen. Da diese zusätzlich prim ist, ist die elliptische Kurve für kryptographische Zwecke sehr gut geeignet. |
|
Als Fazit meiner Untersuchungen kann ich festhalten, dass der SEA-Algorithmus ein effizientes Hilfsmittel bei der Bestimmung der Punktezahl einer elliptischen Kurve ist. Es ist somit auch in praktischen Anwendungen möglich, kryptographisch starke elliptische Kurven zu finden, die dann für kryptographische Verfahren eingesetzt werden können. Heutzutage ist es zwar noch üblich, das RSA-Verfahren für Verschlüsselungen zu benutzen, allerdings bieten elliptische Kurven eine ernsthafte Alternative zu diesem Verfahren, deren Vorteile gerade bei speicherplatzintensiven Anwendungen zur Geltung kommen. Es ist auf lange Sicht davon auszugehen, dass elliptische Kurven für kommerzielle Anwendungen eine sehr wichtige Rolle spielen werden. |
|
Anmerkung: Im November 2003 ist eine überarbeitete und erweiterte Fassung meiner Diplomarbeit in Form eines Buches mit der ISBN 3-937312-22-6 beim Verlagshaus Monsenstein und Vannerdat in Münster erschienen. Mehr Details dazu befinden sich hier. |
 |
 |
 |
 |
 |
 |
 |
 |
