RSA-KEM

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

ОписаниеПравить

ВведениеПравить

RSA-KEM относится к классу криптографических методов инкапсуляции ключа, спроектированных для безопасной отправки симметричных ключей шифрования с использованием алгоритмов на открытых ключах. На практике, системы шифрования на основе открытых ключей неудобны для передачи длинных сообщений, вместо этого они используются для обмена симметричными ключами, которыми в итоге шифруется текст. Традиционным подходом к отправке симметричного ключа с помощью систем на открытых ключах является следующий алгоритм:

1. Генерация случайного числа.
2. Шифрование числа выбранным открытым ключом. Это зашифрованное сообщение отправляется получателю.
3. Получатель расшифровывает его закрытым ключом и восстанавливает симметричный ключ.

Представленный алгоритм имеет несколько недостатков. Во-первых, так как симметричный ключ мал, требуется его удлинение, а доказательство безопасности удлинения ключа не является строгим. Во-вторых, злоумышленник может отправить своё число, зашифрованное открытым ключом, и обмениваться сообщениями с получателем. В-третьих, не отслеживается целостность данных (обобщение второго пункта). Кроме того, шифры схожих сообщений могут быть похожими. Очевидно, что представленная схема недостаточно хороша и надёжна.

Метод инкапсуляции ключа демонстрирует иной, более продвинутый подход, решающий выявленные проблемы.

Процесс шифрования можно коротко представить следующим образом:

1. Генерируется случайное входное w.
2. Шифруется w с использованием RSA для передачи принимающему.
3. Генерируется материал ключа y = KDF(w) для использования в последующем шифровании.

Принимающий может восстановить w из принятого шифртекста и затем сгенерировать y, чтоб и отправитель и принимающий могли согласиться с одинаковым симметричным ключом.

ПараметрыПравить

Механизм шифрования ключа имеет следующие системные параметры:

1. RSAKeyGen: алгоритм генерации ключа RSA.
2. KDF: A key derivation function.
3. KeyLen: положительное целое число.

Генерация ключаПравить

Открытый ключ состоит из RSA коэффициента $n$$n$ , который является произведением двух больших простых чисел и экспоненты $e$$e$ , где $gcd(e,\mathrm{\varphi <!--\; \varphi \; -->}(n))=1$$gcd(e,\phi (n))=1$  ($gcd$$gcd$  — наибольший общий делитель). Это так же выделяет key derivation function KDF. Пусть nLen обозначает длину n в байтах. Секретный ключ состоит из дешифровой экспоненты d, где $ed=1mod\mathrm{\varphi <!--\; \varphi \; -->}(n)$$ed=1mod\phi (n)$ . Алгоритм генерации ключа ничего не принимает на вход и выполняется следующим образом:

1. Вычисление (n, e, d) = RSAKeyGen().
2. Получение открытого ключа PK (public key).
3. Получение закрытого ключа pk (private key).

n, e, d — целые положительные числа.

ШифрованиеПравить

Целью алгоритма шифрования является произвести псевдослучайный ключ K длины KeyLen и шифротекст $C_0$$C_{0}$ , который шифрует K. Алгоритм шифрования принимает следующее:

1. открытый ключ, состоящий из целого положительного n и e.
2. нет опций шифрования.

Выполняется следующим образом:

1) Генерируется случайное число $z\in <!--\; \in \; -->[\mathrm{0..}n)$$z\in [0..n)$ .

2) Шифруется $z$$z$  открытым ключом получателя $(n,e)$$(n,e)$ 

$c=z^{e}modn$$c=z^{e}modn$ 

3) Число $c$$c$  преобразуется в шифрованную строку $C$$C$ , а $z$$z$  в строчку $Z$$Z$ 

$C=intToStr(c,nLen),$$C=intToStr(c,nLen),$ 

$Z=intToStr(z,nLen)$$Z=intToStr(z,nLen)$ 

4) Создаётся так называемый key-encrypting key(KEK), длиной $kekLen$$kekLen$ , с использованием Key Derivation Function(KDF):

$KEK=KDF(z,kekLen)$$KEK=KDF(z,kekLen)$ 

5) Передаваемая информация оборачивается (в англ. литературе WRAP) ключом KEK, с использованием key-wrapping схемы. На выходе получим шифорованный текст $WK$$WK$ 

$WK=Wrap(KEK,K)$$WK=Wrap(KEK,K)$ 

6) Объединяем $C$$C$  и зашифрованный текст

$EK=C||WK$$EK=C||WK$ 

$EK$$EK$  является выходом алгоритма

Функция производства ключа (KDF)Править

KDF принимает на вход байтовую строчку и целое число $L>0$$L>0$ . Например, функция KDF1. Она параметризуется некоторой хеш функцией и определяется следующим образом: на вход идут аргументы $(Z,L)$$(Z,L)$ , на выходе получаем первые $L$$L$  байт выражения:

