Detail publikace

Parallelized Self-Initializing Quadratic Sieve using OpenMP

BREITENBACHER, D.; HOMOLIAK, I.; HANÁČEK, P. Parallelized Self-Initializing Quadratic Sieve using OpenMP. Santa's Crypto Get-Together 2015. Praha: Trusted Network Solutions, a.s., 2015. p. 39-40. ISBN: 978-80-904257-7-4.
Název česky
Paralelizované Self-Initializing Quadratic Sieve užitím OpenMP
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Breitenbacher Dominik, Ing.
Homoliak Ivan, Ing., Ph.D. (UITS)
Hanáček Petr, doc. Dr. Ing. (UITS)
Klíčová slova

Factorization, SIQS, Parallelization, OpenMP, RSA Cryptanalysis, Profilation

Abstrakt

Tato práce se zabývá faktorizací celých čísel. Faktorizace je velmi známou a používanou metodou pro RSA kryptoanalýzu. V rámci tohoto článku byla jako faktorizační metoda vybrána metoda SIQS (Self-Initializing Quadratic Sieve). Tato metoda byla vybrána na základě náročnosti k naučení a naprogramování a na základě její rychlosti faktorizace. Metoda QS (Quadratic sieve) je obecně považována za druhou nejrychlejší faktorizační metodu a nejrychlejší metodou pro faktorizaci čísel o 100 dekadických číslicích (332 bitů) a méně. Metoda SIQS je nejvíce optimalizovanou verzí QS. Metoda byla v rámci této práce implementována a podrobně zdokumentována, čímž se práce snaží vyplnit mezeru mezi teoretickým popisem metody a jejími stávajícími implementacemi. Přestože SIQS je nejrychlejší metodou do 100 dekadických číslic, není schopna efektivně pracovat v polynomiálním čase. Proto je nutné hledat možnosti, jak tuto metodu co nejvíce urychlit. Nabízí se dvě možnosti, jak toho dosáhnout. Jednou z nich je paralelizace, druhou pak optimalizace. Obě možnosti byly využity v rámci této práce. Pro paralelizaci metody je použito OpenMP. Cílem této práce je ukázat, jak lze využitím paralelizace a detailní analýzou kódu s optimalizací dosáhnout značného urychlení. Metoda iterativní optimalizace se ukázala jako velice efektivní nástroj. Použitím této metody byla až 100x urychlena implementace SIQS oproti referenční verzi a v některých částech kódu dokonce ještě více.

Rok
2015
Strany
39–40
Sborník
Santa's Crypto Get-Together 2015
ISBN
978-80-904257-7-4
Vydavatel
Trusted Network Solutions, a.s.
Místo
Praha
BibTeX 
@inproceedings{BUT119931,
  author="Dominik {Breitenbacher} and Ivan {Homoliak} and Petr {Hanáček}",
  title="Parallelized Self-Initializing Quadratic Sieve using OpenMP",
  booktitle="Santa's Crypto Get-Together 2015",
  year="2015",
  pages="39--40",
  publisher="Trusted Network Solutions, a.s.",
  address="Praha",
  isbn="978-80-904257-7-4"
}
Nahoru