Gelfond-Shanks -algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28. joulukuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 9 muokkausta .

Gelfond-Shanks -algoritmi ( eng. Baby-step giant-step ; kutsutaan myös suurten ja pienten askeleiden algoritmiksi ; nimien täsmäytysalgoritmi löytyy myös hyvin usein esimerkiksi Vasilenkon kirjasta "Number-Theoretic Algorithms of Cryptography" ) - ryhmäteoriassa diskreettien logaritmien deterministinen algoritmi jäännösrenkaan multiplikatiivisessa ryhmässä moduloi alkulukua. Neuvostoliiton matemaatikko Alexander Gelfond vuonna 1962 ja Daniel Shanks ehdottivat sitä vuonna 1972 [1] [2] [3] .

Menetelmä yksinkertaistaa teoreettisesti diskreetin logaritmiongelman ratkaisua, jonka laskennallisen monimutkaisuuden varaan on rakennettu monia julkisen avaimen salausjärjestelmiä . Viittaa tapaamismenetelmiin keskellä .

Laajuus

Diskreetin logaritmin ongelma on erittäin kiinnostava julkisen avaimen salausjärjestelmien rakentamisessa . Olettaen, että tämän ongelman ratkaiseminen on erittäin suuri laskennallinen monimutkaisuus, tällaiset kryptoalgoritmit perustuvat esimerkiksi RSA , DSA , Elgamal , Diffie-Hellman , ECDSA , GOST R 34.10-2001 , Rabin ja muihin. Niissä kryptanalyytikko voi saada yksityisen avaimen ottamalla julkisen avaimen diskreetin logaritmin (kaikkien tiedossa) ja muuntaa sen avulla salatekstin viestin tekstiksi. Kuitenkin, mitä vaikeampaa sen löytäminen on (mitä enemmän operaatioita sinun on tehtävä diskreetin logaritmin löytämiseksi), sitä turvallisempi salausjärjestelmä on. Yksi tapa lisätä diskreetin logaritmiongelman monimutkaisuutta on luoda salausjärjestelmä , joka perustuu suuren järjestyksen omaavaan ryhmään (jossa logaritmi on modulo suuri alkuluku). Yleensä tällainen ongelma ratkaistaan tyhjentävällä luettelolla , mutta tämä algoritmi sallii joissain tapauksissa yksinkertaistaa eksponentin löytämistä (vähentää askelmäärää) laskettaessa modulo alkulukua, edullisimmassa tapauksessa neliöjuurella. kertaa [4] , mutta tämä vähennys ei vieläkään riitä ratkaisemaan ongelmaa elektronisessa tietokoneessa kohtuullisessa ajassa (kysymys diskreetin logaritmiongelman ratkaisemisesta polynomiajassa henkilökohtaisessa tietokoneessa on edelleen avoin) [5] .

Diskreetti logaritmiongelma

Olkoon syklinen ryhmä generaattorilla , joka sisältää elementtejä. Kokonaislukua (välillä - ) kutsutaan elementin diskreetiksi kantalogaritmiksi , jos relaatio on tosi: $G$ $g$ $n$ $x$ $0$ $n-1$ $h\in G$ $g$

g^{x}=h.

Diskreetin logaritmin tehtävänä on määrittää annetulle . $h$ $g$ $x$

Muodollisesti diskreetin logaritmin ongelma esitetään seuraavasti [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}}

edellyttäen, että sitä ei ole olemassa ja se voi myös olla joko alkuluku tai yhdistelmäluku. $x$ $n$

Teoria

Algoritmin ideana on valita optimaalinen ajan ja muistin suhde , eli parannetussa eksponentin haussa.

Olkoon syklinen järjestysryhmä , ryhmän generaattori ja jokin ryhmän elementti . Tehtävä rajoittuu kokonaisluvun etsimiseen , jolle $G$ $n$ $\alpha$ $\beeta$ $x$

\alpha^x = \beta\,.

Gelfond-Shanks-algoritmi perustuu esitykseen muodossa , missä , sekä ja luettelointiin . Rajoitus ja seuraa siitä, että ryhmän järjestys ei ylitä , mikä tarkoittaa, että ilmoitetut vaihteluvälit riittävät saamaan kaikki mahdolliset puolivälistä . Tämä esitys vastaa tasa-arvoa $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$ $\left[0; m\oikea)$

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

(yksi)

Algoritmi laskee etukäteen eri arvot ja tallentaa ne tietorakenteeseen , joka mahdollistaa tehokkaan haun, ja toistaa sitten kaikki mahdolliset arvot ja tarkistaa, vastaako se jotakin arvoa . Siten löydetään indeksit ja , jotka täyttävät suhteen (1) ja mahdollistavat arvon [7] laskemisen . $\alpha^{im}$ $i$ $j$ ${\displaystyle \beta \alpha ^{j))$ $i$ $i$ $j$ $x=i\cdot mj$

