Diskrétní logaritmus

Diskrétní logaritmus (DLOG) je problém invertování funkce v nějaké konečné multiplikativní grupě . $g^{x}$ $G$

Nejčastěji je problém diskrétního logaritmu uvažován v multiplikativní skupině zbytkového kruhu nebo konečného pole , stejně jako ve skupině bodů eliptické křivky nad konečným polem. Účinné algoritmy pro řešení problému diskrétního logaritmu jsou obecně neznámé.

Pro dané g a a se řešení x rovnice nazývá diskrétní logaritmus prvku a v základu g . V případě, že G je multiplikativní skupina zbytkového kruhu modulo m , řešení se také nazývá index čísla a vzhledem k bázi g . Je zaručena existence indexu a až základu g , pokud g je primitivní kořen modulo m . $g^{x}=a$

Prohlášení o problému

Nechť nějaká konečná multiplikativní abelovská grupa dostane rovnici $G$

g^x=a

(jeden)

Řešením problému diskrétního logaritmu je najít nějaké nezáporné celé číslo , které splňuje rovnici (1). Pokud je řešitelný, musí mít alespoň jedno přirozené řešení nepřesahující pořadí skupiny. To okamžitě poskytuje hrubý odhad složitosti algoritmu hledání řešení shora - vyčerpávající vyhledávací algoritmus by našel řešení v počtu kroků, které nejsou vyšší, než je řád dané skupiny. $X$

Nejčastěji se uvažuje případ, kdy , tedy skupina je cyklická generovaná prvkem . V tomto případě má rovnice vždy řešení. V případě libovolné grupy vyžaduje samostatné posouzení otázka řešitelnosti úlohy diskrétního logaritmu, tedy otázka existence řešení rovnice (1). $G=\langle g\rangle$ $G$

Příklad

Zvažte problém diskrétního logaritmu v kruhu reziduí modulo prvočíslo. Nechť je uvedeno srovnání

3^x\ekviv 13\pmod{17}.

Problém vyřešíme výčtem . Vypišme si tabulku všech mocnin čísla 3. Pokaždé dopočítáme zbytek po dělení 17 (například 3 3 ≡ 27 - zbytek po dělení 17 je 10).

3 1 ≡ 3	3 2 ≡ 9	3 3 ≡ 10	3 4 ≡ 13	3 5 ≡ 5	3 6 ≡ 15	3 7 ≡ 11	3 8 ≡ 16
3 9 ≡ 14	3 10 ≡ 8	3 11 ≡ 7	3 12 ≡ 4	3 13 ≡ 12	3 14 ≡ 2	3 15 ≡ 6	3 16 ≡ 1

Nyní je snadné vidět, že řešení uvažovaného srovnání je x=4 , protože 3 4 ≡13.

V praxi je modul obvykle poměrně velký a metoda výčtu je příliš pomalá, takže je potřeba rychlejších algoritmů.

Algoritmy řešení

V libovolné multiplikativní skupině

Článek J. Buchmanna, MJ Jacobsona a E. Teske je věnován řešitelnosti a řešení úlohy diskrétního logaritmu v libovolné konečné abelovské grupě. [1] Algoritmus používá tabulku skládající se z dvojic prvků a provádí násobení. Tento algoritmus je pomalý a není vhodný pro praktické použití. Pro specifické skupiny existují jejich vlastní, efektivnější, algoritmy. $O(\sqrt{|\langle g\rangle|})$ $O(\sqrt{|\langle g\rangle|})$

V kruhu zbytků modulo prime

Zvažte srovnání

a^{x}\equiv b{\pmod {p)),

(2)

kde je prvočíslo a není dělitelné beze zbytku. Jestliže je generujícím prvkem grupy , pak rovnice (2) má řešení pro libovolné . Taková čísla se také nazývají primitivní kořeny a jejich počet je , kde je Eulerova funkce . Řešení rovnice (2) lze nalézt podle vzorce: $p$ $b$ $p$ $A$ $\mathbb{Z}/p\mathbb{Z}$ $b$ $A$ $\phi (p-1)$ $\phi$

x\equiv\sum\limits_{i=1}^{p-2}(1-a^i)^{-1}b^i\pmod{p}.

Složitost výpočtu tohoto vzorce je však horší než složitost výčtu.

Následující algoritmus je složitý . $O(\sqrt{p}\cdot\log{p})$

