Jak komputer kwantowy może złamać 2048-bitowe szyfrowanie RSA w 8 godzin?

Zbliżenie na chip D-Wave Vesuvius Steve Jurvetson | Flickr

Wiele osób obawia się, że komputery kwantowe będą w stanie złamać niektóre kody używane do wysyłania bezpiecznych wiadomości. Kody, o których mowa, szyfrują dane za pomocą matematycznych funkcji pułapek, które działają łatwo w jednym kierunku, ale nie w drugim. To sprawia, że ​​szyfrowanie danych jest łatwe, ale dekodowanie jest niezwykle trudne bez pomocy specjalnego klucza.

Te systemy szyfrowania nigdy nie były nie do złamania. Zamiast tego ich bezpieczeństwo opiera się na ogromnej ilości czasu, jaką zajęłoby klasycznemu komputerowi wykonanie tej pracy. Nowoczesne metody szyfrowania są specjalnie zaprojektowane tak, aby ich odszyfrowanie trwało tak długo, że są praktycznie nie do złamania.

Ale komputery kwantowe zmieniają to myślenie. Maszyny te są znacznie potężniejsze niż klasyczne komputery i powinny być w stanie z łatwością złamać te kody.

Rodzi to ważne pytanie — kiedy komputery kwantowe będą wystarczająco wydajne, aby to zrobić? Po tej dacie wszelkie informacje chronione tą formą szyfrowania stają się niepewne.

Dlatego naukowcy zajmujący się komputerami próbowali obliczyć zasoby, których może potrzebować taki komputer kwantowy, a następnie ustalić, ile czasu potrwa, zanim taka maszyna będzie mogła zostać zbudowana. A odpowiedzią zawsze były dziesięciolecia.

Dziś to myślenie należy zrewidować dzięki pracy Craiga Gidneya z Google w Santa Barbara i Martina Ekerå z Królewskiego Instytutu Technologicznego KTH w Sztokholmie w Szwecji. Ci faceci znaleźli wydajniejszy sposób, aby komputery kwantowe wykonywały obliczenia łamania kodu, zmniejszając wymagane zasoby o rzędy wielkości.

W związku z tym maszyny te są znacznie bliższe rzeczywistości niż ktokolwiek podejrzewał. W rezultacie czytanie będzie niekomfortowe dla rządów, organizacji wojskowych i bezpieczeństwa, banków i każdego, kto potrzebuje zabezpieczyć dane przez 25 lat lub dłużej.

Najpierw trochę tła. W 1994 roku amerykański matematyk Peter Shor odkrył algorytm kwantowy, który przewyższał jego klasyczny odpowiednik. Algorytm Shora uwzględnia duże liczby i jest kluczowym elementem procesu łamania kodów opartych na zapadniach.

Funkcje Trapdoora opierają się na procesie mnożenia, który jest łatwy do wykonania w jednym kierunku, ale znacznie trudniejszy do wykonania w odwrotnym kierunku. Na przykład pomnożenie dwóch liczb przez siebie jest trywialne: 593 razy 829 to 491 597. Ale trudno jest zacząć od liczby 491,597 i obliczyć, które dwie liczby pierwsze muszą zostać pomnożone, aby ją otrzymać.

I staje się to coraz trudniejsze, gdy liczby stają się większe. Rzeczywiście, informatycy uważają za praktycznie niemożliwe, aby klasyczny komputer rozkładał liczby dłuższe niż 2048 bitów, co jest podstawą najczęściej używanej formy szyfrowania RSA.

Shor wykazał, że wystarczająco potężny komputer kwantowy może to zrobić z łatwością, co wywołało falę uderzeniową w branży zabezpieczeń.

Od tego czasu moc komputerów kwantowych rośnie. W 2012 roku fizycy użyli czterokubitowego komputera kwantowego do współczynnika 143. Następnie w 2014 roku użyli podobnego urządzenia do współczynnika 56 153.