Algoritmi

Syöttö : Syklinen järjestysryhmä , generaattori ja jokin elementti . $G$ $n$ $\alpha$ $\beeta$

Tulos : Numero , joka tyydyttää . $x$ $\alpha^{x}=\beta$

$m$ ← $\left\lfloor {\sqrt {n}}\right\rfloor +1$
Laske ← . $\gamma$ ${\displaystyle \alpha ^{m))$
Kaikille , joissa ≤ ≤ : $i$ $yksi$ $i$ $m$
1. Kirjoita pöytään ( , ). (Katso Käyttöönotto-osio) $i$ $\gamma$
2. $\gamma$ ← • $\gamma$ ${\displaystyle \alpha ^{m))$
Kaikille , joissa ≤ ≤ : $j$ $0$ $j$ $m-1$
1. Laske . ${\displaystyle \beta \alpha ^{j))$
2. Tarkista sisältääkö taulukko. ${\displaystyle \beta \alpha ^{j))$
3. Jos kyllä, palauta - . $im$ $j$
4. Jos ei, jatka silmukalla [1] [2] [7] .

Algoritmin perustelu

On tarpeen todistaa, että samat elementit taulukoissa ovat välttämättä olemassa, eli on olemassa sellaisia ja , että . Tämä tasa -arvo tapahtuu tapauksessa , tai . Sillä epätasa- arvo pätee . Eri pareille ja meillä on , koska muuten kävisi ilmi , että ilmoitetulla valinnalla se on mahdollista vain tapauksessa , ja siksi . Näin ollen lausekkeet ottavat kaikki arvot välillä - , mikä johtuu siitä, että sisältää kaikki mahdolliset arvot välillä - . Näin ollen joillekin tasa-arvo [ 2] pätee . $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$ ${\näyttötyyli (i_{1},j_{1})}$ ${\näyttötyyli (i_{2},j_{2})}$ ${\displaystyle 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))$

Algoritmin monimutkaisuuden arviointi

Oletetaan, että meidän on ratkaistava , missä ja ovat positiivisia kokonaislukuja pienempiä kuin . Yksi tapa on iteroida peräkkäin välillä - , vertaamalla arvoa arvoon . Pahimmassa tapauksessa tarvitsemme vaiheita (kun ). Keskimäärin se vaatii toimenpiteitä. Muuten voimme esittää muodossa . Siten ongelma rajoittuu etsimiseen ja . Tässä tapauksessa voit kirjoittaa tehtävän uudelleen muotoon tai . Nyt voimme iteroida kaikkia mahdollisia arvoja lausekkeen oikealla puolella. Tässä tapauksessa nämä ovat kaikki numeroita välillä - . Nämä ovat niin sanottuja suuria askeleita. Tiedetään, että yksi saaduista arvoista on vaadittu. Voimme tallentaa kaikki lausekkeen oikean puolen arvot taulukkoon. Voimme sitten laskea mahdolliset arvot vasemmalle puolelle eri arvoille . Nämä ovat kaikki numeroita, joista yksi on haluttu, ja yhdessä oikean puolen oikean arvon kanssa antaa halutun tuloksen arvolle . Siten tehtävä rajoittuu vasemman puolen eri arvojen lajitteluun ja niiden etsimiseen taulukosta. Jos haluttu arvo löytyy taulukosta, olemme löytäneet , ja siten vastaavan . Tämä kuva havainnollistaa algoritmin nopeutta. Leikkauksia tehdään keskimäärin . Pahimmassa tapauksessa tarvitaan operaatioita [3] . $h=ng$ $h$ $g$ $100$ $n$ $yksi$ $100$ $n \cdot g$ $h$ $100$ $n = 99$ $viisikymmentä$ $n$ $n = 10a-b$ $a$ $b$ $h=(10a-b)g$ $h+bg=10ag$ $a$ $yksi$ $kymmenen$ $a$ $b$ $0$ $9$ $n$ $b$ $n = 10a+b$ $1.5{\sqrt {n))$ $2{\sqrt {n))$

Esimerkki

Alla on esimerkki diskreetin logaritmitehtävän ratkaisemisesta pienellä ryhmäjärjestyksellä. Käytännössä kryptojärjestelmät käyttävät korkeamman asteen ryhmiä kryptografisen vahvuuden parantamiseksi .

