In cryptography, Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway.^{[1]}
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 oneway permutation , this processing is proved in the random oracle model to result in a combined scheme which is semantically secure under chosen plaintext attack (INDCPA). 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 allornothing 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 oneway 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 INDCCA1 secure. However, the original scheme was proved in the random oracle model to be INDCCA2 secure when OAEP is used with the RSA permutation using standard encryption exponents, as in the case of RSAOAEP. ^{[2]} An improved scheme (called OAEP+) that works with any trapdoor oneway permutation was offered by Victor Shoup to solve this problem.^{[3]} More recent work has shown that in the standard model (that is, when hash functions are not modelled as random oracles), that it is impossible to prove the INDCCA2 security of RSAOAEP under the assumed hardness of the RSA problem.^{[4]}^{[5]}
Diagram of OAEP Edit
In the diagram,
 n is the number of bits in the RSA modulus.
 k_{0} and k_{1} are integers fixed by the protocol.
 m is the plaintext message, a (n − k_{0} − k_{1} )bit string
 G and H are typically some cryptographic hash functions fixed by the protocol.
To encode,
 messages are padded with k_{1} zeros to be n − k_{0} bits in length.
 r is a random k_{0}bit string
 G expands the k_{0} bits of r to n − k_{0} bits.
 X = m00..0 ⊕ G(r)
 H reduces the n − k_{0} bits of X to k_{0} 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.
To decode,
 recover the random string as r = Y ⊕ H(X)
 recover the message as m00..0 = X ⊕ G(r)
The "allornothing" 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 bit of a cryptographic hash completely changes the result, the entire X, and the entire Y must both be completely recovered.
ReferencesEdit
 ↑ M. Bellare, P. Rogaway. Optimal Asymmetric Encryption  How to encrypt with RSA. Extended abstract in Advances in Cryptology  Eurocrypt '94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed, SpringerVerlag, 1995. full version (pdf)
 ↑ Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern. RSA OAEP is secure under the RSA assumption. In J. Kilian, ed., Advances in Cryptology  CRYPTO 2001, vol. 2139 of Lecture Notes in Computer Science, SpringerVerlag, 2001. full version (pdf)
 ↑ Victor Shoup. OAEP Reconsidered. IBM Zurich Research Lab, Saumerstr. 4, 8803 Ruschlikon, Switzerland. September 18, 2001. full version (pdf)
 ↑ P. Paillier and J. Villar, Trading OneWayness against ChosenCiphertext Security in FactoringBased Encryption, Advances in Cryptology  Asiacrypt 2006.
 ↑ D. Brown, What Hashes Make RSAOAEP Secure?, IACR ePrint 2006/233.
See alsoEdit
