Efficient Algorithms for Generating Elliptic Curves over Finite Fields Suitable for Use in Cryptography

Baier, Harald (2002)
Efficient Algorithms for Generating Elliptic Curves over Finite Fields Suitable for Use in Cryptography.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

URL / URN: urn:nbn:de:tuda-tuprints-2116

Kurzbeschreibung (Abstract)

The subject of the thesis at hand is the description of an efficient algorithm for finding an elliptic curve over a finite prime field of large characteristic suitable for use in cryptography. The algorithm is called cryptoCurve. It makes use of the theory of complex multiplication. Our work relies on proposals of A.-M.Spallek and G.J.Lay/H.G.Zimmer. However, their work leaves several important questions and problems unanswered. First, neither author presents an algorithm to find a suitable cardinality, that is a prime field and a cardinality of a suitable elliptic curve group. We develop and describe a very efficient algorithm for this task; in addition, we give upper bounds of its complexity. In this efficient algorithm the prime field may not be chosen in advance. However, in some cases the field is given first. For instance, all international cryptographic standards which describe an algorithm for finding a suitable cardinality, make use of the latter approach (P1363, Chapter A.14.2.3, p.155, X9.62, Chapter E.3.2.c, p.115-116). We show how to significantly speed up these algorithms. Second, no previously proposed algorithm for the generation of an elliptic curve considers the class number of the endomorphism ring of the curve. The German Information Security Agency requires the class number of the maximal order containing the endomorphism ring to be at least 200. Our algorithm cryptoCurve respects this condition. Third, we develop and thoroughly investigate different methods to compute class polynomials. The computation of a class polynomial is an important subalgorithm in the complex multiplication approach. In general the integer coefficients of a class polynomial are very large. Hence their computation in practice is rather difficult. It was believed in the cryptographic community that only class polynomials of low degree, say of degree at most 50, are amenable to the complex multiplication approach. However, using our efficient algorithm, we are able to compute a class polynomial of degree up to 3000 in reasonable time, that is in less than 10 minutes on an ordinary PC. In addition, we are able to compute a class polynomial of degree 15000 on the same computer in less than two days. Fourth, we carry out a detailed practical investigation of the floating point precision needed to compute a class polynomial. The precision in use is important for the run time to compute a class polynomial in practice. However, in order to get a correct result, we have to choose the floating point precision with care. As of today, different precisions were proposed. All of them are only based on heuristic arguments, and none of the authors presents a practical investigation. In addition, none of the cryptographic standards P1363 or X9.62 gives a hint on how to choose an appropriate floating point precision. Furthermore, in case of the class polynomial due to N.Yui and D.Zagier, which uses Weber functions, we propose a new floating point precision to compute this polynomial in practice. Our precision yields a significant performance improvement. Sample tests show an acceleration of about 45 % in practice compared to the precision proposed by Lay/Zimmer. All algorithms of this thesis are implemented in C++ and available via the LiDIA module gec.

Typ des Eintrags:

Dissertation

Erschienen:

2002

Autor(en):

Baier, Harald

Art des Eintrags:

Erstveröffentlichung

Titel:

Efficient Algorithms for Generating Elliptic Curves over Finite Fields Suitable for Use in Cryptography

Sprache:

Englisch

Referenten:

Buchmann, Prof. Dr. Johannes ; Köhler, Prof. Dr. Günter

Berater:

Buchmann, Prof. Dr. Johannes

Publikationsjahr:

14 Mai 2002

Ort:

Darmstadt

Verlag:

Technische Universität

Datum der mündlichen Prüfung:

7 Mai 2002

URL / URN:

urn:nbn:de:tuda-tuprints-2116

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

