Blog

Témata:

16. 2. 2026

Bezpečnost Kryptografie

Porovnání digitálních a kvantových počítačů, část 2: Faktorizace

Každého v oblasti IT zajímá, jak velkou hrozbou pro kryptografii jsou kvantové počítače a jak se s daným problémem vyrovnat. Tato série článků se snaží populární formou tento problém vysvětlit. Po Úvodu se můžeme podívat na problém faktorizace.

Algoritmus RSA a problém faktorizace

Začneme problémem faktorizace. Nejlepší způsob, jak zaútočit na tento algoritmus poskytuje takzvané GNFS (General Number Field Sieve – tedy obecné celočíselné síto). To poskytuje seznam dvojic čísel. Pokud tato čísla vzájemně vynásobíme, měli by jsme získat požadovaný součin. Následně je potřeba uvedené číselné dvojice otestovat na jejich prvočíselnost. Pokud chceme zjistit přibližný počet operací, potřebujeme znát složitost vlastního GNFS algoritmu, kterou je možné dopočítat na základě informací o délce n faktorizovaného čísla. Tuto délku uvádíme v bitech.

$M(n) \approx \left( 8 \bullet \exp\left( 3,4 \bullet n^{\frac{1}{3}} \bullet \left( \ln n \right)^{\frac{2}{3}} \right) \right)$

Důležitou součástí je zjištění počtu číselných dvojic. Tento údaj je zpravidla v jednotkách dvojic, výjimkou je situace, kdy by při generování z nějakého důvodu selhalo ověření prvočíselnosti. Tedy tento údaj pracuje jako jakýsi indikátor. Uvedený indikátor na základě dalších testů může upozornit například na nevhodnou volbou testovacího algoritmu. Tedy v ideálním případě získáme jeden jeden výsledek, případně výsledků pět. Pokud jich je více než deset, pravděpodobně došlo někde k selhání a je vhodné zkontrolovat celý mechanismus.
V jakémkoliv z těchto případů následuje test prvočíselnost předpokládaných dvojic. Protože je počet testů nízký, nedochází k výrazné změně složitosti. Důležitá je ale správná volba testovacích algoritmů. Z použitelných se jedná o následující:

AKS (Agrawal–Kayal–Saxena primality test, cyclotomic AKS test), který se z důvodu vysoké výpočetní náročnosti používá jenom u menších bitových rozsahů. Pro čísla nad 256b je tento test nepraktický. Výhodou je jeho deterministický výstup, test má složitostí přibližně O(n⁶)
Baillie-PSW je založen na testu Miller-Rabin a doplňkovém Lukasově testu. Nemá omezení rozsahu, jedná se o heuristický test se složitostí přibližně O(n log n log[log n]).
ECPP (Elliptic Curve Primality Proving/Elliptic Curve Primality testing) testy jsou založené na práci Shafi Goldwassera a jsou použitelné do rozsahu 10⁵+1 bit. Jedná se opět o deterministický test se složitostí O(n⁴)
Miller-Rabin je pravděpodobnostní test, použitelný s klíči zhruba do velikosti 4kb. Problémem je pravděpodobnostní výstup, pro zajištění odpovídající průkaznosti je nutné realizovat vyšší desítky testů. Zpravidla se používá 40-100 průchodů, celková složitost algoritmu je O(kn log²n log[log n]) kde k je počet bází.

Víme tedy, kolik je potřeba logických operací, ale jak uvedené převést na instrukce pro 64b CPU? Na základě požadavků je potřeba vyřešit tvorbu matice (120 instrukcí na jeden krok) a následně analýza obsahu matice (5 instrukcí na jeden krok). Poté se musí výsledky otestovat na prvočíselnost. Tento výpočet platí pro čísla, která se vejdou do registrů procesoru. Jakmile jsou prvočísla větší, začíná se výpočet komplikovat. Samozřejmě obdobným způsobem narůstá počet operací pro tvorbu a nepatrně i pro analýzu matice. Z toho je možné přibližně určit celkový počet instrukcí.
Obdobným způsobem můžeme hledat i celkovou náročnost na paměť. Rozsah paměti potřebné pro tvorbu GNFS matice je přibližně:

$M(n) \approx \left( 8 \bullet \exp\left( 3,4 \bullet n^{\frac{1}{3}} \bullet \left( \ln n \right)^{\frac{2}{3}} \right) \right)$

Na základě uvedených přibližných výpočtů máme odhady, které můžeme použít pro výpočty potřebného strojového času, k tomu vztaženému příkonu a objemu paměti potřebnému ke splnění zadaného úkolu. Úkolem bude faktorizace klíče s cílem zjistit, co je v silách jednotlivců, organizací nebo naší civilizace, případně co je zcela mimo naše možnosti. Pro vlastní výpočet budeme uvažovat hypotetický počítač s 10 jádry na frekvenci 1GHz, bez hyperthreadingu, příkon tohoto počítače bude ideálních 100 W. Na základě předchozích informací pak vychází:

