Czym jest szyfrowanie kratowe i jak zabezpiecza w czasach quantum computing?

Od wielu lat skala ataków, których celem jest przechwycenie danych rośnie lawinowo. Pozyskanie informacji w nieuprawniony sposób staje się coraz bardziej wyszukane i powszechne. W 2018 roku przejęte zostało ponad 4 mld rekordów! Skala tego procederu jest na tyle duża, że straty liczone są w miliardach dolarów. Kolejnym fenomenem, który napędza rozwój nowoczesnych metod kryptograficznych jest obserwowany od kilku lat na światowym rynku IT rozwój komputerów kwantowych. Sytuacja ta zmusza firmy do przemyślenia klasycznych metod zabezpieczania danych i wprowadzenia bardziej odpornych algorytmów.

Wykorzystanie algorytmów kwantowych teoretycznie może umożliwiać złamanie kluczy szyfrujących. Wykorzystywane w tym elemencie są dwa algorytmy Shora i Grovera. O ile drugi algorytm dotyczy przeszukiwania bazy danych w celu znalezienia w niej elementu oznaczonego, o tyle pierwszy umożliwia rozkład liczby naturalnej. Może stanowić on bezpośrednie zagrożenie dla systemu RSA, w którym klucz publiczny jest w skrócie iloczynem dwóch liczb pierwszych. Tak więc nawet teoretyczna możliwość znalezienia tych liczb pozwalałaby poznać klucz prywatny i tym samym złamać cały szyfr.

Wchodzimy w erę post-kwantową

Należy jednak pamiętać, że dostępne obecnie komputery kwantowe nie są na tyle zaawansowane i stabilne, aby stały sie już dziś realnym zagrożeniem. Wielu fachowców jednak potwierdza, że szybkość ich rozwoju może sugerować, że do roku 2029 sytuacja może się diametralnie zmienić. Dlatego też coraz więcej firm zaczyna współpracować, aby zbudować ekosystem kryptograficzny odporny na ataki z wykorzystaniem algorytmów kwantowych. W 2015 r. NSA opublikował dokument mówiący, że następna generacja algorytmów zabezpieczających komunikację internetową powinna być odporna na ataki kwantowe, czyli weszliśmy właśnie w erę kryptografii post-kwantowej.

W 2017 roku NIST rozpoczął proces standaryzacji w zakresie wyboru typu enkrypcji oraz wymiany kluczy i schematów podpisu cyfrowego. W ramach programów CRYSTALS i FALCON stworzone zostało konsorcjum partnerów uniwersyteckich i branżowych, których celem jest stworzenie nowoczesnego paradygmatu szyfrowania spełniającego wymogi standaryzacyjne NSA, przy założeniu pełnej odporności na ataki z użyciem komputerów kwantowych. Pomijając standaryzację protokołu służącego do zabezpieczenia komunikacji internetowej, ważną częścią projektu jest stworzenie nowych bardziej “zaawansowanych” sposobów ochrony prywatności. Jak na razie na etapie badawczym okazało się, że obecnie istnieje bardzo niewiele protokołów wykraczających poza podstawowe schematy szyfrowania i podpisywania, które można uznać za naprawdę praktyczne i na tyle szybkie, aby można je było zastosować w praktyce.

Szyfrowanie bazujące na kratach

Jedna z metod zabezpieczenia danych w erze post-kwantowej jest wykorzystanie w szyfrowaniu algebry bazującej na kratach. Co ciekawe teoria szyfrowanie klucza publicznego oparte na tym prototypie ma prawie tak długą historię jako dyskretne logarytmy i systemy oparte na faktoringu. Aby zrozumieć w jaki sposób zaimplementowane są algorytmy szyfrujące oparte na kratach wróćmy na moment do definicji samej kryptografia. Ogólnie rzecz biorąc szyfrowanie, opiera się na założeniu, że do rozwiązania tego problemu potrzebny jest złożony problem matematyczny, który jest wykorzystywany jako podstawa dla prymitywu kryptograficznego. Najczęściej wykorzystywane problemy matematyczne obejmują faktoryzację całkowitą (rozkład dużej liczby na mnożniki), logarytmy dyskretny i problemy logarytmu dyskretnego o krzywej eliptycznej. Zastosowanie teorii krat w szyfrowaniu wykorzystuje unikalną cechę algebry opartej na kratach, która sprawia, że są one w miarę odporne na złamanie za pomocą komputera kwantowego.

Metoda wykorzystania algebry opartej na kratach w kryptografii, nie jest wcale tak oczywista jak by się wydawało na pierwszy rzut oka. Po raz pierwszy została ona opisana w przełomowej publikacji wydanej w roku 1996 przez Miklos Ajtai, który jest od wielu lat zatrudniony w IBM Almaden Research Center USA. W wyniku tego nastąpiło wyraźne przyspieszenie procesu adopcji tego typu szyfrowania do praktycznego zastosowania w kryptografii.

Czym jest krata?

