Blog

Témata:

23. 2. 2026

Bezpečnost Kryptografie

Porovnání digitálních a kvantových počítačů, část 3: Problém diskrétního logaritmu

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 Problému faktorizace se můžeme podívat na problém diskrétního logaritmu.

Algoritmy využívající problém diskrétního logaritmu

V současnosti využíváme algoritmy založené na problému diskrétního logaritmu ve dvou hlavních skupinách. V první z těchto skupin je klasický a stále ještě používaný Diffie-Hellman (DH), dále dnes již výběhový algoritmus DSA (Digital Signature Algorithm), algoritmus ElGamal a Schnorrův podpis. Jedná se zde o nejznámější algoritmy, nikoliv celkový přehled. Uvedená skupina algoritmů pracuje nad omezenou skupinou celých čísel (operace modulo prvočíslo). Tato skupina používá klíče o velikosti jednotek kilobitů, což má dopady na rychlost. Jakékoliv operace s takto velkými čísly jsou poměrně složité. Druhou skupinou jsou algoritmy ECDH (Elliptic Curve Diffie-Hellman), ECDSA (Elliptic Curve DSA), ale take EdDSA (Edwards curve DSA). Ty pracují v několika variantách. Buď se jedná o body eliptické křivky nad číselným tělesem, omezené opět nějakým prvočíslem. Dále se může jednat o body eliptické křivky nad polynomy, omezené ireducibilním polynomem, případně jako poslední varianta se používají rozšíření těles. Klíče pro dosažení stejné úrovně bezpečnosti jsou o řád menší než u algoritmu RSA a zpravidla mají velikost maximálně stovek bitů. Teoreticky je možné používat i další přístupy založené na problému diskrétního logaritmu, ale o praktickém nasazení nevím, proto se jim zde nebudu věnovat.

Jsou tu tedy skupiny systémů, které mají podobné vlastnosti, ale stejně jako u algoritmu RSA, jaké jsou možnosti útoku? Co je a není v našich silách?

Pro útok na klasický Diffie-Hellman, DSA, ElGamal i Schnorr je možné použít NFS-DL (Number Field Sieve – Discrete Logarithm). První část výpočtu je třídění, používá řádově desítky tisíc instrukcí na krok s obtížnou predikcí větvení (branch prediction), jedná se zároveň o paměťově intenzivní operace. Dochází tedy často k situaci, kdy se potřebná data nenachází v cache. Dalším krokem je filtrování s náročností okolo 500 instrukcí na krok, opět paměťově intenzivní. Poslední částí je vyhodnocení, které používá sice málo instrukcí, zhruba 50 na krok, ale je opět paměťově intenzivní. Celkovou složitost algoritmu je možné vyjádřit následujícím způsobem.

$O\left( \sqrt[3]{\frac{64}{9}} + 2^{n^{\frac{1}{3}}\left( \log n \right)^{\frac{2}{3}}} \right)$

Zatížení paměti je u číselného síta je také docela výrazné, s vyjádřením

$M \approx O\left( {\sqrt[3]{\frac{64}{9}} + 2}^{n^{\frac{1}{3}}\left( \log n \right)^{\frac{2}{3}}} \right)$

Vlastní útok na problém diskrétního logaritmu nad eliptickými křivkami dodnes vychází z algoritmu Pollard 𝜌 (Pollard rho). U něj je možné definovat složitost následujícím způsobem

$O \approx \left( \frac{2^{\frac{n}{2}}}{\sqrt[]{m}} \right)$

V tomto vzorci je n bitová šířka klíče a m je hodnota automorfismu. Z používaných křivek mají Weierstrassovy křivky (NIST P-256, NIST P-384 a NIST P-521, dále brainpoolP256r1, brainpoolP384r1, brainpoolP521r1) automorfismus m=2, komunitní křivky používající Twisted Edwards (Ed25519 a Ed448) mají hodnotu m=8. Pro řešení je nutné použít zhruba 4000 instrukcí na jeden krok, navíc velice často dochází k problémům s branch prediction. To znamená zahození fronty instrukcí a pozastavení výpočtu na několik desítek až nižších stovek cyklů.V případě útoku pomocí Pollard 𝜌 je na druhou stranu výhodou extrémně nízké zatížení paměti.

