Covers and Logarithmic Signatures of Finite Groups in Cryptography

Dateibereich 28110

882,8 KB in einer Datei, zuletzt geändert am 19.08.2011

Dateiliste / Details

DateiDateien geändert amGröße
svaba_dissertation.pdf19.08.2011 15:40:07882,8 KB
Nachdem Diffie und Hellman [1] die Idee von getrennten Schlüsseln für Verschlüsselungsverfahren präsentierten, wurde die asymmetrische Kryptographie zunehmend weiter entwickelt. Viele Public Key Kryptosysteme wurden vorgeschlagen, aber nur wenige wurden letztlich nicht gebrochen. Die meisten von ihnen, die noch heute verwendet werden, basieren auf den bekannten Schwierigkeiten von bestimmten mathematischen Problemen in sehr großen endlichen zyklischen Gruppen. In den späten 1970ern begann S. Magliveras den Nutzen spezieller Faktorisierungen auf endlichen nicht-abelschen Gruppen, bekannt als logarithmische Signaturen, in der Kryptographie zu erforschen [2,3,4,5]. Später folgten weitere wegweisende Arbeiten von Magliveras, Stinson und Tran van Trung [6] die sowohl das Kryptosystem MST1, welches auf logarithmischen Signaturen basiert, als auch MST2, das auf einer anderen Art von Gruppen-Überdeckungen – den sogenannten [s,r]-Gittern – arbeitet, bekannt machten. Bisher sind allerdings noch keine praktische Realisierungen von MST1 oder MST2 bekannt. Kürzlich wurde ein neues Public Key Kryptosystem namens MST3 [7] entwickelt, das auf der Grundlage von logarithmischen Signaturen und zufälligen Überdeckungen von endlichen nicht-abelschen Gruppen arbeitet. Für eine mögliche Realisierung der generischen Version dieses Systems wurden die Suzuki-2-Gruppen vorgeschlagen.

Das Hauptziel dieser Arbeit liegt darin zu zeigen, dass MST3 auf Suzuki-2-Gruppen realisiert werden kann. Diese Frage können wir im positiven Sinne beantworten. Es gab einige Änderungen in der Umsetzung der Realisierung des Systems. Das erste Problem besteht darin, effizient zufällige Überdeckungen für große Gruppen mit guten kryptographischen Eigenschaften zu erzeugen. In dem wir den Bezug zum klassischen Belegungsproblem (“the occupancy problem”) herstellen, können wir eine Schranke für die Wahrscheinlichkeit, dass eine zufällige Ansammlung von Gruppenelementen eine Überdeckung bilden, bestimmen. Eine Konsequenz daraus ist, dass wir das Problem, zufällige Überdeckungen für beliebige große Gruppen zu erzeugen, lösen können. Weiterhin stellen wir einige Resultate spezieller Computerexperimente bezüglich Überdeckungen und gleichmäßigen Überdeckungen zu verschiedenen Gruppen vor. Dank ihrer einfachen Struktur erlauben uns die Suzuki-2-Gruppen die Sicherheit des Systems genau zu studieren und es effizient zu implementieren. In der ersten Realisierung wird eine spezielle Klasse von kanonisch logarithmischen Signaturen zu elementar-abelschen 2-Gruppen als Basis für die Schlüsselgenerierung verwendet. Diese sind leicht zu konstruieren und erlauben eine sehr effiziente Faktorisierung. Wir betrachten einen Angriff, der zeigt, dass kanonische Signaturen nicht benutzt werden können um eine sichere Umsetzung von MST3 mit Suzuki-2-Gruppen zu realisieren. Motiviert durch die Attacke auf die erste Realisierung konnten wir eine neue Variante mit signifikanten Verbesserungen vorstellen, welche die Sicherheit des Systems deutlich stärken. Zu diesem Zweck verwendeten wir für das Setup des Systems eine Funktion zur Maskierung des privaten Schlüssels. Ferner führten wir eine Klasse von fusionierten transversalen logarithmischen Signaturen für die Realisierung des Verfahrens ein. Diese erlauben eine effiziente Faktorisierung mit Hilfe einer “Trapdoor” Information. Wir stellen eine genaue Studie der Sicherheit des Systems vor, in dem wir heuristische und algebraische Methoden verwenden. Zunächst bestimmen wir die untere Schranke der Komplexität bezüglich der Gruppengröße von möglich vorstellbaren direkten Attacken, um den privaten Schlüssel zu erhalten. Diese Schranken geben einen Hinweis auf die Stärke des Systems. Weiterhin entwickeln wir eine mächtige Methode für eine Chosen-Plaintext-Attacke, und zeigen, dass nicht-fusionierte transversale logarithmische Signaturen nicht verwendet werden können. Zudem zeigen wir, dass die vorgeschlagene Klassen von fusionierten transversalen Signaturen dieser Attacke widerstehen, und nach unserem Wissen, sie damit eine sichere Realisierung des Systems ermöglichen. Wir beschreiben und diskutieren die Implementierung des Systems im Detail und ziehen dabei Daten über die Effizienz, die wir als Resultate von einem Experiment erhielten, mit ein.

