Optimal Asymmetric Encryption Padding

Optimal Asymmetric Encryption Padding (略称りゃくしょう：OAEP、試ためし訳やく：「最適さいてき非対称ひたいしょう暗号あんごう化かパディング」)は、暗号あんごう理論りろんにおいて特殊とくしゅな確定かくてい的てき暗号あんごう系けい (落おとし戸と付づけ部分ぶぶん領域りょういき一方いっぽう向性こうせい置換ちかん) を安全あんぜんに利用りようするための平文へいぶんパディング手法しゅほうの一ひとつである。ミヒル・ベラーレ（英語えいご版ばん）とフィリップ・ロガウェイ（英語えいご版ばん）によって1994年ねんに考案こうあんされ^[1]、後のちにPKCS1（英語えいご版ばん）と RFC 2437において標準ひょうじゅん化かされた。この手法しゅほうを用もちいた暗号あんごう系けいはランダムオラクルモデルで適応てきおう的てき選択せんたく暗号あんごう文ぶん攻撃こうげきの下したで暗号あんごう文ぶん識別しきべつ不可能ふかのう性せい（英語えいご版ばん） (IND-CCA2安全あんぜん性せい) を持もつ。RSA暗号あんごうと組くみ合あわせて使つかわれることが多おおく、その場合ばあいはRSA-OAEPと呼よばれる。

概要がいよう

OAEPのアルゴリズムはFeistel構造こうぞうの一種いっしゅであり、非対称ひたいしょう暗号あんごう化かに先立さきだって二ふたつのランダムオラクルを用もちいて平文へいぶんを加工かこうする。この結果けっかを何なんらかの安全あんぜんな落おとし戸と付つき一方いっぽう向性こうせい関数かんすう（英語えいご版ばん） $f$ と組くみ合あわせれば、選択せんたく平文へいぶん攻撃こうげきに対たいしてランダムオラクルモデルで強つよ秘匿ひとく性せいを持もつ(IND-CPA)。また、ある種しゅの落おとし戸と付つき置換ちかん（例たとえばRSA）と共ともに実装じっそうされた場合ばあいは、OAEPは選択せんたく暗号あんごう文ぶん攻撃こうげきに対たいしても安全あんぜんであることが証明しょうめいされている。OAEPはAONT（英語えいご版ばん）を構築こうちくするのに使つかうこともできる。

OAEPは次つぎの二ふたつの性質せいしつを満みたす:

ランダムネスの要素ようそを持もっており、確定かくてい的てき暗号あんごう（英語えいご版ばん）方式ほうしき（例たとえば古典こてん的てきなRSA暗号あんごうなど）を確かく率りつ的てき暗号あんごう（英語えいご版ばん）方式ほうしきに変換へんかんする用途ようとに使つかえる。
攻撃こうげき者しゃが所与しょよの落おとし戸と付つき一方いっぽう向性こうせい関数かんすう $f$ の逆ぎゃく関数かんすうを構成こうせいできない限かぎり、暗号あんごう文ぶんの部分ぶぶん的てきな解読かいどく（またはその他たの情報じょうほう漏洩ろうえい）が不可能ふかのうであることを保証ほしょうする。

歴史れきし

OAEPの初期しょきバージョン(Bellare/Rogaway, 1994)は、ランダムオラクルモデルで任意にんいの落おとし戸と付つき置換ちかんと組くみ合あわせると"plaintext awareness（英語えいご版ばん）"を持もち、これにより選択せんたく暗号あんごう文ぶん攻撃こうげきに対たいする識別しきべつ不可能ふかのう性せい（IND-CCA1安全あんぜん性せい）を持もつとされた。また当初とうしょは適応てきおう的てき選択せんたく暗号あんごう文ぶん攻撃こうげきに対たいしても識別しきべつ不可能ふかのう性せい（IND-CCA2安全あんぜん性せい）を持もつと考かんがえられていた。しかし2001年ねんにビクター･シュープ（英語えいご版ばん）がIND-CCA2ではないことを示しめし、改良かいりょう版ばんとしてOAEP+を提案ていあんした^[2]。同どう時期じきにダン・ボウネイ（英語えいご版ばん）もSAEPおよびSAEP+を提案ていあんした^[3]。但ただし、元もとのOAEPもランダムオラクルモデルで標準ひょうじゅん的てきな暗号あんごう化か指数しすうを用もちいたRSA置換ちかんと組くみ合あわせた場合ばあいは、たまたま（主おもにOAEPではなくRSA関数かんすうの代数だいすう的てきな性質せいしつにより）IND-CCA2になる。すなわち、藤崎ふじさき、岡本おかもと、Pointcheval、Sternの4人にんは、OAEPは元もととなる暗号あんごう系けいが部分ぶぶん領域りょういき一方いっぽう向性こうせい置換ちかんであるならばランダムオラクルモデルでIND-CCA2であること、およびRSA関数かんすうに関かんしては一方いっぽう向性こうせいと部分ぶぶん領域りょういき一方いっぽう向性こうせいが（多項式たこうしき時間じかん帰着きちゃくの下したで）等価とうかであることを示しめした。結果けっか、RSA-OAEPはランダムオラクルモデルでRSA仮定かていからIND-CCA2安全あんぜん性せいを持もつ^[4]。

