RSA-KEM

RSA-KEM (RSA Key Encapsulation Method) — механизм шифрования ключа для передачи в криптосистемах с открытым ключом.

Описание

Введение

RSA-KEM является популярным механизмом шифрования ключа, сочетающим в себе ложные перестановки RSA и KDF (Key Derivation Function). Обладает простотой и превосходными защитными свойствами, по сравнению с OAEP или OAEP+. Основной недостаток состоит в том, что шифротекст немного больше исходного текста.

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

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 = 1 mod \phi(n) \,$. Алгоритм генерации ключа ничего не принимает на вход и выполняется следующим образом:

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

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

Шифрование

Целью алгоритма шифрования является произвести псевдослучайный ключ K длинны KeyLen и шифротекст $C_0 \,$, который шифрует K. Алгоритм шифрования принимает следующее: — открытый ключ, состоящий из целого положительного n и e. — нет опций шифрования. Выполняется следующим образом:

1. Генерация случайного числа $r \in [0 .. n)\,$.
2. Вычисление $y = r^e mod n \,$.
3. Вычисление $K = KDF(I2OSP(r, nLen), KeyLen) \,$.
4. Вычисление $C_0 = I2OSP(y, nLen) \,$.
5. Получение шифротекста $C_0 \,$ и ключа K.

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

Алгоритм дешифрования принимает на вход следующее: — закрытый ключ, состоящий из целого положительного n и d. — шифротекст $C_0 \,$. Выполняется следующим образом:

1. Проверка $|C_0| = nLen \,$, иначе провал.
2. Установка $y = OS2IP(C0) \,$.
3. Проверка $y < n \,$, если нет, то провал.
4. Вычисление $r = y^d mod n \,$.
5. Вычисление $K = KDF(I2OSP(r, nLen), KeyLen) \,$.
6. Вывод ключа $K \,$

Анализ безопасности

Безопасность RSA-KEM может быть проанализирована в случайной модели предсказаний, в которой моделируется вызов KDF как случайной предсказательной очереди. Легко показать, что

$Advantage_{RSA-KEM} (A) \le Advantage_{RSA} (A0) + qD/nBound \,$.

где:

$A0\,$ — это алгоритм для решения случайного случая RSA задачи, который происходит примерно за то же время, что и $A \,$.

$q_D \,$ — это граница числа дешифровок очередей предсказания сделанных $A \,$.

$nBound \,$ — это меньшая граница n.

RSA-KEM предоставляет намного лучшую безопасность, чем RSA-OAEP+ или RSA-OAEP.

Безопасность RSA-KEM не ухудшается при увеличении длины шифротекста. Однако, это верно только тогда, когда число $r \,$ в алгоритме шифрования выбрано однородно модулю $n \,$, или по меньшей мере не неотличимо отклоняется от постоянного распределения. Это отличает RSA-OAEP+, где безопасность снижается линейно от величины шифротекста.

Примечания

Ссылки

• V. Shoup. A Proposal for an ISO Standard for Public Key Encryption. Preprint, December 2001.
• FCD 18033-2 Encryption algorithms — Part 2: Asymmetric ciphers.
• Securing RSA-KEM via the AES
• RSA Algorithm