Оптимальное асимметричное шифрование с дополнением

OAEP (англ. Optimal Asymmetric Encryption Padding, Оптимальное асимметричное шифрование с дополнением) — схема дополнения, обычно используемая совместно с какой-либо односторонней функцией с потайным входом (например RSA или функции Рабина) для повышения криптостойкости последней. OAEP предложено Михиром Белларе и Филлипом Рогавэем, а его применение для RSA впоследствии стандартизировано в PKCS#1 и RFC 2437.

История

Оригинальная версия OAEP, предложенная Белларе и Рогавэем в 1994 году заявлялась как устойчивая к атакам на основе подобранного шифротекста в сочетании с любой односторонней функции с потайным входом. Дальнейшие исследования показали, что такая схема обладает устойчивостью только к атакам на основе неадаптивно подобранного шифротекста. Несмотря на это, было доказано, что в модели случайных оракулов при использовании стандартного RSA с шифрующей экспонентой, схема обладает так же устойчивостью к атакам на основе адаптивно подобранного шифротекста. В более новых работах было доказано, что в стандартной модели (когда хеш-функции не моделируются как случайные оракулы) невозможно доказать устойчивость к атакам на основе адаптивного шифротекста в случае использования RSA.

Алгоритм OAEP

Схема OAEP

Классическая схема OAEP представляет собой двухъячеечную сеть Фейстеля, где в каждой ячейке данные преобразуются с помощью криптографической хеш-функции. На вход сеть получает сообщение с дописанными к нему проверяющими нулями и ключ — случайную строку.

В схеме используются следующие обозначения:

• [math]\displaystyle{ n }[/math] — число бит в подготавливаемом для асимметричного шифрования блоке.
• [math]\displaystyle{ k_0 }[/math] и [math]\displaystyle{ k_1 }[/math] — фиксированные протоколом целые числа.
• [math]\displaystyle{ m }[/math] — открытый текст сообщения, [math]\displaystyle{ n - k_0 - k_1 }[/math]-битная строка.
• [math]\displaystyle{ G }[/math] и [math]\displaystyle{ H }[/math] — криптографические хеш-функции, заданные протоколом.

Шифрование

1. Сообщению [math]\displaystyle{ m }[/math] дописывается [math]\displaystyle{ k_1 }[/math] нулей, благодаря чему оно достигает [math]\displaystyle{ n - k_0 }[/math] бит в длину.
2. Генерируется случайная [math]\displaystyle{ k_0 }[/math]-битная строка [math]\displaystyle{ r }[/math].
3. [math]\displaystyle{ G }[/math] расширяет [math]\displaystyle{ k_0 }[/math] бит строки [math]\displaystyle{ r }[/math] до [math]\displaystyle{ n - k_0 }[/math] бит.
4. [math]\displaystyle{ X = m00..0 \bigoplus G(r) }[/math].
5. [math]\displaystyle{ H }[/math] ужимает [math]\displaystyle{ n - k_0 }[/math] бит [math]\displaystyle{ X }[/math] до [math]\displaystyle{ k_0 }[/math] бит.
6. [math]\displaystyle{ Y = r \bigoplus H(X) }[/math].
7. Зашифрованный текст [math]\displaystyle{ X || Y }[/math].

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

1. Восстанавливается случайная строка [math]\displaystyle{ r = Y \bigoplus H(X) }[/math]
2. Восстанавливается исходное сообщение как [math]\displaystyle{ m00..0 = X \bigoplus G(r) }[/math]
3. Последние [math]\displaystyle{ k_1 }[/math] символов расшифрованного сообщения проверяются на равенство нулю. Если имеются ненулевые символы, то сообщение подделано злоумышленником.

Применение

Алгоритм OAEP применяется для предварительной обработки сообщения перед использованием RSA. Сначала сообщение дополняется до фиксированной длины с помощью OAEP, затем шифруется с помощью RSA. Совместно, такая схема шифрования получила название RSA-OAEP и является частью действующего стандарта шифрования с открытым ключом (RFC 3447). Так же Виктором Бойко было доказано, что функция вида [math]\displaystyle{ g^{G,H}(x) = f(OAEP^{G,H}(x, r)) }[/math] в модели случайных оракулов является преобразованием типа "все или ничего".

