В декабре 2022 года группа исследователей из КНР опубликовала статью о возможности взлома длинных RSA-ключей с помощью современных квантовых компьютеров. Ученые утверждают, что они нашли способ взломать низкоуровневое шифрование RSA, используемое для безопасной передачи данных. Этот метод может быть использован для взлома наиболее продвинутого RSA-2048.
Исследователи из государственной лаборатории математической инженерии и передовых вычислений в китайском Чжэнчжоу рассказали, что им удалось взломать 48-битный ключ системой всего из 10 сверхпроводящих кубитов. Для взлома ключа RSA-2048 потребуется использование квантового компьютера с 372 кубитами, что может иметь серьезные последствия для безопасности.
RSA-шифрование остается в прошлом?
В последние годы в мире ведутся разработки с целью заменить RSA и другие стандартные криптографические решения постквантовой криптографией, которая могла бы стать более устойчивой к атакам.
Предположение, что квантовые компьютеры в конечном итоге взломают шифрование RSA, проистекает из алгоритма, опубликованного математиком Питером Шором в 1994 году. Теоретическая способность квантового компьютера выполнять сверхбыструю факторизацию гигантских целых чисел и, таким образом, сопоставлять ключи для ряда асимметричных криптоалгоритмов, включая шифрование RSA, известна давно.
Но для факторизации длинных ключей требуется большой стабильный квантовый компьютер с миллионами кубитов. Получение таких возможностей в ближайшем будущем казались фантастическими, так как лучшие квантовые компьютеры сегодня работают на 300-400 кубитах, а наиболее продвинутой машиной в настоящее время является Osprey от IBM с 433 кубитами.
Китайские ученые в своем исследовании предложили алгоритм, основанный на решении, предложенном немецким математиком Клаусом-Петером Шнорром в 2022 году, которое значительно ускоряет факторизацию: можно более эффективно разлагать большие числа, нарушая код RSA и делая это с помощью классического компьютера. Китайские исследователи утверждают, что они взломали 48-битный RSA, используя гибридную систему на основе квантового компьютера с 10 кубитами, и могли бы сделать то же самое для 2048-битного, если бы у них был доступ к квантовому компьютеру как минимум с 372 кубитами.
Прорыв был достигнут путем объединения алгоритма Шнорра с дополнительным шагом алгоритма квантовой аппроксимации (QAOA). При этом, в конце статьи команда исследователей предупреждает, что «квантовое ускорение алгоритма неясно из-за неоднозначной сходимости QAOA».
Мнения специалистов
Подход Шнорра ранее подвергся критике со стороны специалистов за неспособность выдержать масштабирование до взлома длинных ключей — практически доказать такую возможность алгоритма не удалось.
Руководитель научной группы Российского квантового центра, профессор МФТИ Алексей Федоров считает, что выводы о революции в криптографии, о которых говорят китайские исследователи, преждевременными:
«Метод Шнорра до сих пор не имеет корректной оценки сложности. Предполагается, что она является экспоненциальной, причем основная трудоемкость сосредоточена не в решении SVP, а в наборе достаточного количества таких задач (как в методе решета числового поля для факторизации требуется набор достаточного количества соотношений). Отсюда следует, что метод Шнорра не масштабируется на числа RSA, реально использующиеся в современной криптографии».
Метод, примененный китайскими исследователями, позволяет получить лишь приближенное решение SVP, которое относительно легко скорректировать для небольших чисел и решеток малой размерности, но практически невозможно для реально используемых параметров криптосистем, отмечает Федоров.
Практические выводы
По итогу неоднозначных, громких заключений и споров в медиапространстве можно сделать один вывод — криптореволюция в очередной раз откладывается. Тем не менее, резонанс помог выявить пробелы в вопросе безопасности.
Во-первых, «постквантовый стандарт» требует тщательного изучения и проработки новых алгебраических подходов (таких как вышеупомянутый алгоритм Шнорра) при выборе квантово-устойчивого алгоритма среди многочисленных предложений.
Во-вторых, на сегодняшний день не кажется срочным переход на постквантовую криптографию, однако отрасли стоит задуматься о приоритизации подобных проектов, пока не стало поздно.
