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

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

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

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

Добавьте элемент случайности, который можно использовать для преобразования детерминированной схемы шифрования (например, традиционного RSA ) в вероятностную схему.
Предотвратите частичную расшифровку зашифрованных текстов (или другую утечку информации), гарантируя, что злоумышленник не сможет восстановить какую-либо часть открытого текста без возможности инвертировать одностороннюю перестановку с люком. $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 ]}

Алгоритм

На диаграмме

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

Кодирование

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

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

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

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

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

Выполнение

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

См. также

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

Ссылки

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

[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 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]