Krata jest zbiorem punktów w n-przestrzenią wymiarową z periodyczną strukturą, w której możemy zapisać wektory bazowe. Przypuśćmy, że podano kwadratową, pełnoprawdziwą macierz A i wartość b=Ax mod p, gdzie x jest wektorem o współczynnikach 0/1, a p jest małą (np. 10-bitową) liczbą pierwszą. Wówczas zadaniem jest znalezienie x. Problem ten ma unikalne rozwiązanie, x, które w rzeczywistości jest dość łatwe do znalezienia przy użyciu eliminacji Gaussowskiej. Z drugiej strony, jeśli wykorzystamy się nieco zmienioną wersję Ax, czyli Ax+e mod p, gdzie e jest jakimś losowym wektorem o współczynnikach 0/1, to dla macierzy o dużym i wystarczającym wymiarze (np. około 512) problem ten staje się zaskakująco trudny. Ten typ problemu związany jest zarówno z sumą podzbiorów, jak i parytetem poznawczym z szumami, które były szeroko badane od lat 80. XX wieku i nie uległy żadnym atakom algorytmicznym, ani klasycznym, ani kwantowym. Co mówiąc w skrócie czyni go problemem typu NP-trudnym.

Duża część badań przeprowadzonych w ostatniej dekadzie koncentrowała się na zwiększeniu zrozumienia różnych wersji opisanego powyżej problemu oraz budowaniu schematów w oparciu o ich przypuszczalną odporność. Pod względem wydajności, najbardziej wydajne szyfrowanie i schematy podpisu – oparte na sieci – są znacznie szybsze niż schematy oparte na RSA i mają klucze, i długości wyjściowe o podobnej wielkości.

Czy kryptografia post-kwantowa jest już dziś gotowa do wykorzystania?

Podstawowe elementy sieciowe kryptografii post-kwantowej są już gotowe, a ich wydajność została już potwierdzona. Dodatkowo zostały już z powodzeniem zaimplementowane z protokołem TLS i wymianą kluczy internetowych (IKE). Jednakże, ponieważ komputery kwantowe nie są jeszcze ogólnodostępne – pomimo ich coraz większej popularności – niewielu specjalistów ds. bezpieczeństwa prawdopodobnie planuje wdrożyć tego typu prymitywy.Wiele firm rozpoczyna jednak proces audytu post-kwantowego i jednoczesnej certyfikacji nowych technologii szyfrowania, a w przyszłości powolnej migracji w kierunku kryptografii opartej na bardziej zaawansowanych algorytmach szyfrujących. Wydaje się, że taka metoda powolnego zastępowania klasycznych metod szyfrujących jest dobra strategią.

Firmy poszukujące nowoczesnych rozwiązań zabezpieczenia danych powinny rozważyć zastosowanie metod kryptografii post-kwantowej w połączeniu z tradycyjnymi metodami. Metoda ta pozwoli na zabezpieczenie danych w sposób hybrydowy, czyli oba paradygmaty wykorzystane w tym procesie dzięki czemu przejście będzie o wiele łatwiejsze. Pozwala to na wyeliminowanie ryzyka związanego z wprowadzeniem nowej technologii. Jeśli metoda ta zostanie prawidłowo wdrożona, to przejście na całkowicie post-kwantową enkrypcję będzie ułatwione. Aby to wdrożyć, wystarczy po prostu kilka dodatkowych kilobajtów danych na sesję komunikacyjną.

Zastosowanie kryptografii post-kwantowej w praktyce

IBM ma szerokie doświadczenie techniczne w dziedzinie zabezpieczenia i szyfrowania danych, obejmującą zarówno kryptografię kwantową i post-kwantową. W niedalekiej przyszłości IBM planuje wdrożyć bezpieczne protokoły post-kwantowe do głównego systemu IBM Z wraz z zabezpieczeniem pamięci masowych protokołem Blockchain. Od wielu lat wykorzystujemy systemy taśmowe do przechowywania „zimnych” danych, jednakże od niedawna planowane jest wdrożenie nowoczesnego systemu zabezpieczenia danych odpornych na ataki kryptograficzne z użyciem algorytmów kwantowych. Na koniec 2019 planowane jest wdrożenie produkcyjne takich właśnie systemów.

Oczywiście w ramach usług IBM możliwe jest też wykonanie audytu bezpieczeństwa post-kwantowego przez naszych specjalistów. Wyraźnie pokazuje to, iż zagrożenia, które jeszcze niedawno wydawały się być domeną fantastyki naukowej przybierają realna formę i zmuszają nas do zaplanowania przyszłości przesyłania i przechowywania danych odporne na erę post-kwantową

IBM rozważa też wprowadzenie innej technologii zabezpieczenia komunikacji w ramach własnej chmury IBM Cloud wykorzystującej metodologie FHE, czyli szyfrowania w pełni homomorficznego, która pozwala na wykonywanie operacji w systemie bez potrzeby deszyfrowania informacji, ale o tym w następnym artykule.

dr Piotr Biskupski jest IBM Q Ambassador, IBM Security – IBM i2 – Pan-IMT Client Technical Professional.