Jesteśmy spóźnieni. Problemy postkwantowej kryptografii
Na całym świecie eksperci w dziedzinie cyberbezpieczeństwa wpatrują się w zegar Y2Q – „Years to Quantum”, który odlicza czas do prognozowanej daty, gdy komputer kwantowy będzie w stanie złamać podstawowe zabezpieczenia współczesnej kryptografii. Chodzi o tzw. kryptografię klucza publicznego opartą na genialnej metodzie publicznego udostępniania tajnych kodów, która zabezpiecza numer karty kredytowej podczas zakupów online i gwarantuje, że aktualizacja oprogramowania telefonu pochodzi od teleoperatora, a nie od hakera. Sygnaliści (whistleblowers) korzystają z niej, kontaktując się z dziennikarzami, a firmy – przesyłając poufne pliki.
Komputer kwantowy uczyniłby zatem standardową kryptografię klucza publicznego bezużyteczną. „To bardzo poważna sprawa – mówi Bruno Huttner, współprzewodniczący Quantum-Safe Security Working Group w Cloud Security Alliance. – Gdyby jutro pojawił się komputer kwantowy, nasza komunikacja zostałaby pozbawiona zabezpieczeń”.
Huttner jest jednym z twórców zegara Y2Q, nazwanego tak na wzór kryzysu Y2K z końca lat 90. W XX wieku w programach lata oznaczano tylko dwiema cyframi, więc rok „00” był zarówno 1900, jak i 2000. Spodziewano się więc dramatycznych skutków zakłóceń w działaniu programów w XXI wieku. Ostatecznie jednak, gdy nastał rok 2001, nie upadły żadne banki, nie wyłączyły się sieci energetyczne i nie spadł żaden samolot. Przejście przebiegło bezproblemowo – głównie dlatego, że firmy i rządy skorygowały błąd.
Nikt nie wie dokładnie, kiedy powstanie komputer kwantowy wystarczająco potężny, by złamać standardy kryptograficzne. Obecnym terminem wyznaczonym na zegarze Y2Q jest 14 kwietnia 2030 roku, ale to tylko hipoteza. Większość badaczy uważa, że nastąpi to w ciągu najbliższych kilku dekad. „Nadchodzi zagrożenie, a podawanie konkretnej daty o nim przypomina” – zauważa Huttner.
Dla rządów i instytucji, którym zależy na zachowaniu tajemnicy przez dłuższy czas, termin ma znacznie większe znaczenie. Jeśli zakodowane i wysłane dziś dane będą zapisane, to ich rozszyfrowanie przez przyszły komputer kwantowy nada im mocy wstecznej. „Jeżeli chcesz zachować tajemnicę przez 20 lat i uważasz, że komputery kwantowe zdolne złamać twoją kryptografię mogą pojawić się w ciągu 20 lat, to masz problem” – ostrzega informatyk Chris Peikert z University of Michigan.
Przewidując to zagrożenie, National Institute of Standards and Technology (NIST) ogłosił w 2016 roku publiczny konkurs na pomysły kryptografii „postkwantowej”, czyli algorytmy, działające na współczesnych komputerach, ale tak solidne, że nawet komputery kwantowe nie byłyby w stanie ich złamać. W grudniu 2022 roku Kongres Stanów Zjednoczonych wzmocnił tę inicjatywę, przyjmując ustawę Quantum Computer Cybersecurity Readness Act, która nakłada na agencje rządowe obowiązek stworzenia planu przejścia na takie algorytmy.
Po czterech etapach zgłoszeń i ocen NIST uznał za najlepsze algorytmy CRYSTALS-Kyber w kategorii szyfrowania z kluczem publicznym i trzy inne w kategorii podpisów cyfrowych używanych do bezpiecznej identyfikacji nadawcy wiadomości. Obecnie NIST współpracuje z naukowcami nad standaryzacją zwycięskich algorytmów, aby programiści mogli rozpocząć tworzenie wersji kwantowoodpornej.
Nieco niepokojące jest jednak to, że trzy z czterech wybranych algorytmów, w tym CRYSTALS-Kyber, opierają się na matematyce krat. Zdaniem ekspertów wiąże się to z bardzo trudnymi problemami, które jednak w przyszłości mogą zostać rozwiązane.
Jedną z pierwszych form kryptografii był szyfr z podstawianiem zwany szyfrem Juliusza Cezara, który zastępował każdą literę tekstu literą oddaloną od niej o trzy pozycje. Zatem „a” zmieniało się w „d”, „b” w „e” itd. By odszyfrować wiadomość wystarczyło odwrócić ten proces, cofając litery o trzy pozycje.
Istnieje nieskończenie wiele odmian szyfru Cezara. Dzieci bawią się czasem, zastępując „a” sercem, „b” gwiazdką itd., ale taki szyfr łatwo złamać. Nietrudno na przykład zauważyć, że jeśli wśród symboli jest dużo izolowanych trójkątów, reprezentujących jednoliterowe słowo, to trójkąt ten oznacza najprawdopodobniej „a” lub „i”. Łamacze kodów radzą sobie zwykle z bardziej skomplikowanymi schematami podstawienia, korzystając z częstości występowania liter w typowych tekstach.
Złoty standard współczesnej kryptografii, znany jako Advanced Encryption Standard (AES), radykalnie komplikuje metodę Cezara. Szyfruje wiadomość, wielokrotnie podstawiając wpisy i tasując je jak talię kart do gry. Po wystarczająco dużej liczbie tasowań i podstawień bardzo trudno jest odtworzyć oryginalną wersję.
Aby odszyfrować wiadomość, należałoby cofnąć całą serię tasowań i podstawień. W przypadku rzeczywistej talii kart jest to prawie niemożliwe – trudno ustalić kolejność szybkich ruchów. Natomiast komputer tasuje wiadomość zgodnie z precyzyjnym zestawem instrukcji – na przykład „przenieś drugi wpis na piąte miejsce” – które łatwo cofnąć, polecając komputerowi odwrócenie kolejności: „przesuń piąty wpis na drugie miejsce”.
Podobnie jak szyfr Cezara, AES ma symetryczne procedury szyfrowania i dekryptażu. Stosuje ten sam proces wprost i wspak, podobnie jak przekręca się klucz w przeciwnych kierunkach, aby zamknąć i otworzyć drzwi. Do lat 70. taka kryptografia symetryczna lub z kluczem symetrycznym była jedynym znanym rodzajem kryptografii. Ma ona jednak istotne ograniczenie: nadawca i odbiorca muszą uzgodnić procedurę szyfrowania i deszyfracji przed wymianą wiadomości – osobiście lub za pośrednictwem poufnego, odrębnego sposobu komunikacji.
Trudno wyobrazić sobie alternatywną metodę dla kryptografii symetrycznej pozbawioną tego ograniczenia. Kiedy więc w roku 1974 student University of California w Berkeley Ralph Merkle przedstawił projekt dotyczący badania metod umożliwiających „bezpieczną komunikację dwóch osób bez żadnych wcześniejszych ustaleń”, zaczął od wyjaśnienia: „to nie żart”. Merkle przewidział możliwość systemu, w którym dwie osoby wymieniają się jawnie wiadomościami, do których ktoś ma dostęp, a mimo tej otwartej korespondencji udaje im się bezpiecznie ustalić schemat kodowania i dekodowania wykorzystywany do wysyłania tajnych wiadomości. Ktoś postronny, czytając korespondencję, nie byłby w stanie zrozumieć schematu. Propozycja Merkle’a została odrzucona przez eksperta ze względu na „nierealistyczne założenia robocze”.
Tymczasem parę lat później pomysł Merkle’a został skonkretyzowany w kilku pracach matematycznych. Dwa z zaproponowanych wówczas algorytmów – Diffie-Hellman i RSA (skrót od nazwisk autorów – Rivest, Shamir, Adleman) – są przyjęte we współczesnej komunikacji. Okazało się też, że jeszcze przed projektem Merkle’a badacze z wywiadu brytyjskiego opracowali takie kodowanie, czyli kryptografię klucza publicznego, ale trzymali to w tajemnicy.
Kiedy sprawdzamy swoje konto bankowe online, nasz komputer i serwer banku wymieniają wiadomości: wysyłamy hasło, a bank przesyła saldo. Informacje są przesyłane przez Internet, ale ktoś niepowołany mógłby je przejąć, muszą więc być zaszyfrowane.
Większość wiadomości szyfrowana jest z użyciem kryptografii symetrycznej, takiej jak AES – szybko i skutecznie. Najpierw jednak komputer i serwer komunikacyjny muszą uzgodnić konkretną procedurę szyfrowania, która nie może być po prostu zapisana, bo ktoś mógłby ją przejąć. Należy więc skorzystać z kryptografii klucza publicznego.
Aby zrozumieć, jak działa ten klucz, wyobraźmy sobie, że dwie osoby, Alicja i Bob, prowadzą piekarnię ze ściśle tajnym przepisem na brownie (amerykańskie ciasto czekoladowe) – tak tajnym, że nawet Alicja i Bob nie znają pełnego przepisu. Każde z nich dodaje specjalny składnik znany tylko temu, kto go dodaje. Oboje rozpoczynają sporządzanie ciasta w różne dni. Czasami Alicja zaczyna mieszanie podstawowych składników ze swoim tajnym i pozostawia ciasto Bobowi, który dodaje swój sekretny składnik i piecze. Innym razem najpierw Bob łączy podstawowe składniki ze swoim sekretnym, a potem Alicja dodaje swój tajny składnik i kończy wypiek.
Efektem jest zawsze takie samo ciasto, którego pełnego składu Alicja i Bob nie znają, a o tym, co sami wiedzą, nikogo nie informują, nawet siebie nawzajem. Nawet przebiegła Ewa, zajmująca się dostawą ciast do sklepów, nie może odkryć sekretnych składników, bo w cieście są one wymieszane z innymi i nie sposób ich rozdzielić (w opisach kryptografii osoby przekazujące sobie tajemnice tradycyjnie są zwane Alicją i Bobem, a potencjalnym szpiegiem jest często Ewa).
Oczywiście komputery nie pieką ciast. Operują liczbami i matematyką. W kryptografii klucza publicznego celem jest uzyskanie wspólnego tajnego numeru – czegoś w rodzaju tymczasowego hasła, które zapewnia dostęp do prywatnej rozmowy – po czym oba komputery mogą komunikować się, korzystając z kryptografii symetrycznej, takiej jak AES.
Różne rodzaje kryptografii klucza publicznego tworzą i udostępniają hasło tymczasowe w różny sposób. Alicja i Bob ukryli przed Ewą przepis na ciasto, mieszając składniki przed transportem. Osoba wdrażająca kryptografię klucza publicznego zamiast tego użyłaby funkcji matematycznych do łączenia tajnych liczb.
Funkcje przypominają maszyny, które pochłaniają liczby, przetwarzają je i wypluwają nową liczbę. Funkcje stosowane w kryptografii klucza publicznego są specyficzne. Wymaga się od nich, aby łatwo mieszały liczby, ale by po wymieszaniu ich rozdzielenie było bardzo trudne. Nawet jeśli Ewa zobaczy liczbowy efekt działania funkcji, nie powinna być w stanie ustalić, które tajne liczby zostały wprowadzone jako dane wejściowe.
Kryptografia RSA opiera się na funkcji mnożenia i jej przeciwieństwie, czyli faktoryzacji. Mieszanie liczb poprzez ich mnożenie jest łatwe dla komputera, nawet jeśli liczby są bardzo duże. Jednak faktoryzacja, a więc cofnięcie mnożenia, bywa bardzo trudne, gdy liczby są duże (faktoryzacja jest odpowiedzią na pytanie: jakie liczby muszę przez siebie pomnożyć, aby otrzymać daną liczbę?; na przykład rozkład 21 na czynniki pierwsze daje 3 i 7.) Odszyfrowanie hasła utworzonego za pomocą RSA wymagałoby rozłożenia na czynniki bardzo dużej liczby. Najlepsze metody polegają na sprawdzaniu wielu liczb w celu znalezienia ich określonej kombinacji, a to zajęłoby komputerowi mnóstwo czasu.
„Zamiast coraz bardziej komplikować schematy kryptograficzne przeszliśmy na kryptografię opartą na bardzo prostych zależnościach, takich jak faktoryzacja liczb całkowitych badana od tysięcy lat” – wyjaśnia informatyk Boaz Barak z Harvard University.
W 1994 ROKU zajmujący się matematyką stosowaną Peter Shor, wówczas pracownik naukowy Bell Labs, odkrył sposób, w jaki komputer kwantowy może złamać dowolny kod zaszyfrowany za pomocą RSA lub algorytmu Diffiego-Hellmana. Będąc na wykładzie dotyczącym wykorzystania komputerów kwantowych do rozwiązywania problemów matematycznych o strukturze okresowej, czyli powtarzalnej, Shor przypomniał sobie o problemie logarytmu dyskretnego. Funkcja logarytmiczna jest odwrotnością funkcji wykładniczej, a zadanie polega na przykład na wyznaczeniu x z równania 2x = 16.
Zwykle jest to łatwe, ale problem logarytmu dyskretnego polega na obliczaniu logarytmu z użyciem alternatywnych form arytmetyki, w których liczy się po okręgu, jak na zegarze. Jak RSA opiera się na faktoryzacji, tak algorytm Diffiego-Hellmana na problemie logarytmu dyskretnego. Informatycy na ogół uważają, że nie ma szybkiej metody znalezienia logarytmu dyskretnego za pomocą klasycznego komputera. Ale Shor znalazł sposób uporania się z tym na komputerze kwantowym. Następnie w podobny sposób pokazał, jak wykorzystać komputer kwantowy do szybkiego rozkładu na czynniki pierwsze dużych liczb. Sposób ten znany jest jako algorytm Shora.
Shor nie rozważał programowania prawdziwego komputera kwantowego – po prostu wykonywał obliczenia matematyczne na kartce. „W tamtym czasie uważano, że komputery kwantowe to odległa przyszłość, więc traktowałem to jako urokliwe twierdzenie matematyczne” – wspomina Shor. Jego algorytm wiąże się jednak ściśle z kryptografią klucza publicznego. Mógłby być wykorzystany przez komputer kwantowy do złamania niemal wszystkich obecnie używanych systemów kryptograficznych.
Klasyczne komputery działają na długich ciągach zer i jedynek zwanych bitami, natomiast w komputerach kwantowych jednostkami są kubity (połączenie początku słowa „kwant” i słowa „bit”). Kubity mogą tworzyć superpozycje – osobliwe stany kombinacji zer i jedynek, a balansując między dwoma stanami, umożliwiają komputerom kwantowym wykonywanie określonych zadań znacznie szybciej niż komputery klasyczne. Jednak komputery kwantowe są „wybredne”. Kubity powinny utrzymywać superpozycję podczas działania algorytmu, tymczasem mają tendencję do „zapadania się” w ciąg zer i jedynek.
Komputery kwantowe wyglądają imponująco – zwisają z sufitu jak masywne złote żyrandole – ale wciąż nie są zbyt potężne. Naukowcom udało się przeprowadzić obliczenia ze skromną liczbą kubitów. Największa, jaką poddano faktoryzacji na komputerze kwantowym z użyciem algorytmu Shora, to zaledwie 21: w 2012 roku badacze z University of Bristol w Anglii wykorzystali komputer kwantowy, aby wykazać, że 21=3×7.
Wielu ekspertów uważa, że komputer kwantowy dostatecznie duży, aby złamać algorytmy RSA i Diffiego-Hellmana, powstanie w ciągu kilku dekad, ale przyznają, że nie jest to pewne. Dla kryptografów, którzy muszą ubiec komputery kwantowe, niepewność jest niepokojąca. „Każda branża ma pewien aspekt, który jest dla niej niezwykle istotny” – mówi Ray Harishankar z IBM. Firmy związane z opieką zdrowotną muszą zabezpieczać dane wykorzystywane w badaniach medycznych, a przedsiębiorstwa korzystające z sieci informatycznych muszą chronić je przed hakerami. „W najgorszym scenariuszu złamanie zabezpieczeń prowadzi do całkowitego ujawnienia poufnych danych” – podsumowuje Harishankar.
Każdy rodzaj kryptografii klucza publicznego jest oparty na trudnym matematycznym problemie. Aby zabezpieczyć tajemnice przed przyszłym kwantowym zagrożeniem, badacze muszą korzystać z problemów tak złożonych, aby nawet komputer kwantowy nie mógł sobie z nimi poradzić w rozsądnym czasie. W ramach konkursu NIST wybierano takie algorytmy kryptograficzne z kluczem publicznym, które można by powszechnie wdrożyć na standardowych komputerach jako alternatywne rozwiązanie dla algorytmów RSA i Diffiego-Hellmana. „Większość powszechnie stosowanych systemów i urządzeń powinna być przystosowana do nowego rodzaju kryptografii” – wyjaśnia Lily Chen, matematyk z NIST.
Na zakończony w 2017 roku konkurs wpłynęły 82 propozycje dotyczące kryptografii postkwantowej (nie należy mylić tego pojęcia z „kryptografią kwantową”, która dotyczy wykorzystania zjawisk kwantowych jako zabezpieczeń). Po wstępnym testowaniu eksperci NIST wybrali 26 algorytmów skierowanych do kolejnej rundy.
Udział szerszego grona opiniodawców jest istotną częścią konkursu NIST. Nie ma gwarancji, że systemy kryptograficzne będą bezpieczne, dlatego wiele osób próbuje znaleźć ich słabe strony. Jeden z proponowanych algorytmów wykorzystywał badaną od dekady kryptografię opartą na izogenii, która wydawała się obiecująca. Jednak dwóch badaczy zauważyło, że do złamania takiego algorytmu można wykorzystać znane od ćwierćwiecza twierdzenie, co zajęło im zaledwie godzinę z użyciem standardowego laptopa.
Ostatecznie eksperci NIST wskazali na kilka algorytmów, z których większość korzystała z teorii krat. „Kraty, których różne aspekty były badane od ponad dwóch dekad, stanowiły naturalny wybór” – mówi Vadim Lyubashevsky z IBM, jeden z twórców CRYSTALS-Kyber.
Krata jest układem rozmieszczonych regularnie punktów. Jedna z najprostszych przypomina tablicę perforowaną – punkty umieszczone w węzłach siatki kwadratowej. Matematycy traktują taką siatkę jako utworzoną z dwóch powtarzających się odcinków równej długości – poziomego i pionowego. Jeśli od punktu umieszczonego na środku kartki poprowadzimy dwa poziome i dwa pionowe odcinki zakończone punktem i od każdego nowego punktu wykonamy taką samą czynność, to powstanie siatka kwadratowa, a punkty będą tworzyć kratę. Różne zestawy pary odcinków tworzą różne kraty. Odcinki mogą mieć różną długość i mogą być prowadzone pod różnymi kątami. Efektem będzie wówczas także regularny układ punktów, ale ich rzędy będą względem siebie przesunięte lub umieszczone w różnych odległościach.
Z kratami wiążą się zaskakująco trudne problemy matematyczne. Na przykład: rysujemy na kartce dwa odcinki, które uznajemy za elementy siatki. Potem gdzieś obok oznaczamy punkt. Problem stanowi znalezienie punktu kraty najbliższego temu oznaczonemu.
W tym przypadku można, korzystając z narysowanych odcinków podstawowych, rozpocząć wyznaczanie punktów kraty i ostatecznie znaleźć ten najbliższy. Jest to jednak możliwe tylko dlatego, że siatka na kartce jest dwuwymiarowa. Nasza wyobraźnia ogranicza się do trzech wymiarów, ale matematycy mogą opisywać kraty o setkach wymiarów, a w nich bardzo trudno jest znaleźć w opisanej sytuacji najbliższy punkt.
Tak obszerne kraty wykorzystywane są w systemach kryptograficznych. Na przykład w 1000-wymiarowej kracie wybiera się jeden punkt. Dokładna lokalizacja tego punktu odpowiada tajnej wiadomości. Po odsunięciu się od sekretnego punktu wybiera się inny, którego lokalizację można udostępnić, nie zdradzając sekretnej. Znalezienie sąsiednich punktów kratowych – w tym sekretnego – jest w tej sytuacji bardzo trudnym problemem matematycznym. Jak zmieszanie składników chroni przepis na brownie, tak odsunięcie się od sekretnego punktu zaciemnia jego dokładną lokalizację.
Informatycy od dawna badają takie problemy i uważają je za bardzo trudne do rozwiązania. Jednak projektując nowy algorytm, kryptografowie muszą obok bezpieczeństwa uwzględniać wiele innych kwestii, takich jak ilość informacji, wymienianych przez dwa komputery oraz trudność obliczeń wymaganych przy szyfrowaniu i deszyfrowaniu wiadomości. Pod tym względem wyróżnia się kryptografia oparta na kratach. „To trochę jak w baśni o Złotowłosej – kraty pasują idealnie jako środek do celu, bo wad i zalet mają w sam raz” – uważa Peikert.
Problem w tym, że nikt nie może zagwarantować, iż kryptografia oparta na kratach pozostanie zawsze bezpieczna. Aby uchronić się przed przełomem matematycznym, którym będzie rozwiązanie podstawowego problemu i złamanie kodu, kryptografowie potrzebują dostępu do różnych typów algorytmów. Jednak trzy z czterech finałowych w konkursie NIST-u są oparte na kratach, a jedynym wybranym do standaryzacji w kategorii ogólnego szyfrowania klucza publicznego został CRYSTALS-Kyber.
W konkursie NIST jest także kategoria obejmująca algorytmy podpisu cyfrowego, które potwierdzają nadawcę i niezmienioną treść wiadomości. „Algorytmy szyfrujące gwarantują, że nikt postronny nie będzie tego czytał, a podpis cyfrowy daje pewność, że nie zostało to zmodyfikowane” – wyjaśnia kryptolog Britta Hale z Naval Postgraduate School w Monterey w Kalifornii. Obecnie używane algorytmy podpisu cyfrowego nie są odporne na algorytm Shora. NIST zdecydował się na standaryzację trzech algorytmów podpisu cyfrowego, w tym dwóch opartych na kratach.
Nadmierne zaufanie jednemu problemowi matematycznemu jest ryzykowne. Nikt nie może być pewny, że w końcu problem nie zostanie rozwiązany. Nie oferuje się też użytkownikom żadnej elastyczności, a może się okazać, że inny rodzaj kryptografii lepiej odpowiada ich specyficznym potrzebom. Dlatego NIST rozszerzył proces standaryzacji w obu kategoriach, aby zbadać algorytmy, które nie są oparte na kratach. „Naszym celem nie jest uzależnienie wybieranych przez nas algorytmów od jednego działu matematyki” – wyjaśnia Dustin Moody, matematyk z NIST.
Nawet algorytmy wybrane do standaryzacji wymagały uprzednio poprawek. Dotyczyło to na przykład programu CRYSTALS-Kyber, w którym badacze zauważyli po pierwszej turze zgłoszeń drobny problem i w kolejnym etapie nieco ulepszyli algorytm. „Zmieniliśmy parametry, aby uzyskać kilka dodatkowych elementów bezpieczeństwa” – mówi Peter Schwabe z Max-Planck-Institut für Sicherheit und Privatsphäre w Bochum w Niemczech, jeden z twórców CRYSTALS-Kyber.
Nist jest obecnie w trakcie ustanawiania standardów, opisujących szczegółowo, krok po kroku, sposób wdrażania algorytmów przez programistów komputerowych. „Wszystko w Internecie musi mieć superspecyficzne standardy dopracowane w najdrobniejszych szczegółach; w przeciwnym razie komputery nie będą mogły się ze sobą kontaktować” – podkreśla Lyubashevsky. Po ustaleniu standardów każdy system komputerowy musi przejść na kryptografię postkwantową, ale nie ma jednego momentu, w którym wszyscy naciskają przełącznik. Konkretni producenci oprogramowania muszą zaktualizować swoje protokoły, rządy muszą zmienić swoje wymagania, a sprzęt musi zostać przynajmniej częściowo wymieniony.
Pełne przejście na kryptografię postkwantową zajmie prawdopodobnie wiele lat, jeśli nie dekad. Dopóki to nie nastąpi, wszelkie wiadomości wysyłane z użyciem dotychczasowych metod kryptografii będą potencjalnie narażone na odczytanie przez przyszły komputer kwantowy. W zależności od tego, jak długo chcesz zachować tajemnicę, czas na obawy o jej ujawnienie mógł już minąć. Jak mówi Hale: „W kryptografii wszyscy patrzą na zegarki i mówią: jesteśmy spóźnieni”.