Оптимальное асимметричное шифрование с дополнением (Khmnbgl,uky gvnbbymjncuky onsjkfguny v ;khkluyunyb)
OAEP (англ. Optimal Asymmetric Encryption Padding, Оптимальное асимметричное шифрование с дополнением) — схема дополнения, обычно используемая совместно с какой-либо односторонней функцией с потайным входом (например RSA или функции Рабина) для повышения криптостойкости последней. OAEP предложено Михиром Белларе[англ.] и Филлипом Рогавэем[англ.][1], а его применение для RSA впоследствии стандартизировано в PKCS#1 и RFC 2437.
История
[править | править код]Оригинальная версия OAEP, предложенная Белларе и Рогавэем в 1994 году заявлялась как устойчивая к атакам на основе подобранного шифротекста в сочетании с любой односторонней функции с потайным входом[1]. Дальнейшие исследования показали, что такая схема обладает устойчивостью только к атакам на основе неадаптивно подобранного шифротекста[2]. Несмотря на это, было доказано, что в модели случайных оракулов при использовании стандартного RSA с шифрующей экспонентой, схема обладает так же устойчивостью к атакам на основе адаптивно подобранного шифротекста[3]. В более новых работах было доказано, что в стандартной модели (когда хеш-функции не моделируются как случайные оракулы) невозможно доказать устойчивость к атакам на основе адаптивного шифротекста в случае использования RSA[4].
Алгоритм OAEP
[править | править код]Классическая схема OAEP представляет собой двухъячеечную сеть Фейстеля, где в каждой ячейке данные преобразуются с помощью криптографической хеш-функции. На вход сеть получает сообщение с дописанными к нему проверяющими нулями и ключ — случайную строку[5].
В схеме используются следующие обозначения:
- — число бит в подготавливаемом для асимметричного шифрования блоке.
- и — фиксированные протоколом целые числа.
- — открытый текст сообщения, -битная строка.
- и — криптографические хеш-функции, заданные протоколом.
Шифрование
[править | править код]- Сообщению дописывается нулей, благодаря чему оно достигает бит в длину.
- Генерируется случайная -битная строка .
- расширяет бит строки до бит.
- .
- ужимает бит до бит.
- .
- Зашифрованный текст .
Расшифрование
[править | править код]- Восстанавливается случайная строка
- Восстанавливается исходное сообщение как
- Последние символов расшифрованного сообщения проверяются на равенство нулю. Если имеются ненулевые символы, то сообщение подделано злоумышленником.
Применение
[править | править код]Алгоритм OAEP применяется для предварительной обработки сообщения перед использованием RSA. Сначала сообщение дополняется до фиксированной длины с помощью OAEP, затем шифруется с помощью RSA. Совместно, такая схема шифрования получила название RSA-OAEP и является частью действующего стандарта шифрования с открытым ключом (RFC 3447). Так же Виктором Бойко было доказано, что функция вида в модели случайных оракулов является преобразованием типа "все или ничего"[англ.][4].
Модификации
[править | править код]В силу таких недостатков, как невозможность доказать криптографическую стойкость к атакам на основе подобранного шифротекста, а также низкая скорость работы схемы[6], впоследствии были предложены модификации на основе OAEP, которые устраняют данные недостатки.
Алгоритм OAEP+
[править | править код]Виктор Шоуп[англ.] предложил свой вариант схемы дополнения на основе OAEP (называемый OAEP+), который является устойчивым к атакам с адаптивно подобранным шифротекстом в случае комбинирования с любой односторонней функцией с потайным входом[2].
- — число бит в подготавливаемом для асимметричного шифрования блоке.
- и — фиксированные протоколом целые числа.
- открытый текст сообщения, -битная строка.
- , и — криптографические хеш-функции, заданные протоколом.
Шифрование
[править | править код]- Генерируется случайная -битная строка .
- преобразует в строку длины .
- преобразует в строку длины .
- Составляется левая часть сообщения .
- преобразует в строку длины .
- Составляется правая часть сообщения .
- Зашифрованный текст .
Расшифрование
[править | править код]- Восстанавливается случайная строка .
- разбивается на две части и , размерами и бит соответственно.
- Восстанавливается исходное сообщение как .
- Если не выполняется , то сообщение подделано.
Алгоритм SAEP/SAEP+
[править | править код]Дэн Боне предложил две упрощённые реализации OAEP, названные SAEP и SAEP+ соответственно. Основная идея упрощения шифрования заключается в отсутствии последнего шага — сообщение «склеивалось» с изначально сгенерированной случайной строкой . Таким образом, схемы состоят только из одной ячейки Фейстеля, благодаря чему достигается прирост к скорости работы[7]. Отличием алгоритмов друг от друга выражается в записи проверяющих битов. В случае SAEP это нули, в то время как для SAEP+ — это хеш от (соответственно как у OAEP и OAEP+)[5]. Недостатком алгоритмов является сильное уменьшение длины сообщения. Надёжность схем в случае использования функции Рабина и RSA была доказана только при следующем ограничении на длину передаваемого текста: для SAEP+ и дополнительно для SAEP[8]. Стоит отметить, что при примерно одинаковой скорости работы, SAEP+ имеет меньше ограничений на длину сообщения чем SAEP[8], благодаря чему признан более предпочтительным[8].
В схеме используются следующие обозначения:
- — число бит в блоке RSA или криптосистемы Рабина.
- и — фиксированные протоколом целые числа.
- открытый текст сообщения, -битная строка.
- и — криптографические хеш-функции, заданные протоколом.
Шифрование SAEP+
[править | править код]- Генерируется случайная -битная строка .
- преобразует в строку длины .
- преобразует в строку длины .
- Вычисляется .
- Зашифрованный текст .
Дешифрование SAEP+
[править | править код]- Вычисляется , где и — строки размерами и соответственно.
- Проверяется равенство . Если равенство выполняется, то исходное сообщение , если нет — то сообщение подделано злоумышленником.
См. также
[править | править код]Примечания
[править | править код]- ↑ 1 2 Optimal Asymmetric Encryption How to Encrypt with RSA, 1995, p. 1.
- ↑ 1 2 OAEP Reconsidered, 2001, p. 1.
- ↑ RSA–OAEP is Secure under the RSA Assumption, 2001, p. 1.
- ↑ 1 2 Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption, 2006, p. 1.
- ↑ 1 2 Simplified OAEP for the RSA and Rabin functions, 2001, p. 277.
- ↑ A low-cost alternative for OAEP, 2001, p. 1.
- ↑ Simplified OAEP for the RSA and Rabin functions, 2001, p. 275.
- ↑ 1 2 3 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.