Komputer kwantowy może złamać 2048-bitowe szyfrowanie w 8 godzin

Systemy szyfrujące nigdy nie były niezniszczalne, ale ich mocną stroną jest to, że złamanie klucza zajmuje mnóstwo czasu. Jest tak przynajmniej tak długo, jak mówimy o klasycznych komputerach. Najnowsze badania pokazują bowiem, że komputer kwantowy będzie w stanie poradzić sobie z 2048-bitowym szyfrowaniem RSA w zaledwie 8 godzin. Mówimy zatem o olbrzymim zagrożeniu.

Naukowcy postanowili sprawdzić, kiedy komputery kwantowe staną się wystarczająco potężne, by aktualne standardy szyfrowania okazały się bezużyteczne i czy rzeczywiście można mówić o zagrożeniu. Okazuje się… że rządy, organizacje wojskowe czy banki, które przechowują zabezpieczone dane przez 25 lat mogą mieć niemały problem.

Zacznijmy jednak od początku. W 1994 roku amerykański matematyk Peter Shor odkrył kwantowy algorytm rozkładu liczb naturalnych na czynniki pierwsze, znacząco przewyższający swój klasyczny odpowiednik. 

Trzeba też wiedzieć, że klucz publiczny kryptosystemu RSA to iloczyn dwóch dużych liczb pierwszych, a ich odtworzenie pozwala na poznanie klucza prywatnego i w konsekwencji: złamanie szyfru. 

Na czym polega trudność. Podajmy przykład: znając dwie liczby (np. 723 i 889) łatwo wyliczymy, że iloczyn wynosi 642 747. Znając jednak liczbę 642 747 nie dojdziemy tak łatwo do tego, jakie dwie liczby trzeba pomnożyć, by uzyskać taki wynik. Wspomniany algorytm faktoryzacji Shora to ułatwia, a komputery kwantowe pozwalają to wykorzystać.

Oczywiście im większa liczba, tym trudniej jest „rozwiązać zagadkę”, a w przypadku klasycznych komputerów praktycznie niemożliwe jest uwzględnianie liczb dłuższych niż 2048-bitowe i taka jest też baza najpopularniejszego formatu szyfrowania RSA. Komputery kwantowe rozwijają się jednak bardzo szybko.

W 2001 roku informatycy z firmy IBM i Uniwersytetu Stanforda wykorzystali algorytm Shora do rozkładu liczby 15, a dziesięć lat później udało się im zrobić to samo z liczbą 21. W 2012 – było to już 143, a pięć lat temu udało się sfaktoryzować liczbę 56 153. To tempo wzrostu jest imponujące i przerażające zarazem.

Jednak choć robi to wrażenie, dużym problemem są zakłócenia. Dlatego naukowcy od dłuższego czasu szacują, że do rozkładu 2048-bitowej liczby potrzebny będzie komputer kwantowy dysponujący miliardem kubitów (czyli bitów kwantowych), Tymczasem najpotężniejsze komputery kwantowe dziś mają ich zaledwie po kilkadziesiąt. 

Teraz naukowcy Craig Gidney z firmy Google i Martin Ekera z KTH Royal Institute of Technology pokazują dowody na to, że wystarczy komputer z 20 milionami kubitów, by z 2048-bitowym RSA poradzić sobie w zaledwie osiem godzin. Jest tak dzięki wykorzystaniu bardziej efektywnej metody wykonywania obliczenia, zwanego potęgowaniem modularnym, a będącego najbardziej skomplikowaną operacją w algorytmie faktoryzacji Shora. Udało się ją jednak zoptymalizować.

Komputer kwantowy mający 20 milionów kubitów to dziś oczywiście wciąż odległe marzenie. Znacznie bliższe jednak niż taki, który dysponuje miliardem bitów kwantowych. Zdecydowanie poważnie należy więc postarać się o odpowiedź na pytanie, czy nie uda się go stworzyć w ciągu najbliższego ćwierćwiecza, czyli: czy zabezpieczane dziś 2048-bitowym szyfrowaniem RSA dane rzeczywiście są całkowicie bezpieczne.

Źródło: TechnologyReview, ExtremeTech, ScienceAlert