Implementing Arithmetic for Elliptic Curve Cryptosystems

Abstract

Työ käsittelee elliptisiin käyriin pohjautuvien kryptosysteemien tehokasta toteuttamista. Näiden systeemien suorituskykyä tarkastellaan vertailemalla äärellisten kuntien ja elliptisten käyrien aritmetiikan eri laskentamenetelmiä. Lisäksi tehdään katsaus kehittyneimpiin algoritmeihin elliptisen käyrän diskreetin logaritmin ongelman ratkaisemiseksi, mikä luo matemaattista pohjaa olettamukselle, että elliptisiin käyriin perustuvilla julkisen avaimen kryptosysteemeillä voidaan saada aikaan vahva salaus suhteellisen Iyhyillä avaimilla.

Elliptisten käyrien laaja matemaattinen teoria juontaa juurensa algebrallisesta geometriasta ja lukuteoriasta. Lyhyyden vuoksi muutama lause, joiden todistaminen vaatisi syvällisempää tietämystä näiltä aloilta, on esitetty suoraan ilman todistusta. Näitä lauseita tarvitaan elliptisen käyrän ryhmärakenteen selvittämiseksi, mikä puolestaan on kyseiseen käyrään perustuvan kryptosysteemin turvallisuuden kannalta merkittävä tekijä.

Elliptisen käyrän ryhmäoperaatio voidaan laskea suorittamalla muutama laskutoimitus kunnassa, jonka päälle kyseinen käyrä on rakennettu. Koska kryptografiassa käytettävät kunnat ovat äärellisiä, tästä seuraa, että äärellisen kunnan nopeat laskenta-algoritmit ovat tärkeitä suunniteltaessa elliptisen käyrän aritmetiikan tehokkaita toteutuksia. Tämän vuoksi äärellisiä kuntia käsitellään työssä yksityiskohtaisesti, painottuen kuntiin, joiden karakteristika on 2.

Mikä tekee karakteristikan 2 äärellisistä kunnista kiinnostavia on se tosiseikka, että nämä voidaan tulkita vektoriavaruuksiksi yli kunnan F_(2) = {0,1}. Kyseiset kunnat voidaan näin ollen luontevasti esittää kiinteän pituisina bittijonoina, mikä puolestaan johtaa hyvin nopeisiin kuntaoperaatioiden toteutuksiin käyttäen logiikkapiirejä tai yleiskäyttöisiä mikroprosessoreita. Työssä esitetään kuvaus eräistä aritmetiikan toteutuksista suurille karakteristikan 2 kunnille.

Elliptisen käyrän kryptosysteemeissä käytettävistä laskutoimituksista tärkein on käyrän pisteen monikerran laskeminen, mikä on analoginen toimenpide potenssiin korotuksen kanssa kertolaskunotaatiolla varustetussa ryhmässä. Työssä esitetään muutama nopea yleisen ryhmän potenssiinkorotusalgoritmi sekä tekniikoita, jotka hyödyntävät elliptisen käyrän pisteiden esitystä projektiivisen tason homogeenisissa koordinaateissa. Yhdistämällä nämä tekniikat äärellisen kunnan algoritmeihin päädytään tehokkaisiin elliptisen käyrän pisteen monikerran laskentamenetelmiin. Työssä vertaillaan näiden menetelmien kompleksisuutta ja tarkastellaan eräitä tehtyjä ohjelmisto- ja mikropiiritoteutuksia.