문서:디피-헬만 키 교환

[목차]
== 개요 ==
디피-헬만 키 교환(Diffie–Hellman key exchange)은 1976년에 발표된 비밀키 교환 방법으로, 이산대수의 난해함에 그 안전성을 두고 있다. 엘가말(ElGamal) 방식이 디피-헬만 키 교환을 참고해 만들어졌다.

통신 전체가 악의적인 스니퍼에 의해서 도청되고 있더라도 키 값(후술할 [math(K_a)]와 [math(K_b)], 이 두 값은 같기 때문에 '키'로 통칭함)을 정할 수 있게 해주는 원리는 바로, 키 값을 전달하는 것이 아니라 '''키 값을 만드는 방법'''을 전달하기 때문이다.

== 방식 ==
 * 앨리스: 통신자 1
 * 밥 : 통신자 2
 * 이브: 스니퍼

앨리스와 밥은 암호화 통신을 성립시키기 위해 상호간 비밀키를 교환하고자 한다. 현재 모든 연결은 암호화되지 않은 상태로 이브에게 노출되고 있다. 이때 앨리스는 밥에게 충분히 큰 소수 [math(P)]와 적절한 정수 [math(G)]를 공개한다. [math(P)]와 [math(G)] 모두 누구의 손에 들어가든 상관 없다.

앨리스는 [math(P)] 미만의 정수 [math(a)]를 임의로 선택하고, [math(A \equiv G^a (mod\ P))]를 만족하는 [math(A)]를 밥에게 전송한다. '''이때 [math(a)]는 앨리스만 알아야 하며''', [math(A)]는 누구의 손에 들어가든 상관 없다.

밥은 [math(P)] 미만의 정수 [math(b)]를 임의로 선택하고, [math(B \equiv G^b (mod\ P))]를 만족하는 [math(B)]를 앨리스에게 전송한다. '''이때 [math(b)]는 밥만 알아야 하며''', [math(B)]는 누구의 손에 들어가든 상관 없다.

앨리스는 이미 공개된 [math(P)]와 [math(B)], 그리고 자신만 알고 있는 [math(a)]로부터 [math(K_a \equiv B^a (mod\ P))]를 만족하는 [math(K_a)]를 계산한다.

밥은 이미 공개된 [math(P)]와 [math(A)], 그리고 자신만 알고 있는 [math(b)]로부터 [math(K_b \equiv A^b (mod\ P))]를 만족하는 [math(K_b)]를 계산한다.

이때의 [math(K_a)]와 [math(K_b)]는 같은 값이 되지만, [math(a)]와 [math(b)] 둘 중 하나도 알지 못하는 이브는 현실적으로 키 값을 알 수 없다.

== 예제 ==
 * 앨리스: 통신자 1
 * 밥: 통신자 2
 * 이브: 스니퍼(=해커)

앨리스와 밥은 통신에 앞서 [math(P = 97)]과 [math(G = 5)]를 선택한다.

앨리스는 [math(P)] 미만의 임의의 정수 [math(a = 47)]을 선택하고 [math(5^{47} (mod\ 97) \equiv A = 58)]를 밥에게 전송한다.

밥은 [math(P)] 미만의 임의의 정수 [math(b = 51)]을 선택하고, [math(5^{51} (mod\ 97) \equiv B = 69)]를 앨리스에게 전송한다.

앨리스는 이미 공개된 [math(P = 97)]과 [math(B = 69)], 그리고 자신만 알고 있는 [math(a = 47)]로부터 [math(K_a \equiv 69^{47} (mod\ 97))]를 만족하는 [math(K_a = 52)]를 계산한다.

밥은 이미 공개된 [math(P = 97)]과 [math(A = 58)], 그리고 자신만 알고 있는 [math(b = 51)]로부터 [math(K_b \equiv58^{51} (mod\ 97))]를 만족하는 [math(K_b = 52)]를 계산한다.

== 수학적 원리 ==
개요에 짧게 기술했듯, 본 알고리즘은 이산대수의 난해함이 안전성의 기반이 된다. 앞선 예제에서 나온 마법의 식 [math(G^a (mod\ P))]을 보자.

