홍라이프 계산기디피-헬먼 키 교환 쉽게 이해하기 — 개념과 원리
디피-헬먼(DH) 키 교환은 처음 만난 두 사람이 누구나 엿볼 수 있는 통신로에서 공통의 비밀값을 정하는 방법입니다. 이렇게 얻은 비밀값으로 암호화 키를 만듭니다. 이 계산기는 작은 수를 써서 각 단계를 손으로 확인할 수 있게 해 주며, 오늘날 HTTPS 연결에서도 주로 타원곡선 위에서 같은 원리가 쓰입니다.
계산 방법
앨리스와 밥은 소수 p와 생성원 g를 공개적으로 정합니다.
- 앨리스는 비밀 a를 고르고 A = gᵃ mod p를 보냅니다.
- 밥은 비밀 b를 고르고 B = gᵇ mod p를 보냅니다.
- 앨리스는 Bᵃ mod p, 밥은 Aᵇ mod p를 계산합니다.
두 값은 모두 g^(ab) mod p로 같아지며 이것이 공유 비밀입니다. 계산기는 모듈러 거듭제곱을 정확히 계산하고 양쪽 값이 같은지 확인합니다.
원리
지수끼리는 곱해지므로 (gᵇ)ᵃ = g^(ba) = (gᵃ)ᵇ이고, 단계마다 p로 나눈 나머지를 취해도 이 관계는 유지됩니다. 도청자는 p, g, A, B는 보지만 a와 b는 모릅니다. A에서 a를 되찾는 것은 이산 로그 문제이며, 충분히 큰 군에서는 gᵃ와 gᵇ만으로 g^(ab)를 구하는 것도 그만큼 어렵다고 여겨집니다. 원소가 23개인 이 예에서는 모든 지수를 대입해 볼 수 있지만, 2,048비트 군에서는 사실상 불가능합니다.
예제 풀이
- 입력값은 p = 23, g = 5, 앨리스의 a = 6, 밥의 b = 15입니다.
- A = 5⁶ mod 23 = 15,625 mod 23 = 8입니다.
- B = 5¹⁵ mod 23 = 19입니다.
- 앨리스는 19⁶ mod 23 = 2, 밥은 8¹⁵ mod 23 = 2를 얻습니다.
- 공유 비밀은 2이고 확인 결과는 match입니다.
| 앨리스의 비밀값 a | 공유 비밀값 |
|---|---|
| 1.5 | 2 |
| 3 | 5 |
| 4.5 | 5 |
| 6 | 2 |
| 7.5 | 2 |
| 9 | 10 |
| 12 | 4 |
결과 해석
match는 양쪽이 같은 값을 얻었다는 뜻으로, 정수를 입력하면 대수적으로 항상 성립합니다. g는 큰 부분군을 만들어야 하며, g를 잘못 고르면 가능한 비밀값이 몇 개로 줄어듭니다. 실제 시스템에서는 공유 값을 그대로 쓰지 않고 HKDF 같은 키 유도 함수를 거쳐 키로 만듭니다.
흔한 실수
- DH만으로 중간자 공격을 막을 수 있다고 생각합니다. 인증서나 서명으로 상대를 인증하지 않으면 공격자가 양쪽과 따로 교환할 수 있습니다.
- 세션마다 같은 a, b를 다시 써서 전방 비밀성을 잃습니다.
- a나 b를 0이나 1로 골라 A가 1이나 g가 됩니다.
자주 묻는 질문
디피-헬먼은 누가 만들었습니까?
1976년 휫필드 디피와 마틴 헬먼이 발표했으며, 랄프 머클의 공개 키 합의 아이디어가 바탕이 되었습니다.
ECDH와 X25519는 무엇입니까?
같은 교환을 타원곡선 군에서 하는 방식으로, 훨씬 짧은 키로 비슷한 보안을 얻어 더 빠릅니다.
디피-헬먼으로 메시지를 암호화합니까?
아닙니다. 비밀값만 합의하고, 실제 데이터는 AES 같은 대칭키 암호로 암호화합니다.
출처: W. Diffie, M. E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory 22(6), 1976 · IETF RFC 7748, Elliptic Curves for Security