search query: @keyword cryptography / total: 20
reference: 3 / 20
« 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 Centre

In 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

  • Aalto University staff members log on to the customer computer using the Aalto username and password.
  • Other customers log on using a shared username and password.

Opening a thesis

  • On the desktop of the customer computers, you will find an icon titled:

    Aalto Thesis Database

  • Click on the icon to search for and open the thesis you are looking for from Aaltodoc database. You can find the thesis file by clicking the link on the OEV or OEVS field.

Reading the thesis

  • You can either print the thesis or read it on the customer computer screen.
  • You cannot save the thesis file on a flash drive or email it.
  • You cannot copy text or images from the file.
  • You cannot edit the file.

Printing the thesis

  • You can print the thesis for your personal study or research use.
  • Aalto University students and staff members may print black-and-white prints on the PrintingPoint devices when using the computer with personal Aalto username and password. Color printing is possible using the printer u90203-psc3, which is located near the customer service. Color printing is subject to a charge to Aalto University students and staff members.
  • Other customers can use the printer u90203-psc3. All printing is subject to a charge to non-University members.
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