On Group Based Public Key Cryptography

Abstract

This thesis considers the analysis of two public key cryptosystems that rely on the difficulty of computational problems in finite groups.

In the first case we study certain factorizations of finite groups, called logarithmic signatures. These form the basis for the cryptosystems MST_1 and MST_3 which were developed by Lempken, Magliveras, Stinson, van Trung und Wei. In two distinct families of groups we study the questions which logarithmic signatures exist and if there are logaritmic signatures among theses that could be candidates for secure MST-systems. In the first family of groups we develop a uniform characterization for all logarithmic signatures which we use to show that a secure system is impossible. In the second family of groups we develop several methods to generate and study new logarithmic signatures. Here we are able to show that none of the currently known logarithmic signatures lead to a secure MST-system.

In the second case we consider the MOR-system (Paeng et al.) in an extension of the general linear group over a finite field. The security of this system relies on the difficulty of the discrete logarithm problem in inner automorphisms groups. We develop two ciphertext-only attacks that allow to reduce the security of the system to the discrete logarithm problem in finite fields.

Diese Arbeit befasst sich mit der Analyse zweier Public Key Kryptosysteme, deren Sicherheit auf Berechnungsproblemen in endlichen Gruppen beruht.

Im ersten Fall werden logarithmische Signaturen untersucht, welches spezielle Faktorisierungen endlicher Gruppen sind. Diese bilden die Basis für die von Lempken, Magliveras, Stinson, van Trung und Wei entwickelten Kryptosysteme MST_1 und MST_3. Neben der Entwicklung einer rigiden Sicherheitsdefinition wurde in zwei verschiedenen Gruppenfamilien untersucht, welche logarithmischen Signaturen existieren und ob darunter logarithmische Signaturen sind, die Kandidaten für sichere MST-Systeme sein könnten. In der ersten Gruppenfamilie wurde eine einheitliche Charakterisierung sämtlicher logarithmischen Signaturen entwickelt mittels der gezeigt werden konnte, dass hier kein sicheres System möglich ist. In der zweiten Gruppenfamilie wurden verschiedene neue Methoden entwickelt um logarithmische Signaturen zu erzeugen und zu untersuchen. Auch hier konnte gezeigt werden, dass mit keiner der aktuell bekannten logarithmischen Signaturen ein sicheres MST-Kryptosystem aufgebaut werden kann.

Im zweiten Fall wird das MOR-System (von Paeng et al.) in einer Erweiterung der Gruppe GL(n,q) untersucht. Die Sicherheit von MOR basiert auf der Schwierigkeit des diskreten Logarithmus Problems in Gruppen von inneren Automorphismen. Es werden zwei Ciphertext-only Angriffe entwickelt, die es ermöglichen die Sicherheit des Systems auf das Diskrete Logarithmus Problem in endlichen Körpern zu reduzieren.