n-bit	Složitost	Faktorizace	Instrukcí	Paměť (B)	Doba (roků)	Energie (J)
512	2^75.2	1.757∙10¹⁹	2.19∙10²¹	6.75∙10¹²	6.96∙10⁵	2.19∙10¹⁵
1024	2^101.6	1.316∙10²⁶	1.64∙10²⁸	2.58∙10¹⁷	5.21∙10¹²	1.64∙10²²
2048	2^136.4	1.533∙10³⁵	1.91∙10³⁷	2.86∙10²³	6.07∙10²¹	1.91∙10³¹
2540	2^149.3	3.527∙10³⁸	4.40∙10⁴⁰	4.99∙10²⁵	1.39∙10²⁵	4.40∙10³⁵
3072	2^161.7	5.805∙10⁴¹	7.25∙10⁴³	6.95∙10²⁷	2.30∙10²⁸	7.25∙10³⁷
4096	2^182.2	1.289∙10⁴⁷	1.61∙10⁴⁹	2.55∙10³¹	5.11∙10³³	1.61∙10⁴³
7168	2^229.3	2.539∙10⁵⁹	3.17∙10⁶¹	4.01∙10³⁹	1.00∙10⁴⁶	3.17∙10⁵⁵
8192	2^242.1	5.708∙10⁶²	7.13∙10⁶⁴	6.88∙10⁴¹	2.26∙10⁴⁹	7.13∙10⁵⁸
13550	2^296.9	1.178∙10⁷⁷	1.47∙10⁷⁹	2.40∙10⁵¹	4.66∙10⁶³	1.47∙10⁷³
37100	2^444.2	3.952∙10¹¹⁵	4.94∙10¹¹⁷	1.16∙10⁷⁷	1.56∙10¹⁰²	4.94∙10¹¹¹
76608	2^591.4	1.342∙10¹⁵⁴	1.67∙10¹⁵⁶	5.64∙10¹⁰²	5.32∙10¹⁴⁰	1.67∙10¹⁵⁰

Bohužel realita bude extrémně odlišná. Pokud nebude stačit paměť, bude přístup k datům v průběhu výpočtu zpomalen z důvodu potřeby přístupu k úložišti dat. Jedná se o rozšíření v řádu 10³ pro NVMe disky, 10⁴ pro SSD disky a 10⁷ pro HDD – točivé disky. Přitom paměť v řádu TB je potřeba už pro samotné 512b číslo. Samotné paměti mají spotřebu, která odpovídá dalším cca 100 W na 1,5 TB. To odpovídá drobnému zvýšení příkonu na desetinných místech. Dále, zvláště při analýze matice, která má obrovskou velikost, se data nevejdou do cache paměti procesoru. To vede k takzvaným cache-miss, tedy jedná se o paměťově intenzivní operace. Jenže jakýkoliv takový přístup potřebuje znovu načíst obsah paměti do cache, spolu s problémy s predikcí skoků v kódu (branch prediction) to bude znamenat ztrátu zhruba 200 cyklů. V tuto dobu nebudou prováděny žádné výpočty. Celkově tak může dojít ke zpomalení o zhruba o 5 řádů (10⁵ až 10⁹ dle použitých technologií).
Jsme schopní takový útok provést? Můžeme to vzít z několika hledisek:

Pokud budeme uvažovat čas a schopnost vyrobit dostatečné množství počítačů? Společnosti Intel a AMD za celou svou historii (můžeme uvažovat 50 let) vyrobili odhadem miliardy procesorů, tedy pohybujeme se v řádu 10⁹. Protože první procesory měly po několik dekád jedno jádro a až po roce 2006 došlo k využívání více jader, je možné uvažovat střed 2,5 jádra na procesor. Uvažovaný dostupný výkon odpovídajícím způsobem sníží čas, ale v celkovém rozsahu tento výkon spíše odstraní drobný výkyv, způsobený problémy s dostupností velkých dat v cache procesoru.
Pokud budeme uvažovat čistě jenom čas, tak vesmír vznikl před 18 miliardami let. To odpovídá řádu 10¹⁰, tedy nejsme schopní takový výpočet provést dostatečně rychle.
Pokud uvažujeme čistě jenom potřebný příkon, můžeme uvažovat následovně. Celá lidská civilizace měla v roce 2025 elektrický příkon okolo 30 000 TWh, tedy v řádu 10¹⁶ Wh. Slunce nám poskytuje zdroj s výkonem 10¹⁷ W (co přijímáme na zemském povrchu), takže pokud bychom chtěli zmrznout, můžeme uvedenou energii použít. V případě zapřažení celého slunce se bavíme o zdroji s výkonem 10²⁶ W. Centrální černá díra naší galaxie pak je schopná poskytnout 10²⁹ W a celá galaxie zhruba 10³⁷ W. Je vidět, že ani tyto zdroje nejsou dostatečné.

