Diffie-Hellman 키분배 알고리즘

출처 : http://n1emand.blogspot.com/2012/01/diffie-hellman.html

Diffie-Hellman 키분배 알고리즘

[알고리즘]
Diffie-Hellman 키분배 알고리즘

Public Key 암호화 기법을 제안한 Diffie-Hellman은 이 기법에서 생성된 키를 안전
하게 송/수신자들에게 분배하는 알고리즘을 제안하였다. 즉, 이 알고리즘은 비밀키
와 공개키를 생성하여 암호화와 복호화를 수행하는 방식에 관한 알고리즘이 아니라
메세지를 주고 받으려는 두 명의 사람이 비밀리에 비밀키를 공유하기 위한 방법이라
는 것을 잊지 말도록 하자. 현재 이 방식은 상용 보안 소프트웨어에 널리 사용되고
있다

Diffie-Hellman의 키분배 알고리즘을 간단하게 설명하면 다음과 같다.

<전제 조건>
n,g : 크기가 큰 정수들로서 메세지의 송수신에 참여하는 모든 사람들에게 공개되어
있다. 그리고 특히 g값은 n보다는 작고 1보다는 크다.

1.송신자는 비교적 크기가 큰 난수 x를 발생시키고 이 값을 보관한다.
2.수신자 역시 비교적 크기가 큰 난수 y를 발생시키고 이값을 보관한다.
3.송신자는 다음의 계산을 하여 그 결과를 수신자에게 보낸다.
X = gx mod n
4.수신자는 다음의 계산을 하여 그 결과를 송신자에게 보낸다.
Y = gy mod n
5.송신자는 Y를 받아서 다음의 계산을 한 후 비밀키 Ks를 얻는다.
Ks = (Y)x mod n = gyx mod n
6.수신자는 X를 받아서 다음의 계산을 한 후 비밀키 Kr을 얻는다.
Kr = (X)y mod n = gxy mod n
위의 (e)와 (f)에서 계산된 결과인 Ks와 Kr이 같은 값을 갖는다는 것을 쉽게 알 수
있을것이다. 따라서 송신자와 수신자는 이 값을 비밀키로하여 메세지를 암호화/복호
화할 수 있게 된다.
계산된 비밀키(Kr 또는 Ks)가 왜 비밀키인가? 라고 의아해 할 독자를 위해 위의 과
정을 정리하면 다음과 같다.

◆수신자와 송신자가 주고 받는 값들(즉 공격자에게 노출될 가능성이 많은 값들)

X(=gx), Y(=gy)


◆모든 사람들이 다 알고 있는 값들(즉, 공격자도 이미 다 알고 있는 값들)


n, g


◆송신자만이 알고 있는 값(그래서 안전하다고 생각되는 값)


x


◆수신자만이 알고 있는 값(그래서 안전하다고 생각되는 값)


y


따라서 공격자가 최대한으로 얻을 수 있는 정보는 n, g, X, Y이다. 공격자들이 비밀
키를 계산하기 위해서는 x 또는 y의 값을 알아야 한다. 이 값을 알기 위해서는 다음
의 계산에서 x 또는 y를 구해야 한다.

X = gx mod n
Y = gy mod n

위의 식에 있어서 (X, g, n), (Y, g, n)을 알고 있고 n이 충분히 클 경우 x, y를
구하는 것은 수학적으로 불가능(infeasible)하다고 알려져 있다(일방향 함수의 특성
). 따라서 비밀키(Kr, Ks)는 비밀키이다.

그러나 Diffie-Hellman의 알고리즘을 공략할 수 있는 공격방법이 없는 것없는 것은
아니다. 즉, 알고리즘 자체는 수학적으로 안전하다고 할 수 있지만 사실 암호 프로
토콜중에 헛점(security hole)이 없는 것은 아무것도 없다. 소위 흉내내기 공격법(i
mpersonation attack)이란 것이 Diffie-Hellman 키 분배 프로토콜의 공격방법이다.

즉, 공격자가 송신자와 수신자의 사이에서 "송신자에게는 공격자 자신이 수신자인
것처럼" 그리고 "수신자에게는 공격자 자신이 송신자인 것처럼" 속이는 방법이다.
이방법은 다음과 같이 이루어진다.

<전제 조건>
공격자는 송신자와 수신자가 주고 받는 모든 데이타를 얻을 수 있다.


1.공격자는 송신자가 보낸 X값을 가로채서 보관하고 자신이 생성시킨 난수값 z을 이
용하여 Z를 송신자와 수신자에게 보낸다.
Z = gz mod n
2.공격자는 수신자로부터 Y값을 얻는다.
3.송신자와 수신자는 자신들이 얻은 값 Z를 이용하여 다음의 비밀키를 생성한다.
송신자 : Kxz = gxz mod n
수신자 : Kzy = gzy mod n
4.공격자는 (b)에서 얻은 X, Y 값을 이용하여 다음의 비밀키를 계산할 수 있다.
송신자용 비밀키 : gzx mod n
수신자용 비밀키 : gzy mod n

결과적으로 Kxz와 Kzy라는 두개의 비밀키가 생성되어 전자는 송신자와 공격자가 통
신을 하는 데 사용되고 후자는 공격자와 수신자가 통신을 하는데 사용된다. 당연히
송신자와 수신자는 서로가 서로에게 메세지를 안전하게(?) 주고 받는 다고 착각을
하고 있게 된다.