Optimal Asymmetric Encryption Padding - Diagram of OAEP

Diagram of OAEP

In the diagram,

• n is the number of bits in the RSA modulus.
• k₀ and k₁ are integers fixed by the protocol.
• m is the plaintext message, an (n − k₀ − k₁ )-bit string
• G and H are typically some cryptographic hash functions fixed by the protocol.

To encode,

1. messages are padded with k₁ zeros to be n − k₀ bits in length.
2. r is a random k₀-bit string
3. G expands the k₀ bits of r to n − k₀ bits.
4. X = m00..0 ⊕ G(r)
5. H reduces the n − k₀ bits of X to k₀ bits.
6. Y = r ⊕ H(X)
7. The output is X || Y where X is shown in the diagram as the leftmost block and Y as the rightmost block.

To decode,

1. recover the random string as r = Y ⊕ H(X)
2. recover the message as m00..0 = X ⊕ G(r)

The "all-or-nothing" security is from the fact that to recover m, you must recover the entire X and the entire Y; X is required to recover r from Y, and r is required to recover m from X. Since any changed bit of a cryptographic hash completely changes the result, the entire X, and the entire Y must both be completely recovered.