Darstellung und Effizienzuntersuchung der Algorithmen zur Lösung des diskreten Logarithmus Problems

  Matthias Dohn Studienarbeit August  2002

Inhaltsverzeichnis

1.  Aufgabenstellung Seite  3

2.  Rho-Methode  

  a. Darstellung des Algorithmus Seite  4

  b. Implementierung Seite  5

  c. Beispielrechnung Seite  8

  d. Zeitmessungen Seite  9

3.  Baby -Step-Giant Step  

  a. Darstellung des Algorithmus Seite  11

  b. Implementierung Seite  12

  c. Beispielrechnung Seite  14

  d. Zeitmessungen Seite  15

4.  Kangaroo-Methode  

  a. Darstellung des Algorithmus Seite  17

  b. Implementierung Seite  18

  c. Beispielrechnung Seite  22

  d. Zeitmessungen Seite  23

5.  Programmbeschreibung  

  a. Anforderungen Seite  25

  b. Bedienung Seite  25

6.  Quellenverzeichnis  

  a. Bibliography Seite  27

  b. Webliography Seite  27

- 2 -

1. Aufgabenstellung

Aufgabenstellung:

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.

Einführung:

Das diskrete Logarithmus Problem ist ein oft diskutiertes mathematische Problem welches in der Kryptographie am bedeutendsten ist. Die Schwierigkeit das Lösen der Formel a ^x 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 k angaroos“.

- 3 -

2. Rho-Methode

a) Darstellung:

Die Rho-Methode zur Berechnung des Diskreten Logarithmus wurde 1978 von J.M.Pollard e ntdeckt 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.

xx = Nach ca q Operationen tritt die Bedingung i2i ein. Und man eine Tabelle

generiert aus dessen Daten sich der Diskrete Logarithmus nach folgenden Formel berechnen lässt.

αβ=αβ gg bbaa ⁻⁻ β=α Aufgrund von und ⁱ²ⁱ²ⁱⁱ kann man nun berechnen: ^{abab ii2i2i} rbbmodq =−

i2i

r ^-1 ( a 2i - a i ) mod q = log a ß

- 4 -

b) Implementierung/Quelltext

public BigInteger rhoDiscLog(BigInteger alpha, BigInteger prime, BigInteger beta,BigInteger order) {

final BigInteger ZWEIBIG = new BigInteger("2"); final BigInteger DREIBIG = new BigInteger("3");

LinkedList xSet = new LinkedList();

LinkedList aSet = new LinkedList(); LinkedList bSet = new LinkedList();

long t1 = System.currentTimeMillis();

//initialize the sets

xSet.add(BigInteger.ONE); aSet.add(BigInteger.ZERO); bSet.add(BigInteger.ZERO);

//System.out.println("liste xSet " + xSet);

//System.out.println("liste aSet " + aSet); //System.out.println("liste bSet " + bSet);

int lauf=0;

System.out.println("Beginn der Tabellenerstellung " );

do { lauf++;

if ( lauf%100 == 0)

{

Date d2 = new Date(System.currentTimeMillis()); System.out.println("Lauf ist momentan : " + lauf + " " + d2.toString()); }

BigInteger xi = (BigInteger)xSet.get(lauf-1);

BigInteger xi_plus1 = new BigInteger("0");

BigInteger ai = (BigInteger)aSet.get(lauf-1);

BigInteger ai_plus1 = new BigInteger("0");

BigInteger bi = (BigInteger)bSet.get(lauf-1);

BigInteger bi_plus1 = new BigInteger("0");

- 5 -

//System.out.println("i = " +(lauf-1) + " ; xi = " + xSet.get(lauf-1) + " ; ai = //" + aSet.get(lauf-1) + // " ; bi = " + bSet.get(lauf-1));

if ( xi.mod(DREIBIG).equals(BigInteger.ONE))

{

xi_plus1 = beta.multiply(xi); xSet.add(xi_plus1.mod(prime));

aSet.add(ai);

bi_plus1 = bi.add(BigInteger.ONE);

bSet.add(bi_plus1.mod(order)); }

else if (xi.mod(DREIBIG).equals(BigInteger.ZERO)) { xi_plus1 = xi.pow(2); xSet.add(xi_plus1.mod(prime));

ai_plus1 = ai.multiply(ZWEIBIG);

aSet.add(ai_plus1.mod(order));

bi_plus1 = bi.multiply(ZWEIBIG);

bSet.add(bi_plus1.mod(order)); }

else if ( xi.mod(DREIBIG).equals(ZWEIBIG)) {

xi_plus1 = alpha.multiply(xi); xSet.add(xi_plus1.mod(prime));

ai_plus1 = ai.add(BigInteger.ONE);

aSet.add(ai_plus1.mod(order));

bSet.add(bi);

}

//abbruchbedingung überprüfen

if (lauf%2 ==0) {

if (xSet.get(lauf).equals(xSet.get(lauf/2))) break; } } while (true);

- 6 -

BigInteger r = ((BigInteger)bSet.get(lauf/2)).subtract( (BigInteger)bSet.get(lauf) ); r = r.mod(order); System.out.println("r = " +r); System.out.println("order: "+ order); r = r.modInverse(order); //System.out.println("r = " +r);

BigInteger temp = ((BigInteger)aSet.get(lauf)).subtract(

(BigInteger)aSet.get(lauf/2) ); r = r.multiply(temp); r = r.mod(order);

return r;

}

- 7 -