Digitální a kvantové počítače, část 9

Porovnání digitálních a kvantových počítačů, část 9: Zhodnocení útoku dle původního návrhu

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 seznámení se s dostupnými technologiemi je možné zkusit odhadnout schopnosti kvantových počítačů okolo roku 2035.

Celkové zhodnocení schopností kvantových počítačů

Na základě těchto informací je možné vytvořit následující přehled, který je opět odhadem pro rok 2035. Pro útok na následující algoritmy potřebuje kvantový stejně jako digitální počítač konkrétní čas, v případě kvantového pak minimální počet průchodů. Následuje post-processing na běžném digitálním počítači. Mimo uvedeného času vyžaduje také jistý minimální počet qbitů, v této oblasti ale dochází k neustálému vývoji, takže už v době psaní článku je výsledek lehce nadhodnocený. U těchto požadavků tu je patrně nejvýznamnější vstup, to je příkon chlazení. Zde je upravená tabulka, která počítá s příkonem jednotlivých qbitů a hradel v rámci pW, tepelným vyzařováním kabeláže 1mW/m, vyčítání stavu z jednoho qbitu pak 100mW. Uvedená systém počítá s kvalitní izolací a potřebou chlazení na teplotu 1mK, používá ocelovou nosnou konstrukci s mechanickými parametry pro hmotnost zařízení odpovídající ocelové kouli daného objemu. Cíleně je zanedbána nutnost interního chlazení pro odvod tepla, jedná se pouze o teoretický model. Potřebná konstrukce pro odvod tepla by extrémně změnila podmínky celého přibližného výpočtu. Výsledná uváděná energie je potřebná pro realizaci jednoho výpočtu, nikoliv všech opakování pro zajištění odpovídající míry pravděpodobnosti. Zároveň nezahrnuje post-processing, který ale na druhou stranu nemá významné požadavky na příkon.


AlgoritmusLogické qbityPočet hradelČas (s) Objem (m3)Energie (J)
DSA 102420581.074·10101.074·103 0.0281.667·1014
DSA 204841068.590·10108.590·103 0.0552.661·1015
DH 102420581.074·10101.074·103 0.0281.667·1014
DH 204841068.590·10108.590·103 0.0552.661·1015
DH 307261542.899·10112.899·104 0.0831.346·1016
DH 409682026.872·10116.872·104 0.1114.252·1016
DH 6144122982.319·10122.319·105 0.1662.152·1017
DH 8192163945.498·10125.498·105 0.2216.800·1017
brainpoolP256r15221.678·10816.780.007 6.607·1011
brainpoolP384r17785.662·10856.620.010 3.324·1012
brainpoolP521r110521.414·109141.420.014 1.122·1013
NIST P-2565221.678·10816.780.007 6.607·1011
NIST P-3847785.662·10856.620.010 3.324·1012
NIST P-52110521.414·109141.420.014 1.122·1013
Curve255195201.658·10816.580.007 6.505·1011
Curve4489068.992·10889.920.012 6.146·1012
RSA 51210296.711·10867.110.014 5.210·1012
RSA 102420535.369·109536.870.028 8.316·1013
RSA 204841014.295·10104.295·103 0.0551.329·1015
RSA 254050858.194·10108.194·103 0.0693.143·1015
RSA 307261491.450·10111.450·104 0.0836.725·1015
RSA 409681973.436·10113.436·104 0.1102.125·1016
RSA 7168143411.841·10121.841·105 0.1931.992·1017
RSA 8192163892.749·10122.749·105 0.2213.399·1017
RSA 13550271051.244·10131.244·106 0.3652.544·1018
RSA 37100742052.553·10142.553·107 1.0001.429·1020
RSA 766081532212.248·10152.248·108 2.0642.599·1021

