Diskret logaritme

Diskret logaritme (DLOG) er problemet med at invertere en funktion i en eller anden finit multiplikativ gruppe . $g^{x}$ $G$

Oftest betragtes det diskrete logaritmeproblem i den multiplikative gruppe af en restring eller et endeligt felt , såvel som i gruppen af punkter i en elliptisk kurve over et endeligt felt. Effektive algoritmer til løsning af det diskrete logaritmeproblem er generelt ukendte.

For givet g og a kaldes løsningen x af ligningen den diskrete logaritme af elementet a i grundtallet g . I det tilfælde, hvor G er den multiplikative gruppe af restringen modulo m , kaldes løsningen også indekset for tallet a med hensyn til grundtallet g . Et indeks af a til basis g er garanteret at eksistere, hvis g er en primitiv rod modulo m . $g^{x}=a$

Udtalelse af problemet

Lad en eller anden finit multiplikativ abelsk gruppe få ligningen $G$

g^x=a

(en)

Løsningen på det diskrete logaritmeproblem er at finde et ikke-negativt heltal , der opfylder ligning (1). Hvis det er opløseligt, skal det have mindst én naturlig løsning, der ikke overstiger rækkefølgen af gruppen. Dette giver umiddelbart et groft skøn over kompleksiteten af løsningssøgningsalgoritmen ovenfra - den udtømmende søgealgoritme ville finde en løsning i et antal trin, der ikke er højere end rækkefølgen af den givne gruppe. $x$

Oftest betragtes tilfældet, når , dvs. gruppen er cyklisk genereret af elementet . I dette tilfælde har ligningen altid en løsning. I tilfælde af en arbitrær gruppe kræver spørgsmålet om løseligheden af det diskrete logaritmeproblem, det vil sige spørgsmålet om eksistensen af løsninger til ligning (1), separat overvejelse. $G=\langle g\rangle$ $g$

Eksempel

Overvej problemet med diskret logaritme i ringen af rester modulo et primtal. Lad sammenligning gives

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

