Public-key encryption, hybrid schemes and HPKE

RSA-OAEPRSA-OAEP: RSAES-OAEP, RSA encryption with Optimal Asymmetric Encryption Padding (RFC 8017). Random padding makes every ciphertext different, and decryption refuses any ciphertext whose padding does not check. More in “Public-key cryptography: RSA and elliptic curves” with a 2,048-bit key and SHA-256 encrypts at most 190 bytes, so a 1 MiB file does not fit and a message of 191 bytes throws an error. Public-key encryption therefore never encrypts the data itself: it protects a short key, and a symmetric cipher protects the data under that key.

This lesson measures the limit and builds the pattern that every modern scheme follows, hybrid encryptionhybrid encryption: Encrypting data with a fresh symmetric key and delivering that key under the recipient's public key. The data is protected by an AEAD, so the message size does not depend on the public-key size limit.. It then rebuilds HPKE, the standard form of that pattern, from the test vector of RFC 9180, shows what goes wrong when the pieces are put together by hand, and ends with the choice between a standard, a library and an envelope of your own.

Public-key encryption wraps a short key, and hybrid schemes encrypt the data under it

RSA works on one number smaller than its modulus, and OAEP spends part of that room on a random seed, a hash of an optional label and two marker bytes. RFC 8017 leaves k − 2·hLen − 2 bytes for the message, for a modulus of k bytes and a hash of hLen bytes. The program finds the limit by trying, for a 2,048-bit and a 3,072-bit key with SHA-256, and then does the job the hybrid way:

// RSA-OAEP has a size limit: a message must fit in the padded block, k - 2 * hLen - 2 bytes for a modulus of k bytes and a
// hash of hLen bytes (RFC 8017 section 7.1.1). The program finds the limit by trying, for 2048-bit and 3072-bit keys with
// SHA-256, then does the job the hybrid way: one RSA-OAEP operation wraps a 32-byte AES key, and AES-GCM encrypts the data.
const { subtle } = globalThis.crypto;
const HASH_LENGTH = 32; // SHA-256

async function largestMessage(modulusLength) {
  const pair = await subtle.generateKey({ name: 'RSA-OAEP', modulusLength, publicExponent: new Uint8Array([1, 0, 1]), hash: 'SHA-256' }, false, ['encrypt', 'decrypt', 'wrapKey', 'unwrapKey']);
  const fits = (n) => subtle.encrypt({ name: 'RSA-OAEP' }, pair.publicKey, new Uint8Array(n)).then(() => true, (err) => err.name === 'OperationError' ? false : Promise.reject(err));
  let [low, high] = [0, modulusLength / 8]; // low fits, high does not
  while (high - low > 1) {
    const mid = (low + high) >> 1;
    if (await fits(mid)) low = mid;
    else high = mid;
  }
  const error = await subtle.encrypt({ name: 'RSA-OAEP' }, pair.publicKey, new Uint8Array(low + 1)).catch((err) => err.name);
  return { pair, low, error };
}

console.log('RSA-OAEP with SHA-256 (hLen = 32): the largest message that encrypts');
let pair2048;
for (const bits of [2048, 3072]) {
  const k = bits / 8;
  const { pair, low, error } = await largestMessage(bits);
  if (bits === 2048) pair2048 = pair;
  console.log(`  ${bits}-bit key (k = ${k} bytes): ${low} bytes encrypt, ${low + 1} bytes throw ${error}; k - 2 * ${HASH_LENGTH} - 2 = ${k - 2 * HASH_LENGTH - 2}`);
}

const FILE = 1024 * 1024;
const chunk = 256 - 2 * HASH_LENGTH - 2;
const directOperations = Math.ceil(FILE / chunk);
console.log(`\na ${FILE.toLocaleString('en-US')}-byte file with the 2048-bit key`);
console.log(`  directly: ${directOperations} RSA-OAEP operations and ${(directOperations * 256).toLocaleString('en-US')} bytes of ciphertext`);
const aesKey = await subtle.generateKey({ name: 'AES-GCM', length: 256 }, true, ['encrypt', 'decrypt']);
const wrapped = new Uint8Array(await subtle.wrapKey('raw', aesKey, pair2048.publicKey, { name: 'RSA-OAEP' }));
const iv = new Uint8Array(12); // one message under a fresh key, so a fixed nonce is safe here
const sealed = new Uint8Array(await subtle.encrypt({ name: 'AES-GCM', iv }, aesKey, new Uint8Array(FILE)));
console.log(`  hybrid: 1 RSA-OAEP operation wraps the 32-byte AES key into ${wrapped.length} bytes; AES-GCM seals the file into ${sealed.length.toLocaleString('en-US')} bytes`);
console.log(`  hybrid total with the 12-byte nonce: ${(wrapped.length + iv.length + sealed.length).toLocaleString('en-US')} bytes, ${(wrapped.length + iv.length + sealed.length - FILE).toLocaleString('en-US')} more than the file`);

RSA-OAEP with SHA-256 (hLen = 32): the largest message that encrypts
  2048-bit key (k = 256 bytes): 190 bytes encrypt, 191 bytes throw OperationError; k - 2 * 32 - 2 = 190
  3072-bit key (k = 384 bytes): 318 bytes encrypt, 319 bytes throw OperationError; k - 2 * 32 - 2 = 318

a 1,048,576-byte file with the 2048-bit key
  directly: 5519 RSA-OAEP operations and 1,412,864 bytes of ciphertext
  hybrid: 1 RSA-OAEP operation wraps the 32-byte AES key into 256 bytes; AES-GCM seals the file into 1,048,592 bytes
  hybrid total with the 12-byte nonce: 1,048,860 bytes, 284 more than the file

The limit is 190 bytes for the 2,048-bit key and 318 for the 3,072-bit key, one byte more throws OperationError, and both equal the formula. Encrypting a 1 MiB file directly with the 2,048-bit key would take 5,519 RSA operations and give 1,412,864 bytes. The hybrid way takes one operation to wrap a 32-byte key into 256 bytes and one AES-GCM call for the file, 1,048,860 bytes in all.

Hybrid schemes put each primitive where it belongs. Public-key encryption wraps a fresh symmetric key, and an AEADAEAD: Authenticated encryption with associated data: one operation that encrypts a message and computes a tag over it and over associated data, so that opening returns the whole plaintext or fails. AES-GCM and ChaCha20-Poly1305 are AEADs. More in “Authenticated encryption: AES-GCM and ChaCha20” encrypts the data under it, so the cost and the size of the message follow the cipher and not the modulus. Step through the pattern:

Three names cover what follows. RSA-OAEP wraps a short key under an RSA public key, with random padding that decryption checks. Hybrid schemes in general encapsulate a fresh keykey encapsulation: Delivering a fresh symmetric key under a recipient's public key, so that only the matching private key recovers it. RSA-OAEP key wrapping and ML-KEM do this; an AEAD then encrypts the data under that key. More in “Public-key cryptography: RSA and elliptic curves” for the recipient and encrypt the data with an AEAD under it. HPKE is the standard hybrid scheme of RFC 9180, with one specified key encapsulation, key derivation and AEAD, and test vectors for all of it.

RSA-OAEP’s limit follows from its padding, and PKCS#1 v1.5 encryption stays out Pro: opens with a Pro, Premium or Ultimate pass