Niespodziewana konsekwencja faktoryzacji liczby 143: kwantowy algorytm zagraża popularnym szyfrom
Żyjemy w przekonaniu, że sporo czasu minie, zanim komputerykwantowe poślą stosowane przez nas systemy kryptograficzne do lamusa.Gwarantowane przez asymetryczne szyfry bezpieczeństwo komunikacji wSieci może jednak prysnąć wcześniej niż sądzono. Niespodziewanie dlaspecjalistów w tej dziedzinie okazało się, że uruchomienie kwantowegoalgorytmu na dziś dostępnych, wciąż prymitywnych maszynach kwantowychpozwala na faktoryzację znacznie większych liczb, niż te, które dotądrozkładano.
Konsekwencji swoich prac nie dostrzegli chińscy badacze. W 2011roku opublikowali pracępt. Quantum Factorization of 143 on a Dipolar-Coupling NMR system,chwaląc się w niej faktoryzacją liczby 143 na wykorzystującym jądrowyrezonans magnetyczny komputerzekwantowym, posiadającym zaledwie 4 kubity. Rozłożenie liczby 143na czynniki pierwsze za pomocą adiabatycznego algorytmu AQC (głównegokonkurenta dla dobrze znanego algorytmu Shora) było szerokokomentowane w prasie naukowej – wcześniej największąliczbą, którą udało się sfaktoryzować za pomocą komputera kwantowegobyło 21.
Osiągnięciu temu przyjrzeli się bliżej zajmujący się chemiąkwantową uczeni z Japonii i Kanady, dochodząc do wniosku, że rezultatChińczyków jest znacznie bardziej doniosły, niż dotąd sądzono. Wpracy pt. *Quantumfactorization of 56153 with only 4 qubits *dowodzą,że faktoryzacja 143 w rzeczywistości oznaczała faktoryzację znaczniewiększych liczb – 3599, 11663 oraz 56153. Co szczególnieistotne, w przeciwieństwie do dotychczasowych faktoryzacjiprzeprowadzanych za pomocą niepełnych implementacji algorytmu Shora,tutaj nie była konieczna wcześniejsza znajomość odpowiedzi.
Skąd to śmiałe twierdzenie? Jakoże 4-kubitową maszynę kwantową relatywnie łatwo symulować naklasycznym komputerze, autorzy przeprowadzili taką symulację,odkrywając coś w rodzaju kolizji między 143 a innymi liczbami.Okazuje się, że istnieją całe klasy liczb, które po rozpisaniu narównania faktoryzacyjne mają taką samą formę, różniąc się jedyniezmiennymi. Z perspektywy kwantowego procesora oznacza to, żehamiltoniany takich liczb (czyli funkcje współrzędnych i pędówopisujące stan układu) są takie same, jedynie kubity przedstawiająodmienne pozycje w odpowiadających im binarnych ciągach. Wspomniane143 dzieli tę właściwość ze wspomnianymi liczbami 3599, 11663 oraz56153.
To znaczące osiągnięcie z dwóch powodów. Po raz pierwszy dokonanofaktoryzacji liczby bez wcześniejszej znajomości wyniku (jak to byłow wypadku dotyczasowych prób z algorytmem Shora), znacząco teżzmniejszono liczbę kubitów potrzebnych do tej operacji. Przykładowo,do rozłożenia na czynniki pierwsze za pomocą algorytmu Shora liczby15 (dla zainteresowanych, tak, to iloczyn liczb 5 i 3) potrzeba ośmiukubitów. W swojej pracy autorzy zademonstrowali tymczasem rozkładliczby 175 na trzy liczby pierwsze z wykorzystaniem zaledwie trzechkubitów, pokazali też, w jaki sposób można przeprowadzić faktoryzacjęliczby 291311 przy użyciu 6 kubitów.
Oczywiście omawiane tu liczby są o wiele rzędów wielkościmniejsze, niż te, które znajdują zastosowanie w asymetrycznejkryptografii, na czele z popularnym szyfrem RSA. Najmocniejsze modeleprodukowanych przez kanadyjską firmę D-Wave komputerówquasikwantowych, na których można uruchamiać algorytmyAQC, oferują dziś jednak 512 kubitów. Co prawda nie wiadomo, jakparametry tych kontrowersyjnych maszyn (jeden egzemplarz zakupiło wzeszłym roku Google dla swojego laboratorium kwantowego) mają się donormalnych komputerów kwantowych – ale jeśli okaże się, żemożna na nich przeprowadzać faktoryzację na sposób przedstawiony womawianej tu pracy, kryptografów będzie czekało sporo pracy.Pojawienie się efektywnych procesorów kwantowych nie oznacza bowiemkońca wszelkiej prywatności i bezpieczeństwa w informatyce, badanianad kryptografią w postkwantowej erze trwają od lat. Zainteresowanymciekawym wprowadzeniem do tej tematyki polecamy artykuł Daniela J.Bernsteina (tego Bernsteina od demona poczty qmail i serwera DNSdjbdns) – Introduction to post-quantum cryptography.