Gelfond-Shanks algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 december 2019; kontroller kräver 9 redigeringar .

Gelfond-Shanks-algoritmen ( eng. Baby-step giant-step ; även kallad algoritmen för stora och små steg ; du kan också väldigt ofta hitta namnmatchningsalgoritmen , till exempel i Vasilenkos bok "Number-Theoretic Algorithms of Cryptography" ) - i gruppteorin, en deterministisk algoritm av diskreta logaritmer i den multiplikativa gruppen av restringen modulo ett primtal. Det föreslogs av den sovjetiske matematikern Alexander Gelfond 1962 och Daniel Shanks 1972 [1] [2] [3] .

Metoden förenklar teoretiskt lösningen av det diskreta logaritmproblemet, på vars beräkningskomplexitet många kryptosystem med offentliga nyckel är byggda . Avser metoder för att mötas i mitten .

Omfattning

Det diskreta logaritmproblemet är av stort intresse för konstruktionen av kryptosystem med publika nyckel . På antagandet om en extremt hög beräkningskomplexitet för att lösa detta problem är sådana kryptoalgoritmer baserade, till exempel RSA , DSA , Elgamal , Diffie-Hellman , ECDSA , GOST R 34.10-2001 , Rabin och andra. I dem kan kryptoanalytikern erhålla den privata nyckeln genom att ta den diskreta logaritmen för den offentliga nyckeln (känd för alla), och använda den för att konvertera chiffertexten till texten i meddelandet. Men ju svårare det är att hitta det (ju fler operationer du behöver göra för att hitta den diskreta logaritmen), desto säkrare är kryptosystemet. Ett sätt att öka komplexiteten i det diskreta logaritmproblemet är att skapa ett kryptosystem baserat på en grupp med en stor ordning (där logaritmen kommer att vara modulo ett stort primtal). I det allmänna fallet löses ett sådant problem genom uttömmande uppräkning , men denna algoritm gör det i vissa fall möjligt att förenkla att hitta exponenten (minska antalet steg) vid beräkning av modulo ett primtal, i det mest gynnsamma fallet, med kvadratroten av gånger [4] , men denna minskning är fortfarande inte tillräcklig för att lösa problemet på en elektronisk dator inom rimlig tid (frågan om att lösa det diskreta logaritmproblemet i polynomtid på en persondator är fortfarande öppen) [5] .

Diskret logaritmproblem

Låt en cyklisk grupp med generator ges , innehållande element. Ett heltal (i intervallet från till ) kallas den diskreta baslogaritmen för ett element om relationen är sann: $G$ $g$ $n$ $x$ $0$ $n-1$ $h\in G$ $g$

g^{x}=h.

Uppgiften för diskret logaritm är att bestämma för givet . $h$ $g$ $x$

Formellt ställs problemet med diskret logaritm enligt följande [6] :

{\begin{cases}{\text{Input:}}\quad &g,h,n\in \mathbb {N} \\{\text{Output:}}\quad &x\in \mathbb {N } :\ g^{x}\equiv h{\pmod {n}}\\\end{cases}}

förutsatt att det kanske inte finns, och det kan också vara antingen ett primtal eller ett sammansatt tal. $x$ $n$

Teori

Idén med algoritmen är att välja det optimala förhållandet mellan tid och minne , nämligen i en förbättrad sökning efter exponenten.

Låt en cyklisk grupp av ordning , en generator av gruppen , och något element av gruppen ges . Uppgiften reduceras till att hitta ett heltal för vilket $G$ $n$ $\alfa$ $\beta$ $x$

\alpha^x = \beta\,.

Gelfond-Shanks-algoritmen är baserad på representationen i formen , där , och uppräkning av och . Begränsningen på och följer av det faktum att gruppens ordning inte överstiger , vilket innebär att de angivna intervallen är tillräckliga för att erhålla alla möjliga från halvintervallet . Denna representation är likvärdig med jämställdheten $x$ $x=i\cdot mj$ $m = \left\lfloor \sqrt{n} \right\rfloor + 1$ $1 \leq i \leq m$ $0 \leq j < m$ $i$ $j$ $m$ $x$ $\vänster[0; m\höger)$

$\alpha^{im} = \beta \alpha^j\,.$

(ett)

Algoritmen förberäknar för olika värden och lagrar dem i en datastruktur som möjliggör effektiv uppslagning, och itererar sedan över alla möjliga värden och kontrollerar om det matchar något värde . Således hittas index och som uppfyller relation (1) och låter oss beräkna värdet [7] . $\alpha^{im}$ $i$ $j$ ${\displaystyle \beta \alpha ^{j))$ $i$ $i$ $j$ $x=i\cdot mj$

