Hlavní navigace

Gilles Brassard: Kryptoalgoritmy RSA a ECDSA jsou z kvantového pohledu kompletně rozbité

Autor: Karel Wolf
Karel Wolf

Jaký je hlavní problém klasické asymetrické kryptografie z pohledu kvantových algoritmů? Mluvili jsme s Gillesem Brassardem, který spolu s Charlesem Bennettem před 36 lety vytvořil první protokol kvantové kryptografie.

Doba čtení: 6 minut

Sdílet

Gilles Brassard dnes působí primárně jako profesor informatiky na Montrealské univerzitě v Kanadě. V době, kdy se o kvantovou informační vědu zajímala jen hrstka „šílenců“, pomohl položit základy kvantové kryptografie a patří mu také prestižní místo mezi autory konceptu kvantové teleportace.

Mezi léty 1991 a 1997 působil jako šéfredaktor vědeckého časopisu Journal of Cryptology a je autorem tří odborných knih, které byly přeloženy do osmi jazyků. Je také členem Londýnské královské společnosti, Kanadského institutu pro pokročilý výzkum a mezinárodní asociace pro kryptologický výzkum. V domovské Kanadě se mu dostalo vědeckých ocenění NSERC Gerhard Herzberg Canada Gold Medal for Science and Engineering a Killam Prize for Natural Sciences a je držitelem několika čestných doktorátů doma i v Evropě.

V roce 2018 se stal prvním Kanaďanem, který obdržel mezinárodní Wolfovu cenu za fyziku a v loňském roce mu byla udělena také Miciusova kvantová cena. Mluvili jsme s ním před jeho evropskou přednáškou v rámci Insights in Technology Talks na Schaffhausen Institute of Technology ve Švýcarsku.

Jaký je váš názor na kryptografii založenou na kryptografické hašovací funkci, obstála by ve světě postkvantové kryptografie?

Možná vás to trochu překvapí, ale moje zcela upřímná odpověď zní, že nevím. Vím například, že řada kolegů přišla s návrhy, jak před kvantovými útoky zabezpečit RSA kryptografii a že některé z nich využívají právě hašovací funkci, ale nestudoval jsem detaily, takže si netroufám momentálně dávat fundovanou odpověď.

Když už jste zmínil RSA, můžete čtenářům zkusit přiblížit, v čem je hlavní problém šifrovacích metod založených na RSA a případně eliptických křivkách z pohledu kvantových algoritmů?

Výborně, to je mnohem jednodušší otázka. Stručná odpověď by mohla znít, že jejich hlavní problém je, že jsou z optiky kvantových algoritmů totálně rozbité. Pokud bychom měli k dispozici plnohodnotný obecný kvantový počítač, a ne jen jeho simulaci, která je za něj dnes často vydávána PR odděleními některých firem, tak RSA, DH, a dokonce i ECDSA bohužel nemají šanci obstát.

Dnes již bezpečně víme, že v případě RSA je útočník s kvantovým počítačem schopný rozlousknout klíč rychleji, než bude trvat na běžném počítači tento klíč vygenerovat. To, jestli je potřeba tyto kryptografické metody v jejich současné podobě nahradit, tedy není otázka, ale imperativ. Jde jen o to nalézt nejefektivnější způsob, jak to udělat.

Jinak, když se ještě vrátím k tomu kvantovému počítači, bavíme se tu o obecném kvantovém počítači s výpočetní silou minimálně několika tisíc kvantových bitů (qubitů), ne o malém kvantovém počítači/počítači pro řešení konkrétních úloh.

Dnes víme, že se v našem „klasickém světě“ RSA, ECDSA a Diffie-Hellman jeví jako bezpečné metody, ale nemůžeme dokázat, že tomu tak skutečně je. Oproti tomu ale umíme dokázat, že RSA, DH, a dokonce i ECDSA nejsou bezpečné metody v „kvantovém světě“. Stejná situace, jaká platila v klasickém světě pro RSA, ECDSA a DH, platí v kvantovém světě pro McEliece, New Hope a Frodo (mohou být bezpečné, ale neumíme to prokázat).

Mají stejný problém také Schnorr signatures? Přeci jenom, přestože jsou ještě o maličko starší než ECDSA, nemají některé slabiny eliptických křivek.

Myslím, že ano, měly by trpět úplně stejnými neduhy jako RSA a ECDSA, ale netroufám si to tvrdit na 100%, neboť jsem o nich četl naposled před 25 lety a nepamatuji si již přesně detaily toho, jak Schnorr signatures pracují.