Łatwo sobie wyobrazić, że przy takim tempie postępu komputery kwantowe powinny wkrótce prześcignąć najlepsze komputery klasyczne.

Bynajmniej. Okazuje się, że faktoring kwantowy jest w praktyce znacznie trudniejszy, niż można by się tego spodziewać. Powodem jest to, że hałas staje się poważnym problemem dla dużych komputerów kwantowych. Najlepszym obecnie sposobem radzenia sobie z hałasem jest używanie kodów korekcji błędów, które same w sobie wymagają znacznych dodatkowych kubitów.

Uwzględnienie tego znacznie zwiększa zasoby wymagane do rozłożenia na czynniki 2048-bitowych liczb. W 2015 r. naukowcy oszacowali, że komputer kwantowy potrzebowałby miliarda kubitów, aby niezawodnie wykonać tę pracę. To znacznie więcej niż 70 kubitów w dzisiejszych najnowocześniejszych komputerach kwantowych.

Na tej podstawie eksperci ds. bezpieczeństwa mogliby uzasadnić pomysł, że upłyną dekady, zanim wiadomości z 2048-bitowym szyfrowaniem RSA zostaną złamane przez komputer kwantowy.

Teraz Gidney i Ekerå pokazali, jak komputer kwantowy może wykonać obliczenia z zaledwie 20 milionami kubitów. Rzeczywiście, pokazują, że takie urządzenie zajęłoby tylko osiem godzin, aby zakończyć obliczenia. [W rezultacie] oszacowanie najgorszego przypadku, ile kubitów będzie potrzebnych do podzielenia 2048-bitowych liczb całkowitych RSA, spadło o prawie dwa rzędy wielkości, mówią.

Ich metoda koncentruje się na bardziej wydajnym sposobie wykonywania procesu matematycznego zwanego wykładnią modułową. Jest to proces znajdowania reszty, gdy liczba zostanie podniesiona do określonej potęgi, a następnie podzielona przez inną liczbę.

Ten proces jest najbardziej kosztowną obliczeniowo operacją w algorytmie Shora. Jednak Gidney i Ekerå znaleźli różne sposoby na jego optymalizację, znacznie zmniejszając zasoby potrzebne do uruchomienia algorytmu.

To interesująca praca, która powinna mieć ważne implikacje dla każdego, kto przechowuje informacje na przyszłość. 20-milionowy komputer kwantowy z pewnością wydaje się dziś odległym marzeniem. Ale pytanie, które ci eksperci powinni sobie zadać, brzmi, czy takie urządzenie będzie możliwe w ciągu 25 lat, w których chcą zabezpieczyć informacje. Jeśli uważają, że tak, potrzebują nowej formy szyfrowania.

Rzeczywiście, eksperci ds. bezpieczeństwa opracowali kody post-kwantowe, których nawet komputer kwantowy nie będzie w stanie złamać. Dlatego już dziś można chronić dane przed przyszłymi atakami komputerów kwantowych. Ale te kody nie są jeszcze używane jako standard.

Dla zwykłych ludzi ryzyko jest niewielkie. Większość ludzi używa szyfrowania 2048-bitowego lub podobnego do zadań takich jak wysyłanie danych karty kredytowej przez Internet. Jeśli te transakcje zostaną zarejestrowane dzisiaj i rozbite za 25 lat, niewiele stracimy.

Ale dla rządów stawka jest większa. Wiadomości, które wysyłają dzisiaj – na przykład między ambasadami lub wojskiem – mogą mieć znaczenie za 20 lat i dlatego warto zachować je w tajemnicy. Jeśli takie wiadomości są nadal wysyłane za pomocą 2048-bitowego szyfrowania RSA lub czegoś podobnego, organizacje te powinny zacząć się martwić — szybko.

Nr ref.: arxiv.org/abs/1905.09749 : Jak rozłożyć na czynniki 2048-bitowe liczby całkowite RSA w ciągu 8 godzin przy użyciu 20 milionów hałaśliwych kubitów

ukryć