MIT против RSA: Новый квантовый алгоритм приближает крах шифрования

Современные методы шифрования, такие как RSA, основаны на том, что даже самые мощные классические компьютеры не способны быстро разложить большое число на простые множители. Однако квантовые компьютеры обещают значительно ускорить этот процесс благодаря алгоритму, предложенному в 1994 году Питером Шором, который доказал, что квантовый компьютер может взламывать криптографию RSA.

На протяжении последних 30 лет ученые активно разрабатывают квантовые компьютеры, но до сих пор не удалось создать устройство, достаточно мощное для запуска алгоритма Шора. Для его выполнения требуется квантовый компьютер с примерно 20 миллионами кубитов, в то время как самые современные квантовые компьютеры насчитывают около 1,100 кубитов.

Некоторые исследователи сосредоточены на создании более мощных квантовых компьютеров, тогда как другие пытаются улучшить алгоритм Шора, чтобы его можно было запускать на менее мощных устройствах. Год назад учёный из Нью-Йоркского университета Одед Регев предложил теоретическое улучшение алгоритма, которое позволило бы ему работать быстрее, но потребовало бы больше памяти.

На основе этой идеи исследователи из MIT разработали новый подход, который сочетает скорость алгоритма Регева с экономичностью алгоритма Шора в плане использования памяти. Новый алгоритм не только так же быстр, как алгоритм Регева, но и требует меньше кубитов, а также обладает более высокой устойчивостью к шумам в квантовых системах, что делает его более практичным для реализации.

Этот новый алгоритм может сыграть важную роль в будущем, когда потребуется разработать новые методы шифрования, способные противостоять мощным квантовым компьютерам. Если квантовые компьютеры станут достаточно большими, традиционные методы криптографии, такие как RSA, перестанут быть безопасными, и понадобится использовать новые технологии шифрования.

Исследование было представлено на Международной конференции по криптологии в 2024 году. Ученые из MIT также предложили новый метод вычисления экспонент на квантовом компьютере с использованием чисел Фибоначчи, что позволяет выполнять операции с использованием всего двух квантовых регистров памяти. Это делает процесс вычисления более эффективным и уменьшает количество необходимой памяти.

Кроме того, они предложили метод коррекции ошибок, который позволяет фильтровать некорректные результаты и использовать только правильные, что также делает алгоритм более пригодным для практической реализации.

В перспективе исследователи надеются сделать алгоритм ещё более эффективным и протестировать его на реальном квантовом компьютере. Однако остается вопрос, насколько близко это достижение подводит нас к реальному взлому RSA-криптографии, так как текущие улучшения становятся полезными только при разложении чисел, значительно превышающих 2048 бит.

Таким образом, разработка MIT – это значительный шаг в сторону создания практических квантовых алгоритмов, которые могут оказать существенное влияние на безопасность данных в будущем.