Pokračování bude v části Algoritmy využívající problém diskrétního logaritmu

Reference:

Sage Math script - Faktorizace RSA
Zdroj: https://cryptosession.info/ke-stazeni
A Tale of Two Sieves
Zdroj: https://www.ams.org/
On Polynomila Selection for the General Number Field Sieve
Zdroj: https://www.ams.org/

Autor článku:

Jan Dušátko

Jan Dušátko se počítačům a počítačové bezpečnosti věnuje již skoro čtvrt století. V oblasti kryptografie spolupracoval s předními odborníky např. s Vlastimilem Klímou, či Tomášem Rosou. V tuto chvíli pracuje jako bezpečnostní konzultant, jeho hlavní náplní jsou témata související s kryptografií, bezpečností, e-mailovou komunikací a linuxovými systémy.

1. Úvodní ustanovení

1.1. Tyto všeobecné obchodní podmínky jsou, není-li ve smlouvě písemně dohodnuto jinak, nedílnou součástí všech smluv týkajících školení, pořádaných nebo poskytovaných školitelem, Jan Dušátko, IČ 434 797 66, DIČ 7208253041, se sídlem Pod Harfou 938/58, Praha 9, zapsané u Úřadu městské části Praha 9 (dále jen „školitel“).
1.2. Smluvními stranami ve všeobecných obchodních podmínkách jsou míněni školitel a objednatel, kdy objednatel může být zároveň zprostředkovatelem smluvního vztahu.
1.3. Záležitosti, které nejsou upravené těmito obchodními podmínkami, se řeší podle Občanského zákoníků, tj. zákon č. 89/2012 Sb.

2. Vznik smlouvy přihlášením ke kurzu

2.1. Přihláškou se rozumí jednostranný úkon objednatele adresovaný školiteli prostřednictvím datové schránky s identifikací euxesuf, e-mailu na adresu register@cryptosession.cz nebo register@cryptosession.info, internetových stránek cryptosession.cz, cryptosession.info nebo kontaktním telefonem +420 602 427 840.
2.2. Odesláním přihlášky objednatel souhlasí s těmito všeobecnými podmínkami a prohlašuje, že se s nimi seznámil.
2.3. Přihláška se považuje za přijatou momentem potvrzení (stadnardně do 2 pracovních dní) školitelem nebo zprostředkovatelem. Toto potvrzení je zasláno do datové schránky nebo na kontaktní e-mail.
2.4. Standardní doba pro přihlášení je nejpozději 14 pracovních dní před konáním vzdělávací akce, pokud není uvedeno jinak. V případě fyzické nepodnikající osoby musí být objednávka alespoň 28 pracovních dní před konáním vzdělávací akce.
2.5. Na jednu přihláškou lze přihlásit i více než jednoho účastníka.
2.6. Pokud je více než 10 účastníků od jednoho objednatele, je možné se domluvit na školení v místě sídla zprostředkovatele nebo objednatele.
2.7. Přihlášky jsou přijímány a zpracovávány v pořadí, v jakém došly poskytovateli. Poskytovatel neprodleně informuje objednatele o všech skutečnostech. Těmi se míní naplnění kapacity, příliš nízký počet účastníků, nebo jiný závažný důvod, jako je nemoc lektora nebo zásah vyšší moci. Objednateli bude v tomto případě nabídnut nový termín, případně účast na jiné vzdělávací akci. V případě, že objednatel nebude s přesunutím či účastí na jiné nabídnuté vzdělávací akci souhlasit, poskytovatel mu vrátí účastnický poplatek. Nedostatečný účastníků je oznámen objednateli alespoň 14 dní před začátkem plánovaného termínu.
2.8. Smlouva mezi poskytovatelem a objednatelem vzniká odesláním potvrzení poskytovatelem objednateli.
2.9. Smlouvu lze změnit nebo zrušit pouze za splnění zákonných předpokladů a pouze písemně.

3. Zánik smlouvy zrušením přihlášky