Článek obsahuje pouze odhad, nikoliv konkrétní implementaci. Nejedná se dokonce ani o optimální odhad, protože vývoj v oblasti algoritmů pro kvantové počítače bude útoky zrychlovat. Už v současnosti jsou algoritmy výrazně jednodušší, ale jejich vysvětlení je náročné a je extrémně obtížné najít nějakou vhodnou představu. Otázkou je, nakolik jsou rizika plynoucí z kvantových počítačů nadhodnocena z hlediska časového rámce. Další otázkou je vliv multiplexingu, kdy několik qbitů využívá jedno hradlo. To sice snižuje potřebný počet hradel (spojů) a jejich příkon, zároveň se v odpovídajícím poměru prodlužuje celková doba zpracování. Útok za pomoci kvantových počítačů je rozhodně v možnosti celé lidské civilizace, možná i v možnostech některých státních aktérů. Přesto může být poněkud problematické útočit i na jednodušší eliptické křivky z prostého důvodu. Tímto důvodem je zajištění odpovídajícího množství dostupné energie. Kryptograficky relevantní kvantový počítač bude mít mimo konstrukčních obtíží problém i s uvedeným zdrojem příkonu. Podle tohoto základního popisu by útok na asymetrické algoritmy mohl vyžadovat významné investice do zdrojů. Na druhou stranu zvýšení pracovní teploty o jediný řád uvedené dopady výrazně omezí. K tomu se přidává otázka, jak vyřešit problém s odpadním teplem. Podle tohoto odhadu jsou kvantové počítače prozatím teoretickým útokem. Tento útok se ale může stát v dohledné době realizovatelným, kde jakýkoliv technologický průlom ohrožuje současnou kryptografii.

Pokud bych na základě uvedených výsledků pro zjednodušení představy zvažoval napájení pomocí bloků s reaktory o výkonu 1GW, dostávám se k následujícím výsledkům. Pro Curve25519, brainpoolP256r1 a NIST P-256 by se jednalo o 39 bloků, pro brainpoolP384r1 a NIST P-384 pak 58 bloků, pro Curve448 už 60 bloků a pro brainpoolP521r1 a NIST P-521 dokonce 78 bloků. Jsem opravdu zvědavý, nakolik tento odhad bude odpovídat realitě. Vzhledm ke možnostem poskytovaným kvantovými počítači bych si přál, abych se pletl.

\mathit{N}_{\mathit{1GW\ bloků}}\mathit{=}\frac{\mathit{Energie\ potřebná\ pro\ výpočet\ (J)}}{{1 \cdot 10}^{\mathit{9}}W \cdot čas\ výpočtu\ (s)}

Zároveń z uvedeného přehledu vyplývá, že pro malé velikosti klíčů by mohl být klasický digitální počítač pro luštění vhodnější než kvantový. Příkladem je například DSA 1024b, DH 1024, DSA 2048b a DH 2048b. U malých velikostí klíčů algoritmu RSA tento rozdíl není tak velký, od začátku zde dominují kvantové počítače. Pro velké klíče má samozřejmě ve všech případech kvantový počítač výrazně navrch. Největší problém je zde chlazení, teplota blízko absolutní nuly je steně limitující, jako rychlost světla. Cílem vývoje je proto provozní teploty systému posunout do příjemnějších teplotních rozsahů. Zde je přehled, co by to znamenalo v energetické náročnosti, tedy potřebné energii pro jeden výpočet.


