Hilat ja kryptografia
Olaussen, Oskar (2017-11-02)
O. Olaussen
02.11.2017
© 2017 Oskar Olaussen. 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-201711033030
https://urn.fi/URN:NBN:fi:oulu-201711033030
Tiivistelmä
Tämä tutkielma esittelee hilojen teoriaa, ja sitä miten tätä teoriaa voidaan käyttää salausmenetelmien pohjana. Lisäksi tutkielmassa näytetään, kuinka näitä salausmenetelmiä vastaan voidaan hyökätä.
1990-luvulta eteenpäin on kehitetty useita salausmenetelmiä, joiden turvallisuus perustuu hilojen teoriaan. Hilojen teoriaan perustuvien menetelmien kehittämistä motivoi se, että niiden vaatimat laskutoimitukset ovat usein nopeampia kuin muiden menetelmien. Osaltaan tutkielman tekemistä motivoi myös se, että aiheesta on vähän suomenkielistä aineistoa.
Aluksi tutkielmassa käsitellään lineaarialgebran perusteita ja määritellään hilan käsite. Tämän jälkeen esitellään hilaongelmia. Tällaisia ongelmia ovat esimerkiksi hilan lyhyimmän vektorin sekä tiettyä vektoria lähinnä olevan vektorin löytäminen. Hilaongelmat ovat vaikeita, ja tutkielmassa esiteltävien salausmenetelmien turvallisuus perustuukin niiden haastavuuteen.
Tutkielmassa esitellään myös hilan redusointialgoritmeja. Erityisesti LLL-algoritmi on aiheen kannalta tärkeä, sillä käytännössä kaikki hyökkäykset hilojen teoriaan perustuvia salausmenetelmiä vastaan hyödyntävät tätä algoritmia tavalla tai toisella.
Tutkielman lopussa käsitellään GGH- ja NTRU-salausmenetelmien toimintaperiaatteet sekä menetelmiä vastaan kehitettyjä hyökkäyksiä. Tutkielmassa esitetään Nguenin hyökkäys GGH-salausmenetelmää vastaan, joka teki tästä salausmenetelmästä käytännössä turvattoman. NTRU-salausmenetelmän on kiinnostava, sillä se on harvoja salausmenetelmiä, jota vastaan ei ole tunnettua kvanttitietokonehyökkäystä.
1990-luvulta eteenpäin on kehitetty useita salausmenetelmiä, joiden turvallisuus perustuu hilojen teoriaan. Hilojen teoriaan perustuvien menetelmien kehittämistä motivoi se, että niiden vaatimat laskutoimitukset ovat usein nopeampia kuin muiden menetelmien. Osaltaan tutkielman tekemistä motivoi myös se, että aiheesta on vähän suomenkielistä aineistoa.
Aluksi tutkielmassa käsitellään lineaarialgebran perusteita ja määritellään hilan käsite. Tämän jälkeen esitellään hilaongelmia. Tällaisia ongelmia ovat esimerkiksi hilan lyhyimmän vektorin sekä tiettyä vektoria lähinnä olevan vektorin löytäminen. Hilaongelmat ovat vaikeita, ja tutkielmassa esiteltävien salausmenetelmien turvallisuus perustuukin niiden haastavuuteen.
Tutkielmassa esitellään myös hilan redusointialgoritmeja. Erityisesti LLL-algoritmi on aiheen kannalta tärkeä, sillä käytännössä kaikki hyökkäykset hilojen teoriaan perustuvia salausmenetelmiä vastaan hyödyntävät tätä algoritmia tavalla tai toisella.
Tutkielman lopussa käsitellään GGH- ja NTRU-salausmenetelmien toimintaperiaatteet sekä menetelmiä vastaan kehitettyjä hyökkäyksiä. Tutkielmassa esitetään Nguenin hyökkäys GGH-salausmenetelmää vastaan, joka teki tästä salausmenetelmästä käytännössä turvattoman. NTRU-salausmenetelmän on kiinnostava, sillä se on harvoja salausmenetelmiä, jota vastaan ei ole tunnettua kvanttitietokonehyökkäystä.
Kokoelmat
- Avoin saatavuus [37864]