디피-헬먼 키교환 알고리즘

디피-헬먼(DH) 키교환 알고리즘은 GCHQ의 윌리엄슨에 의해 발명되었다. 그러다가 곧 독립적으로, 이름에서 짐작할 수 있듯이 화이트필즈 디피와 마틴 헬먼에 의해 재발명되었다.

DH는 암호화나 서명을 위해 사용되는것이 아니라 사용자가 비밀 공유를 설정하는 데 사용된다.
대칭키 암호의 근본적인 문제 중 하나가 키 설정의 문제이기 때문에 그 의미는 크다.

대칭키 암호에서 송수신자간 대칭된 키를 공유해야 되는데 이 때 키교환 시 사용한다는 말이다.

DH의 보안성은 이산 로그 문제의 계산 난이도에 의존한다.
이산 로그 문제는 비록 NP-complete 문제로 알려져 있지는 않지만 인수분해 문제처럼 풀기가 매우 어렵다.

DH 의 수학적 표현은 상대적으로 단순하다.
p를 소수라하고 q는 생성자라 하자.
여기서 어떤 x ∈ {1,2, ... ,p-1}에 대해 x = g^n mod p 를 만족하는 지수 n을 찾을 수 있다.

p의 값과 생성자 q는 공개되어 있다.
이제 키 교환을 위해 A는 자신의 비밀 지수 a를 생성하고, B는 그의 비밀 지수 b를 생성한다.
A는 (g^a mod p)를 B에게 보내고 B는 (g^b mod p)를 A에게 보낸다. 이어서 A는 다음을 계산한다.

(g^b)^a mod p = g^ab mod p

B도 유사한 방법으로 다음을 계산한다. 

(g^a)^b mod p = g^ab mod p 

그러면 (g^ab mod p) 가 공유한 비밀이 되어 통상적인 대칭키로 사용될 수 있다.

이 때 공격자 C는 중간에 (g^b)^a mod p, (g^a)^b mod p 를 볼 수 있기 때문에 (g^ab mod p) 를 거의 알 수 있는 것처럼 보이지만 C는
g^a * g^b = g^(a+b) ≠ g^ab mod p
위가 성립하기 때문에 쉽게 알 수가 없다.

C는 어려운 이산 로드 문제를 풀기 위해 필요한 a나 b를 찾아야한다.

이러한 DH 알고리즘은 중간자 공격에 민감하다.
이것은 C가 직접 A와 B 중간에 서서 오가는 메시지를 가로채는 능동적인 공격이다.

C가 앞서 말한 위치에 있으면 A와 B 간의 DH교환은 부서질 수 있다.

이렇게 되면 A나 B둘 중 누구도 잘못된 것을 알지 못하고 있는 사이에 C는 A와 B간에 오가는 모든 메시지를 읽고 변경할 수 있게 된다.

이러한 중간자 공격을 어떻게 막을 수 있을까??

1. 공유하는 대칭키로 DH교환을 암호화
2. 공개키로 DH교환을 암호화
3. 개인키로 DH값을 서명