11 октября 2026Команда Сарнас

Новый метод атаки на RSA: подделка подписи вместо факторизации

Исследователи показали, что подделать подпись RSA можно без разложения ключа на множители — через вариант решета числового поля с оракулом. Атака удешевляет взлом до тысяч ядро-лет и снижает стойкость даже 4096-битных ключей ниже безопасного порога. Разбираем, какие реализации уязвимы и почему стандартные схемы с паддингом пока остаются в безопасности.

Долгое время считалось, что единственный практический путь сломать RSA — разложить модуль n на простые множители. Новая работа показывает, что это не так: подделать подпись можно, не трогая сам ключ. Разбираем, на какой математической задаче это построено, какие реализации уязвимы и почему большинство систем сегодня всё же вне опасности.

Что именно изобрели: решето плюс оракул

Вместо факторизация применяется вариант решето числового поля. Этот «special» number field sieve используется вместе с оракулом. Выполняя массу операций, атакующий собирает достаточно информации, чтобы расшифровать шифртекст.

Авторы называют это key forgery attack, а не факторизацией, потому что цель — подделка подписи, а не разложение ключа. Разница в цене: факторизация 1024-битного ключа требует примерно 2^80 операций и от 500 000 до 1 млн CPU core-years, тогда как подделка подписи с помощью решета заняла 2^65 операций и 1 380 core-years.

Кого атака задевает, а кого нет

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

Это важно разграничить с тем, что описано в RFC 8017. Там определены две схемы шифрования и две схемы подписи с приложением. Отдельно спецификация предупреждает: если одна пара ключей используется и в схеме шифрования с оптимальным асимметричным шифрованием, и в схеме шифрования с паддингом по стандарту PKCS#1 версии 1.5, противник может эксплуатировать слабость реализации второй из них, чтобы восстановить сообщения, зашифрованные любой из схем, хотя первая сама по себе устойчива к атаке. Аналогично, если пара ключей применяется и в схеме подписи с вероятностным паддингом, и в схеме подписи с паддингом по стандарту PKCS#1 версии 1.5, доказательство безопасности первой перестаёт быть достаточным — оно не учитывает возможность генерации подписей второй схемой.

Механика: чего в описании нет

Пошаговой последовательности действий атакующего с указанием входных данных (открытый ключ, подписи, шифртексты) и вычислений на каждом шаге в источниках нет. Известно только, что атака реализует вариант решета числового поля 2007 года и использует оракул — свойство протокола, дающее ответы на запрашиваемые входные данные.

Описан только один исход — подделка подписи.

Точные пороги и стоимость

Атака уже полностью практична для 1024-битного RSA. Для 2048- и 4096-битных ключей она снижает стойкость до неприемлемого уровня:

Размер ключа	Уровень стойкости после атаки
1024 бит	2^65
2048 бит	2^90
4096 бит	2^119

Требуется не менее 128 бит стойкости — то есть операции должны превышать 2^128. Ни один из этих уровней порог не проходит.

Вычислительные затраты: 1 380 core-years, что соответствует примерно 12,09 млн core-hours. На одной высококлассной GPU с оптимизированным CUDA-конвейером это заняло бы примерно 24 000–48 000 часов; на кластере из 4 000 GPU — около 6–12 часов. В другом месте источника та же оценка для одной современной высокопроизводительной GPU приводится как примерно 200–600 часов. Применение атаки к 1024-битным ключам заняло несколько месяцев на академическом CPU-кластере.

Как сравнивали и что получилось

Есть сопоставление двух стоимостей для 1024-битного ключа:

Классическая факторизация: примерно 2^80 операций и 500 000–1 000 000 CPU core-years.
Подделка подписи через решето: 2^65 операций и 1 380 core-years.

Обе цифры относятся к 1024-битному ключу. Оговорка: это оценки стоимости, а не воспроизводимый стенд с указанием железа, версий и параметров нагрузки. Для 2048- и 4096-битных ключей приводятся только итоговые уровни стойкости (2^90 и 2^119), без отдельных замеров в core-years или часах на конкретном железе.

Что происходит при повторном использовании ключа и смене схемы

RFC 8017 прямо не рекомендует использовать одну пару ключей RSA в нескольких схемах для новых приложений. Причины:

Совместное применение в RSAES-OAEP и RSAES-PKCS1-v1_5 позволяет противнику через слабость реализации второй схемы восстанавливать сообщения, зашифрованные любой из них.
Совместное применение в RSASSA-PSS и RSASSA-PKCS1-v1_5 лишает доказательство безопасности PSS силы, поскольку оно не учитывает генерацию подписей второй схемой.
Сходные соображения применимы, если пара ключей используется в одной из определённых здесь схем и в варианте, определённом в другом месте.

