How to Encrypt Properly with RSA
David Pointcheval · 2002
In 1993, Bellare and Rogaway formalized the concept of a random oracle, imported from complexity theory for cryptographic purposes. This new tool allowed them to present several asymmetric encryption and signature schemes that are both ecien t and provably secure (in the random oracle model). The Optimal Asymmetric Encryption Padding (OAEP) is the most signican t application of the random ora- cle model to date. It gives an ecien t RSA encryption scheme with a strong security guarantee (semantic security against chosen-ciphertext attacks). After Bleichenbacher's devastating attack on RSA{PKCS #1 v1.5 in 1998, RSA{OAEP became the natural successor (RSA{PKCS #1 v2.0) and thus a de facto international standard. Surpris- ingly, Shoup recently showed that the original proof of security for OAEP is incorrect. Without a proof, RSA{OAEP cannot be trusted to provide an adequate level of security. Luckily, shortly after Shoup's discovery a formal and complete proof was found in joint work by the author and others that rearmed the strong level of security provided by RSA{OAEP. However, this new security proof still does not guarantee security for key sizes used in practice due to the ineciency of the security reduction (the reduction to inverting RSA takes quadratic time). Recent alternatives to OAEP, such as OAEP + , SAEP + , and REACT, admit more ecien t proofs and thus provide adequate security for key sizes used in practice.