Indexcalculusalgoritme

In de groepentheorie, een onderdeel van de wiskunde, is het indexcalculusalgoritme een algoritme om voor sommige groepen de discrete logaritme, h = gⁿ, op te lossen, waar g en h elementen van groep, G, zijn. Een discrete logaritme is gedefinieerd op een eindige groep G. Voor g als voortbrenger van G en h ${\displaystyle \in }$ G wordt naar de oplossing van ${\displaystyle h=g^{n}}$ gevraagd.

Het algoritme

Het indexcalculusalgoritme kan onder andere toegepast worden op eindige lichamen.

De methode voor priemlichamen ${\displaystyle \mathbb {F} }$${\displaystyle _{p}}$ en binaire lichamen ${\displaystyle \mathbb {F} _{2^{m}}}$ kan als volgt beschreven worden:

In priemlichamen

${\displaystyle \langle }$g${\displaystyle \rangle }$ is een subgroep van ${\displaystyle \mathbb {F} _{p}^{*}}$, h ${\displaystyle \in }$ ${\displaystyle \langle }$g${\displaystyle \rangle }$
Voor welke n ${\displaystyle \in \mathbb {Z} }$ geldt ${\displaystyle h=g^{n}}$ (mod p)

Het algoritme maakt gebruik van een factorbasis van een aantal kleine priemgetallen, B={ (-1), 2, 3, 5, 7,..., r}

Stap 1:
Zoek een aantal elementen van ${\displaystyle \langle }$g${\displaystyle \rangle }$ die de eigenschap hebben dat ze te ontbinden zijn in priemfactoren uit de verzameling B.
Die groepselementen schrijven we als ${\displaystyle g^{r_{i}}=(-1)^{e_{1}}\cdot p_{2}^{e_{2}}\cdot \dots \cdot p_{k}^{e_{k}}}$

Stap 2:
Neem aan beide zijden de logaritme. Zo ontstaat een stelsel van lineaire vergelijkingen waaruit de discrete logaritmen van de gebruikte priemgetallen op te lossen zijn.

Stap 3:
Zoek vervolgens naar een element ${\displaystyle g^{i}}$ zodat h ${\displaystyle \cdot }$ ${\displaystyle g^{i}}$ te ontbinden is met priemfactoren uit B.
h ${\displaystyle \cdot }$ (g${\displaystyle ^{r_{i}}}$) = (-1)${\displaystyle ^{e_{1}}}$ ${\displaystyle \cdot }$ ${\displaystyle p_{2}}$${\displaystyle ^{e_{2}}}$ ${\displaystyle \cdot }$ ... ${\displaystyle \cdot }$ ${\displaystyle p_{k}}$${\displaystyle ^{e_{k}}}$
Door aan beide zijden de logaritme te nemen volgt de waarde van n.
Met behulp van onderstaand voorbeeld zijn de drie stappen van het algoritme uitgewerkt.

In binaire lichamen

De elementen van het eindige lichaam ${\displaystyle \mathbb {F} _{2^{m}}}$ worden weergegeven als veeltermen in ${\displaystyle \mathbb {F} }$${\displaystyle _{2}}$[x] met een graad die ten hoogste ( m-1) is. De operatie is vermenigvuldigen modulo een vastgestelde veelterm van de graad n, f(x) in ${\displaystyle \mathbb {F} }$${\displaystyle _{2}}$[x], die niet te ontbinden is.
Kies voor factorbasis B elementen uit de verzameling van alle niet te ontbinden veeltermen in ${\displaystyle \mathbb {F} }$${\displaystyle _{2}}$[x] met als graad niet meer dan een tevoren vastgestelde bovengrens.

Stap 1:
Zoek veeltermen ${\displaystyle g^{k}}$ mod f(x), met g als voortbrenger van ${\displaystyle \mathbb {F} _{2^{m}}}$ die een product zijn van veeltermen uit B.

Stap 2:
Precies als bij priemlichamen zijn de logaritmen van de veeltermen te vinden door een stelsel vergelijkingen op te lossen.

