Key encapsulation
Encyclopedia
Key encapsulation mechanisms (KEMs) are a class of encryption
techniques designed to secure symmetric cryptographic key material for transmission using asymmetric (public-key) algorithms. In practice, public key systems are clumsy to use in transmitting long messages. Instead they are often used to exchange symmetric keys, which are relatively short. The symmetric key is then used to encrypt the longer message.
The traditional approach to sending a symmetric key with public key systems is to first generate a random symmetric key and then encrypt it using the chosen public key algorithm. The recipient then decrypts the public key message to recover the symmetric key. As the symmetric key is generally short, padding is required for full security and proofs of security for padding schemes are often less than complete. KEMs simplify the process by generating a random element in the finite group
underlying the public key system and deriving the symmetric key by hashing that element, eliminating the need for padding.
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 M
, 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.
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
techniques designed to secure symmetric cryptographic key material for transmission using asymmetric (public-key) algorithms. In practice, public key systems are clumsy to use in transmitting long messages. Instead they are often used to exchange symmetric keys, which are relatively short. The symmetric key is then used to encrypt the longer message.
The traditional approach to sending a symmetric key with public key systems is to first generate a random symmetric key and then encrypt it using the chosen public key algorithm. The recipient then decrypts the public key message to recover the symmetric key. As the symmetric key is generally short, padding is required for full security and proofs of security for padding schemes are often less than complete. KEMs simplify the process by generating a random element in the finite group
Finite group
In mathematics and abstract algebra, a finite group is a group whose underlying set G has finitely many elements. During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of...
underlying the public key system and deriving the symmetric key by hashing that element, eliminating the need for padding.
Example using RSA encryption
Using the same notation employed in the RSA system article, say AliceAlice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
has transmitted her public key
to BobAlice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
, 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 M
, 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 OAEPOptimal Asymmetric Encryption Padding
In cryptography, Optimal Asymmetric Encryption Padding is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway....
. 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 functionKey derivation function
In cryptography, a key derivation function derives one or more secret keys from a secret value such as a master key or other known information such as a password or passphrase using a pseudo-random 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
Chinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
. 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.
See also
- Key WrapKey WrapKey Wrap constructions are a class of symmetric encryption algorithms designed to encapsulate cryptographic key material. The Key Wrap algorithms are intended for applications such as protecting keys while in untrusted storage, or transmitting keys over untrusted communications networks...
- Optimal Asymmetric Encryption PaddingOptimal Asymmetric Encryption PaddingIn cryptography, Optimal Asymmetric Encryption Padding is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway....