Detail publikace
Parallelized Self-Initializing Quadratic Sieve using OpenMP
Homoliak Ivan, doc. Ing., Ph.D. (UITS)
Hanáček Petr, doc. Dr. Ing. (UITS)
Factorization, SIQS, Parallelization, OpenMP, RSA Cryptanalysis, Profilation
Tato práce se zabývá faktorizací celých čísel.Faktorizace je velmi známou a používanou metodoupro RSA kryptoanalýzu. V rámci tohoto článku byla jako faktorizační metodavybrána metoda SIQS (Self-Initializing Quadratic Sieve). Tato metoda bylavybrá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 zadruhou 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íceoptimalizovanou 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 popisemmetody 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. Proparalelizaci metody je použito OpenMP. Cílem této práce je ukázat, jak lzevyužitím paralelizace a detailní analýzou kódu s optimalizací dosáhnoutznačného urychlení. Metoda iterativní optimalizace se ukázala jako veliceefektivní nástroj. Použitím této metody byla až 100x urychlena implementaceSIQS oproti referenční verzi a v některých částech kódu dokonce ještě více.
@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"
}