Algoritmus	Složitost	Operací	Instrukcí	Paměť (B)	Doba (roků)	Energie (J)
DSA1024	2^48.7	1.21∙10¹⁴	1.81∙10¹⁸	1.21∙10¹⁴	5.76∙10⁰	5.05∙10⁶
DSA2048	2^62.8	8.09∙10¹⁸	1.21∙10²³	8.09∙10¹⁸	3.84∙10⁵	3.37∙10¹¹
DH1024	2^46.7	1.21∙10¹⁴	1.81∙10¹⁸	1.21∙10¹⁴	5.76∙10⁰	5.05∙10⁶
DH2048	2^62.8	8.09∙10¹⁸	1.21∙10²³	8.09∙10¹⁸	3.84∙10⁵	3.37∙10¹¹
DH3072	2^74.4	2.54∙10²²	3.81∙10²⁶	2.54∙10²²	1.20∙10⁹	1.05∙10¹⁵
DH4096	2^83.8	1.76∙10²⁵	2.64∙10²⁹	1.76∙10²⁵	8.36∙10¹¹	7.33∙10¹⁷
DH6144	2^99.0	6.77∙10²⁹	1.01∙10³⁴	6.77∙10²⁹	3.21∙10¹⁶	2.82∙10²²
DH8192	2^111.4	3.55∙10³³	5.33∙10³⁷	3.55∙10³³	1.68∙10²⁰	1.48∙10²⁶
brainpoolP256r1	2^127.5	2.40∙10³⁸	9.62∙10⁴¹	1	3.05∙10²⁴	1.0∙10¹⁰
brainpoolP384r1	2^191.5	4.43∙10⁵⁷	1.77∙10⁶¹	1	5.62∙10⁴³	4.93∙10⁴⁹
brainpoolP521r1	2^260.0	1.85∙10⁷⁸	7.41∙10⁸¹	1	2.34∙10⁶⁴	2.05∙10⁷⁰
NIST P-256	2^127.5	2.40∙10³⁸	9.62∙10⁴¹	1	3.05∙10²⁴	1.0∙10¹⁰
NIST P-384	2^191.5	4.43∙10⁵⁷	1.77∙10⁶¹	1	5.62∙10⁴³	4.93∙10⁴⁹
NIST P-521	2^260.0	1.85∙10⁷⁸	7.41∙10⁸¹	1	2.34∙10⁶⁴	2.05∙10⁷⁰
Curve25519	2^126.0	8.50∙10³⁷	3.40∙10⁴¹	1	1.07∙10²⁴	9.45∙10²⁹
Curve448	2^222.5	9.35∙10⁶⁶	3.81∙10⁷⁰	1	1.20∙10⁵³	1.05∙10⁵⁹

Opět, jedná se o ideální podmínky. V případě útoků na DH a DSA bude realita bude extrémně odlišná. Paměť je zde opět úzké místo, proto bude přístup k datům v průběhu výpočtu omezen rychlostí úložišť. Jedná se o prodloužení výpočtu v řádu 10³ pro NVMe disky, 10⁴ pro SSD disky a 10⁷ pro HDD (magnetické 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á opět obrovský rozsah, budou častým jevem cache miss. Protože se jedná o paměťově intenzivní operace, data se nevejdou do cache procesoru. Přístup k paměti bude díky tomu často pozastaven na zhruba 200 cykly, kdy nebude prováděn výpočet a dojde k opětovnému načtení paměti do cache. To znamená zpomalení o zhruba o 5 řádů (10⁵ až 10⁹ dle použitých technologií). V případě eliptických křivek je problémem pouze branch prediction, zpomalující výpočet až o tři řády (10³).

Jak je vidět, z hlediska možností je útok na DSA1024, DSA2048, DH1024 a DH2048 v našich možnostech. V případě 1024b klíčů a menších se jedná o schopnosti dostupné i jednotlivcům, pro 2048b klíče pak schopnosti dostupné velkým společnostem nebo státním aktérům. Co se týká větších klíčů nebo v současnosti stále ještě používaných eliptických křivek, zde už není situace až tak jednoduchá. Otázkou opět je, jsme schopní takový útok provést i pro tyto algoritmy? 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 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. Výjimkou jsou zde algoritmy DSA a algoritmy DH do velikosti klíčů 3072b.
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 kapacitou 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 dává 10²⁹ W a celá galaxie potom zhruba 10³⁷W. Je vidět, že ani tyto zdroje nejsou dostatečné.

Pokračování bude v části Útok pomocí kvantových počítačů (2.března 2026)

Reference:

Sage Math script - Pollard rho and NFS-DL
Zdroj: https://cryptosession.info/ke-stazeni
An algorithm to solve the discrete logarithm problem with the number field sieve
Zdroj: https://www.acm.org
NFS with Four Large Primes: An Explosive Experiment
Zdroj: https://link.springer.com/
Computing Individual Discrete Logarithms Faster in GF(p^n) with the NFS-DL Algorithm
Zdroj: https://eprint.iacr.org
On the Efficiency of Pollard's Rho Method for Discrete Logarithms
Zdroj: https://maths-people.anu.edu.au/
About Pollard rho
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 3: Problém diskrétního logaritmu

Algoritmy využívající problém diskrétního logaritmu

Reference:

Autor článku:

Podobné články