Hybrid Encryption and the Cost of Encrypting Long Messages

A public-key operation cannot encrypt a message of arbitrary length. The arithmetic produces one group element, so the plaintext must be smaller than the modulus for RSA, or it must be a point on the curve for an elliptic curve scheme. A 3072-bit RSA key can carry at most 384 bytes in one operation, and most of that is padding. Any protocol that needs to send a file, a request body, or a stream therefore uses a hybrid construction: the public-key operation carries a symmetric key, and the symmetric cipher carries the data.

The two-layer structure and why it is not a compromise

The layered design is not a workaround for a limitation of public-key cryptography; it is the correct architecture even if public-key operations could handle long messages. Symmetric ciphers are faster by orders of magnitude, they are the primitives with the most analysis behind them, and authenticated modes give integrity for the message as a whole. A public-key layer provides exactly one thing the symmetric layer cannot: the ability to establish a key between parties who share no secret.

So the split is along capability, not convenience. The public-key layer solves key distribution; the symmetric layer solves bulk data. The interface between them is where the design decisions live.

The naive version of the interface is to generate a random symmetric key, encrypt it with RSA, and concatenate. That works, and it has a defect: it wastes the structure RSA offers and inherits whatever weaknesses the padding has. The refined version derives the symmetric key from the public-key output with a hash, so that even a partial break of the public-key step does not directly yield the key.

RSA-KEM: hashing the raw output

RSA-KEM, standardised in ISO/IEC 18033-2, treats RSA as a key encapsulation mechanism. The sender draws a random integer $r$ uniformly from $[1, n-1]$, computes $c = r^e \bmod n$, and derives the symmetric key as $K = \mathrm{KDF}(r)$. It sends $c$; the recipient computes $r = c^d \bmod n$ and the same derivation.

The construction removes the padding entirely, and that is its point. There is no encoded message structure to get wrong, no separator byte to validate, and no oracle that distinguishes one malformed block from another — a random $r$ is valid by definition. The KDF, typically HKDF with a protocol-specific label, absorbs the non-uniform distribution of $r$ and produces keys of the required length.

sender:    r <- uniform [0, n)      c = r^e mod n      K = HKDF(r, info)
receiver:  r = c^d mod n            K = HKDF(r, info)

The security argument is tighter than for RSA-OAEP because the underlying primitive is used directly, without an encoding layer that has to be proven indifferentiable. The trade-off is that the raw RSA operation is a permutation and the KDF must do all the work of extracting a uniform key from it. HKDF’s extract step, which is a keyed hash of the input, is designed for exactly this.

RSA-KEM also fixes a practical problem with OAEP: the maximum message length. OAEP can carry a message of at most $k - 2h - 2$ bytes for a $k$-byte modulus and an $h$-byte hash, so a 2048-bit key with SHA-256 carries at most 190 bytes. RSA-KEM carries no message at all, only a key, so the size constraint disappears from the protocol’s data path.

ECIES: an ephemeral exchange per message

ECIES, the elliptic curve integrated encryption scheme, takes the same shape with a key agreement instead of a key transport. The sender generates an ephemeral scalar $r$, computes $R = rG$, computes the shared point $S = r \cdot Q$ where $Q$ is the recipient’s public key, and derives keys from $S$. The recipient computes $S = d \cdot R$ with its private scalar $d$. Both arrive at the same point because $r \cdot (dG) = d \cdot (rG)$.

The x-coordinate of $S$ is the shared secret. It is fed to a KDF together with the ephemeral public point and the recipient’s public key, so that the derived keys are bound to the specific exchange. The ciphertext carries $R$ in the clear; it is not secret, only the shared point is.

import hashlib, hmac, os

def ecies_keys(recipient_pub, N, G, scalar_mul, encode):
    r = int.from_bytes(os.urandom(32), "big") % N   # ephemeral scalar
    R = scalar_mul(r, G)                            # ephemeral public point
    S = scalar_mul(r, recipient_pub)                # shared point
    ctx = encode(R) + encode(recipient_pub)
    prk = hmac.new(ctx, encode(S), hashlib.sha256).digest()    # extract
    key = hmac.new(prk, b"ecies-key", hashlib.sha256).digest()  # expand
    nonce = os.urandom(12)
    return encode(R), key, nonce

