Z kpt. mgr inż. Elżbietą Burek z Wydziału Cybernetyki Wojskowej Akademii Technicznej o kryptografii, projektowaniu i łamaniu szyfrów rozmawia Dominika Naruszko.
Dominika Naruszko: Gdzie w życiu codziennym spotykamy się z kryptografią?
Elżbieta Burek: Właściwie wszędzie – przede wszystkim na protokołach kryptograficznych oparte jest bezpieczeństwo całej komunikacji w Internecie, ale z kryptografią cały czas stykamy się także poza nim. Transakcje, kluczyki do samochodu, bilety w komunikacji miejskiej, cała technologia zbliżeniowa, czyli wszelkie karty zbliżeniowe, kontrola dostępu, na przykład przepustki do pracy, które często mają mikroprocesory czy mikrokontrolery, także wykorzystują kryptografię.
Często spotkać się można z pojęciem kryptografii postkwantowej. Czym ona w ogóle jest?
Kryptografia postkwantowa polega na projektowaniu algorytmów, które uruchamiane są na komputerach klasycznych, ale pozostają bezpieczne zarówno przed atakami wykorzystującymi komputery klasyczne, jak i komputery kwantowe.
Rozróżniamy kryptografię symetryczną i asymetryczną. W kryptografii symetrycznej dwie osoby, które chcą się komunikować, wykorzystują jeden klucz tajny. W przypadku kryptografii asymetrycznej każda z osób ma parę kluczy – prywatny i publiczny – które są ze sobą powiązane. Klucz publiczny udostępniamy osobie, z którą chcemy się komunikować, klucz prywatny ukrywamy. Na podstawie pary kluczy możemy podpisywać lub szyfrować wiadomości, ale ponieważ kryptografia asymetryczna jest dość wolna obliczeniowo, najczęściej wykorzystuje się ją do uzgadniania tajnego klucza dla znacznie szybszej kryptografii symetrycznej.
Kryptografia postkwantowa skupiła się przede wszystkim na kryptografii asymetrycznej, ponieważ pierwszy poważny algorytm wykorzystujący komputery kwantowe, który został opracowany przez Petera Shora, pozwala łamać między innymi problem faktoryzacji.
Na czym polega problem faktoryzacji i dlaczego jest tak istotny?
Problem faktoryzacji polega na rozłożeniu dużej liczby na czynniki pierwsze. Na problemie faktoryzacji oparte jest bezpieczeństwo algorytmu RSA, który stosowany jest również obecnie. Peter Shor opracował algorytm dla komputerów kwantowych, który rozwiązuje ten problem w czasie wielomianowym. Za pomocą tego algorytmu rozwiązywany może być także problem logarytmu dyskretnego.
Jakie ma to znaczenie? Otóż to właśnie na tych problemach są dzisiaj oparte algorytmy kryptografii asymetrycznej, dlatego algorytm Shora spowodował spore poruszenie. Dzięki niemu można poznać klucz prywatny, a tym samym uzyskać dostęp do informacji, które są szyfrowane.
Pojawiło się pytanie, jak zabezpieczyć przed komputerami kwantowymi algorytmy kryptografii asymetrycznej. Dlatego kryptografia postkwantowa skupia się głównie na algorytmach kryptografii asymetrycznej.
Jeśli chodzi o szyfry kryptografii symetrycznej – mamy algorytm Grovera, wykorzystujący komputery kwantowe, który przeznaczony jest do przeszukiwania nieuporządkowanej bazy danych. W klasyczny sposób takie przeszukiwanie średnio wymaga N/2, a w najgorszym przypadku N‑1 zapytań, gdzie N to liczba danych. Dzięki komputerom kwantowym i algorytmowi Grovera przeszukanie może wymagać zapytań. Algorytm Grovera można wykorzystać do ataku na szyfry symetryczne, wykorzystując ideę ataku brutalnego. Atak brutalny polega na przeszukaniu całej przestrzeni kluczy, a więc sprawdzeniu każdej możliwej wartości klucza, w celu znalezienia tego prawidłowego.
Jak można to zablokować?
Szyfry kryptografii symetrycznej można zabezpieczyć przed tym atakiem, wydłużając klucz. Jeśli weźmiemy dwa razy dłuższy klucz, uzyskamy założony poziom bezpieczeństwa. Powiedzmy, że mamy szyfr, dla którego długość klucza wynosi 128 bitów. Gdybyśmy chcieli wykonać atak brutalny na komputerze klasycznym, to musielibyśmy sprawdzić wszystkie możliwe wartości klucza. Wszystkich możliwości w przypadku 128 bitów jest 2128. Jest to na tyle dużo, że sprawdzenie za pomocą komputerów klasycznych jest nieefektywne, tzn. wymagałoby całych dekad. Ale za pomocą komputera kwantowego i algorytmu Grovera takie przeszukanie wymaga wykonania 264 sprawdzeń. To już stosunkowo mało. Dlatego w celu zapewnienia bezpieczeństwa wystarczy użyć dwa razy dłuższego klucza – 256-bitowego i dlatego kryptografia symetryczna uważana jest za relatywnie bezpieczną przed atakami z wykorzystaniem komputerów kwantowych.
Czyli kryptografia postkwantowa dotyczy głównie kryptografii asymetrycznej?
Tak, ponieważ wszystkie problemy obliczeniowe, na których oparte jest bezpieczeństwo obecnych algorytmów kryptografii asymetrycznej, rozwiązywane są w czasie wielomianowym przez algorytm Shora. Jednak obecne komputery kwantowe posiadają za mało fizycznych kubitów, dlatego nie istnieje jeszcze możliwość praktycznego wykonania takiego ataku. Mimo to opracowywane są już algorytmy postkwantowe, które mogą zastąpić obecne algorytmy kryptografii asymetrycznej.
Dlaczego w ogóle powstała kryptografia asymetryczna?
Z powodu problemów z dystrybucją kluczy kryptograficznych. Szyfrowanie symetryczne wiąże się z tym, że musimy przekazać drugiej osobie klucz tajny. Przypuśćmy, że jest ona w Australii. Jak przekazać jej w sposób bezpieczny i niejawny klucz, którym możemy się komunikować? Dlatego powstała kryptografia asymetryczna, która umożliwia „wyliczenie” klucza tajnego na podstawie kluczy prywatnych i publicznych obu użytkowników.
Czym się różni kryptografia kwantowa od postkwantowej?
Kryptografia postkwantowa to algorytmy uruchamiane i działające na komputerach klasycznych, ale mające zabezpieczać przed atakami wykorzystującymi komputery kwantowe. Kryptografia kwantowa to protokoły wykorzystujące zjawiska fizyki kwantowej, takie jak splątanie czy superpozycja.
Przykładem jest protokół QKD, czyli kwantowy protokół dystrybucji klucza, który służy do uzgadniania klucza sesji. W dużym uproszczeniu – generujemy klucz dla szyfru symetrycznego jako ciąg bitów, kodujemy je kwantowo i przesyłamy. Po drugiej stronie osoba odbiera ten zakodowany kwantowo klucz i dekoduje z powrotem na ciąg bitów. Ogólnie wygląda to tak, jak byśmy po prostu przesłali klucz tajny, ale efekty kwantowe pozwalają wykryć, czy ktoś podsłuchał naszą transmisję.
Czy istnieje kryptografia doskonała?
Istnieje szyfr doskonale bezpieczny, jest to szyfr z kluczem jednorazowym. To klasyczny szyfr, zaliczający się do kryptografii symetrycznej, tylko jest niepraktyczny – właśnie z powodu klucza jednorazowego. Jeśli chcemy zaszyfrować daną wiadomość, to potrzebujemy klucza losowego tak długiego jak wiadomość. Ponadto danego klucza możemy użyć tylko raz. Więc żeby Pani wysłała mi wiadomość, to muszę wygenerować losowy klucz, tak długi jak wiadomość i bezpiecznie go Pani przekazać. Mamy tutaj znowu problem dystrybucji klucza. Po zaszyfrowaniu wiadomości tym kluczem należy go usunąć, ponieważ nie wolno go wykorzystać ponownie. Dlatego w celu zaszyfrowania kolejnej wiadomości należy ponownie wygenerować i dostarczyć klucz jednorazowy.
Gdy pojawią się komputery kwantowe, cała nasza komunikacja ulegnie odszyfrowaniu?
Jeśli obecna komunikacja jest przechwytywana oraz archiwizowana, to po pojawieniu się – odpowiednio złożonych – komputerów kwantowych będzie można ją odszyfrować. Brak komputera kwantowego nie sprawia, że jesteśmy bezpieczni. Istnieje ogromna potrzeba postkwantowych standardów bezpieczeństwa. Powinniśmy być gotowi na pojawienie się komputera kwantowego i używać kryptografii postkwantowej.
Kryptografia to bardzo rozbudowany obszar. Na czym polega Pani praca?
Zajmuję się kryptoanalizą. Czyli nie projektuję szyfrów, ale próbuję je złamać.
Opracowała Pani wraz z dr. inż. Michałem Wrońskim z Wydziału Cybernetyki Wojskowej Akademii Technicznej metodę ataków na szyfry lekkie. To nowatorskie podejście i praca.
Wszystko zaczęło się od jednego pytania. Kryptografia symetryczna uważana jest za bezpieczną wobec komputerów kwantowych. Rozwiązaniem ma być tu podwojenie klucza. Zastanawiało nas, czy może istnieć specjalistyczny atak na konkretny szyfr. W przypadku kryptoanalizy klasycznej podstawowym atakiem jest już wcześniej wspomniany atak brutalny, który można zastosować do każdego szyfru. Ale istnieją także ataki klasyczne, które wykorzystują strukturę szyfru.
Zastanawialiśmy się, czy można przeprowadzić atak kwantowy, który będzie specjalistycznym atakiem na daną strukturę, a nie na dowolny szyfr blokowy. W międzyczasie dr inż. Michał Wroński zajmował się zastosowaniem wyżarzania kwantowego do ataków na algorytmy kryptografii asymetrycznej. Wyżarzanie kwantowe to proces poszukiwania minimalnego rozwiązania w przestrzeni rozwiązań, wykorzystujący zjawiska fizyki kwantowej. Zaciekawiło nas, czy można to wykorzystać do ataków algebraicznych. Takie ataki funkcjonują w kryptoanalizie z wykorzystaniem komputerów klasycznych. Atak algebraiczny polega na przedstawieniu całego szyfru za pomocą układu równań, który następnie należy po prostu rozwiązać. Przy czym „po prostu rozwiązać” to obecnie spore wyzwanie, ponieważ otrzymywane układy są duże i nie ma narzędzi, które rozwiązywałyby je efektywnie.
Państwo znaleźli sposób?
My zaproponowaliśmy wykorzystanie wyżarzania kwantowego. Jest to domena tzw. komputera kwantowego specjalnego przeznaczenia.
Obecnie rozwijane są dwa główne rodzaje komputerów kwantowych. Najbardziej popularny jest komputer kwantowy w tzw. modelu bramkowym, jednak aktualne jego wersje mają ograniczone możliwości ze względu na małą liczbę fizycznych kubitów – obecnie największy posiada 433 kubity. Drugim rodzajem jest komputer kwantowy specjalnego przeznaczenia, jak komputer firmy D‑Wave, posiadający 5000 kubitów. „Specjalne przeznaczenie” oznacza, że umożliwia rozwiązanie problemu tylko pewnej klasy, a dokładnie kwadratowych problemów optymalizacyjnych, w których rozwiązanie globalne daje minimalną wartość funkcji celu.
Opracowaliśmy metodę, jak krok po kroku przejść od problemu rozwiązania układu równań, którego rozwiązaniem jest szukany klucz, do problemu optymalizacyjnego, którego globalne rozwiązanie minimalne zwraca prawidłowy klucz, w taki sposób, aby otrzymany problem optymalizacyjny był jak najmniejszego rozmiaru.
Wybiera Pani konkretny szyfr i próbuje go atakować?
Tak, analizuję strukturę konkretnego szyfru, aby go opisać za pomocą takiego układu równań, który po przekształceniu do problemu optymalizacyjnego – zaproponowaną przez nas metodą – da możliwie najmniejszy problem. Im mniejszy jest problem końcowy, tym łatwiej można go rozwiązać z wykorzystaniem komputera D‑Wave. Niestety, uzyskane problemy są wciąż zbyt duże, żeby komputer kwantowy D‑Wave mógł je rzeczywiście rozwiązać. Mimo to – w celu sprawdzenia poprawności działania naszej metody – dla każdego analizowanego szyfru utworzyliśmy jego mniejszą instancję, uzyskując mniejsze problemy optymalizacyjne, które zostały rozwiązane i odzyskano prawidłowe klucze. W tym celu wykorzystaliśmy zdalny dostęp do zasobów komputera kwantowego D‑Wave. Ponadto, chociaż złożoność rozwiązywania problemów optymalizacyjnych przez ten komputer nie została do tej pory określona, to opublikowano pewne heurystyczne oszacowania, według których zaproponowany przez nas atak dla szyfru Speck mógłby być lepszy niż atak pełnego przeszukiwania.
W filmach łamanie szyfrów rzadko kojarzy się z rozwiązywaniem wzorów z matematyki – pokazuje się głównie komputerowych geniuszy, którzy radzą sobie z problemami błyskawicznie.
Takie obrazy są medialne. Niejeden młody człowiek chciałby usiąść w piwnicy w bluzie z kapturem, być wybitnie zdolnym hakerem i atakować szyfry. Takie są marzenia. Najpierw jednak trzeba przysiąść jak Rejewski i przeanalizować żmudnie strukturę szyfru. Zawsze zaczyna się od podstaw. I te podstawy trzeba znać.
Dominika Naruszko
