Pohlig-Hellman algoritme

Het Pohlig-Hellman algoritme is een algoritme om het Discrete Logaritme Probleem (DLP) zoals dat is gedefinieerd in een cyclische groep te berekenen.

Het algoritme is gebaseerd op het feit dat een geheel getal n geschreven kan worden als $n \equiv n_0 + pn_1 + \cdots + p^{i-1}n_{i-1}(\bmod p^i$) en dat de simultane congruenties $n \equiv a \bmod r$ en $n \equiv b \bmod s$ volgens de Chinese reststelling een unieke oplossing heeft. Deze oplossing is het gevraagde getal n als $n\leq rs$.

Het algoritme werd ontdekt door Roland Silver, maar voor het eerst gepubliceerd door Stephen Pohlig en Martin Hellman (onafhankelijk van Silver).

Het algoritme is belangrijk op eindig lichaamen $\mathbb{F}_q$. Elk getal is te schrijven als een product van priemfactoren. Stel q - 1 = ${p_1}^{e_1}$·${p_2}^{e_2}$·...·${p_i}^{e_i}$, waar q een priemgetal is. Als q - 1 een product is van kleine priemfactoren, dan is het Polig-Hellman algoritme een methode om deze discrete logaritme te berekenen. In dat geval zeggen we dat het getal q - 1 glad is. In het Duits gebruikt men het woord "glatt" en in het Engels "smooth".

Theorie

Laat q een priemgetal zijn en laat $g$ voortbrenger zijn van $\mathbb{F}_q^*$. We zoeken het positief getal n kleiner dan q - 1, zo dat $g^n$=h(mod q). Als q - 1 = ${p_1}^{e_1}$·${p_2}^{e_2}$·...·${p_i}^{e_i}$, is het voldoende n(mod $p^e$) te vinden voor elke priemfactor $p$ van q - 1. Vooraf berekenen we voor elke priemfactor afzonderlijk de p-de-machts wortelen $r_{p,j}$=$g^{\frac{j(q-1)}{p}}$ voor j = 1, 2, ..., p - 1. Om $n_0$ te vinden, berekenen we $h^{\frac{q-1}{p}}$.

Volgens de kleine stelling van Fermat geldt $h^{q-1}$mod q = 1. Dus berekent $h^{\frac{q-1}{p}}$ de p-de-machts wortel van 1.

Vanwege $g^n$=h krijgen we $h^{\frac{q-1}{p}}$ = ${g^n}^{\frac{q-1}{p}}$ = ${g}^{\frac{n(q-1)}{p}}$ = ${g}^{\frac{n_0(q-1)}{p}}$. Dit laatste is gelijk aan $r_{p,n_0}$. Nu vergelijken we $h^{\frac{q-1}{p}}$ met {$r_{p,j}$} en stellen $n_0$ gelijk aan j als $h^{\frac{q-1}{p}}$ = $r_{p,j}$.

Na $n_0$ moeten we $n_1$, $n_2$, enz. vinden. Om $n_1$ te vinden, maken we de aanpassing $h_1$ = $\frac{h}{g^{n_0}}$.

De discrete logaritme van n = $log_g (h)$ wordt dan n = $log_g$($h_1$·$g^{n_0}$) = $log_g$($h_1$) + $log_g$($g^{n_0}$) = $log_g$ ($h_1$) + $n_0$. Dus $log_g$ ($h_1$) = n - $n_0$ = $pn_1$ + $p^2$$n_2$ + ... + $p^{m-1}$ $n_{m-1}$ (mod $p^m$). n Hieruit volgt $h_1$ = $g^{n-n_0}$ en dus ${h_1}^{\frac{q-1}{p}}$ = ${g^{(n-n_0)}}^{\frac{q-1}{p}}$ = ${g^{q-1}}^{\frac{n-n_0}{p}}$ = ${(1)}^{\frac{n-n_0}{p}}$ = 1. Tevens ${h_1}^{\frac{q-1}{p^2}}$ = $g^{\frac{(n-n_0)(q-1)}{p^2}}$ = $g^{\frac{(pn_1+p^{2}n_2 + ... + p^{m-1}n_{m-1})(q-1)}{p^2}}$ = $g^{\frac{(n_1+pn_2 + ... + p^{m-2}n_{m-1})(q-1)}{p}}$ = $g^{\frac{n_{1}(q-1)}{p}}$ = $r_{p,n_1}$.

