Квантовый компьютер с 20 миллионами кубитов может сломать 2048-битное шифрование за 8 часов
Исследователи разрабатывают новый квантовый алгоритм, который использует меньше ресурсов для выполнения вычислений с нарушением кода. Квантовому компьютеру с 20-миллионным кубитом, работающему по этому алгоритму, потребуется всего 8 часов, чтобы взломать 2048-битное шифрование RSA.
Несомненно, что квантовые компьютеры смогут взломать существующие коды шифрования, используемые для отправки секретных сообщений. Эти методы шифрования никогда не были полностью надежными. Вместо этого они зависят от сложных математических функций, которые работают только в одном направлении, что упрощает шифрование информации.
Безопасность таких методов основана на времени, которое классический компьютер тратит на расшифровку информации. Современные методы шифрования практически не ломаются, поскольку сегодняшним компьютерам потребуются тысячи лет для расшифровки их кода.
Однако квантовые компьютеры могли бы легко взломать этот код, и эти машины гораздо ближе к реальности, чем ожидалось.
Недавно исследователи из Google и Королевского технологического института KTH в Швеции придумали более эффективную технику, которую квантовые компьютеры могли бы использовать для расшифровки секретных сообщений. Это позволило бы квантовым компьютерам использовать меньше ресурсов для выполнения вычислений с нарушением кода.
Квантовые компьютеры становятся все более мощными
В 1994 году американский математик Питер Шор разработал квантовый алгоритм для экспоненциального вычисления больших чисел по сравнению с лучшими существующими алгоритмами, работающими на классическом компьютере. Он предположил, что достаточно мощная квантовая машина могла бы легко сломать современные методы шифрования.
В последнее десятилетие в квантовых вычислениях был достигнут большой прогресс. В 2012 году ученые смогли использовать квантовый компьютер с 4 кубитами, чтобы получить коэффициент «143». Два года спустя они использовали похожую машину с коэффициентом «56153».
Учитывая скорость прогресса, квантовые компьютеры скоро смогут превзойти современные компьютеры. По крайней мере, это то, что ученые ожидали несколько лет назад.
Оказывается, факторинг больших чисел в квантовых машинах намного сложнее, чем предполагалось. Это связано со значительным шумом в больших квантовых компьютерах. Проблема может быть решена с помощью кодов, исправляющих ошибки, которые сами требуют дополнительных кубитов.
Принимая во внимание этот фактор шума, квантовому компьютеру понадобится один миллиард кубитов для расчета 2048-битных чисел (или для дешифрования 2048-битного шифрования RSA). Однако современные универсальные квантовые компьютеры имеют всего 70 кубитов.
Модульное экспонирование
Новый алгоритм позволяет квантовым компьютерам выполнять эти вычисления всего с 20 миллионами кубитов. Фактически, исследователи показали, что квантовому устройству, работающему по этому новому алгоритму, потребуется всего 8 часов, чтобы взломать 2048-битное шифрование RSA.
«Это означает, что наихудшая оценка числа кубитов, необходимая для вычисления 2048-битных целых чисел RSA, упала примерно на два порядка», - отмечает исследовательская группа.
Их метод выполняет модульное возведение в степень - тип возведения в степень, выполненный по модулю - эффективным способом. Эта математическая операция является вычислительно дорогой в алгоритме Шора.
Исследователи нашли разные способы оптимизировать эту операцию, резко сократив ресурсы, необходимые для запуска алгоритма.
Хотя квантовый компьютер с 20-миллионным кубитом в ближайшем будущем невозможен, эксперты по безопасности должны подумать о новой форме шифрования, которую даже мощный квантовый компьютер не сможет взломать.