Představují kvantové počítače hrozbu pro současnou kryptografii? – 2. díl
Vznik a rozšíření nového kryptografického algoritmu je běh na velmi dlouhou trať plný těžkých překážek.
Doba od vymyšlení algoritmu, přes jeho vývoj, pečlivé testování, standardizaci, implementaci v běžných kryptografických knihovnách, počátek praktického užívání, až po rozšíření mezi širokou veřejnost, se neměří v měsících, ale v letech, a zpravidla ve dvouciferných číslech.
Proto kryptologové museli reagovat už v okamžiku, kdy se ukázalo, že by kvantové počítače mohly potenciálně ohrozit současnou kryptografii. Začali hledat řešení v podobě nových asymetrických algoritmů, které mají sloužit jako náhrada za v současnosti používané RSA a algoritmy na bázi eliptických křivek.
Při hledání se zaměřili zejména na dosud nepříliš prozkoumané skupiny těžkých matematických problémů, u kterých není známý způsob, jak na ně efektivně útočit ani za použití kvantových počítačů. Jde například o kryptografii založenou na mřížkách, hashích, samoopravných kódech nebo na isogenii eliptických křivek (jiný způsob využití eliptických křivek, který nijak nesouvisí s tím současným). Těmto novým asymetrickým algoritmům odolným proti kvantovým počítačům se říká postkvantové algoritmy.
Na světlo se vynořily kromě úplně nových i již dlouho známé algoritmy, jako je například jeden z nejstarších známých asymetrických algoritmů McEliece z roku 1978 (pouze o rok mladší, než je RSA).
Problematiky postkvantových algoritmů se chopil americký Národní úřad pro standardy a technologii NIST (v podstatě hlavní standardizační instituce v oboru kryptografie, z jehož dílny vychází standardy jako DES, AES, SHA a mnoho jiných), který vyhlásil pro jejich standardizaci v roce 2016 veřejnou soutěž. Cílem této soutěže bylo vybrat několik vhodných algoritmů, které budou standardizovány.
Hledaly se algoritmy ve dvou kategoriích – první je elektronický podpis, tou druhou proces dohody nad klíči a šifrování klíčů (tento název pokrývá jak přístup zvolený RSA, kdy se klíč k šifrování dat přímo šifruje pomocí asymetrické kryptografie, tak přístup zvolený (EC)DH, kdy se pomocí asymetrické kryptografie odvodí šifrovací klíč a samotné šifrování proběhne za pomocí symetrického algoritmu, například AES).
Mezi požadavky na nové algoritmy patřilo například, aby nebyly zatíženy patenty (problematika patentů značně zpomalila adopci algoritmů na eliptických křivkách), či aby dosahovaly odpovídajících úrovní bezpečnosti. Úrovní bezpečnosti bylo stanoveno celkem 5, kdy úrovně 1,3 a 5 jsou definovány jako: „algoritmus je stejně bezpečný, jako je AES 128/192/256 bezpečný proti útoku hrubou silou“ a úrovně 2 a 4 jsou popsány jako: „stejně bezpečný, jako je SHA 256/384 proti hledání kolizí“.
Do soutěže bylo přihlášeno celkem 82 kandidátů, jejich počet byl během prvních dvou kol do roku 2020 zredukován na 7 + 8 náhradníků – některé algoritmy byly vyřazeny, protože byly prolomeny, v jiných případech došlo ke spojení dvou nebo více algoritmů do jednoho. Z těchto algoritmů byli v roce 2022 vybráni 4 vítězové, kteří budou standardizováni
Kromě toho byla soutěž prodloužena ještě o 4. kolo, ve kterém zůstávají 3 algoritmy (z nichž jeden je výše zmiňovaný McEliece), u kterých se předpokládá, že budou v blízké budoucnosti také standardizovány.
Mezi vyhlášením soutěže a prvními standardizovanými postkvantovými algoritmy uběhlo 8 let. Možná se divíte, proč to trvalo tak dlouho, ale je třeba si uvědomit, že zejména analýza bezpečnosti algoritmů je velmi náročná záležitost jak z hlediska času, tak vynaložených prostředků.
Často bývá citován americký expert na kryptografii a kybernetickou bezpečnost Bruce Schneier: „Každý, ať už úplný amatér nebo ten nejlepší kryptolog, dokáže vymyslet algoritmus, který on sám nedokáže prolomit.“ A toto tvrzení se ukázalo pravdivým i v rámci této soutěže, kdy velká část přihlášených algoritmů byla dříve či později prolomena, a to zpravidla bez použití kvantových počítačů.
Za zmínku stojí zejména prolomení jednoho z finalistů soutěže, algoritmu pro elektronický podpis Rainbow, ve kterém byla v roce 2022, tj. po 6 letech od začátku soutěže, objevena natolik kritická zranitelnost, že jej je i obyčejný notebook schopen prolomit přes víkend, či čtvrtý náhradník, algoritmus SIKE, který byl ve stejném roce prolomen pro všechny bezpečnostní úrovně.
Na závěr už zbývá jen zmínit vítěze soutěže a budoucí postkvantové standardy. Jsou to algoritmy CRYSTALS-DILITHIUM, FALCON a SPHINCS+ v kategorii elektronických podpisů a CRYSTALS-KYBER v kategorii procesu dohody nad klíči a šifrování klíčů. Momentálně jsou standardy těchto algoritmů ve fázi veřejného návrhu a oficiální verze těchto standardů by měla být vydána někdy v roce 2024.
Štítky: kryptografie, kvantová kryptografie
K článku “Představují kvantové počítače hrozbu pro současnou kryptografii? – 2. díl” se zde nenachází žádný komentář - buďte první.
Diskuse na tomto webu je moderována. Pod článkem budou zobrazovány jen takové komentáře, které nebudou sloužit k propagaci konkrétní firmy, produktu nebo služby. V případě, že chcete, aby z těchto stránek vedl odkaz na váš web, kontaktujte nás, známe efektivnější způsoby propagace.