Olkoon se tiedossa . Alussa luomme ja täytämme taulukon "isoista askeleista". Valitsemme ← ( ). Sitten se ajaa osoitteesta - . $5^{x}\equiv 3{\pmod {23}}$ $m = 5$ ${\sqrt {16}}+1$ $i$ $yksi$ $5$

$i$	yksi	2	3	neljä	5
${\displaystyle 5^{im}=20^{i))$	kaksikymmentä	9	19	12	kymmenen

Etsitään sopiva arvo , jotta molempien taulukoiden arvot täsmäävät $j$ $3\cdot 5^{j}\ {\bmod {\ }}23$

$j$	yksi	2	3	neljä
$\beta \alpha ^{j}=3$ · ${\näyttötyyli 5^{j))$	viisitoista	6	7	12

Voidaan nähdä, että toisessa taulukossa , tällainen arvo on jo ensimmäisessä taulukossa. Etsi [2] . $j=4$ $x=mi-j=5\cdot 4-4=16$

Toteutus

On olemassa tapa parantaa Gelfond -Shanks-algoritmin suorituskykyä. Se koostuu tehokkaan taulukon käyttöjärjestelmän käytöstä. Paras tapa on käyttää hash-taulukkoa . Sinun tulisi tiivistää toinen komponentti ja suorittaa sitten tiivistehaku pääsilmukan taulukosta . Koska hajautustaulukon elementtien saaminen ja lisääminen vie aikaa ( vakio ), tämä ei asymptoottisesti hidasta algoritmia. $\gamma$ $O(1)$

Algoritmin ajoajaksi on arvioitu , mikä on paljon parempi kuin eksponentien tyhjentävän laskennan ajoaika [4] . $O({\sqrt {n)))$ $Päällä)$

Ominaisuudet

Gelfond-Shanks-algoritmi toimii mielivaltaiselle äärelliselle sykliselle ryhmälle [7] [3] .
Ryhmän järjestystä ei tarvitse tietää etukäteen. Algoritmi toimii myös, jos on ryhmän järjestyksen yläraja [7] . $G$ $n$
Tyypillisesti Gelfond-Shanks-algoritmia käytetään ryhmille, joiden järjestys on alkuluku . Jos järjestys on yhdistelmäluku , on suositeltavaa käyttää Polig-Hellman-algoritmia [7] .
Gelfond-Shanks-algoritmi vaatii muistia. Algoritmin ensimmäisessä vaiheessa on mahdollista valita pienempi . Tämä pidentää ohjelman käyntiaikaa . Diskreetille logaritmille voidaan käyttää myös Pollardin ρ-menetelmää , joka toimii samaan aikaan, mutta vaatii vähän muistia [7] . $Päällä)$ $m$ $O(n/m)$

Muistiinpanot

↑ 1 2 D. Varret. Todellisen neliökentän infrastruktuuri ja sen sovellukset. Numeroteoriakonferenssin aineisto. - Coloradon yliopisto, Boulder, 1972. - S. s. 217-224. .
↑ 1 2 3 4 I. A. Pankratova. Numeroteoreettiset menetelmät kryptografiassa: Oppikirja. - Tomsk: TSU, 2009. - S. 90-98. – 120 s. .
↑ 1 2 3 V.I. Nechaev. Salauksen elementit. Tietoturvateorian perusteet . - M . : Korkeakoulu, 1999. - S. 61 -67. — 109 s. — ISBN 5-06-003644-8 . .
↑ 12 D.C. Terr . Muunnos Shanksin baby-step jättiläisaskel-algoritmista . — Laskennan matematiikka. - 2000. - T. 69. - S. 767-773. .
↑ Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa . - Moskova: MTSNMO , 2003. - S. 163-185. — 328 s. — ISBN 5-94057-103-4 . Arkistoitu kopio (linkki ei saatavilla) . Käyttöpäivä: 23. marraskuuta 2016. Arkistoitu alkuperäisestä 27. tammikuuta 2007. (määrätön) .
↑ Yan, Song Y. Primaliteettitestaus ja kokonaislukujen faktorointi julkisen avaimen kryptografiassa . - 2. - Springer, 2009. - S. 257-260. — 374 s. — ISBN 978-0-387-77267-7 . .
↑ 1 2 3 4 5 6 Glukhov M. M., Kruglov I. A., Pichkur A. B., Cheremushkin A. V. Johdatus lukuteoreettisiin kryptografian menetelmiin. - 1. painos - Pietari. : Lan, 2010. - S. 279-298. – 400 s. Kanssa. - ISBN 978-5-8114-1116-0 . .

Kirjallisuus

A.O. Gelfond, Yu.V. Linnik. Analyyttisen lukuteorian perusmenetelmät. - M .: Fizmatgiz, 1962. - 272 s.

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi