Optimal Asymmetric Encryption Padding
Optimal Asymmetric Encryption Padding（OAEP、最適非対称暗号化パディング）は、暗号理論において、特殊な決定性暗号系を安全に利用するための平文パディング手法です。1994年にミヒル・ベラーレとフィリップ・ロガウェイによって考案され、後にPKCS1とRFC 2437で標準化されました。
この手法を用いた暗号系は、ランダムオラクルモデルにおいて、適応的選択暗号文攻撃に対する識別不可能性（IND-CCA2安全性）を有します。特にRSA[[暗号]]と組み合わせて使われることが多く、その場合はRSA-OAEPと呼ばれています。
OAEPのアルゴリズムは、Feistel構造の一種であり、非対称暗号化に先立って、2つのランダムオラクルを用いて平文を加工します。この結果を、安全な落とし戸付き一方向性関数と組み合わせることで、選択平文攻撃に対してランダムオラクルモデルで高い秘匿性（IND-CPA）を確保できます。
また、RSAなどの落とし戸付き置換と組み合わせて実装した場合、OAEPは選択暗号文攻撃に対しても安全であることが証明されています。さらに、OAEPはAONT（All-or-Nothing Transform）を構築するのにも利用できます。
OAEPは主に以下の2つの性質を満たします。
1. ランダム性の要素を持ち、決定的な暗号方式（古典的なRSA[[暗号]]など）を確率的な暗号方式に変換します。
2. 攻撃者が、与えられた落とし戸付き一方向性関数の逆関数を構成できない限り、暗号文の部分的な解読や情報漏洩を不可能にします。
初期バージョンのOAEP（Bellare/Rogaway, 1994）は、ランダムオラクルモデルで任意の落とし戸付き置換と組み合わせると、plaintext awarenessを持ち、これにより選択暗号文攻撃に対する識別不可能性（IND-CCA1安全性）を持つとされていました。当初は適応的選択暗号文攻撃に対しても識別不可能性（IND-CCA2安全性）を持つと考えられていましたが、2001年にビクター・シュープがIND-CCA2ではないことを示し、改良版としてOAEP+が提案されました。同時期にダン・ボウネイもSAEPおよびSAEP+を提案しています。
しかし、元のOAEPも、ランダムオラクルモデルで標準的な暗号化指数を用いたRSA置換と組み合わせた場合は、結果としてIND-CCA2となることが判明しました。藤崎、岡本、Pointcheval、Sternの研究により、OAEPは元となる暗号系が部分領域一方向性置換であるならば、ランダムオラクルモデルでIND-CCA2であること、およびRSA関数に関しては一方向性と部分領域一方向性が（多項式時間帰着の下で）等価であることが示されました。結果として、RSA-OAEPはランダムオラクルモデルでRSA仮定からIND-CCA2安全性を持つことが証明されています。
近年では、標準モデル（ハッシュ関数がランダムオラクルではないモデル）において、RSA問題の困難性が現在推測されている程度だと仮定した場合、RSA-OAEPのIND-CCA2安全性を証明することは不可能であることが示されています。さらに、OAEPを含むパディング方式全般と理想的な落とし戸付き置換の組み合わせについて、標準モデルでは安全性を証明することができないという結果も得られています。
OAEPの動作概念図を以下に示します。この図に現れる記号の意味は以下の通りです。
n: RSAの法などのビット数
k0, k1: プロトコルが定める整数
m: 平文メッセージであり、n - k0 - k1に等しいビット数を持つ
G, H: ランダムオラクルまたはプロトコルが定める暗号学的ハッシュ関数
r: ランダムなビット列であり、k0ビットの長さを持つ
1. 平文に対してk1個の0をパディングし、長さをn - k0ビットにします。
2. Gによってrの長さをk0ビットからn - k0ビットに拡張します。
3. mとG(r)の間で排他的論理和を取り、結果としてビット列Xを得ます。
4. HによってXの長さをn - k0ビットからk0ビットに縮小します。
5. rとH(X)の間で排他的論理和を取り、結果としてビット列Yを得ます。
6. X || Yを出力します（||はビット列の連結を表す）。
1. YとH(X)の間で排他的論理和を取り、結果としてrを得ます。
2. XとG(r)の間で排他的論理和を取り、結果としてmを得ます。
これがAONT安全性を持つ理由は、mを復元するにはまずX全体とY全体を復元する必要があるためです。Yからrを復元するにはXが必要であり、Xからmを復元するにはrが必要です。暗号学的ハッシュ値が1ビットでも変わると結果が大きく変わるため、XとYの両方を完全に復元する必要があります。
http://itpro.nikkeibp.co.jp/word/page/10005074/
http://cryptrec.nict.go.jp/rep_ID0006.pdf
Bellare, M., & Rogaway, P. (1994). Optimal Asymmetric Encryption. In Advances in Cryptology — EUROCRYPT’94 (pp. 92–111). Springer, Berlin, Heidelberg.
この手法を用いた暗号系は、ランダムオラクルモデルにおいて、適応的選択暗号文攻撃に対する識別不可能性（IND-CCA2安全性）を有します。特にRSA[[暗号]]と組み合わせて使われることが多く、その場合はRSA-OAEPと呼ばれています。
OAEPの概要
OAEPのアルゴリズムは、Feistel構造の一種であり、非対称暗号化に先立って、2つのランダムオラクルを用いて平文を加工します。この結果を、安全な落とし戸付き一方向性関数と組み合わせることで、選択平文攻撃に対してランダムオラクルモデルで高い秘匿性（IND-CPA）を確保できます。
また、RSAなどの落とし戸付き置換と組み合わせて実装した場合、OAEPは選択暗号文攻撃に対しても安全であることが証明されています。さらに、OAEPはAONT（All-or-Nothing Transform）を構築するのにも利用できます。
OAEPは主に以下の2つの性質を満たします。
1. ランダム性の要素を持ち、決定的な暗号方式（古典的なRSA[[暗号]]など）を確率的な暗号方式に変換します。
2. 攻撃者が、与えられた落とし戸付き一方向性関数の逆関数を構成できない限り、暗号文の部分的な解読や情報漏洩を不可能にします。
歴史
初期バージョンのOAEP（Bellare/Rogaway, 1994）は、ランダムオラクルモデルで任意の落とし戸付き置換と組み合わせると、plaintext awarenessを持ち、これにより選択暗号文攻撃に対する識別不可能性（IND-CCA1安全性）を持つとされていました。当初は適応的選択暗号文攻撃に対しても識別不可能性（IND-CCA2安全性）を持つと考えられていましたが、2001年にビクター・シュープがIND-CCA2ではないことを示し、改良版としてOAEP+が提案されました。同時期にダン・ボウネイもSAEPおよびSAEP+を提案しています。
しかし、元のOAEPも、ランダムオラクルモデルで標準的な暗号化指数を用いたRSA置換と組み合わせた場合は、結果としてIND-CCA2となることが判明しました。藤崎、岡本、Pointcheval、Sternの研究により、OAEPは元となる暗号系が部分領域一方向性置換であるならば、ランダムオラクルモデルでIND-CCA2であること、およびRSA関数に関しては一方向性と部分領域一方向性が（多項式時間帰着の下で）等価であることが示されました。結果として、RSA-OAEPはランダムオラクルモデルでRSA仮定からIND-CCA2安全性を持つことが証明されています。
近年では、標準モデル（ハッシュ関数がランダムオラクルではないモデル）において、RSA問題の困難性が現在推測されている程度だと仮定した場合、RSA-OAEPのIND-CCA2安全性を証明することは不可能であることが示されています。さらに、OAEPを含むパディング方式全般と理想的な落とし戸付き置換の組み合わせについて、標準モデルでは安全性を証明することができないという結果も得られています。
OAEPの動作概念図
OAEPの動作概念図を以下に示します。この図に現れる記号の意味は以下の通りです。
n: RSAの法などのビット数
k0, k1: プロトコルが定める整数
m: 平文メッセージであり、n - k0 - k1に等しいビット数を持つ
G, H: ランダムオラクルまたはプロトコルが定める暗号学的ハッシュ関数
r: ランダムなビット列であり、k0ビットの長さを持つ
平文の符号化手順
1. 平文に対してk1個の0をパディングし、長さをn - k0ビットにします。
2. Gによってrの長さをk0ビットからn - k0ビットに拡張します。
3. mとG(r)の間で排他的論理和を取り、結果としてビット列Xを得ます。
4. HによってXの長さをn - k0ビットからk0ビットに縮小します。
5. rとH(X)の間で排他的論理和を取り、結果としてビット列Yを得ます。
6. X || Yを出力します（||はビット列の連結を表す）。
元の平文への復元手順
1. YとH(X)の間で排他的論理和を取り、結果としてrを得ます。
2. XとG(r)の間で排他的論理和を取り、結果としてmを得ます。
これがAONT安全性を持つ理由は、mを復元するにはまずX全体とY全体を復元する必要があるためです。Yからrを復元するにはXが必要であり、Xからmを復元するにはrが必要です。暗号学的ハッシュ値が1ビットでも変わると結果が大きく変わるため、XとYの両方を完全に復元する必要があります。
参考資料
http://itpro.nikkeibp.co.jp/word/page/10005074/
http://cryptrec.nict.go.jp/rep_ID0006.pdf
参考文献
Bellare, M., & Rogaway, P. (1994). Optimal Asymmetric Encryption. In Advances in Cryptology — EUROCRYPT’94 (pp. 92–111). Springer, Berlin, Heidelberg.
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。