Key Encapsulation - Example Using RSA Encryption

Example Using RSA Encryption

Using the same notation employed in the RSA system article, say Alice has transmitted her public key to Bob, while keeping her private key secret, as usual. Bob then wishes to send symmetric key M to Alice. M might be a 128 or 256-bit AES key, for example. Note that the public key n is typically 1024-bits or even longer, thus much larger than typical symmetric keys. If e is small enough that, then the encryption can be quickly broken using ordinary integer arithmetic.

To avoid such potential weakness, Bob first turns M into a larger integer by using an agreed-upon reversible protocol known as a padding scheme, such as OAEP. He then computes the ciphertext corresponding to:

Alice can recover from by using her private key exponent by the following computation:

Given, she recovers the original message M by reversing the padding scheme.

With KEM the process is simplified as follows:

Instead of generating a random symmetric key M, Bob first generates a random m, . He derives his symmetric key M by, where KDF is a key derivation function, such as a cryptographic hash. He then computes the ciphertext corresponding to m:

Alice then recovers from by using her private key exponent by the same method as above:

Given, she can recover the symmetric key M by .

The KEM eliminates the complexity of the padding scheme and the proofs needed to show the padding is secure. p. 4 Note that while M can be calculated from m in the KEM approach, the reverse is not possible, assuming the key derivation function is one-way. An attacker who somehow recovers M cannot get the plaintext m. With the padding approach, he can. Thus KEM is said to encapsulate the key.

Note that if the same m is sent to e or more recipients in an encrypted way, and the receivers share the same exponent e, but different p, q, and n, then one can decrypt the original clear text message via the Chinese remainder theorem. Thus key encapsulation should not be used directly to send the same symmetric key to multiple recipients. Instead the common symmetric key can be encrypted using separate symmetric keys (Key Encryption Keys) for each recipient and the encrypted keys then sent separately.

Similar techniques are available for Diffie-Hellman encryption and other public key methods.