Algoritmus

Přiřadit $H:=\left\lpatro \sqrt{p}\pravé\rpatro + 1$
Vypočítat $c= a^H\bmod{p}$
Vytvořte tabulku hodnot pro a seřaďte ji. $c^u\bmod{p}$ $1\leq u\leq H$
Vytvořte tabulku hodnot pro a seřaďte ji. $b\cdot a^v\bmod{p}$ $0\leq v\leq H$
Najděte společné prvky v tabulkách. Pro ně kde $c^u\equiv b\cdot a^v\pmod{p},$ $a^{Hu-v}\equiv b\pmod{p}.$
Vydání . $Huv$

Existuje také mnoho dalších algoritmů pro řešení problému diskrétního logaritmu v poli reziduí. Obvykle se dělí na exponenciální a subexponenciální. Polynomiální algoritmus pro řešení tohoto problému zatím neexistuje.

Algoritmy s exponenciální složitostí

Shanksův algoritmus ( algoritmus velkého a malého kroku , baby-step gigant-step )
Polyg-Hellmanův algoritmus - funguje, pokud je znám rozklad čísla na prvočinitele. Obtížnost: . Pokud jsou faktory, na které se rozkládají , dostatečně malé, pak je algoritmus velmi efektivní [2] . $p-1=\prod\limits_{i=1}^{s}q_i^{\alpha_i}$ $O(\sum\limits_{i=1}^{s}\alpha_i(\log{p}+q_i))$ $p-1$
Pollardova ρ-metoda má heuristický odhad složitosti [3] . $O(p^{\frac{1}{2)))$

Subexponenciální algoritmy

V L-notaci se výpočetní složitost těchto algoritmů odhaduje jako aritmetické operace, kde a jsou nějaké konstanty. Účinnost algoritmu do značné míry závisí na blízkosti hodnot a k 1 a 0. $L_{p}[d,c]$ $C$ $0\leq d<1$ $C$ $d$

Adlemanův algoritmus se objevil v roce 1979 [4] . Byl to první sub-exponenciální diskrétní logaritmický algoritmus. V praxi to však není příliš efektivní. v tomto algoritmu . $d=\frac{1}{2}$
Algoritmus COS navrhli v roce 1986 matematici Don Coppersmith, Andrew Odlyzko a Schroeppel [ 5 ] . V tomto algoritmu je konstanta , . V roce 1991 byl pomocí této metody proveden modulo logaritmus . V roce 1997 Weber provedl modulo diskrétní logaritmus pomocí některé verze tohoto algoritmu. Experimentálně bylo prokázáno, že pro algoritmus COS je lepší než síto číselného pole. $c=1$ $d=\frac{1}{2}$ $p \cca 10^{58}$ $p \cca 10^{85}$ $p \leq 10^{90}$
Diskrétní logaritmus pomocí číselného pole síta byl aplikován na diskrétní logaritmus později než na faktorizaci čísel. První nápady se objevily v 90. letech 20. století. Algoritmus navržený D. Gordonem v roce 1993 měl heuristickou složitost [6] , ale ukázal se být značně nepraktický. Později bylo navrženo mnoho různých vylepšení tohoto algoritmu. Ukázalo se, že se sítem je číselné pole rychlejší než COS. Pomocí této metody se získávají moderní záznamy v diskrétním logaritmu. $L_{p}\left[{\tfrac {1}{3)),3^{3/2}\right]$ $p \geq 10^{100}$

Nejlepší parametry v odhadu složitosti jsou v současnosti , [7] . $c=(92+26{\sqrt {13)))^{\frac {1}{3}}/3\cca 1{,}902$ $d=\frac{1}{3}$

U čísel zvláštního druhu lze výsledek zlepšit. V některých případech je možné sestavit algoritmus, pro který budou konstanty , . Vzhledem k tomu, že konstanta je dostatečně blízko 1, mohou takové algoritmy předběhnout algoritmus s . $c\cca 1{,}00475$ $d=\frac{2}{5}$ $C$ $d=\frac{1}{3}$

V libovolném konečném poli

Problém je uvažován v poli GF(q) , kde , je jednoduché. $q=p^{n}$ $p$

