Bliżej złamania niełamalnego: postępy w algorytmach kwantowych i zagrożenie dla szyfru RSA

WarsawKomputery kwantowe mogą w przyszłości złamać metody szyfrowania, które kiedyś uważano za bezpieczne. Podczas gdy tradycyjne komputery mają trudności z rozkładaniem dużych liczb na czynniki pierwsze, komputery kwantowe mogą rozwiązywać te problemy szybko za pomocą algorytmu Shora. Jednakże, stworzenie praktycznych komputerów kwantowych jest wyzwaniem, ponieważ wymagają one ogromnych zasobów.

W ostatnich latach naukowcy poczynili postępy w dwóch kluczowych dziedzinach:

• Tworzenie większych komputerów kwantowych
• Udoskonalanie algorytmów do działania na mniejszych obwodach kwantowych

Oded Regev z Uniwersytetu Nowojorskiego zaproponował sposób na przyspieszenie algorytmu Shora, ale wymagało to więcej pamięci. Naukowcy z MIT opracowali lepszy algorytm, który zachowuje prędkość Regeva, ale wykorzystuje efektywność pamięci algorytmu Shora. Ten nowy algorytm zużywa mniej kubitów i lepiej radzi sobie z szumem kwantowym. Te usprawnienia mogą pomóc w tworzeniu komputerów kwantowych zdolnych do rozwiązywania rzeczywistych problemów kryptograficznych.

Złamanie szyfru RSA mogłoby mieć ogromne konsekwencje. RSA jest kluczowym elementem nowoczesnej bezpiecznej komunikacji i trudnym do złamania ze względu na konieczność faktoryzacji dużych liczb. Algorytm Shora mógłby potencjalnie złamać to zabezpieczenie, umożliwiając faktoryzację tych liczb za pomocą komputera kwantowego. Niemniej jednak, zbudowanie komputera kwantowego na tyle potężnego, aby to osiągnąć, nadal stanowi poważne wyzwanie inżynieryjne.

Zobacz również:

Dzisiaj · 12:24

Przełomowy proces przekształca odpady w ekologiczne paliwo lotnicze

Największe komputery kwantowe dzisiaj posiadają około 1,100 kubitów, ale eksperci uważają, że potrzeba około 20 milionów kubitów, aby w użyteczny sposób zastosować algorytm Shora do łamania szyfrowania. Nowa metoda opracowana przez MIT rozwiązuje niektóre z tych problemów poprzez zmniejszenie liczby potrzebnych bramek kwantowych, co jest istotne, ponieważ każda bramka wprowadza szum.

Zespół z MIT skupia się również na naprawianiu błędów, ponieważ komputery kwantowe muszą działać niemal doskonale, aby zachować dokładność. Opracowali nową metodę redukcji błędów, co czyni ich algorytm bardziej praktycznym dla rzeczywistych maszyn kwantowych.

Pozostają ważne pytania, na które trzeba odpowiedzieć. Jednym z głównych jest to, czy te ulepszenia umożliwią faktoryzację dużych liczb wykorzystywanych we współczesnym szyfrowaniu, takich jak liczby 2,048-bitowe w szyfrowaniu RSA. Chociaż te techniki wykazują potencjał, konieczne są dalsze prace, zanim będzie można je zastosować w rzeczywistych systemach zabezpieczeń.

Badania zaprezentowane na Międzynarodowej Konferencji Kryptologicznej w 2024 roku przedstawiają postępy w dziedzinie komputerów kwantowych. Ulepszenia w algorytmach i korekcji błędów czynią komputery kwantowe bardziej praktycznymi. Głównym wyzwaniem pozostaje skalowanie tych osiągnięć do poziomu niezbędnego do wpływania na obecne metody szyfrowania.