111. RSA 키 생성의 수학적 원리

⚠️ 이 문서는 "어떻게 컴퓨터가 자물쇠(공개키)와 열쇠(개인키) 쌍을 한 세트로 찍어내는가?"에 대한 근원적인 질문을, 소인수분해의 난제와 오일러의 파이(Totient) 함수를 통해 풀어내는 RSA 알고리즘의 핵심 수학 메커니즘을 다룹니다.

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

본질: RSA 키 생성은 아주 거대한 두 소수 $p$와 $q$를 곱해서 $N$을 만든 뒤, **오일러 파이 함수 $\phi(N) = (p-1)(q-1)$**를 이용하여 공개키 지수 $e$와 짝을 이루는 개인키 지수 $d$를 수학적으로 엮어내는 과정이다.

가치: $N$과 $e$는 전 세계에 공개되어도 무방하다. 왜냐하면 개인키 $d$를 계산해 내려면 반드시 $p$와 $q$를 알아야 하는데, 거대한 우주 스케일의 $N$을 소인수분해하여 다시 $p$와 $q$로 쪼개는 것은 현존하는 슈퍼컴퓨터로도 수만 년이 걸리기 때문이다.

융합: 이 수학적 한 방향성(Trapdoor) 덕분에, 누구나 $N$과 $e$로 메시지를 잠글(암호화) 수는 있지만 오직 $p$와 $q$를 기억하고 있는(또는 $d$를 가진) 주인만이 그 메시지를 열어볼(복호화) 수 있는 완벽한 비대칭(Asymmetric) 통신 아키텍처가 융합된다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

"자물쇠(공개키)는 뿌리고 열쇠(개인키)는 숨긴다." 이 혁명적인 비대칭키 개념은 훌륭했지만, 이 두 개를 어떻게 '수학적으로 연결'할 것인지가 가장 큰 문제였다. 자물쇠와 열쇠는 모양이 완전히 달라야 하지만(해커가 자물쇠를 보고 열쇠를 깎을 수 없도록), 두 개가 딱 맞물려 돌아가야(정상적으로 복호화) 하기 때문이다.

1977년 MIT의 리베스트(Rivest), 샤미르(Shamir), 애들먼(Adleman)은 이를 **'모듈러 연산(나머지 시계 연산)'**과 **'오일러 파이 함수'**라는 정수론의 오랜 마법을 끄집어내어 완벽하게 해결했다. 그들이 만든 공식 하나가 오늘날 전 세계 수십억 개의 은행 공인인증서와 인터넷 쇼핑몰(HTTPS)을 탄생시킨 씨앗이 되었다.

📢 섹션 요약 비유: 페인트 두 색깔을 섞는 것과 같습니다. 노란색($p$)과 파란색($q$) 페인트를 섞어서 초록색($N$)을 만드는 건 1초면 되지만, 초록색 페인트를 통째로 주고 다시 완벽하게 노란색과 파란색으로 분리해 내라고 하면 전 세계 과학자가 다 모여도 불가능합니다. RSA는 바로 이 '섞기는 쉽지만 분리하기는 불가능한' 꼼수를 이용해 열쇠를 찍어냅니다.

Ⅱ. RSA 키 생성 5단계 (수학적 심층 해부)

RSA의 심장부에서 서버가 공개키($e, N$)와 개인키($d$)를 찍어내는 과정이다. (수학 공식을 이해하면 암호학의 정수를 맛볼 수 있다.)

소수 준비 (Prime Generation)
- 매우 큰(보통 1024비트 이상) 서로 다른 두 소수 $p$ 와 **$q$**를 임의로 뽑는다. (이 두 숫자는 나만 아는 절대 비밀이어야 한다!)
- 예시 (쉬운 숫자): $p=3$, $q=11$
모듈러스 N 생성 (Modulus)
- 두 소수를 곱한다. $N = p \times q$
- $N = 3 \times 11 = 33$
- 이 **$N$은 나중에 전 세계에 널리 공개(Public)**된다. 해커가 $N$(33)을 보고 "아, 이건 3과 11을 곱한 거네?"라고 눈치채면 해킹당한다. 그래서 실제 $p$와 $q$는 수백 자리의 괴물 같은 소수를 써서 곱한다.
오일러 파이 함수 계산 (Totient)
- 이 부분이 가장 중요한 마법이다. 1부터 $N$까지의 숫자 중 $N$과 서로소인 숫자의 개수를 구하는 함수다. 소수 $p, q$의 곱일 경우 아주 간단한 공식이 성립한다.
- $\phi(N) = (p-1) \times (q-1)$
- $\phi(33) = (3-1) \times (11-1) = 2 \times 10 = 20$
- 이 $\phi(N)$(20) 값 역시 나만 아는 절대 비밀이다!
공개키 지수 e 선택 (Public Exponent)
- $1 < e < \phi(N)$ 이면서, $\phi(N)$과 서로소인 정수 $e$를 하나 고른다.
- $\phi(33)=20$ 이므로, 20과 겹치는 약수가 없는 수 중 $e=3$을 선택한다.
- 완성! 내 [공개키]는 $(e=3, N=33)$ 이다. 홈페이지에 당당히 걸어둔다.
개인키 지수 d 계산 (Private Exponent)
- $e \times d \equiv 1 \pmod{\phi(N)}$ 을 만족하는 $d$를 찾는다. (즉, $e$와 곱해서 $\phi(N)$으로 나눈 나머지가 1이 되는 수)
- $3 \times d \equiv 1 \pmod{20}$ 을 만족하는 숫자는 $d=7$ 이다. ($3 \times 7 = 21$, 20으로 나누면 나머지 1)
- 완성! 내 [개인키]는 $d=7$ 이다.