V čem přesně spočívá hlavní slabina kryptografie založené na RSA a ECDSA z perspektivy kvantových algoritmů?  

Peter Shor v roce 1994 objevil způsob, jak s pomocí kvantového počítače faktorizovat velká čísla a také, jak se někdy říká, jak extrahovat diskrétní logaritmy. S těmito dvěma dovednostmi již lze louskat klíče používané asymetrickou kryptografií jako na běžícím pásu.

Princip Shorova postupu ve zkratce spočívá v nalezení periody posloupnosti, jež je výstupem počítání zbytku po dělení nad čísly N a r, za podmínky, že r bude libovolné zvolené číslo nesoudělné s N, což je číslo, které chceme faktorizovat.

Když se podíváme na to, jak funguje RSA, zjistíme, že staví na vlastnostech násobení dvou prvočísel s velkou pravděpodobností, kdy je garantováno, že faktorizací násobku budou právě tato prvočísla. Před příchodem kvantových výpočtů existovala prakticky nulová pravděpodobnost nalézt tato prvočísla přímou cestou. S příchodem Shorova algoritmu to ale přestává platit.

Samotný algoritmus využívá diskrétní Fourierovy transformace a její schopnosti zjistit, jestli je nějaká diskrétní funkce periodická a jakou periodu má, k čemuž se právě využívá paralelních výpočtových vlastností kvantového systému. Pokud ale vaše otázka zněla, jak přesně celý algoritmu funguje, tak se obávám, že sice vyčerpáme zbývající čas, ale rozhodně ne samotné téma.

To rozhodně nezní moc povzbudivě s ohledem na to, kde všude a v jaké škále se oba šifrovací postupy používají.

Co vás může zatím trochu uklidnit, je, že potřebný kvantový počítač zatím k dispozici nemáme a snad (doufejme) ještě nějaký čas mít nebudeme.

Teď trochu z jiného soudku. Jak byste úplně laickému čtenáři přiblížil základní princip kvantové kryptografie?

Kvantová teorie říká, že není možné žádným způsobem měřit kvantové informace (minimálně ne přesně) a jakýkoli pokus tak učinit vytváří disturbanci, která je nezvratná a nevyhnutelná. Když se na to podíváme z kryptografické perspektivy, pokud Alice pošle Bobovi tajný vzkaz, který je zakódovaný kvantovým systémem, tak jakýkoli pokus o odposlechnutí konverzace vytvoří disturbanci, která je Bobem detekovatelná. Kvantová kryptografie nám tak dává k dispozici kanál, který není možné pasivně odposlouchávat a který není možné odposlouchávat bez toho, že bychom za sebou zanechali snadno detekovatelnou stopu. V tom spočívá její hlavní síla.

Toho můžeme využít k vytvoření bezpečného klíče pomocí klasické kryptografie tím, že klíč vygenerujeme právě skrze kvantový kanál. Pokud při jeho vytváření nezaznamenáme disturbanci, víme, že můžeme použít takto vygenerovaný klíč k podepsání a bezpečnému poslání zprávy pomocí klasické one-time pad metody (Vernamovy šifry – poznámka redakce).

TIP: Poslechněte si podcast s kryptologem Tomášem Rosou:

Pokud to tedy správně chápu, tak jediný smysl kvantového kanálu je vytvoření a distribuce klíče?

BRAND temata

V podstatě ano, kvantové kanály neslouží k samotnému přenosu tajné informace, ale právě jen k bezpečnému generování a distribuci náhodného klíče. Pokud je Alice schopná se s Bobem na dálku bezpečným způsobem domluvit na náhodném klíči (což je samostatné téma a klíč musí samozřejmě splňovat požadavek na potřebnou délku), může následně s pomocí one-time pad metody poslat tajná data bezpečným způsobem nezabezpečeným kanálem.

V praxi je potřeba se vypořádat ještě s některými fyzikálními problémy, v neideálním světě totiž bude docházet k chybám při posílání klíče a u nich Bob nedokáže rozlišit, zda byly chyby způsobeny skutečně odposlechem, nebo jen nepřesností přístrojů, což je problém. To lze částečně napravit za pomoci procesů, které chyby opravují a zesilují bezpečnost. Na to je ovšem třeba obětovat část bitů z prostého klíče, jinými slovy publikovat výsledky některých měření atd.