RSA-KEM
RSA-KEM (RSA Key Encapsulation Method) — однопроходный (store-and-forward) механизм шифрования ключа для передачи в криптосистемах с открытым ключом. Сочетает в себе ложные перестановки RSA и KDF (Key Derivation Function). Обладает простотой и превосходными защитными свойствами, по сравнению с OAEP или OAEP+.[источник не указан 3405 дней] Основной недостаток состоит в том, что шифротекст немного больше исходного текста.
Описание
[править | править код]Введение
[править | править код]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)
[править | править код]KDF принимает на вход байтовую строчку и целое число . Например, функция KDF1. Она параметризуется некоторой хеш функцией и определяется следующим образом[2]: на вход идут аргументы , на выходе получаем первые байт выражения:
- || || ... || ||
- где
"Близнецом" функции KDF1 является KDF2. Она отличается от KDF1 лишь тем, что счётчик проходит от до , а не от до . Однако для этих функций трудно установить, насколько "хорошими" генераторами псевдослучайных чисел они являются. В связи с этой потенциальной уязвимостью желательно использовать функцию KDF3, например. Она принимает в качестве параметров Hash и На выход идут первые байт выражения:
- || || · · · || , ||
- где .
Рекомендуемые хеш-функции SHA1 и RIPMD-160. Рекомендуемый . О надёжности KDF3 уже можно судить достаточно уверенно. Функция описанная в стандарте IEEE P1363, преобразует число в строку. Её работа основана на функции , которая наоборот, из строки получает число.
Схема обертки ключа (Key Wrapping Schema)
[править | править код]Спецификация 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+, нельзя назвать «хрупким» алгоритмом, то есть не найдены возможности для атак на его реализации.
Примечания
[править | править код]Ссылки
[править | править код]- 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