RSA-KEM

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle C=intToStr(c,nLen),}$

${\displaystyle Z=intToStr(z,nLen)}$

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

${\displaystyle KEK=KDF(z,kekLen)}$

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

${\displaystyle WK=Wrap(KEK,K)}$

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

${\displaystyle EK=C||WK}$

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

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

${\displaystyle Hash(Z}$ || ${\displaystyle I2OSP(0,4))}$|| ... || ${\displaystyle Hash}$${\displaystyle (Z}$||${\displaystyle I2OSP(k-1,}$ ${\displaystyle 4)),}$

где ${\displaystyle k=L/Hash.outputLen.}$

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

${\displaystyle Hash(I2OSP(0,padding)}$ || ${\displaystyle Z)}$ || · · · || ${\displaystyle Hash(I2OSP(k-1}$, ${\displaystyle padding)}$ || ${\displaystyle Z),}$

где ${\displaystyle k=L/Hash.outputLen}$.

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

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

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

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

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

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

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

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

${\displaystyle C||WK=EK}$

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

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

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

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

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

${\displaystyle Z=IntToStr(z,nLen)}$

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

${\displaystyle KEK=KDF(Z,kekLen)}$

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

${\displaystyle K=Unwrap(KEK,WK)}$

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

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

Безопасность 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. Архивная копия от 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