Elbukott a titkosítás: feltörték a szuperszámítógépet

A jövő kvantumszámítógépeinek egyik kiemelkedő képessége az lesz, hogy nagyon gyorsan fel tudják törni a mai hagyományos számítógépeken használt titkosítást. A titkosítás azonban nagyon hasznos dolog, ezért már a kvantumszámítógépek megjelenése előtt elkezdődött olyan titkosítási algoritmusok kifejlesztése, amelyeket nem tör fel könnyen egy kvantumszámítógép. Amikor azonban egy hagyományos számítógép egymagos processzorral egy óra alatt feltör egy titkosítást, aminek a kvantumszámítógépeken kellene kifognia, az lényegében a teljes ellentéte annak, aminek történnie kellene.

A nyár közepén az amerikai kereskedelmi minisztérium és a szabványügyi hivatal (NIST) bejelentette, hogy kiválasztott négy poszt-kvantumszámítástechnikai titkosító algoritmust, amelyek a RSA és Diffie-Hellman algoritmusokat válthatják. Ezzel egy időben bejelentettek négy további algoritmust, amelyek szintén bekerülhetnek a posztkvantum eszközkészletbe, ha átmennek a többfordulós szigorú próbákon.

A jelöltek közül az első, a SIKE azonban megbukott. A SIKE neve a supersingular isogeny key encapsulation szavakat takarja, a szuperszinguláris izognénia által védett diffie-hellman kulcscsere protokoll egy formája. 

A 70-es években megjelent aszimmetrikus, nyílt kulcsú titkosítás azért jelentett nagy áttörést, mert lehetővé tette, hogy egymás számára teljesen ismeretlen felek is teljes biztonságban kommunikálhassanak a publikus és privát kulcsok ötvözésével. a rendszer azonban a gyakorlatban macerásnak bizonyult, ezért más rendszerek szimmetrikus kulcsokat használnak, amelyet egy enkapszuláció nevű eljárással védenek. Az enkapszulációt a kvantumszámítógépek könnyen feltörik, az új algoritmusok ezt a problémát komplex matematikai konstrukciók segítségével oldják meg. 

Régi matek

A SIKE algoritmust a Leuveni Katolikus Egyetem kutatói, Wouter Castryck és Thomas Decru törték fel, amivel elnyerték a NIST 50 ezer dolláros jutalmát. A titkosítás törésének elméleti háttere olyan matematika, ami nem matematikusok számára nem járható terep. Annyi mindenesetre tudható róla, hogy a titkosításnál használt ellipszisek tulajdonságait felhasználó módszer sebezhetőségét Ernst Kani fedezte fel 1997-ben „ragasztás és vágás” nevű teorémájában, amit matematikusok 2000-ben fejlesztettek támadási eszközzé, amely alapján 2016-ban publikáltak egy „GPST adaptív támadás” nevű törési módszert. A módszer szépsége, hogy a támadáshoz egyáltalán nincs szükség kvantumszámítógépre.

Idén ez a második poszt-kvantum titkosításra jelölt, amely elbukott. Februárban az IBM kutatója Ward Beullens publikált, amelyben egy kvadratikus egyenletekből álló összetett rendszer megoldásaira támaszkodó megoldás, a Rainbow titkosítását törte fel. A Rainbow a tesztek harmadik körében, míg a SIKE a negyedik körben esett el. Utóbbi azért kirívó eset, mert úgy ment át három korábbi körön, hogy végül klasszikus algoritmussal törték fel.

David Jao, a Waterloo Egyetem professzora és a SIKE feltalálója vártalannak nevezte a titkosítását ért csapást és nagyon szerényen csak ennyit mondott az esetről:

Általában véve rengeteg olyan mély matematika létezik, amit a matematikai irodalomban közöltek, de a kriptográfusok nem értik eléggé. Magamat a matematikusok azon széles csoportjába helyezem, akik nem értik annyira a matematikát, amennyire kellene. Szóval néha elég, ha valaki felismeri a létező elméleti matematika alkalmazhatóságát az új kriptográfiai rendszerekben. Ez történt itt is.

(Ars Technica)

(Borítókép: Képünk illusztráció. Fotó:  Gavin Roberts / PC Plus Magazine / Getty Images)