Cairn
algorithms · cryptography · O(k) time, k = RSA modulus byte length, dominated by the underlying modular exponentiation's own O(log n) cost; O(k) space

↩ back to Cryptography

OAEP

RSA Encryption's own Pitfalls section names the exact gap this page closes, then leaves it open: textbook RSA is deterministic and multiplicative — checked directly on that page, encrypting 5 and 7 separately and multiplying the results gives exactly the encryption of 35, no decryption required. "Real deployments pad the message (OAEP) before encrypting specifically so this multiplicative shortcut, and the determinism it rides on, never applies to real ciphertexts," that page says, without ever building it. OAEP (Optimal Asymmetric Encryption Padding — Bellare and Rogaway, 1994; standardized as part of PKCS#1 v2, RFC 8017) is that padding scheme. It doesn't touch RSA's own arithmetic at all — it restructures and randomizes the plaintext before RSA's modular exponentiation ever sees it, using nothing but two nested rounds of a mask built from this site's own SHA-256.

Try it

Generate a toy RSA keypair below first. It's deliberately bigger than RSA Encryption's own n = 3,233 — OAEP paired with SHA-256 needs real room to work with, see Pitfalls — but it's still a demo size, generated fresh in your browser in well under a second, nowhere near a real deployment's 2048-bit-or-larger recommendation.

No key yet — click to generate one (~900-bit modulus).

Now encrypt the same message twice in a row, with the same key, and compare. Textbook RSA would produce the identical ciphertext both times — OAEP's random seed means it never does.

Generate a key first.

Decrypt the most recent ciphertext above and confirm it recovers the original message, then try tampering: flip one bit of a valid ciphertext and decrypt that instead. Every tamper, no matter which internal check it actually breaks, fails with the exact same generic message — see Why it works for why that's deliberate, not a missing error-message detail.

Why it works

Given a k-byte RSA modulus and SHA-256 as the hash (hLen = 32 bytes), encoding a message M builds:

DB = lHash ‖ PS ‖ 0x01 ‖ M              // lHash = SHA-256(label); label is empty on this page
seed = k random bytes (hLen of them)
maskedDB   = DB   ⊕ MGF1(seed, k-hLen-1)
maskedSeed = seed ⊕ MGF1(maskedDB, hLen)
EM = 0x00 ‖ maskedSeed ‖ maskedDB        // exactly k bytes — this is what RSA actually encrypts

MGF1 (Mask Generation Function 1) is nothing new on top of SHA-256 — it just hashes seed ‖ counter for counter = 0, 1, 2, … and concatenates the digests until there's enough output, the same trick HMAC and PBKDF2 each reuse SHA-256's own output for a different purpose rather than defining a new primitive. The seed is fresh and random on every single encryption — that's the entire source of the non-determinism demonstrated above, nothing else about RSA changes.

The two masking rounds are chained on purpose, not just doubled up for extra safety. maskedDB depends on seed; maskedSeed is then masked using maskedDB itself as the input to the second MGF1 call. Decoding has to reverse that exact order — recover seed from maskedSeed first (using maskedDB, already in hand, to regenerate the seed mask), then use the recovered seed to unmask DB. Flip even one bit anywhere in EM and SHA-256's own avalanche property (already measured on its own page: roughly half the output bits flip for a one-bit input change) means the recovered seed comes out effectively random, which means the recovered DB comes out effectively random too — nothing about the original message survives a tamper in a way that would let an attacker learn which bit they flipped from the result.

Every one of decode's internal checks collapses into one outcome. A correctly decoded block must have its leading byte equal to 0x00, its recovered lHash match the hash of the label actually used, and a 0x01 separator somewhere after the zero padding. A real implementation — this page's included — never reports which of those three failed, only "decoding error," for all of them. See Pitfalls for why that single detail is itself a documented, named attack this scheme has to defend against.

Reference implementation

Built directly on top of the exact processBlocks/padMessage SHA-256 primitives SHA-256's own page already built and verified — copied here rather than imported, same as every other page on this site:

function mgf1(seed, maskLen) {
  var hLen = 32, out = new Uint8Array(maskLen), pos = 0, counter = 0;
  while (pos < maskLen) {
    var C = new Uint8Array(4);
    writeUInt32BE(C, 0, counter);
    var digest = sha256Bytes(concatBytes(seed, C));
    var take = Math.min(hLen, maskLen - pos);
    out.set(digest.subarray(0, take), pos);
    pos += take;
    counter++;
  }
  return out;
}

function oaepEncode(message, k, label) {
  var hLen = 32;
  if (message.length > k - 2 * hLen - 2) throw new Error('message too long for this modulus');
  var lHash = sha256Bytes(label);
  var psLen = k - message.length - 2 * hLen - 2;
  var DB = new Uint8Array(k - hLen - 1);
  DB.set(lHash, 0);                                  // PS (psLen zero bytes) is already zero-filled
  DB[hLen + psLen] = 0x01;
  DB.set(message, hLen + psLen + 1);

  var seed = randomBytes(hLen);
  var maskedDB = xorBytes(DB, mgf1(seed, k - hLen - 1));
  var maskedSeed = xorBytes(seed, mgf1(maskedDB, hLen));

  var EM = new Uint8Array(k);
  EM.set(maskedSeed, 1);
  EM.set(maskedDB, 1 + hLen);
  return EM;                                          // EM[0] stays 0x00
}

