Instytut Łączności

Określenie ‘post-kwantowa’ odnosi się do epoki po pojawieniu się komputerów kwantowych, zdolnych uruchomić algorytm Shora. Już w 1994 r. Peter Shor pokazał, że odpowiednio duży komputer kwantowy rozwiąże w czasie wielomianowym faktoryzację liczb (RSA) i dyskretny logarytm (Diffie-Hellman, ECDSA), czyli stosowane powszechnie algorytmy kryptografii asymetrycznej. To oznaczało wyrok dla dzisiejszych algorytmów, tyle że wykonanie wyroku odroczył brak sprzętu o odpowiedniej mocy obliczeniowej.

Obecnie komputery kwantowe są jeszcze zbyt słabe, by łamać nasze szyfry. Jednak kryptolodzy już teraz muszą działać z wyprzedzeniem, bo migrowanie całego internetu na nowe algorytmy protokoły trwa latami. Trudno czekać do ostatniej chwili – stąd wyścig po algorytmy odporne na przyszłe ataki kwantowe. 

Skoro postkwantowa kryptografia nie wykorzystuje fizyki kwantowej, to jak zamierza oprzeć się mocy komputerów kwantowych? Rozwiązaniem są klasyczne algorytmy kryptograficzne, ale oparte na takich problemach matematycznych, dla których nie znamy efektywnego algorytmu kwantowego. Innymi słowy: bazujemy na łamigłówkach trudnych, zarówno dla zwykłych komputerów, jak i (o ile wiemy) dla kwantowych. Przykłady takich matematycznych łamigłówek pojawiały się już dekady temu. Słynny system McEliece (1978) wykorzystuje teorię kodów korekcyjnych – jego bezpieczeństwo sprowadza się do problemu dekodowania losowych kodów liniowych, który przetrwał ponad 40 lat kryptanalizy. Inna rodzina to algorytmy wykorzystujące mechanizm kratownic (i układy równań liniowych z szumem), zapoczątkowane w latach 90. i rozwijane aż po współczesne konstrukcje typu CRYSTALS-Kyber czy Dilithium. Do tego dochodzą koncepcje oparte na wielomianach (np. podpis Rainbow bazuje na układach równań kwadratowych), na funkcjach haszujących (np. rodzina SPHINCS), czy na szczególnych własnościach krzywych eliptycznych (schematy isogeny, jak SIDH/SIKE). Co kilka lat naukowcy proponują nową klasę problemów i algorytmów – byleby tylko znaleźć następców RSA/ECC (krzywe eliptyczne), zanim powstaną komputery kwantowe.

Przez długi czas postkwantowa kryptografia była domeną akademickich konferencji. Jednak prawdziwe przyspieszenie nastąpiło, gdy amerykański instytut standardów i technologii (NIST) ogłosił globalny konkurs na standardy postkwantowe (2016). Zgłoszono 69 kandydatów do I rundy, spośród których, w roku 2024, po kilku latach analiz wyłoniono finałową czwórkę: algorytmy CRYSTALS-Kyber (wymiana klucza) oraz CRYSTALS-Dilithium, FALCON i SPHINCS+ (podpisy cyfrowe). Wszystkie one opierają się na problemach badanych od dawna – głównie kratownicach (Kyber, Dilithium, Falcon) lub drzewach haszujących (SPHINCS). Następnie, NIST dobrał algorytm wymiany klucza HQC  oparty na kodach i rozpoczął kolejną rundę poszukiwań nowych podpisów cyfrowych. Choć nie mamy matematycznego dowodu bezpieczeństwa tych schematów wobec komputerów kwantowych (takiego dowodu może nigdy nie być), to fakt, że bazują na “starych”, trudnych problemach, wyznacza pewien poziom zaufania. Im więcej lat bez przełomu w kryptanalizie, tym lepiej dla danego kandydata.

W idealnym świecie nowy algorytm zastępujący RSA lub krzywe eliptyczne powinien być równie szybki i wygodny jak one. Niestety, realia są takie, że nie ma ideału – każda propozycja postkwantowa ma jakieś poważne wady w porównaniu do klasycznych rozwiązań. Najczęściej problemem jest rozmiar parametrów kryptograficznych: klucze publiczne i szyfrogramy bywają ogromne. Wiele algorytmów PQC wymaga znacznie większych rozmiarów kluczy niż klasyczne systemy ery przedkwantowej. Dla przykładu, klasyczny algorytm McEliece zapewnia wysoki poziom bezpieczeństwa, ale jego publiczny klucz ma rozmiar 1 megabajta!  Nawet algorytmy kratowe wybrane przez NIST generują klucze rzędu kilkuset bajtów. To wciąż dużo więcej niż np. 32-bajtowy klucz publiczny w krzywych eliptycznych czy 64-bajtowy podpis ECDSA.

