Discrete logaritme

In de wiskunde is de discrete logaritme voor een groep met vermenigvuldiging de inverse functie van machtsverheffen. Het is het analogon van de gewone logaritme voor de reële getallen. Onder de term 'discreet' moet hier 'geheeltallig' verstaan worden.

In een cylische groep zijn alle elementen een macht van een voortbrengend element. Die machten zijn meestal eenvoudig te berekenen. Moeilijker is het van een gegeven element te bepalen welke macht het is van het voortbrengende element en er is geen algemene methode daarvoor bekend. In de cryptografie maakt men daarvan gebruik door een zorgvuldige keuze van de groepsgrootte.

De discrete logaritme is vergelijkbaar met een array-index. Bij een gegeven index is het relatief eenvoudig het array-element te vinden. Omgekeerd is het in het algemeen lastig voor een bepaalde waarde van een element de bijbehorende index te bepalen, anders dan door het array te doorzoeken.

Definitie

Laat $G$ een groep zijn, eindig of oneindig, en $g,h\in G$ twee elementen. Een geheel getal $m$ waarvoor

$g^{m}=h$

heet een discrete logaritme van $h$ bij het grondtal $g$, genoteerd als:

$m=\,^{g}\!\log h$

of

$m=\log _{g}h$

Als $G$ een cyclische groep is, eindig of oneindig, en $g$ een voortbrenger van $G$, is de logaritme $m$ eenduiduig bepaald.

Als de groep eindig is van orde $n$, maar niet cyclisch, is een discrete logaritme eenduidig modulo $n$.

Toepassing

In de praktijk wordt de discrete logaritme toegepast bij eindige cyclische groepen. Kiest men een priemgetal voor de orde van de groep, dan is de discrete logaritme moeilijker met het Pohlig-Hellman-algoritme te berekenen.

Voorbeeld

De verzameling $G=\{1,2,\ldots 6\}$ vormt bij het rekenen modulo 7 een cyclische groep van de orde 6 voor de vermenigvuldiging als groepsbewerking. Het getal 5 is een voortbrenger van $G$, dus alle elementen zijn te schrijven als $5^{i},i\in \mathbb {N}$.

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

Neem nu $g=5$ en $h=4$. Gezocht is het getal $n={}^{5}\!\log 4$ waarvoor geldt dat $4\equiv 5^{n}{\pmod {7}}$. Uit de bovenstaande opsomming blijkt dat $n=2$. Deze methode, die eigenlijk alle mogelijkheden nagaat, maakt gebruik van brute kracht en kan alleen goed toegepast worden in eenvoudige gevallen.

Een handiger methode is het zoeken van een getal $s$ dat tegelijk te schrijven is als $s=k\cdot 7+4,k\in \mathbb {N}$ en als macht van 5. Dan geldt namelijk dat $s=5^{n}\equiv 4{\pmod {7}}$. Het getal $s=25$ voldoet, dus $n=2$.

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
• Indexcalculusalgoritme
• Pohlig-Hellman-algoritme
• Pollards lambda-algoritme
• Pollards rho-algoritme

Referenties

• (en) Alfred J. Menezes, Paul C. van Oorschot & 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.