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

Схема, часто используемая с шифрованием 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 — сообщение, которое необходимо дополнить, длиной mlen (максимум байт), ${\displaystyle \mathrm {mLen} =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. Сгенерируйте seedMask , который использовался для маскировки семени : ${\displaystyle \mathrm {seedMask} =\mathrm {MGF} (\mathrm {maskedDB} ,\mathrm {hLen} )}$
4. Чтобы отменить шаг 8, восстановите начальное значение с помощью seedMask : ${\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, поскольку начальное число генерируется случайным образом и влияет на все закодированное сообщение.

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

Безопасность " все или ничего " заключается в том, что для восстановления M необходимо восстановить весь maskedDB и весь maskedSeed ; maskedDB требуется для восстановления seed из maskedSeed , а seed требуется для восстановления блока данных DB из maskedDB . Поскольку любой измененный бит криптографического хеша полностью меняет результат, весь maskedDB и весь maskedSeed должны быть полностью восстановлены.

Выполнение

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

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

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

Ссылки

1. M. Bellare , P. Rogaway . Оптимальное асимметричное шифрование — как шифровать с помощью RSA . Расширенный реферат в Advances in Cryptology – Eurocrypt '94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed, Springer-Verlag , 1995. полная версия (pdf)
2. Эйитиро Фудзисаки, Тацуаки Окамото, Дэвид Пойнтшеваль и Жак Стерн . RSA-- OAEP безопасен при предположении RSA . В J. Kilian, ed., Advances in Cryptology – CRYPTO 2001, vol. 2139 of Lecture Notes in Computer Science, SpringerVerlag, 2001. полная версия (pdf)
3. Виктор Шоуп. OAEP Reconsidered . IBM Zurich Research Lab, Saumerstr. 4, 8803 Ruschlikon, Switzerland. 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. doi : 10.17487/RFC8017 . RFC 8017. Получено 04.06.2022 .
7. Браун, Дэниел Р.Л. (2006). «Какие хэши делают RSA-OAEP безопасным?» (PDF) . Архив IACR Cryptology ePrint . Получено 03.04.2019 .