出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/06/04 13:53 UTC 版)

図中に現れる記号の意味は次の通り。

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

平文の符号化手順

1. 平文に対して k₁ 個の 0 をパディングして、長さを n - k₀ ビットとする。
2. G によって r の長さを k₀ ビットから n - k₀ ビットに拡張する。
3. m と G( r ) の間で排他的論理和を取り、結果としてビット列 X を得る。
4. H によって X の長さを n - k₀ ビットから k₀ ビットに縮小する。
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

参考文献

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, http://www-cse.ucsd.edu/users/mihir/papers/oae.pdf 
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, http://rd.springer.com/chapter/10.1007%2F3-540-44647-8_17 
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, https://www.iacr.org/archive/asiacrypt2006/42840253/42840253.pdf 
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, https://www.iacr.org/archive/eurocrypt2009/54790389/54790389.pdf 2014年7月24日閲覧。