128. DH (Diffie-Hellman 키 교환)

⚠️ 이 문서는 암호학 역사상 최초로 "서로 만난 적도, 안전한 통신선도 없는 두 사람이, 해커가 지켜보는 뻥 뚫린 인터넷 게시판에서 대화를 주고받는 것만으로 어떻게 완벽하게 동일한 비밀번호를 공유할 수 있는가?"라는 불가능한 과제를 이산 대수 문제(DLP)의 마법으로 풀어낸 디피-헬만(DH) 키 교환 알고리즘을 다룹니다.

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

본질: 디피-헬만(Diffie-Hellman, DH)은 1976년 발표된 암호학 최초의 공개키 개념으로, 앨리스와 밥이 모듈로 거듭제곱 연산($g^x \pmod p$)의 일방향성(해커가 결과를 봐도 지수 $x$를 역추적 불가)을 이용하여 안전하게 대칭키(공통 비밀번호)를 합의해 내는 알고리즘이다.

가치: 대칭키 암호학(DES, AES)의 가장 치명적 맹점이었던 '키 배송 문제(비밀키를 도둑맞지 않고 어떻게 전해줄 것인가?)'를 우편 배달이 아닌 **'수학적 믹스(Mixing)'**로 완벽히 격파하여 인터넷 암호 통신의 기초 공사를 끝마쳤다.

한계/융합: 이 마법 같은 교환 방식도 중간에 해커가 끼어들어 양쪽과 따로따로 키를 맺어버리는 **'중간자 공격(Man-in-the-Middle, MitM)'**에는 완전히 털리는 치명적 맹점이 있어, 이를 막기 위해 반드시 RSA 기반의 '전자서명 인증서(PKI)'와 융합되어야만 HTTPS가 완성된다.

Ⅰ. 개요 및 키 배송의 패러다임 파괴 (Context & Necessity)

"우리 내일부터 AES 자물쇠 번호 1234로 잠가서 카톡 하자! 근데 이 1234라는 번호를 너한테 어떻게 몰래 알려주지? 전화로 말하면 국정원이 도청할 텐데?"

1970년대까지 인류는 이 **키 배송 문제(Key Distribution)**를 물리적 가방(007 가방에 키를 넣어 비행기로 배달)으로 해결했다. 하지만 인터넷 시대에 수백만 명에게 가방을 보낼 수는 없었다.

1976년, 휘트필드 디피(Whitfield Diffie)와 마틴 헬만(Martin Hellman)은 천재적인 논문 "New Directions in Cryptography"를 발표했다. "서로 열쇠를 배달하지 마라. 대신 너와 내가 각자 마법의 물감을 섞은 뒤 찌꺼기를 인터넷(공개)으로 던져라. 그걸 받아서 내 물감을 한 번 더 섞으면, 우리 둘의 손에는 100% 똑같은 색깔의 물감(비밀번호)이 기적처럼 쥐어질 것이다!" (이 논문 1년 뒤에 이것을 자물쇠로 승화시킨 RSA가 탄생한다.)

📢 섹션 요약 비유: 우체부에게 절대 비밀 편지를 뺏기지 않는 법. 내가 편지를 상자에 넣고 내 자물쇠(A)로 잠가서 친구에게 보낸다. 친구는 상자를 받자마자 자기 자물쇠(B)로 한 번 더 잠가서(자물쇠 2개) 나한테 반송한다. 내가 받아서 내 자물쇠(A)를 풀고 친구에게 보낸다. 친구는 자기 자물쇠(B)만 열면 마침내 편지를 볼 수 있다! 우체부는 한 번도 열린 상자를 본 적이 없다.

Ⅱ. 물감 섞기: DH 키 교환의 수학적 메커니즘

이 마법의 물감을 수학적으로 구현한 것이 바로 앞서 배운 모듈로 거듭제곱 (이산 대수 문제, Discrete Logarithm Problem) 이다.

$g^x \pmod p = Y$. (여기서 결과 $Y$와 힌트 $g, p$를 해커가 훔쳐가도, 거듭제곱한 횟수인 엑스오어($x$)를 거꾸로 찾는 것은 수학적으로 수백만 년이 걸린다.)

