Brain112. RSA-OAEP (Optimal Asymmetric Encryption Padding)
⚠️ 이 문서는 수학 교과서에 나오는 순정 RSA 공식을 그대로 인터넷 환경에 썼다가는 "똑같은 평문에 똑같은 암호문이 나오는" 결정론적 치명타(CPA/CCA 공격)를 맞고 시스템이 붕괴하므로, 암호화 전에 평문을 난수로 비벼 헝클어버리는 완벽한 방어 갑옷인 OAEP 패딩 기법을 다룹니다.
핵심 인사이트 (3줄 요약)
- 본질: RSA-OAEP는 평문 $M$을 $M^e \bmod N$으로 바로 굽기 전에, 수학적 믹서기(해시 함수와 무작위 난수)를 이용해 평문을 쓰레기 문자열로 뻥튀기하고 섞어주는 비대칭키 전용 고급 패딩(Padding) 기술이다.
- 가치: 똑같은 평문 "Hello"를 100번 암호화해도 OAEP를 거치면 매번 들어가는 무작위 난수(Seed) 덕분에 100번 모두 완전히 다른 암호문이 튀어나온다. 이로써 **선택 평문 공격(CPA)**을 무력화한다.
- 융합: 단순히 난수만 섞는 것이 아니라, 해커가 암호문 1비트를 슬쩍 조작해서 서버의 반응을 엿보는(오라클 찌르기) 극악의 선택 암호문 공격(IND-CCA2) 상황에서도 서버가 힌트를 흘리지 않게 원천 차단하여, 현실의 TLS 통신에서 RSA를 안전하게 쓸 수 있도록 융합(표준화)시켰다.
Ⅰ. 개요 및 순정 RSA(Textbook RSA)의 참사
교과서에 나오는 RSA 공식은 아름답다. $C = M^e \pmod N$. 하지만 이 순정 RSA(Textbook RSA)를 은행 개발자가 그대로 코딩하면 그 은행은 다음 날 파산한다. 왜 그럴까? **순정 RSA는 결정론적(Deterministic)**이기 때문이다. 수학 공식에 변수가 없으므로, "10만 원 송금"이라는 똑같은 평문을 넣으면 항상 "X9@#$"라는 똑같은 암호문만 튀어나온다.
- 해커의 CPA 공격 (선택 평문 공격): 해커가 몰래 "10만 원", "100만 원" 등 온갖 금액을 RSA로 암호화해 보고 암호문 사전을 만든다. 나중에 내 통신선을 훔쳐보다가 "X9@#$"가 지나가면, 굳이 비밀키를 몰라도 "아! 쟤 10만 원 보냈구나!" 하고 평문을 알아채 버린다.
이를 막기 위해 블록 암호(AES)에서는 IV(초기화 난수)를 썼듯, RSA에서도 평문을 암호화하기 전에 **무작위 난수(Random)를 잔뜩 버무려 주는 마법의 밀가루 반죽, '패딩(Padding)'**이 절대적으로 필요해졌다.
📢 섹션 요약 비유: 순정 RSA는 투명한 얼음 틀입니다. 물을 부으면 무조건 투명한 얼음이 나오죠(똑같은 암호문). OAEP 패딩은 물을 붓기 전에 매번 색깔이 다른 식용색소(무작위 난수)를 무조건 한 방울씩 떨어뜨리는 기계입니다. 결과물은 매번 빨간색, 파란색, 노란색 등 전혀 다르게 나와 도둑이 원래 무슨 물이었는지 찍어 맞출 수 없게 합니다.
Ⅱ. 구형 패딩(PKCS#1 v1.5)의 비극과 블라이헨바허 공격
초기에는 그냥 평문 앞에 00 02 [무작위 난수] 00 [평문] 형태로 난수를 때려 박는 PKCS#1 v1.5라는 패딩 방식을 썼다.
하지만 1998년 다니엘 블라이헨바허(Bleichenbacher)가 이 구형 패딩을 **CCA(선택 암호문 공격)**로 처참하게 박살 냈다.
- 오라클 찌르기: 해커가 인터넷에서 훔친 암호문 수백만 개를 살짝살짝 변조해서 서버에 마구잡이로 보낸다.
- 서버의 말실수: 서버는 변조된 암호문을 풀다가 패딩 형식이
00 02로 시작하지 않으면 "야! 패딩 규격 틀렸어!(Error)"라고 에러 메시지를 뱉는다. - 해커의 쾌재: 해커는 "아하, 요기를 요렇게 고치면 에러가 나네?"라며 서버의 에러 반응(Oracle)을 청진기 삼아, 무려 100만 번의 찌르기 끝에 개인키 없이도 평문을 100% 해독해 냈다. (밀리언 메시지 공격)
Ⅲ. 완전 방패의 등장: RSA-OAEP의 샌드위치 믹서기 구조
블라이헨바허 사태로 충격을 받은 암호학계는 미히르 벨라레(Mihir Bellare) 등이 발명한 **OAEP (Optimal Asymmetric Encryption Padding)**를 차세대 표준으로 황급히 도입했다.
OAEP는 평문에 단순히 난수를 이어 붙이는 바보 같은 짓을 그만두고, 평문과 난수를 해시 믹서기(MGF, 마스크 생성 함수)에 넣고 두 번이나 엑스오어(XOR)로 비벼버리는 치밀한 페이스텔(Feistel) 구조의 축소판을 채택했다.
OAEP의 암호화(패딩) 과정
- 난수 생성: 128비트짜리 완벽한 일회용 무작위 난수(Seed)를 하나 굽는다.
- 1차 비비기: 이 난수를 해시 믹서기(MGF)에 넣고 부풀린 뒤, 진짜 평문 데이터($M$)와 마구잡이로 XOR ⊕ 시킨다. (평문이 형체를 알 수 없는 쓰레기가 됨)
- 2차 비비기: 방금 엉망진창이 된 쓰레기 평문을 다시 해시 믹서기(MGF)에 넣고 부풀려, 아까 처음에 만들었던 난수(Seed)와 한 번 더 XOR ⊕ 시켜버린다. (난수마저도 쓰레기로 덮임)
- 결과물 (패딩 완료): 이렇게 두 번 꼬아서 만들어진 완벽한 쓰레기 덩어리(Padded Message)를 그제야 **순정 RSA 기계($M^e \pmod N$)**에 넣고 진짜 암호문으로 굽는다.
┌───────────────────────────────────────────────────────────────────────────────┐
│ RSA-OAEP의 무작위 샌드위치 패딩 구조 시각화 │
├───────────────────────────────────────────────────────────────────────────────┤
│ │
│ [ 준비물 ] │
│ - 진짜 평문 메시지 (Message) │
│ - 이번 턴에만 쓸 일회용 난수 (Seed) │
│ │
│ [ OAEP 믹서기 ] │
│ │
│ 난수(Seed) ──▶ [ 해시 함수 부풀리기(MGF) ] │
│ │ │ │
│ │ ▼ │
│ │ ( XOR ⊕ ) ◀── 진짜 평문 │
│ │ │ │
│ ▼ ▼ │
│ [ 해시 함수(MGF) ] ◀────── [ 엉망이 된 평문 덩어리 ] │
│ │ │ │
│ ▼ │ │
│ ( XOR ⊕ ) │ │
│ │ │ │
│ ▼ ▼ │
│ [ 숨겨진 난수 ] [ 엉망이 된 평문 덩어리 ] │
│ └───────────────┬───────────────┘ │
│ ▼ │
│ [ RSA 공식(M^e mod N) 암호화 엔진 투입 전 최종 데이터! ] │
│ │
│ * 핵심 효과: 평문과 난수가 실타래처럼 엉켜서, 해커가 암호문 끝에 1비트만 │
│ 조작해서 서버에 던져도 복호화(역산) 과정에서 난수와 평문이 통째로 붕괴되어 │
│ 서버는 "이게 뭐야?" 하고 에러 메시지조차 없이 즉시 세션을 끊어버린다! │
└───────────────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] OAEP의 가장 큰 마법은 "ALL or NOTHING (전부 아니면 무)" 구조다. 해커가 암호문 1비트를 장난쳐서 서버(오라클)에 넣으면, 서버가 OAEP를 거꾸로 푸는 과정에서 해시 함수($MGF$) 연산이 박살 나버린다. 서버는 "네가 보낸 데이터는 구조가 완전히 뭉개져서(1비트가 100바이트를 망가뜨리는 눈사태 효과) 뭐가 문젠지도 모르겠어!"라며 해독 자체를 포기한다. 따라서 해커는 찌르기에 대한 피드백(에러 종류)을 얻을 수 없어 IND-CCA2 방어가 완벽히 성립된다.
- 📢 섹션 요약 비유: 구형 패딩은 비밀 편지 겉봉에 "비밀!"이라고 적어 보낸 거라, 도둑이 "비밀" 글씨만 "메롱"으로 살짝 고치면 은행 직원이 "앗! 비밀 글씨가 이상해요!"라고 힌트를 줬습니다(블라이헨바허 공격). OAEP는 비밀 편지를 물감 통에 통째로 담갔다가 꺼내 보내는 거라서, 도둑이 편지 모서리를 살짝만 찢어도 편지 전체가 가루로 부서져 은행 직원이 아예 읽기조차 포기하게 만들어 힌트를 차단합니다.
Ⅳ. 실무 적용의 표준화 (PKCS#1 v2.1)
현재 모든 정상적인 글로벌 인터넷 서비스(HTTPS, JWT 토큰 서명, 클라우드 키 관리 등)는 RSA 암호화를 수행할 때 무조건 기본값으로 RSA-OAEP를 쓰도록 강제되어 있다.
- 암호학 라이브러리(Java JCE, OpenSSL 등)에서 암호화 규격을 세팅할 때, 단순히
"RSA"로만 세팅하면 보안 감사에서 100% 지적당한다. - 반드시
"RSA/ECB/OAEPWithSHA-256AndMGF1Padding"과 같이 촘촘하고 명시적인 패딩 알고리즘을 지정해 주어야만 안전한 아키텍처가 구현된다.
Ⅴ. 결론
"이론적인 암호의 뼈대에, 실전을 견디는 강철 근육을 붙이는 작업." 수학 교과서의 RSA는 우아하지만, 오물이 튀고 해커의 찌르기가 난무하는 현실의 네트워크 바다에서는 며칠 만에 난도질당할 온실 속의 화초였다. OAEP(최적 비대칭 암호화 패딩)는 일회용 난수라는 무작위성을 주입하여 평문의 패턴을 100% 지워버리고(CPA 방어), 실타래 믹서기 구조를 통해 해커의 찌르기 공격(CCA2 방어)마저 완벽히 흡수하는 인류 최고의 방패 마스크(Mask)가 되었다.
📌 관련 개념 맵
- 전제/상위 기술: RSA 알고리즘 (순정 RSA의 한계 극복)
- 보안 달성 목표: IND-CPA (무작위성 추가), IND-CCA2 (해커의 가짜 암호문 찌르기 방어)
- 파괴한 공격 기법: 블라이헨바허 공격 (Bleichenbacher Attack, 패딩 오라클 공격의 일종)
- 내부 사용 요소: MGF1 (Mask Generation Function, 보통 SHA-256 같은 해시 함수를 씀), Seed(난수)
👶 어린이를 위한 3줄 비유 설명
- 자물쇠(RSA) 안에 "사과"라는 편지를 넣고 잠그면, 항상 겉모양이 뾰족한 똑같은 금고 상자가 나와서 도둑들이 금방 "저 뾰족한 건 무조건 사과야!" 하고 눈치챘어요.
- 그래서 똑똑한 요리사가 상자에 편지를 넣기 전에 '무작위 주사위 숫자(난수)'와 편지를 블렌더(OAEP)에 넣고 형체를 알 수 없게 확 갈아버린 뒤 상자에 담았죠.
- 이제 똑같은 "사과"를 넣어도 매번 상자 모양이 둥글게, 네모나게 마구 바뀌게 되어서 도둑들이 힌트를 하나도 얻지 못하고 절망하게 되었답니다!