OAEP ( англ. O ptimal A symmetric E ncryption P adding , Оптимальное асимметричное шифрование с дополнением) — схема дополнения , обычно используемая совместно с какой-либо односторонней функцией с потайным входом (например RSA или функции Рабина ) для повышения криптостойкости последней. OAEP предложено и , а его применение для RSA впоследствии стандартизировано в PKCS#1 и .

История

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

Алгоритм OAEP

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

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

• ${\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 и является частью действующего стандарта шифрования с открытым ключом ( ). Так же Виктором Бойко было доказано, что функция вида ${\displaystyle g^{G,H}(x)=f(OAEP^{G,H}(x,r))}$ в модели случайных оракулов является .

Модификации

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

Алгоритм OAEP+

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

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

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

• ${\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

Примечания

Литература

• M. Bellare, P. Rogaway. (англ.) . — Springer Berlin Heidelberg, 1995. — Vol. 950. — P. 92—111. — ISBN 978-3-540-60176-0 . — ISSN . — doi : .
• Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern. (англ.) . — Springer Berlin Heidelberg, 2001. — Vol. 2139. — P. 260—274. — ISBN 978-3-540-42456-7 . — ISSN . — doi : .
• P. Paillier and J. Villar. (англ.) . — Springer Berlin Heidelberg, 2006. — Vol. 4284. — P. 252—266. — ISBN 978-3-540-49475-1 . — ISSN . — doi : .
• Peter Schartner. (англ.) . — 2001. — ISBN 978-1-4503-0882-3 . — doi : .
• Victor Shoup. (англ.) . — Springer Berlin Heidelberg, 2001. — Vol. 2139. — P. 239—259. — ISBN 978-3-540-42456-7 . — ISSN . — doi : .
• D. Boneh. (англ.) . — Springer Berlin Heidelberg, 2001. — Vol. 2139. — P. 275—291. — ISBN 978-3-540-42456-7 . — ISSN . — doi : .
• Victor Boyko. (англ.) . — Springer Berlin Heidelberg, 1999. — Vol. 1666. — P. 503—518. — ISBN 978-3-540-66347-8 . — ISSN . — doi : .