出典 しゅってん : フリー百科 ひゃっか 事典 じてん 『ウィキペディア(Wikipedia)』
Optimal Asymmetric Encryption Padding (略称 りゃくしょう :OAEP 、試 ためし 訳 やく :「最適 さいてき 非対称 ひたいしょう 暗号 あんごう 化 か パディング」)は、暗号 あんごう 理論 りろん において特殊 とくしゅ な確定 かくてい 的 てき 暗号 あんごう 系 けい (落 お とし戸 と 付 づけ 部分 ぶぶん 領域 りょういき 一方 いっぽう 向性 こうせい 置換 ちかん ) を安全 あんぜん に利用 りよう するための平文 へいぶん パディング手法 しゅほう の一 ひと つである。ミヒル・ベラーレ (英語 えいご 版 ばん ) とフィリップ・ロガウェイ (英語 えいご 版 ばん ) によって1994年 ねん に考案 こうあん され[ 1] 、後 のち にPKCS1 (英語 えいご 版 ばん ) と RFC 2437 において標準 ひょうじゅん 化 か された。この手法 しゅほう を用 もち いた暗号 あんごう 系 けい はランダムオラクルモデルで適応 てきおう 的 てき 選択 せんたく 暗号 あんごう 文 ぶん 攻撃 こうげき の下 した で暗号 あんごう 文 ぶん 識別 しきべつ 不可能 ふかのう 性 せい (英語 えいご 版 ばん ) (IND-CCA2安全 あんぜん 性 せい ) を持 も つ。RSA暗号 あんごう と組 く み合 あ わせて使 つか われることが多 おお く、その場合 ばあい はRSA-OAEPと呼 よ ばれる。
OAEPのアルゴリズムはFeistel構造 こうぞう の一種 いっしゅ であり、非対称 ひたいしょう 暗号 あんごう 化 か に先立 さきだ って二 ふた つのランダムオラクル を用 もち いて平文 へいぶん を加工 かこう する。この結果 けっか を何 なん らかの安全 あんぜん な落 お とし戸 と 付 つ き一方 いっぽう 向性 こうせい 関数 かんすう (英語 えいご 版 ばん )
f
{\displaystyle f}
と組 く み合 あ わせれば、選択 せんたく 平文 へいぶん 攻撃 こうげき に対 たい してランダムオラクルモデルで強 つよ 秘匿 ひとく 性 せい を持 も つ(IND-CPA )。また、ある種 しゅ の落 お とし戸 と 付 つ き置換 ちかん (例 たと えばRSA)と共 とも に実装 じっそう された場合 ばあい は、OAEPは選択 せんたく 暗号 あんごう 文 ぶん 攻撃 こうげき に対 たい しても安全 あんぜん であることが証明 しょうめい されている。OAEPはAONT (英語 えいご 版 ばん ) を構築 こうちく するのに使 つか うこともできる。
OAEPは次 つぎ の二 ふた つの性質 せいしつ を満 み たす:
ランダムネス の要素 ようそ を持 も っており、確定 かくてい 的 てき 暗号 あんごう (英語 えいご 版 ばん ) 方式 ほうしき (例 たと えば古典 こてん 的 てき なRSA暗号 あんごう など)を確 かく 率 りつ 的 てき 暗号 あんごう (英語 えいご 版 ばん ) 方式 ほうしき に変換 へんかん する用途 ようと に使 つか える。
攻撃 こうげき 者 しゃ が所与 しょよ の落 お とし戸 と 付 つ き一方 いっぽう 向性 こうせい 関数 かんすう
f
{\displaystyle 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の法 ほう などのビット数 すう
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 全体 ぜんたい が両方 りょうほう とも完全 かんぜん に復元 ふくげん されなければならない。
^ 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 , http://www-cse.ucsd.edu/users/mihir/papers/oae.pdf
^ 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, 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 , “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 , 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 , “On the security of padding-based encryption schemes (Or: why we cannot prove OAEP secure in the standard model)”, LNCS 5479 : 389-406, https://www.iacr.org/archive/eurocrypt2009/54790389/54790389.pdf 2014年 ねん 7月 がつ 24日 にち 閲覧 えつらん 。
アルゴリズム 理論 りろん 標準 ひょうじゅん 化 か 関連 かんれん 項目 こうもく
カテゴリ