Discrete logaritme

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

In een cyclische 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 ${\displaystyle G}$ een groep zijn, eindig of oneindig, en ${\displaystyle g,h\in G}$ twee elementen. Een geheel getal ${\displaystyle m}$ waarvoor

${\displaystyle g^{m}=h}$

heet een discrete logaritme van ${\displaystyle h}$ bij het grondtal ${\displaystyle g}$, genoteerd als:

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

of

${\displaystyle m=\log _{g}h}$

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

Als de groep eindig is van orde ${\displaystyle n}$, maar niet cyclisch, is een discrete logaritme eenduidig modulo ${\displaystyle 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.

Voorbeelden

De verzameling ${\displaystyle 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 ${\displaystyle G}$, dus alle elementen zijn te schrijven als ${\displaystyle 5^{i},i\in \mathbb {N} }$.

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

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

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

Het Diffie-Hellman-sleuteluitwisselingsprotocol 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 worden opgelost door het maken van tabellen omdat er daarvoor veel te veel mogelijkheden zijn. De volgende methoden bieden mogelijkheden, te gebruiken in bijvoorbeeld ${\displaystyle \mathbb {Z} _{p}^{*}}$, ${\displaystyle \mathbb {F} _{q}^{*}}$ en ${\displaystyle \mathbb {F} _{2^{m}}^{*}}$

• Baby-steps giant-steps-algoritme
• Indexcalculusalgoritme
• Pohlig-Hellman-algoritme
• Pollards lambda-algoritme
• Pollards rho-algoritme

Literatuur

• AJ Menezes, PC van Oorschot en SA Vanstone. Handbook of applied cryptography, 2001.
• DJ Bernstein. Generic attacks and index calculus. voor de Universiteit van Illinois
• N Koblitz. A Course in Elementary Number Theory and Cryptography, 1994. Springer. ISBN 978-0387942933