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

Подделка RSA-подписей без факторизации модуля: что именно утверждает атака

Статья разбирает атаку на RSA-подписи, которая обходится без факторизации модуля: вместо разложения ключа она ищет мультипликативные соотношения между представителями сообщений. Это интересно потому, что показывает принципиально иной вектор атаки, чем привычный «взлом RSA через факторизацию», и объясняет, почему конкретные схемы кодирования способны её заблокировать.

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

Что решает атака вместо разложения n

Вместо факторизации n атака решает другую задачу: ищет мультипликативные соотношения между представителями сообщений, разлагая сами представители на набор малых значений, например малых простых. Представитель сообщения. Если такие представители удаётся разложить на малые множители, между ними возникают мультипликативные соотношения, и из них можно скомбинировать подпись, не зная закрытого ключа. Такая задача относится к атакам типа предложенной Desmedt и Odlyzko, а не к факторизации n.

Предположение о стойкости RSA сформулировано иначе — как неосуществимость вычисления корней степени e по модулю n: «Assuming that computing e-th roots modulo n is infeasible…». То есть стойкость схемы опирается на сложность одной задачи, а атака бьёт по другой — по структуре самих кодированных сообщений.

Метод кодирования EMSA-PKCS1-v1_5 гарантирует, что закодированное сообщение, преобразованное в целое, является большим и по крайней мере отчасти «случайным», что предотвращает такие атаки: «This prevents attacks of the kind proposed by Desmedt and Odlyzko [CHOSEN]…». Анализ сложности этой атаки против EMSA-PKCS1-v1_5 показал её непрактичность: требуется больше операций, чем при поиске коллизий хэш-функции, то есть более 2^80 операций.

Модель угроз и предпосылки

Модель атакующего с доступом к оракулу подписи, с числом допустимых запросов или с требованием знания хэша сообщения не описывается. Описание атак с оракулом относится к расшифровке, а не к подписи: «an adversary is given the opportunity to send queries to an oracle simulating the decryption primitive.»

Для схем с дополнением (signature scheme with appendix) указано, что для проверки подписи необходимо иметь само сообщение: «To verify a signature constructed with this type of scheme, it is necessary to have the message itself.»

Стойкость обеих схем формулируется через предположение о невозможности вычисления корней степени e по модулю n. Для RSASSA-PSS: «Assuming that computing e-th roots modulo n is infeasible and the hash and mask generation functions in EMSA-PSS have appropriate properties, RSASSA-PSS provides secure signatures.» Для RSASSA-PKCS1-v1_5 сказано, что подделка подписей без знания закрытого ключа предполагается вычислительно невозможной: «forging signatures without knowing the RSA private key is conjectured to be computationally infeasible.»

Отдельно отмечено, что в EMSA-PKCS1-v1_5 встроен идентификатор хэш-функции, поэтому атакующему для поиска сообщения с той же подписью нужно искать коллизии именно выбранной хэш-функции: «an adversary trying to find a message with the same signature as a previously signed message must find collisions of the particular hash function being used».

Ограничения на параметры ключа и схемы

Источники описывают ограничения на параметры RSA-ключа и схемы подписи, но не на параметры самой атаки.

Для открытого ключа: модуль n — произведение u различных нечётных простых r_i, где u >= 2, а открытая экспонента e — целое от 3 до n - 1, удовлетворяющее GCD(e, λ(n)) = 1. Для закрытого ключа n также произведение u различных нечётных простых, u >= 2, а d — положительное целое меньше n, удовлетворяющее e * d == 1 (mod λ(n)).

В EMSA-PSS длина соли sLen задаёт длину соли в октетах, а emBits должен быть не менее 8hLen + 8sLen + 9, где hLen — длина выхода хэш-функции в октетах.

Типичные длины соли — hLen и 0, а в общем случае рассматриваются длины от 0 до hLen. В MGF1 maskLen не должен превышать 2^32 hLen, иначе выводится ошибка «mask too long».

Как устроено кодирование EMSA-PKCS1-v1_5

