Discrete Logaritme Probleem

Het Discrete Logaritme Probleem (DLP) is gedefinieerd in elke cyclische groep.

Uitleg

Laat G een cyclische groep zijn. Laat g $\in$ G voortbrenger zijn van G en h $\in$ G.
Het DLP is nu als volgt: $g^n$ = h, bepaal n.

Ook als de orde van G oneindig groot is worden alle elementen van G voortgebracht als machten van de voortbrenger g.
Denk bijvoorbeeld aan de verzameling $\mathbb{Z}$.
$\mathbb{Z}$* = $\mathbb{Z}$\{0}. Het getal 1 brengt met de operatie optellen de hele groep voort.

In de praktijk wordt bij het DLP gebruikgemaakt van eindige cyclische groepen. Met het kiezen van een priemgetal voor de orde van de groep is het DLP vanwege het Pohlig-Hellman algoritme moeilijker op te lossen.

Voorbeeld

G = $\mathbb{F}$$_7$$^*$
g = 5 is een mogelijke voortbrenger van $\mathbb{F}$$_7$$^*$, dus alle elementen zijn te schrijven als $5^{i}$, i $\in$ $\mathbb{N}$
|$\mathbb{F}$$_7$$^*$| = 6, de orde is dus geen priemgetal.

$\begin{matrix} 5^1&=&5&&&\equiv&5&\bmod 7\\ 5^2&=&25&=&3\cdot7 + 4&\equiv&4&\bmod 7\\ 5^3&=&125&=&17\cdot7 + 6&\equiv&6&\bmod 7\\ 5^4&=&625&=&89\cdot7 + 2&\equiv&2&\bmod 7\\ 5^5&=&3125&=&446\cdot7 + 3&\equiv&3&\bmod 7\\ 5^6&=&15625&=&2232\cdot7 + 1&\equiv&1&\bmod 7 \end{matrix}$

$5^{p-1}$$\equiv$ 1 ( mod 7). De orde van $\mathbb{F}$$_7$$^*$ is (p - 1)

Voor g = 5 en h = 4 geldt voor n dus n = $^5\log 4 (\bmod 7)$.

Zoek naar een getal dat tegelijk te schrijven is al k $\cdot$ 7 + 4 (k $\in$ $\mathbb{N}$) en als macht van 5.
Omdat p klein gekozen is, is het probleem hier gemakkelijk op te lossen. n = 2 voldoet.

Bij de keuze van een groter getal voor h zijn er verschillende mogelijkheden om de waarde van n te vinden, onder meer door gebruik te maken van de rekenregels voor logaritmen.

Voor g = 5 en h = 1953125 geldt n = $^5$log(1953125) ( mod 7)

• Omdat 1953125 = 279017$\cdot$ 7 + 6 en dus 1953125 $\equiv$ 6 ( mod 7), geldt n = $^5$log6 ( mod 7). n = 3 voldoet.
• Omdat 1953125 = 625 $\cdot$ 3125 geldt n = $^5$log(625 $\cdot$ 3125 ) ( mod 7) $\equiv$ $^5$log(2 $\cdot$ 3) ( mod 7) = $^5$log6 ( mod 7) = zie bovenstaand tabelletje = 3
• Ook geldt: n = $^5$log(625 $\cdot$ 3125 ) ( mod 7) = $^5$log($5^4$ $\cdot$ $5^5$) ( mod 7) = $^5$log$5^4$( mod 7) + $^5$log$5^5$( mod 7)= 4 + 5 = 9 $\equiv$ 3

Het Diffie-Hellman protocol en het Elgamal-encryptiesysteem maken gebruik van producten van machten, waarbij de afzonderlijke exponenten als geheime code verborgen kunnen blijven.

Bij keuze van een grote orde van de groep kan het probleem moeilijk opgelost worden door het maken van tabellen omdat er daarvoor veel te veel mogelijkheden zijn. De onderstaande methoden bieden mogelijkheden, te gebruiken in bijvoorbeeld $\mathbb{Z}$$_p$$^*$, $\mathbb{F}$$_q$$^*$ en $\mathbb{F}_{2^m}$$^*$

Zie ook

• Baby-steps giant-steps algoritme
• Index calculus algoritme
• Pohlig-Hellman algoritme
• Pollards lambda-algoritme
• Pollards rho-algoritme

Referenties

• (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.