Квантовый компьютер с 20 миллионами кубитов может взломать 2048-битное шифрование за 8 часов

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

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

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

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

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

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

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

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

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

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

Ссылка:arXiv:1905.09749 | Обзор технологий MIT

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

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

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

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

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

Читайте:5 квантовых процессоров с новой вычислительной парадигмой

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