Pollards rho-algoritme

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Pollards rho-algoritme is een algoritme dat door John Pollard in 1978 beschreven werd om het discreet logaritme zoals dat is gedefinieerd in een cyclische groep te berekenen. Het grote voordeel ten opzichte van het Baby-steps giant-steps-algoritme is dat voor deze methode geen opslagruimte nodig is.

Inleiding[bewerken]

Laat G een groep zijn, met orde p, en G cyclisch. Laat g \in G voortbrenger zijn van G en h \in G. Het discreet logaritme luidt nu als volgt: Bepaal de oplossing van g^{n}=h.

Pollards rho-algoritme definieert eerst een pseudowillekeurige reeks (opeenvolging) van elementen van een groep en kijkt dan naar een cyclus (kringloop) die in deze reeks voorkomt.

Deze groep wordt verdeeld in drie deelverzamelingen S1, S2, S3 van ongeveer gelijke grootte, d.m.v. een eenvoudig te testen eigenschap.

Vervolgens wordt er een functie gedefinieerd die de groep afbeeldt op zichzelf waardoor de elementen op een andere manier worden gerangschikt. Verder wordt f(x) zo gekozen dat elk opeenvolgend element een functie is van alleen het voorgaande element. Eigenlijk worden twee reeksen elementen gemaakt waarbij de tweede reeks twee keer zo snel de groepselementen doorloopt als de eerste reeks. We zoeken nu totdat we twee dezelfde elementen hebben gevonden. Als we een element vinden dat voor de tweede keer voorkomt, is elk daaropvolgend element een herhaling van elementen eerder in de reeks.

De verjaardagenparadox zegt nu dat we zo’n cyclus zullen vinden nadat we slechts O(√p) elementen van de reeks hebben berekend. (In het algemeen geldt dat als er volkomen willekeurig elementen worden geselecteerd uit een verzameling, met grootte n dan hoeft men maar O(√p) elementen van deze verzameling te selecteren om een kans van ½ te hebben om hetzelfde element twee keer te trekken.)

Algoritme[bewerken]

G is een groep met orde p, voortbrenger g, en h\in G en x\in \mathbb{Z} Gegeven het volgende discrete logaritme: g^n= h Bepaal n

G kan worden verdeeld in drie deelverzamelingen (geen subgroepen) met behulp van een functie k die aan de elementen van G een waarde toekent, bijvoorbeeld k: G→ {1,2,3} De groep kan dan als volgt in drie groepen worden verdeeld

x\in S_1 als k(x)=1
x\in S_2 als k(x)=2
x\in S_3 als k(x)=3

Vervolgens worden deze elementen x_0, x_1, x_2, .... gerangschikt met behulp van onderstaande functie:

