RSA больше не вечен: миллион кубитов — и неделя на взлом

Компания Google опубликовала исследование, согласно которому взлом RSA-шифрования с длиной ключа 2048 бит может стать возможным менее чем за неделю при наличии квантового компьютера с менее чем миллионом физических (noisy qubits, шумных) кубитов. Работа под руководством Крейга Гидни размещена на arXiv и в блоге Google Security.

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

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

Прорыв стал возможен за счёт внедрения approximate modular exponentiation — приближённого модульного возведения в степень, что позволило значительно сократить число логических кубитов. Кроме того, применена более плотная модель размещения кубитов с коррекцией ошибок, в том числе с использованием yoked surface codes (модифицированных поверхностных кодов с объединённой структурой) и дистилляции магических состояний — техники, необходимой для реализации универсальных квантовых операций.

RSA и аналогичные схемы факторизации лежат в основе защищённых цифровых коммуникаций — от онлайн-банкинга до электронных подписей. Исследование подтверждает необходимость перехода на постквантовую криптографию (PQC). В 2024 году Национальный институт стандартов и технологий США (NIST) утвердил первые стандарты PQC и рекомендовал полностью отказаться от уязвимых алгоритмов после 2030 года.

Подробнее: https://www.securitylab.ru/news/559773.php