Titelaufnahme

Titel
Die Performanz unterschiedlicher Varianten der Pollard-Rho-Methode zur Berechnung des Diskreten Logarithmus
Weitere Titel
On the performance of variants of Pollard´s Rho methods calculating the discrete logarithm
VerfasserKramer, Ines
GutachterHaböck, Ulrich
Erschienen2016
Datum der AbgabeJanuar 2016
SpracheDeutsch
DokumenttypBachelorarbeit
Schlagwörter (DE)diskretes Logarithmus Problem / Performanz / Pollard-Rho-Methode / Adding-Walks / Floyds-Cycle-Detection / Brents-Cycle-Detection / Geburtstagsparadoxon
Schlagwörter (EN)discrete logarithm problem / performance / Pollard Rho Method / Adding Walks / Floyds Cycle Detection / Brents Cycle Detection / birthday paradox
Zugriffsbeschränkung
 _
Klassifikation
Zusammenfassung (Deutsch)

Die Pollard-Rho-Methode ist ein zufallsbasierter Algorithmus zur Bestimmung des diskreten Logarithmus, ein mathematisches Problem, dessen Schwierigkeit von verschiedenen kryptographischen Verfahren ausgenutzt wird. Inhalt dieser Arbeit ist eine Analyse der Performanz der Pollard-Rho-Methode beschränkt auf Primzahlkörper.

Die Laufzeit des Algorithmus ist abhängig von der statistischen Qualität der pseudozufälligen Sequenzen und dem gewählten Cycle-Detection-Algorithmus. In dieser Arbeit werden die Pseudo-Zufalls-Sequenzen der originalen Pollard-Rho-Methode mit E.Teskes Adding-Walks in Kombination mit den bekannten Cycle-Detection-Algorithmen von Floyd und Brent verglichen. Zur empirischen Analyse der Laufzeit wurden vier unterschiedliche Varianten implementiert, die Messungen wurden mit dafür zufällig generierten Parametern bis zu 70 Bit durchgeführt. Der Unterschied zu früheren Arbeiten von E.Teske, S. Bai und R. Brent besteht darin, dass die aktuellen Messungen einen größeren Bereich an Instanzen abdecken, wenn auch mit dem Abstrich geringerer Stichprobengröße.

Bei der performantesten Implementierung steigt die Laufzeit in Prozessorticks exponentiell mit 2 ^ (0,4897·xA−1,5214) zur Bitlänge (xA) der Safe-Prime.

Zusammenfassung (Englisch)

Pollard´s rho method is a randomized algorithm to determine the discrete logarithm. Various cryptographical techniques are based on the difficulty of solving this mathematical problem. The content of this paper is limited to the performance analysis of the algorithm in arbitrary prime fields. The runtime is dependent on the statistical qualitiy of the pseudo-random sequence and the cycle finding algorithm. We compare pseudo-random sequences of the original Pollard-Rho-walk and E. Teskes Adding-walk combined with Floyd´s and Brent´s cycle finding algorithm. The performance analysis is based on four different algorithms coded in C and randomly generated parameters up to a length of 70 bit for testing. In addition to former work by E. Teske, S. Bai and R. Brent we focused on the bit length for testing with a trade-off in the sample size.

The runtime in ticks of the most efficient implementation is growing exponentially with 2 ^ (0,4897·xA−1,5214) corresponding to the bitlength (xA) of the safe prime.