function oaepDecode(EM, k, label) {
  var hLen = 32;
  var Y = EM[0];
  var maskedSeed = EM.slice(1, 1 + hLen);
  var maskedDB = EM.slice(1 + hLen);
  var seed = xorBytes(maskedSeed, mgf1(maskedDB, hLen));
  var DB = xorBytes(maskedDB, mgf1(seed, k - hLen - 1));
  var lHash = sha256Bytes(label);
  var lHashOk = true;
  for (var i = 0; i < hLen; i++) if (lHash[i] !== DB[i]) lHashOk = false;

  var sepIdx = -1;
  for (var j = hLen; j < DB.length; j++) { if (DB[j] !== 0) { sepIdx = j; break; } }
  var valid = (Y === 0) && lHashOk && sepIdx !== -1 && DB[sepIdx] === 0x01;
  if (!valid) throw new Error('decoding error');       // one message, every failure cause
  return DB.slice(sepIdx + 1);
}

Verified both directions against Node's own crypto.publicEncrypt/privateDecrypt with RSA_PKCS1_OAEP_PADDING and oaepHash: 'sha256' at a real 2048-bit key, before any of this reached the page above: this page's own oaepEncode, fed through plain BigInt modular exponentiation with that key's real exponent, decrypted and unpadded correctly by Node's native OAEP decoder; and separately, a message encrypted by Node's own native OAEP encoder, decrypted by this page's own oaepDecode after a plain BigInt decrypt, recovered byte-for-byte. Also checked: encoding the identical message twice produces two completely different EM values (the live demo above); a one-bit tamper anywhere in EM always throws the single generic decoding error; and the maximum message length formula (k - 66 bytes for SHA-256) round-trips exactly at the boundary and rejects one byte past it. The RSA keygen and modPow behind the "Generate toy RSA keypair" button above reuse the identical square-and-multiply technique Modular Exponentiation walks through and the identical Miller–Rabin primality test Miller–Rabin already verified — scaled up to 448-bit candidate primes (rather than those pages' own worked examples) because that's what it takes to clear OAEP's own minimum modulus size with SHA-256, below.

Pitfalls

Determinism is gone, and that's the entire point — demonstrated live above, not just asserted. RSA Encryption's own multiplicative shortcut (encrypting a and b separately, multiplying the ciphertexts, getting exactly the encryption of ab) relied on every encryption of a fixed message under a fixed key landing on the exact same number. OAEP's random seed breaks that from the first step: two encryptions of the identical message never produce related ciphertexts, so there's no multiplicative structure left for that shortcut to exploit in the first place.

SHA-256 forces a real minimum modulus size, independent of factoring hardness. Encoding needs room for lHash (32 bytes), at least one padding byte, the 0x01 separator, and the message itself, inside a k-byte block split as 0x00 ‖ seed (32 bytes) ‖ DB. Working through the arithmetic: k ≥ 2·32 + 2 = 66 bytes (528 bits) just to encode a zero-length message with nothing left over — verified directly against this page's own implementation, which round-trips exactly at that floor and throws one byte below it. This page's toy key (~900 bits, 112 bytes) clears that floor comfortably, with room for a 46-byte message, but it's nowhere near the ≥2048-bit (256-byte) modulus real deployments use — that larger size is driven by a different constraint, the factoring-hardness margin RSA Encryption's and RSA Digital Signature's own toy-modulus pitfalls already cover. OAEP's 66-byte floor and RSA's factoring margin are two separate reasons small keys don't work, not the same reason twice — a modulus can clear one and still fail the other, and this page's own toy key is a direct example: safely over OAEP's floor, nowhere close to safe against factoring.

The single generic decode error isn't a missing feature — distinguishing error cases here is a real, named attack. James Manger published a 2001 attack against OAEP implementations that returned a different, observably different error (or took measurably different time) depending on which check failed first — whether the leading byte was wrong versus a later check. An attacker who can submit chosen ciphertexts and tell those cases apart can use that distinction as an oracle, decrypting a target ciphertext one query at a time without ever recovering the private key — the same high-level shape as Bleichenbacher's 1998 attack against RSA's older PKCS#1 v1.5 encryption padding, the scheme OAEP replaced for exactly this class of reason. This page's own oaepDecode collapses all three internal checks (leading byte, label hash, separator) into one thrown message before anything is returned — demonstrated live by the tamper button above, which fails identically no matter which byte of a valid ciphertext gets flipped.

The label parameter is real and this page doesn't exercise it. RFC 8017 lets an encoder bind a public, non-secret context string (the "label") into lHash, so a ciphertext encoded for one context fails to decode under a different one even with the correct key. This page always uses the empty label — the default essentially every major OAEP implementation ships — rather than building label-mismatch handling as its own feature.

Complexity

Time: O(k) for encode or decode — two MGF1 calls, each a small number of SHA-256 compressions over roughly k bytes total, the same O(n) cost SHA-256's own Complexity section already establishes. In practice this is negligible next to the RSA modular exponentiation it wraps — O(log n) multiplications of k-byte numbers, the real cost driver, measured the same way on RSA Encryption's own Complexity section. Space: O(k) — the encoded block is exactly as large as the modulus it's about to be encrypted under, no larger. Security: OAEP introduces no new hardness assumption of its own; it's a construction proven secure (in the random-oracle model, treating SHA-256/MGF1 as an idealized random function) against chosen-ciphertext attacks, assuming the underlying trapdoor — RSA's factoring hardness here — holds. It doesn't make a small modulus safe against factoring, and factoring hardness alone doesn't make textbook RSA safe without it; both pieces have to hold at once.