Abgesehen von dem zentralen Forschungsobjekt werden wir noch einen neuen Ansatz für die Konstruktion pseudo-zufälliger Zahlengeneratoren (PRNG) vorstellen, welcher auf zufälligen Überdeckungen von endlichen Gruppen basiert. PRNGs basierend auf zufälligen Überdeckungen, auch MSTg genannt, zeigten sich bisher zu einer bestimmten Klasse von Gruppen als höchst effizient und produzierten qualitativ hochwertige zufällige Bit-Sequenzen. Eine sehr komplexe Folge von aufwendigen Zufälligkeits-Tests zeigte durch Nutzung der NIST Statistical Test Suite und Diehard Battery of Test die starken Eigenschaften der neuen Methodik. Noch wichtiger ist allerdings, dass wir Beweise erbringen können, dass diese Klasse von Generatoren adäquat für kryptographische Anwendungen sind. Schließlich fügen wir noch Daten über die Effizienz der Generatoren an und schlagen eine Methode zur praktischen Anwendung vor.

[1] W. Diffie and M. E. Hellman, New Directions in Cryptography, IEEE Trans. on Inform. Theory, IT-22(6) (1976), 644–654.
[2] S. S. Magliveras, B. A. Oberg and A. J. Surkan, A New Random Number Generator from Permutation Groups, In Rend. del Sem. Matemat. e Fis. di Milano, LIV (1984), 203–223.
[3] S. S. Magliveras, A cryptosystem from logarithmic signatures of finite groups, in Proceedings of the 29’th Midwest Symposium on Circuits and Systems, Elsevier Publ. Co. (1986), 972–975.
[4] S. S. Magliveras and N.D. Memon, Properties of Cryptosystem PGM, Advances in Cryptology, Lecture Notes in Comp. Sc., Springer-Verlag, 435 (1989), 447–460.
[5] S. S. Magliveras and N.D. Memon, Random Permutations from Logarithmic Signatures, Computing in the 90’s, First Great Lakes Comp. Sc. Conf., Lecture Notes in Computer Science, Springer-Verlag, 507 (1989), 91–97.
[6] S. S. Magliveras, Tran van Trung and D.R. Stinson, New approaches to designing public key cryptosystems using one-way functions and trap-doors in finite groups, J. of Cryptology, 15 (2002), 285–297.
[7] W. Lempken, S. S. Magliveras, Tran van Trung and W. Wei, A public key cryptosystem based on non-abelian finite groups, J. of Cryptology, 22 (2009), 62–74.
Lesezeichen:
Permalink | Teilen/Speichern
Dokumententyp:
Wissenschaftliche Abschlussarbeiten » Dissertation
Fakultät / Institut:
Fakultät für Ingenieurwissenschaften » Informatik und Angewandte Kognitionswissenschaft
Dewey Dezimal-Klassifikation:
000 Informatik, Informationswissenschaft, allgemeine Werke » 000 Informatik, Wissen, Systeme » 004 Datenverarbeitung; Informatik
Stichwörter:
logarithmic signature, random cover, finite group, mst3, cryptosystem, pseudorandom number generator
Beitragende:
Prof. Dr. van Tran, Trung [Betreuer(in), Doktorvater]
Prof. Dr. ir. Vinck, Han [Gutachter(in), Rezensent(in)]
Sprache:
Englisch
Kollektion / Status:
Dissertationen / Dokument veröffentlicht
Datum der Promotion:
22.06.2011
Dokument erstellt am:
22.08.2011
Promotionsantrag am:
09.03.2011
Dateien geändert am:
22.08.2011
Medientyp:
Text