Hybrid Encryption and Key Encapsulation

A hybrid encryption scheme encrypts a message of arbitrary length using a combination of public-key and symmetric-key primitives, achieving the security guarantees of public-key cryptography (no shared secret needed in advance) with the performance of symmetric cryptography (linear-time processing of large payloads). The standard way to build one is the KEM/DEM paradigm, introduced formally by Cramer and Shoup and later standardized in ISO/IEC 18033-2. A Key Encapsulation Mechanism (KEM) is a triple of algorithms `(KeyGen, Encaps, Decaps)`. `KeyGen` produces a public/private key pair `(pk, sk)`. `Encaps(pk)` outputs a pair `(K, c)`: a fresh, uniformly random symmetric key `K` and a ciphertext `c` that "encapsulates" it. `Decaps(sk, c)` recovers `K` from `c`. Crucially, a KEM does not let the sender choose the key — it only generates a random one, which simplifies both the algorithm and its security proof compared to public-key encryption of an arbitrary chosen message. A Data Encapsulation Mechanism (DEM) is a symmetric-key scheme — typically an authenticated encryption scheme like AES-GCM or ChaCha20-Poly1305 — that takes a key `K` and a message `m` of any length and produces a ciphertext that is both confidential and tamper-evident. The hybrid encryption scheme `HE = (KEM, DEM)` simply runs: ``` Encrypt(pk, m): (K, c1) = KEM.Encaps(pk) c2 = DEM.Enc(K, m) return (c1, c2) ``` The security intuition is a clean separation of concerns: the KEM's job is only to deliver a random, secret key to the receiver in a way that an eavesdropper cannot distinguish from noise; the DEM's job is only to protect a message under a key that is already shared and secret. Neither component needs to solve the other's problem, which is what makes both the constructions and their proofs simpler than trying to build one monolithic public-key scheme for arbitrary-length messages (as classic textbook RSA/ElGamal encryption attempts and fails to do securely).

Building a KEM from RSA

The most direct KEM construction wraps RSA. Instead of encrypting a chosen message, the sender picks a random integer, encrypts it with RSA, and derives the symmetric key from it using a key-derivation function (KDF). This avoids the structural weaknesses of "textbook" RSA encryption (multiplicativity, no randomization) because the KDF output looks random even though RSA itself is deterministic. ``` RSA-KEM.KeyGen(): generate RSA modulus n = p*q, exponents (e, d) pk = (n, e); sk = (n, d) return (pk, sk) RSA-KEM.Encaps(pk = (n, e)): r = random integer in [0, n-1] c = r^e mod n K = KDF(r, length = symmetric key size) return (K, c) RSA-KEM.Decaps(sk = (n, d), c): r = c^d mod n K = KDF(r, length = symmetric key size) return K ```

Building a KEM from Diffie–Hellman (the ECIES pattern)

The Diffie–Hellman-based KEM, often called DHIES/ECIES in its full authenticated form, uses an ephemeral key pair generated fresh for each encryption. The sender's ephemeral public key becomes the "ciphertext" of the KEM. ``` DH-KEM.KeyGen(): choose group G with generator g, order q x = random in [1, q-1] pk = g^x; sk = x return (pk, sk) DH-KEM.Encaps(pk = g^x): y = random in [1, q-1] // ephemeral c = g^y // sent to receiver Z = pk^y = g^(xy) // shared DH value K = KDF(Z, c, pk) // bind context into K return (K, c) DH-KEM.Decaps(sk = x, c = g^y): Z = c^x = g^(xy) K = KDF(Z, c, pk) return K ``` Both parties land on the same `Z = g^{xy}`, exactly as in ordinary Diffie-Hellman Key Exchange, but here it is packaged as one-shot encapsulation rather than an interactive protocol — perfect for encrypting a message to someone's static public key without any live handshake.

The full hybrid encryption pipeline

