Original title: Polynomiální rovnice nad konečnými tělesy a algebraická kryptoanalýza
Translated title: Polynomial equations over finite fields and algebraic cryptanalysis
Authors: Seidl, Jan ; Stanovský, David (advisor) ; Drápal, Aleš (referee)
Document type: Master’s theses
Year: 2014
Language: cze
Abstract: [cze] [eng]
Název práce: Polynomiální rovnice nad konečnými tělesy a algebraická kryptoanalýza Autor: Jan Seidl Katedra: Katedra algebry Vedoucí diplomové práce: doc. RNDr. David Stanovský, Ph.D., Katedra algebry Abstrakt: Předložená práce se zaobírá postupem algebraické kryptoanalýzy, při kterém je nejprve problém prolomení šifry převeden na problém nalezení řešení polynomiální soustavy rovnic a následně je problém nalezení řešení této rovnice převeden na problém SAT. Práce popisuje konkrétně metody, které umožňují převést problém prolomení šifry RC4 na problém SAT. Jed- notlivé metody byly naprogramovány v programovacím jazyce Mathematica a následně aplikovány na RC4 s délkou slova 2, 3. Pro nalezení splnitelného ohodnocení výsledné logické formule byl použit SAT-solver CryptoMiniSAT. V případě RC4 s délkou slova 2 bylo dosaženo nalezení řešení v rozpětí 0,09 až 0,34 sekundy, v případě RC4 s délkou slova 3 pak bylo dosaženo na- lezení řešení v rozpětí 1,10 až 1,23 sekundy. Klíčová slova: RC4, SAT, CryptoMiniSAT 1 Title: Polynomial equations over finite fields and algebraic cryptanalysis Author: Jan Seidl Department: Department of Algebra Supervisor: doc. RNDr. David Stanovský, Ph.D., Department of Algebra Abstract: The present work deals with the procedure of algebraic crypta- nalysis, in which the problem of breaking cipher is at first converted to the problem of finding solutions to polynomial systems of equations and then the problem of finding a solution to this equation is converted to the SAT problem. The work specifically describes the methods that allow you to con- vert the problem of breaking cipher RC4 to the SAT problem. The individual methods were programmed in Mathematica programming language and then applied to RC4 with a word length of 2, 3. For finding of satisfiable evaluation of the resulting logical formula was used SAT-solver CryptoMiniSAT. In case of RC4 with word length 2 the solution was reached in the range from 0.09 to 0.34 second. In case of RC4 with word length 3 the solution was reached in the range from 1.10 to 1.23 second. Keywords: RC4, SAT, CryptoMiniSAT 1
Keywords: CryptoMiniSAT; RC4; SAT; CryptoMiniSAT; RC4; SAT

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/71735

Permalink: http://www.nusl.cz/ntk/nusl-340861


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses