Decoding RSA-KEM: Bridging to Hybrid Post-Quantum Cryptography - Blog

Decoding RSA-KEM: Bridging to Hybrid Post-Quantum Cryptography

Over at EXAMROOM.AI, we’re on a non-stop mission to lock down your secrets tighter than a duck’s feathers in water — and this enlightening piece is to understand Post-Quantum/Traditional composite Key Encapsulation Mechanism (KEM) algorithms. Consider this your backstage pass to the magic show where we’re pulling security rabbits out of digital hats!

A Key Encapsulation Mechanism (KEM) operates analogously to an asymmetric cipher, with the notable distinction that its encryption process requires only the receiver’s Public Key as input. Unlike traditional asymmetric encryption algorithms, which encrypt a given plaintext, the KEM’s encryption algorithm autonomously generates a pair consisting of a Shared Secret and its associated ciphertext. This method streamlines the encryption process by eliminating the need for external input data, focusing solely on the secure generation and transmission of shared secrets. For example, RSA-KEM (RSA Key Encapsulation Mechanism) and RSAES (RSA Encryption Scheme) are both cryptographic protocols that utilize the RSA algorithm for securing data transmission, but they serve different purposes and operate in distinct ways.

The three algorithms of the KEM can be represented as follows and illustrated in the Fig 1:

KeyGen -> {Public Key, Private Key} Encapsulation(PublicKey_Receiver) -> {Shared Secret, Ciphertext} Decapsulation(PrivateKey_Receiver, Ciphertext) -> {Shared Secret}

Fig 1. Key Encapsulation Mechanism

In terms of KEM, the following terms can be used interchangeably:

Encryption/Encapsulation

Decryption/Decapsulation

Private Key/Decapsulation Key

Public Key/Encapsulation Key

Having established a foundational understanding of Key Encapsulation Mechanisms (KEM), we are now poised to advance our discussion to RSA-KEM. This specialized cryptographic protocol is structured around three critical phases: RSA.KeyGen, RSA.Encrypt, and RSA.Decrypt.

RSA.KeyGen

RSA.KeyGen algorithm does not take any input and generates public key (n,e) and private key (d) for the users where RSA public key consists of two components:

Modulus (n): A large integer that is the product of two distinct large prime numbers (denoted as p and q), i.e., n = p×q. The security of RSA relies on the difficulty of factoring this large number back into its prime components.

Public Exponent (e): A positive integer less than n that is co-prime to (p−1)×(q−1), meaning e and (p−1)×(q−1) share no common divisors other than 1.

RSA-KEM.Encrypt

The RSA-KEM.Encrypt algorithm inputs are a public key with positive integers n and e, without any encryption options and then follows the steps below-

Generate a Random Number r: The algorithm starts by generating a random number r within the range [0..n), where n is part of the public key (the RSA modulus).

Convert r to Octet String R: The random number r is then converted into an octet string R using the I2OSP function, with a length that depends on the size of n.

Encrypt R to Produce C: The octet string R is encrypted using the RSA public key, specifically the public exponent e and modulus n, to produce the ciphertext C.

Derive Key K: The KDF is applied to R to derive a secret key K of a specified length. This step is where the KDF’s role is critical: it takes the random number r, represented by R, as its input and generates a secure key that can be used for further cryptographic operations.

Output C and K: The algorithm outputs the ciphertext C and the derived secret key K. The ciphertext can be sent openly, while K is used as a secret key for encrypting additional data or for other cryptographic purposes.

RSA-KEM.Decrypt

The RSA decryption process involves a series of detailed steps that ensure the secure transformation of encrypted data back into its original form, alongside the derivation of a secret key. Here’s a breakdown of these steps in detail:

RSATransform(C,d,n): The algorithm takes as input a ciphertext C, and the private key components: a positive integer n (the modulus) and a positive integer d (the private exponent). The RSA transformation involves the following steps:

Input Verification: Checks if the length of C matches the expected length, which should be equal to the byte representation length of n. This ensures C is a valid ciphertext formatted correctly for decryption.

Conversion to Integer: Uses the Octet String to Integer Primitive (OS2IP) to convert C from an octet string to an integer representation, let's denote this integer as 'c'.

Boundary Check:Ensures that c>n, verifying that c is within the valid range for RSA operations.

Modular Exponentiation: Performs c^d mod n which decrypts the ciphertext back into the original plaintext or message equivalent, in integer form. This operation leverages the RSA decryption formula.

Integer to Octet String: Converts the resulting integer from the modular exponentiation back into an octet string, R, using the Integer to Octet String Primitive (I2OSP). R represents the decrypted data.

Compute K = KDF(R, KeyLen):

Input: R (the decrypted data from the previous step) and KeyLen (the desired length of the output key).

Process: The Key Derivation Function (KDF) is a cryptographic algorithm that takes the decrypted data R and derives from it a fixed-size secret key K. The process typically involves hashing or other forms of cryptographic transformations to ensure K is cryptographically strong and suitable for use as a key in subsequent encryption operations.

RSA-KEM’s design offers a secure method of key encapsulation based on the hardness of the RSA inversion problem, with tight security reductions and robustness against multiple types of attacks, including implementation attacks and those arising in multi-plaintext scenarios. This makes RSA-KEM a solid choice for secure key encapsulation in cryptographic applications.

Note: Key Agreement involves two or more parties contributing to the generation of a shared secret. This is achieved through algorithms like Diffie-Hellman, where each party generates a public-private key pair and the shared secret is derived through an exchange of public keys and local computations using the private keys.

This article is heavily influenced by “ISO/IEC 18033–2: Information technology — Security techniques — Encryption algorithms — Part 2: Asymmetric Ciphers” written by Victor Shoup in 2004.

Discover the future of cybersecurity with Examroom.AI’s latest blog series, offering an in-depth exploration of Post-Quantum technology implementation.

Written by: Dr. Priti Kumari