Key encapsulation

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 n is typically 1024-bits or even longer, thus much larger than typical symmetric keys. If 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 m, ${\displaystyle 1<m<n}$. He derives his symmetric key M by ${\displaystyle M=KDF(m)}$, where KDF is a key derivation function, such as a cryptographic hash. He then computes the ciphertext ${\displaystyle c}$ corresponding to 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] 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 used to encapsulate keys for e or more recipients, and the receivers share the same exponent e, but different p, q, and n, then one can recover m via the Chinese remainder theorem. Thus, if key encapsulations for several recipients need to be computed, independent values m should be used.

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

• Key Wrap
• Optimal Asymmetric Encryption Padding