Liitospohjainen kryptografia elliptisillä käyrillä
Illikainen, Aada (2023-02-20)
Illikainen, Aada
A. Illikainen
20.02.2023
© 2023 Aada Illikainen. Ellei toisin mainita, uudelleenkäyttö on sallittu Creative Commons Attribution 4.0 International (CC-BY 4.0) -lisenssillä (https://creativecommons.org/licenses/by/4.0/). Uudelleenkäyttö on sallittua edellyttäen, että lähde mainitaan asianmukaisesti ja mahdolliset muutokset merkitään. Sellaisten osien käyttö tai jäljentäminen, jotka eivät ole tekijän tai tekijöiden omaisuutta, saattaa edellyttää lupaa suoraan asianomaisilta oikeudenhaltijoilta.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:oulu-202302201192
https://urn.fi/URN:NBN:fi:oulu-202302201192
Tiivistelmä
Tutkielmassa tutustutaan erilaisiin elliptisiin käyriin, niiden avulla määriteltäviin liitoksiin sekä liitospohjaisiin kryptografisiin algoritmeihin. Lukijalta odotetaan kuntien sekä kuntalaajennusten tuntemusta.
Tutkielman ensimmäisessä luvussa määritellään elliptinen käyrä sekä esitellään elliptisen käyrän aritmetiikkaa. Lisäksi luvussa määritellään myöhemmin tutkielmassa käytettäviä konsepteja, kuten diskreetin logaritmin ongelma.
Toisessa luvussa esitellään yleistetty elliptinen käyrä, jotta voidaan määritellä elliptinen käyrä karakteristikaa kaksi olevan kunnan yli. Luvussa käsitellään yleistetyn elliptisen käyrän aritmetiikkaa ja tapoja laskea tällaisen käyrän pisteiden lukumäärä. Esitellään myös Koblitz-käyrä, jolla pisteiden monikertojen laskeminen voidaan suorittaa normaalia käyrää tehokkaammin.
Kolmannessa luvussa käsitellään äärellisen kertaluvun pisteet sekä jakajat elliptisellä käyrällä. Näiden avulla määritellään Weilin liitos sekä Taten liitos. Jotta liitoksia voidaan käyttää kryptografisin tarkoituksiin, täytyy liitokset voida laskea tehokkaasti. Tätä varten esitellään Millerin algoritmi. Liitoksien tehokas laskeminen kuitenkin tehostaa myös MOV-algoritmia, jonka tarkoituksena on muuntaa elliptisen käyrän diskreetin logaritmin ongelma diskreetin logaritmin ongelmaksi.
Jos kaksi pistettä on saman pisteen monikertoja, näiden pisteiden liitos on aina yksi. Neljännessä kappaleessa esitellään muodonmuutoskuvaus, jonka ideana on muuntaa toinen pisteistä sellaiseksi, että liitos antaa ykkösestä eroavan luvun. Neljännessä luvussa esitellään myös yksi esimerkki muodonmuutoskuvauksesta, jota käytetään tutkielmassa myöhemmin kryptografisissa algoritmeissa.
Loput luvuista käsittelevät kukin yhden kryptografisen algoritmin. Ensin esitellään kolmen osapuolen Diffie-Hellman avaimenvaihtoa varten. Seuraavaksi käsitellään ID-pohjainen julkisen avaimen kryptosysteemi, jota voidaan käyttää viestien salaamiseen. Lopuksi käsitellään BLS-allekirjoitus. Kaikki mainituista perustuvat liitoksiin, joita tässä tutkielmassa käytetään yhdessä muodonmuutoskuvauksen kanssa.
Tutkielman ensimmäisessä luvussa määritellään elliptinen käyrä sekä esitellään elliptisen käyrän aritmetiikkaa. Lisäksi luvussa määritellään myöhemmin tutkielmassa käytettäviä konsepteja, kuten diskreetin logaritmin ongelma.
Toisessa luvussa esitellään yleistetty elliptinen käyrä, jotta voidaan määritellä elliptinen käyrä karakteristikaa kaksi olevan kunnan yli. Luvussa käsitellään yleistetyn elliptisen käyrän aritmetiikkaa ja tapoja laskea tällaisen käyrän pisteiden lukumäärä. Esitellään myös Koblitz-käyrä, jolla pisteiden monikertojen laskeminen voidaan suorittaa normaalia käyrää tehokkaammin.
Kolmannessa luvussa käsitellään äärellisen kertaluvun pisteet sekä jakajat elliptisellä käyrällä. Näiden avulla määritellään Weilin liitos sekä Taten liitos. Jotta liitoksia voidaan käyttää kryptografisin tarkoituksiin, täytyy liitokset voida laskea tehokkaasti. Tätä varten esitellään Millerin algoritmi. Liitoksien tehokas laskeminen kuitenkin tehostaa myös MOV-algoritmia, jonka tarkoituksena on muuntaa elliptisen käyrän diskreetin logaritmin ongelma diskreetin logaritmin ongelmaksi.
Jos kaksi pistettä on saman pisteen monikertoja, näiden pisteiden liitos on aina yksi. Neljännessä kappaleessa esitellään muodonmuutoskuvaus, jonka ideana on muuntaa toinen pisteistä sellaiseksi, että liitos antaa ykkösestä eroavan luvun. Neljännessä luvussa esitellään myös yksi esimerkki muodonmuutoskuvauksesta, jota käytetään tutkielmassa myöhemmin kryptografisissa algoritmeissa.
Loput luvuista käsittelevät kukin yhden kryptografisen algoritmin. Ensin esitellään kolmen osapuolen Diffie-Hellman avaimenvaihtoa varten. Seuraavaksi käsitellään ID-pohjainen julkisen avaimen kryptosysteemi, jota voidaan käyttää viestien salaamiseen. Lopuksi käsitellään BLS-allekirjoitus. Kaikki mainituista perustuvat liitoksiin, joita tässä tutkielmassa käytetään yhdessä muodonmuutoskuvauksen kanssa.
Kokoelmat
- Avoin saatavuus [31657]