Optimal Asymmetric Encryption Padding
OAEPのアルゴリズムはFeistel構造の一種であり、非対称暗号化に先立って二つのランダムオラクルを用いて平文を加工する。この結果を何らかの安全な落とし戸付き一方向性関数(英語版) f {\displaystyle f} と組み合わせれば、選択平文攻撃に対してランダムオラクルモデルで強秘匿性を持つ(IND-CPA)。また、ある種の落とし戸付き置換(例えばRSA)と共に実装された場合は、OAEPは選択暗号文攻撃に対しても安全であることが証明されている。OAEPはAONT(英語版)を構築するのに使うこともできる。
OAEPは次の二つの性質を満たす:
ランダムネスの要素を持っており、確定的暗号(英語版)方式(例えば古典的なRSA暗号など)を確率的暗号(英語版)方式に変換する用途に使える。
攻撃者が所与の落とし戸付き一方向性関数 f {\displaystyle f} の逆関数を構成できない限り、暗号文の部分的な解読(またはその他の情報漏洩)が不可能であることを保証する。
図中に現れる記号の意味は次の通り。
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(英語版)安全性を持つ理由は、m を復元するにはまず X 全体と Y 全体を復元しなければならないからである。Y から r を復元するには X が必要であり、X から m を復元するには r が必要である。暗号学的ハッシュ値が1ビットでも変わると結果は全く変わってしまうので、X 全体と Y 全体が両方とも完全に復元されなければならない。