디피-헬만 키 교환 알고리즘(Diffie-Hellman key exchange)

디피라는 사람과 헬만 이라는 사람이 공동 개발했다고 해서 디피-헬만법이다. 경우에 따라 디피-헬만 프로토콜이라고도 한다.

 - 비대칭키(공개키) 알고리즘에서 사용되는 키 교환 방식이다.
 - 상대방의 공개키와 나의 비밀키를 이용하여 비밀키를 생성한다.
 - A의 공개키와 B의 개인키를 DH연산하면 B의 비밀키가 되고
 - B의 공개키와 A의 개인키를 DH연산하면 A의 비밀키가 된다.
 - 이산대수법에 의거한 수학적 공식에 의해 A의 비밀키와 B의 비밀키는 같아진다.
 - 송신자와 수신자는 이 비밀키를 사용하여 데이터를 암호화한 후 전달한다.

최초의 공개키 교환 알고리즘으로 IPSec, S-HTTP, SSL등 많은 프로토콜에서 기본적으로 사용하는 중요한 알고리즘이다. RSA또한 이 디피-헬만법에서 아이디어를 얻었다. (단, RSA는 이산대수법은 아님)

디피-헬만법은 이산대수의 어려움을 이용한 알고리즘이다. 쉽게 말해 주어진 g, x, p 를 이용하여 y = g^x mod p 를 구하기는 쉽지만 g, y , p 값을 이용하여 원래의 x를 찾기 어렵다는 원리를 이용한 것이다.

절차

A는 임의의 큰 수 11를 선택했다. 2^11 mod 17 = 8

B는 임의의 큰 수 13를 선택했다. 2^13 mod 17 = 15

A는 B에게 8을 보낸다.

B는 A에게 15을 보낸다.

A는 받은 15으로 계산한다. 15^11 mod 17 = 9

B는 받은 8로 계산한다.  8^13 mod 17 = 9

A만 알고 있는 키는 11이다.

B만 알고 있는 키는 13이다.

둘다 알고 있는 키는 2, 17, 8, 15, 9이다.

11과 13이라는 각각의 개인키는 노출 될 일이 없다. 둘 다 알고 있는 2, 17, 8, 15, 9는 노출될 수 있다.

지금은 예시이기 때문에 매우 작은 숫자를 이용하였으나, 숫자가 수십~수백자리로 커지게 되면 2, 17, 8, 15, 9에 해당하는 숫자는 노출이 되어도 이를 역으로 11과 13을 유추해 내기가 매우매우 힘들다는 것이 수학적 안전성의 근거이다.

취약점
신분위장 공격에 취약하다 : 애초에 B가 아닌 사람이 B인척 하거나 연산된 결과인 비밀키만 취득한 제 3자가 B 행세를 할 수도 있다.
재전송 공격에 취약하다 : 단순히 비밀키로 잘 암호화 되어왔는지만 확인하므로 암호화된 정보를 스니핑 해서 재전송 함으로써 행위를 조작할 수 있다.

참고

인수분해 기반 : RSA

이상대수법 기반 : ElGamel, Diffie-Hellman, ECC