Квантовые компьютеры могут в любой момент взломать RSA-шифрование

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

Исследователи рассказали о первом в истории взломе 48-битного ключа системой всего из 10 сверхпроводящих кубитов. Для взлома ключа RSA-2048 потребуется не более 400 кубитов, что уже находится в диапазоне современных возможностей квантовых кубитов.

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

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

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

Ученые смогли получить революционный результат, объединив классические методы факторизации с уменьшением решетки с алгоритмом квантовой приближенной оптимизации (QAOA). По оценкам исследователей, для взлома ключа RSA-2048 потребуется всего 372 кубита. Подобная система, например, скоро появится у компании IBM. Так процессор IBM Osprey открывает доступ к 433 кубитам.

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