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

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

История

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

Алгоритм OAEP

Схема OAEP

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

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

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

Шифрование

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

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

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

Применение

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

Модификации

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

Алгоритм OAEP+

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

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

Шифрование

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

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

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

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

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

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

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

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

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

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

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

См. также

• RSA-KEM

Примечания

1. Optimal Asymmetric Encryption How to Encrypt with RSA, 1995, p. 1.
2. OAEP Reconsidered, 2001, p. 1.
3. RSA–OAEP is Secure under the RSA Assumption, 2001, p. 1.
4. Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption, 2006, p. 1.
5. Simplified OAEP for the RSA and Rabin functions, 2001, p. 277.
6. A low-cost alternative for OAEP, 2001, p. 1.
7. Simplified OAEP for the RSA and Rabin functions, 2001, p. 275.
8. Simplified OAEP for the RSA and Rabin functions, 2001, p. 290.

Литература

• 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.