Algoritmus1μK (J)1mK (J)0,1K (J)1K (J)10K (J)100K (J)
DSA 10241.667·10171.667·10141.667·1012 1.667·10111.667·10101.667·109
DSA 20482.661·10182.661·10152.661·1013 2.661·10122.661·10112.661·1010
DH 10241.667·10171.667·10141.667·1012 1.667·10111.667·10101.667·109
DH 20482.661·10182.661·10152.661·1013 2.661·10122.661·10112.661·1010
DH 30721.346·10191.346·10161.346·1014 1.346·10131.346·10121.346·1011
DH 40964.253·10194.253·10164.253·1014 4.253·10134.253·10124.253·1011
DH 61442.152·10202.152·10172.152·1015 2.152·10142.152·10132.152·1012
DH 81926.800·10206.800·10176.800·1015 6.800·10146.800·10136.800·1012
brainpoolP256r16.607·10146.607·10116.607·109 6.607·1086.607·1076.607·106
brainpoolP384r13.324·10153.324·10123.324·1010 3.324·1093.324·1083.324·107
brainpoolP521r11.122·10161.122·10131.122·1011 1.122·10101.122·1091.122·107
NIST P-2566.607·10146.607·10116.607·109 6.607·1086.607·1076.607·106
NIST P-3843.324·10153.324·10123.324·1010 3.324·1093.324·1083.324·107
NIST P-5211.122·10161.122·10131.122·1011 1.122·10101.122·1091.122·107
Curve255196.505·10146.505·10116.505·109 6.505·1086.505·1076.505·106
Curve4486.146·10156.146·10126.146·1010 6.146·1096.146·1086.146·107
RSA 5125.210·10155.210·10125.210·1010 5.210·1095.210·1085.210·107
RSA 10248.316·10168.316·10138.316·1011 8.316·10108.316·1098.316·108
RSA 20481.329·10181.329·10151.329·1013 1.329·10121.329·10111.329·109
RSA 25403.143·10183.143·10153.143·1013 3.143·10123.143·10113.143·1010
RSA 30726.725·10186.725·10156.725·1013 6.725·10126.725·10116.725·1010
RSA 40962.125·10192.125·10162.125·1014 2.125·10132.125·10122.125·1011
RSA 71681.992·10201.992·10171.992·1015 1.992·10141.992·10131.992·1012
RSA 81923.399·10203.399·10173.399·1015 3.399·10143.399·10133.399·1012
RSA 135502.544·10212.544·10182.544·1016 2.544·10152.544·10142.544·1013
RSA 371001.429·10231.429·10201.429·1018 1.429·10171.429·10161.429·1014
RSA 766082.599·10242.599·10212.599·1019 2.599·10182.599·10172.599·1016

V této sérii jsem se snažil vysvětlit problémy útoků na současnou asymetrickou kryptografii a trochu populární formou vysvětlit problémy při útocích s pomocí kvantových počítačů a Shorrova algoritmu. Přestože se část věnující se kvantovým počítačům snaží uvedenou problematiku vysvětlit, jedná hlavně o populární formu a součástí je i jisté zkreslení informací, za které se omlouvám. Tato oblast je extrémně složitá a její vysvětlení je obtížné. Dle mého je ale nutné upozornit na veřejně přehlížený problém času útoku v závislosti na potřebě dosažení jisté přesnosti a v případě kryogenických zařízení potřebu účinně takové zařízení chladit.

Na tuto sérii bude v budoucnu volně navazovat kritické hodnocení úspěchů při útocích na asymetrickou kryptografii jak pomocí klasických počítačů (historie), tak s pomocí kvantových počítačů. Důvodem je snaha upozornit na dle mého názoru zavádějící experimety a jejich případnou nevhodnou interpretace. Stejně tak bych chtěl do budoucnosti porovnat požadavky na příkon pro jednotlivé kvantové algoritmy.

Autor článku:

Jan Dušátko
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.

Informace o sběru a zpravování osobních údajů

Zpracovatel Jan Dušátko (dále jen „Správce“), dle nařízení Evropského parlamentu a Rady (EU) č. 2016/679 o ochraně fyzických osob v souvislosti se zpracováním osobních údajů a o volném pohybu těchto údajů a o zrušení směrnice 95/46/ES (obecné nařízení o ochraně osobních údajů, dále jen „Nařízení“) zpracovává osobní údaje. Dále jsou rozepsané jednotlivé osobní údaje, které jsou součástí zpracování při konkrétních aktivitách u této webové prezentace a v rámci obchodního styku.
Přestože je sběr dat všudypřítomný, provoz tohoto webu si zakládá na právu na soukromí každého uživatele. Z uvedeného důvodu sběr informací o uživatelích probíhá v naprosto nezbytné míře a to jen v případě, kdy se uživatel rozhodne kontaktovat provozovatele. Jakýkoliv další sběr a zpracování dat považujeme za neetický.

