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]