Algorytm kryptograficzny RSA, od czasu publikacji w 1977 roku był celem wielu ataków. O jego sile świadczy fakt, że do tej pory uważany jest za bezpieczny – przy założeniu odpowiedniej długości klucza. Może się to zmienić za sprawą komputerów kwantowych.
Siłę algorytmu RSA zapewnia matematyka. Jego podstawowa konstrukcja opiera się na tzw. problemie faktoryzacji iloczynów liczb pierwszych. O ile łatwo jest pomnożyć przez siebie dwie liczby pierwsze, takie jak np. 65537 i 65539, o tyle ustalenie, wynikiem jakiego mnożenia jest liczba 4295229443 zajmuje znacząco więcej czasu. Można próbować dzielić 4295229443 przez wszystkie kolejne liczby, jednak to bardzo pracochłonne zajęcie. Można także skorzystać z algorytmu sita kwadratowego (dla liczb krótszych niż 150 cyfr dziesiętnych) lub algorytmu GNFS (dla liczb większych niż 100 cyfr dziesiętnych), jednak dla liczb dłuższych niż ok. 232 liczby dziesiętne (768 bitów) te ataki stają się całkowicie nieprzydatne – czas ich trwania rośnie wykładniczo wraz z długością atakowanej liczby.
Z pomocą (lub zagrożeniem) przychodzi fizyka kwantowa, pozwalająca na tworzenie komputerów, zachowujących się zupełnie inaczej niż komputery klasyczne. Bez wnikania w szczegóły (które wymagają zapewne przynajmniej powtórki materiału z liceum), komputery kwantowe mają pomóc w znacznie szybszym rozwiązaniu problemu faktoryzacji dużych liczb pierwszych. W kilku laboratoriach na całym świecie trwają próby skonstruowania komputera kwantowego, który potrafiłby przeprowadzić faktoryzację iloczynu liczb pierwszych w oparciu o algorytm Shora.
Tak wygląda komputer kwantowy
Pierwszą udana faktoryzację liczby 15 (wynikiem której oczywiście było 3 i 5) przeprowadzono z użyciem komputera kwantowego już w roku 2001. Próba była jednak kwestionowana przez naukowców, ponieważ nie zaobserwowano stanu splątanego, charakterystycznego dla operacji kwantowych. Dopiero w lutym tego roku naukowcy z Uniwersytetu Kalifornijskiego przeprowadzili faktoryzację liczby 15 przy użyciu prawdziwego komputera kwantowego. Wyniki ich pracy ogłoszono niedawno w czasopiśmie Nature Physics (link do pełnego dokumentu) Co ciekawe, prawidłowy wynik (3×5) otrzymano tylko w 48% ze 150 tysięcy prób, co jest zgodne z działaniem algorytmu Shora. Oczywiście nie stanowi to żadnego problemu, ponieważ łatwo można przetestować otrzymane odpowiedzi i wybrać tą właściwą.
Poniżej możecie zobaczyć film opisujący eksperyment oraz jego wyniki.
Postęp w dziedzinie budowy komputerów kwantowych oznacza, że wraz z ich rozwojem granica możliwości obliczeniowych będzie ulegać znacznemu przesunięciu. W oparciu o dane teoretyczne już dzisiaj można powiedzieć, że faktoryzacja iloczynu dużych liczb pierwszych zamiast trwać miliardy lat, będzie mogła zostać przeprowadzona w ciągu kilkunastu minut. Oznacza to, że w przyszłości algorytmy takie jak RSA mogą okazać się przestarzałe i nieprzydatne.
Czy należy się obawiać, że nasze połączenie z bankiem może zostać podsłuchane? Na razie na pewno nie. Możemy się jednak spodziewać, ze za kilka (lub kilkanaście) lat konieczna będzie wymiana większości mechanizmów szyfrowania, wykorzystywanych w dzisiejszym świecie.
