r   e   k   l   a   m   a
r   e   k   l   a   m   a

Niespodziewana konsekwencja faktoryzacji liczby 143: kwantowy algorytm zagraża popularnym szyfrom

Strona główna AktualnościOPROGRAMOWANIE

Żyjemy w przekonaniu, że sporo czasu minie, zanim komputery kwantowe poślą stosowane przez nas systemy kryptograficzne do lamusa. Gwarantowane przez asymetryczne szyfry bezpieczeństwo komunikacji w Sieci może jednak prysnąć wcześniej niż sądzono. Niespodziewanie dla specjalistów w tej dziedzinie okazało się, że uruchomienie kwantowego algorytmu na dziś dostępnych, wciąż prymitywnych maszynach kwantowych pozwala na faktoryzację znacznie większych liczb, niż te, które dotąd rozkładano.

Konsekwencji swoich prac nie dostrzegli chińscy badacze. W 2011 roku 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ądrowy rezonans magnetyczny komputerze kwantowym, posiadającym zaledwie 4 kubity. Rozłożenie liczby 143 na czynniki pierwsze za pomocą adiabatycznego algorytmu AQC (głównego konkurenta dla dobrze znanego algorytmu Shora) było szeroko komentowane w prasie naukowej – wcześniej największą liczbą, którą udało się sfaktoryzować za pomocą komputera kwantowego był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 rezultat Chińczyków jest znacznie bardziej doniosły, niż dotąd sądzono. W pracy pt. Quantum factorization of 56153 with only 4 qubits dowodzą, że faktoryzacja 143 w rzeczywistości oznaczała faktoryzację znacznie większych liczb – 3599, 11663 oraz 56153. Co szczególnie istotne, w przeciwieństwie do dotychczasowych faktoryzacji przeprowadzanych za pomocą niepełnych implementacji algorytmu Shora, tutaj nie była konieczna wcześniejsza znajomość odpowiedzi.

r   e   k   l   a   m   a

Skąd to śmiałe twierdzenie? Jako że 4-kubitową maszynę kwantową relatywnie łatwo symulować na klasycznym 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 na równania faktoryzacyjne mają taką samą formę, różniąc się jedynie zmiennymi. Z perspektywy kwantowego procesora oznacza to, że hamiltoniany takich liczb (czyli funkcje współrzędnych i pędów opisujące stan układu) są takie same, jedynie kubity przedstawiają odmienne pozycje w odpowiadających im binarnych ciągach. Wspomniane 143 dzieli tę właściwość ze wspomnianymi liczbami 3599, 11663 oraz 56153.

To znaczące osiągnięcie z dwóch powodów. Po raz pierwszy dokonano faktoryzacji liczby bez wcześniejszej znajomości wyniku (jak to było w 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 liczby 15 (dla zainteresowanych, tak, to iloczyn liczb 5 i 3) potrzeba ośmiu kubitów. W swojej pracy autorzy zademonstrowali tymczasem rozkład liczby 175 na trzy liczby pierwsze z wykorzystaniem zaledwie trzech kubitó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ści mniejsze, niż te, które znajdują zastosowanie w asymetrycznej kryptografii, na czele z popularnym szyfrem RSA. Najmocniejsze modele produkowanych przez kanadyjską firmę D-Wave komputerów quasikwantowych, na których można uruchamiać algorytmy AQC, oferują dziś jednak 512 kubitów. Co prawda nie wiadomo, jak parametry tych kontrowersyjnych maszyn (jeden egzemplarz zakupiło w zeszłym roku Google dla swojego laboratorium kwantowego) mają się do normalnych komputerów kwantowych – ale jeśli okaże się, że można na nich przeprowadzać faktoryzację na sposób przedstawiony w omawianej tu pracy, kryptografów będzie czekało sporo pracy. Pojawienie się efektywnych procesorów kwantowych nie oznacza bowiem końca wszelkiej prywatności i bezpieczeństwa w informatyce, badania nad kryptografią w postkwantowej erze trwają od lat. Zainteresowanym ciekawym wprowadzeniem do tej tematyki polecamy artykuł Daniela J. Bernsteina (tego Bernsteina od demona poczty qmail i serwera DNS djbdns) – Introduction to post-quantum cryptography.

© dobreprogramy
r   e   k   l   a   m   a
r   e   k   l   a   m   a

Komentarze

r   e   k   l   a   m   a
r   e   k   l   a   m   a
Czy wiesz, że używamy cookies (ciasteczek)? Dowiedz się więcej o celu ich używania i zmianach ustawień.
Korzystając ze strony i asystenta pobierania wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.