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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Шифрование

[править | править код]
  1. Сообщению дописывается нулей, благодаря чему оно достигает бит в длину.
  2. Генерируется случайная -битная строка .
  3. расширяет бит строки до бит.
  4. .
  5. ужимает бит до бит.
  6. .
  7. Зашифрованный текст .

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

[править | править код]
  1. Восстанавливается случайная строка
  2. Восстанавливается исходное сообщение как
  3. Последние символов расшифрованного сообщения проверяются на равенство нулю. Если имеются ненулевые символы, то сообщение подделано злоумышленником.

Применение

[править | править код]

Алгоритм OAEP применяется для предварительной обработки сообщения перед использованием RSA. Сначала сообщение дополняется до фиксированной длины с помощью OAEP, затем шифруется с помощью RSA. Совместно, такая схема шифрования получила название RSA-OAEP и является частью действующего стандарта шифрования с открытым ключом (RFC 3447). Так же Виктором Бойко было доказано, что функция вида в модели случайных оракулов является преобразованием типа "все или ничего"[англ.][4].

Модификации

[править | править код]

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

Алгоритм OAEP+

[править | править код]

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

  •  — число бит в подготавливаемом для асимметричного шифрования блоке.
  • и  — фиксированные протоколом целые числа.
  • открытый текст сообщения, -битная строка.
  • , и  — криптографические хеш-функции, заданные протоколом.

Шифрование

[править | править код]
  1. Генерируется случайная -битная строка .
  2. преобразует в строку длины .
  3. преобразует в строку длины .
  4. Составляется левая часть сообщения .
  5. преобразует в строку длины .
  6. Составляется правая часть сообщения .
  7. Зашифрованный текст .

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

[править | править код]
  1. Восстанавливается случайная строка .
  2. разбивается на две части и , размерами и бит соответственно.
  3. Восстанавливается исходное сообщение как .
  4. Если не выполняется , то сообщение подделано.

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

[править | править код]

Дэн Боне предложил две упрощённые реализации OAEP, названные SAEP и SAEP+ соответственно. Основная идея упрощения шифрования заключается в отсутствии последнего шага — сообщение «склеивалось» с изначально сгенерированной случайной строкой . Таким образом, схемы состоят только из одной ячейки Фейстеля, благодаря чему достигается прирост к скорости работы[7]. Отличием алгоритмов друг от друга выражается в записи проверяющих битов. В случае SAEP это нули, в то время как для SAEP+ — это хеш от (соответственно как у OAEP и OAEP+)[5]. Недостатком алгоритмов является сильное уменьшение длины сообщения. Надёжность схем в случае использования функции Рабина и RSA была доказана только при следующем ограничении на длину передаваемого текста: для SAEP+ и дополнительно для SAEP[8]. Стоит отметить, что при примерно одинаковой скорости работы, SAEP+ имеет меньше ограничений на длину сообщения чем SAEP[8], благодаря чему признан более предпочтительным[8].

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

  •  — число бит в блоке RSA или криптосистемы Рабина.
  • и  — фиксированные протоколом целые числа.
  • открытый текст сообщения, -битная строка.
  • и  — криптографические хеш-функции, заданные протоколом.

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

[править | править код]
  1. Генерируется случайная -битная строка .
  2. преобразует в строку длины .
  3. преобразует в строку длины .
  4. Вычисляется .
  5. Зашифрованный текст .

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

[править | править код]
  1. Вычисляется , где и  — строки размерами и соответственно.
  2. Проверяется равенство . Если равенство выполняется, то исходное сообщение , если нет — то сообщение подделано злоумышленником.

Примечания

[править | править код]

Литература

[править | править код]