Numerická metoda Index Calculus

Numerická metoda zvaná Index Calculus slouží k řešení problému diskrétního logaritmu. Je tedy využitelná ke kryptoanalýze systémů jako ElGamal či Diffie–Hellmanův protokol. Efektivita metody je výrazně lepší, nežli metoda hrubé síly (prosté zkoušení všech možných kombinací), přesto však není natolik dobrá, aby se kryptosystémy spoléhající na diskrétní logaritmus mohly nazvat prolomené.

Princip

Řešíme rovnici (tj. hledáme celé číslo x):

g^x ≡ h (mod p)

kde obecně g je generátor multiplikativní grupy, h libovolné celé číslo a p je prvočíselný řád této grupy (pro vysvětlení těchto pojmů viz např. kapitola ElGamal). Tedy hledáme hodnotu diskrétního logaritmu.

1. Vytvoříme faktorovou základnu F složenou z r prvočísel (obvykle prvních r) a čísla (-1). Faktorová základna je vlastně uspořádaná množina těchto čísel, počet prvků F je (r + 1). Tedy:

   F = {-1, p₁, p₂, p₃, ..., , p_r}

   kde p_i představuje nějaké prvočíslo.

2. Nyní generujeme náhodná celá čísla k a vyčíslujeme hodnotu g(k) jako:

   g(k) = g^k mod p

   přičemž pokud je číslo g(k) hladké nad F, ukládáme jeho exponenty do matice M. Vložený řádek také nesmí být lineární kombinací již vložených řádků, pokud se tak stane, neuvažujeme jej.

   Několik poznámek:

   1. Číslo je hladké nad množinou celých čísel F, pokud jeho prvočíselný rozklad tvoří pouze vybrané prvky z F (tj. neobsahuje žádné prvočíslo neobsažené v množině F).

   2. Matici konstruujeme tím stylem, že v prvním sloupečku jsou exponenty daného čísla příslušející (-1), ve druhém sloupečku prvnímu prvočíslu v F, v dalším druhému prvočíslu v F atd. V posledním sloupečku je výjimka, zde je uloženo samotné číslo k.

3. Algoritmus dle druhého bodu končí ve chvíli, kdy se podaří nalézt (r + 1) řádků matice M.

4. Nyní se vyřeší rozšířená matice soustavy (tj. matice se převede do redukovaného pivotovaného tvaru). Zde pozor na to, že se pracuje v prostoru kongruencí (mod p - 1). Pokud si označíme seřazená řešení jako e₀, e₁, e₂, ..., e_r

5. Postupně se pro čísla k = 0, 1, 2, 3, ... zkouší vypočítat hodnotu s(k):

   s(k) = s^k·h mod p

   Pokud je číslo s(k) hladké nad F (viz definice výše), algoritmus končí. Příslušné exponenty se dle logiky kroku čtyři označí jako: f₀, f₁, f₂, ..., f_r.

6. Řešením, tedy hledanou hodnotou x diskrétního logaritmu, je:

   x = (e₀·f₀ + e₁·f₁ + ... + e_r·f_r - s(k) ) mod p