디피-헬먼 키 교환 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Diffie-Hellman-Schlüsselaustausch.svg|thumb]]
'''디피-헬먼 키 교환'''(Diffie–Hellman key exchange)은 [[키 (암호)|암호 키]]를 교환하는 하나의 방법으로, 두 사람이 암호화되지 않은 통신망을 통해 공통의 비밀 키를 공유할 수 있도록 한다.
[[휫필드 디피]]와 [[마틴 헬만]]이 1976년에 발표하였다.

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

== 방식 ==

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

# 앨리스가 [[소수 (수론)|소수]] <math>p</math>, 그리고 <math>1</math>부터 <math>p-1</math>까지의 정수 <math>g</math>를 선택하여 사전에 밥과 공유한다.
# 앨리스가 정수 a를 선택한다. 이 정수는 외부에 공개되지 않으며, 밥 또한 알 수 없다.
# 앨리스가 <math>A = g^a \text{ mod }p</math>, 즉 <math>g^a</math>를 <math>p</math>로 나눈 나머지를 계산한다.
# 밥이 마찬가지로 정수 b를 선택하여 <math>B = g^b \text{ mod }p</math>를 계산한다.
# 앨리스와 밥이 서로에게 <math>A</math>와 <math>B</math>를 전송한다.
# 앨리스가 <math>B^a \text{ mod }p</math>를, 밥이 <math>A^b \text{ mod }p</math>를 계산한다.

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

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

=== 예제 ===

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

# 앨리스와 밥은 ''<span style="color:blue">p</span>''=<span style="color:blue">23</span>, ''<span style="color:blue">g</span>''=<span style="color:blue">5</span>를 사용하기로 합의한다.
# 앨리스가 비밀 정보를 전송하기 위해 임의의 정수 '''''<span style="color:red">a</span>'''''='''<span style="color:red">6</span>'''을 고른 후, 밥에게 <span style="color:blue">A</span> = ''<span style="color:blue">g</span><sup>'''<span style="color:red">a</span>'''</sup>'' mod ''<span style="color:blue">p</span>'' 을 전송한다.
#* <span style="color:blue">A</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:blue">23</span>
#* <span style="color:blue">A</span> = '''<span style="color:red">15,625</span>''' mod <span style="color:blue">23</span>
#* <span style="color:blue">A</span> = <span style="color:blue">8</span>
# 밥은 임의의 정수 '''''<span style="color:red">b</span>'''''='''<span style="color:red">15</span>'''를 고르고, 앨리스에게 <span style="color:blue">B</span> = ''<span style="color:blue">g</span><sup>'''<span style="color:red">b</span>'''</sup>'' mod ''<span style="color:blue">p</span>''를 전송한다.
#* <span style="color:blue">B</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span>
#* <span style="color:blue">B</span> = '''<span style="color:red">30,517,578,125</span>''' mod <span style="color:blue">23</span>
#* <span style="color:blue">B</span> = <span style="color:blue">19</span>
# 앨리스는 밥에게서 받은 ''<span style="color:blue">B</span>''를 바탕으로 '''<span style="color:red">s</span>''' = ''<span style="color:blue">B</span>'' ''<sup>'''<span style="color:red">a</span>'''</sup>'' mod ''<span style="color:blue">p</span>''를 계산한다.
#* '''<span style="color:red">s</span>''' = <span style="color:blue">19</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">47,045,881</span>''' mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''
# 밥은 앨리스에게서 받은 ''<span style="color:blue">A</span>''를 바탕으로 '''<span style="color:red">s</span>''' = ''<span style="color:blue">A</span>'' ''<sup>'''<span style="color:red">b</span>'''</sup>'' mod ''<span style="color:blue">p</span>''를 계산한다.
#* '''<span style="color:red">s</span>''' = <span style="color:blue">8</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">35,184,372,088,832</span>''' mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''
# 앨리스와 밥은 이제 비밀 키 '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''를 공유하게 되었다.

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

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

== 안전성 ==

디피-헬먼 키 교환은 소수 <math>p</math>와 <math>g</math>를 적절하게 고르면 도청에 대해 안전한 것으로 알려져 있다. 도청자 ''이브''가 비밀키를 얻어내기 위해서는 ''앨리스''와 ''밥'' 사이의 통신에서 도청할 수 있는 정보인 <math>g^a</math>와 <math>g^b</math>로부터 <math>g^{ab}</math>를 구해야 한다. 이 문제를 '''디피-헬먼 문제'''(Diffie-Hellman problem)로 부르며, 이 문제를 푸는 효율적인 [[알고리즘]]은 아직까지 알려지지 않았다. [[이산 로그]] 문제를 효율적으로 풀 수 있을 경우 디피-헬먼 문제 또한 효율적으로 풀 수 있지만, 그 역이 참인지는 알려지지 않았다.

안전한 키 교환을 위해서는 <math>p</math>와 <math>g</math>를 신중하게 선택해야 한다. <math>g</math>는 [[순환군]] <math>G</math>의 차수가 소수이거나, 인수분해하기 어려운 큰 소수를 약수로 갖도록 해야 한다. 이 때문에 <math>p</math>와 <math>\frac{p-1}{2}</math>이 모두 소수인 [[소피 제르맹 소수|안전 소수]]를 고르기도 한다. <math>p</math>가 안전 소수일 경우 <math>G</math>의 차수는 <math>2</math> 또는 <math>\frac{p-1}{2}</math>만을 약수로 갖게 된다.

또한 앨리스와 밥이 충분히 안전하지 못한 난수 생성 알고리즘을 사용할 경우, 공격자는 이를 이용해 다음 <math>a</math>와 <math>b</math>의 특성을 어느정도 예측할 수 있다.

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

{{공개 키 암호 방식}}

[[분류:암호 프로토콜]]
[[분류:공개 키 암호]]