OAEP

OAEP (Optimal Asymmetric Encryption Padding, оптимальное асимметричное дополнение шифрования) — это криптографическая схема дополнения (padding), используемая перед шифрованием с открытым ключом, в частности, в алгоритме RSA. Разработана для повышения безопасности асимметричного шифрования путём добавления случайных данных и проверки целостности, что предотвращает ряд атак, включая атаки по выбранному шифротексту.

История и предпосылки создания

Схема OAEP была предложена в 1994 году криптографами Михаилом Белларе и Филиппом Рогауэем. Её появление было связано с необходимостью устранения уязвимостей в базовой реализации RSA, где шифрование без дополнения (так называемый «голый» RSA) позволяло злоумышленнику легко восстанавливать открытый текст, если он был коротким или предсказуемым.

До OAEP использовались более простые схемы, такие как PKCS#1 v1.5, которая, однако, оказалась уязвимой к атаке Блехенбахера (1998 год). OAEP была разработана как более надёжная альтернатива, обеспечивающая доказуемую безопасность в модели случайного оракула. В 2001 году стандарт PKCS#1 v2.0 включил OAEP в качестве рекомендуемого метода дополнения для RSA.

Принцип работы

OAEP преобразует исходное сообщение (открытый текст) в блок данных фиксированной длины, который затем шифруется алгоритмом RSA. Схема включает два этапа: дополнение и шифрование.

Дополнение (OAEP)

Пусть:

• M — исходное сообщение длиной mLen байт.
• k — длина модуля RSA в байтах (например, для RSA-2048 это 256 байт).
• hLen — длина хеш-функции (например, для SHA-256 это 32 байта).

Процесс дополнения:

1. Формирование блока данных (DB):

• К сообщению M добавляется хеш-значение метки (по умолчанию пустой строки) — lHash (hLen байт).
• Затем добавляется один байт 0x01 и нулевые байты (0x00) до тех пор, пока длина блока не станет равной k - hLen - 1 байт.
• Если сообщение слишком длинное, дополнение невозможно — возникает ошибка.

1. Генерация маски (MGF):

• Создаётся случайное число seed длиной hLen байт.
• С помощью функции генерации маски (MGF, Mask Generation Function) из seed вычисляется маска dbMask длиной, равной длине DB.

1. Наложение маски на DB:

• maskedDB = DB XOR dbMask.

1. Наложение маски на seed:

• С помощью MGF из maskedDB вычисляется маска seedMask длиной hLen.
• maskedSeed = seed XOR seedMask.

1. Формирование итогового блока (EM):

• Итоговый блок EM состоит из одного байта 0x00, за которым следуют maskedSeed и maskedDB.

Шифрование

Полученный блок EM (длиной k байт) интерпретируется как целое число и шифруется алгоритмом RSA: C = EM^e mod n, где e — открытая экспонента, n — модуль RSA.

Расшифрование

При расшифровании:

1. Вычисляется EM = C^d mod n (где d — закрытая экспонента).
2. Извлекаются байт 0x00, maskedSeed и maskedDB.
3. Восстанавливается seed: seed = maskedSeed XOR MGF(maskedDB).
4. Восстанавливается DB: DB = maskedDB XOR MGF(seed).
5. Проверяется структура DB: наличие lHash, нулевых байтов и байта 0x01. Если проверка не пройдена — возвращается ошибка (расшифрование не удалось).

Криптографические свойства

Доказуемая безопасность

OAEP обеспечивает доказуемую безопасность в модели случайного оракула. Это означает, что если хеш-функция и MGF ведут себя как идеальные случайные функции, то взлом OAEP эквивалентен взлому RSA (то есть задаче факторизации модуля). В частности, OAEP защищает от атак по выбранному шифротексту (CCA, Chosen Ciphertext Attack) — злоумышленник не может получить информацию об открытом тексте, даже если может запрашивать расшифрование произвольных шифротекстов.

Ограничения

• Длина сообщения: Максимальная длина сообщения, которое можно зашифровать с помощью OAEP, ограничена: **mLen ≤ k - 2 * hLen - 2**. Например, для RSA-2048 и SHA-256 (hLen=32) можно зашифровать до 190 байт (256 - 64 - 2 = 190). Для длинных сообщений требуется использовать гибридное шифрование (например, RSA + AES).
• Зависимость от хеш-функции: Безопасность OAEP зависит от стойкости используемой хеш-функции. Рекомендуется использовать SHA-256 или более сильные варианты.
• Уязвимость к атакам на реализацию: Как и любой криптографический алгоритм, OAEP может быть уязвим к атакам по сторонним каналам (например, по времени выполнения) при некорректной реализации.

Применение

OAEP широко используется в современных криптографических системах:

• TLS/SSL: В протоколах защищённой передачи данных (например, TLS 1.2 и 1.3) для обмена ключами часто используется RSA с OAEP (в режиме RSA-OAEP).
• PGP/GPG: В программах шифрования электронной почты (например, GnuPG) для шифрования сессионных ключей.
• Стандарты: OAEP включён в стандарты PKCS#1 v2.0, ISO/IEC 18033-2, а также в рекомендации NIST (SP 800-56B).
• Криптографические библиотеки: Реализован в OpenSSL, Bouncy Castle, Crypto++ и других популярных библиотеках.

Сравнение с другими схемами

Критика и альтернативы

Хотя OAEP считается безопасной схемой, её применение имеет ограничения. В современных системах всё чаще используется гибридное шифрование, где RSA применяется только для шифрования короткого симметричного ключа (например, AES), а сам ключ затем используется для шифрования сообщения. Это позволяет обойти ограничение на длину сообщения.

Альтернативой OAEP является RSA-OAEP+ (модификация, предложенная в 2001 году), которая обеспечивает доказуемую безопасность без использования модели случайного оракула. Однако на практике OAEP остаётся стандартом де-факто.

Интересные факты

• Название «Optimal Asymmetric Encryption Padding» отражает цель схемы — достичь оптимальной безопасности (доказуемой) при минимальном увеличении длины шифротекста.
• В 2001 году Шай Хейл и Дэвид Пойнтчевал показали, что OAEP безопасна в модели случайного оракула, но её безопасность в реальной модели (без случайного оракула) остаётся открытым вопросом.
• Схема OAEP была разработана до появления атаки Блехенбахера (1998), но именно эта атака показала практическую необходимость в её использовании.

Источники

• Bellare, M., Rogaway, P. (1994). «Optimal Asymmetric Encryption — How to Encrypt with RSA». Advances in Cryptology — EUROCRYPT '94.
• PKCS#1 v2.0: RSA Cryptography Standard (1998, обновлён в 2001).
• NIST Special Publication 800-56B: Recommendation for Pair-Wise Key Establishment Schemes Using Integer Factorization Cryptography.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography».