디피-헬만 키 교환


1 개요

디피-헬만 키 교환(Diffie–Hellman key exchange)은 1976년에 발표된 비밀키 교환 방법으로, 공용키 암호인 엘가말(ElGamal)처럼 이산대수의 난해함에 그 안전성을 두고 있다.

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

2 방식

  • 앨리스: 통신자 1
  • 밥 : 통신자 2
  • 이브: 스니퍼

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

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

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

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

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

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

3 예제

  • 앨리스: 통신자 1
  • 밥: 통신자 2
  • 이브: 스니퍼

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

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

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

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

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

4 수학적 원리

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

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

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

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

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

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

5 구현 예제

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


#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()


#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()

6 공격 예제

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


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

6.1 실행 결과

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