Thesis Details

Paralelizace faktorizace celých čísel z pohledu lámání RSA

Master's Thesis Student: Breitenbacher Dominik Academic Year: 2014/2015 Supervisor: Homoliak Ivan, Ing., Ph.D.
English title
Parallelization of Integer Factorization from the View of RSA Breaking
Language
Czech
Abstract

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

Factorization, Quadratic sieve, MPQS, SIQS, Pollard Rho method, Fermat factorization, Elliptic curves, NFS, primality test, parallelization, OpenMP, RSA cryptoanalysis

Department
Department of Intelligent Systems FIT BUT
Degree Programme
Information Technology, Field of Study Information Technology Security
Files
Status
defended, grade A
Date
19 June 2015
Reviewer
Henzl Martin, Ing. Mgr.
Committee
Hanáček Petr, doc. Dr. Ing. (DITS FIT BUT), předseda
Balík Miroslav, Ing., Ph.D. (FIT CTU), člen
Burget Radek, doc. Ing., Ph.D. (DIFS FIT BUT), člen
Drábek Vladimír, doc. Ing., CSc. (DCSY FIT BUT), člen
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT), člen
Matoušek Petr, doc. Ing., Ph.D., M.A. (DIFS FIT BUT), člen
Citation
BREITENBACHER, Dominik. Paralelizace faktorizace celých čísel z pohledu lámání RSA. Brno, 2015. Master's Thesis. Brno University of Technology, Faculty of Information Technology. 2015-06-19. Supervised by Homoliak Ivan. Available from: https://www.fit.vut.cz/study/thesis/16961/
BibTeX 
@mastersthesis{FITMT16961,
    author = "Dominik Breitenbacher",
    type = "Master's thesis",
    title = "Paralelizace faktorizace cel\'{y}ch \v{c}\'{i}sel z pohledu l\'{a}m\'{a}n\'{i} RSA",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2015,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/16961/"
}

Theses

Back to top