Key encapsulation mechanism

Using the same notation employed in the RSA system article, say Alice has transmitted her public key ${\displaystyle (n,e)}$ 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 ${\displaystyle n}$ is typically 2048-bits or even longer, thus much larger than typical symmetric keys. If ${\displaystyle e}$ is small enough that ${\displaystyle M^{e}<n}$, then the encryption can be quickly broken using ordinary integer arithmetic.[2]

To avoid such potential weakness, Bob first turns M into a larger integer ${\displaystyle 1<m<n}$ by using an agreed-upon reversible protocol known as a padding scheme, such as OAEP. He then computes the ciphertext ${\displaystyle c}$ corresponding to:

${\displaystyle c\equiv m^{e}{\pmod {n}}.}$

Alice can recover ${\displaystyle m}$ from ${\displaystyle c}$ by using her private key exponent ${\displaystyle d}$ by the following computation:

${\displaystyle m\equiv c^{d}{\pmod {n}}.}$

Given ${\displaystyle m}$, she recovers the original message M by reversing the padding scheme.

With KEM the process is simplified as follows:[3]

Instead of generating a random symmetric key M, Bob first generates a random ${\displaystyle m}$ with ${\displaystyle 1<m<n}$. He derives his symmetric key M by ${\displaystyle M=KDF(m)}$, where ${\displaystyle KDF}$ is a key derivation function, such as a cryptographic hash. He then computes the ciphertext ${\displaystyle c}$ corresponding to ${\displaystyle m}$:

${\displaystyle c\equiv m^{e}{\pmod {n}}.}$

Alice then recovers ${\displaystyle m}$ from ${\displaystyle c}$ by using her private key exponent ${\displaystyle d}$ by the same method as above:

${\displaystyle m\equiv c^{d}{\pmod {n}}.}$

Given ${\displaystyle m}$, she can recover the symmetric key M by ${\displaystyle M=KDF(m)}$.

The KEM eliminates the complexity of the padding scheme and the proofs needed to show the padding is secure.[1] Note that while M can be calculated from ${\displaystyle 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 ${\displaystyle m}$. With the padding approach, he can. Thus KEM is said to encapsulate the key.

Note that if the same ${\displaystyle m}$ is used to encapsulate keys for ${\displaystyle e}$ or more recipients, and the receivers share the same exponent ${\displaystyle e}$, but different ${\displaystyle p,q}$ and ${\displaystyle n}$, then one can recover ${\displaystyle m}$ via the Chinese remainder theorem. Thus, if key encapsulations for several recipients need to be computed, independent values ${\displaystyle m}$ should be used.

Earlier versions of Transport Layer Security used RSA for key exchange, before they were deprecated in favour of more efficient Elliptic Curve Cryptography.[4]

Similar techniques are available for Diffie-Hellman key exchange and other public key methods.[5]

• Key Wrap
• Optimal Asymmetric Encryption Padding
• Hybrid Cryptosystem