3.1. Přihláška může být objednatelem zrušena pomocí e-mailu, nebo pomocí datové schránky.
3.2. Zákazník má právo stornovat svoji přihlášku na kurz 14 dní před konáním kurzu bez jakýchkoliv poplatků. Pokud se jedná o kratší dobu, dochází k následné změně. V intervalu 7-13 dní je účtován administrativní poplatek 10%, storno účasti v kratším intervalu než 7 dní pak poplatek 25%. V případě storna přihlášky nebo objednávky ze strany zákazníka je nabízena možnost účasti zákazníka v náhradním termínu bez dalšího poplatku. Právo na zrušení přihlášky zaniká realizací objednaného školení.
3.3. Při zrušení přihlášky školitelem náleží objednateli plná náhrada za neuskutečněnou akci.
3.4. Objednatel má právo žádat náhradní termín nebo náhradní školení. V takovém případě bude objednatel informován o všech otevřených kurzech. Náhradní termín si nelze vymáhat ani vynucovat, závisí na aktuální dostupnosti kurzu. Pokud má náhradní školení nižší cenu, objednatel doplatí rozdíl. Pokud má náhradní školení nižší cenu, školitel vrátí rozdíl cen školení objednateli.

4. Cena a platební podmínky

4.1. Odesláním přihlášky objednatel akceptuje smluvní cenu (dále jen účastnický poplatek) uvedenou u daného kurzu.
4.2. V případě více účastníků přihlášených jednou přihláškou je možná sleva.
4.3. Účastnický poplatek musí být uhrazen na bankovní účet společnosti vedený u Komerční banky č. 78-7768770207/0100. Při platbě je nutné uvést variabilní symbol, který je uveden na faktuře, odeslané objednateli školitelem.
4.4. Účastnický poplatek zahrnuje náklady poskytovatele včetně školicích materiálů. Poskytovatel je plátce DPH.
4.5. Účastnický poplatek je objednatel povinen uhradit do 14 pracovních dní od přijetí faktury, pokud nebylo samostatnou smlouvou uvedeno jinak.
4.6. Pokud se přihlášená osoba neúčastní školení a nedošlo k jiné domluvě, je její neúčast považována za storno příhlášku v intervalu kratším než 7 dní, tj. školiteli náleží odměna ve výši 25% z ceny kurzu. Přeplatek je vrácen do 14 dní na platební účet odesílatele, ze kterého byly prostředky odeslány. Platba na jiné číslo účtu není možná.
4.7. Nejdéle do 5 pracovních dní od začátku školení bude školitelem vystavena faktura, která bude dle dohody odeslána e-mailem nebo datovou schránkou.

5. Podmínky školení

5.1. Školitel je povinnen informovat objednatele 14 dní dopředu o místě a času školení, včetně termínu zahájení a ukončení denního programu.
5.2. Pokud objednatel není studentem kurzu, je povinnen zajistit distribuci těchto informací koncovým účastníkům. Za nesplnění těchto podmínek školitel nenese odpovědnost.
5.2. Standardně školení probíhá v čase od 9:00 do 17:00 na předem určeném místě.
5.3. Školitel může být dle aktuálních podmínek k dispozici od 8:00 do 9:00 a následně od 17:00 do 18:00 pro dotazy účastníků.
5.4. Na konci školení je koncovým uživatelům předán certifikát o absolovování.
5.5. Na konci školení koncoví uživatelé vyhodnocují přístup lektora a mají se vyjádřit k ohodnocení jeho prezentace, způsobu přednesení a ohodnotit významn poskytnutých informací.

6. Reklamace

6.1. Pokud je účastník hrubě nespokojen s průběhem kurzu, je školitel o této informaci vyrozuměn.
6.2. Důvody nespokojenosti jsou ten samý den zapsány do protokolu ve dvou kopiích. Jedna je předána objednateli a jednu má školitel.
6.3. Vyjádření k reklamaci bude podáno e-mailem do dvou týdnů. Následně do jednoho týdne bude domluven způsob řešení.
6.4. Nespokojenost zákazníka může být důvodem k rozvázání další spolupráce, nebo finanční kompenzaci až do výše ceny školení po odečtení nákladů.

7. Autorská práva k poskytnutým materiálům

7.1. Školicí materiály poskytnuté školitelem v rámci konání školení splňují znaky autorského díla dle zákona č. 121/2000 Sb.
7.2. Žádný ze školicích materiálů ani jeho část nesmí být bez předchozího písemného souhlasu školitele jakýmkoli způsobem dále zpracovávána, rozmnožována, rozšiřována nebo využívána k dalším prezentacím nebo školením.

8. Zodpovědnost

8.1. Školitel nepřebírá odpovědnost za nedostatky ve službách kterékoliv třetí strany, kterou využívá při školeních.
8.2. Školitel nepřebírá odpovědnost za zranění, škody a ztráty, vzniklé účastníkům vzdělávacích akcí, nebo které byly účastníky způsobeny. Takové náklady, způsobené uvedenými okolnostmi, ponese výhradně účastník vzdělávací akce.

9. Platnost podmínek

9.1 Tyto všeobecné obchodní podmínky jsou platné a účinné od 1. října 2024.

Blog

Porovnání digitálních a kvantových počítačů, část 2: Faktorizace

Algoritmus RSA a problém faktorizace

Reference:

Autor článku:

Podobné články