Optimal asymmetric encryption padding

<h2 id="algorithm">Algorithm</h2>

In the diagram,

<ul><li>MGF is the <a href="/facts/Mask_generation_function/2KLvL81q">mask generating function</a>, usually MGF1,</li>
<li>Hash is the chosen <a href="/facts/Cryptographic_hash_function/cuxkgbST">hash function</a>,</li>
<li>hLen is the length of the output of the hash function in bytes,</li>
<li>k is the length of the <a href="/facts/RSA_(cryptosystem)/XTzyfHuq">RSA</a> modulus n in bytes,</li>
<li>M is the message to be padded, with length mLen (at most 
 
 
 
 
 m
 L
 e
 n
 
 =
 k
 −
 2
 ⋅
 
 h
 L
 e
 n
 
 −
 2
 
 
 {\displaystyle \mathrm {mLen} =k-2\cdot \mathrm {hLen} -2}
 
 bytes),</li>
<li>L is an optional label to be associated with the message (the label is the empty string by default and can be used to authenticate data without requiring encryption),</li>
<li>PS is a byte string of 
 
 
 
 k
 −
 
 m
 L
 e
 n
 
 −
 2
 ⋅
 
 h
 L
 e
 n
 
 −
 2
 
 
 {\displaystyle k-\mathrm {mLen} -2\cdot \mathrm {hLen} -2}
 
 null-bytes.</li>
<li>⊕ is an <a href="/facts/Exclusive_or/FHyr7hGQ">XOR</a>-Operation.</li></ul>
<h3>Encoding</h3>
RFC 8017<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> for PKCS#1 v2.2 specifies the OAEP scheme as follows for encoding:

<ol><li>Hash the label L using the chosen hash function: 
 
 
 
 
 l
 H
 a
 s
 h
 
 =
 
 H
 a
 s
 h
 
 (
 L
 )
 
 
 {\displaystyle \mathrm {lHash} =\mathrm {Hash} (L)}
 
</li>
<li>Generate a padding string PS consisting of 
 
 
 
 k
 −
 
 m
 L
 e
 n
 
 −
 2
 ⋅
 
 h
 L
 e
 n
 
 −
 2
 
 
 {\displaystyle k-\mathrm {mLen} -2\cdot \mathrm {hLen} -2}
 
 bytes with the value 0x00.</li>
<li>Concatenate lHash, PS, the single byte 0x01, and the message M to form a data block DB: 
 
 
 
 
 D
 B
 
 =
 
 l
 H
 a
 s
 h
 
 
 |
 
 
 |
 
 
 P
 S
 
 
 |
 
 
 |
 
 
 0
 x
 01
 
 
 |
 
 
 |
 
 
 M
 
 
 
 {\displaystyle \mathrm {DB} =\mathrm {lHash} ||\mathrm {PS} ||\mathrm {0x01} ||\mathrm {M} }
 
. This data block has length 
 
 
 
 k
 −
 
 h
 L
 e
 n
 
 −
 1
 
 
 {\displaystyle k-\mathrm {hLen} -1}
 
 bytes.</li>
<li>Generate a random seed of length hLen.</li>
<li>Use the mask generating function to generate a mask of the appropriate length for the data block: 
 
 
 
 
 d
 b
 M
 a
 s
 k
 
 =
 
 M
 G
 F
 
 (
 
 s
 e
 e
 d
 
 ,
 k
 −
 
 h
 L
 e
 n
 
 −
 1
 )
 
 
 {\displaystyle \mathrm {dbMask} =\mathrm {MGF} (\mathrm {seed} ,k-\mathrm {hLen} -1)}
 
</li>
<li>Mask the data block with the generated mask: 
 
 
 
 
 m
 a
 s
 k
 e
 d
 D
 B
 
 =
 
 D
 B
 
 ⊕
 
 d
 b
 M
 a
 s
 k
 
 
 
 {\displaystyle \mathrm {maskedDB} =\mathrm {DB} \oplus \mathrm {dbMask} }
 