$Hash(Z$$Hash(Z$  || $I2OSP(0,4))$$I2OSP(0,4))$ || ... || $Hash$$Hash$ $(Z$$(Z$ ||$I2OSP(k-<!--\; -\; -->1,$$I2OSP(k-1,$  $4)),$$4)),$ 

где $k=L/Hash.outputLen.$$k=L/Hash.outputLen.$ 

"Близнецом" функции KDF1 является KDF2. Она отличается от KDF1 лишь тем, что счётчик проходит от $1$$1$  до $k$$k$ , а не от $0$$0$  до $k-<!--\; -\; -->1$$k-1$ . Однако для этих функций трудно установить, насколько "хорошими" генераторами псевдослучайных чисел они являются. В связи с этой потенциальной уязвимостью желательно использовать функцию KDF3, например. Она принимает в качестве параметров Hash и $padding⩾<!--\; ⩾\; -->4.$$padding\geqslant 4.$  На выход идут первые $L$$L$  байт выражения:

$Hash(I2OSP(0,padding)$$Hash(I2OSP(0,padding)$  || $Z)$$Z)$  || · · · || $Hash(I2OSP(k-<!--\; -\; -->1$$Hash(I2OSP(k-1$ , $padding)$$padding)$  || $Z),$$Z),$ 

где $k=L/Hash.outputLen$$k=L/Hash.outputLen$ .

Рекомендуемые хеш-функции SHA1 и RIPMD-160. Рекомендуемый $padding=4$$padding=4$ . О надёжности KDF3 уже можно судить достаточно уверенно. Функция $I2OSP$$I2OSP$  описанная в стандарте IEEE P1363, преобразует число в строку. Её работа основана на функции $OS2IP$$OS2IP$ , которая наоборот, из строки получает число.

Схема обертки ключа (Key Wrapping Schema)Править

Спецификация RFC 5990 требует, чтобы в качестве схемы обертки использовалась одна из следующих:

1. AES Key Wrap
2. Triple-DES Key Wrap
3. Camillia Key Wrap

Наиболее распространена схема обертки AES. Она оперирует блоками по 64 бита и требует на вход сообщение длиной более одного такого блока. Если длина сообщения 64бита или меньше, постоянная определённая спецификацией и ключевая информация формируют единственный 128-битный блок, обертывание которого бессмысленно.

ДешифрованиеПравить

Алгоритм дешифрования принимает на вход следующее:

1. закрытый ключ, состоящий из целого положительного n и d.
2. шифротекст $C_0$$C_{0}$ .

Выполняется следующим образом:

1. Разделение зашифрованной информации о ключе $EK$$EK$  на шифротекст $C$$C$  длины $nLen$$nLen$  байт и обернутую информацию о ключе:
   
   $C||WK=EK$$C||WK=EK$ 
   
   Если длина зашифрованной информации о ключе отличается от $nLen$$nLen$ , то дешифрование прекращается с ошибкой.
2. Преобразование шифротекста $C$$C$  в целое число $c$$c$  и его расшифровка с использованием закрытого ключа принимающего:
   
   $c=StrToInt(C)$$c=StrToInt(C)$ 
   $z=c^{d}modn$$z=c^{d}modn$ 
   
   Если $c$$c$  не находится в пределах $0⩽<!--\; ⩽\; -->c⩽<!--\; ⩽\; -->n-<!--\; -\; -->1$$0\leqslant c\leqslant n-1$ , то дешифрование прекращается с ошибкой.
3. Преобразование целого $z$$z$  в байтовую строку $Z$$Z$  длины $nLen.$$nLen.$ 
   
   $Z=IntToStr(z,nLen)$$Z=IntToStr(z,nLen)$ 
   
   
4. Создание $KEK$$KEK$  длины $kekLen$$kekLen$  байт из строки $Z$$Z$  при помощи KDF:
   
   $KEK=KDF(Z,kekLen)$$KEK=KDF(Z,kekLen)$ 
   
   
5. Разворачивание информации о ключе $WK$$WK$  при помощи $KEK$$KEK$ :
   
   $K=Unwrap(KEK,WK)$$K=Unwrap(KEK,WK)$ 
   
   Если операция разворачивания прекращается с ошибкой, выполнение всего алгоритма прекращается с ошибкой.
6. Получение $K$$K$  на выходе алгоритма.

Оценка надёжностиПравить

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

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

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

