Začínám sérii snadno čitelných denních příspěvků o postkvantové bezpečnosti. Ale nemám tušení, kolik dní to :) vydrží. Tak se podíváme. DEN 1: Shorův algoritmus a kvantová apokalypsa(?) Většina našeho bezpečnostního stacku – RSA, ECC, Diffie-Hellman – spoléhá na jediný předpoklad: Celočíselná faktorizace a diskrétní logy jsou "těžké". Na klasickém křemíku ano. K rozluštění RSA-2048 byste potřebovali jednoduše více času, než je věk vesmíru. Ale to není fyzikální zákon. Je to omezení klasického výpočtu. V roce 1994 Peter Shor ukázal, že je lze efektivně vyřešit na kvantovém počítači. Shorův algoritmus nepoužívá jen hrubou sílu kláves; používá kvantovou Fourierovu transformaci (QFT [ne kvantová teorie pole]) k nalezení periody funkce f(x) = a^x mod N. Jakmile máte menstruaci, máte faktory. A jakmile máte faktory, soukromý klíč je mrtvý. Protože soukromý klíč lze rekonstruovat z veřejného klíče. Právě ta složitost je skutečná "apokalypsa". Přecházíme z subexponenciálního času do polynomiálního času O((log N)^3). Nemluvíme o desetinásobném zrychlení; mluvíme o přechodu z bilionů let na několik hodin na CRQC. Podobně jako RSA, ani ECC (kryptografie s eliptickou křivkou) NENÍ bezpečná. Díky efektivní algebraické skupinové struktuře vyžaduje prolomení 256bitového ECC klíče ve skutečnosti méně logických qubitů než RSA-2048. --- Díky za přečtení! Zítra si probereme, proč hrozba HNDL (harvest-now-decrypt-later) znamená, že postkvantový přechod musí proběhnout právě teď. (Vizuál: Peter Shor)