Soluautomaattien käyttö kryptografiassa: uusi Langtonin muurahaiseen perustuva salausalgoritmi
Kivihalme, Vilho (2020-04-07)
Soluautomaattien käyttö kryptografiassa: uusi Langtonin muurahaiseen perustuva salausalgoritmi
Kivihalme, Vilho
(07.04.2020)
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2020041719060
https://urn.fi/URN:NBN:fi-fe2020041719060
Tiivistelmä
Salausta on käytetty tuhansia vuosia piilottamaan arkaluontoisia yksityisiä viestejä vihollisilta, tai miltä tahansa muilta tahoilta, joille viestin viestien sisältöä ei haluta paljastaa. Salauksen käyttötarkoitus on edelleen sama, mutta käyttökohteet ovat yleistyneet arkipäiväisemmiksi. Koko internetin olemassaolon ja toimivuuden ehtona on, että salausmenetelmät ovat tehokkaita ja turvallisia. Internetin välityksellä tehdään paljon yksityisiä asioita, kuten maksetaan laskuja ja kirjaudutaan erilaisiin palveluihin. Internetissä kulkevaa liikennettä voidaan kuitenkin seurata melko helposti, joten on ensiarvoisen tärkeää, että kaikki viestit lähetetään salattuna. Näin esimerkiksi pankkitunnukset ja yksityisviestit kahden henkilön välillä pysyvät ainoastaan kommunikoivien osapuolten tiedossa.
Soluautomaatti on tietojenkäsittelytieteessä tutkittu dynaaminen malli, jossa eräänlaisella ruudukolla simuloidut solut ovat vuorovaikutuksessa keskenään. Vähimmillään soluautomaattina voi ajatella ruutupaperia, jonka solut väritetään mustaksi tai valkoiseksi riippuen siitä, ovatko ne eläviä vai kuolleita. Simulaation aikana solut syntyvät ja kuolevat riippuen niiden lähellä olevien solujen tilasta. Yksinkertaisillakin säännöillä solut muodostavat monimutkaisia rakenteita, kuten toistuvia syklejä, rajatonta ja kiihtyvää laajenemista, sekä itsensä kopioimista.
Langtonin muurahainen on eräänlainen soluautomaatti ja Turingin kone. Muurahainen on ruudukolla liikkuva osoitin, joka liikkuu ruudusta toiseen niiden värien perusteella, vaihtaen ruutujen värejä tarkkaan määriteltyjen sääntöjen perusteella. Tarkoista säännöistä huolimatta muurahaisen liikkeitä ei voi ennustaa etukäteen. Liikkuminen näyttää usein satunnaiselta ja epäsäännölliseltä, mutta tietyillä säännöillä syntyy myös säännöllisiä rakenteita ja usein myös epäsäännöllisesti liikkuvat muurahaiset päätyvät lopulta päättymättömään säännölliseen jaksoon.
Tutkielmassa perehdytään soluautomaattien ja salausalgoritmien perusteisiin esimerkkien avulla, jonka jälkeen tehdään kirjallisuuskatsaus soluautomaattien avulla toteutettuihin salausjärjestelmiin. Tämän jälkeen esitellään uudenlainen Langtonin muurahaisen avulla toteutettu salausjärjestelmä ja pohditaan sen käyttökelpoisuutta ja turvallisuutta. Encryption has been used for thousands of years in order to hide private messages from enemies and any other entities that should not be able to read them. The usage of encryption has remained the same, but the applications have become more mundane. Powerful and secure encryption methods are vital for transferring messages on modern day internet. Money transfer and accessing data in various services are two very common online activities that should remain private. Because internet traffic can be monitored easily, encryption of all communication should be considered almost mandatory.
A cellular automaton is a discrete dynamical system where artificial cells arranged into a regular grid interact with each other. Simplest example would be a grid paper where black and white squares represent dead and alive cells. During a simulation certain cells die, and new cells are born depending on the state of adjacent cells. Even the simplest rules can cause complex behavior like repeating cycles, infinite and accelerating growth and self-replication.
Langton's ant is a cellular automaton and a Turing machine. The ant is a pointer that moves on a regular grid depending on the color of the cell it occupies, changing the colors as it moves. Even though the color changing rules of are known, it is impossible to predict how the ant moves. While the moving is usually irregular and almost random-like, with certain rules the ant can also produce regular patterns. Often the irregularly moving ants also transition to regular infinite period of moves.
This thesis covers the basics of cryptography and cellular automata using various examples. This is followed by a survey of existing encryption algorithms that are based on cellular automata. Finally, a novel encryption algorithm that is based on Langton's ant is presented and analyzed in terms of usability and security.
Soluautomaatti on tietojenkäsittelytieteessä tutkittu dynaaminen malli, jossa eräänlaisella ruudukolla simuloidut solut ovat vuorovaikutuksessa keskenään. Vähimmillään soluautomaattina voi ajatella ruutupaperia, jonka solut väritetään mustaksi tai valkoiseksi riippuen siitä, ovatko ne eläviä vai kuolleita. Simulaation aikana solut syntyvät ja kuolevat riippuen niiden lähellä olevien solujen tilasta. Yksinkertaisillakin säännöillä solut muodostavat monimutkaisia rakenteita, kuten toistuvia syklejä, rajatonta ja kiihtyvää laajenemista, sekä itsensä kopioimista.
Langtonin muurahainen on eräänlainen soluautomaatti ja Turingin kone. Muurahainen on ruudukolla liikkuva osoitin, joka liikkuu ruudusta toiseen niiden värien perusteella, vaihtaen ruutujen värejä tarkkaan määriteltyjen sääntöjen perusteella. Tarkoista säännöistä huolimatta muurahaisen liikkeitä ei voi ennustaa etukäteen. Liikkuminen näyttää usein satunnaiselta ja epäsäännölliseltä, mutta tietyillä säännöillä syntyy myös säännöllisiä rakenteita ja usein myös epäsäännöllisesti liikkuvat muurahaiset päätyvät lopulta päättymättömään säännölliseen jaksoon.
Tutkielmassa perehdytään soluautomaattien ja salausalgoritmien perusteisiin esimerkkien avulla, jonka jälkeen tehdään kirjallisuuskatsaus soluautomaattien avulla toteutettuihin salausjärjestelmiin. Tämän jälkeen esitellään uudenlainen Langtonin muurahaisen avulla toteutettu salausjärjestelmä ja pohditaan sen käyttökelpoisuutta ja turvallisuutta.
A cellular automaton is a discrete dynamical system where artificial cells arranged into a regular grid interact with each other. Simplest example would be a grid paper where black and white squares represent dead and alive cells. During a simulation certain cells die, and new cells are born depending on the state of adjacent cells. Even the simplest rules can cause complex behavior like repeating cycles, infinite and accelerating growth and self-replication.
Langton's ant is a cellular automaton and a Turing machine. The ant is a pointer that moves on a regular grid depending on the color of the cell it occupies, changing the colors as it moves. Even though the color changing rules of are known, it is impossible to predict how the ant moves. While the moving is usually irregular and almost random-like, with certain rules the ant can also produce regular patterns. Often the irregularly moving ants also transition to regular infinite period of moves.
This thesis covers the basics of cryptography and cellular automata using various examples. This is followed by a survey of existing encryption algorithms that are based on cellular automata. Finally, a novel encryption algorithm that is based on Langton's ant is presented and analyzed in terms of usability and security.