Co to oznacza dla nas? Prawdopodobnie świat postkwantowy będzie korzystał z kilku standardów jednocześnie, w różnych zastosowaniach. Wysiłek w zapewnieniu sprawności nowych schematów wkładają zespoły z całego świata – jednym z wiodących badaczy implementacji postkwantowych (zwłaszcza na sprzęcie FPGA) jest m.in. prof. Kris Gaj z George Mason University, który wraz z zespołem od lat optymalizuje i porównuje sprzętowe wersje finalistów NIST. Takie prace pokazują, że sprytna inżynieria może znacząco ulepszyć rozwiązanie, ale pewnych ograniczeń matematyki nie przeskoczymy. 

W roku 2022 świat postkwantowej kryptografii doświadczył trzęsienia ziemi – niektórzy mówią wręcz o armagedonie. Dwa obiecujące algorytmy, które dotarły bardzo daleko w procesie standaryzacji NIST, zostały spektakularnie złamane. Stało się to na krótko przed planowanym ogłoszeniem standardów, co jednocześnie przeraziło i... ucieszyło kryptografów. Te algorytmy to Rainbow schemat podpisu cyfrowego oparty na wielomianach wielowartościowych) oraz protokół uzgadniania klucza SIKE (oparty na izogeniach supersingularnych krzywych eliptycznych). Oba od lat uchodziły za mocnych kandydatów odpornych na moc obliczeniową komputerów kwantowych, oba przetrwały wcześniejsze rundy oceny. Aż tu nagle okazało się, że lód, po którym stąpaliśmy, był jednak zbyt cienki... i pękł.

Jak do tego doszło? W pogoni za wydajnością wdrożeń sprzętowych algorytmów, projektanci często wprowadzają pewne udoskonalenia lub dodatkową strukturę matematyczną do swoich schematów. To tak, jak budować skrót przez zamarznięte jezioro – żeby było szybciej – licząc, że lód wytrzyma. Niestety, może się on załamać. W przypadku Rainbow próbowano przyspieszyć klasyczny schemat Oil&Vinegar przez “zagnieżdżenie” go warstwowo. Przez lata wydawało się to bezpieczne, aż kryptolog Ward Beullens znalazł sprytny atak. Podpis Rainbow udało się podrobić w około 53 godziny na zwykłym laptopie. Co więcej, atak Beullensa został praktycznie wdrożony – autor opublikował kod, więc każdy mógł go uruchomić i przekonać się o skuteczności.

Jeszcze większym echem odbiło się złamanie algorytmu SIKE (Supersingular Isogeny Key Encapsulation). SIKE dotarł aż do finału NIST – był jednym z czterech faworytów. Latem 2022 trzy niezależne grupy badaczy dokonały przełomu. Tu warto wskazać jeden z ich. Wouter Castryck i Thomas Decru, znaleźli sposób na pełne złamanie SIKE na pojedynczym rdzeniu procesora w około 1 godzinę (dla podstawowego wariantu bezpieczeństwa). Mocniejsza wersja (SIKEp751) padła w ciągu  ok. 21 godzin – wciąż godzin, nie lat! To niewiarygodne, jeśli pomyślimy, że mówimy o ataku na algorytm, który miał chronić przed komputerem kwantowym. Co ważne, atak Castrycka i Decru jest czysto klasyczny – nie wymaga żadnego kwantowego sprzętu.

Oba te wydarzenia były szokiem dla społeczności kryptologów. NIST błyskawicznie wykluczył Rainbow i SIKE z dalszych prac standaryzacyjnych. Można powiedzieć, że dobrze że stało się to teraz, a nie za kilka lat, gdy np. SIKE zdążyłby wejść do powszechnego użytku. Mimo to 2022 zapisał się jako bolesna lekcja pokory. Kryptolodzy zdali sobie sprawę, że niektóre konstrukcje były jak wspomniany cienki lód – wyglądały solidnie, ale brakowało im zapasu bezpieczeństwa. 

Nie każdy głośny “atak” kończy się faktycznym obaleniem algorytmu. Czasem zdarza się sytuacja odwrotna – ktoś ogłasza przełom w łamaniu kryptografii, ale po analizie okazuje się, że to błąd. Takie przypadki, choć mogą wywołać panikę, finalnie wzmacniają zaufanie do algorytmów: skoro przetrwały próbę ognia, możemy spać spokojniej. Dobrym przykładem jest historia z roku 2024, kiedy to pewien szanowany, który prezentował na najbardziej znanych konferencjach uczony z Szanghaju, prof. Yilei Chen, opublikował pracę pt. “Quantum Algorithms for Lattice Problems” (w repozytorium ePrint jako publikacja 2024/555). Ogłosił w niej, że znalazł skuteczny algorytm kwantowy rozwiązujący w czasie wielomianowym wariant problemu Learning With Errors (LWE). Jeśli te rewelacje by się potwierdziły, byłaby to kryptograficzna bomba – LWE to podstawa większości postkwantowych schematów (m.in. Kyber, Dilithium). Innymi słowy, Chen sugerował: “komputery kwantowe jednak poradzą sobie z kratownicami!”. Trudno się dziwić, że w środowisku zawrzało. Trwało gorączkowe weryfikowanie dowodu Chena – wielu specjalistów próbowało zrozumieć i powtórzyć jego wynik. Wydawało się, że oto nadciąga kwantowy kryzys dla całej klasy algorytmów kratowych.