Algoritm

Ingång : En cyklisk ordergrupp , en generator och något element . $G$ $n$ $\alfa$ $\beta$

Output : Ett tal som uppfyller . $x$ $\alpha^{x}=\beta$

$m$ ← $\left\lfloor {\sqrt {n}}\right\rfloor +1$
Beräkna ← . $\gamma$ ${\displaystyle \alpha ^{m))$
För alla där ≤ ≤ : $i$ $ett$ $i$ $m$
1. Skriv till tabellen ( , ). (Se avsnittet Implementering) $i$ $\gamma$
2. $\gamma$ ← • $\gamma$ ${\displaystyle \alpha ^{m))$
För alla där ≤ ≤ : $j$ $0$ $j$ $m-1$
1. Beräkna . ${\displaystyle \beta \alpha ^{j))$
2. Kontrollera om tabellen innehåller. ${\displaystyle \beta \alpha ^{j))$
3. Om ja, returnera - . $im$ $j$
4. Om inte, fortsätt med loop [1] [2] [7] .

Motivering av algoritmen

Det är nödvändigt att bevisa att samma element i tabellerna nödvändigtvis existerar, det vill säga att det finns sådana och , att . Denna jämlikhet sker i fallet med , eller . För ojämlikheten gäller . _ För olika par och vi har , eftersom det annars skulle visa sig att med det angivna valet är det endast möjligt i fallet med , och därför, . Alltså tar uttryck alla värden i intervallet från till , som, på grund av det faktum att , innehåller alla möjliga värden från till . Därför gäller för vissa och jämlikheten [2] . $i$ $j$ ${\displaystyle g^{mi}=\beta \cdot g^{j}=g^{x+j))$ $mi=x+j{\pmod {n}}$ $x=mi-j{\pmod {n))$ $1\leq i\leq m$ $1\leq j\leq m$ $0\leq mi-j\leq m^{2}-1$ $(i_{1},j_{1})$ $(i_{2},j_{2})$ $mi_{1}-j_{1}\neq mi_{2}-j_{2}$ $m(i_{1}-i_{2})=(j_{1}-j_{2})$ $i_{1},i_{2}$ $i_{1}=i_{2}$ ${\displaystyle j_{1}=j_{2))$ $mi-j$ $0$ $m^{2}-1$ $m^{2}>n$ $x$ $0$ $n-1$ $i$ $j$ $x=mi-j{\pmod {n))$

Uppskattning av komplexiteten hos en algoritm

Antag att vi måste lösa , där och är positiva heltal mindre än . Ett sätt är att iterera sekventiellt från till och jämföra värdet med . I värsta fall behöver vi steg (när ). I genomsnitt kommer det att ta steg. Annars kan vi representera som . Därmed reduceras problemet till att hitta och . I det här fallet kan du skriva om uppgiften som eller . Nu kan vi iterera över alla möjliga värden på höger sida av uttrycket. I det här fallet är alla siffror från till . Det är de så kallade stora stegen. Det är känt att ett av de erhållna värdena för är det som krävs. Vi kan registrera alla värden på höger sida av uttrycket i en tabell. Vi kan sedan beräkna de möjliga värdena för vänster sida för olika värden på . Dessa är alla siffror från till varav ett är det önskade, och tillsammans med rätt värde på högersidan ger det önskade resultatet för . Således reduceras uppgiften till att sortera igenom de olika värdena på vänster sida och söka efter dem i tabellen. Om det önskade värdet finns i tabellen har vi hittat , och därför motsvarande . Den här illustrationen visar algoritmens hastighet. I genomsnitt utförs operationer. I värsta fall krävs operationer [3] . $h=ng$ $h$ $g$ $100$ $n$ $ett$ $100$ $n \cdot g$ $h$ $100$ $n=99$ $femtio$ $n$ $n=10a-b$ $a$ $b$ $h=(10a-b)g$ $h+bg=10ag$ $a$ $ett$ $tio$ $a$ $b$ $0$ $9$ $n$ $b$ $n=10a+b$ $1.5{\sqrt {n))$ $2{\sqrt {n))$

Exempel

Nedan är ett exempel på att lösa det diskreta logaritmproblemet med en liten gruppordning. I praktiken använder kryptosystem grupper av högre ordning för att förbättra kryptografisk styrka .

