최적의 비대칭 암호화 패딩

암호학에서 OAEP(Optimal Asymmetric Encryption Pading)는 RSA 암호화와 함께 자주 사용되는 패딩 방식이다.OAEP는 벨라레와 로가웨이에 의해 도입되었고,^[1] 이후 PKCS#1 v2와 RFC 2437에서 표준화되었다.

OAEP 알고리즘은 Feistel 네트워크의 한 형태로, 비대칭 암호화에 앞서 일반 텍스트를 처리하기 위해 임의의 오라클 G와 H 한 쌍을 사용한다.어떤 보안 $트랩도어{\displaystyle }$ 단방향 순열 f ${\displaystyle f}$과 결합할 때$,$ 이 처리 과정은 랜덤 오라클 모델에서 입증되어 선택된 일반 텍스트 공격(IND-CPA) 하에서 의미론적으로 안전한 결합 체계를 만든다.특정 트랩도어 순열(예: RSA)으로 구현될 때 OAEP는 또한 선택된 암호문 공격에 대해 안전한 것으로 입증된다.OAEP는 전체 또는 무(無) 변환을 구축하는 데 사용될 수 있다.

OAEP는 다음 두 가지 목표를 만족한다.

1. 결정론적 암호화 체계(예: 기존 RSA)를 확률론적 체계로 변환하는 데 사용할 수 있는 무작위성의 요소를 추가하십시오.
2. 적수가 트랩도어 단방향 순열 $f{\displaystyle }$ ${\displaystyle f}$을(를) 반전시키지 않고 일반 텍스트의 일부를 복구할 수 없도록 함으로써 암호문(또는 기타 정보 유출)의 부분 암호 해독을 방지한다$.$

OAEP의 원본 버전(Bellare/Rogaway, 1994)은 임의의 트랩도어 순열과 함께 OAEP를 사용할 때 랜덤 오라클 모델에서 "플레인텍스트 인식"(선택한 암호문 공격에 대한 보안을 의미한다고 주장)의 형태를 보였다.후속 결과는 OAEP가 단지 IND-CCA1 안전하다는 것을 보여주면서 이 주장과 모순되었다.그러나 RSA-OAEP의 경우와 같이 표준 암호화 지수를 사용하는 RSA 순열화와 함께 OAEP를 사용할 경우, 원래의 체계가 IND-CCA2 보안이 되는 것으로 랜덤 오라클 모델에서 입증되었다.^[2]어떤 트랩도어 단방향 순열과 함께 작동하는 개선된 계획(OAEP+라 한다)은 빅터 슈프가 이 문제를 해결하기 위해 제공했다.^[3]보다 최근의 연구는 표준 모델(즉, 해시 함수를 랜덤 오라클로 모델링하지 않은 경우)에서 RSA 문제의 가정된 경도 하에서는 RSA-OAEP의 IND-CCA2 보안을 증명하는 것이 불가능하다는 것을 보여주었다.^[4][5]

알고리즘.

도표에서

• n은 RSA 계수의 비트 수입니다.
• k와₀ k는₁ 프로토콜에 의해 고정된 정수다.
• m은 일반 텍스트 메시지, (n₀ - k - k )비트₁ 문자열
• G와 H는 선택한 암호해시함수에 기초한 마스크 생성함수다.
• ⊕은 xor 수술이다.

인코딩하려면

1. 메시지는 길이가 n - k 비트로₀ 0으로₁ 채워진다.
2. r은 임의로 생성된 k-bit₀ 문자열이다.
3. G는 r의 k비트를₀ n - k비트로₀ 확장한다.
4. X = m00...0 ⊕ G(r)
5. H는 X의 n - k 비트를₀ k 비트로₀ 줄인다.
6. Y = r ⊕ H(X)
7. 출력은 X Y이며, 여기서 X는 다이어그램에서 가장 왼쪽 블록으로, Y는 오른쪽 블록으로 표시된다.

RSA에서의 사용: 인코딩된 메시지는 RSA로 암호화될 수 있다.이제 RSA의 결정론적 속성은 OAEP 인코딩을 사용함으로써 피할 수 있다.

해독하려면

1. 임의 문자열을 r = Y x H(X)로 복구
2. 메시지를 m00으로 복구하다...0 = X ⊕ G(r)

보안

"전부 또는 무전부" 보안은 m을 복구하기 위해서는 X 전체와 Y 전체를 복구해야 하고, Y에서 r을 복구하기 위해서는 X가 필요하며, X에서 m을 복구하기 위해서는 r이 필요하다는 사실에서 비롯된다.암호 해시의 어떤 변화된 비트가 결과를 완전히 변화시키므로, 전체 X와 전체 Y는 모두 완전히 복구되어야 한다.

실행

PKCS#1 표준에서 임의의 굴곡 G와 H는 동일하다.또한 PKCS#1 표준에서는 임의의 오라클이 적절한 해시 함수의 MGF1이 되도록 요구한다.^[6]

참고 항목

• 키 캡슐화

참조