Разбираем, как устроены примитивы и схемы RSA по RFC 8017 — от возведения в степень до кодирования перед подписью. Вопрос нетривиален тем, что «RSA» — это не одна операция, а семейство примитивов и схем с разными гарантиями: одни доказуемо стойкие, другие лишь предположительно, а уязвимости прячутся не в математике, а в порядке проверок и в том, как приложение сообщает об ошибках.
Что именно определено и что рекомендовано
RFC 8017 определяет две схемы шифрования: RSAES-OAEPсхема шифрования RSA, в которой перед возведением в степень к сообщению добавляется дополнение — избыточные данные, которые затем обратимо удаляются при расшифровании, чтобы шифртекст нельзя было сопоставить с открытым текстом и RSAES-PKCS1-v1_5схема шифрования RSA с дополнением по PKCS#1 версии 1.5. Для новых приложений требуется поддерживать RSAES-OAEP; RSAES-PKCS1-v1_5 включена только для совместимости с существующими приложениями.
Также определены две схемы подписи: RSASSA-PSSсхема подписи RSA с вероятностным дополнением и RSASSA-PKCS1-v1_5схема подписи RSA с дополнением по PKCS#1 версии 1.5. Совместное использование одной пары ключей RSA в разных схемах не рекомендуется для новых приложений. В частности, не рекомендуется применять одну пару и в RSASSA-PSS, и в RSASSA-PKCS1-v1_5: тогда доказательство безопасности RSASSA-PSS перестаёт быть достаточным. Не рекомендуется и совместное применение RSAES-OAEP с RSAES-PKCS1-v1_5: хотя RSAES-OAEP сам по себе атаке противостоит, противник может использовать слабость реализации RSAES-PKCS1-v1_5.
Примитивы RSA по шагам
Все схемы опираются на четыре примитива, которые различаются только назначением и именами аргументов.
RSAEP — примитив шифрованиябазовая операция возведения в степень открытым ключом. Принимает открытый ключ (n, e) — модуль и открытый показатель — и представитель сообщенияцелое число от 0 до n−1, кодирующее сообщение в виде числа для возведения в степень. Первым шагом проверяется диапазон: если m не между 0 и n−1, выводится ошибка message representative out of range и работа прекращается. Если проверка пройдена, вычисляется:
c = m^e mod nРезультат — представитель шифртекстацелое число от 0 до n−1, кодирующее шифртекст.
RSADP — обратная операция закрытым ключом. Принимает ключ K и представитель шифртекста c, целое между 0 и n−1. Сначала проверяется диапазон c: иначе ciphertext representative out of range и остановка. Дальше поведение зависит от формы ключа. Если K задан как пара (n, d), то m = c^d mod n. Если K задан как набор (p, q, dP, dQ, qInv) и, возможно, с дополнительными тройками (r_i, d_i, t_i), вычисления идут по китайской теореме об остаткахметоду ускорения: возведение в степень выполняется отдельно по каждому простому множителю модуля, а результаты объединяются, что быстрее прямого возведения по большому модулю n: сначала m_1 = c^dP mod p и m_2 = c^dQ mod q, при u > 2 — ещё m_i = c^(d_i) mod r_i для i = 3..u. Затем h = (m_1 − m_2) qInv mod p и m = m_2 + q h; при u > 2 добавляется итеративное восстановление по дополнительным простым. В конце выводится m.
Согласованность CRT-коэффициентов задаётся в определении ключа: dP и dQ — положительные целые меньше p и q, удовлетворяющие edP == 1 (mod (p−1)) и edQ == 1 (mod (q−1)); qInv — положительное целое меньше p, удовлетворяющее q*qInv == 1 (mod p).
RSASP1Примитив подписи RSA, который принимает закрытый ключ и представитель сообщения от 0 до n−1 и выдаёт представитель подписи, возвращая ошибку message representative out of range при выходе за диапазон. и RSAVP1 — примитивы подписиоперации, совпадающие с RSADP и RSAEP, но предназначенные для подписи. RSASP1 принимает закрытый ключ K и представитель сообщения m (0..n−1), выдаёт представитель подписи s (0..n−1), а при выходе m за диапазон возвращает message representative out of range. RSAVP1 принимает открытый ключ (n, e) и представитель подписи s (0..n−1), выдаёт представитель сообщения m (0..n−1), а при выходе s за диапазон возвращает signature representative out of range.
Схемы шифрования: OAEP и PKCS#1 v1.5
RSAES-OAEP-ENCRYPT
Сначала проверяются длины: если длина метки L превышает предел хеш-функции — ошибка label too long; если mLen > k − 2hLen − 2 — ошибка message too long. Здесь k — длина модуля в октетах, hLen — длина вывода хеш-функции.
Затем в EME-OAEPметоде кодирования сообщения для OAEP: если L не задана, она считается пустой строкой, и вычисляется lHash = Hash(L) длиной hLen. Генерируется строка дополнения PS из k − mLen − 2hLen − 2 нулевых октетов (может быть нулевой длины). Формируется блок данных DB = lHash || PS || 0x01 || M длиной k − hLen − 1. Генерируется случайный seed длиной hLen, и через MGF1функцию генерации маски на основе хеш-функции, которая превращает короткое случайное зерно в длинную псевдослучайную строку, чтобы замаскировать данные и сделать их неотличимыми от случайных вычисляются маски: dbMask = MGF(seed, k − hLen − 1), maskedDB = DB xor dbMask, seedMask = MGF(maskedDB, hLen), maskedSeed = seed xor seedMask. Итог — EM = 0x00 || maskedSeed || maskedDB длиной k октетов.
Метка L ассоциируется с сообщением; по умолчанию её значение — пустая строка. В этой версии PKCS #1 L — пустая строка, другие применения метки вне области документа.
RSAES-OAEP-DECRYPT
Принимает закрытый ключ K, шифртекст C длины k и необязательную метку L. Сначала проверки длин: если длина L превышает предел хеш-функции, если длина C не равна k октетам или если k < 2hLen + 2 — выводится decryption error и работа прекращается. Затем C преобразуется в целое c = OS2IP(C), применяется RSADP(K, c); если RSADP сообщает ciphertext representative out of range (c >= n), снова выводится decryption error.
Полученное m преобразуется в EM = I2OSP(m, k), после чего идёт декодирование EME-OAEP: если L не задана, берётся пустая строка, вычисляется lHash = Hash(L), EM разделяется на Y, maskedSeed длины hLen и maskedDB длины k − hLen − 1. Из maskedDB через MGF получается seedMask, из maskedSeed xor seedMask — seed, из seed через MGF — dbMask, и DB = maskedDB xor dbMask. DB разделяется как lHash' || PS || 0x01 || M; если нет октета 0x01, отделяющего PS от M, если lHash не равен lHash' или если Y ненулевой — decryption error и остановка.
Ключевое требование: противник не должен различать разные условия ошибки на этом шаге — ни по сообщению об ошибке, ни по времени, и вообще не должен узнавать частичную информацию об EM. Иначе он получит полезные сведения о расшифровке C, что ведёт к атаке с выбранным шифртекстоматаке, в которой противник подбирает шифртексты и наблюдает реакцию на их расшифровку, подобной атаке Мангера.
RSAES-PKCS1-v1_5
При шифровании первым шагом проверяется длина: если mLen > k − 11, где k — длина модуля n в октетах, операция завершается ошибкой message too long. Затем генерируется строка PS длины k − mLen − 3 из псевдослучайных ненулевых октетов, причём её длина не меньше восьми октетов, и формируется кодированное сообщение:
EM = 0x00 || 0x02 || PS || 0x00 || MДалее EM преобразуется в целое m = OS2IP(EM), применяется RSAEP с открытым ключом (n, e), и результат c преобразуется в шифртекст C = I2OSP(c, k).
При расшифровании сначала проверяется, что длина C равна k октетам и что k не меньше 11, иначе decryption error. После RSADP и преобразования EM = I2OSP(m, k) проверяется, что первый октет EM равен 0x00, второй равен 0x02, что существует октет 0x00, отделяющий PS от M, и что длина PS не меньше 8 октетов; при нарушении любого из условий — decryption error.
Почему RSAES-PKCS1-v1_5 уязвима
Можно создавать корректные шифртексты RSAES-PKCS1-v1_5, не зная соответствующих открытых текстов, с разумной вероятностью успеха. Это используется в атаке с выбором шифртекста, как показано в работе Bleichenbacher. При декодировании EME-PKCS1-v1_5 проверяется формат EM = 0x00 || 0x02 || PS || 0x00 || M, и при несоответствии выводится decryption error. Если противник может различать разные условия ошибки по сообщению или по времени, он получает полезную информацию о расшифровании C, что ведёт к усиленной версии атаки Bleichenbacher.
RFC 8017 рекомендует легко реализуемые контрмеры: добавление структуры к кодируемым данным, строгую проверку соответствия PKCS #1 v1.5 (и другой избыточности) в расшифрованных сообщениях и объединение сообщений об ошибках в клиент-серверном протоколе на основе PKCS #1 v1.5. Отдельно указано: нужно следить, чтобы противник не различал условия ошибки — ни по сообщению, ни по времени.
Схемы подписи: PSS и PKCS#1 v1.5
EMSA-PSS-ENCODE
Параметризуется выбором хеш-функции, функции генерации маски и длины соли. Принимает сообщение M и максимальную битовую длину emBits — не менее 8hLen + 8sLen + 9.
Сначала проверяется, что длина M не превышает ограничение хеша (иначе message too long), затем вычисляется mHash = Hash(M) длиной hLen. Если emLen = ceil(emBits/8) меньше hLen + sLen + 2 — ошибка encoding error. Генерируется случайная соль длины sLen (при sLen = 0 — пустая строка), и формируется M' = восемь нулевых октетов || mHash || salt длиной 8 + hLen + sLen. Затем H = Hash(M'), и DB = PS || 0x01 || salt, где PS — строка нулей длины emLen − sLen − hLen − 2 (может быть нулевой). Маска dbMask = MGF(H, emLen − hLen − 1), maskedDB = DB xor dbMask, после чего левые 8*emLen − emBits бит самого левого октета maskedDB обнуляются. Итоговое закодированное сообщение имеет вид:
EM = maskedDB || H || 0xbcТипичные длины соли в октетах — hLen и 0.
EMSA-PSS-VERIFY
Принимает M, EM длины emLen = ceil(emBits/8) и emBits, возвращает consistent или inconsistent. Если длина M превышает предел хеш-функции — сразу inconsistent. Вычисляется mHash = Hash(M). Если emLen < hLen + sLen + 2 — inconsistent. Если самый правый октет EM не равен 0xbc — inconsistent.
Из EM выделяются maskedDB (левые emLen − hLen − 1 октетов) и H (следующие hLen октетов); проверяется, что левые 8emLen − emBits бит самого левого октета maskedDB равны нулю. Затем dbMask = MGF(H, emLen − hLen − 1), DB = maskedDB xor dbMask, и левые 8emLen − emBits бит самого левого октета DB обнуляются. Проверяется, что левые emLen − hLen − sLen − 2 октетов DB равны нулю, а октет на позиции emLen − hLen − sLen − 1 равен 0x01 — иначе inconsistent. Соль берётся как последние sLen октетов DB. Наконец, вычисляется H' = Hash(M') для M' = восемь нулевых октетов || mHash || salt; если H = H' — consistent, иначе inconsistent.
EMSA-PKCS1-v1_5
Формирует значение из фиксированного префикса для выбранной хеш-функции и хеш-значения H. Для девяти хеш-функций (MD2, MD5, SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256) заданы точные байтовые префиксы. Например, для SHA-256 префикс равен 30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20, после которого идёт H. Каждый префикс включает OID хеш-функции, параметр NULL и длину хеш-значения. Схема детерминирована, потому что хеш-функции детерминированы: выход полностью определяется входом. Поэтому проверка может просто повторить кодирование и сравнить результат с ранее полученным закодированным сообщением.
Почему PSS предпочтительнее
RSASSA-PSS использует рандомизированную схему кодирования EMSA-PSS с солью — случайным значением, добавляемым к хешу сообщения. Это делает подпись вероятностной и обеспечивает доказуемую стойкость: сложность подделки подписи напрямую связывается со сложностью инвертирования RSA-функции. При проверке извлекаются соль и хеш, и проверяющий убеждается, что хеш, соль и сообщение согласованы.
RSASSA-PKCS1-v1_5 использует детерминированное кодирование EMSA-PKCS1-v1_5способ подготовки сообщения к подписи, при котором к хешу добавляется фиксированный префикс, и его стойкость лишь предполагается. В EMSA-PKCS1-v1_5 идентификатор хеш-функции встроен в кодированное сообщение, что вынуждает противника искать коллизии именно выбранной хеш-функции, но доказуемой стойкости это не даёт. Рекомендуется постепенный переход от EMSA-PKCS1-v1_5 к EMSA-PSS как предосторожность против будущих разработок.
MGF1 и хеш-функции
MGF1 принимает seed mgfSeed и желаемую длину маски maskLen в октетах. Если maskLen > 2^32 hLen, выводится mask too long и работа прекращается. Затем T инициализируется пустой строкой, и для counter от 0 до ceil(maskLen / hLen) − 1 выполняется цикл: counter преобразуется в 4-октетную строку C = I2OSP(counter, 4), после чего к T присоединяется Hash(mgfSeed || C). В конце выводятся первые maskLen октетов T.
RFC 8017 перечисляет девять хеш-функций: MD2, MD5, SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 и SHA-512/256. MD2 и MD5 объявлены криптографически небезопасными и должны быть удалены из существующих приложений; эта версия стандарта поддерживает их только для обратной совместимости. Для новых приложений рекомендованы только SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 и SHA-512/256. MD2, MD5 и SHA-1 рекомендованы только для совместимости с существующими приложениями на основе PKCS #1 v1.5. Для RSAES-OAEP и EMSA-PSS рекомендованы SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 и SHA-512/256. Для EMSA-PKCS1-v1_5 рекомендованы SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 и SHA-512/256.
Форматы ключей и ASN.1
RSAPublicKey — ASN.1 SEQUENCE из двух обязательных INTEGER: modulus (модуль n) и publicExponent (открытая экспонента e).
RSAPrivateKey — SEQUENCE, где обязательны version, modulus, publicExponent, privateExponent, prime1, prime2 и coefficient, а otherPrimeInfos помечен OPTIONAL. version — INTEGER с именованными значениями two-prime(0) и multi(1); он должен быть 0, если multi-prime не используется, и 1 при multi-prime. coefficient — обратный элемент q по модулю p. otherPrimeInfos содержит сведения о дополнительных простых r_3, ..., r_u по порядку; он должен быть опущен при version 0 и содержать минимум один OtherPrimeInfo при version 1. Каждый OtherPrimeInfo — SEQUENCE из prime (простой множитель r_i, i >= 3), exponent (d_i = d mod (r_i − 1)) и coefficient (CRT-коэффициент t_i = (r_1 r_2 ... * r_(i−1))^(−1) mod r_i).
OID и параметры AlgorithmIdentifier:
| Схема | OID | Параметры |
|---|---|---|
| rsaEncryption (RSAES-PKCS1-v1_5) | { pkcs-1 1 } | NULL |
| id-RSAES-OAEP | { pkcs-1 7 } | RSAES-OAEP-params |
| id-RSASSA-PSS | { pkcs-1 10 } | RSASSA-PSS-params |
Для схем подписи PKCS#1 v1.5 OID выбирается по хеш-алгоритму: md2WithRSAEncryption {pkcs-1 2}, md5WithRSAEncryption {pkcs-1 4}, sha1WithRSAEncryption {pkcs-1 5}, sha224WithRSAEncryption {pkcs-1 14}, sha256WithRSAEncryption {pkcs-1 11}, sha384WithRSAEncryption {pkcs-1 12}, sha512WithRSAEncryption {pkcs-1 13}, sha512-224WithRSAEncryption {pkcs-1 15}, sha512-256WithRSAEncryption {pkcs-1 16}. Для каждого из них параметры AlgorithmIdentifier обязаны быть NULL.
Что из этого следует на практике
- Схема — не примитив. RSAEP/RSADP/RSASP1/RSAVP1 различаются только назначением и именами аргументов; вся защита от атак лежит в кодировании перед примитивом и в порядке проверок при декодировании. Слабость реализации RSAES-PKCS1-v1_5 может подорвать RSAES-OAEP при общей паре ключей.
- Ошибки расшифрования нельзя различать. И для OAEP, и для PKCS#1 v1.5 RFC прямо требует, чтобы противник не отличал условия ошибки ни по сообщению, ни по времени. Иначе — атака с выбранным шифртекстом (Мангер для OAEP, усиленная Bleichenbacher для v1.5).
- PSS даёт доказуемую стойкость, v1.5 — предположительную. Рандомизация солью в PSS связывает сложность подделки со сложностью инвертирования RSA; в v1.5 такой гарантии нет, и RFC рекомендует постепенный переход.
- MD2 и MD5 непригодны. Они объявлены криптографически небезопасными и должны быть удалены; для новых приложений рекомендованы только SHA-2 семейства.
- Одна пара ключей — одна схема. Совместное использование пары в PSS и v1.5 или в OAEP и v1.5 не рекомендуется: доказательства безопасности перестают работать.
- Детерминированность v1.5 упрощает проверку. Поскольку кодирование детерминировано, верификация может повторить кодирование и сравнить результат — но это же свойство не даёт PSS-подобных гарантий.