Stap 3: Zoek vervolgens naar een veelterm ${\displaystyle g^{i}}$ zodat h ${\displaystyle \cdot }$ ${\displaystyle g^{i}}$ te ontbinden is met veeltermen uit B.
Door aan beide zijden de logaritme te nemen volgt de waarde van n.

Voorbeelden

In priemlichamen

We gaan uit van ${\displaystyle \mathbb {F} _{2003}^{*}}$= ${\displaystyle \langle }$5${\displaystyle \rangle }$ met p=2003.
We kiezen nu h = 543 uit die groep en willen n oplossen uit h = ${\displaystyle 5^{n}}$ mod 2003.

Stap 1:
Neem B = {(-1), 2, 3, 5, 7, 11, 13, 19}. Dit is een kleine factorbasis.
Het nadeel daarvan is dat je langer moet zoeken naar getallen die daarmee te ontbinden zijn, het voordeel is dat het op te lossen stelsel beperkt van omvang is.
We kiezen nu willekeurig getallen uit ${\displaystyle \langle }$5${\displaystyle \rangle }$ en ontbinden die in priemgetallen. Alleen de getallen die m.b.v.B te ontbinden zijn kunnen we gebruiken.

964 = ${\displaystyle 2^{2}}$ ${\displaystyle \cdot }$ ${\displaystyle 241^{1}}$
zullen we niet gebruiken.

Na een aantal keer proberen hebben we:

${\displaystyle {\begin{matrix}5^{37}&=&2^{3}&\cdot &13^{1}&\cdot &19^{1}\\5^{37}&=&(-1)^{1}&\cdot &3^{3}&&&\\5^{1998}&=&2^{1}&\cdot &7^{1}&\cdot &19^{1}\\5^{21}&=&2^{9}&&&&\\5^{108}&=&(-1)^{1}&\cdot &7^{1}&\cdot &13^{2}\end{matrix}}}$

Elk priemgetral komt minstens twee keer voor. De eerste vergelijking schrijven we nu als volgt op:

${\displaystyle ^{5}}$log ${\displaystyle 5^{37}}$ = ${\displaystyle ^{5}}$log (${\displaystyle 2^{3}}$ ${\displaystyle \cdot }$ ${\displaystyle 13^{1}}$ ${\displaystyle \cdot }$ ${\displaystyle 19^{1}}$) = ${\displaystyle ^{5}}$log ${\displaystyle 2^{3}}$ + ${\displaystyle ^{5}}$log13 + ${\displaystyle ^{5}}$log19
37 = 3 ${\displaystyle \cdot }$ ${\displaystyle ^{5}}$log2 + 1 ${\displaystyle \cdot }$ ${\displaystyle ^{5}}$log13 + 1 ${\displaystyle \cdot }$ ${\displaystyle ^{5}}$log19

Voor 108 geldt:
108 = 1 ${\displaystyle \cdot }$ ${\displaystyle ^{5}}$log(-1) + 1 ${\displaystyle \cdot }$ ${\displaystyle ^{5}}$log7 + 2 ${\displaystyle \cdot }$ ${\displaystyle ^{5}}$log13

Omdat ${\displaystyle 5^{2002}}$ = 1, en dus (${\displaystyle 5^{1001}}$)${\displaystyle ^{2}}$ = 1, moet gelden dat ${\displaystyle 5^{1001}}$ = -1 (mod 2002). Elk element van ${\displaystyle \langle }$5${\displaystyle \rangle }$ is immers uniek.
Daardoor weten we dat
108 = 1001 + 1 ${\displaystyle \cdot }$ ${\displaystyle ^{5}}$log7 + 2 ${\displaystyle \cdot }$ ${\displaystyle ^{5}}$log13

Stap 2:
We willen nu de waarde van de gebruikte logaritmen weten. Die vinden we door gebruik te maken van de volgende matrix.

${\displaystyle {\begin{matrix}^{5}\log 2&^{5}\log 7&^{5}\log 13&^{5}\log 19&\\3&0&1&1&37\\1&1&0&1&1998\\0&1&2&0&1109\\9&0&0&0&21\end{matrix}}}$

