Ausgehend von dem Artikel im Journal of Cryptology “Kangaroos, Monopoly and Discrete Logrithms“ sollen die Algorithmen von J.M. Pollard dargestellt, implementiert und hinsichtlich ihrer Effizienz untersucht werden.
Das diskrete Logarithmus Problem ist ein oft diskutiertes mathematische Problem welches in der Kryptographie am bedeutendsten ist. Die Schwierigkeit das Lösen der Formel ax mod p = ß wird zur Zeit bei Public-Key Verfahren angewandt.
Zahlreiche Mathematiker, unter anderem Edlyn Teske und Andreas Stein beschäftigen sich mit der Verbesserung von Methoden zur Lösung des DLP. Je nachdem welche Informationen bekannt sind kommen andere effiziente Algorithmen zur Anwendung.
J.M. Pollard hat in dem Artikel im Journal of Cryptology mehrere Methoden zur Lösung des Diskreten Logarithmus Problems vorgestellt. Die Rho-Methode wurde kurz erwähnt und wird im folgenden Kapitel vorgestellt. Im darauf folgenden Kapitel wird die Baby-Step-Giant-Step-Methode erläutert und anschliessend die „Lambda-Method for catching kangaroos“.
Inhaltsverzeichnis
1. Aufgabenstellung
2. Rho-Methode
a. Darstellung des Algorithmus
b. Implementierung
c. Beispielrechnung
d. Zeitmessungen
3. Baby-Step-Giant-Step
a. Darstellung des Algorithmus
b. Implementierung
c. Beispielrechnung
d. Zeitmessungen
4. Kangaroo-Methode
a. Darstellung des Algorithmus
b. Implementierung
c. Beispielrechnung
d. Zeitmessungen
5. Programmbeschreibung
a. Anforderungen
b. Bedienung
Zielsetzung & Themen
Die vorliegende Studienarbeit verfolgt das Ziel, drei ausgewählte Algorithmen von J.M. Pollard zur Lösung des „Diskreten Logarithmus Problems“ (DLP) theoretisch darzustellen, praktisch zu implementieren und hinsichtlich ihrer Effizienz zu analysieren.
- Darstellung und Analyse der Rho-Methode
- Untersuchung des Baby-Step-Giant-Step-Algorithmus
- Implementierung und Validierung der Kangaroo-Methode
- Effizienzvergleich der Verfahren durch Zeitmessungen
- Softwaretechnische Realisierung in Java unter Verwendung von BigInteger
Auszug aus dem Buch
a) Darstellung:
Die Rho-Methode zur Berechnung des Diskreten Logarithmus wurde 1978 von J.M.Pollard entdeckt und ist ein zufallsbasierter Algorithmus, nicht zu verwechseln mit dem gleichbenannten Rho-Algorithmus zur Primfaktorzerlegung.
Bei der Rho-Methode muss die Ordnung g der zyklischen Gruppe bekannt sein und der Algorithmus hat dann eine Laufzeit von Oq . q ist in dem Falle die Ordung. Die Ordnung muss zur Lösungsfindung prim sein.
Algorithmus: Die drei Mengen X ,A und B werden nach folgenden Bedingungen generiert.
Nach ca q Operationen tritt die Bedingung i 2i xx ein. Und man eine Tabelle generiert aus dessen Daten sich der Diskrete Logarithmus nach folgenden Formel berechnen lässt.
Aufgrund von i i 2i 2i a b ab gg und i 2i 2ii b b aa kann man nun berechnen:
r = b_i - b_2i mod q
r^-1 ( a_2i - a_i ) mod q = log_a(ß)
Zusammenfassung der Kapitel
1. Aufgabenstellung: Einführung in das diskrete Logarithmus Problem (DLP) und Definition des Untersuchungsrahmens für die Algorithmen von J.M. Pollard.
2. Rho-Methode: Theoretische Herleitung und praktische Umsetzung der Rho-Methode inklusive Beispielrechnungen und Zeitmessungen.
3. Baby-Step-Giant-Step: Erläuterung des Baby-Step-Giant-Step-Algorithmus mit detaillierter Implementierung, Beispielwerten und Leistungsdaten.
4. Kangaroo-Methode: Vorstellung der Lambda-Methode for Catching Kangaroos unter Berücksichtigung der Intervallvorgaben, deren Implementierung und Effizienzanalyse.
5. Programmbeschreibung: Dokumentation der Anforderungen und Bedienung der zugehörigen Java-Software-Implementierung basierend auf dem JBuilder5-Projekt.
Schlüsselwörter
Diskretes Logarithmus Problem, DLP, Kryptographie, J.M. Pollard, Rho-Methode, Baby-Step-Giant-Step, Kangaroo-Methode, BigInteger, Effizienzanalyse, Public-Key-Verfahren, Algorithmik, Java, Laufzeit, Zyklische Gruppe.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der mathematischen Darstellung und praktischen Implementierung spezieller Algorithmen zur Lösung des Diskreten Logarithmus Problems.
Welche zentralen Themenfelder werden behandelt?
Im Fokus stehen drei spezifische Verfahren von J.M. Pollard: die Rho-Methode, der Baby-Step-Giant-Step-Algorithmus und die Kangaroo-Methode.
Was ist das primäre Ziel der Untersuchung?
Das Hauptziel ist die Untersuchung der Effizienz dieser Algorithmen durch eine praktische Implementierung in Java und anschließende Zeitmessungen.
Welche wissenschaftliche Methode kommt zum Einsatz?
Es werden mathematische Algorithmen theoretisch hergeleitet, mittels Software (Java) implementiert und an Hand von Beispielrechnungen sowie Zeitmessungen empirisch geprüft.
Was beinhaltet der Hauptteil der Arbeit?
Der Hauptteil ist in drei große Kapitel gegliedert, welche jeweils Darstellung, Implementierung, Beispielrechnung und Zeitmessung für die drei behandelten Algorithmen enthalten.
Welche Schlüsselbegriffe charakterisieren die Arbeit?
Die Arbeit lässt sich primär über Begriffe wie Diskretes Logarithmus Problem, Kryptographie, Algorithmik und Effizienzanalyse definieren.
Wie wird die Kangaroo-Methode in Bezug auf Endlosschleifen gehandhabt?
Da Zufallszyklen zu Endlosschleifen führen können, wurde eine Variable `maxLauf` eingeführt, die die Anzahl der Operationen begrenzt und bei Überschreitung einen Neustart mit neuen Zufallszahlen erzwingt.
Warum ist die Wahl der Softwareumgebung für die Implementierung entscheidend?
Die Implementierung nutzt die `BigInteger`-Klasse von Java, da die Berechnungen bei wachsender Schlüssellänge die Kapazitäten normaler Datentypen schnell übersteigen.
- Citar trabajo
- Matthias Dohn (Autor), 2002, Darstellung und Effizienzuntersuchung der Algorithmen zur Lösung des diskreten Logarithmus Problems, Múnich, GRIN Verlag, https://www.grin.com/document/11603
