Diskrétní logaritmus

Nechť $p,g,k,Y$ jsou přirozená čísla, pro něž platí $Y\equiv g^{k}{\pmod {p}}$ . Potom každé číslo $k$ odpovídající uvedené rovnici nazveme diskrétní logaritmus o základu $g$ z $Y$ vzhledem k modulu $p$ . Tato definice nedefinuje číslo $k$ jednoznačně, proto se někdy upravuje tak, že ze všech možných diskrétních logaritmů ve smyslu předchozí definice se vybere ten nejmenší.

Obecně se nemusí jednat přímo o přirozená čísla modulo $m$ , diskrétní logaritmus je zobecnění klasického logaritmu pro konečné cyklické grupy.

Praktické užití

Zatímco spočíst $Y$ ze znalosti $k,p,g$ je snadné, spočíst diskrétní logaritmus $k$ ze znalosti $Y,p,g$ je velmi obtížné. To předurčuje tento problém k využití v asymetrické kryptografii. Ale standard NIST redukuje grupu pro $p$ (například 1024 bitů) na podgrupu $q$ (160 bitů).^[1]

Reference

↑ http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf - Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography

Externí odkazy

Diskrétní logaritmus v encyklopedii MathWorld (anglicky)
https://web.archive.org/web/20121029133807/http://www.wimp.com/howencryption/

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.

[1] ttp://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf - Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography

[1]