x_0 = 1 en
[x_{i+1}=f(x_i)]=\left\{\begin{array}{lcl}
h \cdot x_i&&x_i \in S_1  \\
x_i^2&\mbox{als }& x_i \in S_2 \\
 g \cdot x_i&&x_i \in S_3 
\end{array}\right.

Waarbij geldt: a_0 =0,b_0 =0, i\geq0

a_{i+1}=\left\{\begin{array}{lcl}
a_i&&x_i \in S_1 \\
2a_i \bmod p&\mbox{als }&x_i \in S_2 \\
a_i+1\bmod p&&x_i \in S_3 
\end{array}\right.
b_{i+1}=\left\{\begin{array}{lcl}
 b_i+1\bmod p &&x_i \in S_1 \\
2b_i \bmod p&\mbox{als }&x_i \in S_2\\
b_i+1&&x_i \in S_3 
\end{array}\right.

De elementen x_i zijn nu als volgt gedefinieerd: x_i = g^{a_i + b_in}

We zoeken nu totdat we twee dezelfde elementen x_i=g^{a_i+b_in} = x_j=g^{a_j+b_jn} hebben gevonden.

Voorbeeld[bewerken]

Het element 5 is een voortbrenger van de subgroep G van \mathbb{Z}_{1000003}^* met orde 1 000 002 Gegeven het volgende discrete logaritme: 5^n (mod 1 000 003) = 262 682. Bepaal n

De groep G wordt in drie deelverzamelingen verdeeld met behulp van de volgende criteria:

x\in S_1 als x \equiv 1 (mod 3)
x\in S_2 als x \equiv 2 (mod 3)
x\in S_3 als x \equiv 0 (mod 3)

Volgens bovenstaande definitie worden de elementen van de groep nu als volgt gerangschikt

x_0 = 1 en
[x_{i+1}=f(x_i)]=\left\{\begin{array}{lcl}
5^n \cdot x_i&&x_i \equiv 1 \bmod 3 \\
 x_i^2&\mbox{als }&x_i \equiv 2 \bmod 3 \\
5 \cdot x_i&&x_i \equiv 0 \bmod 3
\end{array}\right.

We verkrijgen zo onderstaande reeks:

x_1 =  5^nx_0 = 5^n ≡ 262682 (mod 1000003) → 262682 ≡ 2 mod 3
x_2 = x_1^2= 5^{2n} ≡ (262682)^2 (mod 1000003) = 626121 (mod 1000003) → 626121 ≡ 0 mod 3
x_3 = 5x_2 = 5^{2n+1} ≡ (5 \cdot 626121) (mod 1000003) = 130596 (mod 1000003) → 130596 ≡ 0 mod 3
x_4 = 5x_3 = 5^{2n+2} ≡ (5 \cdot130596) (mod 1000003) = 652980 (mod 1000003)→652980 ≡ 0 mod 3
x_5 = 5x_4 = 5^{2n+3} ≡ (5  \cdot 652980) (mod 1000003) = 264891 mod 1000003) → 264891 ≡ 0 mod 3
x_6= 5x_5=5^{2n+4} ≡ (5  \cdot 264891) (mod 1000003) = 324452 (mod 1000003) → 324452 ≡ 2 mod 3
x_7 = (x_6)^2 = (5^{2n+4})^2 = 5^ {4n+8} ≡ (324452)^2 (mod 1000003) = 784500 (mod 1000003) → 784500 ≡ 0 mod 3
.
.
x_{1785} = 5 ^{(249847n+759123)} ≡ 555013 (mod 1000003)
.
.
x_{3570} = 5  ^{(388795n+632781)}  ≡ 555013 (mod 1000003)

Pollard rho cycle.jpg

Uit deze laatste twee volgt: 249847 n + 759123 ≡ 388795 n + 632781 (mod 1000002)

138 948 n ≡ 126 342 (mod 1 000 002) Omdat 138 948 en 1 000 002 niet relatief priem zijn (de grootste gemene deler (138948,1000002) = 6), heeft 138 948 geen inverse. We bekijken daarom de vergelijkbare vergelijking voor n (modulo 166 667)

23158 n = 21057 (mod 166667)

n = 21057 . 23158^{-1} Met behulp van het uitgebreid algoritme van Euclides berekenen we de inverse van 23158 (mod 166667):

Ggd (23158 , 166667) = 1 1 = (4133 .166667) – (29745 . 23158), dus 1= -29745 . 23158 ≡ 1 (mod 166667) -29745 ≡ 136922 (mod 166667) De inverse van 23158 is dus 136922 (mod 166667) n = 21057 . 23158^{-1} (mod 166667)

Vervolgens bekijken we welke van de 6 gevonden waarden voor n voldoet: n = 21057 . (136922 + k . 166667) met k = 0, 1, 2, 3, 4, 5

n = 21057 . 136922 mod 1000002 ≡ 160788 of n = 21057 . 303589 mod 1000002 ≡ 660789 of n = 21057 . 470256 mod 1000002 ≡ 160788 of n = 21057 . 636923 mod 1000002 ≡ 660789 of n = 21057 . 803590 mod 1000002 ≡160788 of n = 21057 . 970257 mod 1000002 ≡ 660789

5^{160789} mod 1000003 = 686596 5^{660789} mod 1000003 = 262682 Dus n = 660789 is het getal dat we zochten.

Zie ook[bewerken]

Referenties[bewerken]

  • (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.
  • (en) J. M. Pollard, Monte Carlo methods for index computation mod p, Mathematics of Computation, Volume 32, Issue 143 (jul.1978), 918-924.
  • (en) D. Hankerson and Alfred J. Menezes, The Discrete Logarithm Problem, Auburn University and University of waterloo, Jun. 17, 2004.