Über die Sicherheit und Effizienz kryptographischer Verfahren in algebraischen Zahlkörpern

Meyer, Andreas (2006)
Über die Sicherheit und Effizienz kryptographischer Verfahren in algebraischen Zahlkörpern.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

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

Kurzbeschreibung (Abstract)

In dieser Arbeit leisten wir einen Beitrag zur Suche nach alternativen sicheren und effizienten Kryptoverfahren. Wir befassen uns mit dem Entwurf, der Sicherheit und der praktischen Effizienz von Public Key-Kryptoverfahren, deren Sicherheit auf der Schwierigkeit des diskreten Logarithmusproblems, des Diffie-Hellman-Problems oder des Wurzelproblems in Klassengruppen algebraischer Zahlkörper (number fields) vom Grad größer 2 basiert. (Solche Kryptoverfahren nennen wir NF-Kryptoverfahren.) Die Verwendung von algebraischen Zahlkörpern in der Kryptographie (NF-Kryptographie) wurde zwar in [Buchmann:1991] und [Buchmann/Paulus:1997] vorgeschlagen, jedoch blieben die Details offen. Bislang wurde in einer Reihe von Arbeiten lediglich die Verwendung des einfachsten Spezialfalls der quadratischen Zahlkörper analysiert. Die oben genannten mathematischen Basisprobleme, die zum Brechen der Kryptoverfahren gelöst werden müssen, sind für Zahlkörper vom Grad größer 2 noch schwieriger als für quadratische Zahlkörper. Zudem erscheint deren Lösung selbst dann schwierig, wenn die heute in der Praxis in Kryptoverfahren verwendeten Basisprobleme effizient gelöst würden, z.B. das Faktorisierungproblem ganzer Zahlen oder das diskrete Logarithmusproblem in endlichen Körpern oder der Punktegruppe einer elliptischen Kurve über endlichen Körpern. Das macht Zahlkörper höheren Grades für die Kryptographie besonders interessant. Die vorliegende Arbeit löst die zahlreichen Problemstellungen, die bzgl. NF-Kryptographie noch offen waren: Wir zeigen, dass man überhaupt kryptographische Protokolle über Klassengruppen algebraischer Zahlkörper entwerfen kann, obwohl hier die Gruppenordnung unbekannt und nicht effizient berechenbar ist. Hierzu stellen wir einige NF-Kryptoverfahren zur Signatur, zur Verschlüsselung, zum Schlüsselaustausch, zur Identifikation und für weitere Anwendungen vor. Wir zeigen, dass die NF-Kryptoverfahren sicher sind unter der Annahme, dass die Berechnung diskreter Logarithmen und Wurzeln in Klassengruppen nicht effizient möglich ist. Wir erläutern, wie der algebraische Zahlkörper ausgewählt werden soll, damit diese Annahme nach heutigem Kenntnisstand mit sehr hoher Wahrscheinlichkeit erfüllt ist. Mittels theoretischer Resultate und praktischer Untersuchungen zeigen wir ferner, wie groß die Parameter (die Diskriminante und der Grad eines Zahlkörpers) ausgewählt werden müssen, damit das Brechen der NF-Kryptoverfahren nach heutigem Kenntnisstand genauso schwierig ist wie das Brechen heute in der Praxis verwendeter Kryptoverfahren wie RSA (mit z.B. 2048 Bit Schlüssellänge). Zudem untersuchen wir die Effizienz der NF-Kryptoverfahren und der darunter liegenden Arithmetik für Klassengruppen algebraischer Zahlkörper. Wir zeigen, dass NF-Kryptoverfahren schon hinreichend effizient sind, um auf modernen Computern eingesetzt werden zu können. In unserer Implementierung des R-Fiat-Shamir-Identifikationsprotokolls in der Klassengruppe kubischer Stender-Körper mit 404 Bit-Diskriminante benötigen beispielsweise Beweiser und Verifizierer auf einem 433 MHz PC jeweils 528 ms. Auf dem gleichen PC bräuchte der Beweiser bei vergleichbarer Sicherheit im RSA-Verfahren (4096 Bit Schlüssellänge) bei Verwendung einer anerkannt effizienten Referenzimplementierung 640 ms.

