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.

Frage zum Eintrag

Redaktionelle Details anzeigen