Usean muuttujan julkisen avaimen salausjärjestelmät
Salo, Jesse (2019-06-06)
Salo, Jesse
J. Salo
06.06.2019
© 2019 Jesse Salo. Tämä Kohde on tekijänoikeuden ja/tai lähioikeuksien suojaama. Voit käyttää Kohdetta käyttöösi sovellettavan tekijänoikeutta ja lähioikeuksia koskevan lainsäädännön sallimilla tavoilla. Muunlaista käyttöä varten tarvitset oikeudenhaltijoiden luvan.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:oulu-201906082506
https://urn.fi/URN:NBN:fi:oulu-201906082506
Tiivistelmä
Jotkin arkaluonteiset tiedot on tarkoitettu ainoastaan rajatun joukon luettaviksi ja käsiteltäviksi. Salausjärjestelmiä käytetään, jotta tällaisia tietoja pystyvät käyttämään vain ne, joilla on siihen tarvittavat oikeudet. Kvanttitietokoneiden kehittyminen asettaa kuitenkin useat käytössä olevat salausjärjestelmät murtumisuhan alle, joten näiden tilalle on kehitettävä uusia menetelmiä. Usean muuttujan julkisen avaimen salausjärjestelmät ovat yksi tällainen tutkimuskohde, joiden joukosta pyritään löytämään kvanttitietokoneiden suuren laskentakapasiteetin mahdollistamien hyökkäysten kestäviä järjestelmiä.
Nämä salausjärjestelmät saavat nimensä siitä, että niiden julkinen avain koostuu usean muuttujan polynomiyhtälöistä jonkin äärellisen kuntalaajennuksen suhteen. Yhtälöt ovat salatun tekstin suhteen lineaarisia, joten viestin lähettäminen on yksinkertaista. Salatun viestin kaapanneen on kuitenkin ratkaistava epälineaarinen yhtälöryhmä saadakseen selville selkokielisen viestin. Viestin salaus on silti helppo purkaa tunnetun salaisen avaimen avulla.
Lukijalta edellytetään esitietoina lineaarialgebran, kuntarakenteiden sekä salausmenetelmien perustuntemusta. Tutkielman ensimmäisessä luvussa määritellään tarvittavia käsitteitä sekä todistetaan myöhemmin käytettäviä tuloksia lineaarialgebrasta ja kuntarakenteista, sillä äärellisiä kuntalaajennuksia käsitellään tutkielmassa vektoriavaruuksina kerroinkunnan suhteen.
Toinen luku käsittelee Imai-Matsumoto -järjestelmää, joka on ensimmäinen usean muuttujan julkisen avaimen salausjärjestelmä. Se julkaistiin vuonna 1988 ja aloitti näiden järjestelmien historian. Ensin esitetään järjestelmän matemaattinen rakenne, jonka jälkeen sen käyttöä valaistaan esimerkein. Seuraavaksi osoitetaan, miksi järjestelmä on turvaton. Luvun lopuksi esitellään lyhyesti muunnos Imai-Matsumoto -järjestelmästä, joka kuitenkin on myös murrettavissa.
Tutkielman seuraavassa luvussa esitellään 1990-luvun puolivälissä julkaistu Patarinin Pieni lohikäärme -järjestelmä, joka perustuu edeltäjäänsä Imai-Matsumotoon. Matematiikka Pienen lohikäärmeen taustalla esitetään ja järjestelmän käytöstä annetaan esimerkkejä. Seuraavaksi perustellaan miksi järjestelmä ei murru samalla menetelmällä kuin Imai-Matsumoto. Järjestelmän rakentamisessa valitaan salainen eksponentti, joka huonosti tehtynä vaarantaa järjestelmän turvallisuuden mikä osoitetaan myös. Lopuksi esitetään Coppersmith-Patarin -menetelmä, jolla Pieni lohikäärme saadaan murrettua yleisessä tapauksessa.
Neljäs luku alkaa Ison lohikäärmeen esittelyllä, joka on myös Patarinin ehdotus. Tätä seuraa kappale permutaatiopolynomeista, jossa määritellään tarvittavia käsitteitä ja todistetaan tuloksia. Näitä käytetään seuraavissa kappaleissa, joissa käsitellään 2010-luvun alussa julkaistuja järjestelmiä. Nämä pohjautuvat Pieneen lohikäärmeeseen ja niitä kutsutaankin nimillä Pieni lohikäärme kaksi sekä Poly-Dragon. Molemmista esitetään niiden matemaattinen tausta sekä käyttöön liittyviä esimerkkejä. Järjestelmien turvallisuutta käsitellään myös omissa osioissaan.
Tutkielman lopuksi luodaan lyhyt katsaus usean muuttujan julkisen avaimen salausjärjestelmien aiempaan menestykseen sekä niiden nykytilanteeseen.
Nämä salausjärjestelmät saavat nimensä siitä, että niiden julkinen avain koostuu usean muuttujan polynomiyhtälöistä jonkin äärellisen kuntalaajennuksen suhteen. Yhtälöt ovat salatun tekstin suhteen lineaarisia, joten viestin lähettäminen on yksinkertaista. Salatun viestin kaapanneen on kuitenkin ratkaistava epälineaarinen yhtälöryhmä saadakseen selville selkokielisen viestin. Viestin salaus on silti helppo purkaa tunnetun salaisen avaimen avulla.
Lukijalta edellytetään esitietoina lineaarialgebran, kuntarakenteiden sekä salausmenetelmien perustuntemusta. Tutkielman ensimmäisessä luvussa määritellään tarvittavia käsitteitä sekä todistetaan myöhemmin käytettäviä tuloksia lineaarialgebrasta ja kuntarakenteista, sillä äärellisiä kuntalaajennuksia käsitellään tutkielmassa vektoriavaruuksina kerroinkunnan suhteen.
Toinen luku käsittelee Imai-Matsumoto -järjestelmää, joka on ensimmäinen usean muuttujan julkisen avaimen salausjärjestelmä. Se julkaistiin vuonna 1988 ja aloitti näiden järjestelmien historian. Ensin esitetään järjestelmän matemaattinen rakenne, jonka jälkeen sen käyttöä valaistaan esimerkein. Seuraavaksi osoitetaan, miksi järjestelmä on turvaton. Luvun lopuksi esitellään lyhyesti muunnos Imai-Matsumoto -järjestelmästä, joka kuitenkin on myös murrettavissa.
Tutkielman seuraavassa luvussa esitellään 1990-luvun puolivälissä julkaistu Patarinin Pieni lohikäärme -järjestelmä, joka perustuu edeltäjäänsä Imai-Matsumotoon. Matematiikka Pienen lohikäärmeen taustalla esitetään ja järjestelmän käytöstä annetaan esimerkkejä. Seuraavaksi perustellaan miksi järjestelmä ei murru samalla menetelmällä kuin Imai-Matsumoto. Järjestelmän rakentamisessa valitaan salainen eksponentti, joka huonosti tehtynä vaarantaa järjestelmän turvallisuuden mikä osoitetaan myös. Lopuksi esitetään Coppersmith-Patarin -menetelmä, jolla Pieni lohikäärme saadaan murrettua yleisessä tapauksessa.
Neljäs luku alkaa Ison lohikäärmeen esittelyllä, joka on myös Patarinin ehdotus. Tätä seuraa kappale permutaatiopolynomeista, jossa määritellään tarvittavia käsitteitä ja todistetaan tuloksia. Näitä käytetään seuraavissa kappaleissa, joissa käsitellään 2010-luvun alussa julkaistuja järjestelmiä. Nämä pohjautuvat Pieneen lohikäärmeeseen ja niitä kutsutaankin nimillä Pieni lohikäärme kaksi sekä Poly-Dragon. Molemmista esitetään niiden matemaattinen tausta sekä käyttöön liittyviä esimerkkejä. Järjestelmien turvallisuutta käsitellään myös omissa osioissaan.
Tutkielman lopuksi luodaan lyhyt katsaus usean muuttujan julkisen avaimen salausjärjestelmien aiempaan menestykseen sekä niiden nykytilanteeseen.
Kokoelmat
- Avoin saatavuus [31941]