- 관련 문서: 암호 알고리즘
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