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
- a) Darstellung
- b) Implementierung/Quelltext
- c) Beispielrechnung
- d) Zeitmessungen
- 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
- 6. Quellenverzeichnis
- a) Bibliography
- b) Webliography
Zielsetzung und Themenschwerpunkte
Ziel dieser Studienarbeit ist die Implementierung und Effizienzuntersuchung der Algorithmen von J.M. Pollard zur Lösung des Diskreten Logarithmus Problems. Diese Arbeit konzentriert sich auf die Algorithmen Rho-Methode, Baby-Step-Giant-Step und Kangaroo-Methode, die im Artikel "Kangaroos, Monopoly and Discrete Logrithms" im Journal of Cryptology vorgestellt wurden.
- Darstellung der Algorithmen von J.M. Pollard
- Implementierung der Algorithmen in Java
- Effizienzuntersuchung der Algorithmen anhand von Zeitmessungen
- Analyse der jeweiligen Vor- und Nachteile der Algorithmen
- Bedeutung des Diskreten Logarithmus Problems in der Kryptographie
Zusammenfassung der Kapitel
Das erste Kapitel führt in das Thema der Studienarbeit ein und definiert die Aufgabenstellung. Es werden das diskrete Logarithmus Problem, seine Bedeutung in der Kryptographie und die verschiedenen Lösungsansätze, insbesondere die von J.M. Pollard, erläutert.
Das zweite Kapitel beschäftigt sich mit der Rho-Methode. Es werden die Funktionsweise, die Implementierung in Java, ein Beispiel für die Berechnung des Diskreten Logarithmus und die Ergebnisse von Zeitmessungen präsentiert.
Das dritte Kapitel behandelt die Baby-Step-Giant-Step-Methode. Ähnlich wie bei der Rho-Methode wird die Funktionsweise, die Implementierung, ein Beispiel und die Ergebnisse der Zeitmessungen vorgestellt.
Das vierte Kapitel widmet sich der Kangaroo-Methode. Auch hier werden die Funktionsweise, die Implementierung, ein Beispiel und die Ergebnisse der Zeitmessungen erläutert.
Das fünfte Kapitel beschreibt die Anforderungen und die Bedienung des Programms, welches für die Implementierung und die Effizienzuntersuchung der Algorithmen verwendet wurde.
Das sechste Kapitel umfasst das Quellenverzeichnis, welches die bibliografischen und webbasierten Quellen für diese Arbeit auflistet.
Schlüsselwörter
Diskreter Logarithmus, Kryptographie, Public-Key-Verfahren, Rho-Methode, Baby-Step-Giant-Step, Kangaroo-Methode, Java-Implementierung, Effizienzuntersuchung, Zeitmessungen, Algorithmen, Pollard.
- Quote paper
- Matthias Dohn (Author), 2002, Darstellung und Effizienzuntersuchung der Algorithmen zur Lösung des diskreten Logarithmus Problems, Munich, GRIN Verlag, https://www.grin.com/document/11603
