OAEP — Optimal Asymmetric Encryption Padding

PKCS#1 v1.5 padding for encryption has been a footgun for thirty years (Bleichenbacher 1998, ROBOT 2017, Marvin 2023). OAEP is the modern replacement, standardized in PKCS#1 v2 and recodified in RFC 8017 §7.1.

OAEP turns m into an encoded message EM of length k (the modulus byte length) using a random seed and a mask-generation function.

The construction (encode)

Given parameters: hash function H (output hLen bytes), label L (empty by default), seed S (random, hLen bytes), message M:

lHash = H(L)                                       // hLen bytes
PS    = 00...00                                    // k - mLen - 2*hLen - 2 zero bytes
DB    = lHash || PS || 0x01 || M                   // k - hLen - 1 bytes
dbMask    = MGF1(S, k - hLen - 1)
maskedDB  = DB XOR dbMask
seedMask  = MGF1(maskedDB, hLen)
maskedSeed = S XOR seedMask
EM    = 0x00 || maskedSeed || maskedDB              // k bytes

Then RSA encryption: c = pow(int(EM), e, n).

MGF1 — Mask Generation Function 1 (§B.2.1)

OAEP needs a "stream" of pseudo-random bytes derived from a seed. MGF1 builds one by hashing seed || counter for counter = 0, 1, 2, ...:

mgf1(seed, length, H):
    T = b""
    for c = 0; len(T) < length; c++:
        T += H(seed || I2OSP(c, 4))           // 4-byte big-endian counter
    return T[:length]

Why it's secure

Provably secure under the random-oracle model assuming RSA is hard to invert (Bellare-Rogaway 1994; tightened by Fujisaki-Okamoto-Pointcheval-Stern 2001).

The two layers of masking + the lHash integrity check defeat the Bleichenbacher chosen-ciphertext attack: an attacker cannot tell from decryption failures whether lHash was wrong or the 0x01 separator was missing or the leading byte was non-zero.

Common foot-gun: error reporting

You must not reveal which of the OAEP checks failed (lHash, separator, leading zero). RFC 8017 §7.1.2 Note 1 is emphatic: return a single opaque "decryption error" regardless of which step failed. Otherwise you re-introduce a padding oracle (Manger 2001 broke a non-constant-time OAEP).

In this exercise

You implement the pure padding step — EME-OAEP-encode and MGF1. RSA modular exponentiation is the next step; here we expose only the encoding so you can compare byte-for-byte against published vectors.