# How does OAEP improve the security of RSA?

The heart of OAEP algorithm used for RSA encryption are the cryptographic hash functions $H$ and $G$.

Does everybody (so also an adversary) know these functions?

• If YES: How does it help the security, if he just can decode the padding and read the message?

• If NO: What knowledge is needed for these functions? Are keys or something priorly exchanged? Are they related to the receivers private key?

-

Well, yes, everyone (or, at least, everyone who can use the public key) knows the hash function H and G; so we can assume that an adversary knows them as well.

If YES: How does it help the security, if he just can decode the padding and read the message?

Well, he can't decode the padding; the ciphertext has been encrypted using RSA, and he doesn't have the private key; so he can't get at the padded version.

Here's how OAEP works; you take the plaintext message $m$ to send, you pick a random value $r$, and compute the function:

$Padded = OAEP(m, r)$

(with H and G as parts of OAEP). Then, once we have that, we encrypt it using the base RSA public operation (using the public key):

$Ciphertext = RSA(PublicKey, Padded)$

The $Ciphertext$ is what's actually sent; because it is encrypted using RSA, the attacker cannot recover $Padded$.

So, if the OAEP operation doesn't prevent an attacker from decrypted the ciphertext in this straightforward manner, why is it there at all?

Well, raw RSA has some nastly properties (called an homeomorphic property), namely:

$RSA(k, A) \times RSA(k, B) = RSA(k, A\times B)$

(where $\times$ is implicitly modulo the public key modulus).

Because of this property, using raw RSA to directly encrypt plaintexts is almost always the wrong thing to do; there are clever ways to use this homeomorphic property to recover plaintext.

What the OAEP function does is try to mimic a random function between plaintexts and padded versions; because we present the raw RSA operation with effectively random texts, these homeomorphic properties are no concern.

-
For some reason I thought, the padding is done AFTER the message was encrypted! Now it makes sense. Thanks a lot for the detailed explanation! –  schrobe May 16 '13 at 22:36
How the legal receiver gets rid of the pad if he doesn't know the $r$? It just spits the $#pad$ bytes? That implied a public knowledge of the pad length. –  curious Dec 17 '13 at 9:58
@curious: the $OAEP$ function is designed to be invertable; however it does assume that the length of $r$ is publicly known. –  poncho Dec 17 '13 at 15:01