Zastosowanie ciał rozszerzonych w celu przyspieszenia obliczeń na

  • Published on
    11-Jan-2017

  • View
    216

  • Download
    3

Embed Size (px)

Transcript

<ul><li><p>XLIII KZM ZAKOPANE 2014</p><p>Micha Wroski</p><p>WAT Warszawa</p><p>Zastosowanie cia rozszerzonych w celu</p><p>przyspieszenia oblicze na krzywych eliptycznych</p><p>Krzywe eliptyczne s jednym z podstawowych narzdzi wykorzystywanym wewspczesnej kryptografii, przede wszystkim w protokoach podpisu cyfrowego. Pozaoczywistymi zaletami, takimi jak odporno na podwykadnicze ataki na logarytmdyskretny, posiadaj take pewne wady, z ktrych najwiksz wydaje si by zoo-no (a tym samym czasochonno) obliczania na nich krotnoci punktu na krzywejeliptycznej, dlatego te podejmowanych jest wiele prb przyspieszenia tego dziaa-nia. W tym zakresie spotyka si dwa zasadnicze (niewykluczajce si) podejcia.Pierwsze dotyczy optymalizacji samej metody obliczania krotnoci, tak aby zosta-o wykonanych jak najmniej podwoje i dodawa punktw na krzywej eliptycznej.Drugie podejcie dotyczy natomiast zminimalizowania liczby krokw niezbdnych dowykonania poszczeglnych operacji. W tym celu najczciej wykorzystuje si rnesposoby zapisu punktu na krzywej eliptycznej.</p><p>W roku 2007 pojawia si nowa reprezentacja krzywych eliptycznych, znanychobecnie jako krzywe Edwardsa, a pniej rwnie ich uoglnienie skrcone krzy-we Edwardsa. Pionierami w tej dziedzinie (oprcz Harolda Edwardsa) s przedewszystkim Daniel Bernstein i Tanja Lange. Wikszo literatury dotyczcej zasto-sowa krzywych Edwardsa i skrconych krzywych Edwardsa jest ich autorstwa.</p><p>Krzywe Edwardsa i skrcone krzywe Edwardsa posiadaj dwie bardzo wane zale-ty w porwnaniu do krzywych eliptycznych w postaci Weierstrassa. Dodawanie i po-dwojenie punktu jest mniej czasochonne oraz podwojenie punktu mona wykonajako dodawanie tych samych punktw, co uprzednio nie byo moliwe. Jest to o tylewane, e znacznie utrudnia moliwo wyznaczania krotnoci punktu poprzez anali-z charakterystyk poboru mocy. Minusem reprezentacji krzywej eliptycznej w postaciEdwardsa (skrconej Edwardsa) jest to, e nie dla kadej krzywej eliptycznej zapi-sanej w formie Wierestrassa mona znale krzyw Edwardsa (skrcon Edwardsa),ktra byaby do niej izomorficzna. Dostpne s opracowania poruszajce problema-tyk obliczenia krotnoci punktu na izogenicznej skrconej krzywej Edwardsa, alew ciele rozszerzonym.</p><p>W niniejszym opracowaniu przedstawimy ide przechodzenia z dowolnej krzy-wej eliptycznej w skrconej formie Weierstrassa w ciele GF (p) na skrcon krzywEdwardsa w ciele GF (p3) oraz przedstawimy efektywny sposb implementacji ukadumnocego w tym ciele, dziki czemu czna efektywno obliczeniowa wyznaczaniakrotnoci punktu na krzywej eliptycznej znacznie wzrasta.</p></li></ul>

Recommended

View more >