TU Darmstadt / ULB / TUbiblio

Zur Berechnung von Klassengruppen

Neis, Stefan (2002)
Zur Berechnung von Klassengruppen.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

Die Public-Key-Kryptographie ist eine Ansammlung von Verfahren, die zwar einerseits traditionell immer in Restklassenringen Z/mZ spielen, die aber leicht auf andere Gruppen übertragen werden können. Z.B. der Diffie-Hellman-Schlüsselaustausch (1976), die El-Gamal-Signatur (1985, seit 1994 auch als "Digital Signature Algorithm", DSA bekannt), die RSA-Verschlüsselung und -Signatur (1977) und das Signaturverfahren von Guillou-Quisquater (1989) beziehen ihre Sicherheit letztlich entweder daraus, dass es schwierig ist, die Gruppenordnung zu finden oder daraus, dass der sog. diskrete Logarithmus in der zu Grunde liegenden Gruppe schwer zu berechnen ist. Prinzipiell ist aber jede Gruppe für kryptographische Zwecke geeignet, in der zumindest eines der beiden Probleme schwierig zu lösen ist, wie das Beispiel der elliptischen Kurven zeigt. In diesem Sinne sind z.B. auch Klassengruppen algebraische Zahlkörper kryptographisch interessant - tatsächlich beschäftigt die Frage, wie man effizient die Gruppenordnung einer Klassengruppe bzw. einen diskreten Logarithmus in einer Klassengruppe bestimmen kann, die Mathematik schon seit langem, ohne dass dabei eine zufriedenstellende Antwort zutage gefördert wurde. Daher kann man Klassengruppen prinzipiell mit dem gleichen Vertrauen für kryptographische Zwecke einsetzen wie die zur Zeit populären Gruppen. Unklar ist allerdings, wie die "Schlüssellänge" gewählt werden muss, um eine Sicherheit zu bieten, die mit den wohlbekannten Verfahren vergleichbar ist. Diese Lücke versucht diese Arbeit zumindest teilweise zu schließen, indem sie zum einen die auch bisher schon zu beobachtende Ähnlichkeit in der Verfahrensweise zwischen Faktorisierung und Klassengruppenberechnung ausnutzt und das asymptotisch effizienteste bekannte Faktorisierungsverfahren auf den Fall der Klassengruppenberechnung übertragt und zum anderen das neue Verfahren implementiert und die praktische Reichweite der Implementierung im Bereich von Zahlkörpern der Grade 3 bis 6 detailliert untersucht, wobei sich zeigt, dass die Gruppenordnung für Zahlkörper mit Diskriminanten von bis zu etwa 50 Dezimalstellen innerhalb kurzer Zeit berechnet werden kann. Die Arbeit selbst beschäftigt sich nach einer knappen Darstellung der mathematischen Grundlagen im wesentlichen mit den beiden Teilproblemen der Idealarithmetik und der Relationengenerierung. Für die Idealarithmetik, die sich in den letzten Jahrzehnten zu einem unübersichtlichen Sammelsurium von Ad-hoc-Methoden entwickelt hat, geben wir eine neue theoretische Modellierung, die die Idealarithmetik auf Probleme der linearen Algebra über Z/mZ reduziert, wobei wir auch erstmals zeigen, wie diese Probleme im Falle von zusammengesetzten Zahlen m gelöst werden können. Daneben zeigen wir auch unsere objekt-orientierte praktische Implementierung. Danach wenden wir uns der Relationengenerierung zu, die bisher im wesentlichen vergleichbar mit der Probedivision bei der Faktorisierung ablief und übertragen das Siebverfahren des "Number Field Sieve" auf unsere Situation. Wir illustrieren anhand praktischer Beispiele, dass man mit diesem Verfahren sehr viele Relationen in kurzer Zeit finden kann und nehmen einige Optimierungen des Verfahrens vor. Schließlich geben wir ausführliche Laufzeit-Tabellen für zufällige algebraische Zahlkörper unterschiedlicher Signaturen, die die Effizienz des Verfahrens und seiner Implementierung illustrieren.

Typ des Eintrags: Dissertation
Erschienen: 2002
Autor(en): Neis, Stefan
Art des Eintrags: Erstveröffentlichung
Titel: Zur Berechnung von Klassengruppen
Sprache: Deutsch
Referenten: Buchmann, Prof. Dr. Johannes ; Pethoe, Prof. Dr. Atilla
Berater: Buchmann, Prof. Dr. Johannes
Publikationsjahr: 18 Dezember 2002
Ort: Darmstadt
Verlag: Technische Universität
Datum der mündlichen Prüfung: 28 Mai 2002
URL / URN: urn:nbn:de:tuda-tuprints-2835
Kurzbeschreibung (Abstract):