Algoritmus výpočtu indexu ( index-calculus ) je efektivní, pokud je malý. V tomto případě má heuristický odhad složitosti . $p$ $L_{p}\left[{\tfrac {1}{2}},c\right]$
Algoritmus ElGamal , který se objevil v roce 1985, je použitelný a má složitost aritmetických operací. $n=2$ $L_{p}\left[{\tfrac {1}{2}},c\right]$
Coppersmithův algoritmus pro diskrétní logaritmus v konečném poli charakteristiky 2 se stal prvním subexponenciálním diskrétním logaritmickým algoritmem s konstantou v odhadu složitosti . Tento algoritmus se objevil v roce 1984 - před vynálezem číselného síta [8] . $d=\frac{1}{3}$ $L_{p}[d,c]$

Ve skupině bodů na eliptické křivce

Uvažuje se skupina bodů eliptické křivky nad konečným polem. Tato skupina definuje operaci sčítání dvou bodů. Pak je toto . Řešením problému diskrétního logaritmu na eliptické křivce je najít takové přirozené číslo , které pro dané body a $t.t$ $\underbrace{P+\ldots+P}\limits_{m}$ $m$ $mP = A$ $P$ $A.$

Do roku 1990 neexistovaly žádné diskrétní logaritmické algoritmy, které by braly v úvahu strukturální rysy skupiny bodů na eliptické křivce. Následně Alfred Menezes , Tatsuaki Okamoto a Scott Vanstone navrhli algoritmus využívající Weilovo párování [9] . Pro eliptickou křivku definovanou přes pole tento algoritmus redukuje problém diskrétního logaritmu na podobný problém v poli . Toto snížení je však užitečné pouze v případě, že je stupeň malý. Tato podmínka je splněna hlavně pro nadsingulární eliptické křivky. V jiných případech taková redukce téměř nikdy nevede k subexponenciálním algoritmům. $GF(q)$ $GF(q^k)$ $k$

Výpočetní složitost a aplikace v kryptografii

Problém diskrétního logaritmu je jedním z hlavních problémů, na kterých je založena kryptografie s veřejným klíčem . Klasická kryptografická schémata na něm založená jsou schéma generování společného klíče Diffie-Hellman [10] , schéma elektronického podpisu ElGamal [11] [12] , kryptosystém Massey-Omura [13] pro přenos zpráv. Jejich kryptografická síla je založena na údajně vysoké výpočetní složitosti invertování exponenciální funkce. Přestože samotná exponenciální funkce se počítá poměrně efektivně, i nejmodernější algoritmy pro výpočet diskrétního logaritmu mají velmi vysokou složitost, která je srovnatelná se složitostí nejrychlejších algoritmů pro faktorování čísel .

Další možností pro efektivní řešení problému výpočtu diskrétního logaritmu souvisí s kvantovým počítáním . Teoreticky bylo dokázáno, že pomocí Shorova algoritmu lze vypočítat diskrétní logaritmus v polynomiálním čase [14] [15] [16] . V každém případě, pokud je implementován polynomiální algoritmus pro výpočet diskrétního logaritmu, bude to znamenat, že kryptosystémy na něm založené jsou pro dlouhodobou ochranu dat prakticky nevhodné. Je zvažována řada nápadů na vytvoření nových algoritmů veřejného klíče .

Poznámky

