한양과기고 에듀테크 수업도구 대시보드

디피–헬만 키 교환 (Diffie–Hellman)

두 사람이 한 번도 만난 적 없고 주고받는 모든 메시지를 도청당하는 상황에서, 둘만 아는 공통 비밀 숫자를 만들어 낼 수 있을까? 1976년 디피와 헬만이 "가능하다"고 답했다. 오늘날 HTTPS(TLS), SSH, 시그널·와츠앱 메시지가 매 연결마다 이 방식으로 세션 키를 정한다. 핵심 도구는 나머지 연산(mod)의 되돌리기 어려움 하나뿐이다.

1. 직관: 섞기는 쉽고, 되돌리기는 어렵다

물감은 섞으면 새 색이 되지만, 섞인 색만 보고 원래 두 색을 정확히 분리하는 건 매우 어렵다. 이 "한쪽으로만 쉬운" 성질을 이용한다. 공개된 바탕색에 각자 비밀색을 섞어 교환하고, 받은 색에 다시 자기 비밀색을 섞으면 둘 다 같은 최종색에 도달한다.

앨리스

공개 바탕색 + 비밀색(파랑)

= 앨리스가 공개로 보내는 색

밥

공개 바탕색 + 비밀색(빨강)

= 밥이 공개로 보내는 색

서로 받은 색 + 자기 비밀색을 한 번 더 섞으면 → 같은 최종색

앨리스: + = = 밥: +

도청자는 바탕색과 오간 두 색만 본다. 최종색을 만들려면 둘 중 누군가의 비밀색이 필요한데, 섞인 색에서 그걸 분리해 낼 수 없다. 숫자 버전에서는 이 "분리"가 이산 로그 문제다.

2. 숫자로 직접 해 보기 — `A = gᵃ mod p`

공개값: 소수 p와 밑 g. 비밀값: 앨리스의 a, 밥의 b (슬라이더로 바꿔 보기). 각자 공개키 = g^비밀 mod p를 계산해 교환하고, 받은 공개키에 자기 비밀을 지수로 올리면 g^ab mod p로 일치한다.

소수 p 23

밑 g 5

앨리스 비밀 a 6

밥 비밀 b 15

앨리스 (비밀 a)

공개키 A = g^a mod p
= 8

밥에게서 B 받음 → B^a mod p
= 2

밥 (비밀 b)

공개키 B = g^b mod p
= 19

앨리스에게서 A 받음 → A^b mod p
= 2

이브 (도청자)

엿본 값: p, g, A, B
23, 5, 8, 19

공유 비밀?
a나 b를 알아야만 계산 가능

앨리스 = 밥 = 2 ✓ 공유 비밀 성립

여기서 p는 장난감 크기(수십~수백)라 이브가 완전 탐색으로 a를 찾을 수 있다. 실제 TLS의 p는 2048~4096비트(십진수 600자 이상) 소수라, 지금까지 알려진 어떤 컴퓨터로도 gᵃ mod p에서 a를 되돌리지 못한다. 이 되돌리기가 이산 로그 문제다.

3. 교환 절차 한눈에

공개 합의: 큰 소수 p와 밑 g를 정한다. 누구나 봐도 된다.
앨리스가 비밀 a를 뽑아 A = g^a mod p를 계산해 밥에게 보낸다.
밥이 비밀 b를 뽑아 B = g^b mod p를 계산해 앨리스에게 보낸다.
앨리스: s = B^a mod p · 밥: s = A^b mod p.
둘 다 s = g^ab mod p로 같은 값. 이 s를 해시해서 대칭키(AES 등)로 쓴다.
도청자는 p, g, A, B만 안다. a나 b 없이는 s를 못 만든다.

지수 법칙 (g^a)^b = (g^b)^a = g^ab가 성립하는데 mod를 씌워도 그대로라서, 순서와 무관하게 같은 값이 나온다.

4. 파이썬으로 구현

# 공개 파라미터 (실제로는 RFC 3526의 검증된 큰 소수 사용)
p = 0xFFFFFFFF_FFFFFFFF_C90FDAA2_...   # 2048비트 이상
g = 2

import secrets, hashlib

a = secrets.randbelow(p - 2) + 2      # 앨리스 비밀
b = secrets.randbelow(p - 2) + 2      # 밥 비밀

A = pow(g, a, p)                     # 앨리스 공개키  (빠른 모듈러 거듭제곱)
B = pow(g, b, p)                     # 밥 공개키

s_alice = pow(B, a, p)               # B^a mod p
s_bob   = pow(A, b, p)               # A^b mod p
assert s_alice == s_bob            # 같은 공유 비밀!

key = hashlib.sha256(str(s_alice).encode()).digest()  # → AES 키

pow(g, a, p)는 "제곱하며 접기(square-and-multiply)"로 O(log a)번의 곱셈만 쓴다. 정방향은 눈 깜짝할 사이, 역방향(이산 로그)은 사실상 불가능 — 이 비대칭성이 안전성의 전부다.

5. 중간자 공격과 실제 사용

MITM 취약

DH 자체는 상대가 누구인지 확인하지 않는다. 중간자가 양쪽과 각각 DH를 맺으면 도청 가능.

해결: 인증 결합

공개키에 서명(RSA/ECDSA)이나 인증서를 붙여 신원을 증명. TLS가 이렇게 한다.

전방향 비밀성(PFS)

연결마다 새 임시 a, b를 쓰고 버린다(DHE/ECDHE). 서버 키가 나중에 털려도 과거 트래픽은 안전.

ECDH

같은 아이디어를 타원곡선 위에서. 훨씬 짧은 키(256비트)로 동급 안전성 → 요즘 표준.

쓰이는 곳

HTTPS 핸드셰이크, SSH, WireGuard VPN, 시그널·와츠앱(더블 래칫), 아이메시지.

양자 컴퓨터