Na szczęście, ku wielkiej uldze wszystkich, okazało się, że praca Chena zawierała istotny błąd. Niezależnie dwie grupy badaczy doszły do wniosku, że pewien krok w algorytmie jest błędny i cały dowód się załamuje. Sam Chen szybko przyznał rację krytykom i wycofał swoje śmiałe twierdzenia. Innymi słowy, rzekomy “wielomianowy algorytm kwantowy” nie zadziałał. Społeczność odetchnęła z ulgą, a cała sprawa stała się ciekawą anegdotą. Można to uznać za zwycięstwo algorytmów postkwantowych – kolejne potwierdzenie, że nie poddadzą się bez walki. Warto zauważyć, że takie sytuacje są również cenne z punktu widzenia naukowego: mobilizują środowisko do dokładnego prześwietlenia podstaw bezpieczeństwa. Każdy fałszywy alarm sprawia, że rośnie nasze przekonanie, iż obecne algorytmy zostały naprawdę solidnie przeegzaminowane.

Na zakończenie warto wspomnieć o jeszcze jednym aspekcie: praktycznej implementacji nowych algorytmów. Nawet najlepszy schemat kryptograficzny może okazać się dziurawy, jeśli zostanie nieumiejętnie zaimplementowany. Zagrożeniem są tzw. ataki kanałem bocznym (side-channel attacks), czyli wykorzystanie informacji pobocznych wyciekających z urządzenia podczas wykonywania operacji kryptograficznych. To trochę jak “telefon do przyjaciela” w teleturnieju – zamiast rozwiązać zagadkę samodzielnie, podglądamy fragment odpowiedzi. W kontekście kryptografii takim “podglądaniem” mogą być np. pomiary poboru prądu czy czasu wykonywania obliczeń. Niestety, dzisiejsze algorytmy (szczególnie podpisy ECDSA oparte na krzywych eliptycznych) są bardzo czułe na tego typu wycieki. Jeśli atakujący zdoła podejrzeć choćby kilka bitów sekretnego klucza lub losowej liczby używanej w podpisie, to może wykorzystać sprytne metody (np. algorytm Hidden Number Problem z metodą LLL) i odzyskać cały klucz prywatny. W literaturze pokazano, że nawet ujawnienie jednego bitu z każdego klucza w wystarczającej liczbie podpisów może złamać ECDSA – to wręcz niewiarygodnie krucha konstrukcja. Również subtelne niedostatki generatora liczb losowych (rzędu kilku bitów niepewności) wystarczyły, by złamać ECDSA za pomocą technik kratowych.

Przed tego typu atakami broni się implementacja, nie matematyka. Stosuje się techniki, takie jak programowanie stałoczasowe (algorytm wykonuje zawsze dokładnie te same operacje, niezależnie od wartości klucza) czy maskowanie danych (wprowadzanie losowego szumu do zużycia energii). Niestety, im bardziej złożony algorytm, tym trudniej upewnić się, że nic nie zdradza sekretów. 

Czy algorytmy postkwantowe rozwiążą ten problem? Niestety, dla wielu obecnych rozwiązań kryptografii postkwantowej ataki kanałem pobocznym są głównym problemem. Na szczęście jest jeszcze trochę czasu na badania w tym obszarze. Instytut Łączności – PIB prowadzi badania w obszarze wytworzenia metod oceny odporności implementacji algorytmów postkwantowych na ataki kanałem pobocznym. Celem jest zagwarantowanie, że gdy nowe algorytmy trafią do urządzeń (czy to smartfon, czy karta sieciowa), nie powtórzą się stare błędy znane z wdrożeń ECDSA. Dzięki solidnej konstrukcji matematycznej i bezpiecznej implementacji postkwantowa kryptografia ma szansę być nie tylko odporna na komputery kwantowe, ale i na bardziej przyziemne sztuczki.

Kryptografia postkwantowa to fascynująca dziedzina na styku matematyki, informatyki i inżynierii. Choć pełnoskalowych komputerów kwantowych jeszcze nie mamy, wyścig z czasem trwa. Po drodze czekają nas i wzloty (nowe odkrycia, udane standaryzacje), i upadki (spektakularne ataki, dyskwalifikacje kandydatów). Jednak obserwując tempo rozwoju oraz zaangażowanie globalnej społeczności, można mieć nadzieję, że nie damy się zaskoczyć. Gdy kwantowe mrozy nadejdą, kryptografia nie pozostanie bezbronna, będzie uzbrojona po zęby w dobrze przebadane, odporne algorytmy. A to wszystko bez użycia kwantowych cudów, jedynie z mądrym wykorzystaniem klasycznej nauki i sprytu człowieka. Bez kwantów – a jakże skutecznie! 

Autor: Daniel Waszkiewicz, Zakład Cyberbezpieczeństwa oraz Technologii i Zastosowań Internetu, Instytut Łączności - PIB