본문에서는 적절한 정수 [math(G)]라고 표기했지만 엄밀하게 말하면 [math(G)]값은 [math(P)]의 곱셈군 [math(ZP*)]에서 생성자(Generator) 값을 사용해야 한다. 위 이산대수의 식에서 적절한 생성자로부터 도출되는 수들은 [math(G)]를 제곱하는 수(본 식에서는 [math(a)])의 값이 [math(P)] 미만이라는 가정 하에 [math(P)] 미만의 모든 숫자가 한 번씩 등장하게 된다.

이러한 생성자를 구하는 방법은 간단하다. [[군(대수학)|군]][[환(대수학)|환]][[체(대수학)|체]]론 관련 문서에서 적절히 설명하지 않는 관계로 여기에서 설명한다. [math(P-1)]을 [[소인수분해]]한다고 하자. 예제의 [math(P = 97)]에서 [math(P-1 = 96)]을 소인수분해해 보자. 그렇다면 [math(P-1 = p_1^{e_1} \times \cdots \times p_i^{e_i})]과 같은 형태를 띄게 된다. 예제의 경우에는 [math(96 = 2^5 \times 3)]이다. 이제 [math(h(i) = \displaystyle \frac{P-1}{p_i})]를 구하자. 예제의 경우에서는 [math(p_1 = 2,\ p_2 = 3)]이므로 [math(h(1) = \displaystyle \frac{96}{2} = 48)]이고, [math(h(2) = \displaystyle \frac{96}{3} = 32)]이다.

이제 [math(Z97*)]의 원소 [math(\{1,\ 2,\ \cdots,\ 95,\ 96\})] 중 임의로 하나(여기서는 [math(y)])를 뽑아 [math(y^{h(i)} (mod\ P) \equiv 1)]이 성립하지 않는지 확인한다. 가령 저 원소 중 랜덤으로 [math(11)]을 뽑았다고 치자. 이 경우 [math(11^{48} (mod\ 97) \equiv 1)]이므로 [math(11)]은 이 군의 생성원이 아니지만, [math(5)]의 경우에는 [math(5^{48} (mod\ 97) \equiv 96)], [math(5^{32} (mod\ 97) \equiv 53)]이므로 [math(5)]는 [math(Z97*)]의 생성원이다.

그렇다면 [math(G)] 값이 적절한 생성자가 아니라면 무슨 일이 일어날까? 바로 충돌값이 생기게 된다. 가령 [math(a)] 값을 1024로 정해놨는데 512로도 풀릴 수 있다는 이야기다.

그렇다면 [math(K_a)]와 [math(K_b)]가 같은 값이라는 것은 어떻게 증명될까? 증명은 의외로 간단하다. 다시 마법의 식을 보자(뒤에 붙은 모듈러 연산은 이해를 돕기 위해 생략한다.). [math(A \equiv G^a)], [math(B \equiv G^b)], [math(K_a \equiv B^a)], [math(K_b \equiv A^b)]의 네 가지 식이 있다. 이 식을 [math(K_a \equiv (G^b)^a)], [math(K_b \equiv (G^a)^b)]의 두 가지로 줄여보자. 제곱의 위치는 상관이 없으니 [math(G)]에 [math(a)]를 제곱한 뒤 [math(b)]를 제곱하건 [math(b)]를 제곱한 뒤 [math(a)]를 제곱하건 값에는 상관이 없다.

== 구현 예제 ==
아래는 [[Python]] 알고리즘 코드 예제이다. 차례대로 서버와 클라이언트 한 쌍으로 구현되어 있고, 디피-헬만으로 적절한 키를 만든 후 이를 [[MD5]]로 가공한 후 서버의 현재 시간을 [[AES]]하여 클라이언트로 보내는 프로그램이다. 실질적인 암호화의 의의는 없으나 가동 방식 등을 익히는데에는 좋은 예제이다. Python2로 돌리자.