Vi løser problemet ved opregning . Lad os skrive en tabel over alle potenser af tallet 3. Hver gang beregner vi resten af divisionen med 17 (for eksempel 3 3 ≡ 27 - resten af divisionen med 17 er 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

Nu er det let at se, at løsningen af den betragtede sammenligning er x=4 , da 3 4 ≡13.

I praksis er modulet normalt ret stort, og opregningsmetoden er for langsom, så der er behov for hurtigere algoritmer.

Løsningsalgoritmer

I en vilkårlig multiplikativ gruppe

Artiklen af J. Buchmann, MJ Jacobson og E. Teske er viet til løsbarheden og løsningen af det diskrete logaritmeproblem i en vilkårlig finit Abelsk gruppe. [1] Algoritmen bruger en tabel bestående af par af elementer og udfører multiplikationer. Denne algoritme er langsom og ikke egnet til praktisk brug. For specifikke grupper er der deres egne, mere effektive algoritmer. $O(\sqrt{|\langle g\rangle|})$ $O(\sqrt{|\langle g\rangle|})$

I ringen af rester modulo prime

Overvej sammenligningen

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

(2)

hvor er et primtal og er ikke deleligt med uden en rest. Hvis er et genererende element i gruppen , så har ligning (2) en løsning for enhver . Sådanne tal kaldes også primitive rødder , og deres tal er , hvor er Euler-funktionen . Løsningen af ligning (2) kan findes ved formlen: $s$ $b$ $s$ $-en$ $\mathbb{Z}/p\mathbb{Z}$ $b$ $-en$ $\phi (p-1)$ $\phi$

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

Kompleksiteten ved at beregne denne formel er dog værre end kompleksiteten af opregning.

Følgende algoritme har kompleksitet . $O(\sqrt{p}\cdot\log{p})$

Algoritme

Tildel $H:=\venstre\lgulv \sqrt{p}\højre\rgulv + 1$
Beregn $c= a^H\bmod{p}$
Opret en værditabel for og sorter den. $c^u\bmod{p}$ $1\leq u\leq H$
Opret en værditabel for og sorter den. $b\cdot a^v\bmod{p}$ $0\leq v\leq H$
Find almindelige elementer i tabeller. For dem hvor $c^u\equiv b\cdot a^v\pmod{p},$ $a^{Hu-v}\equiv b\pmod{p}.$
Udstedelse . $Huv$

Der er også mange andre algoritmer til at løse det diskrete logaritmeproblem i restfeltet. De er normalt opdelt i eksponentielle og subeksponentielle. En polynomiel algoritme til at løse dette problem eksisterer endnu ikke.

Algoritmer med eksponentiel kompleksitet

Shanks' algoritme ( stor og lille trin algoritme , baby-step kæmpe-trin )
Polyg-Hellman algoritme - virker, hvis dekomponeringen af et tal til primfaktorer er kendt. Sværhedsgrad :. Hvis de faktorer, som dekomponeres i, er små nok, så er algoritmen meget effektiv [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$
Pollards ρ-metode har et heuristisk kompleksitetsestimat [3] . $O(p^{\frac{1}{2)))$

Subeksponentielle algoritmer

I L-notation estimeres beregningskompleksiteten af disse algoritmer som aritmetiske operationer, hvor og er nogle konstanter. Algoritmens effektivitet afhænger i høj grad af værdiernes nærhed og til henholdsvis 1 og 0. $L_{p}[d,c]$ $c$ $0\leq d<1$ $c$ $d$

Adlemans algoritme dukkede op i 1979 [4] . Det var den første sub-eksponentielle diskrete logaritmealgoritme. I praksis er det dog ikke særlig effektivt. i denne algoritme . $d=\frac{1}{2}$
COS-algoritmen blev foreslået i 1986 af matematikerne Don Coppersmith, Andrew Odlyzko og Schroeppel [ 5 ] . I denne algoritme er konstanten , . I 1991 blev modulo-logaritmen udført ved hjælp af denne metode . I 1997 lavede Weber den modulo diskrete logaritme ved hjælp af en eller anden version af denne algoritme. Det er eksperimentelt blevet vist , at COS-algoritmen er bedre end talfeltsigten. $c=1$ $d=\frac{1}{2}$ $p \ca. 10^{58}$ $p \ca. 10^{85}$ $p \leq 10^{90}$
Diskret logaritme ved hjælp af en talfeltsigte blev anvendt til diskret logaritme senere end til faktorisering af tal. De første ideer dukkede op i 1990'erne. Algoritmen foreslået af D. Gordon i 1993 havde heuristisk kompleksitet [6] , men viste sig at være ret upraktisk. Senere blev der foreslået mange forskellige forbedringer af denne algoritme. Det har vist sig, at med en si er nummerfeltet hurtigere end COS. Moderne optegnelser i diskret logaritme opnås ved hjælp af denne metode. $L_{p}\left[{\tfrac {1}{3)),3^{3/2}\right]$ $p \geq 10^{100}$

De bedste parametre i estimeringen af kompleksitet i øjeblikket er , [7] . $c=(92+26{\sqrt {13)))^{\frac {1}{3}}/3\approx 1{,}902$ $d=\frac{1}{3}$

For numre af en særlig art kan resultatet forbedres. I nogle tilfælde er det muligt at konstruere en algoritme, for hvilken konstanterne vil være , . På grund af det faktum, at konstanten er tæt nok på 1, kan sådanne algoritmer overhale algoritmen med . $c\approx 1{,}00475$ $d=\frac{2}{5}$ $c$ $d=\frac{1}{3}$

I et vilkårligt begrænset felt

Problemet betragtes i feltet GF(q) , hvor , er simpelt. $q=p^{n}$ $s$

Indeksberegningsalgoritmen ( index-calculus ) er effektiv, hvis den er lille. I dette tilfælde har den et heuristisk kompleksitetsestimat . $s$ $L_{p}\venstre[{\tfrac {1}{2}},c\right]$
ElGamal-algoritmen , som dukkede op i 1985, er anvendelig til og har kompleksiteten af aritmetiske operationer. $n=2$ $L_{p}\venstre[{\tfrac {1}{2}},c\right]$
Coppersmiths algoritme for diskret logaritme i et endeligt felt med karakteristik 2 blev den første subeksponentielle diskrete logaritmealgoritme med en konstant i kompleksitetsestimatet . Denne algoritme dukkede op i 1984 - før opfindelsen af talfeltsigten [8] . $d=\frac{1}{3}$ $L_{p}[d,c]$

I en gruppe af punkter på en elliptisk kurve

En gruppe af punkter i en elliptisk kurve over et begrænset felt betragtes. Denne gruppe definerer operationen med at tilføje to punkter. Så er dette . Løsningen på problemet med diskret logaritme på en elliptisk kurve er at finde et sådant naturligt tal , at for givne punkter og $smp$ $\underbrace{P+\ldots+P}\limits_{m}$ $m$ $mP=A$ $P$ $EN.$

Indtil 1990 var der ingen diskrete logaritmealgoritmer, der tog højde for de strukturelle træk ved en gruppe punkter på en elliptisk kurve. Efterfølgende foreslog Alfred Menezes , Tatsuaki Okamoto og Scott Vanstone en algoritme ved hjælp af Weil-parring [9] . For en elliptisk kurve defineret over et felt , reducerer denne algoritme det diskrete logaritmeproblem til et lignende problem i et felt . Denne reduktion er dog kun nyttig, hvis graden er lille. Denne betingelse er opfyldt hovedsageligt for supersingulære elliptiske kurver. I andre tilfælde fører en sådan reduktion næsten aldrig til subeksponentielle algoritmer. $GF(q)$ $GF(q^k)$ $k$

Beregningsmæssig kompleksitet og applikationer i kryptografi

Det diskrete logaritmeproblem er et af hovedproblemerne, som offentlig nøglekryptografi er baseret på . De klassiske kryptografiske skemaer baseret på det er Diffie-Hellman fælles nøglegenereringsskema [10] , ElGamal elektroniske signaturskema [11] [12] , Massey-Omura kryptosystem [13] til meddelelsestransmission. Deres kryptografiske styrke er baseret på den formodede høje beregningsmæssige kompleksitet ved at invertere den eksponentielle funktion. Selvom selve eksponentialfunktionen beregnes ret effektivt, har selv de mest moderne algoritmer til beregning af den diskrete logaritme en meget høj kompleksitet, som kan sammenlignes med kompleksiteten af de hurtigste algoritmer til faktorisering af tal .

En anden mulighed for effektivt at løse problemet med at beregne den diskrete logaritme er relateret til kvanteberegning . Det er blevet teoretisk bevist, at ved brug af Shor 's algoritme kan den diskrete logaritme beregnes i polynomisk tid [14] [15] [16] . Under alle omstændigheder, hvis en polynomial algoritme til beregning af den diskrete logaritme er implementeret, vil dette betyde, at kryptosystemer baseret på den praktisk talt er uegnede til langsigtet databeskyttelse. En række ideer til at skabe nye offentlige nøglealgoritmer overvejes .

Noter

↑ Buchmann J. , Jacobson MJ, Teske E. Om nogle beregningsmæssige problemer i finite abelske grupper // Mathematics of Computation : journal. - 1997. - Bd. 66 . - S. 1663-1687 . - doi : 10.1090/S0025-5718-97-00880-6 .
↑ S. Pohlig, M. Hellman. En forbedret algoritme til beregning af logaritmer og dens kryptografiske betydning (Corresp.) // IEEE Transactions on Information Theory. - 1978. - Januar ( bind 24 , hæfte 1 ). - S. 106-110 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1978.1055817 . Arkiveret fra originalen den 21. juni 2018.
↑ JM Pollard. Monte Carlo metoder til indeksberegning (mod p) // Mathematics of Computation. - 1978. - Januar ( bind 32 , hæfte 143 ). - S. 918-924 . - doi : 10.1090/S0025-5718-1978-0491431-9 .
↑ L. Adleman. En subeksponentiel algoritme til det diskrete logaritmeproblem med applikationer til kryptografi // 20th Annual Symposium on Foundations of Computer Science. - 1979. - Oktober. - S. 55-60 . - doi : 10.1109/SFCS.1979.2 . Arkiveret fra originalen den 10. maj 2017.
↑ Don Coppersmith, Andrew M. Odlzyko, Richard Schroeppel. Diskrete logaritmer i GF(p) (engelsk) // Algorithmica. - 1986. - November ( bind 1 , udg. 1-4 ). - S. 1-15 . - doi : 10.1007/BF01840433 . Arkiveret fra originalen den 13. april 2018.
↑ Daniel M. Gordon. Diskrete logaritmer i GF(p) Brug af talfeltsigten // SIAM Journal om diskret matematik. - 1993. - T. 6 , no. 1 . - S. 124-138 . - doi : 10.1137/0406010 .
↑ Don Coppersmith. Ændringer af Number Field Sieve // Journal of Cryptology. - 1993. - Bd. 6 , iss. 3 . - S. 169-180 . - doi : 10.1007/BF00198464 . Arkiveret fra originalen den 19. juni 2018.
↑ D. Kobbersmed. Hurtig evaluering af logaritmer i felter med karakteristisk to // IEEE Transactions on Information Theory. - 1984. - Juli ( bind 30 , hæfte 4 ). - S. 587-594 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1984.1056941 .
↑ AJ Menezes, T. Okamoto, SA Vanstone. Reduktion af elliptiske kurvelogaritmer til logaritmer i et begrænset felt // IEEE Transactions on Information Theory. — 1993-09-01. - T. 39 , no. 5 . - S. 1639-1646 . — ISSN 0018-9448 . - doi : 10.1109/18.259647 . Arkiveret fra originalen den 2. juli 2017.
↑ Diffie, Hellman, 1976 .
↑ Elgamal, 1984 .
↑ Elgamal, 1985 .
↑ James L. Massey, Jimmy K. Omura. Fremgangsmåde og apparat til at opretholde privatlivets fred for digitale meddelelser, der formidles ved offentlig transmission (28. januar 1986). Arkiveret fra originalen den 20. oktober 2016. (ubestemt)
↑ Shor, 1994 .
↑ Shor PW Polynomial-Time Algorithms for Prime Factorization and Discrete Logaritms on a Quantum Computer // Fundamenter for datalogi: Konferencepublikationer. - 1997. - S. 1484-1509.
↑ CompuTerra Online #224 - Kvantecomputere og kvantecomputere ... Samtale med kandidaten for fysiske og matematiske videnskaber, en ekspert i teorien om algoritmer Mikhail Vyaly (Computing Center for det russiske videnskabsakademi)

Links

Diffie W. , Hellman M. E. New Directions in Cryptography // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1976. - Vol. 22, Iss. 6. - S. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
Elgamal T. Et offentligt nøglekryptosystem og et signaturskema baseret på diskrete logaritmer, et offentligt nøglekryptosystem og et signaturskema baseret på diskrete logaritmer // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1985. - Vol. 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. Et offentligt nøglekryptosystem og et signaturskema baseret på diskrete logaritmer, et offentligt nøglekryptosystem og et signaturskema baseret på diskrete logaritmer // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1985. - Vol. 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 Logaritms and Factoring (engelsk) // 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. Talteoretiske algoritmer i kryptografi . - Moskva: MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 . Arkiveret 27. januar 2007 på Wayback Machine
Koblitz N. Et kursus i talteori og kryptografi. - Moskva: TVPb, 2001. - 254 s. — ISBN 5-85484-014-6 .
Odlyzko AM Diskrete logaritmer i endelige felter og deres kryptografiske betydning // LNCS . - 1984. - T. 209 . - S. 224-316 .
Yu. V. Nesterenko. Kapitel 4.8. Diskret logaritme // Introduktion til kryptografi / Red. V. V. Yashchenko. - Peter, 2001. - 288 s. - ISBN 5-318-00443-1 .
Oversigt over diskrete logaritmemetoder
Nechaev V.I. På spørgsmålet om kompleksiteten af en deterministisk algoritme for en diskret logaritme // Matematiske noter . - 1994. - Februar ( bind 55 , hæfte 2 ). - S. 91-101 .

Ordbøger og encyklopædier	Stor russer