┌─────────────────────────────────────────────────────────────────┐
│           RSA 암호화 및 복호화 메커니즘 (자물쇠와 열쇠의 결합)  │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│ [ 🔐 암호화 (앨리스 -> 밥) ]                                    │
│   평문 메시지 M = 5 (숫자로 변환된 데이터)                      │
│   밥의 공개키: (e=3, N=33)                                      │
│                                                                 │
│   공식: C = M^e mod N                                           │
│   계산: C = 5^3 mod 33 = 125 mod 33 = 26 (암호문 탄생!)         │
│                                                                 │
│ [ 🔓 복호화 (밥이 직접 열기) ]                                  │
│   해커가 26을 훔쳐도 개인키(d=7)를 몰라서 못 풂.                │
│   밥은 자기의 개인키 d=7 로 엽니다.                             │
│                                                                 │
│   공식: M = C^d mod N                                           │
│   계산: M = 26^7 mod 33                                         │
│           = 8031810176 mod 33 = 5 (원래 메시지 5로 완벽 복구!)  │
└─────────────────────────────────────────────────────────────────┘

[다이어그램 해설] $M^e$ 를 한 번 더 $d$ 제곱하면 $M^{ed}$ 가 되는데, 오일러의 정리(Euler's Theorem)라는 수학의 절대 법칙에 의해 $M^{ed} \pmod N$ 은 마법처럼 원래의 $M$으로 툭 떨어지게 된다. 해커가 이 마법을 풀려면 $d$를 알아야 하고, $d$를 알려면 $\phi(N)$을 알아야 하며, $\phi(N)$을 알려면 $N$을 소인수분해 해서 $p$와 $q$를 알아야 한다. 하지만 소인수분해는 불가능하므로, 결국 우주가 멸망할 때까지 앨리스의 편지는 안전하다!

📢 섹션 요약 비유: 시계의 바늘을 마구 돌려서(공개키 덧셈) 엉뚱한 시간을 가리키게 한 뒤(암호문), 내가 몰래 빼둔 원래 시계의 톱니바퀴 개수(개인키)만큼 바늘을 정확히 역으로 돌리면(복호화), 기적처럼 원래의 시간(평문)으로 다시 돌아오는 태엽 장치와 같습니다.

Ⅲ. 실무적 약점과 2048비트의 시대

이론적으로 완벽한 이 마법에도 약점은 존재한다. 수학적 공식 자체의 결함이 아니라, "컴퓨터가 너무 똑똑해져서 $N$을 소인수분해 해버리는 것 아니야?" 하는 불안감이다.

N의 크기(Key Size) 팽창
- 1977년 발명 당시 $N$의 길이는 426비트(129자리 십진수)로 충분하다고 믿었지만, 1994년 17년 만에 전 세계 컴퓨터가 힘을 합쳐 이를 분해해 냈다.
- 오늘날 금융권과 웹 브라우저(HTTPS)는 최소 RSA-2048 (비트 수) 이상을 강제한다. 2048비트는 대략 600자리 십진수다. 이 정도 크기의 $N$을 두 소수 $p, q$로 쪼개는 것은 현존하는 슈퍼컴퓨터로 수백억 년이 걸린다.
양자 컴퓨터의 위협 (Shor's Algorithm)
- 평화로운 RSA 왕국에 폭탄이 떨어졌다. 1994년 피터 쇼어(Peter Shor)가 "양자 컴퓨터가 상용화되면 소인수분해를 지수 함수 속도가 아니라 다항 시간 안에 순식간에 풀어버릴 수 있다"는 공식을 증명해 버렸다.
- 양자 컴퓨터가 나오면 RSA-2048은 종이조각이 된다. 현재 보안 업계는 이 파국(Q-Day)에 대비하여 소인수분해를 안 쓰는 완전히 다른 수학(격자 암호 등)으로 넘어가는 양자 내성 암호(PQC) 전환을 국가적 비상사태로 준비하고 있다.

Ⅳ. 결론

"정수론(Number Theory)이라는 쓸모없어 보이던 순수 수학이, 2천 년 만에 인류의 가장 비싼 디지털 자산을 지키는 금고로 환생했다." 소인수분해의 맹점을 역이용한 RSA의 키 생성 원리는 암호학의 역사를 반으로 쪼개는 특이점(Singularity)이었다. 누구에게나 잠글 수 있는 권리(공개키)를 무료로 나눠주면서도 풀 권리(개인키)는 한 명에게만 독점시키는 이 우아한 불균형 덕분에, 우리는 은행에 가지 않고도 비밀번호를 안전하게 전송하는 전자상거래의 시대를 마음껏 누리고 있다.

📌 관련 개념 맵

전제 지식: 비대칭키 암호 (Asymmetric Encryption)
보안의 근원: 일방향 트랩도어 함수 (Trapdoor One-way Function)
수학적 기반: 소인수분해 (Integer Factorization Problem), 오일러 파이 함수, 모듈러 연산
천적 (해독 위험): 양자 컴퓨터 (Shor's Algorithm)

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

자물쇠를 만들 때, 컴퓨터가 아주아주 커다란 소수 2개를 몰래 골라서($p$와 $q$) 곱하기를 해버려요($N$).
곱해서 나온 엄청나게 큰 숫자($N$)로 튼튼한 금고(공개키)를 만들어서 온 동네에 쫙 뿌려요!
나쁜 도둑이 금고를 주워서 분해해 보려고 해도, 원래 곱했던 2개의 숫자($p, q$)가 뭔지 맞추려면 1만 년이 걸려서 결국 금고를 열 수 없는 완벽한 열쇠고리 기술이랍니다!