Модификации

В силу таких недостатков, как невозможность доказать криптографическую стойкость к атакам на основе подобранного шифротекста, а также низкая скорость работы схемы, впоследствии были предложены модификации на основе OAEP, которые устраняют данные недостатки.

Алгоритм OAEP+

Виктор Шоуп предложил свой вариант схемы дополнения на основе OAEP (называемый OAEP+), который является устойчивым к атакам с адаптивно подобранным шифротекстом в случае комбинирования с любой односторонней функцией с потайным входом.

• [math]\displaystyle{ n }[/math] — число бит в подготавливаемом для асимметричного шифрования блоке.
• [math]\displaystyle{ k_0 }[/math] и [math]\displaystyle{ k_1 }[/math] — фиксированные протоколом целые числа.
• [math]\displaystyle{ m }[/math] открытый текст сообщения, [math]\displaystyle{ n - k_0 - k_1 }[/math]-битная строка.
• [math]\displaystyle{ G }[/math], [math]\displaystyle{ H }[/math] и [math]\displaystyle{ H' }[/math] — криптографические хеш-функции, заданные протоколом.

Шифрование

1. Генерируется случайная [math]\displaystyle{ k_0 }[/math]-битная строка [math]\displaystyle{ r }[/math].
2. [math]\displaystyle{ H' }[/math] преобразует [math]\displaystyle{ r || m }[/math] в строку длины [math]\displaystyle{ k_1 }[/math].
3. [math]\displaystyle{ G }[/math] преобразует [math]\displaystyle{ r }[/math] в строку длины [math]\displaystyle{ n - k_0 - k_1 }[/math].
4. Составляется левая часть сообщения [math]\displaystyle{ X = (G(r) \bigoplus m) || H'(r || m) }[/math].
5. [math]\displaystyle{ H }[/math] преобразует [math]\displaystyle{ X }[/math] в строку длины [math]\displaystyle{ k_0 }[/math].
6. Составляется правая часть сообщения [math]\displaystyle{ Y = H(X) \bigoplus r }[/math].
7. Зашифрованный текст [math]\displaystyle{ X || Y }[/math].

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

1. Восстанавливается случайная строка [math]\displaystyle{ r = Y \bigoplus H(X) }[/math].
2. [math]\displaystyle{ X }[/math] разбивается на две части [math]\displaystyle{ X_1 }[/math] и [math]\displaystyle{ X_2 }[/math], размерами [math]\displaystyle{ n - k_1 - k_0 }[/math] и [math]\displaystyle{ k_1 }[/math] бит соответственно.
3. Восстанавливается исходное сообщение как [math]\displaystyle{ m = G(r) \bigoplus X_1 }[/math].
4. Если не выполняется [math]\displaystyle{ H'(r||m) = X_2 }[/math], то сообщение подделано.

Алгоритм SAEP/SAEP+

Дэн Боне предложил две упрощённые реализации OAEP, названные SAEP и SAEP+ соответственно. Основная идея упрощения шифрования заключается в отсутствии последнего шага — сообщение «склеивалось» с изначально сгенерированной случайной строкой [math]\displaystyle{ r }[/math]. Таким образом, схемы состоят только из одной ячейки Фейстеля, благодаря чему достигается прирост к скорости работы. Отличием алгоритмов друг от друга выражается в записи проверяющих битов. В случае SAEP это нули, в то время как для SAEP+ — это хеш от [math]\displaystyle{ m || r }[/math] (соответственно как у OAEP и OAEP+). Недостатком алгоритмов является сильное уменьшение длины сообщения. Надёжность схем в случае использования функции Рабина и RSA была доказана только при следующем ограничении на длину передаваемого текста: [math]\displaystyle{ m \leqslant n/2 + k_0 }[/math] для SAEP+ и дополнительно [math]\displaystyle{ m \leqslant n/4 }[/math] для SAEP. Стоит отметить, что при примерно одинаковой скорости работы, SAEP+ имеет меньше ограничений на длину сообщения чем SAEP, благодаря чему признан более предпочтительным.

В схеме используются следующие обозначения:

• [math]\displaystyle{ n }[/math] — число бит в блоке RSA или криптосистемы Рабина.
• [math]\displaystyle{ k_0 }[/math] и [math]\displaystyle{ k_1 }[/math] — фиксированные протоколом целые числа.
• [math]\displaystyle{ m }[/math] открытый текст сообщения, [math]\displaystyle{ n - k_0 - k_1 }[/math]-битная строка.
• [math]\displaystyle{ G }[/math] и [math]\displaystyle{ H }[/math] — криптографические хеш-функции, заданные протоколом.

Шифрование SAEP+

1. Генерируется случайная [math]\displaystyle{ k_0 }[/math]-битная строка [math]\displaystyle{ r }[/math].
2. [math]\displaystyle{ G }[/math] преобразует [math]\displaystyle{ m || r }[/math] в строку длины [math]\displaystyle{ k_1 }[/math].
3. [math]\displaystyle{ H }[/math] преобразует [math]\displaystyle{ r }[/math] в строку длины [math]\displaystyle{ n - k_0 }[/math].
4. Вычисляется [math]\displaystyle{ X = ( m || G(m || r) ) \bigoplus H(r) }[/math].
5. Зашифрованный текст [math]\displaystyle{ X || r }[/math].

Дешифрование SAEP+

1. Вычисляется [math]\displaystyle{ X_1 || X_2 = X \bigoplus H(r) }[/math], где [math]\displaystyle{ X_1 }[/math] и [math]\displaystyle{ X_2 }[/math] — строки размерами [math]\displaystyle{ n - k_0 - k_1 }[/math] и [math]\displaystyle{ k_0 }[/math] соответственно.
2. Проверяется равенство [math]\displaystyle{ X_2 = G(X_1 || r) }[/math]. Если равенство выполняется, то исходное сообщение [math]\displaystyle{ X_1 }[/math], если нет — то сообщение подделано злоумышленником.

См. также

• RSA-KEM

Литература

• M. Bellare, P. Rogaway. Optimal Asymmetric Encryption -- How to Encrypt with RSA (англ.). — Springer Berlin Heidelberg, 1995. — Vol. 950. — P. 92—111. — ISBN 978-3-540-60176-0. — ISSN 0302-9743. — doi:10.1007/BFb0053428.
• Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern. RSA–OAEP is Secure under the RSA Assumption (англ.). — Springer Berlin Heidelberg, 2001. — Vol. 2139. — P. 260—274. — ISBN 978-3-540-42456-7. — ISSN 0302-9743. — doi:10.1007/3-540-44647-8_16.
• P. Paillier and J. Villar. Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption (англ.). — Springer Berlin Heidelberg, 2006. — Vol. 4284. — P. 252—266. — ISBN 978-3-540-49475-1. — ISSN 0302-9743. — doi:10.1007/11935230_17.
• Peter Schartner. A low-cost alternative for OAEP (англ.). — 2001. — ISBN 978-1-4503-0882-3. — doi:10.1145/2349913.2349914.
• Victor Shoup. OAEP Reconsidered (англ.). — Springer Berlin Heidelberg, 2001. — Vol. 2139. — P. 239—259. — ISBN 978-3-540-42456-7. — ISSN 0302-9743. — doi:10.1007/3-540-44647-8_15.
• D. Boneh. Simplified OAEP for the RSA and Rabin functions (англ.). — Springer Berlin Heidelberg, 2001. — Vol. 2139. — P. 275—291. — ISBN 978-3-540-42456-7. — ISSN 0302-9743. — doi:10.1007/3-540-44647-8_17.
• Victor Boyko. On the Security Properties of OAEP as an All-or-Nothing Transform (англ.). — Springer Berlin Heidelberg, 1999. — Vol. 1666. — P. 503—518. — ISBN 978-3-540-66347-8. — ISSN 0302-9743. — doi:10.1007/3-540-48405-1_32.