Blog

Témata:

16. 3. 2026

Bezpečnost Kryptografie

Porovnání digitálních a kvantových počítačů, část 6: Shorův algoritmus

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 vysvětlení jak pracují kvantové počítače= je načase se seznámit se Shorovým algoritmem.

Shorův algoritmus

Přestože je Shorův algoritmus jako takový relativně jednoduchý oproti jiným algoritmům v kvantové zoo, jeho implementace se drobně liší pro použití u faktorizace a diskrétního logaritmu. V použitých příkladech je pro počet logických qbitů u faktorizace použito pravidlo $2 \bullet n + 5$ , pro útok na diskrétní logaritmus $2 \bullet n + 10$ a pro počet hradel v obou případech pak $O\left( n^{3} \right)$ . Vzhledem k vývoji v oblasti algoritmizace uvedená pravidla nemusí odpovídat aktuálním úrovni poznání, ale pro odhad uvedené informace postačují.

Faktorizace

Pro faktorizaci se používá Shorův algoritmus se vstupem a jedním registrem. Vstup i registr musí mít délku klíče. Při schematickém zakreslení pak vypadá tento algoritmus následujícím způsobem.

Pro pochopení, jak jsou zapojené jednotlivé logické brány a jejich významu pro výpočet, je potřeba toto zapojení podstatně detailněji vysvětlit. Před spuštěním je potřeba zakódovat část veřejného klíče, tedy číslo n a náhodně zvolenou hodnotu a (nesoudělnou s n) do zapojení obvodu. Na začátku dojde k superpozici všech hodnot řídícího registru (x) pomocí Hadamardových bran, tedy o superpozici všech možných exponentů a pracovní registr je nastaven do definovaného stavu. Následně se využívají kombinace CNOT a CCNOT hradel pro řízené sekvence modulárního násobení $a^{x}\ mod\ N$ . Každý qbit exponentu řídí celou sadu reverzibilního modulárního násobení realizované v rámci sítě CNOT a CCNOT hradel. CNOT a CCNOT hradla zároveň transformují mezivýsledky do pracovního registru. Celý tento proces probíhá v superpozici stavů. Po dokončení modulárního mocnění tak jsou oba registry kvantově provázány a na řídící registr se aplikuje kvantová Fourierova transformace pro zjištění periody. Ta převádí periodickou strukturu fází na měřitelný výsledek, který je možné později odečíst a vyhodnotit v rámci post-processingu z řídícího registru. QFT sama o sobě používá Hadamardovy brány, brány řízených fázových rotací (CP, CR_k) a brány SWAP pro úpravu pořadí qbitů. Pracovní registr obsahuje příspěvky řídícího registru a na konci výpočtu je možné ho zahodit.

Pro útok na problém diskrétního logaritmu (DLP) se používá Shorův algoritmus, tentokrát ale se vstupem a dvěma registry. Jak vstup, tak oba registry musí mít délku klíče. Zapojení se ale liší mezi útokem na čisté DLP, tedy DH a DSA (multiplikativní grupa) a mezi útokem na ECDLP, tedy ECDH a ECDSA (aditivní grupa). Pro čistý DLP problém je jedná toto schéma.

A pro ECDLP pak schéma mírně odlišné.

Reálná zapojení jsou opět komplikovanější. Vysvětlení odlišnosti od faktorizace a vlastní rozbor běhu algoritmu je spojen do jednoho odstavce, protože se liší pouze výpočetní část. Ta je jako rozdíl mezi DLP a ECDLP uvedena samostatně.

Před spuštěním je potřeba do obvodu zakódovat důležité parametry. Pro DLP tedy generátor g a modul p, pro ECDLP počáteční bod G a parametry křivky. Na začátku dojde k superpozici všech hodnot nezávislých řídících registrů (a) a (b) pomocí Hadamardových bran. Dojde tedy k superpozici všech možných stavů samostatně pro každý registr. Registry reprezentují neznámé hledané hodnoty. Pracovní registr je nastaven do výchozího stavu. Postupně se z něj vytváří hodnoty pro potřebné grupové operace (mocnění v multiplikativní grupě pro DLP, sčítání a zdvojování v aditivní grupě pro ECDLP). Díky tomu je v pracovním registru uložena superpozice všech hodnot odpovídající jednotlivým operacím s generátorem, tedy možné hodnoty jeho mocnin pro DLP nebo bodů křivky pro ECDLP. Po vytvoření kvantového provázání mezi řídícími a pracovním registrem se použije na řídící registry kvantová Fourierova transformace pro zjištění periody. Ta převádí periodickou strukturu fází na měřitelný výsledek, který je možné později odečíst a vyhodnotit v rámci post-processingu. Vyhodnocení probíhá nad řídícími registry. QFT sama o sobě používá Hadamardovy brány, brány řízených fázových rotací (CP, CR_k) a brány SWAP pro úpravu pořadí qbitů, v případě řešení problému diskrétního logaritmu se provádí nad oběma registry současně.

