I was studying OAEP and see we introduce a random value $r$ when computing the padding. See the figure below from Wikipedia

So if we are adding randomness to encryption, how could this ciphertext be mapped to plaintext? I understand a plaintext $m$ being mapped to numerous $c_i$ ?

Also to decrypt, don't we need to know $r$? In that case $r$ becomes a key https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding


To decrypt the ciphertext you definitely need to recover the random token $r$. But $r = Y \oplus H(X)$. Then knowing $r$ the padded message can be recovered as $m0\dots0 = X \oplus G(r)$. The decryptor only need to known the size of the random token $r$ and this is usually part of the standard. Of course the standard has to define the $F$ and $G$ functions and how to pad the message. The padding process has to be such that unpadding the message after the decryption is deterministic and unique.

The randomness added to the encryption process makes impossible for an attacker having access to an encryption oracle (or observing a lot of messages and their effect) to create a dictionary of corresponding couples of $(m_i, c_i)_{i\in S}$ where $c_i = Enc(m_i)$. This property has been defined for the first time in the paper by Goldwasser and Micali "Probabilistic Encryption" (Shafi Goldwasser and Silvio Micali, Probabilistic Encryption, Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984)

  • $\begingroup$ Ah ok I should've distinguished $r$ being a part of the standard and the size of $r$ being a part of the standard. Thanks $\endgroup$
    – kuzdogan
    Feb 21 '19 at 12:42

You are right that in decryption we need to know the value of $r$, but this can be easily recovered from the ciphertext alone, in fact, $r = Y \oplus H(X)$ and both $X,Y,H$ are known. Then the message can be recovered as $m00..0 = X \oplus G(r)$

Now, you might wonder how to depad from zeros, or equivalenty how can the decryptor distinguish between $X$ and $Y$. Well, in fact, the real OAEP is more complicated than the wikipedia figure: OAEP padding from PKCS#1

Here, $lHash$ is the hash of the label, $PS$ are zero octets to pad, $01$ is a $0x01$ byte used to remove the $PS$ padding and $M$ is the original message.

The sizes of $seed$ and $lHash$ depend only on the size of output of the selected hash function, which should be known to the decryptor.

  • $\begingroup$ Note lhash and mgf can use different hashes, although it's not clear why you would want to, and I've seen about a dozen stack Qs caused by doing so unintended and unaware. Also PKCS1v2.0 originally said 'parameters' instead of 'label', which is why the ASN.1 still uses PSource... and PSpecified.... $\endgroup$ Feb 22 '19 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.