Pohlig-Hellman-algoritme

Uit Wikipedia, de vrije encyclopedie
(Doorverwezen vanaf Pohlig-Hellman algoritme)
Ga naar: navigatie, zoeken

Het Pohlig-Hellman algoritme is een algoritme om het discreet logaritme 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[bewerken]

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^2n_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[bewerken]

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

Voorbeeld 1[bewerken]

Gegeven is 2n = 28 (mod 37). Te berekenen is n. Aanpak: 37 - 1 = 36 = 22·32 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 = n0 + pn1.

We berekenen voor de priemdelers de lijsten {r_{2,j}} = {1,-1} en {r_{3,j}} = {1,26,10}. Stel h = 2n = 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 n0 = 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 n0 = 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[bewerken]

Gegeven is 6n = 7531 (mod 8101). Aanpak: 8101 - 1 = 8100 = 2^{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 n0 = 1. h_ 1 = \frac{7531}{6} = 8006 (\bmod 8101) en 8006^{\frac{8100}{2^2}} = 1 (\bmod 8101) = r_{2,0} dus n1 = 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 n0 = 2. h_1 = \frac{7531}{6^2} = 6735 (\bmod 8101) en vervolgens 6735^{\frac{8100}{3^2}} = 1 (\bmod 8101) = r_{3,0} dus n1 = 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 n3 = 1.

De congruentievergelijking is dan n = 2+0·3+2·32+1·33=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 ni 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 n0 en n1 hoeven te weten. {7531}^{\frac{8100}{5}} = 5221 (\bmod 8101) = r_{5,4} dus n0 = 4.

h_1 = \frac{7531}{6^4} = 7613 (\bmod 8101) en 7613^{\frac{8100}{5^2}} = 356 (\bmod 8101) = r_{5,2} dus n1 = 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[bewerken]

Gegeven is 71n = 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 n0 = 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 n0 = 2. Dan h_1 = \frac{210}{71^2} = 10 (\bmod 251) en 10^{\frac{250}{25}} = 113 (\bmod 251) = r_{5,4} dus n1 = 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[bewerken]

Referenties[bewerken]

  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