Program diplomskega dela - Nuša Zidarič, Implementacija končnih obsegov in eliptičnih krivulj z vezjem FPGA

Delo predstavi matematične osnove, potrebne za razumevanje osnovnih računskih operacij v binarnih obsegih, ki so posebno zanimivi za kriptosisteme implementirane v strojni opremi. Osrednja motivacija je učinkovita implementacija seštevanja, kvadriranja, množenja in invertiranja na FPGA (Field Programmable Gate Array), ki se uporabljajo za računanja večkratnika točke na eliptični krivulji in so osnova za protokole zasnovane na kriptografiji javnih ključev, kot npr. digitalni podpisi. Opravi naj se še primerjava različnih algoritmov glede na prostorsko in časovno zahtevnost ter analiza rezultatov, ki omogoča izbiro optimalnih modulov.

Povzetek. Kriptosistemi z javnimi ključi, ki temeljijo na eliptičnih krivuljah nad binarnim končnim obsegom GF(2m), so čedalje bolj razširjeni. Da bi zadostili potrebam po hitrosti in prepustnosti sistemov, v katerih se uporabljajo, smo se obrnili k implementaciji aritmetike binarnih končnih obsegov in operacij nad točkami eliptične krivulje na FPGA. Raziskali smo različne algoritme za posamezne operacije in izbrali tiste z najugodnejšo časovno in prostorsko zahtevnostjo. Seštevanje elementov binarnega končnega obsega izvajamo z operatorjem XOR, kar dodatno olajša strojno implementacijo. Zelo preprosto in poceni je tudi kvadriranje. Zaradi pogostosti pojavitev je najbolj pomembna optimizacija množenja elementov izbranega končnega obsega. Najboljše rezultate dobimo z uporabo hibridnega Montgomeryjevega množilnika, ki za izračun produkta potrebuje le dve urini periodi. Množenje uporabljamo pri potenciranju v končnih obsegih in pri računanju s točkami eliptične krivulje. Zanimivo pa je, da dobimo pri potenciranju boljše rezultate, če uporabimo kombinatorično kombinatorični množilnik. Zaradi velikega števila obhodov se računanje inverza izkaže za časovno zelo zahtevno. Operacije nad točkami eliptične krivulje so pogojene z učinkovitostjo binarne aritmetike. Algoritme za seštevanje in podvojevanje točk izboljšamo s prehodom na projektivne koordinate. Le-to omogoči implementacijo seštevanja in podvojevanja z uporabo kvadriranj in množenj, časovno zahteven inverz pa je potreben le pri prehodu na običajne koordinate. Najboljše rezultate dosežemo z uporabo projektivnih koordinat Lopez-Dahab, zato jih uporabimo tudi pri implementaciji množenja točke s skalarjem.

Ključne besede: FPGA, strojna implementacija, binarni končni obsegi, množenje Montgomery, razširjen Evklidov algoritem, eliptične krivulje, projektivne koordinate