Algoritmus Baby-step Giant-step patří k univerzálním algoritmům pro řešení problému diskrétního logaritmu Pro své fungování vyžaduje více paměti, ale za to dostáváme odmocninovou složitost oproti hrubé síle. To ovlivnuje vztah velikosti klíče na bezpečnost algoritmu. U Diffie Helman používáme z důvodu existence těchto algoritmů delší klíč.
Je lepší zvolit modul známého číslam, než náhodně vygenerované prvočíslo.
Pokud je modul M složené celé číslo - tzn. je součinem mnoha prvočísel je snažší prolomit Diffie Helmanův algoritmus.
Pracujeme v multiplikativní grupě.
Známe modul (řád grupy) M, prvek g a hodnotu
$$b = |g^x|_M$$
Chceme tímto algoritmem najít hodnotu x.
Vyjádřeme si x jako x = i*n + j kde i, j, n jsou celá čísla ℤ. Vyjádříme si n jako odmocninu modulu $n = \sqrt{M}$, pro platí 0 ≤ i, j < n:
-
$|g^{in+j}|_M = b$, vydělíme rovnici $g^{in}$
$|g^{j}|_M = |\frac{b}{ g^{in} }|_M$
- Spočítáme si tabulku pro všechna j → gj, kde 0 ≤ j < n:
- Spočítáme si g-n.
Využíváme znalosti z teorie čísel:- Z Fermatovy věty víme, že pro celé číslo a je $a^{p-1}$ kongruentní s 1.
- $aa^{-1} = 1$ z definice inverze.
$a^{p-1} = aa^{-1}$
$a^{p-2} = a^{-1}$
To znamená, že inverzi vypočítáme vydělením a.
- Dosazujeme hodnoty i do $b.g^{-n} = b.g^{-in}$ a hledáme rovnost v tabulce.