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

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

Учёные предпринимают попытки масштабировать алгоритм Шора таким образом, чтобы взлом RSA не был настолько ресурсоемким для квантовых систем. В 2016 году группа физиков Массачусетского технологического института и Инсбрукского университета разработала квантовый компьютер, который подтвердил масштабирование при выполнении алгоритма Шора. Но серьёзного прорыва на тот момент не произошло.

У китайские учёных была достаточно скромная квантовая система. Чтобы масштабировать ее, они воспользовались исследованиями другого специалиста по криптографии — Клауса-Питера Шнорра, который весной прошлого года разработал методику, существенно ускоряющую факторизацию. Тогда Работа Шнорра столкнулась с критикой из-за неспособности выдержать масштабирование до взлома длинных ключей, «смерть» которых действительно могла бы покончить с RSA-шифрованием. Но китайские исследователи утверждают, что смогли обойти это ограничение и взломали 48-битный ключ 10-кубитной квантовой системой. По их словам, метод работает для взлома ключей криптографически большей длины.

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