[암호학] 7.4 Diffie-Hellman Key Exchange

암호화에서 중요한 문제는 두 사람이 DES, AES와 같은 암호화 프로토콜을 사용할 때 키를 선정하는 기준이다.

이 챕터에서는 기본적인 Diffie-Hellman 알고리즘을 바탕으로 이산 로그 계산의 어려움과 보안의 밀접한 관계를 설명한다.

---

모든 통신이 공개된 channel을 통해 이루어 진다 할 때, Alice와 Bob이 공통의 비밀키 K를 설정하는 방식에 대해 알아보자.

1. Alice 혹은 Bob이 안전하고 큰 수의 소수 p와 원시근 a (mod p)를 선택한다. (이때 p, a 모두 공개 가능)
2. Alice는 1<= x <= p-2 인 무작위 난수 x를 선택하고 Bob은 1<= y <= p-2인 무작위 난수 y를 선택한다.
3. Alice는 a^x(mod p)를 Bob에게 보내고, Bob은 a^y(mod p)를 Alice에게 보낸다.
4. 각자 받은 메시지를 사용하여 세션 키K를 계산한다. Alice는 K = a^xy (mod p)를 통해 K를 계산하고, Bob은 a^xy (mod p)를 통해 K를 계산한다. 그렇게 이 둘은 공통의 비밀키를 공유한다.

 

이때 K의 값이 같으므로 사전에 정해놓은 절차를 통해 키를 생성할 수 있다.

(예를 들어 56비트의 키를 뽑아내서 DES 키를 얻어낼 수 있음)

---

공격자 Eve가 Alice와 Bob의 통신을 엿듣고 있다고 가정하면 Eve는 a^x와 a^y를 알 수 있다.

만약 Eve가 이산로그 계산이 가능하다면 a^x의 이산 로그를 찾아 x를 얻을 수 있다. 이후 a^y에 x를 제곱하여 a^xy = K를 구할 수 있다. 이 경우 Alice, Bob과 같은 방법을 사용해 통신키를 추출할 수 있게 된다.

즉, Eve가 이산로그 계산이 가능하다면 보안 시스템 파괴가 가능하다.

 

하지만 Eve가 K를 찾기 위해 x, y를 필수적으로 계산해야하는 것은 아니다.

Eve가 풀어야 할 문제는 크게 2가지 이다.

1) Computational Diffie-Hellman Problem

- 소수 p, 원시근 a (mod p) 이고 a^x(mod p)와 a^y(mod p)가 주어졌을 때, a^xy (mod p)를 찾는 문제

2) Decision Diffie-Hellman Problem

- 소수 p, 원시근 a (mod p) 이고 a^x(mod p)와 a^y(mod p)가 주어지고, c != 0 (mod p)일 때, c = a^xy(mod p)인 c를 찾는 문제

 

만약 Eve가 c = a^xy (mod p)를 발견했다고 주장한다면 이 주장이 사실인지 아닌지 어떻게 알 수 있을까?

Diffie-Hellman problem을 해결 할 수 있으면 a^xy (mod p)를 계산해서 c가 맞는지 확인만 하면 된다.

 

하지만 Diffie-Hellman problem을 해결하는 방법은 현재까지 알려지지 않았다. brute force 공격을 사용해서 수많은 c를 선택하고 a^xy (mod p)가 되도록 각 값을 확인하는 방법만이 있는데, 이 방법은 이산로그 문제를 계산하는 것만큼 시간이 걸려 비현실적이다.

 

이는 타원곡선과 비슷한 부분이 존재하는데, decision Diffie-Hellman의 경우 빠른 해결법이 알려져 있지만 Diffie-Hellman problem에 대해서는 아직 실질적인 해결법이 알려져 있지 않다.