Die Public-Key-Kryptographie ist eine Ansammlung von Verfahren, die zwar einerseits traditionell immer in Restklassenringen Z/mZ spielen, die aber leicht auf andere Gruppen übertragen werden können. Z.B. der Diffie-Hellman-Schlüsselaustausch (1976), die El-Gamal-Signatur (1985, seit 1994 auch als "Digital Signature Algorithm", DSA bekannt), die RSA-Verschlüsselung und -Signatur (1977) und das Signaturverfahren von Guillou-Quisquater (1989) beziehen ihre Sicherheit letztlich entweder daraus, dass es schwierig ist, die Gruppenordnung zu finden oder daraus, dass der sog. diskrete Logarithmus in der zu Grunde liegenden Gruppe schwer zu berechnen ist. Prinzipiell ist aber jede Gruppe für kryptographische Zwecke geeignet, in der zumindest eines der beiden Probleme schwierig zu lösen ist, wie das Beispiel der elliptischen Kurven zeigt. In diesem Sinne sind z.B. auch Klassengruppen algebraische Zahlkörper kryptographisch interessant - tatsächlich beschäftigt die Frage, wie man effizient die Gruppenordnung einer Klassengruppe bzw. einen diskreten Logarithmus in einer Klassengruppe bestimmen kann, die Mathematik schon seit langem, ohne dass dabei eine zufriedenstellende Antwort zutage gefördert wurde. Daher kann man Klassengruppen prinzipiell mit dem gleichen Vertrauen für kryptographische Zwecke einsetzen wie die zur Zeit populären Gruppen. Unklar ist allerdings, wie die "Schlüssellänge" gewählt werden muss, um eine Sicherheit zu bieten, die mit den wohlbekannten Verfahren vergleichbar ist. Diese Lücke versucht diese Arbeit zumindest teilweise zu schließen, indem sie zum einen die auch bisher schon zu beobachtende Ähnlichkeit in der Verfahrensweise zwischen Faktorisierung und Klassengruppenberechnung ausnutzt und das asymptotisch effizienteste bekannte Faktorisierungsverfahren auf den Fall der Klassengruppenberechnung übertragt und zum anderen das neue Verfahren implementiert und die praktische Reichweite der Implementierung im Bereich von Zahlkörpern der Grade 3 bis 6 detailliert untersucht, wobei sich zeigt, dass die Gruppenordnung für Zahlkörper mit Diskriminanten von bis zu etwa 50 Dezimalstellen innerhalb kurzer Zeit berechnet werden kann. Die Arbeit selbst beschäftigt sich nach einer knappen Darstellung der mathematischen Grundlagen im wesentlichen mit den beiden Teilproblemen der Idealarithmetik und der Relationengenerierung. Für die Idealarithmetik, die sich in den letzten Jahrzehnten zu einem unübersichtlichen Sammelsurium von Ad-hoc-Methoden entwickelt hat, geben wir eine neue theoretische Modellierung, die die Idealarithmetik auf Probleme der linearen Algebra über Z/mZ reduziert, wobei wir auch erstmals zeigen, wie diese Probleme im Falle von zusammengesetzten Zahlen m gelöst werden können. Daneben zeigen wir auch unsere objekt-orientierte praktische Implementierung. Danach wenden wir uns der Relationengenerierung zu, die bisher im wesentlichen vergleichbar mit der Probedivision bei der Faktorisierung ablief und übertragen das Siebverfahren des "Number Field Sieve" auf unsere Situation. Wir illustrieren anhand praktischer Beispiele, dass man mit diesem Verfahren sehr viele Relationen in kurzer Zeit finden kann und nehmen einige Optimierungen des Verfahrens vor. Schließlich geben wir ausführliche Laufzeit-Tabellen für zufällige algebraische Zahlkörper unterschiedlicher Signaturen, die die Effizienz des Verfahrens und seiner Implementierung illustrieren.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

For historical reasons, public key cryptography is a collection of algorithms which are doing computations in residual rings Z/mZ. However, those algorithms are easy to apply to other groups. E.g. Diffie-Hellman key exchange (1976), El-Gamal signature (1985, famous as "Digital Signature Algorithm" (DSA) since 1994), RSA encryption and signature(1977) and the signature algorithm of Guillou-Quisquater (1989) all obtain their security from the fact that it is difficult either to compute the actual order of the group or to solve the discrete logarithm problem in the group. In principle, every group where at least one of those two problems is hard to solve is suited for cryptographic applications as has been demonstrated by the usage of elliptic curves. Similarly, the class groups of algebraic number fields are interesting for cryptographic purposes - in fact mathematicians have been searching for efficient algorithms to compute the class number or a discrete logarithm within a class group for many years without finding a satisfying solution. Therefore, class groups are just as trustworthy as the currently more popular groups. In practice, however, it is totally unclear what "key length" is needed to get as much security as we get for the well-known algorithms with a given key length. Closing that gap at least partially is the aim of our work. We achieve this in two steps: First, we make use of the noticeable similarity between existing algorithms for computing class groups and algorithms for factoring and apply the latest, most efficient factoring algorithm to the situation of class group computation. Second, we implement the resulting algorithm and investigate its limits for algebraic number fields of degrees 3 to 6. In doing this, we find that we can compute the class numbers of fields with discriminants of up to 50 digits within a short time. After giving a short overview over the theoretical background, this work essentially focuses on two problems, namely ideal arithmetic and generation of relations. For the ideal arithmetic which has grown to an unwieldy conglomeration of ad hoc methods over the past decades, we give a new theoretic model which reduces ideal arithmetic to problems of linear algebra over Z/mZ. For a first time, we give a detailed description how to solve those linear algebra problems even for composed numbers m. We also show our object-oriented, efficient implementation of those algorithms. Then we look at the generation of relations which up to now was essentially based on methods which can be compared to trial division in the case of factoring integers. We show how to apply ideas of the number field sieve to our situation and give examples proving that it now becomes easy to find lots of relations within a short time. Then we show several improvements and optimizations of this new method. Finally, we included a number of tables showing running times and results for random number fields of varying signature which prove the efficiency of the method and its implementation.

Englisch
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
Hinterlegungsdatum: 17 Okt 2008 09:21
Letzte Änderung: 14 Jan 2019 10:08
PPN:
Referenten: Buchmann, Prof. Dr. Johannes ; Pethoe, Prof. Dr. Atilla
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 28 Mai 2002
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen