Китайские ученые Шанхайского университета применили квантовый компьютер для факторизации 22-битного целого числа в алгоритме шифрования RSA. Об этом пишет Earth со ссылкой на исследование.
«Используя [устройство] D-Wave Advantage, мы успешно разложили на множители 22-битное целое число RSA, продемонстрировав потенциал квантовых машин для решения криптографических задач», — пишут авторы.
До этого алгоритм сопротивлялся попыткам взлома на том же классе оборудования.
Хотя 22-битные ключи не являются безопасными по современным стандартам и поддаются факторизации на классических системах, на сегодняшний день это самое большое число, полученное с помощью квантового отжига .
В большинстве соверменных систем безопасности используется 2048-битное шифрование, а самый объемный ключ, взломанный традиционными методами, составляет всего 829 бит (RSA-250). Его удалось расшифровать за несколько недель вычислений на суперкомпьютере.
Для факторизации 22-битного RSA ученые использовали тот же метод, что и при успешной дешифровке алгоритмов Present, Gift-64 и Rectangle в октябре 2024 года. Они назвали прорыв «первым случаем, когда реальный квантовый компьютер представляет существенную угрозу для нескольких полномасштабных структурированных алгоритмов».
Методология
22-битный ключ тривиально мал по сравнению с RSA промышленного уровня, однако тест имеет значение, поскольку подход масштабируется за пределы прошлых исследований, которые ограничивались 19 битами и требовали большего количества кубитов на переменную.
Согласно статье, уменьшение коэффициентов локального поля и связи в модели Изинга снижает уровень шума, позволяя отжигу чаще достигать правильных коэффициентов и указывая пути к более крупным ключам.
Универсальные квантовые машины на основе вентилей работают по алгоритму Шора , который в теории может «разбить» RSA, найдя период модульного возведения в степень за полиномиальное время. Однако подобные устройства испытывают трудности с коррекцией ошибок и требуют большого количества кубитов.
Для оптимизации процесса китайские ученые применили отжиг вместо метода Шора. Таким образом они изменили тип задачи для компьютера с нахождения периода числа на поиск самого значения. Стратегия позволяет обойти текущие ограничения по количеству кубитов, но за это приходится платить экспоненциальным масштабированием, поэтому удалось получить только 22-битный модуль.
Угроза уже здесь
Алгоритм RSA с большим ключом по-прежнему безопасен, однако исследование показывает, что усовершенствование оборудования и оптимизация вычислений уже представляют угрозу.
Большинство предприятий, включая банки и другие зависящие от шифрования структуры, еще не обновили свои криптографические ресурсы, пишут журналисты Earth. При этом многие даже не знают, от каких алгоритмов зависят их системы.
Организации, десятилетиями хранящие конфиденциальные данные, медицинские записи, финансовые файлы и дипломатические телеграммы, могут сильнее всего пострадать, если будут ждать появления полномасштабного квантового компьютера.
Хотя взлом 22-битного RSA основывался на долгой предварительной и последующей обработке, а отжигу требовалось много запусков для нахождения нужных значений, криптографы рекомендуют фирмам и учреждениям начть прорабатывать план по переходу на новые алгоритмы.
Кроме того, «промежуточные» взломы систем шифрования уже могут представлять значительную угрозу безопасности. Поэтому рекомендуется применять комбинированные методы защиты данных.
