[정보보안] Diffie-Hellman(디피헬만) 키 교환 알고리즘

Diffie-Hellman 알고리즘은 대칭키 배송 문제 해결 방법 중 하나입니다.

두 사람이나 시스템 간에 안전하게 통신하기 위해 비밀 키를 안전하게 교환하는 데 사용합니다.

---

Diffie-Hellman(디피-헬만) 알고리즘이란?

대칭키(비밀키)를 안전하게 교환하기 위한 알고리즘 중 하나입니다.

공개키 암호 시스템의 한 종류로서, 통신에 사용되는 공개 키와 개인 키를 생성하고 교환하여 통신의 안전성을 보장합니다.

---

Diffie-Hellman 알고리즘의 작동원리

1. 소수와 원시근 선택

• 두 통신 당사자가 함께 사용할 큰 소수(P)와 원시근(G)를 선택합니다.
• 두 통신 당사자는 서로 소수(P)와 원시근(G)를 공개합니다.

소수 선택 조건

• 충분히 큰 소수를 선택해야 합니다.
• 큰 소수를 선택함으로써 해킹 시도를 어렵게 만들어 보안성을 높일 수 있습니다.

원시근 선택 조건

• G가 P의 원시근이여야 합니다.
• 원시근의 거듭제곱이 P로 나누어 떨어지지 않는 모든 다른 수를 만들어야합니다.
• 선택한 원시근 G를 사용하여 G의 1승부터 G의 P-1승까리 계산 했을떄, 이 값들이 P로 나누어 떨어지면 안됩니다.
• 나누어 떨어지면 키 교환에 사용되는 숫자가 예측 가능해집니다.

---

2. 개인 키 생성

• 각 통신 당사자는 개인 비밀 키 (x,y)를 선택합니다.
• 개인키 x,y는 소수 P와 서로소인 수여야 합니다.

---

3. 공개 키 생성

• 각 당사자는 선택한 소수(P)와 원시근(G)를 사용하여 공개 키를 계산합니다.

공개 키 계산 공식

 

---

4. 비밀 키 생성

• 각 당사자는 상대방의 공개 키와 자신의 개인 키를 사용하여 공동으로 비밀 키를 생성합니다.
• 둘의 비밀 키 값이 동일하면 최종적으로 공유되는 대칭키가 됩니다.

---

5. 비밀 키 교환

• Alice는 Bob에게 비밀 키 Ka를 보냅니다.
• Bob은 Alice에게 비밀 키 Kb를 보냅니다.

---

6. 암호화와 복호화

• Alice와 Bob은 안전하게 공유된 비밀키를 사용하여 메시지를 암호화하고 복호화할 수 있습니다.

---

예제

Alice와 Bob은 소수(P)를 23으로 그 소수의 원시근(G) 5를 사용하여 디피헬만 알고리즘을 사용하여 비밀키를 공유하기로 했습니다. Alice의 개인 키는 6이고, Bob의 개인키는 15입니다. 이때 최종적으로 얻어지는 비밀 키의 값은 얼마입니까?

 

풀이

 

비밀 키 값이 모두 2이므로, 최종적으로 얻어지는 비밀 키의 값은 2입니다.