Gegenstand der vorliegenden Arbeit ist die Beschreibung eines effizienten Algorithmus zum Auffinden einer elliptischen Kurve über einem endlichen Primkörper $\F_p,$ deren Punktegruppe über $\F_p$ kryptographisch geeignet ist. Der Algorithmus basiert auf der Theorie der Komplexen Multiplikation. Für kryptographische Zwecke sind nur elliptische Kurven relevant, deren Endomorphismenring eine imaginärquadratische Ordnung ist. Wir schreiben $\OD$ für eine solche Ordnung. Die Theorie der Komplexen Multiplikation erlaubt es zu entscheiden, ob zu vorgegebener Primzahlpotenz $q,$ positiver, ganzer Zahl $N$ und Endomorphismenring $\OD$ eine elliptische Kurve über $\F_q$ existiert, deren Punktegruppe über $\F_q$ die Ordnung $N$ hat und deren Endomorphismenring gleich $\OD$ ist. Im Falle der Existenz liefert die Theorie der Komplexen Multiplikation ferner ein Verfahren, um zu gegebenen $q,$ $N$ und $\OD$ eine solche Kurve zu bestimmen. Erste Arbeiten zur Erzeugung kryptographisch geeigneter, elliptischer Kurven mittels der Theorie der Komplexen Multiplikation stammen von A.-M.~Spallek und Lay/Zimmer. Diese Arbeiten beschreiben jedoch keinen geschlossenen Algorithmus, der bei Eingabe von gewünschten Sicherheitsparametern eine entsprechende Kurve auffindet. Ferner lassen die Arbeiten eine Vielzahl von Fragen ungeklärt, denen wir uns in dieser Arbeit widmen. Zunächst wird in keiner der Arbeiten beschrieben, wie man effizient einen endlichen Körper $\F_p$ und eine Ordnung einer kryptographisch geeigneten Punktegruppe über $\F_p$ bestimmt. Abhängig davon, ob $p$ vorgegeben ist oder nicht, entwickeln wir jeweils effiziente Algorithmen für diese Aufgabe. Unser Algorithmus berücksichtigt ferner die Klassenzahl der zu dem Endomorphismenring gehörenden maximalen Ordnung. Um nämlich Kurven zu generieren, die den Kriterien des deutschen Signaturgesetzes genügen, muss diese Klassenzahl z.Zt.\ größer oder gleich 200 sein. Darüberhinaus entwickeln wir ein effizientes Verfahren zur Berechnung von Klassenpolynomen. Die Berechnung solcher Klassenpolynome stellt einen wichtigen Teilalgorithmus dar, da der Grad des zu berechnenden Klassenpolynoms mitentscheidend für die Gesamtlaufzeit ist. Bisher galten lediglich Polynome vom Grad maximal 50 als verwendbar für Erzeugungsverfahren basierend auf der Theorie der Komplexen Multiplikation. Wir zeigen, dass wir sogar Klassenpolynome vom Grad 3000 in vertretbarer Zeit berechnen können, also mit einer Laufzeit von weniger als 10 Minuten auf einem handelsüblichen PC. Ferner untersuchen wir die zur Berechnung eines Klassenpolynoms hinreichende Präzision und geben entsprechende Formeln an. Eine solche praktische Untersuchung ist bisher nicht bekannt. Im Fall eines Klassenpolynoms, das von Yui/Zagier vorgeschlagen wurde, entwickeln wir eine neue Formel, die in der Praxis eine Laufzeitverbesserung von bis zu 45 % gegenüber bisherigen Vorschlägen ergibt. Schließlich erweitern wir unseren Algorithmus zur Bestimmung von elliptischen Kurven über Optimalen Erweiterungskörpern, deren Punktegruppe von Primzahlordnung ist. Außerdem entwickeln wir einen Algorithmus, der eine elliptische Kurve über $\F_p$ ausgibt, so dass die Punktegruppen der Kurve und eines Twists über $\F_p$ zyklisch von Primzahlordnung sind. Alle in dieser Arbeit entwickelten Algorithmen sind in C++ programmiert und in dem LiDIA-Modul gec verfügbar.

Deutsch

Freie Schlagworte:

elliptic curve, complex multiplication, cryptology, efficient algorithms, class field, modular function, Fourier series, class group, digital signature, German Digital Signature Act

Sachgruppe der Dewey Dezimalklassifikatin (DDC):

000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik

Fachbereich(e)/-gebiet(e):

20 Fachbereich Informatik

Hinterlegungsdatum:

17 Okt 2008 09:21

Letzte Änderung:

20 Mai 2018 21:23

PPN:

Referenten:

Buchmann, Prof. Dr. Johannes ; Köhler, Prof. Dr. Günter

Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: