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 de discrete logaritme zoals die is gedefinieerd in een cyclische groep, te berekenen. In het bijzonder vindt het algoritme toepassing op de multiplicatieve groep \mathbb{F}_q^* van een eindig lichaam \mathbb{F}_q. Als q-1 het product is van kleine priemfactoren, noemt men het getal q-1 glad en is het Polig-Hellman-algoritme een geschikte methode om deze discrete logaritme te berekenen.

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

Het belang van deze methode is dat de hoeveelheid rekenwerk niet afhangt van de orde van de groep, maar van de grootste factor in de orde. Het nadeel is dat de orde gefactoriseerd moet worden in priemfactoren en een dergelijke factorisatie in het algemeen moeilijk vast te stellen is.

Algoritme[bewerken]

De werking van het algoritme wordt verklaard voor de multiplicatieve groep G=\mathbb{F}_q^* van het eindige lichaam \mathbb{F}_q met als orde q, een priemgetal. De orde van G is dan q-1. Zij nu g een voortbrenger van G, dan wordt het positieve gehele getal n < q gezocht, zodanig dat g^n=h\!\!\!\! \pmod q.

Het algoritme bepaalt voor elke priemfactor p_j in de ontbinding:

q = {p_1}^{e_1}{p_2}^{e_2}\ldots{p_i}^{e_i}

voor n een congruentievergelijking \bmod p_j^{e_j}. Omdat de p_j onderling priem zijn, is er volgens de Chinese reststelling een gemeenschappelijke oplossing n voor deze vergelijkingen.

Deelalgoritme[bewerken]

Het algoritme kan gedeeltelijk gereduceerd worden tot een algoritme dat voor de priemfactor p=p_j een congruentievergelijking voor n vindt. Daartoe schrijft men, met m=e_j:

n = n_0 + pn_1 + \ldots + p^{m-1}n_{m-1}\!\!\!\!\pmod {p^m}

en bepaalt in vergelijkbare stappen successievelijk de getallen n_j .

Vooraf worden voor j=0,1,\ldots,p-1 de p-de-machtswortels

r_{p,j}=g^{\frac{j(q-1)}{p}}

berekend, waaruit later teruggezocht kan worden welke j bij een bepaalde waarde van deze wortels hoort. Ook wordt om n_0 te vinden h^{\frac{q-1}{p}} berekend.

Volgens de kleine stelling van Fermat geldt a^{q-1}\!\!\!\!\pmod q=1, dus, omdat g^n=h\!\!\!\! \pmod q, volgt

h^{\frac{q-1}{p}}=\left(g^n\right)^{\frac{q-1}{p}}=g^{\frac{n(q-1)}{p}}=g^{\frac{n_0(q-1)}{p}}g^{(n_1+n_2p+\ldots +n_{m-1}p^{m-2})(q-1)}=g^{\frac{n_0(q-1)}{p}} =r_{p,n_0}\!\!\!\!\pmod q.

Vergelijk nu h^{\frac{q-1}{p}} met de berekende wortels in de lijst \{r_{p,j}\} en stel n_0=j als h^{\frac{q-1}{p}}=r_{p,j}.

Na n_0 moeten n_1,n_2,\ldots gevonden worden. Om n_1 te vinden, wordt h_1=\frac{h}{g^{n_0}} gesteld.

Voor de discrete logaritme n=\log_g(h) volgt dan

n=\log_g(h_1g^{n_0}) = \log_g(h_1) + \log_g(g^{n_0}) = \log_g(h_1)+n_0.

Dus er ontstaat een analoog probleem

h_1=g^{n-n_0}

en er moet gelden


{h_1}^{\frac{q-1}{p^2}}=g^{\frac{(n-n_0)(q-1)}{p^2}}=g^{\frac{(pn_1+p^{2}n_2 + \ldots + p^{m-1}n_{m-1})(q-1)}{p^2}}=g^{\frac{(n_1+pn_2 + \ldots + p^{m-2}n_{m-1})(q-1)}{p}}=g^{\frac{n_1(q-1)}{p}}=r_{p,n_1}.

Vergelijk nu {h_1}^{\frac{q-1}{p^2}} met de lijst \{r_{p,j}\} en stel n_1=j als {h_1}^{\frac{q-1}{p^2}}=r_{p,j}.

Op deze manier worden alle n_k gevonden voor k= 1,2,\ldots ,m-1. Om n_k te vinden, stelt men

h_k = \frac{h}{g^{n_0 + pn_1 + \ldots + p^{k-1}n_{k-1}}}.

De discrete logaritme n=\log_g (h) wordt dan

n \equiv n_0 + pn_1 + \ldots + p^{k-1}n_{k-1}\!\!\!\! \pmod {p^i}.

Hieruit volgt

h_k = g^{n-n_0-n_1-\ldots -p^{k-1}n_{k-1}}

en dus

{h_k}^{\frac{q-1}{p^k}} = 1

en {h_k}^{\frac{q-1}{p^{k+1}}} = r_{p,n_k}.

Vergelijk vervolgens {h_k}^{\frac{q-1}{p^{k+1}}} met de lijst \{r_{p,j}\} en stel n_k=j als {h_k}^{\frac{q-1}{p^{k+1}}}=r_{p,j}.

Zo is voor elk van de p=p_j een congruentievergelijking voor n gevonden:

n \equiv n_0 + pn_1 + \ldots + p^{i-1}n_{i-1}\!\!\!\!\pmod {p^i}.