Для RSAES-OAEP выбор хэш-функции и функции генерации маски должен быть зафиксирован для данного ключа RSA.

Параметры схем, влияющие на применимость

Применимость атаки зависит от длины модуля RSA (k), размера хэша (hLen), длины соли (sLen) в PSS и режима OAEP.

Для RSAES-OAEP сообщение может быть длиной до k − 2hLen − 2 октетов, где hLen — длина выхода хэш-функции, k — длина модуля в октетах. При превышении выдаётся ошибка «message too long».

В EMSA-PSS длина соли sLen задаётся как параметр, и emBits должен быть не менее 8hLen + 8sLen + 9. Типичные длины соли — hLen и 0; в обоих случаях безопасность RSASSA-PSS может быть связана со сложностью инвертирования RSAVP1.

В OAEP метка L по умолчанию — пустая строка, а хэш и MGF фиксируются для данного ключа.

Что видит клиент

Проверка подписи выполняется на стороне верификатора, а не на стороне клиента, поэтому обнаружение самой атаки по побочным признакам в источниках не описано. При проверке подписи по схеме EMSA-PSS-VERIFY проверка завершается отказом «inconsistent»:

если длина сообщения M превышает предел хэш-функции (2^61 − 1 октет для SHA-1);
если emLen < hLen + sLen + 2;
если правый октет EM не равен 0xbc;
если итоговое сравнение H и H' не совпало.

При проверке подписи по схеме RSASSA-PKCS1-v1_5-VERIFY неверная длина подписи S даёт «invalid signature».

Почему выбрали именно эту модификацию

Авторы использовали «special» number field sieve 2007 года вместе с оракулом. Массовое выполнение операций позволяет собрать достаточно информации для расшифровки шифртекста. Техника применима только к реализациям со слепой подписью, тогда как подавляющее большинство используемого сегодня RSA применяет padding PKCS или PSS, добавляющий данные к открытому тексту перед шифрованием.

Компромисс по длине ключа прост: чем меньше ключ, тем меньше операций нужно для подделки. Уровни 2^65, 2^90 и 2^119 для 1024, 2048 и 4096 бит соответственно — все ниже требуемых 128 бит.

В RFC 8017 заложен свой компромисс: RSAES-OAEP обязателен для новых приложений, а RSAES-PKCS1-v1_5 включён только для совместимости с существующими.

Какие предположения о стойкости пошатнулись

Стойкость RSASSA-PKCS1-v1_5 в RFC 8017 выводится из предположения, что вычисление корней e-й степени по модулю n неосуществимо, а хэш-функция в EMSA-PKCS1-v1_5 обладает подходящими свойствами. При этих условиях подделка подписей без знания закрытого ключа считается вычислительно неосуществимой.

Новая атака показывает, что RSA можно практически сломать без взлома ключа: это вводит подделку подписей как новый способ взлома RSA без факторинга. При этом атака работает только против реализаций со слепой подписью, а для RSA с PKCS или PSS padding практической угрозы не представляет, поскольку они дают другой тип оракула.

Что из этого следует на практике

Слепая подпись (textbook RSA) — вне игры. Именно она даёт оракул нужного типа. Если ваша схема подписи не добавляет паддинг, атака применима напрямую.
1024-битные ключи непригодны. Атака для них полностью практична: 2^65 операций и 1 380 core-years, что укладывается в месяцы на академическом CPU-кластере.
2048- и 4096-битные ключи тоже ниже порога. 2^90 и 2^119 против требуемых 128 бит. Размер ключа сам по себе проблему не решает.
Не переиспользуйте пару ключей в нескольких схемах. RFC 8017 прямо не рекомендует это для новых приложений: слабость одной схемы подрывает стойкость другой, а доказательство безопасности PSS перестаёт учитывать подписи, сделанные через PKCS1-v1_5.
Для новых приложений — RSAES-OAEP и современные хэши. Спецификация требует поддерживать RSAES-OAEP и рекомендует только SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 и SHA-512/256. Для схем подписи половина длины хэша должна быть не меньше желаемого уровня стойкости в битах.
Ротация ключей помогает, но не спасает. Большинство реализаций Privacy Pass регулярно меняет ключи — это сильно снижает, но не устраняет автоматически шансы атакующего.
Направление — уход от RSA. Авторы указывают, что новая атака повышает срочность полного отказа от этой криптосистемы.