Blog

Témata:

2. 3. 2026

Bezpečnost Kryptografie

Porovnání digitálních a kvantových počítačů, část 4: Útok pomocí kvantového počítače

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 diskrétního logaritmu a jeho řešení na digitálních počítačích je vhodné pochopit, jaký dopad mají kvantové počítače.

Principy útoku na současné asymetrické algoritmy pomocí kvantových počítačů

Zlomení současných algoritmů pro asymetrickou kryptografii vyžaduje použití QFT, kvantové Fourierovy transformace (Quantum Fourier Transformation). Současné asymetrické algoritmy jsou postaveny na určitých předpokladech a složitosti problémů, které jsme prozatím nedokázali řešit.

Algoritmus RSA je postaven nad problémem faktorizace. Tedy, pokud máme číslo n, nejsme schopni určit čísla p a q, ze kterých vzniklo. V případě RSA jsou z důvodu ochrany před výpočetním útokem hrubou silou p a q velká prvočísla. Rozklad takových čísel je extrémně výpočetně náročný.

Algoritmy DH, DSA, ECDH, ECDSA jsou algoritmy, které jsou postaveny nad problémem diskrétního logaritmu. Zjednodušeně, běžně dokážeme spočítat mocninu čísla. Ale existuje určité oblasti matematiky, kde jsou odmocniny komplikované. Jedná se o modulární aritmetiku, která využívá čísla v určitých skupinách (grupách). Všichni jsme tuto oblast potkali ve škole, jedná se o počítání se zbytkem. Je možné si to představit jako počítání na hodinách, které mají prvočíselný počet záznamů (počítání modulo prvočíslo). Umocnění čísla na nějakou hodnotu nám řekne počet kroků, ale protože se otáčímě v kruhu, často se můžeme dostat na stejné hodnoty. Jaké byly původní hodnoty a číslo, na které jsme mocnili?

Ve výše uvedených případech nám může pomoci QFT. Její princip je již dnes známý, ale jedná se o funkci, umožňující hledat nějakou periodu opakování. Původní Fourierova transformace po převodu do formy kvantového algoritmu umožnila Peteru Shorovi v roce 1995 navrhnout postup pro útok na algoritmus RSA. Později byl tento princip použit i pro útok na další formy asymetrické kryptografie. V případě faktorizace tak postup hledá periodu funkce, v případě eliptických křivek lineární funkci (lineární vztahy mezi jednotlivými prvky), které umožní dopočítat parametry tajného klíče.

Pokud se bavíme o konkrétních algoritmech, pro RSA se bude hledat řád (modulární základ). Je možné si to představit jako bazén, který má délku a šířku odpovídající délce čísla n. Jeho hladinu rozkmitáme, takže máme vlny všech velikostí a frekvencí. Kvantový počítač tento povrch vyhodnocuje pomocí QFT najednou. Místa, kde jsou největší výchylky, zároveň označují nejpravděpodobnější kombinace čísel. Algoritmus se snaží zjistit, které kombinace výsledků jsou nejpravděpodobnější, ale výsledek je nutné následně ověřit na běžném digitálním počítači. Tomu se říká post-processing. Cílem nových variant algoritmu je snížit náročnost na počet qbitů a zvýšit pravděpodobnost úspěšného výsledku.

U eliptických křivek je situace trochu odlišná. Zde se hledá základ lineární funkce. Křivka má určité parametry a zpravidla určený výchozí bod. Když známe cílový bod, může QFT posloužit k zjištění všech možných kombinací násobků, které vedou k danému výsledku. Na základě uvedených hodnot pak algoritmus zjišťuje pravděpodobnost pro dané hodnoty, protože pro určité násobky není možné daných míst dosáhnout. Představa takového řešení je podstatně složitější. Běžně se používá pro zakreslení funkce milimetrový papír, ale v tomto případě bude uvedený papír nesmírně pružný. Protože je prvočíslem omezený na určitou délku a šířku, pro zakreslení nekonečné křivky potřebujeme určitou úpravu. Znamená to spojení horní a dolní strany (vznikne válec) a následně vzájemné spojení bočních stran (vznikne toroid, něco jako nafouknutá pneumatika). Pokud známe počáteční bod a koncový bod, QFT hledá veškeré možné parametry, kdy je možné se z počátečního do koncového bodu dostat. Něco jako napnutá struna, která kopíruje tuto křivku od počátečního do koncového bodu. Těchto strun je nesmírné množství. Na všechny tyto struny je možné zahrát určité kombinace tónů (frekvence opakování). Ty, které nejsou naladěné, hrají falešně. Falešné frekvence se automaticky vyřadí, zbytek vytřídí právě funkce QFT. Tato funkce hledá struny s nejčistším tónem, tedy hledá vhodné kombinace parametrů. Jenže na rozdíl od RSA je zde nutné pro výpočet použít ne jeden, ale dva registry, proto je počet qbitů větší. Stejně jako u RSA je i zde po výpočtu nutné provést post-processing. Protože se dnes hledají stále lepší a lepší postupy, je cílem nových variant algoritmu snížit náročnost na počet qbitů a zvýšit pravděpodobnost úspěšného výsledku.

Miniaturizace kvantových počítačů a její meze

