Optimal Asymmetric Encryption Padding

Optimal Asymmetric Encryption Padding (약칭：OAEP, 시역：「최적 비대칭 암호화 패딩」)은, 암호 이론에 있어 특수한 확정적 암호계(흘림호부부분 영역 한방향성 치환)를 안전하게 이용하기 위한 평문패딩 방법의 하나이다.미힐・베라레(영문판)와 필립・로가 웨이(영문판)에 의해서 1994년에 고안 되어[¹], 후에 PKCS1(영문판)와 RFC 2437에 대해 표준화 되었다.이 수법을 이용한 암호계는 랜덤 오라클 모델로 적응적 선택 암호문 공격아래에서 암호문 식별 불가능성(영문판) (IND-CCA2 안전성)를 가진다.RSA 암호와 조합해서 사용되는 것이 많아, 그 경우는 RSA-OAEP로 불린다.

목차

개요

OAEP의 알고리즘은 Feistel 구조의 일종이며, 비대칭 암호화에 앞서 두 개의 랜덤 오라클을 이용해 평문을 가공한다.이 결과를 어떠한 안전한 흘림문 한방향성 함수(영문판) ${\displaystyle f}$  (와)과 조합하면, 선택평문공격에 대해서 랜덤 오라클 모델로 강은닉성을 가진다(IND-CPA).또, 어떤 종류의 흘림문 치환(예를 들면 RSA)과 함께 실장되었을 경우는, OAEP는 선택 암호문 공격에 대해서도 안전하다라고 하는 것이 증명되고 있다.OAEP는 AONT(영문판)를 구축하는데 사용할 수도 있다.

OAEP는 다음 두 개의 성질을 채운다:

1. 란담네스의 요소를 가지고 있어 확정적 암호(영문판) 방식(예를 들면 고전적인 RSA 암호등)을 확률적 암호(영문판) 방식으로 변환하는 용도에 사용할 수 있다.
2. 공격자가 소여의 흘림문 한방향성 함수 ${\displaystyle f}$  의 역함수를 구성할 수 없는 한, 암호문의 부분적인 해독(또는 그 외의 정보 누설)이 불가능한 것을 보증한다.

역사

OAEP의 초기 버전(Bellare/Rogaway, 1994)은, 랜덤 오라클 모델로 임의의 흘림문 치환과 조합하면"plaintext awareness(영문판)"를 가져, 이것에 의해 선택 암호문 공격에 대한 식별 불가능성(IND-CCA1 안전성)을 가진다고 여겨졌다.또 당초는 적응적 선택 암호문 공격에 대해서도 식별 불가능성(IND-CCA2 안전성)을 가진다고 생각되고 있었다.그러나 2001년에 빅터・슈프(영문판)가 IND-CCA2는 아닌 것을 나타내 보여, 개량판으로서 OAEP+를 제안한[²].동시기에 댄・보우네이(영문판)도 SAEP 및 SAEP+를 제안한[³].단, 원의 OAEP도 랜덤 오라클 모델로 표준적인 암호화 지수를 이용한 RSA 치환과 조합했을 경우는, 우연히(주로 OAEP는 아니고 RSA 함수의 대수적인 성질에 의해) IND-CCA2가 된다.즉, 후지사키, 오카모토, Pointcheval, Stern의 4명은, OAEP는 원이 되는 암호계가 부분 영역 한방향성 치환이다면 랜덤 오라클 모델로 IND-CCA2인 것, 및 RSA 함수에 관해서는 한방향성과 부분 영역 한방향성이(다항식 시간 귀착아래에서) 등가인 것을 나타냈다.결과, RSA-OAEP는 랜덤 오라클 모델로 RSA 가정으로부터 IND-CCA2 안전성을 가지는[⁴].

근래에는, 표준 모델(즉, 해쉬 함수가 랜덤 오라클이 아닌 모델)에 대해서는, RSA 문제의 곤란성이 현재 추측되고 있는 정도라고 가정했을 경우, RSA-OAEP의 IND-CCA2 안전성을 증명하는 것은 불가능하다라고 하는 것이 나타난[⁵][⁶].또, OAEP를 포함한 패딩 방식 전반과 이상적인 흘림문 치환의 편성에 대해서, 표준 모델로는 안전성을 증명 불가능으로 하는 결과가 얻어지고 있는[⁷].

OAEP의 동작 개념도

 

OAEP의 동작 개념도

그림중에 나타나는 기호의 의미는 다음 대로.

• n는 RSA의 법등의 비트수
• k₀와 k₁는 프로토콜이 정하는 정수
• m는 평문메시지이며, n - k₀ - k₁에 동일한 비트수를 가진다고 한다
• G와 H는 랜덤 오라클 또는 프로토콜이 정하는 어떠한 암호 학문적 해쉬 함수
• r는 랜덤인 비트열이며, k₀비트의 길이를 가진다고 한다

평문의 encode 순서

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%2 F3-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일 열람. 

「https://ja.wikipedia.org/w/index.php? title=Optimal_Asymmetric_Encryption_Padding&oldid=59961473」으로부터 취득

This article is taken from the Japanese Wikipedia Optimal Asymmetric Encryption Padding

This article is distributed by cc-by-sa or GFDL license in accordance with the provisions of Wikipedia.

Wikipedia and Tranpedia does not guarantee the accuracy of this document. See our disclaimer for more information.

In addition, Tranpedia is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CC-BY-SA license information.