Русская Википедия:RSA-KEM

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

Описание

Введение

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

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

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

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

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

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

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

Параметры

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

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

Генерация ключа

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

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

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

Шифрование

Целью алгоритма шифрования является произвести псевдослучайный ключ K длины KeyLen и шифротекст <math>C_0</math>, который шифрует K. Алгоритм шифрования принимает следующее:

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

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

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

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

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

<math>C = intToStr(c, nLen),</math>

<math>Z = intToStr(z, nLen)</math>

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

<math>KEK = KDF(z, kekLen)</math>

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

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

<math>EK</math> является выходом алгоритма

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

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

где <math>k = L/Hash.outputLen.</math>

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

<math>Hash(I2OSP(0, padding)</math> || <math>Z)</math> || · · · || <math> Hash(I2OSP(k-1</math>, <math>padding)</math> || <math> Z),</math>

где <math>k = L/Hash.outputLen</math>.

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

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

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

AES Key Wrap
Triple-DES Key Wrap
Camillia Key Wrap

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

Дешифрование

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

закрытый ключ, состоящий из целого положительного n и d.
шифротекст <math>C_0</math>.

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

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

<math>C || WK = EK</math>

Если длина зашифрованной информации о ключе отличается от <math>nLen</math>, то дешифрование прекращается с ошибкой.
Преобразование шифротекста <math>C</math> в целое число <math>c</math> и его расшифровка с использованием закрытого ключа принимающего:

<math>c = StrToInt(C)</math>
<math>z = c ^ d mod n</math>

Если <math>c</math> не находится в пределах <math>0 \leqslant c \leqslant n-1</math>, то дешифрование прекращается с ошибкой.
Преобразование целого <math>z</math> в байтовую строку <math>Z</math> длины <math>nLen.</math>

<math>Z = IntToStr(z, nLen)</math>
Создание <math>KEK</math> длины <math>kekLen</math> байт из строки <math>Z</math> при помощи KDF:

<math>KEK = KDF (Z, kekLen)</math>
Разворачивание информации о ключе <math>WK</math> при помощи <math>KEK</math>:

<math>K = Unwrap (KEK, WK)</math>

Если операция разворачивания прекращается с ошибкой, выполнение всего алгоритма прекращается с ошибкой.
Получение <math>K</math> на выходе алгоритма.

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

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

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

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

<math>Advantage_{RSA-KEM}(A) \le Advantage_{RSA}(A')</math> + <math>qD/nBound (*),</math>

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

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

<math>Pr[F1] \le qD/nBound,</math>

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

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

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

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

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

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

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

[1] Use of the RSA-KEM Key Transport Algorithm

[Shoup-2] 2,0 ^2,1 ^2,2 ^2,3 V. Shoup. A Proposal for an ISO Standard for Public Key Encryption

[3] FCD 18033-2 Encryption algorithms — Part 2: Asymmetric ciphers

[4] AES Key Wrap Specification

[1]

[2]

[3]

[4]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.