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

Схема, часто используемая с шифрованием RSA.

В криптографии оптимальное асимметричное шифрование ( OAEP ) представляет собой схему заполнения, часто используемую вместе с шифрованием RSA . OAEP был представлен Белларе и Рогавеем ^[1] и впоследствии стандартизирован в PKCS#1 v2 и RFC 2437.

Алгоритм OAEP — это разновидность сети Фейстеля , которая использует пару случайных оракулов G и H для обработки открытого текста перед асимметричным шифрованием . В сочетании с любой безопасной односторонней перестановкой с лазейкой эта обработка, как доказано в случайной модели оракула , приводит к созданию комбинированной схемы, которая семантически безопасна при атаке с выбранным открытым текстом (IND-CPA) . При реализации с некоторыми вариантами лазейки (например, RSA) OAEP также оказывается защищенным от атаки с выбранным зашифрованным текстом . OAEP можно использовать для построения преобразования «все или ничего» . ${\displaystyle f}$

OAEP преследует следующие две цели:

1. Добавьте элемент случайности, который можно использовать для преобразования детерминированной схемы шифрования (например, традиционного RSA ) в вероятностную схему.
2. Предотвратите частичную расшифровку зашифрованных текстов (или другую утечку информации), гарантируя, что злоумышленник не сможет восстановить какую-либо часть открытого текста без возможности инвертировать одностороннюю перестановку с люком . ${\displaystyle f}$

Первоначальная версия OAEP (Bellare/Rogaway, 1994) демонстрировала форму « осведомленности об открытом тексте » (которая, как они утверждали, подразумевает защиту от атак с выбранным зашифрованным текстом ) в модели случайного оракула, когда OAEP используется с любой перестановкой лазейки. Последующие результаты опровергли это утверждение, показав, что OAEP был безопасным только IND-CCA1 . Однако в модели случайного оракула было доказано , что исходная схема безопасна IND-CCA2, когда OAEP используется с перестановкой RSA с использованием стандартных показателей шифрования, как в случае RSA-OAEP. ^[2] Для решения этой проблемы Виктор Шуп предложил улучшенную схему (называемую OAEP+), которая работает с любой односторонней перестановкой с люком . ^[3] Более поздние работы показали, что в стандартной модели (то есть, когда хэш-функции не моделируются как случайные оракулы) невозможно доказать безопасность IND-CCA2 RSA-OAEP при предполагаемой сложности проблемы RSA . ^{[4] [5]}

Алгоритм

Схема кодирования OAEP согласно RFC 8017.

На диаграмме

• MGF — функция генерации маски , обычно MGF1,
• Хэш — выбранная хеш-функция ,
• hLen — длина вывода хэш-функции в байтах,
• k — длина модуля RSA n в байтах,
• M — сообщение, которое необходимо дополнить (не более байтов), ${\displaystyle k-2\cdot \mathrm {hLen} -2}$
• L — необязательная метка, связанная с сообщением (по умолчанию метка представляет собой пустую строку и может использоваться для аутентификации данных без необходимости шифрования),
• PS — это байтовая строка из нулевых байтов. ${\displaystyle k-\mathrm {mLen} -2\cdot \mathrm {hLen} -2}$
• ⊕ — это операция XOR .

Кодирование

RFC 8017 ^[6] для PKCS#1 v2.2 определяет следующую схему OAEP для кодирования:

1. Хэшируйте метку L , используя выбранную хэш-функцию: ${\displaystyle \mathrm {lHash} =\mathrm {Hash} (L)}$
2. Создайте строку заполнения PS , состоящую из байтов со значением 0x00. ${\displaystyle k-\mathrm {mLen} -2\cdot \mathrm {hLen} -2}$
3. Объедините lHash , PS , одиночный байт 0x01 и сообщение M, чтобы сформировать блок данных DB :. Этот блок данных имеет длину в байтах. ${\displaystyle \mathrm {DB} =\mathrm {lHash} ||\mathrm {PS} ||\mathrm {0x01} ||\mathrm {M} }$ ${\displaystyle k-\mathrm {hLen} -1}$
4. Сгенерируйте случайное начальное число длиной hLen .
5. Используйте функцию генерации маски, чтобы сгенерировать маску соответствующей длины для блока данных: ${\displaystyle \mathrm {dbMask} =\mathrm {MGF} (\mathrm {seed} ,k-\mathrm {hLen} -1)}$
6. Замаскируйте блок данных сгенерированной маской: ${\displaystyle \mathrm {maskedDB} =\mathrm {DB} \oplus \mathrm {dbMask} }$
7. Используйте функцию генерации маски, чтобы сгенерировать маску длины hLen для начального числа: ${\displaystyle \mathrm {seedMask} =\mathrm {MGF} (\mathrm {maskedDB} ,\mathrm {hLen} )}$
8. Замаскируйте семя сгенерированной маской: ${\displaystyle \mathrm {maskedSeed} =\mathrm {seed} \oplus \mathrm {seedMask} }$
9. Закодированное (дополненное) сообщение представляет собой байт 0x00, объединенный с MaskedSeed и MaskedDB : ${\displaystyle \mathrm {EM} =\mathrm {0x00} ||\mathrm {maskedSeed} ||\mathrm {maskedDB} }$