🎨 [ 앨리스와 밥의 마법 물감(키) 섞기 시나리오 ]

기초 물감 (공개): 둘은 인터넷 공개 게시판에서 "야, 우리 기초 물감(소수 $p=23$, 밑 $g=5$)으로 합의하자!" 고 떠든다. (해커도 이 글을 다 읽음)
나만의 비밀 물감 타기 (개인키 생성):
- 👩 앨리스: 남몰래 숫자 $a=4$ (내 개인 물감)를 고른다. 기초 물감 5를 4번 제곱한다. $A = 5^4 \bmod 23 = 4$. (이 섞인 물감 **$4$**를 인터넷으로 밥에게 휙 던짐!)
- 👨 밥: 남몰래 숫자 $b=3$ (내 개인 물감)을 고른다. 기초 물감 5를 3번 제곱한다. $B = 5^3 \bmod 23 = 10$. (이 섞인 물감 **$10$**을 인터넷으로 앨리스에게 휙 던짐!)
최종 섞기 (마스터 대칭키 완성):
- 👩 앨리스: 밥이 보낸 10(물감 B)을 받아, 내 비밀 횟수 $a=4$ 번 다시 거듭제곱한다. $K_1 = 10^4 \bmod 23 = \mathbf{18}$ (★)
- 👨 밥: 앨리스가 보낸 4(물감 A)를 받아, 내 비밀 횟수 $b=3$ 번 다시 거듭제곱한다. $K_2 = 4^3 \bmod 23 = \mathbf{18}$ (★)

┌─────────────────────────────────────────────────────────────────────────────┐
│           디피-헬만(DH) 키 교환의 일방향성(해커의 절망) 시각화              │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│ [ 🕵️ 해커가 훔쳐서 알고 있는 정보 (도청 데이터) ]                           │
│   - p=23, g=5 (공개된 기초 물감)                                            │
│   - A=4 (앨리스가 밥에게 던진 중간 찌꺼기)                                  │
│   - B=10 (밥이 앨리스에게 던진 중간 찌꺼기)                                 │
│                                                                             │
│ [ ☠️ 해커가 18 이라는 마스터키를 맞추려면? ]                                │
│   해커는 앨리스의 진짜 속마음(a=4)이나 밥의 속마음(b=3) 중 하나를 무조건    │
│   알아야만 저 두 찌꺼기를 곱해서 18 이라는 결론에 도달할 수 있다.           │
│   하지만 "5의 몇 승을 해야 23으로 나눴을 때 4가 나오지(5^a mod 23 = 4)?"    │
│   라는 이산 대수 문제(DLP)는 슈퍼컴퓨터로도 역산(로그 풀기)이 불가능하다!   │
│   -> 해커는 눈앞에서 데이터가 다 날아다녀도 결국 마스터키 조립에 실패한다.  │
└─────────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 지수 법칙 $(g^a)^b = (g^b)^a = g^{ab}$ 가 성립한다는 중학교 수학 수준의 공식 하나로 인류의 통신 패러다임을 바꾼 걸작이다. 해커는 $g^a$ 와 $g^b$ 덩어리는 훔칠 수 있지만, 저 둘을 단순히 곱한다고 $g^{ab}$ 가 나오는 게 아니다 (거듭제곱의 장벽). 속마음 횟수 $a$ 와 $b$ 가 도청되지 않는 한 앨리스와 밥의 마스터키 18은 절대 털리지 않는다.

📢 섹션 요약 비유: 앨리스(노란색)와 밥(파란색)이 각각 자기만의 비밀 물감을 기초 하얀색에 섞어서(탁한 노랑, 탁한 파랑) 서로에게 던집니다. 해커가 탁한 노랑 물감을 공중에서 훔쳤지만, 노란색을 얼마나 넣었는지 화학적으로 분리(DLP)할 수가 없어요. 반면 앨리스와 밥은 남이 준 탁한 물감에 자기 비밀 물감을 한 번 더 섞어서, 완벽히 똑같은 '탁한 초록색(마스터키)' 잉크를 둘이서만 동시에 쥐게 되는 마술입니다.