V případě DLP se v pracovním registru vypočítávají hodnoty typu $g^{x} \bullet h^{b}\ mod\ p$ . Tyto operace jsou realizovány pomocí reverzibilní aritmetiky založené na CNOT a CCNOT hradlech. Každý qbit řídicího registru ovládá příslušné sekvence modulárního násobení, přičemž celý výpočet probíhá paralelně nad superpozicí všech možných exponentů. V případě ECDLP se provádí řízené skalární násobení bodu eliptické křivky za pomocí reverzibilních obvodů pro sčítání bodů a jejich zdvojování. Tyto obvody jsou opět sestaveny ze sítí CNOT a CCNOT hradel a jsou řízeny jednotlivými qbity řídicích registrů. V obou případech každý qbit řídícího registru ovládá příslušnou část výpočtu bodových operací, přičemž celý proces probíhá v kvantové superpozici. Pracovní registr obsahuje příspěvky obou registrů a na konci výpočtu je možné ho zahodit.

Odhad doby výpočtu

Protože je obtížné odhadnout, jaká bude na dané technologii rychlost přepínání hradel (rotace v Hilbertově prostoru), pro výpočet byly použity následující předpoklady. Počet qbitů se zdvojnásobí každé 3 roky, ale jedná se o fyzické, nikoliv logické qbity. Pro ochranu bude každý logický qbit tvořen 1000 fyzických qbitů. Fyzický objem QPU se pak každé 3 roky zmenší zhruba na dvě třetiny původní velikosti. Tyto podmínky platí pouze pokud bude vývoj pokračovat stejným způsobem, nedojde k technologickému průlomu nebo nenarazíme na fyzikální bariéry (což je také možné). Dále, rychlost hradel bude stálá, všechna hradla se spínají rychlostí 1µs. To také není pravda, ale pro odhad uvedená informace postačuje. Na základě uvedeného vývoje a požadovaného počtu qbitů a hradel je možné odhadnout velikost objemu kvantového počítače bez chlazení a izolace okolo roku 2035. Zde znovu upozorňuji, jedná se pouze o odhad. A poslední důležitý kousek skládačky. Protože informace se šíří pouze rychlostí světla (v tomto případě se jedná o limit popisující délku interakce mezi několika qbity), je na základě objemu určena velikost koule. Pro tuto kouli je při rovnoměrném rozmístění komponent určena střední vzdálenost, která umožňuje určit průměrnou prodlevu zpoždění hradla. Pokud se o tyto údaje opřeme, je možné odhadnout parametry daného kryptograficky relevantního kvantového počítače okolo roku 2035. A to včetně doby, po kterou by se zpracovával běh jednoho průchodu Shorovým algoritmem.

Algoritmus	Logické qbity	Počet hradel	Čas (s)	Objem (m³)
DSA 1024	2058	1.074·10¹⁰	1.074·10³	0.028
DSA 2048	4106	8.590·10¹⁰	8.590·10³	0.055
DH 1024	2058	1.074·10¹⁰	1.074·10³	0.028
DH 2048	4106	8.590·10¹⁰	8.590·10³	0.055
DH 3072	6154	2.899·10¹¹	2.899·10⁴	0.083
DH 4096	8202	6.872·10¹¹	6.872·10⁴	0.111
DH 6144	12298	2.319·10¹²	2.319·10⁵	0.166
DH 8192	16394	5.498·10¹²	5.498·10⁵	0.221
brainpoolP256r1	522	1.678·10⁸	16.78	0.007
brainpoolP384r1	778	5.662·10⁸	56.62	0.010
brainpoolP521r1	1052	1.414·10⁹	141.42	0.014
NIST P-256	522	1.678·10⁸	16.78	0.007
NIST P-384	778	5.662·10⁸	56.62	0.010
NIST P-521	1052	1.414·10⁹	141.42	0.014
Curve25519	520	1.658·10⁸	16.58	0.007
Curve448	906	8.992·10⁸	89.92	0.012
RSA 512	1029	6.711·10⁸	67.11	0.014
RSA 1024	2053	5.369·10⁹	536.87	0.028
RSA 2048	4101	4.295·10¹⁰	4.295·10³	0.055
RSA 2540	5085	8.194·10¹⁰	8.194·10³	0.069
RSA 3072	6149	1.450·10¹¹	1.450·10⁴	0.083
RSA 4096	8197	3.436·10¹¹	3.436·10⁴	0.110
RSA 7168	14341	1.841·10¹²	1.841·10⁵	0.193
RSA 8192	16389	2.749·10¹²	2.749·10⁵	0.221
RSA 13550	27105	1.244·10¹³	1.244·10⁶	0.365
RSA 37100	74205	2.553·10¹⁴	2.553·10⁷	1.000
RSA 76608	153221	2.248·10¹⁵	2.248·10⁸	2.064