N is the order of the base point, scalar_mul is the curve’s point multiplication, and encode is the profile’s point serialisation. The two scalar multiplications dominate the cost; the hash construction is HKDF’s extract-then-expand shape written out with HMAC directly. The ciphertext is then whatever the profile’s authenticated cipher produces from key, nonce, and the message, with encode(R) supplied as associated data. That last part matters: binding the ephemeral point into the authenticated data means a ciphertext cannot be re-associated with a different $R$, which would otherwise let an attacker swap the key-derivation context. The general principle is that every value the key derivation depends on must also be authenticated, or the binding is advisory.

ECIES has no single standard; ISO/IEC 18033-2 defines one profile, SEC 1 defines another, and several libraries implement their own variants with different KDFs and different curve encodings. The incompatibility is a real operational hazard, and the reason a protocol should specify its exact profile rather than say “ECIES”.

What the KEM interface changes

The abstraction that has become standard is the key encapsulation mechanism: a pair of algorithms, Encapsulate(pk) -> (ciphertext, key) and Decapsulate(sk, ciphertext) -> key. The interface deliberately hides whether the underlying primitive is RSA, a Diffie-Hellman exchange, or something else, because the consuming protocol only needs a key and a blob.

That abstraction is what makes post-quantum migration tractable. A protocol written against a KEM interface can swap the KEM implementation without changing the record layer, the key schedule, or the message framing. TLS 1.3’s key exchange is structured this way, and the hybrid key agreements now deployed combine a classical group with a post-quantum KEM by concatenating both shared secrets and feeding the concatenation to the KDF.

The hybrid construction is worth stating precisely because its security argument is a conjunction, not a disjunction. If the combined secret is $K = \mathrm{KDF}(s_{\text{classical}} | s_{\text{pq}})$, then an attacker must break both components to recover $K$. Breaking only one leaves the other as an unknown input to the hash. This is stronger than choosing one scheme and hoping: it holds even if the post-quantum scheme turns out to be weaker than advertised, and even if the classical scheme falls to a quantum computer.

The cost is size. A hybrid key share carries both public values, so a handshake that would carry 32 bytes of X25519 carries those plus a post-quantum encapsulation of a kilobyte or more. That increase is the practical obstacle to hybrid deployment in constrained protocols, and it is why the choice of post-quantum KEM matters more for wire size than for security.

Failure modes that the layering introduces

The two-layer design creates seams, and the seams are where implementations break.

Key and ciphertext binding. If the symmetric key is derived without binding the ciphertext’s context, an attacker can transplant a ciphertext from one session into another and have it decrypt under the same key. Deriving the key from the transcript, and authenticating the public-key output as associated data, closes this. The failure mode is the same as the one described for key agreement in Ephemeral Diffie-Hellman and What Forward Secrecy Actually Buys.

Nonce management. The symmetric layer needs a nonce, and the nonce must be unique per key. A hybrid scheme that derives a fresh key per message makes a fixed nonce safe, but a scheme that reuses a key across messages must carry a nonce and must never repeat it. Reusing a nonce with a stream cipher or with GCM is catastrophic: it reveals the XOR of plaintexts and, for GCM, the authentication key.

Mismatched security levels. A hybrid scheme is as strong as its weakest layer. A 256-bit curve combined with AES-128 gives 128 bits of security, not 256. Combining a 2048-bit RSA key with a post-quantum KEM at a lower level caps the whole construction. The equivalence reasoning is in Key Size Equivalence Across RSA, Diffie-Hellman, and Curves.

Decapsulation oracles. The public-key step can fail in ways that leak. RSA-KEM’s failure mode is benign — any $c$ decrypts to some $r$ — but a KEM built on a key agreement must reject invalid public values, and the rejection must be indistinguishable from a wrong-key failure at the protocol level. Otherwise the decapsulation becomes an oracle of the same shape as the one that broke PKCS #1 v1.5 padding, covered in RSA Padding and Why Textbook RSA Fails.

When not to use a hybrid at all

If the parties already share a symmetric key, the public-key layer adds nothing and costs a full exponentiation or scalar multiplication per message. Key establishment protocols exist to create the shared key once; after that, the symmetric layer carries everything. A design that performs a public-key operation per message is paying for key distribution on every message.

The same reasoning applies to a server with many clients: the expensive part is the key establishment, and it is amortised across the connection, not across the data. This is why connection reuse and session resumption matter so much for the CPU cost of a TLS server, and why the cost of an ephemeral exchange, quantified in the forward-secrecy article, is a per-connection budget rather than a per-byte one.