Nu vergelijken we ${h_1}^{\frac{q-1}{p^2}}$ met de lijst {$r_{p,j}$} en stellen $n_1$ gelijk aan j als ${h_1}^{\frac{q-1}{p^2}}$ = $r_{p,j}$.

Op deze manier kunnen we verder alle $n_i$ vinden voor i = 1, 2, ..., m-1. Om $n_i$ te vinden, maken we de aanpassing $h_i = \frac{h}{g^{n_0 + pn_1 + ... + p^{i-1}n_{i-1}}}$. De discrete logaritme van n = $log_g (h)$ wordt dan $n \equiv n_0 + pn_1 + ... + p^{i-1}n_{i-1} \bmod p^i$.

Hieruit volgt $h_i = g^{n-n_{0}-n_{1}-...-p^{i-1}n_{i-1}}$ en dus ${h_{i}}^{\frac{q-1}{p^i}} = 1$ en ${h_{i}}^{\frac{q-1}{p^{i+1}}} = r_{p,n_i}$.

Nu vergelijken we ${h_{i}}^{\frac{q-1}{p^{i+1}}}$ met de lijst {$r_{p,j}$} en stellen n_i gelijk aan j als ${h_{i}}^{\frac{q-1}{p^{i+1}}}$ = $r_{p,j}$.

Voorbeelden

Hier volgen enkele voorbeelden met kleine getallen om m.b.v. het algoritme een DLP op te lossen. In de praktijk rekent men uiteraard met veel grotere getallen om de aanvallen van krakers af te slaan.

Voorbeeld 1

Gegeven is 2ⁿ = 28 (mod 37). Te berekenen is n. Aanpak: 37 - 1 = 36 = 2²·3² en we zien dat dit inderdaad een ontbinding is met kleine priemfactoren 2 en 3. Vanwege de exponenten die bij de priemfactoren staan (beide 2) zoeken we voor zowel p = 2 als p = 3 naar congruenties n = n₀ + pn₁.

We berekenen voor de priemdelers de lijsten {$r_{2,j}$} = {1,-1} en {$r_{3,j}$} = {1,26,10}. Stel h = 2ⁿ = 28 (mod 37) en bereken ${28}^{\frac{36}{2}} = 1 (\bmod 37)$

Dan geldt ${2^n}^{\frac{36}{2}} = {2}^{\frac{36n}{2}} = {2}^{\frac{36n_0}{2}} = r_{2,n_0}$. Hieruit volgt n₀ = 0

Bereken nu $h_1 = \frac{28}{2^0} = 28$ en daarmee ${28}^{\frac{36}{2^2}} = -1 (\bmod 37) = r_{2,n_1}$. Hieruit volgt $n_1 = 1$. Voor p = 2 wordt de congruentie dus n = 0 + 2·1 (mod 4) = 2 (mod 4).

Voor p = 3 gaan we als volgt te werk: bereken ${28}^{\frac{36}{3}} = 26 (\bmod 37) = r_{3,n_0}$. Hieruit volgt n₀ = 1.

Bereken nu $h_1 = \frac{28}{2^1} = 14$ en daarmee ${14}^{\frac{36}{3^2}} = 10 (\bmod 37) = r_{3,n_1}$. Hieruit volgt $n_1 = 2$. Voor p = 3 wordt de congruentie dus n = 1 + 3·2 (mod 9) = 7 (mod 9). Het stelsel congruentievergelijking dat opgelost kan worden met de Chinese reststelling is dus

n = 2 (mod 4)

n = 7 (mod 9)

en heeft als unieke oplossing n = 34.

Voorbeeld 2

Gegeven is 6ⁿ = 7531 (mod 8101). Aanpak: 8101 - 1 = 8100 = 2²·$3^{4}$·$5^{2}$ en we hebben weer kleine priemfactoren. {$r_{2,j}$} = {1,-1}; {$r_{3,j}$} = {1,5883,2217} en {$r_{5,j}$} = {1,3547,356,7077,5221}.

Voor p = 2: $7531^{\frac{8100}{2}} = -1 (\bmod 8101) = r_{2,1}$ dus n₀ = 1. $h_ 1 = \frac{7531}{6} = 8006 (\bmod 8101)$ en $8006^{\frac{8100}{2^2}} = 1 (\bmod 8101) = r_{2,0}$ dus n₁ = 0.

Voor p = 3 geldt een exponent 4, wat betekent dat de congruentievergelijking die we zoeken van de vorm $n = n_0 + 3n_1 + 3^{2}n_2 + 3^{3}n_3 \bmod 3^4$ is. We moeten dus $n_0$ t/m $n_3$ berekenen en vergelijken met de waarden uit de lijst {$r_{3,j}$} = {1,5883,2217}.

$7531^{\frac{8100}{3}} = 2217 (\bmod 8101) = r_{3,2}$ dus n₀ = 2. $h_1 = \frac{7531}{6^2} = 6735 (\bmod 8101)$ en vervolgens $6735^{\frac{8100}{3^2}} = 1 (\bmod 8101) = r_{3,0}$ dus n₁ = 0. $6735^{\frac{8100}{3^3}} = 2217 (\bmod 8101) = r_ {3,2}$ dus ook $n_2$ = 2. $\frac{6735}{6^{18}} = 6992 (\bmod 8101)$ en $6992^{\frac{8100}{3^4}} = 5883 (\bmod 8101) = r_{3,1}$ dus n₃ = 1.

De congruentievergelijking is dan n = 2+0·3+2·3²+1·3³=47 (mod 81). Opgemerkt zij nog dat na de berekening van $n_2$ we een aanpassing moeten maken. In de theorie staat dat $h_i$ gevonden kan worden door h te delen door $g^{n_0 + pn_1 + p^{2}n_{2} + ... + p^{i-1}n_{i-1}}$. We hadden dus om 6992 (mod 8101) te vinden ook de deling $\frac{7531}{6^{20}}$ kunnen doen. Hier hebben we dat niet gedaan, maar na elke stap het grondtal waarmee we rekenen omgebouwd, op het moment dat de gevonden n_i een getal ongelijk 0 opleverde. Je moet dan wel rekening houden met welke i je bezig bent, om die goed te verrekenen in de exponent bij 6.

Tenslotte p = 5, waarbij we alleen n₀ en n₁ hoeven te weten. ${7531}^{\frac{8100}{5}} = 5221 (\bmod 8101) = r_{5,4}$ dus n₀ = 4.

$h_1 = \frac{7531}{6^4} = 7613 (\bmod 8101)$ en $7613^{\frac{8100}{5^2}} = 356 (\bmod 8101) = r_{5,2}$ dus n₁ = 2. De derde congruentievergelijking is hiermee gevonden en het stelsel wordt dan

n = 1 (mod 4)

n = 47 (mod 81)

n = 14 (mod 25)

De unieke oplossing van dit stelsel is n = 6689.

Voorbeeld 3

Gegeven is 71ⁿ = 210 (mod 251). Aanpak: 251 - 1 = 250 = 2·$5^{3}$ en we hebben weer kleine priemfactoren. {$r_{2,j}$} = {1,-1}; {$r_{5,j}$} = {1,20,149,219,113}. Voor p = 2: $210^{\frac{250}{2}} = -1 (\bmod 251) = r_{2,1}$ dus n₀ = 1

Voor p = 5 geldt een exponent 3, wat betekent dat de congruentievergelijking die we zoeken van de vorm $n = n_0 + 5n_1 + 25n_2$ is. $210^{\frac{250}{5}} = 149 (mod 251) = r_{5,2}$ dus n₀ = 2. Dan $h_1 = \frac{210}{71^2} = 10 (\bmod 251)$ en $10^{\frac{250}{25}} = 113 (\bmod 251) = r_{5,4}$ dus n₁ = 4. Dan $h_2 = \frac{10}{71^20} = 231 (\bmod 251)$ en $231^{\frac{250}{125}} = 149 (\bmod 251) = r_{5,2}$ dus ook $n_2$ = 2.

De beide congruentievergelijkingen zijn dan n = 1 (mod 2) en n = 72 (mod 125) met unieke oplossing n = 197.

Zie ook

• Baby-steps giant-steps algoritme
• Index calculus algoritme
• Pollard's lambda algoritme
• Pollard's rho algoritme

Referenties

1. S. Pohlig en M. Hellman "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance", IEEE Transactions on Information Theory 24 (1978), pp. 106-110.
2. N. Koblitz "A Course in Number Theory and Cryptography, Graduate Texts in Mathematics 114 (1994), pp. 102-103