Současné kvantové počítače vyžadují na jeden logický qbit stovky až jednotky tisíc fyzických qbitů. Je to způsobeno šumem a potřebou zajistit odpovídající korekci chyb pomocí kvantových korekčních kódů. Většina lidí z informatiky je zvyklá na Mooreův zákon (přesněji pozorování) a uklidňuje se představou, že stačí pouze několik let počkat. Jenže mezi digitálními a kvantovými počítači je výrazný rozdíl. Mooreovo pravidlo bylo postaveno na automatizaci, zvyšování hustoty a zanedbatelném šumu, v současnosti (přesněji již od roku 2015) již také naráží na své hranice. V případě kvantových počítačů je situace podstatně horší. Každý jednotlivý qbit prostě není tranzistor, nejde ho jednoduše zmenšit. Potřebuje řízení, izolaci a kalibraci. Přidání qbitů zároveň nemusí znamenat zvýšení výkonu. Důvodem je vzájemné ovlivňování v celém systému, každý qbit znamená více kabeláže, chlazení, šumu, a tedy také více korekcí chyb.

Pozorování vývoje je prozatím příliš krátké na možný odhad pravidel vývoje. Patrně nejlepší metrika v této oblasti se nazývá Quantum Volume. Popisuje nárůst na základě počtu qbitů, hloubky obvodů a chybovosti, přesto ani ta nedokáže predikovat vývoj odpovídajícím způsobem. Takže přestože počet qbitů zdánlivě roste exponenciálním způsobem, nemá to odpovídající vliv na logické qbity, výkon a výrazné zlepšení v oblasti snížení chybovosti. Škálování je v současnosti extrémně náročné, výroba kvantových počítačů není automatizovaná sériová linka, na kterou jsme u křemíku zvyklí. Jedná se spíše o manufakturu s desítkami až stovkami velice kvalifikovaných specialistů.

Vlastní miniaturizace pak naráží na několik fyzikálních problémů. Jeden problém je princip neurčitosti, známý jako Heisenbergův princip. Zjednodušeně řečeno, máme hybnost částice a její polohu, ale znát můžeme jenom jednu z položek. Jiný pohled je podobný, máme čas a energii, opět můžeme znát jenom jednu z položek. Jakékoliv měření vyžaduje energii, čím menší částice je tím vyšší. A měřením samozřejmě částici ovlivníme. Další problém se týká adresace hodnoty způsobený použitou energií. Tedy čím menší je daný prvek, tím vyšší energii pro manipulaci potřebuje. To samozřejmě ovlivňuje i okolní systémy a vytváří nechtěný šum. Mimo uvedené problémy musí být vzdálenost jednotlivých qbitů větší, než je vlnová délka ovládajících elektromagnetických polí, dnes se zpravidla používají mikrovlny. V jiném případě by docházelo k vzájemnému ovlivňování jednotlivých fyzických qbitů. Pak tu máme další z problémů, to je poměr objemu a povrchu qbitu. Čím menší je qbit, tedy čím menší má objem, tím výraznější je tento poměr k povrchu a pod určitou velikostí určuje chování qbitu hlavně plocha jeho povrchu. Protože na povrchu dochází k nejvýraznější tvorbě šumu (interakce s okolím), plocha povrchu výrazně ovlivňuje chybovost daného fyzického qbitu. Pod rozměrem okolo 10nm povrch určuje schopnost odolávat šumu. Můžeme pokračovat přes limity velikosti založené na Planckových jednotkách (Planckova délka 1.6∙10⁻³⁵ m a Planckův čas 5.4∙10⁻⁴⁴ s), tedy nejmenší délky a nejkratšího času. Pod touto hranicí přestává mít představa qbitu význam. Přesněji, je otázkou, zda má pod touto hranicí význam i cokoliv jiného, ale to jsou otázky, na které asi moc lidí odpovědět nedokáže. Tohoto limitu patrně nebudeme nikdy schopni dosáhnout. Nakonec tu je stejně jako u klasických počítačů Landauerův limit. Ten specifikuje, že zničení jakékoliv informace vytváří teplo. Z tohoto důvodu je lepší informace nemazat, ale odpočítávat. Pro kvantové počítače je teplo dalším zdrojem šumu, který ohrožuje jejich schopnost realizovat výpočty. Navíc čím menší je obvod, tím hůře se teplo odvádí. Landauerův limit tak vytváří přirozenou bariéru, která bude mít vždy vliv na konstrukci počítače a hrozbu přerušení výpočtu spontálním kolapsem.

V tomto odstavci je často zmiňován termín fyzický a logický qbit, ale jaký v něm je vlastně rozdíl? Fyzický qbit je implementace v hardware, fyzický prvek s kvantovými vlastnostmi. Logický qbit je konstrukce nad několika fyzickými qbity pomocí kvantových korekčních kódú. Je výrazně stabilnější, protože vazba mezi fyzickými reprezentacemi dovoluje za pomoci uvedených kódů zajistit tvorbu stabilnější logické reprezentace. Mimo výrazného vlivu na spolehlivost ale také právě tato vlasnost dovoluje jistou volnost v marketingových reprezentacích produktů.

Pokračování bude v části Jak pracuje kvantový počítač (9.března 2026)

Reference:

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Zdroj: https://arxiv.org/
Semiclassical Fourier Transform for Quantum Computation
Zdroj: https://arxiv.org/
Circuit for Shor’s algorithm using 2n+3 qubits
Zdroj: https://arxiv.org/
Surface codes: Towards practical large-scale quantum computation
Zdroj: https://arxiv.org/
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
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