Důležitým parametrem pro zjištění výsledku je počet opakování. Problémem u kvantových výpočtu je pravděpodobnostní průběh. A tady to začíná být zajímavé. Pokud chci dosáhnout odpovídající statistické hodnoty sigma (směrodatná odchylka), musí dojít u běžného náhodného rozdělení výstupů k značnému počtu opakování výpočtu. Počet opakování je tak uveden jako samostatný parametr, který závisí na pravděpodobnosti správného výsledku úlohy. Nejlepší možný případ je 60%, nejhorší možný případ je 40%. Nevýhodou jsou náklady na zvyšování přesnosti. Pro jednoduchou změnu přesnosti z 1% na 0,1% dojde k zvýšení počtu potřebných měření stonásobně.

$N = \frac{p \bullet (1 - p)}{\sigma^{2}} = \frac{0,5 \bullet (1 - 0,5)}{{0,01}^{2}} = 2500$

Výhodou na naší straně je ale vlastní výstup Shorova algoritmu. Ten nemá typické Gausovské rozdělení, tedy funkce, připomínající klobouk nebo obrázek hada co spolkl slona z Malého prince. Má ostré výchylky (peaky), které ukazují na konkrétní hodnoty možných výstupů. To vypadá přibližně následujícím způsobem.

Díky existenci těchto ostrých hodnot a pravděpodobnosti nalezení odpovídajících hodnot je možné výrazně snížit počet opakování. Z původních tisíců potřebných měření se tak dostaneme na jednotky až desítky opakování. Zmiňované ostré hodnoty jsou určitým způsoem rozloženy ve výstupu v poměru odpovídajícímu délce registru oproti hledané periodě funkce. Tedy je tu několik pravděpodobných výstupů a my je musíme najít a otestovat. To nás dostane k následujícímu změně. Ta je pro zjednodušení pouze ve formě tabulky, neobsahuje ani kompletní sadu možných algoritmů. Výsledky jsou víceméně podobné.

Algoritmus	Délka registru	Počet peaků	Počet měření pro 99% pravděpodobnost
RSA 2048	2048	~2¹⁰²⁴	7
DH 3072	3072	~2³⁰⁷²	7
ECDH 256	512	~2²⁵⁶	7

Výsledky výpočtu pomocí kvantového počítače prochází post-processingem na klasickém počítači. Doba tohoto výpočtu je vzhledem k práci prováděné kvantovým počítačem zanedbatelná. U problémů diskrétního logaritmu se jedná o časy menší než 1s, pro 1024b RSA klíč jednotky sekund, pro 2048b desítky sekund a následně přibližně každé zdvojnásobení šířky klíče rozšiřuje dobu zpracování výsledků na klasickém digitálním počítači desetkrát. Přesto se jedná oproti výpočtu o zanedbatelný čas. Kvantový počítač je tak možné si z tohoto pohledu představit jako jakýsi analogový pravděpodobnostní stroj.

Pokračování bude v části Odhad příkonu kvantových počítačů (23.března 2026)

Reference:

Quantum complexity of Shor’s algorithms implementations
Zdroj: https://www.nature.com/
Quantum Computation and Shor’s Algorithm tutorial
Zdroj: https://journals.aps.org/
Surface codes: Towards practical large-scale QC
Zdroj: https://www.pnas.org/
Google Quantum AI, Suppressing quantum errors by scaling a surface code logical qubit
Zdroj: https://www.nature.com/
Lieb–Robinson bounds and locality in quantum systems
Zdroj: https://journals.aps.org/
Quantum algorithms for discrete logarithms on elliptic curves
Zdroj: https://www.worldscientific.com/
Amplitude estimation and quantum probability amplification
Zdroj: https://arxiv.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.