Взломают ли шифрование RSA на квантовом компьютере в 2023 году?

В последние дни 2022 года «компьютерную» общественность взволновало исследование группы китайских ученых, которые намекают, что, умело комбинируя классические и квантовые вычисления, можно взломать фундаментальный для работы интернет-протоколов криптоалгоритм RSA с длиной ключа 2048 бит уже в ближайшем будущем. Насколько эта угроза реальна? Давайте разберемся.

Квантовая азбука

О теоретической способности квантового компьютера сверхбыстро проводить факторизацию гигантских целых чисел и таким образом подбирать ключи для ряда асимметричных криптоалгоритмов, в том числе RSA, известно уже давно. В нашем блогпосте подробно объяснено, что такое квантовый компьютер, как он работает и почему его сложно построить. Все эксперты единодушно сходились, что достаточно большой для взлома RSA квантовый компьютер построят через десятки лет. Для факторизации (разложения на множители) целого числа длиной 2048 бит, которое обычно используется в качестве RSA-ключа, требуется запустить алгоритм Шора на квантовом компьютере с миллионами кубитов (квантовых битов), то есть речь о деле неблизкого будущего, поскольку самые крутые квантовые компьютеры сегодня содержат 300–400 кубитов — и это после десятков лет исследований.

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

Новости из Китая

Китайские исследователи, факторизовав 48-битное число на доступном им 10-кубитном квантовом компьютере, подсчитали, что масштабировать их алгоритм для использования с 2048-битными числами можно при помощи квантового компьютера всего лишь с 372 кубитами. Такой компьютер в принципе существует уже сегодня, например у IBM, поэтому перспектива замены криптосистем по всему Интернету внезапно перестала быть чем-то отдаленным. Прорыв обещан благодаря комбинированию алгоритма Шнорра (не путать с вышеупомянутым алгоритмом Шора) с дополнительным этапом «квантовой оптимизации» (Quantum Approximate Optimization Algorithm, QAOA).

Предложенная схема гибридного алгоритма факторизации

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

Открытые вопросы

Алгоритм Шнорра сам по себе вызвал скепсис в математическом сообществе. Скромное заявление автора «это уничтожит криптосистему RSA» в описании работы было подвергнуто проверке и не выдержало ее. Например, известный криптограф Брюс Шнайер говорит, что «алгоритм хорошо работает для маленьких чисел, но разваливается на больших«. Доказать практическую масштабируемость алгоритма на достаточно большие целые числа не удалось.

Применить к самой «тяжелой» части алгоритма квантовую оптимизацию выглядит хорошей идеей, но эксперты по квантовым вычислениям сомневаются, что оптимизация QAOA будет эффективна в данной вычислительной задаче. Применение квантового компьютера возможно, но вряд ли приведет к экономии времени. Сами авторы работы аккуратно упоминают этот сомнительный момент в самом конце, в заключении:

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

Вишенка на торте — кроме количества кубитов, у квантового компьютера есть и другие важные параметры, такие как уровень помех и ошибок, количество гейтов. По сочетанию всех этих параметров даже самые перспективные компьютеры 2023–2024 года наверняка не подходят для запуска китайского алгоритма в нужном масштабе.

Практические выводы

Хотя революция в криптографии снова откладывается, шум вокруг китайского исследования ставит две конкретные ИБ-задачи. Во-первых, новые алгебраические подходы, такие как алгоритм Шнорра, стоит внимательно изучать при выборе конкретных квантово-устойчивых алгоритмов среди многочисленных предложений на «постквантовый стандарт». Во-вторых, поднять приоритет проектов по переходу на постквантовую криптографию. Это кажется несрочным делом только до тех пор, пока не стало слишком поздно.