Rola komputera kwantowego w szyfrowaniu informacji
Spis treści
- mnożenie i faktoryzacja – mnożenie liczb naturalnych jest łatwe algorytmicznie, ale znalezienie dwóch dużych liczb pierwszych na podstawie ich iloczynu jest trudne obliczeniowo,
- funkcja Rabina – mając N oraz x<N, w równaniu y=x2 (mod N) znalezienie x na podstawie y jest algorytmicznie tak samo trudne jak faktoryzacja N,
- potęgowanie i logarytm dyskretny – mając liczbę pierwszą p, g < p oraz x<p, nie ma efektywnego algorytmu na znalezienie x na podstawie y, g oraz p w równaniu y=gx(mod p)
Na przestrzeni wielu lat badań nie znaleziono efektywnych algorytmów odwracających, które byłyby możliwe do zaimplementowania na obecnych urządzeniach liczących. Należy jednak wziąć pod uwagę możliwość, że może się to zmienić w przyszłości, dlatego systemy wykorzystujące ww. funkcje nie gwarantują pełnego bezpieczeństwa.
Omówmy teraz dokładniej pierwszą z wymienionych propozycji do bycia funkcją jednokierunkową – mnożenie i faktoryzację, która jest wykorzystywana w najpopularniejszym algorytmie kryptograficznym – RSA. Obecnie istniejące algorytmy faktoryzacji nie są zbyt skuteczne. Dla przykładu: klucz RSA o długości 300 bitów może zostać sfaktoryzowany przy użyciu zwykłego komputera w ciągu kilku godzin. Aktualnie największa liczba RSA, która została rozłożona ma 829 bitów (250 cyfr dziesiętnych) i została ogłoszona w lutym 2020 r., a obliczenia zajęły kilka miesięcy i wykorzystały dziesiątki tysięcy maszyn na całym świecie.
To na pierwszy rzut oka może robić wrażenie, ale w praktyce klucze RSA osiągają zwykle długość od 1024 do 4096 bitów, a minimalna rekomendowana przez RSA Security długość wynosi 2048 bitów. Uwzględniając wykładniczy wzrost złożoności obliczeniowej, przy aktualnych możliwościach technicznych złamanie klucza 4096-bitowego jest kompletnie poza zasięgiem obecnych komputerów i prawdopodobnie pozostanie tak jeszcze przez długi czas.
Sprawa bezpieczeństwa komplikuje się, jeśli w rozważaniach uwzględni się komputer kwantowy. Wszystkie trzy wymienione funkcje mogą być funkcjami jednokierunkowymi, ale wiadomo już, że można je łatwo odwracać z użyciem komputera kwantowego. W 1994 roku amerykański matematyk Peter Shor opublikował algorytm, który umożliwia rozkład na czynniki pierwsze liczby naturalnej w czasie wielomianowym (złożoność czasowa rośnie stosunkowo wolno wraz z wielkością danych wejściowych). Pozwoliłoby to na efektywną faktoryzację liczb – poznawanie kluczy prywatnych i tym samym łamanie całych szyfrów. Jest to zagrożenie dla całego kryptosystemu RSA!
Gdzie jest haczyk? Algorytm ten może zostać uruchomiony wyłącznie na komputerze kwantowym, który dysponuje odpowiednio dużą liczbą kubitów. Na ten moment nie istnieje na świecie urządzenie kwantowe, które dałoby radę sfaktoryzować liczbę posiadającą więcej niż kilka cyfr, ale rozwój technologii jest dynamiczny i niewykluczone, że w przeciągu najbliższych dziesiątek lat ulegnie to zmianie. Z tego powodu najbezpieczniej jest założyć, że ostatecznie powstaną komputery kwantowe zdolne łamać obecnie używane szyfry i przygotować się na to wcześniej. Jak? Istnieją dwa działy nauki, które starają się odpowiedzieć na to pytanie. Są nimi:
- kryptografia kwantowa – nauka zajmująca się wykorzystywaniem zjawisk mechaniki kwantowej do wykonywania zadań kryptograficznych,
- kryptografia postkwantowa – nauka zajmująca się algorytmami kryptograficznymi odpornymi na złamanie za pomocą komputera kwantowego. Nie wymaga wykorzystania zjawisk kwantowych, aby osiągnąć tajność danych.
Obie te dziedziny starają się znaleźć sposób na bezpiecznie szyfrowanie informacji w świecie, w którym istnieją komputery kwantowe. Współcześnie trwają intensywne prace w tworzeniu nowych algorytmów, które będzie można wykorzystać w przyszłości.
Wykorzystanie mechaniki kwantowej do szyfrowania informacji oraz optymalnej komunikacji wymaga korzystania ze specjalnych sieci telekomunikacyjnych, które umożliwią swobodną wymianę informacji w postaci kubitów. Te systemy połączeń noszą nazwę sieci kwantowych i składają się (w uproszczeniu) z węzłów końcowych oraz linii komunikacyjnych.
Węzłami końcowymi są procesory kwantowe, a ich celem jest odbieranie oraz wysyłanie informacji. Tymi procesorami mogą być bardzo proste urządzenia składające się z fotodetektorów oraz płytki światłodzielącej dla prostych zastosowań, jednak do korzystania z bardziej skomplikowanych algorytmów mogą być wymagane bardziej zaawansowane jednostki.
Linią komunikacyjną jest sposób, w jaki kubity są transportowane między węzłami. Główną metodą transmisji na długie dystanse jest wykorzystanie fotonów z powodu ich zmniejszonego ryzyka dekoherencji. Fotony te są transportowane za pomocą światłowodów lub przez bezpośrednie wysłanie za pośrednictwem powietrza (lub próżni). W drugim przypadku komunikujące strony muszą leżeć w linii wzroku, jednak rozwiązaniem tego problemu jest komunikacja z użyciem satelity (zademonstrowano satelitę zdolną do transmisji splątanej pary fotonów na odległość 1203 km). Posiada to kilka zalet praktycznych nad światłowodem, lecz kosztem zwiększonego ryzyka utraty informacji na skutek oddziaływania z otoczeniem.
Tematowi bezpieczeństwa w przyszłości poświęca się coraz więcej uwagi, oto kilka przykładów:
- Unia Europejska w 2018 r. zainwestowała miliard euro, aby stworzyć Quantum Technologies Flagship – projekt mający wspierać i gromadzić pracę naukowców, uczelni, instytucji i przemysłu w ich pracy nad rozwojem i zastosowaniami fizyki kwantowej przez okres 10 lat.
- Kilkanaście państw Unii Europejskiej od sierpnia 2019 r. podpisało deklarację, której celem jest wspólne wybudowanie bezpiecznej sieci kwantowej na terenie Unii Europejskiej. W czasie pierwszych 12 miesięcy od powstania deklaracji państwa miały wspólnie ustalić najlepszy sposób na wybudowanie infrastruktury, a ona sama miałaby powstać w czasie kolejnych 10 lat. Na ten moment realizacja projektu jest jednak opóźniona.
- Na początku 2021 r. Chiny ukończyły budowanie sieci kwantowej składającej się z 700 światłowodów oraz dwóch linii transmisyjnych wykorzystujących dwie satelity. Za pomocą tej sieci zrealizowano wymianę QKD pomiędzy ponad 150 węzłami na łączny dystans 4600 km.
Kwantowa dystrybucja klucza
Jeśli do szyfrowanej komunikacji w kryptografii klasycznej będzie używany za każdym razem nowy, losowy klucz znany przez obie strony, to istnieje sposób szyfrowania, który będzie praktycznie nie do złamania/zgadnięcia przez osoby trzecie. Powstaje tutaj problem dystrybucji tego klucza pomiędzy użytkownikami, tak aby osoba trzecia nie mogła go wykraść lub złamać.
Z rozwiązaniem problemu przychodzi dystrybucja klucza kwantowego. Polega ona na wymianie klucza pomiędzy uczestnikami – np. Alicją i Bobem – za pomocą kwantowego kanału. Klucz ten będzie służył do klasycznego zaszyfrowania klasycznej wiadomości. Z faktu, że pomiar wpływa na stan kwantowy wynika, że osoba trzecia (np. Ewa) która chciałaby “podejrzeć” jaki klucz wymieniają między sobą Alicja i Bob przy próbie przechwycenia zmieni stan kwantowy. Wpłynie to na pomiary jakie wykonają Alicja i Bob, więc jeśli zauważą oni jakieś anomalie to będą wiedzieli, że ktoś próbuje ich podsłuchać i nie użyją tego klucza.
Aktualnie istnieją dwa główne podejścia do kwantowej dystrybucji klucza. Jednym z nich jest podejście typu “przygotuj i zmierz”, które korzysta z zasady nieoznaczoności i tego, że pomiar kwantowy można wykonywać w wielu bazach. Np. polaryzację fotonu możemy mierzyć w bazie pionowo-poziomej, lub bazie ukośnej (pomiary w różnych bazach oraz wpływ pomiaru na stan kwantowy dobrze przedstawia filmik o twierdzeniu Bella: “Bell’s Theorem: The Quantum Venn Diagram Paradox”
Najbardziej znanym protokołem tego typu jest BB84 (Bennett, Brassard, 1984r.). W skrócie Alicja chcąca wysłać klucz do Boba wysyła losowy bit (0 lub 1) w losowej bazie (pionowo-poziomej lub ukośnej). Bob mierzy stan kwantowy w losowej bazie (pionowo-poziomej lub ukośnej) i później mówią sobie w jakich bazach mierzyli. Z pomiarach w takiej samej bazie (których będzie ok. 50%) tworzą klucz (dokładne działanie tego algorytmu jest opisane tutaj: https://en.wikipedia.org/wiki/BB84).
Drugi typ protokołu wykorzystuje splątanie kwantowe. Splątanych kubitów nie da się opisać za pomocą samodzielnych stanów i wyniki ich pomiarów zawsze będą ze sobą skorelowane. W najpopularniejszym protokole z tej klasy – E91 (Ekert 1991) Alicja i Bob używają splątanej pary kubitów i prowadzą pomiary w różnych bazach, aby wymienić klucz.
Bibliografia
- https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm
- Yin, Juan; Cao, Yuan; Li, Yu-Huai; Liao, Sheng-Kai; Zhang, Liang; Ren, Ji-Gang; Cai, Wen-Qi; Liu, Wei-Yue; Li, Bo (2017-07-05). „Satellite-Based Entanglement Distribution Over 1200 kilometers”. Science. 356 (2017): 1140–1144 arXiv:1707.01339. Bibcode:2017arXiv170701339Y. doi:10.1126/science.aan3211. PMID 28619937. S2CID 5206894.
- https://qt.eu/
- https://ec.europa.eu/digital-single-market/en/news/future-quantum-eu-countries-plan-ultra-secure-communication-network
- https://www.nature.com/articles/s41586-020-03093-8
Autorzy
- Marek Kowalik
- Urszula Lajzner
- Michał Łukomski
- Janusz Twardak