Deel in de onderste rij door 9.
21 representeert een getal (21 + k ${\displaystyle \cdot }$ 2002)
Voor k = 6 levert dat 12033 en dat is deelbaar door 9.
Nu weten we dat
${\displaystyle ^{5}}$log2 = 1337 (mod 2002).

${\displaystyle {\begin{matrix}^{5}\log 2&^{5}\log 7&^{5}\log 13&^{5}\log 19&\\0&0&1&1&37-3\cdot 1337=30\\0&1&0&1&1998-1337=661\\0&1&2&0&1109\\1&0&0&0&1337\end{matrix}}}$

${\displaystyle {\begin{matrix}^{5}\log 7&^{5}\log 13&^{5}\log 19&\\0&1&1&30\\1&0&1&661\\1&2&0&1109\end{matrix}}}$

${\displaystyle {\begin{matrix}^{5}\log 7&^{5}\log 13&^{5}\log 19&\\0&1&1&30\\1&-1&0&661-30=631\\1&2&0&1109\end{matrix}}}$

${\displaystyle {\begin{matrix}^{5}\log 7&^{5}\log 13&^{5}\log 19&\\0&1&1&30\\1&-1&0&631\\3&0&0&1109+2\cdot 631=369\end{matrix}}}$

Nu volgt ${\displaystyle ^{5}}$log7 = 123 ( mod 2002)
${\displaystyle ^{5}}$log13 = 123 - 631 + 1494 ( mod 2002)
${\displaystyle ^{5}}$log19 = 30 - 1494 = 538 ( mod 2002)

Stap 3:
We zoeken nu naar een geschikte ontbinding van getallen van de volgende vorm: 543 ${\displaystyle \cdot }$ ${\displaystyle 5^{i}}$
Na een paar keer proberen hebben we

543 ${\displaystyle \cdot }$ ${\displaystyle 5^{433}}$ = (-1) ${\displaystyle \cdot }$ ${\displaystyle 2^{2}}$ ${\displaystyle \cdot }$ ${\displaystyle 19^{2}}$

Daaruit volgt de vergelijking

${\displaystyle ^{5}}$log 543 ${\displaystyle \cdot }$ ${\displaystyle 5^{433}}$ = ${\displaystyle ^{5}}$log(-1) + 2 ${\displaystyle \cdot }$ ${\displaystyle ^{5}}$log2 + 2 ${\displaystyle \cdot }$ ${\displaystyle ^{5}}$log19
${\displaystyle ^{5}}$log 543 +433 = 1001 + 2 ${\displaystyle \cdot }$ 1337 + 2 ${\displaystyle \cdot }$ 538

Hieruit volgt ${\displaystyle ^{5}}$log 543 = 314,
de oplossing: n = 314

In binaire lichamen

We gaan uit van ${\displaystyle \mathbb {F} _{2^{7}}}$ mod f(x) = ${\displaystyle x^{7}}$ + x + 1
De elementen van ${\displaystyle \mathbb {F} _{2^{7}}}$ zijn alle veeltermen in ${\displaystyle \mathbb {F} }$${\displaystyle _{2}}$ van ten hoogste de graad 6. De operatie is vermenigvuldigen mod f(x). De orde van ${\displaystyle \mathbb {F} _{2^{7}}}$ is 128 - 1 = 127
De veelterm g = x is voortbrenger van ${\displaystyle \mathbb {F} _{2^{7}}}$
We kiezen nu h = ${\displaystyle x^{4}}$ + ${\displaystyle x^{3}}$ +${\displaystyle x^{2}}$ + x + 1 uit die groep en willen n oplossen uit
${\displaystyle x^{4}}$ + ${\displaystyle x^{3}}$ +${\displaystyle x^{2}}$ + x + 1 =${\displaystyle x^{n}}$ mod f(x)

Stap 1:
Kies als factorbasis de verzameling van alle niet te ontbinden veeltermen in ${\displaystyle \mathbb {F} }$${\displaystyle _{2}}$[x] van ten hoogste de graad 3.
B = { x, x + 1, ${\displaystyle x^{2}}$ + x + 1, ${\displaystyle x^{3}}$ + x + 1, ${\displaystyle x^{3}}$ + ${\displaystyle x^{2}}$ + 1}
Zoek nu veeltermen die te ontbinden zijn met veeltermen uit B. Hieronder staan er vijf waarbij dat lukt.

