Optimal asymmetric encryption padding
In cryptography, Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway, and subsequently standardized in PKCS#1 v2 and RFC 2437.

The OAEP algorithm is a form of Feistel network which uses a pair of random oracles G and H to process the plaintext prior to asymmetric encryption.  When combined with any secure trapdoor one-way permutation , this processing is proved in the random oracle model to result in a combined scheme which is semantically secure under chosen plaintext attack (IND-CPA).  When implemented with certain trapdoor permutations (e.g., RSA), OAEP is also proved secure against chosen ciphertext attack.  OAEP can be used to build an all-or-nothing transform.

OAEP satisfies the following two goals:

Add an element of randomness which can be used to convert a deterministic encryption scheme (e.g., traditional RSA) into a probabilistic scheme.
Prevent partial decryption of ciphertexts (or other information leakage) by ensuring that an adversary cannot recover any portion of the plaintext without being able to invert the trapdoor one-way permutation .

The original version of OAEP (Bellare/Rogaway, 1994) showed a form of "plaintext awareness" (which they claimed implies security against chosen ciphertext attack) in the random oracle model when OAEP is used with any trapdoor permutation.  Subsequent results contradicted this claim, showing that OAEP was only IND-CCA1 secure.  However, the original scheme was proved in the random oracle model to be IND-CCA2 secure when OAEP is used with the RSA permutation using standard encryption exponents, as in the case of RSA-OAEP.
An improved scheme (called OAEP+) that works with any trapdoor one-way permutation was offered by Victor Shoup to solve this problem.
More recent work has shown that in the standard model (that is, when hash functions are not modeled as random oracles) it is impossible to prove the IND-CCA2 security of RSA-OAEP under the assumed hardness of the RSA problem.

Algorithm

In the diagram,
 n is the number of bits in the RSA modulus.
 k0 and k1 are integers fixed by the protocol.
 m is the plaintext message, an (n − k0 − k1 )-bit string
 G and H are mask generation functions based on chosen cryptographic hash functions
 ⊕ is an xor operation.

To encode,
 messages are padded with k1 zeros to be n − k0 bits in length.
 r is a randomly generated k0-bit string
 G expands the k0 bits of r to n − k0 bits.
 X = m00...0 ⊕ G(r)
 H reduces the n − k0 bits of X to k0 bits.
 Y = r ⊕ H(X)
 The output is X || Y where X is shown in the diagram as the leftmost block and Y as the rightmost block.

Usage in RSA:
The encoded message can then be encrypted with RSA. The deterministic property of RSA is now avoided by using the OAEP encoding.

To decode,
 recover the random string as r = Y ⊕ H(X)
 recover the message as m00...0 = X ⊕ G(r)

Security
The "all-or-nothing" security is from the fact that to recover m, one 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.

Implementation
In the PKCS#1 standard, the random oracles G and H are identical. The PKCS#1 standard further requires that the random oracles be MGF1 with an appropriate hash function.

See also
Key encapsulation

References

Public-key encryption schemes
Padding algorithms