Diffie-Hellman 키 교환
키 교환의 딜레마
대칭키 암호화는 빠르고 효율적이다. 하지만 근본적인 문제가 있다. Alice와 Bob이 대칭키로 통신하려면 둘 다 같은 키를 알고 있어야 한다. 그런데 그 키를 어떻게 안전하게 공유할 수 있을까?
직접 만나서 전달하면 안전하지만 현실적이지 않다. 네트워크로 키를 보내면 도청당할 수 있다. 이것이 바로 "키 배포 문제(Key Distribution Problem)"다.
1976년 Whitfield Diffie와 Martin Hellman은 이 문제에 대한 혁신적인 해결책을 제시했다. 두 사람이 공개된 채널에서 메시지를 주고받으면서도, 도청자는 알 수 없는 공유 비밀(shared secret)을 만들어내는 방법이다.
Diffie-Hellman의 핵심 아이디어
Diffie-Hellman은 모듈러 지수 연산의 특성을 활용한다. 핵심은 "계산하기는 쉽지만 역으로 푸는 것은 어렵다"는 비대칭성이다.
먼저 Alice와 Bob은 공개적으로 두 숫자를 정한다. 큰 소수 p와 그 원시근(primitive root) g다. 이 값들은 도청자도 알 수 있다.
Alice는 비밀 정수 a를 선택하고, A = g^a mod p를 계산해서 Bob에게 보낸다. Bob은 비밀 정수 b를 선택하고, B = g^b mod p를 계산해서 Alice에게 보낸다.
이제 Alice는 B^a mod p를 계산한다. Bob은 A^b mod p를 계산한다. 수학적으로 이 두 값은 같다.
B^a mod p = (g^b)^a mod p = g^(ab) mod p
A^b mod p = (g^a)^b mod p = g^(ab) mod p
둘 다 g^(ab) mod p라는 같은 값을 얻게 된다. 이것이 공유 비밀이며, 이후 대칭키로 사용할 수 있다.
왜 안전한가
도청자 Eve는 p, g, A, B를 모두 알 수 있다. 하지만 공유 비밀 g^(ab)를 계산하려면 a나 b 중 하나를 알아야 한다.
A = g^a mod p에서 a를 구하는 것은 이산 로그 문제(Discrete Logarithm Problem)다. p가 충분히 크면(2048비트 이상) 현재 알려진 어떤 알고리즘으로도 현실적인 시간 내에 풀 수 없다.
구체적인 예시
작은 숫자로 과정을 따라가보자.
공개 파라미터로 p = 23, g = 5를 선택한다. Alice는 비밀 값 a = 6을 선택하고 A = 5^6 mod 23 = 8을 계산해서 Bob에게 보낸다. Bob은 비밀 값 b = 15를 선택하고 B = 5^15 mod 23 = 19를 계산해서 Alice에게 보낸다.
Alice는 공유 비밀 s = 19^6 mod 23 = 2를 계산한다. Bob은 공유 비밀 s = 8^15 mod 23 = 2를 계산한다. 둘 다 같은 값 2를 얻었다.
Eve가 8과 19만 보고 2를 알아내려면 a나 b를 추측해야 한다. 이 예시에서는 숫자가 작아서 쉽게 찾을 수 있지만, 실제로는 수백 비트 크기의 숫자를 사용한다.
중간자 공격의 취약점
Diffie-Hellman은 도청에는 안전하지만, 중간자 공격(Man-in-the-Middle Attack)에는 취약하다.
Mallory가 Alice와 Bob 사이에 있다고 하자. Alice가 A를 보내면 Mallory가 가로채고, 자신의 값 M1을 Bob에게 보낸다. Bob이 B를 보내면 Mallory가 가로채고, 자신의 값 M2를 Alice에게 보낸다.
결과적으로 Alice는 Mallory와 공유 비밀을 만들고, Bob도 Mallory와 별도의 공유 비밀을 만든다. Mallory는 중간에서 모든 통신을 복호화하고 다시 암호화해서 전달할 수 있다.
이 문제를 해결하려면 상대방의 신원을 확인하는 인증(authentication)이 필요하다. 디지털 서명이나 CA 인증서를 사용해서 "내가 통신하는 상대가 정말 Bob인가?"를 검증해야 한다.
현대적 활용
Diffie-Hellman은 TLS/SSL, IPsec, SSH 등 현대 암호화 프로토콜의 핵심 구성 요소다.
특히 ECDH(Elliptic Curve Diffie-Hellman)는 타원 곡선 암호화를 적용한 변형으로, 더 짧은 키 길이로 동일한 보안 수준을 제공한다. 256비트 ECDH가 3072비트 일반 DH와 비슷한 보안 강도를 갖는다.
Perfect Forward Secrecy(PFS)를 위해 매 세션마다 새로운 DH 키를 생성하는 것이 현대적인 관행이다. 이렇게 하면 나중에 서버의 개인키가 유출되어도 과거 통신 내용을 복호화할 수 없다.