Original title: Paralelizace faktorizace celých čísel z pohledu lámání RSA
Translated title: Parallelization of Integer Factorization from the View of RSA Breaking
Authors: Breitenbacher, Dominik ; Henzl, Martin (referee) ; Homoliak, Ivan (advisor)
Document type: Master’s theses
Year: 2015
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
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. This paper follows up the factorization of integers. Factorization is the most popular and used method for RSA cryptoanalysis. The SIQS was chosen as a factorization method that will be used in this paper. Although SIQS is the fastest method (up to 100 digits), it can't be effectively computed at polynomial time, so it's needed to look up for options, how to speed up the method as much as possible. One of the possible ways is paralelization. In this case OpenMP was used. Other possible way is optimalization. The goal of this paper is also to show, how easily is possible to use paralelizion and thanks to detailed analyzation the source codes one can reach relatively large speed up. Used method of iterative optimalization showed itself as a very effective tool. Using this method the implementation of SIQS achieved almost 100 multiplied speed up and at some parts of the code even more.
Keywords: Elliptic curves; Factorization; Fermat factorization; MPQS; NFS; OpenMP; parallelization; Pollard Rho method; primality test; Quadratic sieve; RSA cryptoanalysis; SIQS; Eliptické křivky; Faktorizace; Fermatova faktorizace; kryptoanalýza RSA; kvadratické síto; MPQS; NFS; OpenMP; paralelizace; Pollardova Rho metoda; SIQS; test prvočíselnosti

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/52229

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


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