Pohlig-Hellman-algoritme

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 ${𝔽}_q^{*}$ van een eindig lichaam ${𝔽}_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

De werking van het algoritme wordt verklaard voor de multiplicatieve groep $G={𝔽}_q^{*}$ van het eindige lichaam ${𝔽}_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(\mathrm{mod}q)$.

Het algoritme bepaalt voor elke priemfactor $p_j$ in de ontbinding:

$q-1={p_1}^{e_1}{p_2}^{e_2}\dots {p_i}^{e_i}$

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

Deelalgoritme

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+p{n}_1+\dots +p^{m-1}{n}_{m-1}(\mathrm{mod}{p}^m)$

en bepaalt in vergelijkbare stappen successievelijk de getallen $n_j$ .

Vooraf worden voor $j=0,1,\dots ,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}(\mathrm{mod}q)=1$, dus, omdat $g^n=h(\mathrm{mod}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_{2}p+\dots +n_{m-1}{p}^{m-2})(q-1)}=g^{\frac{n_0(q-1)}{p}}=r_{p,n_0}(\mathrm{mod}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,\dots$ 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_1{g}^{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{(p{n}_1+p^2{n}_2+\dots +p^{m-1}{n}_{m-1})(q-1)}{p^2}}=g^{\frac{(n_1+p{n}_2+\dots +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,\dots ,m-1.$ Om $n_k$ te vinden, stelt men

$h_k=\frac{h}{g^{n_0+p{n}_1+\dots +p^{k-1}{n}_{k-1}}}$.

De discrete logaritme $n={\log }_g(h)$ wordt dan

$n\equiv n_0+p{n}_1+\dots +p^{k-1}{n}_{k-1}(\mathrm{mod}{p}^i)$.

Hieruit volgt

$h_k=g^{n-n_0-n_1-\dots -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+p{n}_1+\dots +p^{i-1}{n}_{i-1}(\mathrm{mod}{p}^i)$.

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

Voorbeelden

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

Gevraagd $n$ te berekenen waarvoor $2^n\equiv 28(\mathrm{mod}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+p{n}_1$ gezocht.

Voor de beide priemdelers zijn de lijsten $\{r_{2,j}\}=\{1,36\}$ en $\{r_{3,j}\}=\{1,26,10\}$, want $2^0(\mathrm{mod}37)=1,2^{18}(\mathrm{mod}37)=36$, etc.

Stel $h=2^n=28(\mathrm{mod}37)$ en bereken ${28}^{36/2}=1(\mathrm{mod}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(\mathrm{mod}37)=r_{2,n_1}$. Hieruit volgt $n_1=1$. Voor $p=2$ wordt de congruentie dus $n=0+2\times 1=2(\mathrm{mod}4)$.

Voor $p=3$ berekent men ${28}^{36/3}=26(\mathrm{mod}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(\mathrm{mod}37)=r_{3,n_1}$. Hieruit volgt $n_1=2$. Voor $p=3$ wordt de congruentie dus $n=1+3\times 2=7(\mathrm{mod}9)$. Het stelsel congruentievergelijking dat opgelost kan worden met de Chinese reststelling, is dus

$n\equiv 2(\mathrm{mod}4)$

$n\equiv 7(\mathrm{mod}9)$

en heeft als unieke oplossing $n=34$.

Voorbeeld 2

Gevraagd $n$ te berekenen waarvoor $6^n=7531(\mathrm{mod}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(\mathrm{mod}8101)=r_{2,1}$ dus $n_0=1$.

$h_1=7531/6=8006(\mathrm{mod}8101)$

en

$8006^{8100/2^2}=1(\mathrm{mod}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^2{n}_2+3^3{n}_3(\mathrm{mod}{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(\mathrm{mod}8101)=r_{3,2}$ dus $n_0=2$.

$h_1=7531/6^2=6735(\mathrm{mod}8101)$

en vervolgens

$6735^{8100/3^2}=1(\mathrm{mod}8101)=r_{3,0}$ dus $n_1=0$.

$6735^{8100/3^3}=2217(\mathrm{mod}8101)=r_{3,2}$ dus $n_2=2$.

$6735/6^{18}=6992(\mathrm{mod}8101)$

en

$6992^{8100/3^4}=5883(\mathrm{mod}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(\mathrm{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+p{n}_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.

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

${7531}^{8100/5}=5221(\mathrm{mod}8101)=r_{5,4}$, dus $n_0=4$.

$h_1=7531/6^4=7613(\mathrm{mod}8101)$, dus $n_1=2$.

De derde congruentievergelijking is hiermee gevonden en het stelsel wordt dan

$n\equiv 1(\mathrm{mod}4)$

$n\equiv 47(\mathrm{mod}81)$

$n\equiv 14(\mathrm{mod}25)$

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

Voorbeeld 3

Gevraagd $n$ te berekenen waarvoor $71^n=210(\mathrm{mod}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}\equiv 250\equiv -1(\mathrm{mod}251)=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/5}=149(\mathrm{mod}251)=r_{5,2}$ dus $n_0=2$.

$h_1=210/{71}^2=10(\mathrm{mod}251)$

en vervolgens

$10^{250/5^2}=113(\mathrm{mod}251)=r_{5,4}$ dus $n_1=4$.

$h_2=10/{71}^{20}=231(\mathrm{mod}251)$

en

$231^{250/125}=149(\mathrm{mod}251)=r_{5,2}$ dus $n_2=2$.

De beide congruentievergelijkingen zijn

$n\equiv 1(\mathrm{mod}2)$

$n\equiv 72(\mathrm{mod}125)$

met de unieke oplossing $n=197$.

Zie ook

• Baby-steps giant-steps algoritme
• Index calculus algoritme
• Pollards lambda-algoritme
• Pollards 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