${\displaystyle {\begin{matrix}x^{18}&{\bmod {f}}(x)&=&x^{6}+x^{4}&=&x^{4}(x+1)^{2}\\x^{105}&{\bmod {f}}(x)&=&x^{6}+x^{5}+x^{4}+x&=&x(x+1)^{2}(x^{3}+x^{2}+1)\\x^{72}&{\bmod {f}}(x)&=&x^{6}+x^{5}+x^{3}+x^{2}&=&x^{2}(x+1)^{2}(x^{2}+x+1)\\x^{45}&{\bmod {f}}(x)&=&x^{5}+x^{2}+x+1&=&(x+1)^{2}(x^{3}+x+1)\\x^{121}&{\bmod {f}}(x)&=&x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1&=&(x^{3}+x+1)(x^{3}+x^{2}+1)\end{matrix}}}$

Stap 2:
We willen nu de waarde van de gebruikte logaritmen weten.
stel

${\displaystyle {\begin{matrix}p_{1}&=&^{x}\log x\\p_{2}&=&^{x}\log(x+1)\\p_{3}&=&^{x}\log(x^{2}+x+1)\\p_{4}&=&^{x}\log(x^{3}+x+1)\\p_{5}&=&^{x}\log(x^{3}+x^{2}+1)\end{matrix}}}$

Dit geeft

${\displaystyle {\begin{matrix}18&=&4p_{1}+2p_{2}&{\bmod {1}}27\\105&=&p_{1}+2p_{2}+p_{5}&{\bmod {1}}27\\72&=&2p_{1}+2p_{2}+p_{3}&{\bmod {1}}27\\45&=&2p_{2}+p_{4}&{\bmod {1}}27\\121&=&p_{4}+p_{5}&{\bmod {1}}27\end{matrix}}}$

Omdat ${\displaystyle p_{1}}$ = 1 is dit te vereenvoudigen tot

${\displaystyle {\begin{matrix}14&=&2p_{2}&{\bmod {1}}27\\104&=&2p_{2}+p_{5}&{\bmod {1}}27\\70&=&2p_{2}+p_{3}&{\bmod {1}}27\\45&=&2p_{2}+p_{4}&{\bmod {1}}27\\121&=&p_{4}+p_{5}&{\bmod {1}}27\end{matrix}}}$

Hieruit volgt ${\displaystyle p_{2}}$ = 7, dus ${\displaystyle p_{5}}$ = 90, ${\displaystyle p_{3}}$ = 56 en ${\displaystyle p_{4}}$ = 31

Stap 3:
We zoeken nu naar een geschikte ontbinding van veeltermen van de vorm h ${\displaystyle \cdot }$ ${\displaystyle x^{i}}$ mod f(x) die te ontbinden is met veeltermen uit B.
Dat lukt voor i = 66
(${\displaystyle x^{4}}$ + ${\displaystyle x^{3}}$ + ${\displaystyle x^{2}}$ + x + 1) ${\displaystyle x^{66}}$ mod f(x) = ${\displaystyle x^{5}}$ + ${\displaystyle x^{3}}$ + x = x(${\displaystyle x^{2}}$ + x + 1)${\displaystyle ^{2}}$
Dus ${\displaystyle ^{x}}$log(${\displaystyle x^{4}}$ + ${\displaystyle x^{3}}$ + ${\displaystyle x^{2}}$ + x + 1) = ( ${\displaystyle p_{1}}$ + 2 ${\displaystyle \cdot }$ ${\displaystyle p_{3}}$ -66) ( mod 127) = 47
de oplossing: n = 47

Zie ook

• Baby-steps giant-steps-algoritme
• Pohlig-Hellman-algoritme
• Pollards lambda-algoritme
• Pollards rho-algoritme

Referenties

• (en) Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, 2001.
• (en) D.J. Bernstein, Generic attacks and index calculus , University of Illinois, Chicago.
• (en) Neal Koblitz, A Course in Elementary Number Theory and Cryptography, Springer.