Декодирование

Декодирование работает путем изменения шагов, выполненных в алгоритме кодирования:

1. Хэшируйте метку L , используя выбранную хэш-функцию: ${\displaystyle \mathrm {lHash} =\mathrm {Hash} (L)}$
2. Чтобы отменить шаг 9, разделите закодированное сообщение EM на байт 0x00, MaskedSeed (длиной hLen ) и MaskedDB : ${\displaystyle \mathrm {EM} =\mathrm {0x00} ||\mathrm {maskedSeed} ||\mathrm {maskedDB} }$
3. Создайте семенную маску , которая использовалась для маскировки семени : ${\displaystyle \mathrm {seedMask} =\mathrm {MGF} (\mathrm {maskedDB} ,\mathrm {hLen} )}$
4. Чтобы отменить шаг 8, восстановите начальное число с помощью семенной маски : ${\displaystyle \mathrm {seed} =\mathrm {maskedSeed} \oplus \mathrm {seedMask} }$
5. Создайте dbMask , который использовался для маскировки блока данных: ${\displaystyle \mathrm {dbMask} =\mathrm {MGF} (\mathrm {seed} ,k-\mathrm {hLen} -1)}$
6. Чтобы отменить шаг 6, восстановите блок данных DB: ${\displaystyle \mathrm {DB} =\mathrm {maskedDB} \oplus \mathrm {dbMask} }$
7. Чтобы отменить шаг 3, разделите блок данных на части: . ${\displaystyle \mathrm {DB} =\mathrm {lHash'} ||\mathrm {PS} ||\mathrm {0x01} ||\mathrm {M} }$
   1. Подтвердите это:
      • lHash' равен вычисленному lHash
      • PS состоит только из байтов 0x00
      • PS и M разделены байтом 0x01 и
      • первый байт EM — это байт 0x00.
   2. Если какое-либо из этих условий не выполняется, заполнение недействительно.

Использование в RSA: закодированное сообщение затем можно зашифровать с помощью RSA. Детерминистическое свойство RSA теперь можно избежать при использовании кодировки OAEP, поскольку начальное число генерируется случайным образом и влияет на все закодированное сообщение.

Безопасность

Безопасность « все или ничего » заключается в том, что для восстановления C: необходимо восстановить всю базу данных и все начальное значение ; DB требуется для восстановления начального числа из Seed , а начальное число требуется для восстановления блока данных DB из DB . Поскольку любой измененный бит криптографического хеша полностью меняет результат, вся БД и все начальное число должны быть полностью восстановлены.

Выполнение

В стандарте PKCS#1 случайные оракулы идентичны. Стандарт PKCS#1 также требует, чтобы случайные оракулы были MGF1 с соответствующей хэш-функцией. ^[7]

Смотрите также

• Инкапсуляция ключей

Рекомендации

1. М. Белларе , П. Рогауэй . Оптимальное асимметричное шифрование – Как шифровать с помощью RSA . Расширенный реферат в журнале «Достижения в криптологии - Eurocrypt '94 Proceedings», конспекты лекций по информатике, том. 950, изд. А. Де Сантиса, Springer-Verlag , 1995. Полная версия (pdf)
2. Эйитиро Фудзисаки, Тацуаки Окамото, Дэвид Пойнтчеваль и Жак Стерн . RSA — OAEP безопасен в соответствии с предположением RSA . В изд. Дж. Килиана, Достижения в криптологии – CRYPTO 2001, vol. 2139 конспектов лекций по информатике, SpringerVerlag, 2001. Полная версия (pdf)
3. Виктор Шуп. Пересмотр OAEP . Исследовательская лаборатория IBM в Цюрихе, Saumerstr. 4, 8803 Рушликон, Швейцария. 18 сентября 2001 г. полная версия (pdf)
4. П. Пайе и Дж. Вильяр, Односторонняя торговля против безопасности выбранного зашифрованного текста в шифровании на основе факторинга , Достижения в криптологии - Asiacrypt 2006.
5. Д. Браун, Какие хэши обеспечивают безопасность RSA-OAEP?, IACR ePrint 2006/233.
6. «Операция шифрования». PKCS #1: Спецификации криптографии RSA, версия 2.2. IETF . Ноябрь 2016. с. 22. сек. 7.1.1. дои : 10.17487/RFC8017 . РФК 8017 . Проверено 4 июня 2022 г.
7. Браун, Дэниел Р.Л. (2006). «Какие хэши обеспечивают безопасность RSA-OAEP?» (PDF) . Архив электронной печати криптологии IACR . Проверено 3 апреля 2019 г.