Optimal asymmetric encryption padding: Difference between revisions

Revision as of 06:20, 22 August 2014

Revision as of 17:02, 10 August 2015

Line 1:

{{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 (algorithm)|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/oae.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)]]. When implemented with certain trapdoor permutations (e.g., RSA), OAEP is also proved secure against [[chosen ciphertext attack]]. OAEP can be used to build an [[All or nothing transform|all-or-nothing transform]].

OAEP satisfies the following two goals:

#Add an element of randomness which can be used to convert a [[deterministic encryption]] scheme (e.g., traditional [[RSA (algorithm)|RSA]]) into a [[probabilistic encryption|probabilistic]] scheme.

Line 11:

The original version of OAEP (Bellare/Rogaway, 1994) showed a form of "[[plaintext-aware encryption|plaintext awareness]]" (which they claimed implies security against [[chosen ciphertext attack]]) in the random oracle model when OAEP is used with any trapdoor permutation. Subsequent results contradicted this claim, showing that OAEP was only [[ciphertext indistinguishability|IND-CCA1]] secure. However, the original scheme was proved in the [[random oracle model]] to be [[ciphertext indistinguishability|IND-CCA2]] secure when OAEP is used with the RSA permutation using standard encryption exponents, as in the case of RSA-OAEP.<ref>

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. [http://eprint.iacr.org/2000/061.pdf full version (pdf)]</ref>

An improved scheme (called OAEP+) that works with any trapdoor one-way permutation was offered by [[Victor Shoup]] to solve this problem.<ref>

Victor Shoup. ''OAEP Reconsidered''. IBM Zurich Research Lab, Saumerstr. 4, 8803 Ruschlikon, Switzerland. September 18, 2001. [http://www.shoup.net/papers/oaep.pdf full version (pdf)]</ref>

More recent work has shown that in the [[Standard Model (cryptography)|standard model]] (that is, when hash functions are not modelled as random oracles), that it is impossible to prove the IND-CCA2 security of RSA-OAEP under the assumed hardness of the [[RSA problem]].<ref>

P. Paillier and J. Villar, ''Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption'', Advances in Cryptology -- [[Asiacrypt]] 2006.</ref><ref>

Line 21:

[[Image:Oaep-diagram-20080305.png|thumb|250px|right|OAEP Diagram]]

In the diagram,

* ''n'' is the number of bits in the RSA modulus.

* ''k''₀ and ''k''₁ are integers fixed by the protocol.

* ''m'' is the plaintext message, an (''n''&nbsp;&minus;−&nbsp;''k''₀&nbsp;&minus;−&nbsp;''k''₁ )-bit string

* ''G'' and ''H'' are typically some [[cryptographic hash function]]s fixed by the protocol.

To encode,

# messages are padded with ''k''₁ zeros to be ''n''&nbsp;&minus;−&nbsp;''k''₀ bits in length.

# ''r'' is a random ''k''₀-bit string

# ''G'' expands the ''k''₀ bits of ''r'' to ''n''&nbsp;&minus;−&nbsp;''k''₀ bits.

# ''X'' = ''m''00..0 ⊕ ''G''(''r'')

# ''H'' reduces the ''n''&nbsp;&minus;−&nbsp;''k''₀ bits of ''X'' to ''k''₀ bits.

# ''Y'' = ''r'' ⊕ ''H''(''X'')

# The output is ''X'' || ''Y'' where ''X'' is shown in the diagram as the leftmost block and ''Y'' as the rightmost block.