``` HybridEncrypt(pk, m): (K, c1) = KEM.Encaps(pk) n = random nonce for the DEM (if required) c2 = DEM.Enc(K, n, m) // authenticated encryption return (c1, n, c2) HybridDecrypt(sk, (c1, n, c2)): K = KEM.Decaps(sk, c1) m = DEM.Dec(K, n, c2) // rejects on tag failure if m == REJECT: return ERROR return m ``` Only `c1` (the KEM ciphertext) depends on the public key and the specific KEM algorithm; `c2` is produced by an ordinary symmetric authenticated cipher and can be as large as the plaintext, encrypted at gigabytes-per-second, regardless of which KEM is chosen. This modularity means a system can swap RSA-KEM for a lattice-based KEM (foreshadowing Post-Quantum Cryptography: An Introduction) without touching the DEM layer at all.

Time complexity. RSA-KEM's `Encaps` and `Decaps` each perform one modular exponentiation, costing `O(k^3)` bit operations for a `k`-bit modulus using schoolbook multiplication (or `O(k^2 log k log log k)` with fast multiplication algorithms), independent of message length. DH-KEM likewise performs `O(1)` group exponentiations, each `O(log q)` group operations via square-and-multiply. The DEM, by contrast, runs in `O(|m|)` time using AES-NI or ChaCha20, processing gigabytes per second. Because the expensive public-key operation runs exactly once per message, regardless of the message's size, hybrid encryption's total cost is `O(k^3) + O(|m|)` rather than the `O(|m| / k \cdot k^3) = O(|m| \cdot k^2)` cost of applying RSA block-by-block to the whole payload — a difference of orders of magnitude for large `m`.

Space complexity. The ciphertext overhead is `|c1| + |nonce| + |tag|`, a small constant (RSA modulus size, or one group element, plus a 12–16 byte nonce and 16 byte authentication tag) added once, not per block. This is asymptotically optimal: any semantically secure scheme must add at least some randomness-derived overhead, and hybrid schemes achieve the minimum needed, a single KEM ciphertext.

Correctness. Decapsulation must recover exactly the key that encapsulation produced. For RSA-KEM this follows from RSA's correctness identity: ``` (r^e)^d ≡ r^(ed) ≡ r (mod n) ``` which holds because `ed ≡ 1 (mod φ(n))` by construction and Euler's theorem gives `r^{φ(n)} ≡ 1 (mod n)` for `r` coprime to `n`. For DH-KEM correctness follows from commutativity of exponentiation: `(g^x)^y = (g^y)^x = g^{xy}`, so sender and receiver derive the same `Z` and hence the same `K = KDF(Z, ...)`. In both cases the DEM's correctness is inherited from the underlying authenticated cipher, which decrypts correctly whenever the key and nonce match and the tag verifies.

