Группа исследователей из нескольких китайских научных центров и университетов предложила новый способ оптимизации процесса факторизации параметров RSA-ключей на квантовых компьютерах. По заявлению исследователей разработанный ими метод позволяет обойтись для взлома ключей RSA-2048 квантовым компьютером с 372 кубитами. Для сравнения, IBM Osprey, самый мощный из ныне созданных квантовых процессоров, содержит 433 кубита, а до 2026 года IBM планирует построить систему Kookaburra с 4000 кубитами. Тем не менее, метод пока является лишь теоретическим, не опробован на практике и вызывает скептическое отношение некоторых криптографов.
В основе шифрования RSA лежит операция возведения в степень по модулю большого числа. В открытом ключе содержится модуль и степень. Модуль формируется на основании двух случайных простых чисел, которые известны только владельцу закрытого ключа. Квантовые компьютеры позволяют эффективно решать задачу разложения числа на простые множители, что может использоваться для синтеза закрытого ключа на основе открытого.
До сих пор считалось, что с учётом нынешнего развития квантовых компьютеров RSA-ключи размером 2048 бита ещё долго не смогут быть взломаны, так как при применении классического алгоритма Шора для факторизации 2048-битного RSA-ключа требуется квантовый компьютер с миллионами кубитов. Предложенный китайскими исследователями метод ставит данное предположение под сомнение и в случае подтверждения работоспособности позволяет взламывать ключи RSA-2048 не на системах далёкого будущего, а на уже существующих квантовых компьютерах.
Метод основан на предложенном в 2021 году алгоритме быстрой факторизации Шнорра, позволяющем добиться кардинального сокращения числа операций при подборе на обычных компьютерах. Тем не менее, на практике алгоритм оказался малопригоден для взлома реальных ключей, так как срабатывал только для RSA-ключей с небольшими значениями модуля (целое число, которое нужно разложить на простые числа). Для факторизации больших чисел алгоритм оказался непригоден. Китайские исследователи утверждают, что при помощи квантовых методов они смогли обойти ограничение применения алгоритма Шнорра.
Скептическое отношение некоторых криптографов связано с тем, что в статье китайских исследователей демонстрируется применение их метода только с небольшими числами, примерно того же порядка, для которого срабатывает алгоритм Шнорра. Несмотря на заявления, что ограничение на размер преодолено, доказательств и подробностей пока не предоставлено. На практике работа метода показана для факторизации 48-битных целых чисел с использованием квантового компьютера на 10 кубитов.
Предположение, что для факторизации ключа RSA-2048 будет достаточно 372 физических кубитов делается теоретически, поэтому имеется большая вероятность того, что основанный на алгоритме Шнорра квантовый метод имеет те же проблемы с масштабированием и не сработает при разложении больших чисел. Если же проблема с масштабированием действительно решена, то стойкость криптоалгоритмов, основанных на сложности разложения больших простых чисел на множители, окажется подорванной не в дальней перспективе, как ожидалось, а уже в настоящее время.