Implementing Arithmetic for Elliptic Curve Cryptosystems
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Helsinki University of Technology |
Diplomityö
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Authors
Date
1999
Major/Subject
Matematiikka
Mcode
Mat-1
Degree programme
Language
en
Pages
87
Series
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.Description
Supervisor
Nevanlinna, OlaviThesis advisor
Niemi, ValtteriKeywords
elliptic curves, elliptiset käyrät, elliptic curve cryptosystems, elliptisen käyrän kryptosysteemit, finite fields, äärelliset kunnat, discrete logarithm problem, diskreetin logaritmin ongelma, implementations, toteutukset