Låt det vara känt . I början kommer vi att skapa och fylla i tabellen för de "stora stegen". Låt oss välja ← ( ). Sedan körs den från till . $5^{x}\equiv 3{\pmod {23}}$ $m=5$ ${\sqrt {16}}+1$ $i$ $ett$ $5$

$i$	ett	2	3	fyra	5
${\displaystyle 5^{im}=20^{i))$	tjugo	9	19	12	tio

Låt oss hitta ett lämpligt värde för så att värdena i båda tabellerna matchar $j$ $3\cdot 5^{j}\ {\bmod {\ }}23$

$j$	ett	2	3	fyra
$\beta \alpha ^{j}=3$ · ${\displaystyle 5^{j))$	femton	6	7	12

Det kan ses att i den andra tabellen för finns ett sådant värde redan i den första tabellen. Hitta [2] . $j=4$ $x=mi-j=5\cdot 4-4=16$

Implementering

Det finns ett sätt att förbättra prestanda för Gelfond-Shanks-algoritmen. Det består i att använda ett effektivt schema för tabellåtkomst. Det bästa sättet är att använda en hashtabell . Du bör hasha på den andra komponenten och sedan utföra en hash-sökning i tabellen i huvudslingan på . Eftersom det tar tid att komma åt och lägga till element i en hashtabell ( en konstant ), saktar detta inte asymptotiskt ner algoritmen. $\gamma$ $O(1)$

Löptiden för algoritmen uppskattas till , vilket är mycket bättre än körtiden för uttömmande uppräkning av exponenter [4] . $O({\sqrt {n)))$ $På)$

Funktioner

Gelfond-Shanks-algoritmen fungerar för en godtycklig ändlig cyklisk grupp [7] [3] .
Det finns ingen anledning att veta ordningen på gruppen i förväg. Algoritmen fungerar också om är den övre gränsen för gruppens ordning [7] . $G$ $n$
Vanligtvis används Gelfond-Shanks-algoritmen för grupper vars ordning är ett primtal . Om beställningen är ett sammansatt nummer rekommenderas användning av Polig-Hellman-algoritmen [7] .
Gelfond-Shanks-algoritmen kräver minne. Det är möjligt att välja en mindre i det första steget av algoritmen. Detta ökar programmets körtid till . Det är också möjligt att använda Pollards ρ-metod för diskret logaritm , som fungerar på samma tid, men kräver en liten mängd minne [7] . $På)$ $m$ $O(n/m)$

Anteckningar

↑ 1 2 D. Shanks. Infrastrukturen för ett verkligt kvadratiskt fält och dess tillämpningar. Handlingar från talteorikonferensen. - University of Colorado, Boulder, 1972. - S. pp. 217-224. .
↑ 1 2 3 4 I. A. Pankratova. Talteoretiska metoder i kryptografi: Lärobok. - Tomsk: TSU, 2009. - S. 90-98. — 120 s. .
↑ 1 2 3 V.I. Nechaev. Delar av kryptografi. Grundläggande informationssäkerhetsteori . - M . : Högre skola, 1999. - S. 61 -67. — 109 sid. — ISBN 5-06-003644-8 . .
↑ 12 D.C. Terr . En modifiering av Shanks baby-step giant-step-algoritm . — Beräkningsmatematik. - 2000. - T. 69. - S. 767-773. .
↑ Vasilenko O. N. Talteoretiska algoritmer i kryptografi . - Moskva: MTSNMO , 2003. - S. 163-185. — 328 sid. — ISBN 5-94057-103-4 . Arkiverad kopia (inte tillgänglig länk) . Datum för åtkomst: 23 november 2016. Arkiverad från originalet 27 januari 2007. (obestämd) .
↑ Yan, Song Y. Primalitetstestning och heltalsfaktorisering i kryptografi med offentlig nyckel . - 2. - Springer, 2009. - S. 257-260. — 374 sid. — ISBN 978-0-387-77267-7 . .
↑ 1 2 3 4 5 6 Glukhov M. M., Kruglov I. A., Pichkur A. B., Cheremushkin A. V. Introduktion till talteoretiska metoder för kryptografi. - 1:a upplagan - St Petersburg. : Lan, 2010. - S. 279-298. — 400 s. Med. - ISBN 978-5-8114-1116-0 . .

Litteratur

A.O. Gelfond, Yu.V. Linnik. Elementära metoder i analytisk talteori. - M. : Fizmatgiz, 1962. - 272 sid.

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm