110. RSA 암호 (비대칭키의 제왕)

⚠️ 이 문서는 "암호화하는 열쇠와 복호화하는 열쇠가 서로 달라야만 한다"는 암호학 역사상 가장 위대한 혁명(비대칭키)을 현실의 수학(소인수분해의 어려움)으로 구현해 내어, 오늘날 인터넷 전자상거래와 공인인증서 체계를 홀로 탄생시킨 전설적인 알고리즘 RSA를 다룹니다.

핵심 인사이트 (3줄 요약)

본질: RSA는 1977년 리베스트, 샤미르, 애들먼 세 천재가 발명한 공개키(Public Key) 암호 알고리즘으로, 자물쇠를 잠그는 열쇠(공개키)는 온 세상에 뿌리고, 자물쇠를 푸는 열쇠(개인키)는 나 혼자만 안전하게 숨겨두는 수학적 마법이다.

가치: 기존 대칭키(AES 등)의 가장 끔찍한 약점이었던 "비밀키를 상대방에게 어떻게 안전하게 전달할 것인가?(키 배송 문제)"를 완벽히 해결하여, 서로 얼굴 한 번 본 적 없는 수십억 명의 사람들이 인터넷에서 안전하게 돈(신용카드 번호)을 주고받는 전자상거래의 시대를 열어젖혔다.

융합: 거대한 소수(Prime Number) 2개를 곱하기는 쉽지만, 그 거대한 곱을 다시 두 개의 소수로 쪼개는 것(소인수분해)은 슈퍼컴퓨터로도 수만 년이 걸린다는 **'소인수분해의 수학적 난제'**를 암호학적 일방향 트랩도어로 융합시킨 결정체다.

Ⅰ. 개요 및 탄생 배경 (Context & Necessity)

1970년대까지 세상의 모든 암호는 **대칭키(Symmetric Key)**였다. 내가 '1234'라는 비밀번호로 문서를 암호화하면, 받는 사람도 '1234'를 알아야만 풀 수 있다. 그런데 심각한 모순이 발생했다. "미국에 있는 친구에게 이 암호문을 보낼 건데, 비밀번호 '1234'는 도대체 어떻게 전달하지? 편지로 보내다 우체부가 뜯어보면 어떡해?" 이 모순을 **키 배송 문제(Key Distribution Problem)**라 불렀고, 암호학계의 영원한 저주였다.

1976년, 디피와 헬만이 "암호화 키와 복호화 키를 분리하자(비대칭키)"라는 혁명적인 아이디어를 논문으로 냈다. 하지만 수학적 구현체를 만들지는 못했다. 다음 해인 1977년, MIT의 세 천재(Ron Rivest, Adi Shamir, Leonard Adleman)가 밤을 새워가며 정수론을 뒤지다 마침내 완벽한 수식 모델을 만들어냈다. 세 사람의 성을 딴 RSA 알고리즘의 위대한 탄생이었다. 인터넷이 폭발적으로 팽창할 수 있었던 밑바탕에는 바로 이 RSA가 있었다.

📢 섹션 요약 비유: 대칭키는 "금고와 열쇠 1개"를 만들어 금고를 보내고 열쇠도 어찌어찌 몰래 던져줘야 했습니다(도둑맞을 위험). RSA는 제가 "열린 채로 딸깍 잠기기만 하는 금고(공개키)" 수만 개를 찍어 전 세계에 무료로 쫙 뿌리는 것입니다. 누구나 그 금고에 편지를 넣고 딸깍 닫아 저에게 보낼 수 있지만, 닫힌 금고를 여는 유일한 열쇠(개인키)는 제 주머니에 딱 1개뿐입니다.

Ⅱ. RSA의 압도적인 수학적 마법 (소인수분해의 어려움)

RSA의 심장은 '일방향 트랩도어 함수(Trapdoor One-way Function)'다. 한쪽 방향으로 계산하긴 쉽지만, 거꾸로 계산하기는 불가능한 성질이다. RSA는 이를 **'소인수분해(Factorization)'**에서 찾았다.

1. 소인수분해의 일방향성

