OAEP is an acronym for Optimal Asymmetric Encryption Padding. It is very common to want to encrypt a session key using RSA and sending it over a network, but doing so without any padding opens up the possibility of various attacks. Thus, over time various methods of padding the key out to the size of the RSA modulus have been developed, the most popular being one included in PKCS #1 version 1.5.

However, the PKCS #1 method is non-optimal; various attacks have been developed which make it's use deprecated in new applications. OAEP (sometimes referred to as EME1, it's designation in IEEE 1363) was invented by Mihir Bellare and Phil Rogaway, who provided a reasonably tight proof of security in the random oracle model. The initial paper was "Optimal Asymmetric Encryption - How to Encrypt with RSA", published in Eurocrypt '94.

OAEP uses a hash function (usually SHA-1) and a mask generation function (which is almost always MGF1; most implementations of OAEP hard-code the use of MGF1 in). The mask generation function basically takes an input seed, and a length value, and produces a random string of the specified length, whose value depends only on the seed. An example of a reasonable mask generation function would be a block cipher in OFB mode, using the seed as a key.

OAEP takes the input "plaintext" (which is usually actually a key for a symmetric cipher, rather than actual text) *P* and produces a padded representation *PR*, suitable to be encrypted by the RSA function. This description assumes SHA-1 and MGF1 are used (which is typical). In addition to the message, choose a random string *R*, generally with the same length as the output of the hash function (ie 160 bits for SHA-1). The notation is rather poor, but it's the best I could come up with on short notice:

- Pad
*P* with 0 bytes until it is less than 8 bits smaller in length than the modulus to form *P'*.
- Use MGF1 to compute a random string,
*PAD* of length equal to *P'*, using *R* as the seed.
- XOR
*P'* and *PAD* to produce *P''*
- Hash
*P''* with SHA-1 to produce *H*
*PR* = *P''* || *R* XOR *H*

I'm not going to get into why this is more secure than other alternatives; read the many and various OAEP papers to get all kinds of horrible details.

OAEP, while much more secure than previous alternatives, is not without problems. Specifically, the original proof showed that OAEP was secure against a chosen ciphertext attack (CCA), the most powerful form of attack against a public key algorithm like RSA. But in fact there are two versions of CCA, one of which is much stronger than the other. The proof actually only applied to the weaker one (without specifically saying so), and in fact, Victor Shoup proved that it was impossible for OAEP to be secure against the strong CCA attack (in the general case). But another paper, released around the same time, showed that used with RSA, OAEP *was* secure against the strong CCA attack. Shoup has suggested some replacements for OAEP, but they have not seen wide adoption (read: nobody uses them).

At this time, OAEP is recommended for all new applications that use RSA, though the method of PKCS #1 v1.5 is still very common.

Other public key encryption schemes (such as ElGamal and Rabin) can also make use of OAEP.