Im vorangegangenen Abschnitt haben wir ein Kryptosystem betrachtet, dessen Sicherheit darauf beruht, dass das Diskrete Logarithmusproblem (DLP) schwierig ist, also auf der Annahme, dass es keine polynomiellen Lösungsverfahren gibt. Wir wollen nun versuchen, das DLP algorithmisch zu lösen.

Diskretes Logarithmusproblem (DLP)
Gegeben: Ein Tripel $\text{[math]}$ , wobei $\text{[math]}$ Primzahl ist, $\text{[math]}$ und $\text{[math]}$ primitiv in $\text{[math]}$ .
Gesucht: Das $\text{[math]}$ mit $\text{[math]}$ .

Trivialer Algorithmus
Für $\text{[math]}$ berechne $\text{[math]}$ bis $\text{[math]}$ gilt, die Lösung ist dann $\text{[math]}$ .

Die Anzahl der Multiplikationen bei diesem trivialen Algorithmus ist im worst case $\text{[math]}$ , also nicht polynomiell in der Eingabelänge $\text{[math]}$ .

Der Pohlig-Hellman Algorithmus berechnet zu gegebenem Tripel $\text{[math]}$ ( $\text{[math]}$ prim, $\text{[math]}$ und $\text{[math]}$ primitiv in $\text{[math]}$ ) ein $\text{[math]}$ mit $\text{[math]}$ , wobei $\text{[math]}$ gilt und $\text{[math]}$ eine Primzahl ist mit $\text{[math]}$ , $\text{[math]}$ , aber $\text{[math]}$ .

Kennt man alle paarweise verschiedenen Primteiler $\text{[math]}$ von $\text{[math]}$ , also $\text{[math]}$ , so liefert das Pohlig-Hellman Verfahren Werte $\text{[math]}$ , $\text{[math]}$ . Damit kann der Wert $\text{[math]}$ mit $\text{[math]}$ , $\text{[math]}$ , mit dem Chinesischen Restsatz leicht berechnet werden, sodass gilt $\text{[math]}$ .

Bevor wir das Verfahren anwenden, machen wir zunächst einige Vorbemerkungen. Sei $\text{[math]}$ und $\text{[math]}$ für eine Primzahl $\text{[math]}$ . Der gesuchte Wert $\text{[math]}$ mit $\text{[math]}$ hat eine Darstellung der Form

mit $\text{[math]}$ für $\text{[math]}$ . Man berechnet nun sukzessive die Werte $\text{[math]}$ .

Lemma 8
Seien $\text{[math]}$ prim, $\text{[math]}$ und $\text{[math]}$ primitiv in $\text{[math]}$ . Dann gilt

\text{[math]}

Beweis Aus $\text{[math]}$ und $\text{[math]}$ folgt die Existenz von $\text{[math]}$ mit $\text{[math]}$ . Mit $\text{[math]}$ reicht es daher zu zeigen, dass gilt

\text{[math]}

Dieses ist nach dem Satz von Fermat äquivalent zu

\text{[math]}

was offenbar erfüllt ist.

Beim Pohlig-Hellman Verfahren wird $\text{[math]}$ für $\text{[math]}$ berechnet bis $\text{[math]}$ erfüllt ist, man setzt dann $\text{[math]}$ .

Für $\text{[math]}$ ist man fertig, sonst wird $\text{[math]}$ wie folgt berechnet: Sei $\text{[math]}$ und setze $\text{[math]}$ und $\text{[math]}$ . Dann gilt $\text{[math]}$ und somit folgt wie in Lemma 8

Also wird $\text{[math]}$ berechnet, $\text{[math]}$ , bis $\text{[math]}$ erfüllt ist, dann setzt man $\text{[math]}$ .

Pohlig-Hellman Verfahren:
Gegeben: Ein Tripel $\text{[math]}$ mit $\text{[math]}$ prim, $\text{[math]}$ und $\text{[math]}$ primitiv in $\text{[math]}$ sowie eine Primzahl $\text{[math]}$ mit $\text{[math]}$ aber $\text{[math]}$ .
Gesucht: Ein $\text{[math]}$ mit $\text{[math]}$ und $\text{[math]}$ , wobei gilt $\text{[math]}$ .

Man muss maximal $\text{[math]}$ Schritte durchführen, von denen jeder einzelne in Zeit $\text{[math]}$ durchführbar ist. Mit $\text{[math]}$ und $\text{[math]}$ folgt $\text{[math]}$ . Gilt für jeden einzelnen Primfaktor $\text{[math]}$ mit $\text{[math]}$ nun $\text{[math]}$ , so löst das Pohlig-Hellman Verfahren das Diskrete Logarithmus Problem in Polynomialzeit, wenn die Primfaktorzerlegung von $\text{[math]}$ gegeben ist. Letzteres ist natürlich nicht unproblematisch.

Zusammenfassend können wir sagen: Ist die Primzahlzerlegung von $\text{[math]}$ "leicht" zu finden, so ist das Diskrete Logarithmus Problem mit dem Pohlig-Hellman Verfahren "effizient" zu lösen.

Exkurs: Ein Lösungsansatz für das DLP, Der Pohlig-Hellman Algorithmus

Exkurs: Ein Lösungsansatz für das DLP,
Der Pohlig-Hellman Algorithmus