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.
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.
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.
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.
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.
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.
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.
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.