Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.
Kryptografia postkwantowa
Komputery kwantowe są na razie bardzo trudne do zbudowania, jednak jest to tylko kwestią czasu, aż te zaawansowane maszyny z potencjalną mocą do łamania RSA, protokołu Diffiego-Hellmana i kryptografii krzywych eliptycznych (ECC) zostaną stworzone. Temu katastrofalnemu scenariuszowi, w którym zagrożone jest bezpieczeństwo powszechnie używanych systemów kryptografii klucza publicznego, ma zaradzić kryptografia postkwantowa. Zajmuje się ona algorytmami kryptograficznymi, które mają być odporne na złamanie za pomocą komputera kwantowego.
Postkwantowa kryptografia używa matematycznych konceptów w celu stworzenia systemów, które mogą być trudne do złamania nawet dla komputerów kwantowych. Na wstępie należy zaznaczyć, że kryptografia postkwantowa to nie to samo, co kryptografia kwantowa. Kryptografia postkwantowa nie wymaga wykorzystania zjawisk kwantowych w celu osiągnięcia tajności danych, w przeciwieństwie do kryptografii kwantowej.
Narodowy Instytut Standaryzacji i Technologii (NIST) w Stanach Zjednoczonych w ramach projektu „Post-Quantum Cryptography Standardization” przeprowadza konkurs na stworzenie systemów kryptograficznych nowej generacji. Konkurs ma trwać do 2022 roku, a obecnie trwa jego trzecia runda, w której rozważana jest pula 15 propozycji. Rozpatrywanych jest wiele ciekawych algorytmów kryptografii postkwantowej, a do najbardziej obiecujących należą:
- Algorytmy kratowe (lattice-based)
Krata to struktura matematyczna. Jest to zbiór punktów w n-wymiarowej przestrzeni o periodycznej strukturze. W strukturze tej możemy zapisać wektory bazowe. Jednymi z trudniejszych problemów, które możemy napotkać w algorytmach kratowych, są short integer solution (SIS) bądź learning with errors (LWE). Mogą one zostać przekształcone do problemu najbliższego wektora na kracie lub problemu znalezienia wektora na kracie najbliższego do danego punktu poprzez przekształcenie wektorów bazowych. Problemy te uznawane są za wyjątkowo trudne zarówno dla komputerów klasycznych, jak i kwantowych. Niestety nie przenosi się to jednak bezpośrednio na bezpieczeństwo systemów kryptograficznych; niektóre problemy są trudne jedynie w ich najtrudniejszych przypadkach, aniżeli w przeciętnych, co jest pożądane w algorytmach kryptograficznych. Co gorsza, podczas gdy znalezienie dokładnego rozwiązania dla problemu najbliższego wektora jest trudne, znalezienie jego aproksymacji jest już stosunkowo łatwe.
- Kryptografia wielu zmiennych (Multivariate quadratic equation)
Bazuje na trudności w znalezieniu rozwiązania kwadratowych równań wielu zmiennych w skończonej przestrzeni. Właściwie trudność w rozwiązaniu tego typu problemu zależy od parametrów schematu, liczby równań, rozmiaru, typu liczb, itp. Niestety znalezienie parametrów, które gwarantowałyby bezpieczeństwo, jest bardzo trudne. W większości przypadków rezygnuje się jednak z jej użycia ze względu na wątpliwości co do bezpieczeństwa samego algorytmu, ale także zasobów czasowych oraz pamięciowych, jakich wymaga. - Algorytmy oparte o funkcje skrótu (Hash-based)
Algorytm ten bazuje na dobrze sprawdzonym bezpieczeństwie funkcji mieszającej. Pomysł opiera się na założeniu, że kwantowe komputery nie mogą złamać niczego, co polegałoby na problemie znalezienia kolizji. Wykorzystywany jest do tworzenia podpisu cyfrowego. - Algorytmy oparte na kodach korekcyjnych (Code based)
Oparte są na podstawie kodu korekcji błędów (ECC), technice stworzonej do transmitowania bitów zakłóconym kanałem. Niektóre z algorytmów, które opierają się na kodach korekcyjnych, zostały stworzone, by oferować krótki podpis, którego koszt jest taki sam jak rozmiar dużego klucza. Algorytmy te należą do najczęściej studiowanych algorytmów kryptografii postkwantowej i mogą zostać użyte zarówno do enkrypcji, jak i do podpisu cyfrowego.
W nadchodzących latach rozwój kryptografii postkwantowej będzie kluczowy dla naszego bezpieczeństwa, biorąc pod uwagę tempo rozwoju komputerów kwantowych oraz moc algorytmów Shore’a czy Grovera. Należy brać pod uwagę fakt, że wprowadzenie nowych systemów kryptograficznych kosztuje dużo wysiłku oraz czasu, dlatego prace nad bezpieczeństwem systemów są konieczne już dzisiaj.
Bibliografia
- Post-Quantum Cryptography: Current state and quantum mitigation – ENISA
- https://www.researchgate.net/publication/226115302_Code-Based_Cryptography
- KRYTERIA BUDOWY KOMPUTERA KWANTOWEGO I ALGORYTMY KRYPTOGRAFII POSTKWANTOWEJ Jacek GRUBER, Dawid IWANICKI, Monika JACAK, Ireneusz J. JÓŹWIAK, Piotr P. JÓŹWIAK, Jacek KOWALCZYK
- PQCRYPTO – Post-Quantum Cryptography for Long-Term Security. Initial recommendations of long-term secure post-quantum systems
- https://core.ac.uk/download/pdf/144828958.pdf Post-Quantum Cryptography: State of the ArtJohannes A. Buchmann, Denis Butin, Florian Göpfert, Albrecht Petzoldt
- Serious Cryptographyby Jean-Philippe Aumasson
Autorzy
- Marek Kowalik
- Urszula Lajzner
- Michał Łukomski
- Janusz Twardak