↑ Buchmann J. , Jacobson MJ, Teske E. K některým výpočetním problémům v konečných abelovských grupách // Matematika počítání : deník. - 1997. - Sv. 66 . - S. 1663-1687 . - doi : 10.1090/S0025-5718-97-00880-6 .
↑ S. Pohlig, M. Hellman. Vylepšený algoritmus pro výpočet logaritmů a jeho kryptografický význam (správně) // IEEE Transactions on Information Theory. - 1978. - Leden ( ročník 24 , číslo 1 ). - S. 106-110 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1978.1055817 . Archivováno z originálu 21. června 2018.
↑ JM Pollard. Metody Monte Carlo pro výpočet indexu (mod p) // Matematika počítání. - 1978. - Leden ( roč. 32 , číslo 143 ). - S. 918-924 . - doi : 10.1090/S0025-5718-1978-0491431-9 .
↑ L. Adleman. Subexponenciální algoritmus pro problém diskrétního logaritmu s aplikacemi pro kryptografii // 20. výroční symposium o základech informatiky. - 1979. - Říjen. - S. 55-60 . - doi : 10.1109/SFCS.1979.2 . Archivováno z originálu 10. května 2017.
↑ Don Coppersmith, Andrew M. Odlzyko, Richard Schroeppel. Diskrétní logaritmy inGF(p) (anglicky) // Algorithmica. - 1986. - Listopad ( vol. 1 , iss. 1-4 ). - str. 1-15 . - doi : 10.1007/BF01840433 . Archivováno z originálu 13. dubna 2018.
↑ Daniel M. Gordon. Diskrétní logaritmy v GF(p) pomocí síta číselných polí // SIAM Journal on Discrete Mathematics. - 1993. - T. 6 , no. 1 . - S. 124-138 . - doi : 10.1137/0406010 .
↑ Don Coppersmith. Úpravy číselného pole Sieve // Journal of Cryptology. - 1993. - Sv. 6 , iss. 3 . - S. 169-180 . - doi : 10.1007/BF00198464 . Archivováno z originálu 19. června 2018.
↑ D. Měděník. Rychlé vyhodnocení logaritmů v polích dvou charakteristik // IEEE Transactions on Information Theory. - 1984. - Červenec ( díl 30 , číslo 4 ). - S. 587-594 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1984.1056941 .
↑ AJ Menezes, T. Okamoto, SA Vanstone. Redukce logaritmů eliptických křivek na logaritmy v konečném poli // IEEE Transactions on Information Theory. — 1993-09-01. - T. 39 , č.p. 5 . - S. 1639-1646 . — ISSN 0018-9448 . - doi : 10.1109/18.259647 . Archivováno z originálu 2. července 2017.
↑ Diffie, Hellman, 1976 .
↑ Elgamal, 1984 .
↑ Elgamal, 1985 .
↑ James L. Massey, Jimmy K. Omura. Způsob a zařízení pro zachování soukromí digitálních zpráv přenášených veřejným přenosem (28. ledna 1986). Archivováno z originálu 20. října 2016. (neurčitý)
↑ Shor, 1994 .
↑ Shor PW Polynomiální-časové algoritmy pro prvočinitele a diskrétní logaritmy na kvantovém počítači // Základy informatiky: Publikace z konference. - 1997. - S. 1484-1509.
↑ CompuTerra Online #224 - Kvantové počítače a kvantové výpočty ... Rozhovor s kandidátem fyzikálních a matematických věd, odborníkem na teorii algoritmů Michailem Vjalym (Výpočetní centrum Ruské akademie věd)

Odkazy

Diffie W. , Hellman M. E. Nové směry v kryptografii // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1976. - Sv. 22, Iss. 6. - S. 644-654. — ISSN 0018-9448 ; 1557-9654 – doi:10.1109/TIT.1976.1055638
Elgamal T. Kryptosystém s veřejným klíčem a schéma podpisu založené na diskrétních logaritmech, kryptosystém s veřejným klíčem a schéma podpisu založené na diskrétních logaritmech // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1985. - Sv. 31, Iss. 4. - S. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
Elgamal T. Kryptosystém s veřejným klíčem a schéma podpisu založené na diskrétních logaritmech, kryptosystém s veřejným klíčem a schéma podpisu založené na diskrétních logaritmech // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1985. - Sv. 31, Iss. 4. - S. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring (anglicky) // Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on - IEEE , 1994. - S. 124–134. - ISBN 0-8186-6580-7 - doi:10.1109/SFCS.1994.365700
Vasilenko O. N. Číselné teoretické algoritmy v kryptografii . - Moskva: MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 . Archivováno 27. ledna 2007 na Wayback Machine
Koblitz N. Kurz teorie čísel a kryptografie. - Moskva: TVPb, 2001. - 254 s. — ISBN 5-85484-014-6 .
Odlyzko AM Diskrétní logaritmy v konečných polích a jejich kryptografický význam // LNCS . - 1984. - T. 209 . - S. 224-316 .
Yu. V. Nesterenko. Kapitola 4.8. Diskrétní logaritmus // Úvod do kryptografie / Ed. V. V. Jaščenko. - Petr, 2001. - 288 s. - ISBN 5-318-00443-1 .
Přehled metod diskrétního logaritmu
Nechaev V.I. K otázce složitosti deterministického algoritmu pro diskrétní logaritmus // Matematické poznámky . - 1994. - únor ( ročník 55 , číslo 2 ). - S. 91-101 .

Slovníky a encyklopedie	Velký Rus