Ⅲ. 치명적 맹점: 중간자 공격 (MitM)

하지만 암호학계는 환호하다가 1년 만에 DH의 엄청난 약점을 찾아냈다. "해커가 훔쳐보기만 하는 게(도청) 아니라, 중간에서 물감을 아예 바꿔치기(적극적 개입) 하면 어떡하지?"

중간자 공격 (Man-in-the-Middle Attack):
- 앨리스가 밥에게 A=4 를 보낼 때, 해커 다스(Darth)가 공중에서 낚아챈다.
- 해커 다스는 자기가 앨리스인 척 가짜 A=99 를 밥에게 보낸다. 밥이 보낸 B=10 도 낚아채고, 앨리스에겐 자기가 밥인 척 가짜 B=88 을 보낸다.
- 파국: 앨리스는 (자신과 해커)가 통하는 비밀키 K1을 맺고 밥인 줄 알고 카톡을 보낸다. 밥은 (자신과 해커)가 통하는 비밀키 K2를 맺고 앨리스인 줄 안다. 해커는 중간에 앉아서 K1으로 앨리스의 카톡을 다 풀어서 읽어본 뒤, K2로 다시 암호화해서 밥에게 보내준다.
- 왜 털렸나?: 디피-헬만(DH) 공식 자체에는 **"지금 나랑 물감을 섞는 상대방이 진짜 밥이 맞는지 확인해 주는 '신분증 검사(Authentication)' 기능"**이 단 1%도 없기 때문이다.

해결책: 전자서명(RSA/PKI)의 등판

이 거대한 구멍을 막기 위해 현대 HTTPS 통신에서는, 밥이 앨리스에게 물감(B=10)을 휙 던질 때, 그냥 던지는 게 아니라 "나 네이버(밥) 진짜 맞어!"라는 공인인증서와 함께 RSA 비밀키로 철썩 도장(서명)을 찍어서 던진다. 앨리스는 서명을 확인하고 "아, 해커가 바꿔치기한 물감이 아니네!" 안심한 뒤 최종 마스터키를 만든다. (이것이 키 교환과 전자서명이 항상 한 몸으로 묶여 다니는 이유다.)

Ⅳ. 결론

"암호학을 군대의 전유물에서 일반 대중의 인터넷으로 해방시킨 프로메테우스의 불." 디피-헬만(DH) 키 교환은 그 자체로는 완전한 암호 시스템이 아니며 인증 기능도 없다. 하지만 인류가 골머리를 앓던 '떨어져 있는 사람끼리의 비밀 공유'라는 난제를 일방향 믹서기라는 기발한 방법으로 박살 냄으로써, 오늘날 전 세계를 잇는 TLS, VPN, SSH 등 모든 보안 통신의 터널을 여는 최초의 '마법의 삽' 역할을 톡톡히 해냈다.

📌 관련 개념 맵

해결한 핵심 과제: 키 배송 문제 (Key Distribution Problem)
보안의 기반 수학: 이산 대수 문제 (DLP, Discrete Logarithm Problem)
치명적 약점 (단독 사용 시): 중간자 공격 (MitM - Man in the Middle Attack, 신원 인증 부재)
결합 필수 기술: RSA / ECDSA 디지털 서명 (공인인증서 기반 신원 인증)

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

철수와 영희가 비밀 일기장을 잠글 '비밀번호'를 정해야 하는데, 교실에 나쁜 친구들이 다 듣고 있어서 말을 할 수가 없었어요.
그래서 철수가 5를 곱하고 영희가 3을 곱해서 15(비밀번호)를 만드는 작전을 짰죠! 각자 자기 숫자만 곱해서 나온 결과를 종이에 적어 휙 던지면, 서로 주워서 자기 숫자만 한 번 더 몰래 곱하면 똑같이 15가 나와요.
나쁜 친구들이 공중에서 중간 결과물 종이를 훔쳐봤지만, 두 숫자가 곱해져서 엉망진창이 된 뒤라 도대체 철수가 처음에 무슨 숫자를 썼는지 절대 역추적할 수 없게 만든 천재적인 꼼수랍니다!