Problem diskretnog logaritma za eliptičke krivulje (CROSBI ID 340899)
Ocjenski rad | magistarski rad (mr. sc. i mr. art.)
Podaci o odgovornosti
Kopčinović, Danijel
Dujella, Andrej
hrvatski
Problem diskretnog logaritma za eliptičke krivulje
Osnovni razlog za upotrebu eliptičkih krivulja u kriptografiji je jednostavnost implementacije aritmetike na eliptičkim krivuljama (posebno na krivuljama nad poljima karakteristike 2), i težina problema diskretnog logaritma u grupi točaka eliptičke krivulje. Kako je pokazano i razjašnjeno u četvrtom poglavlju ovog rada, opće metode rješavanja diskretnog logaritma jednako su neefikasne na eliptičkim krivuljama kao i na drugim grupama. Metoda računanja indeksa, koja rješava problem diskretnog logaritma u multiplikativnoj grupi konačnog polja sa subeksponencijalnom složenošću, ne može se efikasno primijeniti na eliptičke krivulje, barem ne u istom obliku. Pokušaj zaobilaženja problema na koje se naišlo u primjeni metode računanja indeksa na eliptičkim krivuljama, je Xedni metoda. Pokazalo se ipak da niti ta metoda ne može efikasno riješiti diskretni logaritam za krivulje koje su u kriptografskoj upotrebi. Postoje, međutim, metode koje koriste neke specifičnosti za određene klase eliptičkih krivulja, i efikasno rješavaju problem diskretnog logaritma na tim krivuljama. To su MOV metoda, koja je efikasna za računanje diskretnog logaritma na supersingularnim krivuljama, te metoda za anomalne krivulje, koja je efikasna na klasi anomalnih krivulja nad nekim poljem. Ipak, pokazuje se da je udio bilo supersingularnih, bilo anomalnih krivulja, zanemariv, a testiranje da li neka slučajna krivulja pripada nekoj od tih klasa nije teško, pa zaključujemo da te metode ne predstavljaju ozbiljnu prepreku za korištenje eliptičkih krivulja u kriptografiji. Možemo rezimirati: eliptičke krivulje pružaju puno veći stupanj sigurnosti od drugih struktura koje se koriste u kriptografiji, jer je problem diskretnog logaritma na eliptičkim krivuljama puno teži nego na drugim strukturama. To jednostavnim rječnikom znači da, za isti stupanj sigurnosti, možemo koristiti eliptičke krivulje sa puno manjim parametrima, što smanjuje zahtjeve za okolinu u kojoj se koristi kriptosustav (računalna snaga, memorijski zahtjevi, propusnost računalne mreže). Standardna veličina parametara je 163-192 bita za eliptičke krivulje, a 1024-2048 bitova za multiplikativnu grupu konačnog polja.
eliptičke krivulje; kriptografija
nije evidentirano
engleski
Discrete logarithm problem for elliptic curves
nije evidentirano
elliptic curves; cryptography
nije evidentirano
Podaci o izdanju
127
02.03.2005.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Prirodoslovno-matematički fakultet, Zagreb
Zagreb