Reppuongelma ja Merklen-Hellmanin salaus
Eerola, Mikko (2024)
Eerola, Mikko
2024
Matematiikan ja tilastotieteen kandidaattiohjelma - Bachelor's Programme in Mathematics and Statistics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2024-03-28
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202403223048
https://urn.fi/URN:NBN:fi:tuni-202403223048
Tiivistelmä
Tutkielmassa perehdytään reppuongelmaan ja sitä hyödyntävään Merklen–Hellmanin salausmenetelmään. Tarkoitus on esitellä tarvittavia pohjatietoja ja rakentaa niiden päälle salausmenetelmä, jota voidaan käyttää tiedon salaamiseen, esimerkiksi internetissä. Esitietoina käydään läpi lukuteorian perustuloksia, erityisesti jaollisuutta sekä kongruenssia. Nämä perustulokset ovat keskiössä koko tutkielman läpi. Lisäksi esitellään Eukleideen algoritmi ja sen laajennus. Laajennettua algoritmia käytetään myöhemmin salausmenetelmän yhteydessä laskemaan käänteisalkioita jäännösluokissa.
Lukija johdatetaan kryptografiaan salausmenetelmän yleisen määritelmän kautta. Lisäksi annetaan yksinkertainen historiallinen esimerkki salausmenetelmästä, Caesar-salaus. Yleisesti salausmenetelmä on joko symmetrinen tai epäsymmetrinen eli niin sanottu julkisen avaimen salausmenetelmä. Työssä esiteltävä Merklen–Hellmanin salausmenetelmä on epäsymmetrinen, eli tiedon salaamiseen käytetään eri avainta kuin tiedon purkamiseen. Tämä mahdollistaa salausavaimen asettamisen julkiseksi, josta sen nimitys tulee. Julkisen salausmenetelmän salausfunktion pitää olla yksisuuntainen, mikä tarkoittaa sitä, että salausfunktio on helppo laskea mutta sen kääntäminen on vaikeaa. Yksisuuntaisten funktioiden erikoistapauksena esitellään salaovifunktiot, joiden kääntäminen onnistuu helposti jonkin lisätiedon avulla. Tällaiset funktiot ovat keskiössä kryptografiassa. Samalla esitellään myös tässä tutkielmassa käytettäviä merkintöjä, sopimuksia ja muunnoksia, joihin esimerkit perustuvat.
Lopullisen salausmenetelmän määrittelemiseksi perehdytään reppuongelmaan. Reppuongelma on pohjimmiltaan hyvin yleinen optimointiongelma. Esimerkiksi pakattaessa laukkua matkalle voidaan optimoida mukaan otettavat esineet niiden hyödyn ja koon perusteella. Yhteishyöty yritetään maksimoida mutta esineiden on mahduttava matkalaukkuun. Reppuongelmasta on monia variaatioita, joista Merklen–Hellmanin salausmenetelmä hyödyntää osajoukko-ongelmaa. Reppuongelmat ovat NP-täydellisiä ongelmia, mikä tarkoittaa, että ratkaisujen etsiminen laskennallisesti on hyvin raskasta. Tämän takia reppuongelmaa voidaan hyödyntää julkisen salausmenetelmän pohjana. Salauksen purku hyödyntää salaovena erikoistilannetta, jossa esineet on valittu erityisesti kasvavasti, eli jokainen esine on suurempi kuin sitä pienemmät esineet yhteensä. Tällaiseen tilanteeseen esitellään hyvin suoraviivainen ratkaisualgoritmi.
Lopuksi esitellään Merklen–Hellmanin salausmenetelmä, jossa yhdistyvät tutkielman esitiedot ja reppuongelma. Luvussa käydään läpi kattava esimerkki salausmenetelmän käytöstä yksinkertaisessa tilanteessa käyttäen bittejä.
Lukija johdatetaan kryptografiaan salausmenetelmän yleisen määritelmän kautta. Lisäksi annetaan yksinkertainen historiallinen esimerkki salausmenetelmästä, Caesar-salaus. Yleisesti salausmenetelmä on joko symmetrinen tai epäsymmetrinen eli niin sanottu julkisen avaimen salausmenetelmä. Työssä esiteltävä Merklen–Hellmanin salausmenetelmä on epäsymmetrinen, eli tiedon salaamiseen käytetään eri avainta kuin tiedon purkamiseen. Tämä mahdollistaa salausavaimen asettamisen julkiseksi, josta sen nimitys tulee. Julkisen salausmenetelmän salausfunktion pitää olla yksisuuntainen, mikä tarkoittaa sitä, että salausfunktio on helppo laskea mutta sen kääntäminen on vaikeaa. Yksisuuntaisten funktioiden erikoistapauksena esitellään salaovifunktiot, joiden kääntäminen onnistuu helposti jonkin lisätiedon avulla. Tällaiset funktiot ovat keskiössä kryptografiassa. Samalla esitellään myös tässä tutkielmassa käytettäviä merkintöjä, sopimuksia ja muunnoksia, joihin esimerkit perustuvat.
Lopullisen salausmenetelmän määrittelemiseksi perehdytään reppuongelmaan. Reppuongelma on pohjimmiltaan hyvin yleinen optimointiongelma. Esimerkiksi pakattaessa laukkua matkalle voidaan optimoida mukaan otettavat esineet niiden hyödyn ja koon perusteella. Yhteishyöty yritetään maksimoida mutta esineiden on mahduttava matkalaukkuun. Reppuongelmasta on monia variaatioita, joista Merklen–Hellmanin salausmenetelmä hyödyntää osajoukko-ongelmaa. Reppuongelmat ovat NP-täydellisiä ongelmia, mikä tarkoittaa, että ratkaisujen etsiminen laskennallisesti on hyvin raskasta. Tämän takia reppuongelmaa voidaan hyödyntää julkisen salausmenetelmän pohjana. Salauksen purku hyödyntää salaovena erikoistilannetta, jossa esineet on valittu erityisesti kasvavasti, eli jokainen esine on suurempi kuin sitä pienemmät esineet yhteensä. Tällaiseen tilanteeseen esitellään hyvin suoraviivainen ratkaisualgoritmi.
Lopuksi esitellään Merklen–Hellmanin salausmenetelmä, jossa yhdistyvät tutkielman esitiedot ja reppuongelma. Luvussa käydään läpi kattava esimerkki salausmenetelmän käytöstä yksinkertaisessa tilanteessa käyttäen bittejä.
Kokoelmat
- Kandidaatintutkielmat [8745]