Optimal asymmetric encryption padding: Difference between revisions

Revision as of 01:30, 22 December 2024

Revision as of 01:31, 22 December 2024

Line 1:

{{Short description|Scheme often used with RSA encryption}}

{{redirect|OAEP|the division of the Thailand Ministry of Science Technology and Environment previously known as the Office of Atomic Energy for Peace|Office of Atoms for Peace}}

In [[cryptography]], '''Optimal Asymmetric Encryption Padding''' ('''OAEP''') is a [[padding (cryptography)|padding scheme]] often used together with [[RSA (cryptosystem)|RSA encryption]]. OAEP was introduced by [[Mihir Bellare|Bellare]] and [[Phillip Rogaway|Rogaway]],<ref>[[Mihir Bellare|M. Bellare]], [[Phillip Rogaway|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. [http://www-cse.ucsd.edu/users/mihir/papers/oaep.pdf full version (pdf)]</ref> and subsequently standardized in [[PKCS1|PKCS#1 v2]] and RFC 2437.

The OAEP algorithm is a form of [[Feistel network]] which uses a pair of [[random oracle]]s G and H to process the plaintext prior to [[asymmetric encryption]]. When combined with any secure [[trapdoor one-way function|trapdoor one-way permutation]] <math>f</math>, this processing is proved in the [[random oracle model]] to result in a combined scheme which is [[semantic security|semantically secure]] under [[chosen plaintext attack]] [[ciphertext indistinguishability|(IND-CPA)]]<nowiki/>. When implemented with certain trapdoor permutations (e.g., RSA), OAEP is also proven to be secure against [[chosen ciphertext attack]]. OAEP can be used to build an [[all-or-nothing transform]].

OAEP satisfies the following two goals:

Line 19 ⟶ 20:

==Algorithm==

[[File:OAEP encoding schema.svg|410x410px|thumb|right|OAEP encoding schema according to RFC 8017]]

In the diagram,

* ''MGF'' is the [[Mask generation function|mask generating function]], usually MGF1,

* ''Hash'' is the chosen [[Cryptographic hash function|hash function]],

* ''hLen'' is the length of the output of the hash function in bytes, Reincarnation hsppend

* ''k'' is the length of themodulusthe [[RSA (cryptosystem)|RSA]] modulus ''n'' in bytes,

* ''M'' is the message to be padded, with length ''mLen'' (at most <math>\mathrm{mLen}= k - 2 \cdot \mathrm{hLen} - 2</math> bytes),

* ''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),

* ''PS'' is a byte string of <math>k - \mathrm{mLen} - 2 \cdot \mathrm{hLen} - 2</math> null-bytes.

* ⊕ is an [[Exclusive or|XOR]]-Operation.

=== Encoding ===

Line 41 ⟶ 43:

# Use the mask generating function to generate a mask of length ''hLen'' for the seed: <math>\mathrm{seedMask} = \mathrm{MGF}(\mathrm{maskedDB}, \mathrm{hLen})</math>

# Mask the seed with the generated mask: <math>\mathrm{maskedSeed} = \mathrm{seed} \oplus \mathrm{seedMask}</math>

# The encoded (padded) message is the byte 0x00 concatenated with the ''maskedSeed'' and ''maskedDB'': <math>\mathrm{EM} = \mathrm{0x00} || \mathrm{maskedSeed} || \mathrm{maskedDB}</math>

=== Decoding ===

Decoding works by reversing the steps taken in the encoding algorithm:

Line 48 ⟶ 52:

# Generate the ''seedMask'' which was used to mask the ''seed'': <math>\mathrm{seedMask} = \mathrm{MGF}(\mathrm{maskedDB}, \mathrm{hLen})</math>

# To reverse step 8, recover the ''seed'' with the ''seedMask'': <math>\mathrm{seed} = \mathrm{maskedSeed} \oplus \mathrm{seedMask}</math>

# Generate the ''dbMask'' which was used to mask the data block: <math>\mathrm{dbMask} = \mathrm{MGF}(\mathrm{seed}, k - \mathrm{hLen} - 1)</math>

# To reverse step 6, recover the data block ''DB:'' <math>\mathrm{DB} = \mathrm{maskedDB} \oplus \mathrm{dbMask}</math>

# To reverse step 3, split the data block into its parts: <math>\mathrm{DB} = \mathrm{lHash'} || \mathrm{PS} || \mathrm{0x01} || \mathrm{M}</math>.

Line 61 ⟶ 65:

===Security===

The "[[All-or-nothing transform|all-or-nothing]]" 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.

===Implementation===

In the PKCS#1 standard, the random oracles are identical. The PKCS#1 standard further requires that the random oracles be [[MGF1]] with an appropriate hash function.<ref>{{Cite journal|url=https://eprint.iacr.org/2006/223.pdf| title=What Hashes Make RSA-OAEP Secure?|journal = IACR Cryptology ePrint Archive| last=Brown |first=Daniel R. L.| date=2006| language=en|access-date=2019-04-03}}</ref>

==See also==