Informace o záznamech přístupu na webovou prezentaci

Tento web nesbírá žádné cookies. Stránka nepoužívá ani žádné analytické scripty třetích stran (sociální sítě, cloud provideři). Z těchto důvodů je také nabízena volba pro zobrazení mapy formou odkazu, kde primárním zdrojem je OpenStreet a alternativy pak často používané Mapy společnosti Seznam, a.s., případně Google Maps společnosti Google LLC Inc. Využití jakéhokoliv z těchto zdrojů je zcela na libovůli uživatelů těchto stránek. Správce nenese odpovědnost za sběr dat realizovaný těmito společnostmi, neposkytuje jim data o uživatelích a na sběru dat nespolupracuje.
Logování přístupů probíhá pouze na úrovni systému, důvodem je identifikace případných technických nebo bezpečnostních problémů. Dalšími důvody jsou přehledové statistiky přístupů. V této oblasti se nesbírají ani nesledují žádné konkrétní údaje a všechny záznamy o přístupech jsou po třech měsících mazány.

Informace o kontaktování provozovatele stránek

Formulář pro kontaktování provozovatele stránek (správce) obsahuje následující osobní údaje: jméno, příjmení, e-mail. Tyto údaje jsou určeny jen a pouze pro tuto komunikaci, odpovídající oslovení uživatele a jsou udržovány po dobu nezbytnou k naplnění účelu, maximálně pak po dobu jednoho roku, pokud si uživatel neurčí jinak.

Informace o objednávkovém formuláři

Pro případ zájmu o objednávku formulář obsahuje více údajů, tj. jméno, příjmení, e-mail a kontaktní údaje na organizaci. Tyto údaje jsou určeny jen a pouze pro tuto komunikaci, odpovídající oslovení uživatele a jsou udržovány po dobu jednoho roku, pokud si uživatel neurčí jinak. V případě, kdy na základě této objednávky dojde k uzavření obchodního vztahu, budou nadále správcem udržovány pouze informace vyžadované českými zákony na základě obchodních vztahů (název a adresa společnosti, číslo bankovního účtu, typ kurzu a jeho cena).

Informace o dokumentu o absolovování kurzu

V rámci kurzu je vydán zpracovatelem dokument o absolovování kurzu. Tento dokument obsahuje následující údaje: jméno a příjmení studenta, název a datum absolovování kurzu a jméno zaměstnavatele. Uvedené informace se následně používají pro tvorbu lineárního stromu hashí (nemodifikovatelný záznam). Tato databáze obsahuje pouze informace o poskytnutých jménech a názvech společností, které mohou a a nemusí odpovídat realitě a je udržován zpracovatelem pro případné opětovné vystavení nebo ověření vydání dokumentu.

Práva subjektu osobních údajů

Zákazník nebo návštěvník tohoto webu má možnost požádat o informace o zpracování osobních údajů, právo požadovat přístup k osobním údajům, případně právo požádat o opravu nebo výmaz veškerých dat, které by o něm byly vedeny. V případě výmazu tento požadavek není možné splnit pouze pokud se nejedná o data nezbytně nutná v rámci obchodního styku. Zákazník nebo návštěvník webu má dále právo na vysvětlení týkající se zpracování jeho osobních údajů, pokud tento zjistí nebo se domnívá, že zpracování je prováděno v rozporu s ochranou jeho soukromého a osobního života nebo v rozporu s platnými právními předpisy a právo požadovat odstranění takto vzniklého stavu a zajištění nápravy.
Zákazník/návštěvník tohoto webu dále může požadovat omezení zpracování nebo vznést námitku proti zpracování údajů a má právo kdykoliv písemně svůj souhlas se zpracováním osobních údajů odvolat, aniž by tím byla dotčena zákonnost jejich zpracování předcházející takovému odvolání. Pro tyto účel slouží kontaktní e-mail adresa support@cryptosession.cz
Zákazník/návštěvník má právo podat stížnost proti zpracování osobních údajů u dozorového úřadu, kterým je Úřad pro ochranu osobních údajů.