Optimal Asymmetric Encryption Padding

Optimal Asymmetric Encryption Padding

: "This article is about the padding scheme used in public-key cryptography. For the division of the Thailand Ministry of Science Technology and Environment entitled Office of Atomic Energy for Peace, see [http://www.oaep.go.th/english/index.html] ."

In cryptography, Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway. [
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. [http://www-cse.ucsd.edu/users/mihir/papers/oae.pdf full version (pdf)]
]

The OAEP algorithm is a form of Feistel network which uses a pair of random oracles G and H to process the plaintext prior to asymmetric encryption. When combined with any secure trapdoor one-way permutation f, this processing is proved in the random oracle model to result in a combined scheme which is semantically secure under chosen plaintext attack (IND-CPA). When implemented with certain trapdoor permutations (e.g., RSA), OAEP is also proved secure against chosen ciphertext attack.

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) into a probabilistic scheme.
#Prevent partial decryption of ciphertexts (or other information leakage) by ensuring that an adversary cannot recover any portion of the plaintext without being able to invert the trapdoor one-way permutation f.

The original version of OAEP (Bellare/Rogaway, 1994) claimed a form of "plaintext awareness" (that implies security against chosen ciphertext attack) in the random oracle model when OAEP is used with any trapdoor permutation. Subsequent results contradicted this result, showing the OAEP was only IND-CPA2 secure. However, the original scheme was proved in the random oracle model to be secure when OAEP is used with the RSA permutation using standard encryption exponents, as in the case of RSA-OAEP. [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)] ] An improved scheme (called OAEP+) that works with any trapdoor one-way permutation was offered by Victor Shoup to solve this problem. [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)] ] More recent work has shown that in the 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. [ P. Paillier and J. Villar, "Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption", Advances in Cryptology -- Asiacrypt 2006.] [D. Brown, [http://eprint.iacr.org/2006/223 "What Hashes Make RSA-OAEP Secure?"] , IACR ePrint 2006/233. ]

Diagram of OAEP

In the diagram,
* n is the number of bits in the RSA modulus.
* k0 and k1 are integers fixed by the protocol.
* m is the plaintext message, a n - k0 - k1 bit string
* G and H are typically some cryptographic hash functions fixed by the protocol.

To encode,
# messages are padded with k1 zeros to be n - k0 bits in length.
# r is a random k0 bit string
# G expands the k0 bits of r to n - k0 bits.
# X = m00..0 ⊕ G(r)
# H reduces the n - k0 bits of X to k0 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.

To decode,
# recover the random string as r = Y ⊕ H(X)
# recover the message as m00..0 = X ⊕ G(r)

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Optimal asymmetric encryption padding — This article is about the padding scheme used in public key cryptography. For the division of the Thailand Ministry of Science Technology and Environment entitled Office of Atomic Energy for Peace, see [1]. In cryptography, Optimal Asymmetric… …   Wikipedia

  • Optimal Asymmetric Encryption Padding — En cryptologie, l OAEP (Optimal Asymmetric Encryption Padding) est un schéma de remplissage, utilisé généralement avec le chiffrement RSA. Cet algorithme fut introduit en 1994 par Mihir Bellare et Phil Rogaway[1]. L OAEP est une forme de réseau… …   Wikipédia en Français

  • Probabilistic encryption — is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts. The term probabilistic encryption is typically used in reference to public key… …   Wikipedia

  • OAEP — Optimal Asymmetric Encryption Padding En cryptologie, l OAEP (Optimal Asymmetric Encryption Padding) est un schéma de remplissage, utilisé généralement avec un encryptage RSA. Cet algorithme fut introduit en 1994 par Mihir Bellare et Phil… …   Wikipédia en Français

  • Oaep — Optimal Asymmetric Encryption Padding En cryptologie, l OAEP (Optimal Asymmetric Encryption Padding) est un schéma de remplissage, utilisé généralement avec un encryptage RSA. Cet algorithme fut introduit en 1994 par Mihir Bellare et Phil… …   Wikipédia en Français

  • RSA — In cryptography, RSA is an algorithm for public key cryptography. It is the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA is widely used in electronic… …   Wikipedia

  • Semantic security — is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message… …   Wikipedia

  • OAEP — #REDIRECT Optimal Asymmetric Encryption PaddingOAEP can mean more than one thing:* Optimal Asymmetric Encryption Padding * Office of Atomic Energy for Peace [http://www.oaep.go.th/english/index.html] , a division of the Thailand Ministry of… …   Wikipedia

  • RSA-Kryptosystem — RSA ist ein asymmetrisches kryptographisches Verfahren, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann.[1] Es verwendet ein Schlüsselpaar, bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder… …   Deutsch Wikipedia

  • RSA-Algorithmus — RSA ist ein asymmetrisches Kryptosystem, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann. Es verwendet ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”