Typ des Eintrags:

Dissertation

Erschienen:

2006

Autor(en):

Meyer, Andreas

Art des Eintrags:

Erstveröffentlichung

Titel:

Über die Sicherheit und Effizienz kryptographischer Verfahren in algebraischen Zahlkörpern

Sprache:

Deutsch

Referenten:

Buchmann, Prof.Dr. Johannes ; Takagi, Prof. Dr. Tsuyoshi

Berater:

Buchmann, Prof.Dr. Johannes

Publikationsjahr:

12 Dezember 2006

Ort:

Darmstadt

Verlag:

Technische Universität

Datum der mündlichen Prüfung:

5 Januar 2006

URL / URN:

urn:nbn:de:tuda-tuprints-7584

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

In this thesis we focus on the search for alternative secure and efficient cryptosystems. We construct public key cryptosystems whose security is based on the intractability of the discrete logarithm problem, the Diffie-Hellman problem or the root problem in class groups of algebraic number fields of degree greater than 2. (In the following we will call these cryptosystems NF-cryptosystems). We analyse the security and the practical efficiency of our new cryptosystems. The use of algebraic number fields in cryptography (NF-cryptography) has been proposed in [Buchmann:1991] and [Buchmann/Paulus:1997], but the details have been left open. In a lot of articles published so far, only the use of the most simple special case of quadratic number fields has been analysed. The mathematical basis problems mentioned above that have to be solved to break the cryptosystems, are more difficult for number fields of degree greater than 2 than for quadratic number fields. In addition, solving these problems seems to be difficult even if the basis problems used in today's real-life cryptosystems were solved efficiently, e.g. the factoring problem of integers or the discrete logarithm problem in finite fields or the group of points of an elliptic curve over finite fields. This makes number fields of higher degree even more attractive for the use in cryptography. This thesis answers the questions which have remained open so far regarding NF-cryptography: We show that it is possible at all to design cryptographic protocols over class groups of algebraic number fields, although the group order is unknown in our case and cannot be determined efficiently. To do so, we present some cryptosystems for digital signature, encryption, key exchange, identification and for further applications. We show that the NF-cryptosystems are secure assuming the computation of discrete logarithms and roots in class groups is infeasible. We explain how to select the algebraic number field such that that assumption is true with very high probability up to today's knowledge. Furthermore, we show by theoretic and experimental results how big the parameters (i.e. the discriminant and the degree of the number field) must be selected such that, up to today's knowledge, breaking the NF-cryptosystems is as hard as breaking the cryptosystems used today in practice like RSA (e.g. with key length of 2048 bit). Moreover, we analyse the practical efficiency of the NF-cryptosystems and the underlying arithmetic for class groups of algebraic number fields. We show that NF-cryptosystems already are sufficiently efficient to be used on modern computers. For example, using our implementation of the R-Fiat-Shamir identification protocol in the class group of cubic Stender fields with 404 bit discriminant, the prover and the verifier need 528 milliseconds on a 433 MHz PC respectively. On the same PC the prover needs 640 milliseconds using an efficient reference implementation of the RSA cryptosystem at a comparable security level of 4096 bit RSA keys.

Englisch

Sachgruppe der Dewey Dezimalklassifikatin (DDC):

000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik

Fachbereich(e)/-gebiet(e):

20 Fachbereich Informatik

Hinterlegungsdatum:

17 Okt 2008 09:22

Letzte Änderung:

26 Aug 2018 21:25

PPN:

Referenten:

Buchmann, Prof.Dr. Johannes ; Takagi, Prof. Dr. Tsuyoshi