Wprowadzenie
W 1994 roku informatyk Peter Shor odkryty że gdyby kiedykolwiek wynaleziono komputery kwantowe, zdziesiątkowałyby większość infrastruktury wykorzystywanej do ochrony informacji udostępnianych online. Ta przerażająca możliwość skłoniła naukowców do wymyślania nowych, „post-kwantowych” schematów szyfrowania, aby zachować jak najwięcej informacji przed wpadnięciem w ręce hakerów kwantowych.
Na początku tego roku Narodowy Instytut Standardów i Technologii ujawnił czterech finalistów w poszukiwaniu standardu kryptografii post-kwantowej. Trzy z nich wykorzystują „kryptografię kratową” — schemat inspirowany kratami, regularnymi układami kropek w przestrzeni.
Kryptografia sieciowa i inne post-kwantowe możliwości różnią się w zasadniczy sposób od obecnych standardów. Ale wszystkie opierają się na asymetrii matematycznej. Bezpieczeństwo wielu obecnych systemów kryptograficznych opiera się na mnożeniu i rozkładaniu na czynniki: każdy komputer może szybko pomnożyć dwie liczby, ale rozłożenie kryptograficznej dużej liczby na jej główne składniki może zająć wieki. Ta asymetria sprawia, że sekrety są łatwe do zakodowania, ale trudne do rozszyfrowania.
Shor ujawnił w swoim algorytmie z 1994 r., że dziwactwo faktoryzacji sprawia, że jest on podatny na ataki komputerów kwantowych. „To bardzo konkretna, wyjątkowa rzecz, którą może zrobić komputer kwantowy”, powiedział Katarzyna Stange, matematyk na Uniwersytecie Kolorado w Boulder. Tak więc po Shorze kryptografowie mieli nowe zadanie: znaleźć nowy zestaw operacji matematycznych, które są łatwe do wykonania, ale prawie niemożliwe do cofnięcia.
Kryptografia kratowa jest jak dotąd jedną z najbardziej udanych prób. Pierwotnie opracowany w latach 1990., opiera się na trudnościach inżynierii wstecznej sum punktów.
Oto jeden sposób na opisanie kryptografii kratowej: wyobraź sobie, że twój przyjaciel ma kratę, która składa się z kilku punktów w regularnym, powtarzającym się wzorze na całej płaszczyźnie. Twój przyjaciel chce, abyś wymienił 10 z tych punktów. Ale jest trudny i nie narysuje całej siatki. Zamiast tego wymienia tylko dwa punkty — pierwszy z x-wartość 101 i a y-wartość 19, druga o współrzędnych [235, 44].
Na szczęście łatwo jest znaleźć nowe punkty na siatce, ponieważ dodając i odejmując dowolne dwa punkty na siatce, otrzymujesz trzeci punkt w tej samej sieci. Więc wszystko, co musisz zrobić, to zsumować punkty, które dał ci znajomy, lub pomnożyć je przez liczby całkowite, a następnie dodać je lub jakąś kombinację tych dwóch. Zrób to na osiem różnych sposobów, a będziesz w stanie odpowiedzieć na pytanie znajomego.
Ale twój przyjaciel nadal nie jest usatysfakcjonowany. Podaje ci te same dwa punkty początkowe, a następnie pyta, czy punkt [2, 1] leży na tej samej siatce. Aby poprawnie odpowiedzieć na to pytanie, musisz znaleźć kombinację [101, 19] i [235, 44], która daje [2, 1]. Ten problem jest znacznie trudniejszy niż pierwszy i prawdopodobnie skończy się na zgadywaniu i sprawdzaniu, aby uzyskać odpowiedź.* Ta asymetria leży u podstaw kryptografii sieciowej.
Jeśli rzeczywiście chcesz używać kryptografii kratowej do udostępniania informacji, wykonaj następujące czynności. Wyobraź sobie, że znajomy (milszy!) chce wysłać Ci bezpieczną wiadomość. Zaczynasz od kwadratowej siatki liczb. Powiedzmy, że ma dwa wiersze i dwie kolumny i wygląda tak:
Teraz wymyślasz prywatny „klucz”, który znasz tylko Ty. W tym przykładzie powiedzmy, że twój klucz prywatny to tylko dwie tajne liczby: 3 i -2. Mnożysz liczby w pierwszej kolumnie przez 3, a w drugiej kolumnie przez −2. Dodaj wyniki w każdym wierszu, aby otrzymać trzecią kolumnę z dwoma wpisami.
Przyklej nową kolumnę na końcu swojej siatki. Ta nowa trzykolumnowa siatka jest Twoim kluczem publicznym. Podziel się nim swobodnie!
(Scenariusz w świecie rzeczywistym będzie nieco bardziej skomplikowany. Aby uniemożliwić hakerom dekodowanie twojego klucza prywatnego, musisz dodać trochę losowego szumu do ostatniej kolumny. Ale tutaj zignorujemy ten krok dla uproszczenia. )
Teraz Twój znajomy użyje klucza publicznego, aby wysłać Ci wiadomość. Wymyśla dwie własne tajne liczby: 2 i 0. Mnoży liczby w pierwszym rzędzie przez 2, a te w drugim rzędzie przez 0. Następnie sumuje wyniki w każdej kolumnie, aby otrzymać trzeci wiersz.
Teraz dołącza nowy wiersz do dolnej części siatki i odsyła go z powrotem. (Ponownie, w prawdziwym systemie, musiałaby dodać trochę hałasu do swojego rzędu.)
Teraz przeczytasz wiadomość. Aby to zrobić, sprawdź, czy ostatni wiersz twojego przyjaciela jest poprawny. Zastosuj własny klucz prywatny do pierwszych dwóch wpisów w jej wierszu. Wynik powinien pasować do ostatniego wpisu.
Twój znajomy może również wysłać Ci wiersz z błędnym numerem w ostatniej kolumnie. Wie, że ta liczba nie pasuje do twoich obliczeń.
Jeśli twoja znajoma wyśle wiersz, w którym ostatnia liczba jest poprawna, zinterpretujesz to jako 0. Jeśli wyśle wiersz, w którym liczba jest nieprawidłowa, zinterpretujesz go jako 1. Dlatego wiersz koduje pojedynczą bit: 0 lub 1.
Pamiętaj, że osoba atakująca z zewnątrz nie będzie miała dostępu ani do Twojego klucza prywatnego, ani do Twojego znajomego. Bez nich atakujący nie będzie miał pojęcia, czy ostateczna liczba jest poprawna, czy nie.
W praktyce chciałbyś wysyłać wiadomości, które są dłuższe niż jeden bit. Tak więc ludzie, którzy chcą otrzymać, powiedzmy, 100-bitową wiadomość, wygenerują 100 nowych kolumn zamiast tylko jednej. Następnie nadawca wiadomości utworzy jeden nowy wiersz, modyfikując 100 ostatnich wpisów, aby zakodować 0 lub 1 dla każdego wpisu.
Jeśli kryptografia kratowa zostanie faktycznie zaimplementowana, będzie zawierała niezliczone niuanse, których nie obejmuje ten scenariusz. Na przykład, jeśli chcesz, aby wiadomość była naprawdę bezpieczna przed wzrokiem ciekawskich, matryca musi mieć niewyobrażalną liczbę wpisów, przez co całość jest tak nieporęczna, że nie warto jej używać. Aby obejść ten problem, naukowcy wykorzystują macierze z użytecznymi symetriami, które mogą zmniejszyć liczbę parametrów. Poza tym istnieje cały zestaw poprawek, które można zastosować do samego problemu, sposobu włączania błędów i nie tylko.
Oczywiście zawsze jest możliwe, że ktoś znajdzie fatalną wadę w kryptografii kratowej, tak jak zrobił to Shor w przypadku faktoringu. Nie ma pewności, że konkretny schemat kryptograficzny zadziała w obliczu jakiegokolwiek możliwego ataku. Kryptografia działa, dopóki nie zostanie złamana. Rzeczywiście, wcześniej tego lata jeden obiecujący schemat kryptografii post-kwantowej został złamany używając nie komputera kwantowego, ale zwykłego laptopa. Dla Stange'a cały projekt tworzy niewygodny paradoks: „To, co wydaje mi się tak niesamowite w kryptografii, to to, że zbudowaliśmy tę infrastrukturę dla rasy ludzkiej na mocnym przekonaniu, że nasze ludzkie zdolności są ograniczone” – powiedziała. „To takie zacofane”.
*: Odpowiedź, jeśli jesteś ciekawy, to 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [wróć do artykułu]
