디피-헬만 키 교환(Diffie-Hellman Key Exchange) 정리

1. 기본 수학 기호

• g^x: g의 x제곱 (거듭제곱)
• mod p: p로 나눈 나머지 연산
• ≡: 합동 기호, $a ≡ b \ (\text{mod } p)$ → “a와 b를 p로 나눈 나머지가 같다”

2. 이산 로그 문제(Discrete Log Problem)

• 핵심 아이디어: DH 보안은 이산 로그 문제의 어려움에 기반
• 문제 예시:

• g, p, A는 공개값

• x는 개인키

• x를 구하는 것은 공격자가 계산으로는 사실상 불가능

• 쉽게 말하면:

“몇 번 곱해야 특정 나머지가 나오는지 알아내는 게 너무 어렵다”

3. 디피-헬만 프로토콜 단계

3.1 공개 매개변수 설정

• p: 큰 소수 (보통 1024비트 이상)
• g: p의 원시근(generator)
• p와 g는 모든 참가자가 공유하는 공개 값

3.2 개인키 생성

• 각자 비밀로 개인키 선택

  • Alice: a (1 < a < p-1)
  • Bob: b (1 < b < p-1)

3.3 공개키 계산 및 교환

• Alice → Bob: $A = g^a \mod p$
• Bob → Alice: $B = g^b \mod p$

공개키만 교환, 개인키는 절대 공개되지 않음

3.4 공유 비밀키 계산

• Alice: $K = B^a \mod p = g^{ab} \mod p$

• Bob: $K = A^b \mod p = g^{ab} \mod p$

• 같은 키가 나오는 이유:

4. 구체적 예시 (작은 수로 이해)

• 공개 매개변수: p = 23, g = 5

1. 개인키 선택

   • Alice: a = 6
   • Bob: b = 15

2. 공개키 계산

   • Alice: A = $5^6 \mod 23 = 8$
   • Bob: B = $5^{15} \mod 23 = 19$

3. 공유키 계산

   • Alice: K = $19^6 \mod 23 = 2$
   • Bob: K = $8^{15} \mod 23 = 2$

✅ 결과: Alice와 Bob 모두 K = 2 → 동일한 공유키

실제 DH에서는 p가 2048비트 이상 → 공격자가 개인키를 찾는 것은 거의 불가능

5. 보안 원리

5.1 공격자의 관점

• 공개 정보: g, p, A, B
• 비밀: a, b (개인키)
• 공격자는 이산 로그 문제를 풀어야 함 → 현실적으로 불가능

5.2 한계와 보완

• 중간자 공격(Man-in-the-Middle Attack)

  • 인증 없으면 공격자가 메시지를 바꿀 수 있음
  • 해결책: 디지털 서명 또는 인증서 추가

• 전방 보안성(Forward Secrecy)

  • 매 세션마다 임시 키 생성 → 개인키가 노출돼도 과거 세션 안전

6. 현대적 변형: 타원곡선 디피-헬만(ECDH)

• 같은 원리, 유한체 대신 타원곡선 위의 점 사용
• 장점: 더 작은 키(예: 256비트)로도 동일 보안 수준(≈3072비트 DH) 제공

7. 요약

• 디피-헬만(DH): 공개 채널에서 안전하게 공유 비밀키 생성
• 공개키 교환 → 공유키 계산
• 보안 핵심: 이산 로그 문제
• 현대 암호: ECDH + 인증으로 보안 강화