Optimal Asymmetric Encryption Padding (略称：OAEP 、試訳：「最適非対称暗号化パディング」)は、暗号理論 において特殊な確定的暗号系 (落とし戸付部分領域一方向性置換) を安全に利用するための平文パディング手法の一つである。ミヒル・ベラーレ （英語版 ） フィリップ・ロガウェイ （英語版 ） [ 1] PKCS1 （英語版 ） RFC 2437 において標準化された。この手法を用いた暗号系はランダムオラクルモデルで適応的選択暗号文攻撃の下で暗号文識別不可能性 （英語版 ） RSA暗号 と組み合わせて使われることが多く、その場合はRSA-OAEPと呼ばれる。
OAEPのアルゴリズムはFeistel構造 の一種であり、非対称暗号化 に先立って二つのランダムオラクル を用いて平文 を加工する。この結果を何らかの安全な落とし戸付き一方向性関数 （英語版 ）
f
{\displaystyle f}
選択平文攻撃 に対してランダムオラクルモデルで強秘匿性 を持つ(IND-CPA )。また、ある種の落とし戸付き置換（例えばRSA）と共に実装された場合は、OAEPは選択暗号文攻撃 に対しても安全であることが証明されている。OAEPはAONT （英語版 ）
OAEPは次の二つの性質を満たす:
ランダムネス の要素を持っており、確定的暗号 （英語版 ） 確率的暗号 （英語版 ） 攻撃者が所与の落とし戸付き一方向性関数
f
{\displaystyle f}
OAEPの初期バージョン(Bellare/Rogaway, 1994)は、ランダムオラクルモデルで任意の落とし戸付き置換と組み合わせると"plaintext awareness （英語版 ） 選択暗号文攻撃 に対する識別不可能性（IND-CCA1 安全性）を持つとされた。また当初は適応的選択暗号文攻撃 に対しても識別不可能性（IND-CCA2 安全性）を持つと考えられていた。しかし2001年にビクター･シュープ （英語版 ） [ 2] ダン・ボウネイ （英語版 ） [ 3] IND-CCA2 になる。すなわち、藤崎、岡本、Pointcheval、Sternの4人は、OAEPは元となる暗号系が部分領域一方向性置換であるならばランダムオラクルモデルでIND-CCA2であること、およびRSA関数に関しては一方向性と部分領域一方向性が（多項式時間帰着の下で）等価であることを示した。結果、RSA-OAEPはランダムオラクルモデルでRSA仮定からIND-CCA2安全性を持つ[ 4]
近年では、標準モデル（即ち、ハッシュ関数がランダムオラクルではないモデル）においては、RSA問題の困難性が現在推測されている程度だと仮定した場合、RSA-OAEPのIND-CCA2安全性を証明することは不可能であることが示された[ 5] [ 6] [ 7]
OAEPの動作概念図 図中に現れる記号の意味は次の通り。
n はRSAの法などのビット数
k0 と k1 はプロトコルが定める整数
m は平文メッセージであり、n - k0 - k1 に等しいビット数を持つとする
G と H はランダムオラクルまたはプロトコルが定める何らかの暗号学的ハッシュ関数
r はランダムなビット列であり、k0 ビットの長さを持つとする 平文の符号化手順
平文に対して k1 個の 0 をパディングして、長さを n - k0 ビットとする。
G によって r の長さを k0 ビットから n - k0 ビットに拡張する。
m と G( r ) の間で排他的論理和 を取り、結果としてビット列 X を得る。
H によって X の長さを n - k0 ビットから k0 ビットに縮小する。
r と H( X ) の間で排他的論理和を取り、結果としてビット列 Y を得る。
X || Y を出力とする。（|| は左辺のビット列の右側に右辺のビット列を連結することを表す） 元の平文への復元手順
Y と H( X ) の間で排他的論理和を取り、結果として r を得る。
X と G( r ) の間で排他的論理和を取り、結果として m を得る。 これがAONT （英語版 ）
^ Bellare, Mihir; Rogaway, Phillip (1995), Eurocrypt '94 Proceedings Lecture Notes in Computer Science (SpringerVerlag) 950 , http://www-cse.ucsd.edu/users/mihir/papers/oae.pdf ^ Shoup, Victor (2001-09-18), OAEP Reconsidered , http://www.shoup.net/papers/oaep.pdf ^ Boneh, Dan (2001), CRYPTO 2001 LNCS (SpringerVerlag) 2139 : 275-291, http://rd.springer.com/chapter/10.1007%2F3-540-44647-8_17 ^ 藤崎, 英一郎; 岡本, 龍明; Pointcheval, David; Stern, Jacques (2001), RSA-OAEP is secure under the RSA assumption Lecture Notes in Computer Science (Springer-Verlag) 2139 : 260-274, http://eprint.iacr.org/2000/061.pdf ^ P. Paillier; J. Villar (2006), “Asiacrypt 2006” , Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption , https://www.iacr.org/archive/asiacrypt2006/42840253/42840253.pdf ^ D. Brown, “What Hashes Make RSA-OAEP Secure?” , IACR ePrint 2006/233 , http://eprint.iacr.org/2006/223 ^ E. Kiltz; K. Pietrzak (2009), EUROCRYPT 2009 LNCS 5479 : 389-406, https://www.iacr.org/archive/eurocrypt2009/54790389/54790389.pdf 2014年7月24日閲覧。
