Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Hinweis zum Urheberrecht

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-16643
URL: http://geb.uni-giessen.de/geb/volltexte/2004/1664/


Design und Analyse kryptografischer Bausteine auf nicht-abelschen Gruppen

Design and analysis of Cryptographic Primitives using Non-Abelian Groups

Tobias, Christian


pdf-Format: Dokument 1.pdf (689 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Freie Schlagwörter (Deutsch): Kryptografie , MOR Kryptosystem , Kryptanalyse , Konjugationsproblem , spezielles Konjugationsproblem
Freie Schlagwörter (Englisch): cryptography , MOR cryptosystem , cryptanalysis , conjugacy problem , special conjugacy problem
Universität Justus-Liebig-Universität Gießen
Institut: Mathematisches Institut
Fachgebiet: Mathematik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Sprache: Deutsch
Tag der mündlichen Prüfung: 30.07.2004
Erstellungsjahr: 2004
Publikationsdatum: 17.08.2004
Kurzfassung auf Deutsch: Die Public-Key Kryptografie ermöglicht es Teilnehmern, kryptografische Protokolle auszuführen (z.B. vertrauliche Nachrichten zu versenden), ohne dass sie dazu vorher über ein gemeinsames Geheimnis verfügen müssen. Die heutzutage gebräuchlichen Public-Key Verfahren basieren auf endlichen abelschen Gruppen. In letzter Zeit werden erhebliche Anstrengungen unternommen, kryptografische Verfahren auf nicht-abelschen Gruppen zu konstruieren. Dabei wird die Schwierigkeit des Konjugationsproblems oder einer Variante als zugrundeliegende Sicherheitsannahme verwendet.

Im ersten Teil der Arbeit werden notwendige Definitionen und Konzepte eingeführt. Insbesondere wird die Schwierigkeit der Berechnung diskreter Logarithmen in der Gruppe Inn(G) der inneren Automorphismen einer nicht-abelschen Gruppe G untersucht und der Zusammenhang zum Problem der Berechnung diskreter Logarithmen und dem speziellen Konjugationsproblem in der zugrundeliegenden nicht-abelschen Gruppe G erörtert.

Der zweite Teil beschäftigt sich mit dem im Jahre 2001 vorgestellten MOR System. Dabei handelt es sich um ein asymmetrisches Verschlüsselungsverfahren auf nicht-abelschen Gruppen, dessen Sicherheit auf der Schwierigkeit der Berechnung diskreter Logarithmen in der Gruppe Inn(G) beruht. Das MOR System kann auf nicht-abelschen Gruppen durchgeführt werden, die bestimmte Anforderungen erfüllen. Der Schwerpunkt des zweiten Teils liegt in der Sicherheitsanalyse von MOR auf diesen Gruppen. Dabei werden verschiedene Betriebsmodi des MOR Systems untersucht. Es stellt sich heraus, dass alle effizienten Modi von MOR bei Benutzung der vorgeschlagenen Gruppen erhebliche Sicherheitslücken aufweisen.

Der dritte Teil der Arbeit beschäftigt sich strukturell mit der Kombination des Konjugationsproblems mit klassischen kryptografischen Problemen, wie dem Problem der Berechnung diskreter Logarithmen oder den Diffie-Hellman Problemen, zu neuen kryptografischen Probleme auf nicht-abelschen Gruppen. Es werden zunächst solche Kombinationen vorgestellt und ihre Abhängigkeiten untereinander untersucht. Anschließend werden verschiedene kryptografische Verfahren, die diese Probleme bereits nutzen, auf ihre Sicherheit untersucht. Es zeigt sich dabei, dass einige dieser Verfahren über ähnliche Designschwächen verfügen. Abschließend wird ein Konstruktionsprinzip zur Vermeidung dieses Designfehlers vorgestellt und dessen Umsetzung exemplarisch an einem Commitment Schema demonstriert.
Kurzfassung auf Englisch: Public-key cryptography enables parties to execute cryptographic protocols (e.g. to send confidential messages) without requiring a common secret. The methods in use today are mostly based on abelian groups. Recently, several cryptographic protocols using non-abelian groups were proposed. Their underlying security assumption is the hardness of the conjugacy problem (or some variant).

The first part of this thesis introduces necessary definitions and concepts. Especially the hardness of the discrete logarithm problem in the group Inn(G) of inner automorphisms of a non-abelian group G and its relation to the discrete logarithm problem and the special conjugacy problem in the underlying group G are discussed.

The second part analyses the MOR system. The MOR system is an asymmetric cryptosystem whose security is based on the hardness of the discrete logarithm problem in Inn(G). It can be used with non-abelian groups fulfilling certain requirements. At present two groups are known that can be used with the MOR system. The main emphasis of the second part is put on the security analysis of MOR using these groups. All efficient modes of the MOR system turn out to be insecure if these groups are used.

The third part investigates combinations of the conjugacy problem and classical cryptographic problems, as the discrete logarithm problem or the Diffie-Hellman problems, to obtain new cryptographic problems on non-abelian groups. Such combinations are presented and their dependencies are discussed. Existing cryptographic protocols that use these combinations are introduced and analysed. Some of these protocols have common design weaknesses. These weaknesses are pointed out and design principles are given to avoid them. In a concluding section a provably secure commitment scheme is defined to demonstrate how to apply these design principles.