WikiSort.ru - Не сортированное

RSA-KEM (RSA Key Encapsulation Method) — однопроходный (store-and-forward) механизм шифрования ключа для передачи в криптосистемах с открытым ключом. Сочетает в себе ложные перестановки RSA и KDF (Key Derivation Function). Обладает простотой и превосходными защитными свойствами, по сравнению с OAEP или OAEP+.^{[источник не указан 1387 дней]} Основной недостаток состоит в том, что шифротекст немного больше исходного текста.

Описание

Оценка надежности

Безопасность RSA-KEM может быть проанализирована в модели случайного оракула (Random Oracle Model, далее RO)^[2]. Суть модели состоит в следующем. Предположим, что существует некая общедоступная функция обладающая такими свойствами:

1. На каждый новый аргумент функция отвечает новым значением и записывает пару (аргумент, значение) в таблицу.
2. Если аргумент уже встречался, то функция обратится к своей таблице и вернет значение, соответствующее этому аргументу.

Доказательство основано на предположении, что KDF является случайным оракулом, и что решение обратной задачи RSA невозможно (проще говоря, RSA нельзя взломать). Для любого алгоритма генерации ключа для RSA (то есть алгоритма, возвращающего n, e и d), всегда выполнено n >= nBound (то есть nBound наименьшая допустимая граница для чисел n), и для каждого злоумышленника A справедливо:

${\displaystyle Advantage_{RSA-KEM}(A)\leq Advantage_{RSA}(A')}$ + ${\displaystyle qD/nBound(*),}$

где ${\displaystyle qD}$ — это максимальное число запросов к оракулу, которое может сделать злоумышленник для попытки разгадать шифр${\displaystyle A}$ , AdvantageRSA-KEM(A) = |Pr[b*-b] - 1/2| — предсказательная способность А, AdvantageRSA(A') обозначает вероятность успешного решения инверсной задачи RSA. Нужно заметить, что приведенное выше неравенство не учитывает тот факт, что в реальности ${\displaystyle RSAKeyGen}$ с ненулевой вероятностью возвращает «плохие» ключи. Чтобы учесть его, требуется лишь прибавить эту вероятность к правой части неравенства.

Приведем доказательство, рассматривая последовательность игр ${\displaystyle G_{i}}$ , и в каждой игре противник A проводит атаку. Каждая из этих игр проходит в одном вероятностном пространстве — меняются только правила того, как рассчитываются случайные величины. В каждой игре будет событие ${\displaystyle S_{i}}$ , связанное с событием ${\displaystyle S_{0}}$ . Докажем, что разность ${\displaystyle |Pr[S_{i}]-Pr[S_{i-1}]|}$ мала, и, более того, она будет свидетельствовать о том что в последней игре ${\displaystyle Pr[S_{k}]=1/2}$ . Пусть ${\displaystyle G0}$ — первая игра, ${\displaystyle S0}$ — событие, обозначающее что ${\displaystyle A}$ правильно угадывает бит ${\displaystyle b}$ в игре ${\displaystyle G0}$ . Пусть ${\displaystyle H}$ обозначает случайное предсказание оракула, размещающее элементы ${\displaystyle Z_{n}}$ в битовые строчки длины ${\displaystyle keyLen}$ в свою таблицу. Пусть ${\displaystyle y^{*}\in Z_{n}}$ — атакуемый шифротекст, и ${\displaystyle r^{*}=(y^{*})^{1/e}\in Z_{n}}$ . Далее мы определим следующую игру ${\displaystyle G1}$ , точно такую же как игру ${\displaystyle G0}$ . Если окажется так, что оракул был вызван для дешифрования с аргументом ${\displaystyle y^{*}}$ раньше, и вызов был успешным, то игра останавливается. Пусть ${\displaystyle S1}$ — событие в игре ${\displaystyle G1}$ , соответствующее событию ${\displaystyle S0}$ . Пусть ${\displaystyle F1}$  — событие, сигнализирующее о том, что игра ${\displaystyle G1}$ была остановлена. Понятно, что

${\displaystyle Pr[F1]\leq qD/nBound,}$

и в промежуток времени, когда игры ${\displaystyle G0}$ и ${\displaystyle G1}$ проходят одинаково, а именно, до того момента как случается ${\displaystyle F1}$ , выполняется следующая лемма:

Пусть ${\displaystyle E,E'}$ и ${\displaystyle F}$ — события, определенные на пространстве случайных событий таким образом, что

${\displaystyle Pr[E}$ ${\displaystyle \land }$ ${\displaystyle \neg }$ ${\displaystyle F]=Pr[E'}$ ${\displaystyle \land }$ ${\displaystyle \neg }$ ${\displaystyle F]}$

Тогда выполняется:

${\displaystyle |Pr[E]}$ ${\displaystyle -Pr[}$ ${\displaystyle E']|}$ ${\displaystyle \leq Pr[F].}$

В нашем случае ${\displaystyle |Pr[S0]}$ ${\displaystyle -Pr[S1]|}$ ${\displaystyle \leq }$ ${\displaystyle qD/nBound.}$ Далее определим игру ${\displaystyle G2}$ , такую же как ${\displaystyle G1}$ , за исключением того, что атакуемый шифротекст генерируется в начале игры, и если противник запрашивает ${\displaystyle H}$ для ${\displaystyle r^{*}}$ , игра останавливается. Пусть ${\displaystyle S2}$ &mdash событие в ${\displaystyle G2}$ , соответствующее событию ${\displaystyle S0}$ . Очевидно, что

${\displaystyle Pr[S2]=1/2}$

в силу того, что ключ ${\displaystyle H(r^{*})}$ независим от чего-либо, доступного противнику в игре ${\displaystyle G2}$ . В этой игре ${\displaystyle H}$ в ${\displaystyle r^{*}}$ вызывается только с целью шифрования.

Пусть ${\displaystyle F2}$ — событие, сигнализирующее о том, что предыдущая игра прервалась. Понятно, что игры ${\displaystyle G1}$ и ${\displaystyle G2}$ протекают одинаково до тех пор, пока не случится ${\displaystyle F2}$ , и, следовательно, по лемме мы получим:

${\displaystyle |Pr[S1]-Pr[S2]|}$ ${\displaystyle \leq Pr[F2]}$

Потребуем, чтобы ${\displaystyle Pr[F2]\leq Advantage_{RSA}(A')}$ для алгоритма A', время работы которого ограничено временем, описанным выше. Тогда неравенство (*) будет выполнено. Алгоритм А' запускается следующим образом. Он получает на вход случайный RSA модуль ${\displaystyle n}$ , RSA экспоненту ${\displaystyle e}$ и случайный элемент ${\displaystyle y*\leq Zn}$ . A' создает открытый ключ, используя ${\displaystyle n}$ и ${\displaystyle e}$ , а затем разрешает противнику A начать игру. Когда А вызывает оракул для шифрования, А' отвечает А парой ${\displaystyle (K^{*},y^{*})}$ , где ${\displaystyle K^{*}}$ — случайный бит строки длиной ${\displaystyle keyLen}$ , а ${\displaystyle y^{*}}$ подается на вход A. Алгоритм A' симулирует случайное предсказание ${\displaystyle H}$ , как и дешифрующее RO, следующим образом. Для каждого входного ${\displaystyle r\leq Z_{n}}$ для случайного предсказания A' вычисляет ${\displaystyle y=r^{e}\in Z_{n}}$ , и размещает ${\displaystyle r}$ , ${\displaystyle y}$ и случайное значение ${\displaystyle K=H(r)}$ в таблицу. Однако, если ${\displaystyle y=y^{*}}$ А' вместо того выводит ${\displaystyle r}$ и завершается. Когда противник A предоставляет шифротекст ${\displaystyle y\in Z_{n}}$ дешифрующему предсказанию, А' ищет значение ${\displaystyle y}$ в описанной таблице, чтобы определить было ли вычислено значение случайного предсказания при ${\displaystyle r=y^{(1/e)}\in Z_{n}}$ . Если да, то А' отвечает дешифрующему предсказанию значением ${\displaystyle K=H(r)}$ , хранящемся в таблице. Иначе, алгоритм создает новый случайный ключ ${\displaystyle K}$ , и размещает пару ${\displaystyle (y,K)}$ во второй таблице. Более того, если в будущем противник А должен будет вычислить случайное предсказание при ${\displaystyle r\leq Z_{n}}$ таком что ${\displaystyle r^{e}=y}$ , то ключ ${\displaystyle K}$ , сгенерированный выше, будет использован как значение ${\displaystyle H(r)}$ . Понятно, что A' отлично симулирует А, и дает на выходе решение для данного случая RSA с вероятностью ${\displaystyle Pr[F2]}$ . Это и доказывает безопасность алгоритма. Количественно можно проверить, что RSA-KEM обеспечивает лучшую защиту по сравнению с RSA-OAEP+ и RSA-OAEP. Это преимущество выражается тем более, чем больше число сообщений, зашифрованных одним открытым ключом (замоделировано в BBM00). Это можно показать воспользовавшись тем, что решение инверсионной задачи RSA является очень трудозатратным. Таким образом безопасность RSA-KEM совсем не уменьшается с возрастанием числа зашифрованных текстов. Нужно заметить, что это утверждение справедливо только если число r в алгоритме шифрования для Simple RSA выбрано равномерно по модулю n, либо, как минимум, его распределение должно быть неотличимо от равномерного с точки зрения вычислений. Кроме прочего, RSA-KEM, в отличие от RSA-OAEP or RSA-OAEP+, нельзя назвать «хрупким» алгоритмом, то есть не найдены возможности для атак на его реализации.

Примечания

Ссылки

• V. Shoup. A Proposal for an ISO Standard for Public Key Encryption. Preprint, December 2001.
• FCD 18033-2 Encryption algorithms — Part 2: Asymmetric ciphers.
• Securing RSA-KEM via the AES
• RSA Algorithm
• The Random Oracle Methodology
• Use of the RSA-KEM Key Transport Algorithm
• AES Key Wrap Specification