{{{#!syntax python
#server

import socket
import random
import hashlib
import base64
from datetime import date
from Crypto import Random
from Crypto.Cipher import AES

BS = 16
pad = lambda s: s + (BS - len(s) % BS) * chr(BS - len(s) % BS).encode()
unpad = lambda s: s[:-ord(s[len(s)-1:])]

def iv():
    return chr(0) * 16

class AESCipher(object):

    def __init__(self, key):
        self.key = key

    def encrypt(self, message):
        message = message.encode()
        raw = pad(message)
        cipher = AES.new(self.key, AES.MODE_CBC, iv())
        enc = cipher.encrypt(raw)
        return base64.b64encode(enc).decode('utf-8')

    def decrypt(self, enc):
        enc = base64.b64decode(enc)
        cipher = AES.new(self.key, AES.MODE_CBC, iv())
        dec = cipher.decrypt(enc)
        return unpad(dec).decode('utf-8')

server_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server_socket.bind(("", 9417))
server_socket.listen(5)


print "Server is Ready"

while 1:
	client_socket, address = server_socket.accept()
	print "New Connection from ", address[0], ":", address[1]
	P = 99877
	G = 99875
	a = random.randint(1, P-1)
	A = pow(G, a)%P

	A = str(A)
	client_socket.send(A.encode())
	B = client_socket.recv(128).decode()
	B = int(B)
	
	Ka = pow(B, a)%P	
	Ka = str(Ka).encode("utf-8")
	sha = hashlib.md5(Ka)
	AES_Key = sha.hexdigest()
	AES_Key = str(AES_Key)

	today = str(date.today())
	encode = AESCipher(AES_Key).encrypt(today)
	client_socket.send(encode.encode())
	print "End-To-End Secure Send Done"
	client_socket.close()
server_socket.close()
}}}

{{{#!syntax python
#client

import socket
import random
import hashlib

import base64
import hashlib
from Crypto import Random
from Crypto.Cipher import AES

BS = 16
pad = lambda s: s + (BS - len(s) % BS) * chr(BS - len(s) % BS).encode()
unpad = lambda s: s[:-ord(s[len(s)-1:])]

def iv():
    return chr(0) * 16

class AESCipher(object):

    def __init__(self, key):
        self.key = key

    def encrypt(self, message):
        message = message.encode()
        raw = pad(message)
        cipher = AES.new(self.key, AES.MODE_CBC, iv())
        enc = cipher.encrypt(raw)
        return base64.b64encode(enc).decode('utf-8')

    def decrypt(self, enc):
        enc = base64.b64decode(enc)
        cipher = AES.new(self.key, AES.MODE_CBC, iv())
        dec = cipher.decrypt(enc)
        return unpad(dec).decode('utf-8')

P = 99877
G = 99875
b = random.randint(1, P-1)
B = pow(G, b)%P

client_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client_socket.connect(("127.0.0.1", 9417))

A = client_socket.recv(128).decode()
B = str(B)
client_socket.send(B.encode())
A = int(A)
Kb = pow(A, b)%P
Kb = str(Kb).encode("utf-8")
sha = hashlib.md5(Kb)
AES_Key = sha.hexdigest()
AES_Key = str(AES_Key)

print "End-To-End Secure Line Has Connected!"
decode = client_socket.recv(4096).decode()
today = AESCipher(AES_Key).decrypt(decode)
print today

client_socket.close()
}}}

== 공격 예제 ==
본 예제에서는 성실하고 근면하게(...) 브루트 포스로 뚫어보자. [[Python|Python3]]로 돌리면 된다.

{{{#!syntax python
import math
import time

P = int(input("input Prime : "))
G = int(input("input G : "))

while 1:
	a = int(input("input a(private) : "))
	if (a >= P):
		print("must x < ", P)
	else:
		break
A = int(pow(G, a)%P)

while 1:
	b = int(input("input b(private) : "))
	if (b >= P):
		print("must y < ", P)
	else:
		break
B = int(pow(G, b)%P)
Ka = int(pow(B, a)%P)
Kb = int(pow(A, b)%P)

i = int(1)

t1 = time.time()

while i < P:
	if (A == pow(G, i)%P):
		print("find!", i)
		break
	print(i)
	i = i + 1

t2 = time.time()
print("P :  ", P)
print("G :  ", G)
print("A :  ", A)
print("a :  ", a)
print("B :  ", B)
print("b :  ", b)
print("Ka : ", Ka)
print("Kb : ", Kb)
print(t2-t1)
}}}

=== 실행 결과 ===
{{{
namu@wiki:~$ python3 DH.py
input Prime : 17
input G : 3
input a(private) : 13
input b(private) : 11
1
#숫자 생략
12
find! 13
P :   17
G :   3
A :   12
a :   13
B :   7
b :   11
Ka :  6
Kb :  6
0.00017547607421875
}}}
== 관련 문서 ==
 * [[암호 알고리즘]]
[[분류:컴퓨터 보안]][[분류:암호학]][[분류:컴퓨터과학 프로젝트]]