Index Calculus
Die Index-Calculus-Methode löst diskrete Logarithmen in Z_p^* mittels Faktorbasis und linearer Algebra, mit subexponentieller Komplexität L_p[1/2,√2].
Zweck
Generische Algorithmen für diskrete Logarithmen in Primkörpern schlagen und damit die Parameterwahl für DSA/DH leiten.
Mechanismus
Eine Faktorbasis S={kleine Primzahlen} wird gewählt. Man zieht zufällige k und berechnet g^k mod p; ist das Ergebnis S-glatt, liefert es eine lineare Relation ∑e_i·log(s_i)≡k (mod p−1). Genügend Relationen sammeln, log(s_i) per linearer Algebra lösen und dann den Ziel-log(h) berechnen.
Anwendungsfälle
- Diskreter-Logarithmus-Angriffe
- Kryptoanalyse
- Zahlentheoretische Algorithmen