Detail práce
Paralelizace faktorizace celých čísel z pohledu lámání RSA
Práce se zabývá faktorizací celých čísel. Faktorizace je nejznámější a nejpoužívanější metodou kryptoanalýzy RSA. V rámci této práce byla vybrána a implementována faktorizační metoda zvaná SIQS. I když se jedná o nejrychlejší metodu (do 100 dekadických číslic), není možné ji efektivně počítat v polynomiálním čase, a tak se hledají různé možnosti, jak tuto metodu co nejvíce urychlit. Jako první se nabízí paralelizace. K tomuto účelu bylo využito OpenMP. Další možností je optimalizace kódu. Cílem této práce je také ukázat, jak jednoduše lze v mnoha případech využít paralelizace kódu a dále, jak díky podrobné analýze kódu lze dosáhnout poměrně velkého urychlení. Použitá metodika iteračního provádění optimalizací se ukázala jako velmi účinná. Touto metodikou byla implementace SIQS vylepšena tak, že faktorizace byla urychlena až 100-krát, v některých částech kódu dokonce ještě více.
Faktorizace, kvadratické síto, MPQS, SIQS, Pollardova Rho metoda, Fermatova faktorizace, Eliptické křivky, NFS, test prvočíselnosti, paralelizace, OpenMP, kryptoanalýza RSA
Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky přítomných členů komise. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm A.
Balík Miroslav, Ing., Ph.D. (FIT ČVUT), člen
Burget Radek, doc. Ing., Ph.D. (UIFS FIT VUT), člen
Drábek Vladimír, doc. Ing., CSc. (UPSY FIT VUT), člen
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT), člen
Matoušek Petr, doc. Ing., Ph.D., M.A. (UIFS FIT VUT), člen
@mastersthesis{FITMT16961, author = "Dominik Breitenbacher", type = "Diplomov\'{a} pr\'{a}ce", title = "Paralelizace faktorizace cel\'{y}ch \v{c}\'{i}sel z pohledu l\'{a}m\'{a}n\'{i} RSA", school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}", year = 2015, location = "Brno, CZ", language = "czech", url = "https://www.fit.vut.cz/study/thesis/16961/" }