디피-헬만 키 교환

Diffie-Hellman Key Exchange

통신을 위한 공통 키를 안전하게 교환하는 방법

공개 키 암호화 방식 중 하나로, 비밀 키를 안전하게 교환하는 방법

• 앨리스
  1. 비밀 키 $a$를 생성
  2. $A = g^a \pmod{p}$를 계산하여 밥에게 전송
  3. $B$를 수신
  4. $K_{AB} = B^a \pmod{p}$를 계산
• 밥
  1. 비밀 키 $a$를 생성
  2. $B = g^b \pmod{p}$를 계산하여 앨리스에게 전송
  3. $B$를 앨리스에게 전송
  4. $A$를 수신
  5. $K_{BA} = A^b \pmod{p}$를 계산

• 앨리스
  1. 비밀 키 $a = 6$를 생성
  2. $A = 3^6 \pmod{31} = 729 \pmod{31} = 16$를 계산하여 밥에게 전송
  3. $B = 20$를 수신, $K_{AB} = 20^6 \pmod{31} = 64000000 \pmod{31} = 4$를 계산
• 밥
  1. 비밀 키 $b = 8$를 생성
  2. $B = 3^8 \pmod{31} = 4,294,967,296 \pmod{31} = 4$를 계산하여 앨리스에게 전송
  3. $A = 16$를 수신, $K_{BA} = 16^8 \pmod{31} = 4,294,967,296 \pmod{31} = 4$를 계산

• $K_{AB} = 4$
• $K_{BA} = 4$

중간자 공격

• 이브는 앨리스와 밥 사이의 비밀 키를 알고 싶어한다. $K_{AB} = K_{BA}$
• 이브는 $(p, g), (A = g^a \mod p), (B = g^b \mod p)$를 가지고 있다.
• 이브가 앨리스의 비밀 키 $a$ 또는 밥의 비밀 키 $b$를 알고 있다면
  • $K_{AB} = B^a = (g^b)^a = g^{ab} = (g^a)^b = A^b = K_{BA}$
  • 위의 식으로 인해 이브는 $K_{AB}$를 계산할 수 있다.
  • DLP(Diffie-Hellman Problem)이 어려운 문제이기 때문에 이브는 $a$ 또는 $b$를 계산할 수 없다.

• $(g, g^a, g^b)$가 주어졌을 때 $g^{ab}$를 계산하는 문제
  비공식적으로, CDH 문제의 어려움은 DLP의 어려움과 동등하며, 기본 군의 차수가 소수일 때 적용된다.

1. 앨리스와 밥이 키 교환을 수행
2. 이브는 앨리스와 밥 사이에 있음
3. 앨리스에게 $g^e$를 전송
4. 밥에게 $g^f$를 전송
5. 앨리스와 밥은 $g^{ef}$를 계산
6. 이브는 $g^{ef}$를 계산하여 앨리스와 밥 사이의 통신을 가로챔

1. 이브가 개인 키 $e$를 생성하고 $E = g^e \mod p$를 계산
2. 앨리스와 밥이 각각 $A$와 $B$를 서로에게 전송
3. 이브는 이를 가로채고, 모두에게 $E$를 전송
4. 앨리스와 밥은 $E$를 수신하고,
   $K_{AE} = E^a = g^{ea} \mod p$, $K_{BE} = E^b = g^{eb} \mod p$를 계산

• 나중에 앨리스가 $C = \text{Enc}(K_{AE}, M)$을 밥에게 보내면, 밥은 이를 해독할 수 없음
• 이브는 $K_{EA} = A^e = (g^a)^e \mod p$를 사용하여 $M$을 얻을 수 있다.

• 인증서 사용
  • 예를 들어, 앨리스와 밥이 서로의 공개 키 서명과 함께 보내서 서로의 공개 키를 확인할 수 있도록 함

• 디피-헬만 키 교환은 중간자 공격에 취약
• 이브가 앨리스와 밥 사이의 통신을 가로챌 수 있음
• 중간자 공격을 방지하기 위해 인증서를 사용