Vis enkel innførsel

dc.contributor.authorAmundsen, Jens-Are
dc.date.accessioned2011-01-07T11:57:48Z
dc.date.available2011-01-07T11:57:48Z
dc.date.issued2010
dc.identifier.urihttp://hdl.handle.net/11250/143930
dc.description.abstractENGELSK: Solving systems of multivariate polynomial equations is hard, even NP-hard in the general case. The method of Göbner bases can be used to solve such systems, and thus has a running time complexity at least that of solving systems of polynomial equations. The running time complexity is often expressed as exponential in D, where D is the largest degree of a polynomial during computation. Even though the method of Gröbner bases belongs to the complexity class PSPACE for zero-dimensional ideals, it still implies a need for huge amounts of computer memory. Computational algebra systems utilizing Gröbner bases algorithms are well known to crash during computation due to a lack of computer memory. In this thesis we investigate the use of d-truncated Gröbner bases over a Boolean ring, applied to systems of equations induced from symmetric ciphers. A Gröbner basis algorithm based on Buchbergers Homogeneous Algorithm is implemented, and we apply this algorithm on systems of equations induced from the ciphers LILI-128 and KASUMI. We show that we can solve a system of equations, induced from 3 rounds KASUMI, in over 9000 unknowns using 3-truncated Gröbner bases in both reasonable time and reasonable amounts of computer memory. For systems of equations induced from LILI-128, using 4-truncated Gröbner bases, we experienced an exponential increase in the number of output bits needed for finding a solution.en_US
dc.description.abstractNORSK: Å løse systemer av ikke-lineære polynomer i flere variable er et vanskelig problem, og det generelle problemet tilhører klassen av NP-komplette problemer. Gröbner baser kan benyttes for å løse slike ligningssystemer, og har dermed minst like høy tids kompleksitet. Tids kompleksiteten for konstruksjon av Gröbner baser er ofte gitt som eksponentiell i D, der D er graden til det største polynomet under eksekvering. Selv om konstruksjon av Gröbner baser tilhører kompleksitetsklassen PSPACE for 0-dimensjonale ideal, betyr det allikevel at det vil være behov for store mengder dataminne. Systemer for symbolsk beregning av algebraiske problemer som bruker Gröbner base metoder er kjent for å krasje på grunn av minne problemer. I dette prosjektet undersøker vi bruk av d-begrensede Gröbner baser over boolske ringer, og anvender det på systemer av ikke-lineære polynomligninger som beskriver symmetriske krypto algoritmer. En Gröbner base algoritme, basert på Buchbergers Homogene algoritme, er implementert og vi anvender denne på systemer av ligninger fra krypto algoritmene LILI-128 og KASUMI. Vi viser at det er mulig å løse ligningssystemer fra 3 runder KASUMI med over 9000 variable på overkommelig tid og overkommelig bruk av dataminne. For ligningssystemer fra LILI-128, der 4-begrensede Gröbner baser er benyttet, fant vi en eksponentiell økning i antallet ut bits som behøves for å løse ligningssystemene.en_US
dc.language.isoengen_US
dc.subjectinformasjonssikkerheten_US
dc.subjectGöbner basesen_US
dc.subjectsymmetric ciphersen_US
dc.titleThe use of d-truncated Gröbner bases in cryptanalysis of symmetric ciphersen_US
dc.typeMaster thesisen_US
dc.subject.nsiVDP::Mathematics and natural science: 400::Information and communication science: 420::Security and vulnerability: 424en_US
dc.source.pagenumberXV, 90 s.en_US


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel