McEliece-koodaussysteemi
Eerikinharju, Paula (2023-05-23)
P. Eerikinharju
23.05.2023
© 2023 Paula Eerikinharju. 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-202305231950
https://urn.fi/URN:NBN:fi:oulu-202305231950
Tiivistelmä
Tässä tutkielmassa esitellään McEliece-koodaussysteemi, tämän pohjalta muodostettu CFS-allekirjoitussysteemi ja kaksi erilaista tapaa hyökätä McEliece-koodaussysteemiin.
Ennen McEliece-koodaussysteemin määrittelemistä määritellään tarpeellisia algebran, matriisiteorian ja koodausteorian käsitteitä. Tärkeitä käsitteitä ovat muun muassa ryhmä, kunta, matriisi, permutaatio ja lineaarinen koodi. Lisäksi määritellään systemaattinen koodi ja esitellään lähimpään naapuriin dekoodaus, johon myös McEliece osittain perustuu. Ei-systemaattinen koodi saadaan myös muokattua systemaattiseen muotoon.
McEliece-koodaussysteemin määrittelemisen yhteydessä määritellään Goppa-koodi, joka on suositeltu tapa käyttää McEliece-koodaussysteemiä. Goppa-koodi on koodi, jonka parametrit noudattavat tiettyjä määrittelyjä. McEliece-koodaussysteemin toiminta perustuu julkiseen avaimeen ja turvallisuus siihen, että julkisen avaimen perusteella on hankalaa selvittää yksityistä avainta. Tässä tapauksessa julkinen avain on matriisi, joka saadaan kolmesta matriisista, jotka muodostavat yksityisen avaimen. McEliece-koodaussysteemin määritelmää seuraa kaksi esimerkkiä. McEliece-koodaussysteemi voidaan myös muodostaa niin, että kyseessä ei ole Goppa-koodi, vaikka se ei ole suositeltavaa.
Viestien salauksessa käytetään yleensä hyödyksi koodaussysteemien lisäksi hash-funktioita. Hash-funktiot ovat tapa lyhentää koodattavia viestejä kompaktimpaan muotoon, jotta tiedon käsittely on tehokkaampaa. Lisäksi hash-funktiot tuovat systeemiin lisää turvallisuutta. Satunnaisoraakkeli-malli on hash-funktion ihanne, jota on käytännössä mahdotonta saavuttaa. Hash-funktioita voidaan muodostaa eri tavoin, esimerkiksi Merkle-Damgård-konstruktion avulla.
CFS-allekirjoitussysteemi perustuu Neiderreiter-koodaussysteemiin. Neiderreiter-koodaussysteemi on johdettu McEliece-koodaussysteemistä, ja siinä hyödynnetään syndromeita. CFS-allekirjoitusjärjestelmän määrittelyä seuraa esimerkki CFS-allekirjoitusjärjestelmän käytöstä. CFS-allekirjoitusjärjestelmä toimii kätevästi McEliece-koodaussysteemin yhteydessä muodostaen salaus-allekirjoitus-kokonaisuuden.
McEliece-koodaussysteemin turvallisuutta on järkevää verrata RSA-koodaussysteemin turvallisuuteen, koska nämä koodaussysteemit ovat kehitetty samoihin aikoihin 1970-luvun lopussa. RSA-koodaussysteemi on tosin levinnyt huomattavasti laajempaan käyttöön kuin McEliece-koodaussysteemi yksinkertaisemman rakenteensa vuoksi. McEliece-koodaussysteemin rakenteessa on ominaisuuksia, jotka tekevät siitä RSA-koodaussysteemiä turvallisemman tulevaisuudessa, kun tietokoneiden laskentateho kasvaa merkittävästi. McEliece-koodaussysteemiä vastaan voi hyökätä esimerkiksi Reedin-Mullerin koodin avulla (Minderin-Shokrollahin hyökkäys) tai rakenteellisen hyökkäyksen avulla (Sternin hyökkäys). Näiden hyökkäysten tehokkuutta ja näin ollen toteutettavuutta voidaan arvioida iso-O-notaation avulla.
Ennen McEliece-koodaussysteemin määrittelemistä määritellään tarpeellisia algebran, matriisiteorian ja koodausteorian käsitteitä. Tärkeitä käsitteitä ovat muun muassa ryhmä, kunta, matriisi, permutaatio ja lineaarinen koodi. Lisäksi määritellään systemaattinen koodi ja esitellään lähimpään naapuriin dekoodaus, johon myös McEliece osittain perustuu. Ei-systemaattinen koodi saadaan myös muokattua systemaattiseen muotoon.
McEliece-koodaussysteemin määrittelemisen yhteydessä määritellään Goppa-koodi, joka on suositeltu tapa käyttää McEliece-koodaussysteemiä. Goppa-koodi on koodi, jonka parametrit noudattavat tiettyjä määrittelyjä. McEliece-koodaussysteemin toiminta perustuu julkiseen avaimeen ja turvallisuus siihen, että julkisen avaimen perusteella on hankalaa selvittää yksityistä avainta. Tässä tapauksessa julkinen avain on matriisi, joka saadaan kolmesta matriisista, jotka muodostavat yksityisen avaimen. McEliece-koodaussysteemin määritelmää seuraa kaksi esimerkkiä. McEliece-koodaussysteemi voidaan myös muodostaa niin, että kyseessä ei ole Goppa-koodi, vaikka se ei ole suositeltavaa.
Viestien salauksessa käytetään yleensä hyödyksi koodaussysteemien lisäksi hash-funktioita. Hash-funktiot ovat tapa lyhentää koodattavia viestejä kompaktimpaan muotoon, jotta tiedon käsittely on tehokkaampaa. Lisäksi hash-funktiot tuovat systeemiin lisää turvallisuutta. Satunnaisoraakkeli-malli on hash-funktion ihanne, jota on käytännössä mahdotonta saavuttaa. Hash-funktioita voidaan muodostaa eri tavoin, esimerkiksi Merkle-Damgård-konstruktion avulla.
CFS-allekirjoitussysteemi perustuu Neiderreiter-koodaussysteemiin. Neiderreiter-koodaussysteemi on johdettu McEliece-koodaussysteemistä, ja siinä hyödynnetään syndromeita. CFS-allekirjoitusjärjestelmän määrittelyä seuraa esimerkki CFS-allekirjoitusjärjestelmän käytöstä. CFS-allekirjoitusjärjestelmä toimii kätevästi McEliece-koodaussysteemin yhteydessä muodostaen salaus-allekirjoitus-kokonaisuuden.
McEliece-koodaussysteemin turvallisuutta on järkevää verrata RSA-koodaussysteemin turvallisuuteen, koska nämä koodaussysteemit ovat kehitetty samoihin aikoihin 1970-luvun lopussa. RSA-koodaussysteemi on tosin levinnyt huomattavasti laajempaan käyttöön kuin McEliece-koodaussysteemi yksinkertaisemman rakenteensa vuoksi. McEliece-koodaussysteemin rakenteessa on ominaisuuksia, jotka tekevät siitä RSA-koodaussysteemiä turvallisemman tulevaisuudessa, kun tietokoneiden laskentateho kasvaa merkittävästi. McEliece-koodaussysteemiä vastaan voi hyökätä esimerkiksi Reedin-Mullerin koodin avulla (Minderin-Shokrollahin hyökkäys) tai rakenteellisen hyökkäyksen avulla (Sternin hyökkäys). Näiden hyökkäysten tehokkuutta ja näin ollen toteutettavuutta voidaan arvioida iso-O-notaation avulla.
Kokoelmat
- Avoin saatavuus [37277]
Ellei muuten mainita, aineiston lisenssi on https://creativecommons.org/licenses/by/4.0/