Mathematik | Informatik
Kaspar Hui, 2004 | Basel, BS
Die Kryptographie mit elliptischen Kurven ist ein wesentlicher Bestandteil moderner Verschlüsselungstechnologien. Diese Arbeit untersucht die theoretischen Grundlagen und die Definition der elliptischen Kurven-Kryptographie in der mathematischen Theorie. Darüber hinaus wird im praktischen Teil eine eigene Python Bibliothek entwickelt, die eine einfache Implementierung von Verfahren der elliptischen Kurven-Kryptographie ermöglicht. Der Schwerpunkt liegt dabei auf der Erstellung eigener Kurven für praktische Anwendungen. Während reale Anwendungen üblicherweise endliche Körper Fp verwenden, konzentriert sich diese Arbeit auf den allgemeineren Fall im Körper Fq, ausschliesslich elliptische Kurven durch die kurze Weierstrass-Gleichung. Ausserdem werden die theoretischen Sicherheitseigenschaften von elliptischen Kurven und deren Implementierung untersucht, einschliesslich der Implementierung eines wichtigen Algorithmus zur Bestimmung der Anzahl der Punkte auf einer Kurve, was für die Überprüfung der Sicherheit entscheidend ist.
Fragestellung
Ziel dieser Arbeit ist es, die theoretischen Grundlagen der Kryptographie mit elliptischen Kurven zu untersuchen und darauf aufbauend eine Python-Bibliothek zu entwickeln, die eine einfache Implementierung dieser Verfahren ermöglicht. Dabei werden auch Sicherheitseigenschaften in Bezug auf eigene Kurven analysiert.
Methodik
Die Entwicklung dieser Arbeit umfasste eine gründliche Einarbeitung in die mathematischen Grundlagen und die Theorie der elliptischen Kurven anhand wissenschaftlicher Arbeiten. Im praktischen Teil wurden Aspekte der objektorientierten Programmierung angewandt. Zur Sicherstellung der Korrektheit wurden umfangreiche Tests sowohl während der Entwicklung als auch in Form von formalen Unit-Tests durchgeführt. Der Grossteil der Implementierung erfolgte in Python ohne externe Bibliotheken, wobei die Bibliothek Numpy für die Entwicklung einer effizienten und sicheren Kurve verwendet wurde.
Ergebnisse
Basierend auf den erlernten Grundlagen wurde eine funktionsfähige Python-Bibliothek erstellt und im Python Package Index (PyPI) veröffentlicht. Diese Bibliothek kann mit dem Python-Paketverwaltungsprogramm pip installiert werden. Eine spezielle Kurve in kryptographischer Grösse mit q = 47^46 wurde unter Verwendung einer effizienteren Arithmetik implementiert. Die Punktmultiplikation P * q dauert etwa eine halbe Sekunde. Obwohl die Kurve alle Sicherheitseigenschaften des nicht-interaktiven diskreten Logarithmus erfüllt, ist eine vollständige Sicherheit der gewählten Kurve aufgrund der kurzen Weierstrass-Gleichung nicht möglich.
Diskussion
Die Erstellung einer eigenen Implementierung des Schoof-Algorithmus war ein entscheidender Schritt, um die theoretische Sicherheit der eigenen Kurven bezüglich des diskreten Logarithmus selbst zu überprüfen. Die Laufzeit der Punktmultiplikation von etwa einer halben Sekunde ist für interne Tests ausreichend, für eine breitere Anwendung jedoch nicht optimal. Es ist anzumerken, dass die Bibliothek nicht für die Verarbeitung sensibler Daten geeignet ist, da das Risiko besteht, dass, selbst wenn die Kurve bezüglich des diskreten Logarithmus sicher ist, vertrauliche Informationen durch Verzweigungspunkt- und Cache-Timing-Angriffe durchsickern könnten.
Schlussfolgerungen
Die Arbeit untersuchte die theoretischen Grundlagen und Anwendungen der Kryptographie mit elliptischen Kurven. Die implementierte Python-Bibliothek stellt eine starke Kurve zur Verfügung und ermöglicht die Erstellung eigener Kurven, deren Sicherheitseigenschaften untersucht werden können. Die Laufzeit der Punktvervielfachung ist ausreichend, aber Verbesserungen sind möglich. Eine Implementierung in einer anderen Programmiersprache würde die Effizienz erheblich steigern. Die Bibliothek ist nicht für sensible Daten geeignet, um Sicherheitsrisiken zu vermeiden. Die Arbeit trägt zum Verständnis und zur Anwendung der Kryptographie mit elliptischen Kurven bei.
Würdigung durch den Experten
Dr. Gregor Seiler
Die Arbeit befasst sich mit der Arithmetik von elliptischen Kurven über endlichen Körpern und deren Anwendung in der Kryptographie. Es wird ein besonderer Fokus auf Kurven über Erweiterungskörpern gelegt, was neben der eigentlichen Kurvenarithmetik zu weiteren interessanten algorithmischen Fragestellungen führt. Ausserdem behandelt die Arbeit ein zentrales Verfahren zum Zählen der Kurvenpunkte. Der mathematische Rahmen ist sehr anspruchsvoll und die betrachteten Algorithmen wurden vom Wettbewerbsteilenehmer tief durchdrungen und in der Programmiersprache Python korrekt implementiert.
Prädikat:
hervorragend
Sonderpreis «Summer School of Science» gestiftet von der Metrohm Stiftung
Gymnasium Bäumlihof, Basel
Lehrer: Dr. Helmut Locher
