DIffie-Hellman

디피-헬먼 키 교환(Diffie–Hellman key exchange)은 암호 키를 교환하는 하나의 방법으로, 두 사람이 암호화되지 않은 통신망을 통해 공통의 비밀 키를 공유할 수 있도록 한다. 휫필드 디피와 마틴 헬먼이 1976년에 발표하였다.

디피-헬먼 키 교환은 기초적인 암호학적 통신 방법을 수립하였으며, 이후 1977년 공개 키 암호 방식인 RSA 암호가 제안되었다.

DH 알고리즘의 핵심은 상대방의 공개키와 나의 개인키를 이용하여 계산을 하면 비밀키가 나온다는 것이다. 

DH 알고리즘은 "키 교환(key exchange)" 알고리즘으로 대칭키를 공유하는데 사용한다. 

이는 암호화나 서명을 위한 것은 아니다.

이는 이산 대수 문제(Discrete Logarithm Problem)(혹은 이산 로그)라는 방식을 이용하는데

일때 g와 x와 p를 안다면 y는 구하기 쉽지만

g와 y와 p를 알땐 x를 구하기는 어렵다는 방식에 착안하여 만들어진 알고리즘이다.

앨리스와 밥이 공개된 통신망에서 디피-헬먼 키 교환을 하기 위해서는 다음과 같은 절차를 거친다.

1. 앨리스가 소수 ${\displaystyle p}$, 그리고 ${\displaystyle 1}$부터 ${\displaystyle p-1}$까지의 정수 ${\displaystyle g}$를 선택하여 사전에 밥과 공유한다.
2. 앨리스가 정수 a를 선택한다. 이 정수는 외부에 공개되지 않으며, 밥 또한 알 수 없다.
3. 앨리스가 ${\displaystyle A=g^{a}{\text{ mod }}p}$, 즉 ${\displaystyle g^{a}}$를 ${\displaystyle p}$로 나눈 나머지를 계산한다.
4. 밥이 마찬가지로 정수 b를 선택하여 ${\displaystyle B=g^{b}{\text{ mod }}p}$를 계산한다.
5. 앨리스와 밥이 서로에게 ${\displaystyle A}$와 ${\displaystyle B}$를 전송한다.
6. 앨리스가 ${\displaystyle B^{a}{\text{ mod }}p}$를, 밥이 ${\displaystyle A^{b}{\text{ mod }}p}$를 계산한다.

마지막 단계에서 ${\displaystyle B^{a}{\text{ mod }}p=(g^{b})^{a}{\text{ mod }}p=g^{ab}{\text{ mod }}p}$, ${\displaystyle A^{b}{\text{ mod }}p=(g^{a})^{b}{\text{ mod }}p=g^{ab}{\text{ mod }}p}$이며 따라서 앨리스와 밥은 ${\displaystyle g^{ab}{\text{ mod }}p}$라는 공통의 비밀 키를 공유하게 된다.

앨리스와 밥 이외의 인물은 a와 b를 알 수 없으며, ${\displaystyle g,p,g^{a}{\text{ mod }}p,g^{b}{\text{ mod }}p}$를 알 수 있다.

예제

이 과정을 실제 숫자를 통해 예를 들면 다음과 같다. 여기서는 설명을 위해 작은 크기의 소수를 사용하지만, 실제 응용에서는 안전을 위해 10진수 수백~수천자리 크기의 큰 소수를 사용한다. 공개된 정보는 파란색으로, 비밀 정보는 붉은색 굵은 글씨로 표시하였다.

1. 앨리스와 밥은 p=23, g=5를 사용하기로 합의한다.
2. 앨리스가 비밀 정보를 전송하기 위해 임의의 정수 a=6을 고른 후, 밥에게 A = g^a mod p 을 전송한다.
   • A = 5⁶ mod 23
   • A = 15,625 mod 23
   • A = 8
3. 밥은 임의의 정수 b=15 를 고르고, 앨리스에게 B = g^b mod p 를 전송한다.
   • B = 5¹⁵ mod 23
   • B = 30,517,578,125 mod 23
   • B = 19
4. 앨리스는 밥에게서 받은 B 를 바탕으로 s = B ^a mod p 를 계산한다.
   • s = 19⁶ mod 23
   • s = 47,045,881 mod 23
   • s = 2
5. 밥은 앨리스에게서 받은 A 를 바탕으로 s = A ^b mod p 를 계산한다.
   • s = 8¹⁵ mod 23
   • s = 35,184,372,088,832 mod 23
   • s = 2
6. 앨리스와 밥은 이제 비밀 키 s = 2 를 공유하게 되었다.

여기서 ${\displaystyle p}$가 충분히 클 경우, 외부에서 비밀 키를 알아내기 위해 도청을 하는 도청자 이브는 ${\displaystyle g^{a}}$나 ${\displaystyle g^{b}}$를 통해 ${\displaystyle s}$를 알아낼 수 없는 것으로 알려져 있다. 앨리스와 밥은 두 사람 만이 아는 비밀 키 ${\displaystyle s}$를 갖게 되었으므로, 대칭키 암호를 이용해 이후의 통신을 암호화할 수 있다.

그러나 ${\displaystyle p}$나 ${\displaystyle a}$, ${\displaystyle b}$가 너무 작을 경우, 도청자는 가능한 모든 조합을 다 계산해보는 방식으로 ${\displaystyle s}$를 계산해낼 수 있다. 따라서 실제 비밀 통신에는 충분히 큰 소수를 사용해야 한다. 만약 ${\displaystyle p}$가 최소 300자리의 소수이고, ${\displaystyle a}$와 ${\displaystyle b}$가 각각 100자리 이상의 정수일 경우, 현재 인류가 보유한 모든 컴퓨터를 동원해도 공개된 정보로부터 비밀 키를 알아낼 수 없는 것으로 알려져 있다.

디피-헬먼 키 교환은 통신을 하는 대상과 비밀 정보를 공유할 수 있지만, 상대방에 대한 인증은 보장되지 않으며 중간자 공격이 가능하다. 앨리스와 밥이 상대방에 대한 인증을 하지 못할 경우, 공격자는 중간에서 통신을 가로채 앨리스와 공격자, 그리고 공격자와 밥 사이에 각각 두 개의 디피 헬먼 키 교환을 생성하고, 앨리스와 밥이 각각 서로와 통신을 하는 것처럼 위장할 수 있다. 이와 같은 종류의 중간자 공격을 막기 위한 여러가지 다른 알고리즘이 개발되어 있다.

다음은 Diffie-Hellman 키 사전분배 방법이다. 올바르게 나열한 것은 무엇인가?

(가) 소수 p와 각각의 사용자 A,B의 공개키를 공개한다.

(나) TA(Trusted Authority, 키 인증기관)는 적당한 계수를 가진 다음 다항식을 선택한다.

(다) TA는 다항식를 다음과 같이 계산하여 안전한 채널로 사용자 A에게 전송한다.

(라) A와 B가 서로 정보를 교환하기를 원할 때는 공통키(common key)를 사용하는 데 A와 B는 각각 공개되어 있는지를 각자의 다항식에 대신 대입한다.

1.(가) → (나) → (다) → (라)

2.(나) → (다) → (라) → (가)

3.(라) → (다) → (나) → (가)

4.(다) → (나) → (가) → (라)

정답 1