Kryptographie - Algebraischer Hintergrund

Prof . Dr. F.-O. Schreyer

Übungsblatt 7: Diskrete Logarithmen

Abgabetermin 2.7.2002

Voraussetzungen: Vorlesungskapitel Diskrete Logarithmen, Elliptische Kurven.

1. Implementieren Sie Shanks' baby-step giant-step Methode zur Berechnung von diskreten Logarithmen für eine allgemeine Gruppe G und testen Sie Ihr Skript mit
   1. G = $\mathbb {F}$_p ^* und

   2. G = E$\left(\vphantom{ \mathbb{F}_{p}}\right.$$\mathbb {F}$_p$\left.\vphantom{ \mathbb{F}_{p}}\right)$. Bestimmen Sie nicht die Gruppenordnung $\left\vert\vphantom{ E\left( \mathbb{F}_{p}\right) }\right.$E$\left(\vphantom{ \mathbb{F}_{p}}\right.$$\mathbb {F}$_p$\left.\vphantom{ \mathbb{F}_{p}}\right)$$\left.\vphantom{ E\left( \mathbb{F}_{p}\right) }\right\vert$, sondern verwenden Sie die obere Abschätzung aus dem Satz von Hasse.

2. Implementieren Sie Pollards $\rho$-Methode zur Berechnung von diskreten Logarithmen in $\mathbb {F}$_p ^* (Speicherung von $\beta_{{2^{j}}}^{}$ und $\beta_{{i}}^{}$ für i = 2^j +1,..., 2^j+1) und testen Sie sie an Beispielen.

3. Implementieren Sie den Pohlig-Hellman-Algorithmus für $\mathbb {F}$_p ^* und testen Sie ihn
   an Beispielen.

4. Vergleichen Sie die Laufzeit der Skripte aus den Aufgaben 1, 2 und 3 an Beispielen.

5. Berechnen Sie mit dem Index-Calculus-Algorithmus unter Verwendung der Faktorbasis
   F : = $$\left\{\vphantom{ 2,3,5}\right.$$2, 3, 5$$\left.\vphantom{ 2,3,5}\right\}$$
   die Lösung von
   13^x $$\equiv$$ 19mod479

Abgabe der Aufgaben bitte als email an:

$$\begin{array}[c]{l}%% \text{boehm@btm8x5.mat.uni-bayreuth.de}\\ \text{oder}\\ \text{boehm@math.uni-sb.de}%% \end{array}$$