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

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

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

Шифрование

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

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

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

1) Генерируется случайное число $z\in [0..n)$.

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

$c=z^{e}modn$

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

$C=intToStr(c,nLen),$

$Z=intToStr(z,nLen)$

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

$KEK=KDF(z,kekLen)$

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

$WK=Wrap(KEK,K)$

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

$EK=C||WK$

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

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

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

$Hash(Z$ || $I2OSP(0,4))$|| ... || $Hash$$(Z$||$I2OSP(k-1,$ $4)),$

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

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

$Hash(I2OSP(0,padding)$ || $Z)$ || · · · || $Hash(I2OSP(k-1$, $padding)$ || $Z),$

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

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

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

1. Разделение зашифрованной информации о ключе $EK$ на шифротекст $C$ длины $nLen$ байт и обернутую информацию о ключе:

$C||WK=EK$

Если длина зашифрованной информации о ключе отличается от $nLen$, то дешифрование прекращается с ошибкой.

1. Преобразование шифротекста $C$ в целое число $c$ и его расшифровка с использованием закрытого ключа принимающего:

$c=StrToInt(C)$
$z=c^{d}modn$

Если $c$ не находится в пределах $0\leqslant c\leqslant n-1$, то дешифрование прекращается с ошибкой.

1. Преобразование целого $z$ в байтовую строку $Z$ длины $nLen.$

$Z=IntToStr(z,nLen)$

1. Создание $KEK$ длины $kekLen$ байт из строки $Z$ при помощи KDF:

$KEK=KDF(Z,kekLen)$

1. Разворачивание информации о ключе $WK$ при помощи $KEK$:

$K=Unwrap(KEK,WK)$

Если операция разворачивания прекращается с ошибкой, выполнение всего алгоритма прекращается с ошибкой.

1. Получение $K$ на выходе алгоритма.

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

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

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

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

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

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

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

$Pr[F1]\leq qD/nBound,$

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

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

$Pr[E$ $\land$ $\neg$ $F]=Pr[E'$ $\land$ $\neg$$F]$

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

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

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

$Pr[S2]=1/2$

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

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

$|Pr[S1]-Pr[S2]|$$\leq Pr[F2]$

Потребуем, чтобы $Pr[F2]\leq Advantage_{RSA}(A')$ для алгоритма A', время работы которого ограничено временем, описанным выше. Тогда неравенство (*) будет выполнено. Алгоритм А' запускается следующим образом. Он получает на вход случайный RSA модуль $n$, RSA экспоненту $e$ и случайный элемент $y*\leq Zn$. A' создаёт открытый ключ, используя $n$ и $e$, а затем разрешает противнику A начать игру. Когда А вызывает оракул для шифрования, А' отвечает А парой $(K^{*},y^{*})$, где $K^{*}$ — случайный бит строки длиной $keyLen$, а $y^{*}$ подаётся на вход A. Алгоритм A' симулирует случайное предсказание $H$, как и дешифрующее RO, следующим образом. Для каждого входного $r\leq Z_{n}$ для случайного предсказания A' вычисляет $y=r^{e}\in Z_{n}$, и размещает $r$, $y$ и случайное значение $K=H(r)$ в таблицу. Однако, если $y=y^{*}$ А' вместо того выводит $r$ и завершается. Когда противник A предоставляет шифротекст $y\in Z_{n}$ дешифрующему предсказанию, А' ищет значение $y$ в описанной таблице, чтобы определить было ли вычислено значение случайного предсказания при $r=y^{(1/e)}\in Z_{n}$. Если да, то А' отвечает дешифрующему предсказанию значением $K=H(r)$, хранящемся в таблице. Иначе, алгоритм создаёт новый случайный ключ $K$, и размещает пару $(y,K)$ во второй таблице. Более того, если в будущем противник А должен будет вычислить случайное предсказание при $r\leq Z_{n}$ таком что $r^{e}=y$, то ключ $K$, сгенерированный выше, будет использован как значение $H(r)$. Понятно, что A' отлично симулирует А, и даёт на выходе решение для данного случая RSA с вероятностью $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