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

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

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

История

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

Алгоритм OAEP

Схема OAEP

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

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

• $n$ — число бит в блоке RSA.
• $k_{0}$ и $k_{1}$ — фиксированные протоколом целые числа.
• $m$ — открытый текст сообщения, $n-k_{0}-k_{1}$-битная строка.
• $G$ и $H$ — криптографические хеш-функции, заданные протоколом.

Шифрование

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

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

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

Модификации

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

Алгоритм OAEP+

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

• $n$ — число бит в блоке RSA.
• $k_{0}$ и $k_{1}$ — фиксированные протоколом целые числа.
• $m$ открытый текст сообщения, $n-k_{0}-k_{1}$-битная строка.
• $G$, $H$ и $H'$ — криптографические хеш-функции, заданные протоколом.

Шифрование

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

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

1. Восстанавливается случайная строка $r=Y\bigoplus H(X)$.
2. $X$ разбивается на две части $X_{1}$ и $X_{2}$, размерами $n-k_{1}-k_{0}$ и $k_{1}$ бит соответственно.
3. Восстанавливается исходное сообщение как $m=G(r)\bigoplus X_{1}$.
4. Если не выполняется $H'(r||m)=X_{2}$, то сообщение подделано.

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

предложил две упрощенные реализации OAEP, названные SAEP и SAEP+ соответственно. Основная идея упрощения шифрования заключается в отсутствии последнего шага - сообщение "склеивалось" с изначально сгенерированной случайной строкой $r$. Таким образом, схема состоит только из одной ячейки Фейстеля, благодаря чему достигается прирост к скорости работы. Недостатком алгоритма является сильное уменьшение длины сообщения. Стоит отметить, что при прочих равных, SAEP+ имеет меньше ограничений чем SAEP.

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

• $n$ — число бит в блоке RSA.
• $k_{0}$ и $k_{1}$ — фиксированные протоколом целые числа.
• $m$ открытый текст сообщения, $n-k_{0}-k_{1}$-битная строка.
• $G$ и $H$ — криптографические хеш-функции, заданные протоколом.

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

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

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

1. Вычисляется $X_{1}||X_{2}=X\bigoplus H(r)$, где $X_{1}$ и $X_{2}$ — строки размерами $n-k_{0}-k_{1}$ и $k_{0}$ соответственно.
2. Проверяется равенство $X_{2}=G(X_{1}||r)$. Если равенство выполняется, то исходное сообщение $X_{1}$, если нет — то сообщение подделано злоумышленником.

Надежность схем в случае использования функции Рабина и RSA была доказана только при серьезном ограничении на длину передаваемого текста: $m\leqslant n/2+k_{0}$ для SAEP+ и дополнительно $m\leqslant n/4$ для SAEP.

См. также

• 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.
• D. Brown. What Hashes Make RSA-OAEP Secure? (англ.). — 2006. — С. 16.
• Peter Schartner. A low-cost alternative for OAEP (англ.). — 2001. — С. 27.
• 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.