Новый квантовый алгоритм позволяет 20-миллионному квантовому компьютеру взломать 2048-битный RSA за 8 часов

Квантовый алгоритм снижает ресурсы для взлома шифрования

Исследователи разработали новый квантовый алгоритм, который использует меньше ресурсов для выполнения вычислений по взлому кода. Квантовый компьютер на 20 миллионов кубитов, работающий на этом алгоритме, затратит всего 8 часов на взлом 2048-битного шифрования RSA.

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

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

Однако квантовые компьютеры смогут взламывать эти коды легко, и эти машины гораздо ближе к реальности, чем ожидалось.

Недавно исследователи из Google и Королевского технологического института в Швеции (KTH) придумали более эффективную технику, которую квантовые компьютеры могли бы использовать для расшифровки секретных сообщений. Она позволит квантовым компьютерам использовать меньше ресурсов для выполнения вычислений по взлому кода.

Квантовые компьютеры становятся мощнее

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

За последнее десятилетие в квантовых вычислениях сделано много достижений. В 2012 году ученые смогли использовать 4-кубитный квантовый компьютер для факторизации «143». Через два года они использовали похожую машину для факторизации «56153».

Учитывая темп прогресса, квантовые компьютеры скоро смогут превзойти современные компьютеры. По крайней мере, так ожидали ученые несколько лет назад.

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

Источник: arXiv:1905.09749 | MIT Technology Review

Учитывая этот фактор шума, квантовый компьютеру потребовался бы один миллиард кубитов для факторизации 2048-битных чисел (или для взлома 2048-битного шифрования RSA). Однако современные универсальные квантовые компьютеры имеют всего 70 кубитов.

Модулярное возведение в степень

Новый алгоритм позволяет квантовым компьютерам выполнять эти вычисления всего с 20 миллионами кубитов. Фактически, исследователи показали, что квантовое устройство, работающее на этом новом алгоритме, затратит всего 8 часов на взлом 2048-битного шифрования RSA.

Их метод эффективно выполняет модулярное возведение в степень — тип возведения в степень, выполняемый по модулю. Эта математическая операция вычислительно затратна в алгоритме Шора.

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

Хотя квантовый компьютер с 20 миллионами кубитов неосуществим в ближайшем будущем, эксперты по безопасности должны подумать о новой форме шифрования, которую даже мощный квантовый компьютер не сможет взломать.