Frage von safur, 10

Babystep-Giantstep-Algorithmus bei Kryptografie?

Kann mir jemand sagen wie man diesen Algo in der Kryptografie einsetzen kann? Ich habe es noch nicht so ganz verstanden.

Antwort
von phigeek, 6

Für die Lösung der Gleichung 3 = 11^x mod 29 ist auf Wikipedia (beim Algorithmus von Shanks )https://de.wikipedia.org/wiki/Babystep-Giantstep-Algorithmus ein gutes Zahlenbeispiel, das zunächst das m zur Gruppenordnung (28) berechnet, danach die Paare (j, 11^j) in einer Tabelle ablegt und danach wird 11^(-m) berechnet. Im 3. Teil wird a(g^(-m))^i für alle i berechnet, bis das Resultat in der 2. Zeile der vorherigen Tabelle gefunden wurde.

Dieses Verfahren dauert doch schon etwas schneller, als wenn Du alle folgenden Rechnungen bis zu 17 (der effektiven Lösung) durchprobieren müsstest:

3 = 11^1 mod 29 ?

3 = 11^2 mod 29 ?

3 = 11^3 mod 29 ?

...

3 = 11^17 mod 29 ! heureka

Kommentar von safur ,

Vielen Dank, verstanden :-)

Keine passende Antwort gefunden?

Fragen Sie die Community