Security — the composition theorem. The central theoretical result is that if the KEM is IND-CCA secure (its ciphertexts don't leak whether the encapsulated key is real or uniformly random, even against an adversary with a decapsulation oracle) and the DEM is IND-CCA secure with authentication (ciphertexts under a truly random key leak nothing and resist tampering), then the composed hybrid scheme is IND-CCA secure as a whole. Proof sketch. Consider an adversary `A` attacking the hybrid scheme in the IND-CCA game: it submits two messages `m0, m1`, receives a challenge `(c1, c2)`, and must guess which message was encrypted, with access to a decryption oracle (except on the challenge ciphertext). We build a sequence of games:

• Game 0: the real IND-CCA game against the hybrid scheme.
• Game 1: replace the challenge key `K` used to form `c2` with a uniformly random key

`K'`, independent of `c1`. If `A`'s advantage changes non-negligibly between Game 0 and Game 1, we can build a KEM distinguisher: simulate `A`'s decryption oracle by decapsulating submitted ciphertexts with the KEM secret key (available to the simulator, not to `A`), and feed the KEM challenge `(K^b, c1)` from the external KEM game directly into the DEM challenge step. Any gap in `A`'s success rate becomes a distinguishing advantage against the KEM's IND-CCA security. Since the KEM is assumed secure, this gap is negligible.

• In Game 1, `c2*` is now an encryption under a key `K'` totally unrelated to anything

`A` has seen, so `A`'s view of `c2` is governed entirely by the DEM's own IND-CCA security. Any residual advantage in Game 1 becomes a distinguishing advantage against the DEM, which is assumed negligible. Hence `A`'s total advantage is bounded by (negligible KEM-distinguishing term) + (negligible DEM-distinguishing term), so it is itself negligible. This "hybrid argument" (in the technical sense of a sequence of indistinguishable games, not to be confused with hybrid encryption*) is the standard proof technique in modern cryptography and is why KEM/DEM security definitions were chosen exactly to make this decomposition airtight.

Tradeoffs. The KEM/DEM split assumes the DEM key is used for a single message (or a clearly bounded session); reusing a KEM-derived key across many unrelated messages without a fresh KEM encapsulation reintroduces nonce-reuse and key-reuse risks that the composition theorem does not cover. RSA-KEM ciphertexts are large (matching the RSA modulus, e.g. 256 bytes for RSA-2048) compared to DH-KEM's ciphertexts (one group element, e.g. 32 bytes for Curve25519), a real bandwidth consideration at scale.

Trace a small (deliberately toy-sized, insecure-for-production but illustrative) RSA-KEM instance end to end.

Setup. Let `p = 61`, `q = 53`, so `n = pq = 3233`, `φ(n) = 6052 = 3120`. Choose `e = 17` (coprime to 3120). Compute `d = e^{-1} mod 3120 = 2753` (verify: `17 2753 = 46801 = 153120 + 1`, so `17*2753 ≡ 1 (mod 3120)`, confirming `d` is correct). `pk = (n=3233, e=17)`, `sk = (n=3233, d=2753)`.

Encapsulation. The sender draws a random `r = 1234` (in real systems `r` is chosen from a CSPRNG over the full range `[0, n-1]`; this toy value is illustrative only). ``` c = r^e mod n = 1234^17 mod 3233 = 3220 K = KDF(1234) = SHA-256(1234) truncated to 128 bits, say K = 0x9f3a...c1 ```

Transmission. `c = 3220` is sent over the public channel alongside the DEM ciphertext.

Decapsulation. The receiver computes ``` r' = c^d mod n = 3220^2753 mod 3233 = 1234 K' = KDF(1234) = same 0x9f3a...c1 ``` matching the sender's key exactly, since RSA's correctness guarantees `r' = r`.

DEM step. Suppose the message is `m = "PAY ALICE $500"`. Using `K` and a fresh 96-bit nonce `nonce = 0x1a2b3c...`, the sender computes with AES-256-GCM: ``` (c2, tag) = AES-GCM.Enc(K, nonce, m) ``` producing a ciphertext `c2` the same length as `m` plus a 16-byte authentication tag. The full message sent is `(c1=3220, nonce, c2, tag)`. On the receiving end, decryption first recomputes `K` via `RSA-KEM.Decaps`, then calls `AES-GCM.Dec(K, nonce, c2, tag)`; if the tag matches, the plaintext `m` is returned, otherwise decryption fails closed.

Notice that the RSA operation touched only the 32-bit integer `1234`, never the 14-byte message — exactly the design goal: public-key cost is paid once, independent of `|m|`.

The KEM/DEM abstraction crystallized ideas that had existed informally in applied cryptography — PGP combined RSA with IDEA/AES this way since the early 1990s — into a formal security framework that could be proven correct.

Hybrid encryption is the default architecture wherever public-key cryptography meets bulk data. TLS uses a KEM-like structure inside its handshake (foreshadowing The TLS Handshake) to establish a shared symmetric key that then protects the entire HTTP session with AES-GCM or ChaCha20-Poly1305. PGP and S/MIME encrypt emails by wrapping a random AES key with the recipient's RSA or elliptic-curve public key. Age and Minisign, modern file-encryption tools, follow the exact KEM/DEM template with X25519-based KEMs. Messaging apps like Signal use ephemeral Diffie–Hellman-style key agreement (the X3DH protocol) as a KEM-like step before symmetric ratcheting takes over for message encryption. As lattice-based and other quantum-resistant algorithms (foreshadowing Post-Quantum Cryptography: An Introduction) like CRYSTALS-Kyber replace RSA and elliptic-curve KEMs in the NIST post-quantum standardization process, the KEM/DEM split remains unchanged — only the KEM's internal math changes, a direct payoff of the modularity this article has developed.

Ask the tutor: How does the KEM/DEM pattern generalize when the KEM is replaced by a lattice-based post-quantum construction like Kyber?