TU Darmstadt / ULB / TUprints

Über die Sicherheit und Effizienz kryptographischer Verfahren mit Klassengruppen imaginär-quadratischer Zahlkörper

Hamdy, Safuat (2002)
Über die Sicherheit und Effizienz kryptographischer Verfahren mit Klassengruppen imaginär-quadratischer Zahlkörper.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
Diss-S.Hamdy.pdf
Copyright Information: In Copyright.

Download (973kB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Über die Sicherheit und Effizienz kryptographischer Verfahren mit Klassengruppen imaginär-quadratischer Zahlkörper
Language: German
Referees: Buchmann, Prof. Dr. Johannes ; Scheidler, Prof. Renate
Advisors: Buchmann, Prof. Dr. Johannes
Date: 25 March 2002
Place of Publication: Darmstadt
Date of oral examination: 20 March 2002
Abstract:

In dieser Arbeit beschreiben wir asymmetrische Kryptoverfahren, deren Sicherheit auf der Schwierigkeit des DL-, des DH- oder des Wurzelproblems in Klassengruppen imaginär-quadratischer Zahlkörper beruht; diese Kryptoverfahren werden im folgenden als IQ-Kryptoverfahren oder einfach nur IQ-Verfahren bezeichnet. Bislang sind über IQ-Kryptographie nur vereinzelte Arbeiten erschienen, in denen einzelne Aspekte der IQ-Kryptographie beschrieben werden. So wurden z.B. in [Buchmann/Williams, 1988] Klassengruppen für den Diffie-Hellman-Schlüsselaustausch vorgeschlagen und eine erste Analyse zur Schwierigkeit des DL-Problems in Klassengruppen imaginär-quadratischer Zahlkörper gegeben, und in [Hafner/McCurley, 1989], [Duellmann, 1991] und [Jacobson, 1999] wurden subexponentielle Methoden zur Berechnung diskreter Logarithmen in Klassengruppen vorgestellt. Die folgenden Fragestellungen waren aber noch offen geblieben: Es war unklar, welche Signaturverfahren für Klassengruppen verwendet werden sollen, denn die Ordung der Klassengruppe oder eines Teilers davon (außer Potenzen von 2) ist i.allg. nicht effizient berechenbar. Daher können Signaturen vom ElGamal-Typ (z.B. DSA) nicht ohne weiteres auf Klassengruppen übertragen werden, da für Signaturen diesen Typs die Gruppenordnung bekannt sein muß. Weiterhin existierte bisher keine Untersuchung darüber, wie eine Klassengruppe ausgewählt werden sollte, so daß die Berechnung diskreter Logarithmen oder Wurzeln darin selbst mit den besten bekannten Algorithmen hierzu nicht effizient möglich ist. Es existierten bisher auch keine Implementierungen von IQ-Kryptoverfahren, weder experimentelle Implementierungen, noch Implementierungen für den praktischen Gebrauch. Letztendlich existierten daher bisher auch keine Untersuchungen über die Effizienz von IQ-Kryptoverfahren. Mit dieser Arbeit soll diese Lücke geschlossen werden: Wir stellen eine Reihe von IQ-Kryptoverfahren zur Signatur, zur Verschlüsselung und zum Schlüsselaustausch vor, und wir beschreiben detailliert, wie diese Kryptoverfahren implementiert werden sollten. Wir gehen dabei in einer Weise vor, wie es sich bei diversen Standards für Public-Key-Kryptographie eingebürgert hat, z.B. ANSI X9.62, ANSI X9.63, IEEE P1363 oder SEC; wir haben uns für unsere Spezifikation konkret den Standard SEC als Vorbild genommen. Wir zeigen, daß die IQ-Kryptoverfahren sicher sind unter der Annahme, daß die Berechnung diskreter Logarithmen und Wurzeln in Klassengruppen nicht effizient möglich ist. Wir zeigen dazu, wie die Diskriminante ausgewählt werden soll, damit diese Annahme mit sehr hoher Wahrscheinlichkeit erfüllt ist, und wir zeigen darüberhinaus, wie eine Diskriminante gewählt werden soll, so daß etwa die Berechnung diskreter Logarithmen in der entsprechenden Klassengruppe so aufwendig ist wie andere bekannte Berechnungsprobleme mit bestimmten Parametern (z.B. Faktorisierung einer ganzen Zahl mit 1024 Bit). Schließlich untersuchen wir die Effizienz der IQ-Kryptoverfahren und der darunter liegenden Arithmetik für Klassengruppen zu Diskriminanten, die für mittelfristigen Gebrauch kryptographisch geeignet sind, und wir zeigen, daß IQ-Kryptoverfahren so effizient sind, daß sie mit "`traditionellen"' Kryptoverfahren wie RSA oder DSA konkurrieren. Wir weisen damit nach, daß IQ-Kryptoverfahren eine sinnvolle und taugliche Alternative in der Familie der asymmetrischen Kryptoverfahren sind.

Alternative Abstract:
Alternative AbstractLanguage

In this work we describe asymmetric crypto-systems, whose security is based on the intractability of the discrete logarithm problem, the Diffie-Hellman problem, or the root problem in class groups of imaginary quadratic number fields; in the sequel, we shall call these crypto-systems IQ-crypto-systems. Until today only a limited number of research papers have been published on IQ-cryptography. For instance, class groups have been proposed for the Diffie-Hellman key exchange in [Buchmann/Williams, 1988]; in the same article a first analysis on the intractability of the discrete logarithm problem in class groups of imaginary quadratic number fields was given. In [Hafner/McCurley, 1989], [Duellmann:1991], and [Jacobson:1999] algorithms with subexponential running time for computing discrete logarithms in class groups were presented. However, the following questions have been left open: it was unclear, which signature schemes can be used for class groups, because the order of a class group or a divisor thereof (except powers of 2) is not efficiently computable in general. Therefore, signature schemes of ElGamal-type (e.g. DSA) cannot directly be used with class groups, for these signature schemes require the knowledge of the group order. Moreover, there hasn't been any investigation on how to select a class group such that computing discrete logarithms in that class group is intractable. Likewise, there haven't been any implementations of IQ-crypto-systems, neither experimental, nor for practical application. Consequently, there haven't been investigations on the efficiency of IQ-crypto-systems This work closes the gap: We present several IQ-crypto-systems for signature, encryption, and key exchange. We give a detailed description on how to implement these crypto-systems. We have done this in a way that is customary for major crypto-standards such as ANSI X9.62, ANSI X9.63, IEEE P1363, or SEC; we have modelled our specification in a manner similar to SEC. We show that IQ-crypto-systems are secure under the assumption that computing discrete logarithms and roots in class groups is intractable. We show how to select the discriminant such that this assumption is true with very high probability. Moreover, we show how to select the size of the diskriminant, such that computing discrete logarithms in corresponding class groups requires about as much computational work as factoring integers of a certain size (e.g. factoring a 1024-bit integer). Finally, we have investigated the efficiency of IQ-crypto-systems and the underlying arithmetics, where the discriminants have been chosen such that they are suitable for cryptographic usage in the mid term. We show then that IQ-crypto-systems compete with "traditional" crypto-systems like RSA or DSA in terms of efficiency. Thus we show that IQ-crypto-systems are reasonable and suitable alternatives in the family of public-key crypto-systems.

English
URN: urn:nbn:de:tuda-tuprints-2031
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 17 Oct 2008 09:21
Last Modified: 21 Mar 2016 11:13
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/203
PPN:
Export:
Actions (login required)
View Item View Item