RSA-KEM
(
RSA
Key Encapsulation Method) ? однопроходный (store-and-forward) механизм шифрования ключа для передачи в
криптосистемах с открытым ключом
. Сочетает в себе ложные перестановки
RSA
и KDF (Key Derivation Function). Обладает простотой и превосходными
защитными свойствами
, по сравнению с
OAEP
или
OAEP+
.
[
источник не указан 3352 дня
]
Основной недостаток состоит в том, что шифротекст немного больше исходного текста.
RSA-KEM относится к классу криптографических методов инкапсуляции ключа, спроектированных для безопасной отправки
симметричных ключей шифрования
с использованием
алгоритмов на открытых ключах
[1]
. На практике, системы шифрования на основе открытых ключей неудобны для передачи длинных сообщений, вместо этого они используются для обмена симметричными ключами, которыми в итоге шифруется текст.
Традиционным подходом к отправке симметричного ключа с помощью систем на открытых ключах является следующий алгоритм:
- Генерация случайного числа.
- Шифрование числа выбранным открытым ключом. Это зашифрованное сообщение отправляется получателю.
- Получатель расшифровывает его закрытым ключом и восстанавливает симметричный ключ.
Представленный алгоритм имеет несколько недостатков
[2]
. Во-первых, так как симметричный ключ мал, требуется его удлинение, а доказательство безопасности удлинения ключа не является строгим. Во-вторых, злоумышленник может отправить своё число, зашифрованное открытым ключом, и обмениваться сообщениями с получателем. В-третьих, не отслеживается целостность данных (обобщение второго пункта). Кроме того, шифры схожих сообщений могут быть похожими. Очевидно, что представленная схема недостаточно хороша и надёжна.
Метод инкапсуляции ключа демонстрирует иной, более продвинутый подход, решающий выявленные проблемы.
Процесс шифрования можно коротко представить следующим образом:
- Генерируется случайное входное
w
.
- Шифруется
w
с использованием
RSA
для передачи принимающему.
- Генерируется материал ключа
y
= KDF(
w
) для использования в последующем шифровании.
Принимающий может восстановить
w
из принятого шифртекста и затем сгенерировать
y
, чтоб и отправитель и принимающий могли согласиться с одинаковым симметричным ключом.
Механизм шифрования ключа имеет следующие системные параметры:
- RSAKeyGen: алгоритм генерации ключа RSA.
- KDF: A key derivation function.
- KeyLen: положительное целое число.
Открытый ключ состоит из RSA коэффициента
, который является произведением двух больших простых чисел и экспоненты
, где
(
?
наибольший общий делитель
)
[3]
. Это так же выделяет key derivation function KDF. Пусть
nLen
обозначает длину
n
в байтах. Секретный ключ состоит из дешифровой экспоненты
d
, где
.
Алгоритм генерации ключа ничего не принимает на вход и выполняется следующим образом:
- Вычисление (
n
,
e
,
d
) = RSAKeyGen().
- Получение открытого ключа PK (public key).
- Получение закрытого ключа pk (private key).
n
,
e
,
d
? целые положительные числа.
Целью алгоритма шифрования является произвести псевдослучайный ключ
K
длины KeyLen и шифротекст
, который шифрует
K
.
Алгоритм шифрования принимает следующее:
- открытый ключ, состоящий из целого положительного
n
и
e
.
- нет опций шифрования.
Выполняется следующим образом
[2]
:
1) Генерируется случайное число
.
2) Шифруется
открытым ключом получателя
3) Число
преобразуется в шифрованную строку
, а
в строчку
4) Создаётся так называемый key-encrypting key(KEK), длиной
, с использованием Key Derivation Function(KDF):
5) Передаваемая информация оборачивается (в англ. литературе WRAP) ключом KEK, с использованием key-wrapping схемы. На выходе получим шифорованный текст
6) Объединяем
и зашифрованный текст
является выходом алгоритма
KDF принимает на вход байтовую строчку и целое число
. Например, функция KDF1. Она параметризуется некоторой хеш функцией и определяется следующим образом
[2]
: на вход идут аргументы
, на выходе получаем первые
байт выражения:
- ||
|| ... ||
||
- где
"Близнецом" функции KDF1 является KDF2. Она отличается от KDF1 лишь тем, что счётчик проходит от
до
, а не от
до
. Однако для этих функций трудно установить, насколько "хорошими" генераторами псевдослучайных чисел они являются. В связи с этой потенциальной уязвимостью желательно использовать функцию KDF3, например. Она принимает в качестве параметров Hash и
На выход идут первые
байт выражения:
- ||
|| · · · ||
,
||
- где
.
Рекомендуемые хеш-функции SHA1 и RIPMD-160. Рекомендуемый
. О надёжности KDF3 уже можно судить достаточно уверенно.
Функция
описанная в стандарте IEEE P1363, преобразует число в строку. Её работа основана на функции
, которая наоборот, из строки получает число.
Спецификация
RFC 5990
требует, чтобы в качестве схемы обертки использовалась одна из следующих:
- AES Key Wrap
- Triple-DES Key Wrap
- Camillia Key Wrap
Наиболее распространена схема обертки AES
[4]
. Она оперирует блоками по 64 бита и требует на вход сообщение длиной более одного такого блока. Если длина сообщения 64бита или меньше, постоянная определённая спецификацией и ключевая информация формируют единственный 128-битный блок, обертывание которого бессмысленно.
Алгоритм дешифрования принимает на вход следующее:
- закрытый ключ, состоящий из целого положительного
n
и
d
.
- шифротекст
.
Выполняется следующим образом:
- Разделение зашифрованной информации о ключе
на шифротекст
длины
байт и обернутую информацию о ключе:
Если длина зашифрованной информации о ключе отличается от
, то дешифрование прекращается с ошибкой.
- Преобразование шифротекста
в целое число
и его расшифровка с использованием закрытого ключа принимающего:
Если
не находится в пределах
, то дешифрование прекращается с ошибкой.
- Преобразование целого
в байтовую строку
длины
- Создание
длины
байт из строки
при помощи KDF:
- Разворачивание информации о ключе
при помощи
:
Если операция разворачивания прекращается с ошибкой, выполнение всего алгоритма прекращается с ошибкой.
- Получение
на выходе алгоритма.
Безопасность RSA-KEM может быть проанализирована в модели случайного оракула (Random Oracle Model, далее RO)
[2]
. Суть модели состоит в следующем. Предположим, что существует некая общедоступная функция обладающая такими свойствами:
- На каждый новый аргумент функция отвечает новым значением и записывает пару (аргумент, значение) в таблицу.
- Если аргумент уже встречался, то функция обратится к своей таблице и вернёт значение, соответствующее этому аргументу.
Доказательство основано на предположении, что KDF является случайным оракулом, и что решение обратной задачи RSA невозможно (проще говоря, RSA нельзя взломать).
Для любого алгоритма генерации ключа для RSA (то есть алгоритма, возвращающего n, e и d), всегда выполнено n >= nBound (то есть nBound наименьшая допустимая граница для чисел n), и для каждого злоумышленника A справедливо:
- +
где
? это максимальное число запросов к оракулу, которое может сделать злоумышленник для попытки разгадать шифр
,
AdvantageRSA-KEM(A) = |Pr[b*-b] - 1/2| ? предсказательная способность А,
AdvantageRSA(A') обозначает вероятность успешного решения инверсной задачи RSA.
Нужно заметить, что приведённое выше неравенство не учитывает тот факт, что в реальности
с ненулевой вероятностью возвращает ≪плохие≫ ключи. Чтобы учесть его, требуется лишь прибавить эту вероятность к правой части неравенства.
Приведём доказательство, рассматривая последовательность игр
, и в каждой игре противник A проводит атаку. Каждая из этих игр проходит в одном вероятностном пространстве ? меняются только правила того, как рассчитываются случайные величины. В каждой игре будет событие
, связанное с событием
. Докажем, что разность
мала, и, более того, она будет свидетельствовать о том что в последней игре
.
Пусть
? первая игра,
? событие, обозначающее что
правильно угадывает бит
в игре
. Пусть
обозначает случайное предсказание оракула, размещающее элементы
в битовые строчки длины
в свою таблицу. Пусть
? атакуемый шифротекст, и
.
Далее мы определим следующую игру
, точно такую же как игру
. Если окажется так, что оракул был вызван для дешифрования с аргументом
раньше, и вызов был успешным, то игра останавливается. Пусть
? событие в игре
, соответствующее событию
.
Пусть
? событие, сигнализирующее о том, что игра
была остановлена. Понятно, что
и в промежуток времени, когда игры
и
проходят одинаково, а именно, до того момента как случается
, выполняется следующая лемма:
Пусть
и
? события, определённые на пространстве случайных событий таким образом, что
-
Тогда выполняется:
-
В нашем случае
Далее определим игру
, такую же как
, за исключением того, что атакуемый шифротекст генерируется в начале игры, и если противник запрашивает
для
, игра останавливается. Пусть
&mdash событие в
, соответствующее событию
. Очевидно, что
в силу того, что ключ
независим от чего-либо, доступного противнику в игре
. В этой игре
в
вызывается только с целью шифрования.
Пусть
? событие, сигнализирующее о том, что предыдущая игра прервалась. Понятно, что игры
и
протекают одинаково до тех пор, пока не случится
, и, следовательно, по лемме мы получим:
Потребуем, чтобы
для алгоритма A', время работы которого ограничено временем, описанным выше. Тогда неравенство (*) будет выполнено.
Алгоритм А' запускается следующим образом. Он получает на вход случайный RSA модуль
, RSA экспоненту
и случайный элемент
. A' создаёт открытый ключ, используя
и
, а затем разрешает противнику A начать игру.
Когда А вызывает оракул для шифрования, А' отвечает А парой
, где
? случайный бит строки длиной
, а
подаётся на вход A.
Алгоритм A' симулирует случайное предсказание
, как и дешифрующее RO, следующим образом. Для каждого входного
для случайного предсказания A' вычисляет
, и размещает
,
и случайное значение
в таблицу. Однако, если
А' вместо того выводит
и завершается. Когда противник A предоставляет шифротекст
дешифрующему предсказанию, А' ищет значение
в описанной таблице, чтобы определить было ли вычислено значение случайного предсказания при
. Если да, то А' отвечает дешифрующему предсказанию значением
, хранящемся в таблице. Иначе, алгоритм создаёт новый случайный ключ
, и размещает пару
во второй таблице. Более того, если в будущем противник А должен будет вычислить случайное предсказание при
таком что
, то ключ
, сгенерированный выше, будет использован как значение
.
Понятно, что A' отлично симулирует А, и даёт на выходе решение для данного случая RSA с вероятностью
. Это и доказывает безопасность алгоритма.
Количественно можно проверить, что RSA-KEM обеспечивает лучшую защиту по сравнению с RSA-OAEP+ и RSA-OAEP. Это преимущество выражается тем более, чем больше число сообщений, зашифрованных одним открытым ключом (замоделировано в BBM00). Это можно показать воспользовавшись тем, что решение инверсионной задачи RSA является очень трудозатратным. Таким образом безопасность RSA-KEM совсем не уменьшается с возрастанием числа зашифрованных текстов. Нужно заметить, что это утверждение справедливо только если число r в алгоритме шифрования для Simple RSA выбрано равномерно по модулю n, либо, как минимум, его распределение должно быть неотличимо от равномерного с точки зрения вычислений.
Кроме прочего, RSA-KEM, в отличие от RSA-OAEP or RSA-OAEP+, нельзя назвать ≪хрупким≫ алгоритмом, то есть не найдены возможности для атак на его реализации.
- ↑
Use of the RSA-KEM Key Transport Algorithm
- ↑
1
2
3
4
V. Shoup. A Proposal for an ISO Standard for Public Key Encryption
- ↑
FCD 18033-2 Encryption algorithms ? Part 2: Asymmetric ciphers
- ↑
AES Key Wrap Specification