EMSA-PKCS1-v1_5 формирует EM детерминированно. Сначала вычисляется хэш H сообщения, затем строится DigestInfo — ASN.1-структура, содержащая идентификатор алгоритма хэширования и сам хэш. DigestInfo имеет вид SEQUENCE из двух полей: digestAlgorithm и digest OCTET STRING. Здесь digestAlgorithm идентифицирует хэш-функцию и должен быть algorithm ID с OID из набора PKCS1-v1-5DigestAlgorithms, а digest — OCTET STRING с хэшем. DER-кодирование T этого DigestInfo для девяти хэш-функций задано явными байтовыми префиксами, за которыми следует H, например для SHA-256:

SHA-256: (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H.

Схема детерминирована, потому что хэш-функции детерминированы: выход полностью определяется входом. Именно поэтому для детерминированного метода проверка может просто перекодировать сообщение и сравнить EM, тогда как для рандомизированного EMSA-PSS проверка сложнее.

Как работает проверка RSASSA-PKCS1-v1_5-VERIFY

Проверка принимает открытый ключ (n, e), сообщение M и подпись S длиной k октетов, где k — длина модуля n в октетах. Порядок шагов такой:

Проверка длины: если длина S не равна k октетам, выводится «invalid signature» и работа прекращается.
S преобразуется в целое s через OS2IP. К (n, e) и s применяется примитив RSAVP1. Если RSAVP1 выдаёт «signature representative out of range», выводится «invalid signature» и работа прекращается.
m преобразуется в EM длиной k октетов через I2OSP; если I2OSP выдаёт «integer too large», выводится «invalid signature» и работа прекращается.
К сообщению M применяется кодирование EMSA-PKCS1-v1_5-ENCODE (M, k), дающее второй закодированный текст EM'. Если кодирование выдаёт «message too long», выводится «message too long»; если «intended encoded message length too short» — выводится «RSA modulus too short».
Сравниваются EM и EM': при совпадении выводится «valid signature», иначе — «invalid signature».

Ключевой момент — на шаге 4 сравнивается не подпись и не хэш, а два закодированных сообщения целиком.

Как устроено кодирование EMSA-PSS-ENCODE

EMSA-PSS-ENCODE — рандомизированная схема кодирования, параметризуемая выбором хэш-функции, функции генерации маски и длины соли. Эти параметры фиксируются для данного ключа RSA, кроме длины соли, которая может быть переменной.

Сначала вычисляется mHash = Hash(M) длиной hLen, затем генерируется случайная соль длины sLen (пустая при sLen = 0), и формируется M' = восемь нулевых октетов || mHash || salt длиной 8 + hLen + sLen. Из M' вычисляется H = Hash(M'), а DB строится как PS || 0x01 || salt, так что DB имеет длину emLen − hLen − 1. Затем вычисляется маска dbMask = MGF(H, emLen − hLen − 1) — псевдослучайная строка той же длины, что и DB, — и maskedDB = DB xor dbMask: маскирование скрывает структуру DB, чтобы по закодированному сообщению нельзя было восстановить соль и разделитель без знания H.

Параметр emBits = modBits − 1 задаёт emLen (длину EM в октетах) и управляет обнулением старших битов: левые 8emLen − emBits бит самого левого октета maskedDB обнуляются, после чего EM = maskedDB || H || 0xbc.

Длина EM будет на один октет меньше k, если modBits − 1 делится на 8, и равна k в противном случае.

Как работает EMSA-PSS-VERIFY

Проверка принимает сообщение M, кодированное сообщение EM длины emLen = ceil(emBits/8) и emBits, и возвращает «consistent» или «inconsistent». Ключевые проверки:

Шаг 3: emLen не меньше hLen + sLen + 2, иначе «inconsistent».
Шаг 4: самый правый октет EM равен 0xbc, иначе «inconsistent».
Шаг 5: из EM выделяются maskedDB (левые emLen - hLen - 1 октетов) и H (следующие hLen октетов).
Шаг 6: левые 8emLen - emBits бит левого октета maskedDB равны нулю, иначе «inconsistent».
Шаги 7–8: dbMask = MGF(H, emLen - hLen - 1), DB = maskedDB xor dbMask.
Шаг 9: левые 8emLen - emBits бит левого октета DB обнуляются.
Шаг 10: если левые emLen - hLen - sLen - 2 октетов DB не нулевые или октет в позиции emLen - hLen - sLen - 1 не равен 0x01 — «inconsistent».
Шаги 11–13: salt — последние sLen октетов DB, M' = восемь нулевых октетов || mHash || salt, H' = Hash(M').
Шаг 14: при H = H' выводится «consistent», иначе «inconsistent».

Примитивы и преобразования

RSASP1 принимает закрытый ключ K и представитель сообщения m, а RSAVP1 принимает открытый ключ (n, e) и представитель подписи s; обе функции выполняют возведение в степень по модулю n. Представитель сообщения — это целое число, полученное из закодированного сообщения, а представитель подписи — целое число, полученное из октетной строки подписи; поэтому для подписи используется функция с закрытым ключом, а для проверки — с открытым. RSASP1 проверяет, что m лежит в диапазоне от 0 до n - 1, иначе выводится «message representative out of range». RSAVP1 проверяет, что s лежит в диапазоне от 0 до n - 1, иначе выводится «signature representative out of range». Эти проверки гарантируют, что входные представители являются допустимыми элементами кольца вычетов по модулю n, так что возведение в степень m^d mod n или s^e mod n определено корректно. Без таких проверок значение вне диапазона могло бы привести к неопределённому поведению при вычислении по модулю.

I2OSP переводит неотрицательное целое x в октетную строку заданной длины xLen: сначала проверяется, что x < 256^xLen, иначе выдаётся ошибка «integer too large»; затем x записывается в xLen-разрядном представлении по основанию 256. OS2IP выполняет обратное преобразование. Ошибка «integer too large» возникает только в I2OSP, когда x >= 256^xLen, то есть при слишком малой длине xLen для данного целого.

Пошаговый разбор атаки

Проверка подписи RSASSA-PKCS1-V1_5 начинается с того, что длина S должна быть ровно k октетов, где k — длина модуля n в октетах; иначе сразу выводится «invalid signature». Затем S преобразуется в целое s = OS2IP(S), и к нему применяется RSAVP1: если s не лежит между 0 и n-1, выводится «signature representative out of range»; иначе вычисляется m = s^e mod n. Полученное m преобразуется обратно в EM длины k октетов через I2OSP(m, k); если m слишком велико для k октетов, выводится «integer too large». Далее независимо вычисляется EM' = EMSA-PKCS1-V1_5-ENCODE(M, k), и подпись считается действительной только если EM совпадает с EM'.

Таким образом, условие S^e mod n = EM равносильно тому, что EM должен быть результатом EMSA-PKCS1-V1_5-ENCODE(M, k) длины k.

Пограничные случаи

При превышении допустимой длины сообщения для схемы v1_5 (mLen > k − 11) операция шифрования прерывается с выводом «message too long» и остановкой, то есть EM не формируется и не шифруется. Для схемы PSS при недостаточной длине закодированного сообщения (emLen < hLen + sLen + 2) операция кодирования прерывается с выводом «encoding error» и остановкой, то есть EM не создаётся. В обоих случаях проверка длины выполняется до формирования EM, поэтому атака, требующая наличия EM, не может быть проведена на этом шаге.

Что если проверяющая сторона использует другой хэш или другую длину соли

Проверяющая сторона в EMSA-PSS-VERIFY сама задаёт опции Hash, MGF и sLen — «intended length in octets of the salt» — и использует их при восстановлении и пересчёте. Если её Hash отличается от того, что подразумевал атакующий, то на шаге 2 она вычислит mHash = Hash(M) своим алгоритмом, а на шаге 13 пересчитает H' = Hash(M') тем же своим алгоритмом, и сравнение H = H' на шаге 14 даст «inconsistent». Если её sLen отличается, то на шаге 10 проверка позиции 0x01 и нулевых октетов DB, а также выделение salt как последних sLen октетов DB (шаг 11) не совпадут с заложенными при подделке, и будет выдан «inconsistent». То есть подделка, рассчитанная на другой хэш или другую длину соли, при проверке не подтвердится.

RFC отдельно отмечает, что согласование хэш-функции MGF с хэш-функцией сообщения служит именно для предотвращения подстановки хэш-функции, но эта защита не нужна, если проверяющий принимает только designated hash function.

Что видит проверяющая сторона

При успешной проверке обе схемы возвращают «valid signature» без каких-либо предупреждений. Для RSASSA-PSS шаг 4 предписывает: «If Result = "consistent", output "valid signature". Otherwise, output "invalid signature".» Для RSASSA-PKCS1-v1_5: «If they are the same, output "valid signature"; otherwise, output "invalid signature".»

Механизмы обнаружения аномалий встроены в саму процедуру проверки EMSA-PSS: она проверяет длину сообщения по ограничению хэш-функции, минимальную длину emLen, наличие завершающего октета 0xbc, нулевые старшие биты maskedDB, нулевые левые октеты DB и октет 0x01, а затем сравнивает H и H'. Для EMSA-PKCS1-v1_5 проверка детерминирована: «the verification operation may apply the message encoding operation to the message and compare the resulting encoded message to the previously derived encoded message. If there is a match, the signature is considered valid.» В RSASSA-PSS проверка сложнее, поскольку метод рандомизирован: «the verification operation in EMSA-PSS extracts the random salt and a hash output from the encoded message and checks whether the hash output, the salt, and the message are consistent».

Почему v1_5 сохранён, несмотря на известные атаки

RSASSA-PKCS1-v1_5 сохранён только для совместимости с существующими приложениями, а для новых приложений требуется RSASSA-PSS: «Although no attacks are known against RSASSA-PKCS1-v1_5, in the interest of increased robustness, RSASSA-PSS is REQUIRED in new applications. RSASSA-PKCS1-v1_5 is included only for compatibility with existing applications.»

Детерминированное кодирование EMSA-PKCS1-v1_5 позволяет проверяющему просто повторить кодирование сообщения и сравнить результат с уже полученным закодированным сообщением. Встраивание идентификатора хеш-функции означает, что противник для подделки должен найти коллизии именно выбранной хеш-функции, а не другой: «Because of this feature, an adversary trying to find a message with the same signature as a previously signed message must find collisions of the particular hash function being used; attacking a different hash function than the one selected by the signer is not useful to the adversary.»

Анализ атак показал, что атака на EMSA-PKCS1-v1_5 непрактична и требует больше операций, чем поиск коллизий: «They also analyzed the complexity of this type of attack against the EMSA-PKCS1-v1_5 encoding method and concluded that an attack would be impractical, requiring more operations than a collision search on the underlying hash function (i.e., more than 2^80 operations).» Поэтому рекомендуется постепенный переход к EMSA-PSS как предосторожность: «Moreover, while no attack is known against the EMSA-PKCS-v1_5 encoding method, a gradual transition to EMSA-PSS is recommended as a precaution against future developments.»

Компромисс между совместимостью и стойкостью также виден в предупреждении не использовать одну пару ключей в нескольких схемах, включая RSASSA-PSS и RSASSA-PKCS1-v1_5: «Then the security proof for RSASSA-PSS would no longer be sufficient since the proof does not account for the possibility that signatures might be generated with a second scheme.»

Что делает PSS устойчивее и где остаются риски

RSASSA-PSS использует рандомизированное кодирование EMSA-PSS с солью: «It is randomized and has an encoding operation and a verification operation», а соль повышает стойкость за счёт более плотного доказательства безопасности по сравнению с детерминированными схемами: «The salt value enhances the security of the scheme by affording a "tighter" security proof than deterministic alternatives such as Full Domain Hashing (FDH)». При проверке из закодированного сообщения извлекаются соль и хэш, после чего проверяется их согласованность с сообщением.

В разделе 8.1 отмечено, что идентификатор хэш-функции не встраивается в кодированное сообщение EMSA-PSS, поэтому теоретически возможна подмена хэш-функции: «a hash function identifier is not embedded in the EMSA-PSS encoded message, so in theory it is possible for an adversary to substitute a different (and potentially weaker) hash function than the one selected by the signer». Для предотвращения такой подмены рекомендуется, чтобы MGF основывалась на той же хэш-функции: «it is RECOMMENDED that the EMSA-PSS mask generation function be based on the same hash function».

Однако сама по себе случайность не критична для безопасности: «However, the randomness is not critical to security. In situations where random generation is not possible, a fixed value or a sequence number could be employed instead, with the resulting provable security similar to that of FDH». Поэтому переход на PSS не является полным решением при ошибках реализации: гарантия безопасности обусловлена корректностью хэша и MGF — «Assuming that computing e-th roots modulo n is infeasible and the hash and mask generation functions in EMSA-PSS have appropriate properties, RSASSA-PSS provides secure signatures», а также тем, что проверка должна корректно восстанавливать соль и пересчитывать H: «Note that the verification operation follows reverse steps to recover salt and then forward steps to recompute and compare H».

Связь с FIPS 186-5

FIPS 186-5 задаёт набор алгоритмов для генерации цифровой подписи, позволяющих обнаруживать несанкционированные изменения данных и аутентифицировать подписанта, а также служить доказательством третьей стороне (non-repudiation).

Условия безопасности RSA-подписей приведены в RFC 8017: для RSASSA-PSS — «Assuming that computing e-th roots modulo n is infeasible and the hash and mask generation functions in EMSA-PSS have appropriate properties, RSASSA-PSS provides secure signatures», а для RSASSA-PKCS1-v1_5 — «Assuming that computing e-th roots modulo n is infeasible and the hash function in EMSA-PKCS1-v1_5 has appropriate properties, RSASSA-PKCS1-v1_5 is conjectured to provide secure signatures». Для EMSA-PKCS1-v1_5 указано, что атака типа Coron–Naccache–Stern «would be impractical, requiring more operations than a collision search on the underlying hash function (i.e., more than 2^80 operations)», и что в этой схеме идентификатор хэш-функции встроен в кодирование, поэтому противнику для поиска сообщения с той же подписью нужно найти коллизии именно выбранной хэш-функции. Для EMSA-PSS отмечено, что идентификатор хэш-функции не встраивается в закодированное сообщение, и потому теоретически возможно подменить хэш-функцию.

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

Атака бьёт не по модулю, а по представителям сообщений: она ищет мультипликативные соотношения, разлагая сами представители на малые значения. Стойкость RSA сформулирована через неосуществимость вычисления корней степени e по модулю n — это другая задача, и защиту даёт именно структура кодирования.
Защита EMSA-PKCS1-v1_5 держится на том, что закодированное сообщение, преобразованное в целое, большое и отчасти «случайное». Это и предотвращает атаки типа Desmedt и Odlyzko.
Атака против EMSA-PKCS1-v1_5 требует больше операций, чем поиск коллизий хэш-функции, то есть более 2^80 операций, — поэтому она признана непрактичной, и схема сохранена ради совместимости.
Для новых приложений требуется RSASSA-PSS: рандомизация с солью даёт более плотное доказательство безопасности, а проверка извлекает соль и хэш и сверяет их с сообщением.
Подделка, рассчитанная на другой хэш или другую длину соли, при проверке не подтвердится: проверяющая сторона задаёт Hash, MGF и sLen сама, и любое расхождение даёт «inconsistent».
Переход на PSS не снимает всех рисков: его гарантия обусловлена корректностью хэша и MGF и корректным восстановлением соли при проверке, а идентификатор хэш-функции в EMSA-PSS не встраивается, поэтому рекомендуется строить MGF на той же хэш-функции.
Нельзя использовать одну пару ключей в нескольких схемах: доказательство стойкости RSASSA-PSS не учитывает, что подписи могут порождаться второй схемой.