쉬운 방향: 13 (소수) $\times$ 17 (소수) = 221 (계산 1초 컷)
불가능한 방향: 자, "408508091" (어떤 소수 두 개의 곱)가 있다. 이 숫자를 만든 두 소수는 무엇인가? $\rightarrow$ 컴퓨터가 없으면 하루 종일 걸린다. (정답: 19997 $\times$ 20437)
RSA는 고작 5자리 소수가 아니라, 컴퓨터 메모리 끝까지 차는 수백 자리의 어마어마하게 거대한 소수 2개($p, q$)를 곱해서 거대한 수 $N$을 만든다. 슈퍼컴퓨터 수만 대를 돌려도 이 $N$을 다시 $p$와 $q$로 분해하려면 지구 나이만큼의 시간이 걸린다.

2. 열쇠의 분리 (수학의 기적)

내가 선택한 어마어마한 두 소수 $p$와 $q$의 비밀 조합을 이용해 수학적 계산(오일러 파이 함수)을 거치면, 한 쌍의 마법 열쇠 ($e, d$)가 탄생한다.
$e$ (공개키, Public Key): $N$과 함께 홈페이지에 당당히 걸어둔다. "내게 비밀 편지 보낼 사람들은 이 $e$라는 자물쇠로 잠가서 보내세요!"
$d$ (개인키, Private Key): 나만 아는 비밀 금고 깊숙한 곳에 숨겨둔다.

┌───────────────────────────────────────────────────────────────────────────┐
│           RSA 비대칭키 암호 통신의 완벽한 시나리오 (앨리스와 밥)          │
├───────────────────────────────────────────────────────────────────────────┤
│                                                                           │
│ [ 준비 단계: 밥의 금고 뿌리기 ]                                           │
│   👨 밥: (비밀 방에서) 소수 2개를 섞어 마법 열쇠 쌍 (e, d)를 만듦.        │
│      - 밥의 공개키(e): "이 자물쇠로 편지를 잠가라!" -> 인터넷에 쫙 뿌림.  │
│      - 밥의 개인키(d): 내 주머니에 쏙 (절대 안 보여줌)                    │
│                                                                           │
│ [ 암호화 전송 단계: 앨리스의 편지 ]                                       │
│   👩 앨리스: "밥에게 내 신용카드 번호 1234를 보내야지."                   │
│      - 앨리스는 인터넷에서 주운 '밥의 공개키(e)'로 편지를 철컥 잠금.      │
│      - (인터넷으로 편지 전송 중...) -> 🕵️ 해커가 편지를 가로챔!           │
│                                                                           │
│ [ 해커의 절망 vs 밥의 평온 ]                                              │
│   🕵️ 해커: "어? 편지를 훔쳤는데 잠겨있네? 나도 인터넷에 돌아다니는        │
│           밥의 공개키(e) 가지고 있는데, 이걸로 열어볼까?"                 │
│           -> 삐빅! 공개키는 '잠그는 기능'만 있고 '푸는 기능'은 없음 ☠️    │
│                                                                           │
│   👨 밥: 편지를 무사히 받음.                                              │
│        주머니에서 나만의 '개인키(d)'를 꺼내서 편지를 철컥! 엶.            │
│        -> 1234 신용카드 번호 안전하게 확인 완료! 🛡️                       │
└───────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이것이 바로 인류 정보 교환의 역사를 바꾼 기적이다. 앨리스는 밥과 단 한 번도 만난 적이 없고, 비밀번호를 몰래 주고받은 적도 없다. 그저 밥이 길거리에 뿌려둔 '잠그는 용도 전용 자물쇠(공개키)'를 주워서 편지를 넣었을 뿐인데, 완벽한 보안 통신이 성립되었다. 해커가 통신선을 아무리 훔쳐봐도, 푸는 열쇠(개인키)는 한 번도 인터넷 선을 타고 넘어간 적이 없으므로 영원히 해독할 수 없다.

📢 섹션 요약 비유: 우체통과 똑같습니다. 우체통 입구(공개키)는 길거리에 활짝 열려 있어서 전 세계 누구나 편지를 쏙 밀어 넣을(암호화) 수 있습니다. 하지만 한 번 편지가 들어가면 절대 다시 손을 집어넣어 뺄 수 없죠. 오직 우체국장님이 가진 단 하나의 열쇠(개인키)로 우체통 밑구멍을 열어야만 편지를 꺼내 볼(복호화) 수 있습니다.

Ⅲ. RSA의 치명적 단점과 융합 (Hybrid Encryption)

그렇다면 전 세계 모든 데이터를 RSA로 다 암호화하면 되지 왜 아직도 AES 같은 대칭키를 쓸까? 정답은 **"RSA는 수학적으로 미친 듯이 무겁고 느려 터졌기 때문"**이다.

최악의 퍼포먼스: RSA는 수백 자리 숫자를 제곱하고 나머지 연산(Modulo)을 하는 괴물 같은 수학 계산을 동반한다. AES(블록 암호)에 비해 암호화 속도가 최소 1,000배 이상 느리다. 1GB짜리 영화를 RSA로 암호화하면 서버 CPU가 다 타버린다.
현실의 융합 타협 (하이브리드 암호):
- 영화나 신용카드 결제 내역 1GB의 본문(알맹이)은 엄청나게 빠르고 가벼운 AES 대칭키로 순식간에 암호화한다.
- 그리고 그 AES를 풀 수 있는 짧은 '비밀번호(대칭키 128비트)' 하나만, 방금 말한 무겁고 단단한 RSA 공개키로 한 번 더 감싸서 보낸다. (속도와 보안의 완벽한 융합) [078 하이브리드 암호 문서 참조]

Ⅳ. 전자서명 (Digital Signature): RSA의 뒷면 거울

RSA의 수학 공식은 또 하나의 엄청난 부가 기능을 선물로 주었다. 공식을 완전히 거꾸로 돌려버리는 것이다.

보통은 [공개키로 잠그고 $\rightarrow$ 개인키로 푼다] (기밀성, 남이 못 보게 하기)
하지만 반대로 [내 개인키로 잠그고 $\rightarrow$ 공개키로 푼다] 도 성립한다!
- 밥이 자신의 '개인키(d)'로 편지를 꾹 눌러서(암호화) 보냈다.
- 이 편지는 전 세계 누구나 밥의 '공개키(e)'를 주워서 열어볼 수 있다. (기밀성 없음)
- 하지만 편지가 밥의 공개키로 무사히 풀린다는 사실 자체가, **"이 편지는 세상에 단 하나뿐인 밥의 개인키로만 잠근 진짜 편지가 맞다!"**는 완벽한 신분 증명이 된다.
- 이것이 바로 주민등록증을 대체하는 **전자서명(공인인증서 체계)**의 완벽한 작동 원리다.

Ⅴ. 결론

"수학적 난제(어려움)가 해커의 눈물을 쥐어짜는 최고의 방패로 승화되었다." RSA는 사이버 스페이스에서 낯선 사람들끼리 서로 믿고 거래할 수 있게 만들어준 절대적인 신뢰의 닻이다. 1977년 탄생 이래 50년 가까이 수많은 해커들이 알고리즘을 부수려 했지만, 소인수분해의 단단한 수학적 벽 앞에서는 한없이 무력했다. 비록 훗날 양자 컴퓨터의 쇼어 알고리즘(Shor's Algorithm)이 등장하면 산산조각 날 운명이지만, RSA가 인류의 인터넷 혁명을 혼자 힘으로 견인했다는 사실은 암호학 역사에 영원히 지워지지 않는 거대한 전설로 남을 것이다.

📌 관련 개념 맵

전체 분류: 비대칭키 암호 (Asymmetric Encryption) / 공개키 암호
핵심 수학 원리: 큰 수의 소인수분해 (Factorization)의 수학적 난제
단점 보완 아키텍처: RSA-OAEP 패딩 (CCA 방어), 하이브리드 암호 시스템 (AES 결합)
부가 파생 기술: 전자서명 (Digital Signature), PKI(공개키 기반 구조)

👶 어린이를 위한 3줄 비유 설명

내가 인터넷으로 물건을 살 때 비밀번호를 보내야 하는데, 해커가 몰래 훔쳐볼까 봐 너무 무서웠어요.
쇼핑몰 사장님은 나한테 열려있는 '철통 금고(공개키)'를 무료로 던져줬어요. 나는 거기에 내 비밀번호를 넣고 "딸깍" 닫기만 했죠!
한 번 잠긴 금고는 밖에서 망치로 쳐도 안 열리지만, 쇼핑몰 사장님 방에 있는 단 하나뿐인 '마스터 열쇠(개인키)'로만 부드럽게 스르륵 열려서 내 비밀번호를 안전하게 전달할 수 있었답니다!