$Advantag{e}_{RSA-<!--\; -\; -->KEM}(A)\le <!--\; \le \; -->Advantag{e}_{RSA}(A^{\prime })$$Advantage_{RSA-KEM}(A)\leq Advantage_{RSA}(A')$  + $qD/nBound(\ast <!--\; \ast \; -->),$$qD/nBound(*),$ 

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

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

$Pr[F1]\le <!--\; \le \; -->qD/nBound,$$Pr[F1]\leq qD/nBound,$ 

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

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

$Pr[E$$Pr[E$  $\wedge <!--\; \wedge \; -->$$\land$  $\mathrm{\neg <!--\; \neg \; -->}$$\neg$  $F]=Pr[E^{\prime }$$F]=Pr[E'$  $\wedge <!--\; \wedge \; -->$$\land$  $\mathrm{\neg <!--\; \neg \; -->}$$\neg$ $F]$$F]$ 

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

$|Pr[E]$$|Pr[E]$ $-<!--\; -\; -->Pr[$$-Pr[$ $E^{\prime }]|$$E']|$  $\le <!--\; \le \; -->Pr[F].$$\leq Pr[F].$ 

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

$Pr[S2]=1/2$$Pr[S2]=1/2$ 

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

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

$|Pr[S1]-<!--\; -\; -->Pr[S2]|$$|Pr[S1]-Pr[S2]|$ $\le <!--\; \le \; -->Pr[F2]$$\leq Pr[F2]$ 

Потребуем, чтобы $Pr[F2]\le <!--\; \le \; -->Advantag{e}_{RSA}(A^{\prime })$$Pr[F2]\leq Advantage_{RSA}(A')$  для алгоритма A', время работы которого ограничено временем, описанным выше. Тогда неравенство (*) будет выполнено. Алгоритм А' запускается следующим образом. Он получает на вход случайный RSA модуль $n$$n$ , RSA экспоненту $e$$e$  и случайный элемент $y\ast <!--\; \ast \; -->\le <!--\; \le \; -->Zn$$y*\leq Zn$ . A' создаёт открытый ключ, используя $n$$n$  и $e$$e$ , а затем разрешает противнику A начать игру. Когда А вызывает оракул для шифрования, А' отвечает А парой $(K^{\ast <!--\; \ast \; -->},y^{\ast <!--\; \ast \; -->})$$(K^{*},y^{*})$ , где $K^{\ast <!--\; \ast \; -->}$$K^{*}$  — случайный бит строки длиной $keyLen$$keyLen$ , а $y^{\ast <!--\; \ast \; -->}$$y^{*}$  подаётся на вход A. Алгоритм A' симулирует случайное предсказание $H$$H$ , как и дешифрующее RO, следующим образом. Для каждого входного $r\le <!--\; \le \; -->Z_n$$r\leq Z_{n}$  для случайного предсказания A' вычисляет $y=r^e\in <!--\; \in \; -->Z_n$$y=r^{e}\in Z_{n}$ , и размещает $r$$r$ , $y$$y$  и случайное значение $K=H(r)$$K=H(r)$  в таблицу. Однако, если $y=y^{\ast <!--\; \ast \; -->}$$y=y^{*}$  А' вместо того выводит $r$$r$  и завершается. Когда противник A предоставляет шифротекст $y\in <!--\; \in \; -->Z_n$$y\in Z_{n}$  дешифрующему предсказанию, А' ищет значение $y$$y$  в описанной таблице, чтобы определить было ли вычислено значение случайного предсказания при $r=y^{(1/e)}\in <!--\; \in \; -->Z_n$$r=y^{(1/e)}\in Z_{n}$ . Если да, то А' отвечает дешифрующему предсказанию значением $K=H(r)$$K=H(r)$ , хранящемся в таблице. Иначе, алгоритм создаёт новый случайный ключ $K$$K$ , и размещает пару $(y,K)$$(y,K)$  во второй таблице. Более того, если в будущем противник А должен будет вычислить случайное предсказание при $r\le <!--\; \le \; -->Z_n$$r\leq Z_{n}$  таком что $r^e=y$$r^{e}=y$ , то ключ $K$$K$ , сгенерированный выше, будет использован как значение $H(r)$$H(r)$ . Понятно, что A' отлично симулирует А, и даёт на выходе решение для данного случая RSA с вероятностью $Pr[F2]$$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. Архивная копия от 5 июля 2008 на Wayback Machine
• FCD 18033-2 Encryption algorithms — Part 2: Asymmetric ciphers. Архивная копия от 24 декабря 2010 на Wayback Machine
• Securing RSA-KEM via the AES (недоступная ссылка)
• RSA Algorithm Архивная копия от 22 ноября 2010 на Wayback Machine
• The Random Oracle Methodology Архивная копия от 3 марта 2016 на Wayback Machine
• Use of the RSA-KEM Key Transport Algorithm Архивная копия от 26 октября 2014 на Wayback Machine
• AES Key Wrap Specification Архивная копия от 17 сентября 2008 на Wayback Machine