Aangezien de p_j onderling priem zijn, hebben deze vergelijkingen volgens de Chinese reststelling een eenduidige oplossing.

Voorbeelden[bewerken]

Hier volgen enkele voorbeelden met kleine getallen om met het algoritme een discrete logaritme te bepalen. In de praktijk rekent men uiteraard met veel grotere getallen om de aanvallen van hackers af te slaan.

Voorbeeld 1[bewerken]

Gevraagd n te berekenen waarvoor 2^n\equiv 28 \pmod {37}. Hier is q=37 en de ontbinding van q-1 is q-1=36=2^2\times 3^2, een ontbinding met kleine priemfactoren 2 en 3. Vanwege de exponenten die bij de priemfactoren staan (beide 2), worden voor zowel p=2 als p=3 naar congruenties n = n_0 + pn_1 gezocht.

Voor de beide priemdelers zijn de lijsten \{r_{2,j}\}= \{1,36\} en \{r_{3,j}\}= \{1,26,10\}, want 2\!\!\!\! \pmod {37} = 1,\ \  2^{18}\!\!\!\! \pmod {37} = 36, etc.

Stel h = 2^n = 28\!\!\!\! \pmod {37} en bereken {28}^{36/2} = 1\!\!\!\! \pmod {37}

Dan geldt 1=h^{18}={2^n}^{36/2} = 2^{18n} = 2^{18n_0} = r_{2,n_0}. Hieruit volgt n_0 = 0.

Bereken nu h_1 = 28/2^0 = 28 en daarmee {28}^{36/2^2} = -1 \!\!\!\!\pmod {37} = r_{2,n_1}. Hieruit volgt n_1 = 1. Voor p = 2 wordt de congruentie dus n = 0 + 2\times 1 = 2\!\!\!\!\pmod 4.

Voor p = 3 berekent men {28}^{36/3} = 26 \pmod {37} = r_{3,n_0}. Hieruit volgt n_0 = 1.

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

n \equiv 2 \pmod 4
n \equiv 7 \pmod 9

en heeft als unieke oplossing n =34 .

Voorbeeld 2[bewerken]

Gevraagd n te berekenen waarvoor 6^n = 7531\!\!\!\!\pmod {8101}. De ontbinding van q-1 is 8101 - 1 = 8100 = 2^2\times 3^4\times 5^2 en er zijn weer alleen kleine priemfactoren.

\{r_{2,j}\} = \{1,-1\}; \{r_{3,j}\} = \{1,5883,2217\}, \{r_{5,j}\} =\{ 1,3547,356,7077,5221\}.

Voor p=2:

7531^{8100/2} = -1 \pmod {8101} = r_{2,1} dus n_0=1.
h_ 1 = 7531/6 = 8006 \pmod {8101}

en

8006^{8100/2^2} = 1 \pmod {8101}= r_{2,0} dus n_1=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^2n_2 + 3^3n_3 \pmod {3^4}

is. Gezocht worden dus n_0,n_1,n_2,n_3. De lijst met vergelijkingswaarden is \{r_{3,j}\}=\{1,5883,2217\}.

7531^{8100/3} = 2217 \pmod {8101} = r_{3,2} dus n_0=2.
h_1 = 7531/6^2 = 6735 \pmod {8101}

en vervolgens

6735^{8100/3^2} = 1 \pmod {8101} = r_{3,0} dus n_1=0.
6735^{8100/3^3} = 2217 \pmod {8101} = r_ {3,2} dus n_2=2.
6735/6^{18} = 6992 \pmod {8101}

en

6992^{8100/3^4} = 5883 \pmod {8101} = r_{3,1} dus n_3=1.

De congruentievergelijking is dan

n \equiv 2 + 0\times 3 + 2\times 3^2 + 1\times 3^3=47 \pmod {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.

Tot slot moeten voor p = 5\quad n_0 en n_1 berekend worden.

{7531}^{8100/5} = 5221 \pmod {8101} = r_{5,4}, dus n_0=4.
h_1 = 7531/6^4 = 7613 \pmod {8101}, dus n_1=2.

De derde congruentievergelijking is hiermee gevonden en het stelsel wordt dan

n \equiv 1 \pmod 4
n \equiv 47 \pmod {81}
n \equiv 14 \pmod {25}

De unieke oplossing van dit stelsel is :n = 6689.

Voorbeeld 3[bewerken]

Gevraagd n te berekenen waarvoor 71^n = 210\!\!\!\!\pmod {251}. De ontbinding van q-1 is 251 - 1 = 250 = 2\times 5^3 en er zijn weer alleen kleine priemfactoren.

\{r_{2,j}\} = \{1,-1\}; \{r_{5,j}\} =\{ 1,20,149,19,113 \}.

Voor p=2:

210^{250/2} = -1 \pmod {8101} = r_{2,1} dus n_0=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. Gezocht worden dus n_0,n_1,n_2.

210^{250/2} = 149 \pmod {251} = r_{5,2} dus n_0=2.
h_1 = 210/{{71}^2} = 10 \pmod {251}

en vervolgens

10^{250/5^2} = 113 \pmod {251} = r_{5,4} dus n_1=4.
h_2=10/{71}^{20} = 231 \pmod {251}

en

231^{250/125} = 149 \pmod {251} = r_{5,2} dus n_2=2.

De beide congruentievergelijkingen zijn

n \equiv 1 \pmod 2
n \equiv 72 \pmod {125}

met de 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