</li>
<li>Use the mask generating function to generate a mask of length hLen for the seed: 
 
 
 
 
 s
 e
 e
 d
 M
 a
 s
 k
 
 =
 
 M
 G
 F
 
 (
 
 m
 a
 s
 k
 e
 d
 D
 B
 
 ,
 
 h
 L
 e
 n
 
 )
 
 
 {\displaystyle \mathrm {seedMask} =\mathrm {MGF} (\mathrm {maskedDB} ,\mathrm {hLen} )}
 
</li>
<li>Mask the seed with the generated mask: 
 
 
 
 
 m
 a
 s
 k
 e
 d
 S
 e
 e
 d
 
 =
 
 s
 e
 e
 d
 
 ⊕
 
 s
 e
 e
 d
 M
 a
 s
 k
 
 
 
 {\displaystyle \mathrm {maskedSeed} =\mathrm {seed} \oplus \mathrm {seedMask} }
 
</li>
<li>The encoded (padded) message is the byte 0x00 concatenated with the maskedSeed and maskedDB: 
 
 
 
 
 E
 M
 
 =
 
 0
 x
 00
 
 
 |
 
 
 |
 
 
 m
 a
 s
 k
 e
 d
 S
 e
 e
 d
 
 
 |
 
 
 |
 
 
 m
 a
 s
 k
 e
 d
 D
 B
 
 
 
 {\displaystyle \mathrm {EM} =\mathrm {0x00} ||\mathrm {maskedSeed} ||\mathrm {maskedDB} }
 
</li></ol>
<h3>Decoding</h3>
Decoding works by reversing the steps taken in the encoding algorithm:

<ol><li>Hash the label L using the chosen hash function: 
 
 
 
 
 l
 H
 a
 s
 h
 
 =
 
 H
 a
 s
 h
 
 (
 L
 )
 
 
 {\displaystyle \mathrm {lHash} =\mathrm {Hash} (L)}
 
</li>
<li>To reverse step 9, split the encoded message EM into the byte 0x00, the maskedSeed (with length hLen) and the maskedDB: 
 
 
 
 
 E
 M
 
 =
 
 0
 x
 00
 
 
 |
 
 
 |
 
 
 m
 a
 s
 k
 e
 d
 S
 e
 e
 d
 
 
 |
 
 
 |
 
 
 m
 a
 s
 k
 e
 d
 D
 B
 
 
 
 {\displaystyle \mathrm {EM} =\mathrm {0x00} ||\mathrm {maskedSeed} ||\mathrm {maskedDB} }
 
</li>
<li>Generate the seedMask which was used to mask the seed: 
 
 
 
 
 s
 e
 e
 d
 M
 a
 s
 k
 
 =
 
 M
 G
 F
 
 (
 
 m
 a
 s
 k
 e
 d
 D
 B
 
 ,
 
 h
 L
 e
 n
 
 )
 
 
 {\displaystyle \mathrm {seedMask} =\mathrm {MGF} (\mathrm {maskedDB} ,\mathrm {hLen} )}
 
</li>
<li>To reverse step 8, recover the seed with the seedMask: 
 
 
 
 
 s
 e
 e
 d
 
 =
 
 m
 a
 s
 k
 e
 d
 S
 e
 e
 d
 
 ⊕
 
 s
 e
 e
 d
 M
 a
 s
 k
 
 
 
 {\displaystyle \mathrm {seed} =\mathrm {maskedSeed} \oplus \mathrm {seedMask} }
 
</li>
<li>Generate the dbMask which was used to mask the data block: 
 
 
 
 
 d
 b
 M
 a
 s
 k
 
 =
 
 M
 G
 F
 
 (
 
 s
 e
 e
 d
 
 ,
 k
 −
 
 h
 L
 e
 n
 
 −
 1
 )
 
 
 {\displaystyle \mathrm {dbMask} =\mathrm {MGF} (\mathrm {seed} ,k-\mathrm {hLen} -1)}
 
