search query: @keyword kryptologia / total: 1
reference: 1 / 1
« previous | next »
Author: | Hänninen, Aleksi |
Title: | Boolean satisfiability problem and cryptography |
Lauselogiikan toteutuvuusongelma kryptologiassa | |
Publication type: | Master's thesis |
Publication year: | 2008 |
Pages: | viii + 60 Language: eng |
Department/School: | Informaatio- ja luonnontieteiden tiedekunta |
Main subject: | Tietojenkäsittelyteoria (T-79) |
Supervisor: | Nyberg, Kaisa |
Instructor: | Nyberg, Kaisa |
OEVS: | Electronic archive copy is available via Aalto Thesis Database.
Instructions Reading digital theses in the closed network of the Aalto University Harald Herlin Learning CentreIn the closed network of Learning Centre you can read digital and digitized theses not available in the open network. The Learning Centre contact details and opening hours: https://learningcentre.aalto.fi/en/harald-herlin-learning-centre/ You can read theses on the Learning Centre customer computers, which are available on all floors.
Logging on to the customer computers
Opening a thesis
Reading the thesis
Printing the thesis
|
Location: | P1 Ark Aalto 8652 | Archive |
Keywords: | trivium cryptography boolean satisfiability (SAT) problem SAT solver nonlinear binary equations Gaussian elimination kryptologia lauselogiikan toteutuvuusongelma SAT -ratkaisija epälineaariset binäärilukuyhtälöt Gaussin eliminaatio |
Abstract (fin): | Tässä diplomityössä tutkitaan lauselogiikan toteutuvuusongelman (SAT -ongelman) ja sen ratkaisijoiden soveltamista kryptologiaan. Ensin aiempia SAT -ongelman sovelluksia kryptologiaan esitetään lyhyesti. Ne voidaan luokitella seuraaviin kategorioihin: SAT - pohjainen salaus, SAT -pohjainen suora hyökkäys, SAT - ratkaisijoihin perustuva sivukanavahyökkäys, SAT -ratkaisijoita apunaan käyttävä hyökkäys ja looginen kryptosysteemien varmennus. Jonosalain Trivium, yksi ECRYPT:in eStream cipher -projektin kandidaatti, esitetään, joitain sen suunnitteluperusteita mainitaan ja sen muutamia ominaisuuksia lasketaan. SAT - ratkaisijoiden toimintaperiaatteita kuvataan, samoin kuin keino muuntaa hyökkäys Triviumia vastaan SAT -ongelmaksi. Tavoitteenamme on analysoida teoreettisesti kuinka SAT -ratkaisija ratkaisee samankaltaisia ongelmia ja kuinka hyökkäyksessä olevat parametrit tulee asettaa. Erilaisten Triviumia vastaan tehtyjen suorien hyökkäysten tulokset esitetään ja tutkitaan. Pienin löytämämme kompleksisuus on luokkaa 263 sekuntia, mikä saadaan tavallisella (ei sisäisen tilan) suoralla hyökkäyksellä. Kompleksisuus avaimen etsimiselle brute force -menetelmällä on 280. Syyksi huonoon menestykseen esitämme Triviumin loogisen piirin rakennetta. Siinä ominaista on suhteellisen pientä tuloporttien määrää, kompleksista rakennetta, jota ei voi tehdä yksinkertaisemmaksi tai jakaa pienemmiksi ongelmiksi. Nämä ominaisuudet ovat läsnä ongelmassa, ja osoitamme, että SAT -ratkaisijat etsivät tällöin ratkaisua tekemällä enimmäkseen päätöksiä tuloporteilla, mikä vastaa likimäärin brute force -hyökkäystä. Lopuksi ehdotamme uutta SAT -pohjaista algoritmia, joka yhdistää Gaussin eliminaation SAT -ratkaisijaan. Algoritmin pääajatus on lineaarisesti approksimoida epälineaarisia termejä. Tämän jälkeen joukko lineaarisia yhtälöitä saadaan aikaiseksi approksimaatioita käyttämällä, joista voimme saada joukon rajoituksia käytettäville approksimaatioille. Lopuksi voimme antaa uudet rajoitukset SAT -ratkaisijalle, joka etsii uudet approksimaatiot, jotka toteuttavat kaikki edelliset rajoitteet. Tätä jatketaan, kunnes joko löydetään oikeat approksimaatiot, jolloin myös ratkaisu voidaan saada, tai sitten rajoitukset, ja siten koko ongelma, löydetään toteutumattomaksi. |
ED: | 2008-05-19 |
INSSI record number: 35607
+ add basket
« previous | next »
INSSI