Titelaufnahme

Titel
Performanz unterschiedlicher Varianten der Pollard-Rho-Methode zur Lösung des diskreten Logarithmus auf elliptischen Kurven
Weitere Titel
On the Performance of different Versions of the Pollard Rho Method solving the Elliptic Curve Discrete Logarithm
VerfasserKramer, Ines
GutachterHaböck, Ulrich
Erschienen2016
Datum der AbgabeMai 2016
SpracheDeutsch
DokumenttypBachelorarbeit
Schlagwörter (DE)diskretes Logarithmus Problem / Performanz / Pollard-Rho-Methode / Adding-Walks / elliptische Kurven / Brents-Cycle-Detection
Schlagwörter (EN)discrete logarithm / elliptic curve / Pollard Rho Method / adding walks / performance / Brent cycle detection
Zugriffsbeschränkung
 _
Klassifikation
Zusammenfassung (Deutsch)

Verschlüsselungsverfahren basierend auf Elliptische Kurven (EC) sind für kryptographische Methoden wichtig, da sie im Verhältnis zu anderen Verfahren ein ähnliches Sicherheitslevel zu viel geringeren Bitlängen ermöglichen. Der diskrete Logarithmus auf elliptischen Kurven ist ein schwieriges mathematisches Problem, bei dem die Pollard-Rho-Methode als performanteste generische Angriffsmethode gilt. Diese Arbeit gibt eine kurze Einführung in EC-Grundlagen und vergleicht die Performanz unterschiedlicher Varianten der Pollard-Rho-Methode angepasst auf elliptische Kurven über Primzahlkörper.

Die Varianten unterscheiden sich in der Iterationsfunktion zur Erstellung der Pseudo-Zufallssequenzen und dem Cycle-Detection-Algorithmus zur Suche einer Kollision. In den Laufzeitmessungen wurden Implementierungen mit der originalen Pollard-Rho-Methode und Teske´s Adding-Walks und zwei unterschiedlichen Brent-Cycle-Detection Varianten mit zufällig dafür generierten Kurven und Instanzen bis zu 60 bit getestet.

Im Unterschied zur Performanzanalyse im Primzahlkörper ist auf elliptischen Kurven die Variante mit Teske´s Adding-Walks um das Doppelte effizienter. Die Verbesserung des Brent-Cycle-Detection Algorithmus brachte nur eine Beschleunigung von 5 %.

Zusammenfassung (Englisch)

The importance of elliptic curve cryptosystems (ECC) compared to other cryptographical approaches is based on a similar security level by providing at the same time a reduction in the bitlength of the group size. The Pollard Rho method is known as the most efficient attack against the discrete logarithm on elliptic curves, which is a hard problem in mathematics. This work gives a short introduction in the basics of ECC and analyses the performance of different implementations of the Pollard Rho method on elliptic curves over primefields.

The versions differ in the iteration function to create a pseudo-random sequence and the cycle detection algorithm to search for a collision. We tested the runtime of randomly generated curves up to 60 bits with the original Pollard Rho method and Teske´s adding walks and two different Brent cycle detection algorithms.

In the case of elliptic curve implementations Teske´s adding walks are twice as efficient in contrast to the performance analysis of the discrete logarithm in prime fields. The faster version of the cycle detection algorithm achieved an acceleration of just about 5%.