</li>
<li>To reverse step 6, recover the data block DB: 
 
 
 
 
 D
 B
 
 =
 
 m
 a
 s
 k
 e
 d
 D
 B
 
 ⊕
 
 d
 b
 M
 a
 s
 k
 
 
 
 {\displaystyle \mathrm {DB} =\mathrm {maskedDB} \oplus \mathrm {dbMask} }
 
</li>
<li>To reverse step 3, split the data block into its parts: 
 
 
 
 
 D
 B
 
 =
 
 l
 H
 a
 s
 
 h
 ′
 
 
 
 |
 
 
 |
 
 
 P
 S
 
 
 |
 
 
 |
 
 
 0
 x
 01
 
 
 |
 
 
 |
 
 
 M
 
 
 
 {\displaystyle \mathrm {DB} =\mathrm {lHash'} ||\mathrm {PS} ||\mathrm {0x01} ||\mathrm {M} }
 
.
<ol><li>Verify that:
<ul><li>lHash' is equal to the computed lHash</li>
<li>PS only consists of bytes 0x00</li>
<li>PS and M are separated by the 0x01 byte and</li>
<li>the first byte of EM is the byte 0x00.</li></ul></li>
<li>If any of these conditions aren't met, then the padding is invalid.</li></ol></li></ol>
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 because the seed is randomly generated and influences the entire encoded message.

<h3>Security</h3>
The "<a href="/facts/All-or-nothing_transform/1tUzEuQ9">all-or-nothing</a>" security is from the fact that to recover M, one must recover the entire maskedDB and the entire maskedSeed; maskedDB is required to recover the seed from the maskedSeed, and the seed is required to recover the data block DB from maskedDB. Since any changed bit of a cryptographic hash completely changes the result, the entire maskedDB, and the entire maskedSeed must both be completely recovered.

<h3>Implementation</h3>
In the PKCS#1 standard, the random oracles are identical. The PKCS#1 standard further requires that the random oracles be <a href="/facts/MGF1/2KLvL81q">MGF1</a> with an appropriate hash function.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Key_encapsulation/uDR3scKh">Key encapsulation</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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, Springer-Verlag, 1995. full version (pdf) <a href="/wiki/Mihir_Bellare" target="_blank">/wiki/Mihir_Bellare</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">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) <a href="/wiki/Jacques_Stern" target="_blank">/wiki/Jacques_Stern</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Victor Shoup. OAEP Reconsidered. IBM Zurich Research Lab, Saumerstr. 4, 8803 Ruschlikon, Switzerland. September 18, 2001. full version (pdf) <a href="http://www.shoup.net/papers/oaep.pdf" target="_blank">http://www.shoup.net/papers/oaep.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">P. Paillier and J. Villar, Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption, Advances in Cryptology – Asiacrypt 2006. <a href="/wiki/Asiacrypt" target="_blank">/wiki/Asiacrypt</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">D. Brown, What Hashes Make RSA-OAEP Secure?, IACR ePrint 2006/233. <a href="http://eprint.iacr.org/2006/223" target="_blank">http://eprint.iacr.org/2006/223</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"Encryption Operation". PKCS #1: RSA Cryptography Specifications Version 2.2. IETF. November 2016. p. 22. sec. 7.1.1. doi:10.17487/RFC8017. RFC 8017. Retrieved 2022-06-04. <a href="https://datatracker.ietf.org/doc/html/rfc8017#section-7.1.1" target="_blank">https://datatracker.ietf.org/doc/html/rfc8017#section-7.1.1</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Brown, Daniel R. L. (2006). "What Hashes Make RSA-OAEP Secure?" (PDF). IACR Cryptology ePrint Archive. Retrieved 2019-04-03. <a href="https://eprint.iacr.org/2006/223.pdf" target="_blank">https://eprint.iacr.org/2006/223.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Optimal asymmetric encryption padding open-in-new

Optimal asymmetric encryption padding