近年きんねんでは、標準ひょうじゅんモデル（即すなわち、ハッシュ関数かんすうがランダムオラクルではないモデル）においては、RSA問題もんだいの困難こんなん性せいが現在げんざい推測すいそくされている程度ていどだと仮定かていした場合ばあい、RSA-OAEPのIND-CCA2安全あんぜん性せいを証明しょうめいすることは不可能ふかのうであることが示しめされた^[5]^[6]。また、OAEPを含ふくむパディング方式ほうしき全般ぜんぱんと理想りそう的てきな落おとし戸と付つき置換ちかんの組くみ合あわせについて、標準ひょうじゅんモデルでは安全あんぜん性せいを証明しょうめい不可能ふかのうとする結果けっかが得えられている^[7]。

OAEPの動作どうさ概念がいねん図ず

図ず中ちゅうに現あらわれる記号きごうの意味いみは次つぎの通とおり。

n はRSAの法ほうなどのビット数すう
k₀ と k₁ はプロトコルが定さだめる整数せいすう
m は平文へいぶんメッセージであり、n - k₀ - k₁ に等ひとしいビット数すうを持もつとする
G と H はランダムオラクルまたはプロトコルが定さだめる何なんらかの暗号あんごう学がく的てきハッシュ関数かんすう
r はランダムなビット列びっとれつであり、k₀ ビットの長ながさを持もつとする

平文へいぶんの符号ふごう化か手順てじゅん

平文へいぶんに対たいして k₁ 個この 0 をパディングして、長ながさを n - k₀ ビットとする。
G によって r の長ながさを k₀ ビットから n - k₀ ビットに拡張かくちょうする。
m と G( r ) の間あいだで排他はいた的てき論理ろんり和わを取とり、結果けっかとしてビット列びっとれつ X を得える。
H によって X の長ながさを n - k₀ ビットから k₀ ビットに縮小しゅくしょうする。
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 全体ぜんたいが両方りょうほうとも完全かんぜんに復元ふくげんされなければならない。

参考さんこう

参考さんこう文献ぶんけん

^ Bellare, Mihir; Rogaway, Phillip (1995), Eurocrypt '94 Proceedings, in A. De Santis, “Optimal Asymmetric Encryption -- How to encrypt with RSA”, Lecture Notes in Computer Science (SpringerVerlag) 950
^ Shoup, Victor (2001-09-18), OAEP Reconsidered, Saumerstr. 4, 8803 Ruschlikon, Switzerland: IBM Zurich Research Lab, http://www.shoup.net/papers/oaep.pdf
^ Boneh, Dan (2001), CRYPTO 2001, “Simplified OAEP for the RSA and Rabin functions”, LNCS (SpringerVerlag) 2139: 275-291
^ 藤崎ふじさき, 英一郎えいいちろう; 岡本おかもと, 龍りゅう明あきら; Pointcheval, David; Stern, Jacques (2001), RSA-OAEP is secure under the RSA assumption, “Advances in Cryptology — CRYPTO 2001”, 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
^ 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, “On the security of padding-based encryption schemes (Or: why we cannot prove OAEP secure in the standard model)”, LNCS 5479: 389-406 2014年ねん7月がつ24日にち閲覧えつらん。

[1] Bellare, Mihir; Rogaway, Phillip (1995), Eurocrypt '94 Proceedings, in A. De Santis, “Optimal Asymmetric Encryption -- How to encrypt with RSA”, Lecture Notes in Computer Science (SpringerVerlag) 950

[2] Shoup, Victor (2001-09-18), OAEP Reconsidered, Saumerstr. 4, 8803 Ruschlikon, Switzerland: IBM Zurich Research Lab, http://www.shoup.net/papers/oaep.pdf

[3] Boneh, Dan (2001), CRYPTO 2001, “Simplified OAEP for the RSA and Rabin functions”, LNCS (SpringerVerlag) 2139: 275-291

[4] 藤崎ふじさき, 英一郎えいいちろう; 岡本おかもと, 龍りゅう明あきら; Pointcheval, David; Stern, Jacques (2001), RSA-OAEP is secure under the RSA assumption, “Advances in Cryptology — CRYPTO 2001”, Lecture Notes in Computer Science (Springer-Verlag) 2139: 260-274, http://eprint.iacr.org/2000/061.pdf

[5] P. Paillier; J. Villar (2006), “Asiacrypt 2006”, Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption

[6] D. Brown, “What Hashes Make RSA-OAEP Secure?”, IACR ePrint 2006/233, http://eprint.iacr.org/2006/223

[7] E. Kiltz; K. Pietrzak (2009), EUROCRYPT 2009, “On the security of padding-based encryption schemes (Or: why we cannot prove OAEP secure in the standard model)”, LNCS 5479: 389-406 2014年ねん7月がつ24日にち閲覧えつらん。

[1]

[2]

[3]

[4]

[5]

[6]

[7]