- 관련 문서: 암호 알고리즘
1 개요
디피-헬만 키 교환(Diffie–Hellman key exchange)은 1976년에 발표된 비밀키 교환 방법으로, 공용키 암호인 엘가말(ElGamal)처럼 이산대수의 난해함에 그 안전성을 두고 있다.
통신 전체가 악의적인 스니퍼에 의해서 도청되고 있더라도 키 값(후술할 Ka와 Kb, 이 두 값은 같기 때문에 '키'로 통칭함)을 정할 수 있게 해주는 원리는 바로, 키 값을 전달하는 것이 아니라 키 값을 만드는 방법을 전달하기 때문이다.
2 방식
- 앨리스: 통신자 1
- 밥 : 통신자 2
- 이브: 스니퍼
앨리스와 밥은 암호화 통신을 성립시키기 위해 상호간 비밀키를 교환하고자 한다. 현재 모든 연결은 암호화되지 않은 상태로 이브에게 노출되고 있다. 이때 앨리스는 밥에게 충분히 큰 소수 P와 적절한 정수 G를 공개한다. P와 G 모두 누구의 손에 들어가든 상관 없다.
앨리스는 P 미만의 정수 a를 임의로 선택하고, A≡Ga(mod P)를 만족하는 A를 밥에게 전송한다. 이때 a는 앨리스만 알아야 하며, A는 누구의 손에 들어가든 상관 없다.
밥은 P 미만의 정수 b를 임의로 선택하고, B≡Gb(mod P)를 만족하는 B를 앨리스에게 전송한다. 이때 b는 밥만 알아야 하며, B는 누구의 손에 들어가든 상관 없다.
앨리스는 이미 공개된 P와 B, 그리고 자신만 알고 있는 a로부터 Ka≡Ba(mod P)를 만족하는 Ka를 계산한다.
밥은 이미 공개된 P와 A, 그리고 자신만 알고 있는 b로부터 Kb≡Ab(mod P)를 만족하는 Kb를 계산한다.
이때의 Ka와 Kb는 같은 값이 되지만, a와 b 둘 중 하나도 알지 못하는 이브는 현실적으로 키 값을 알 수 없다.
3 예제
- 앨리스: 통신자 1
- 밥: 통신자 2
- 이브: 스니퍼
앨리스와 밥은 통신에 앞서 P=97과 G=5를 선택한다.
앨리스는 P 미만의 임의의 정수 a=47을 선택하고 547(mod 97)≡A=58를 밥에게 전송한다.
밥은 P 미만의 임의의 정수 b=51을 선택하고, 551(mod 97)≡B=69를 앨리스에게 전송한다.
앨리스는 이미 공개된 P=97과 B=69, 그리고 자신만 알고 있는 a=47로부터 Ka≡6947(mod 97)를 만족하는 Ka=52를 계산한다.
밥은 이미 공개된 P=97과 A=58, 그리고 자신만 알고 있는 b=51로부터 Kb≡5851(mod 97)를 만족하는 Kb=52를 계산한다.
4 수학적 원리
개요에 짧게 기술했듯, 본 알고리즘은 이산대수의 난해함이 안전성의 기반이 된다. 앞선 예제에서 나온 마법의 식 Ga(mod P)을 보자.
본문에서는 적절한 정수 G라고 표기했지만 엄밀하게 말하면 G값은 P의 곱셈군 ZP∗에서 생성자(Generator) 값을 사용해야 한다. 위 이산대수의 식에서 적절한 생성자로부터 도출되는 수들은 G를 제곱하는 수(본 식에서는 a)의 값이 P 미만이라는 가정 하에 P 미만의 모든 숫자가 한 번씩 등장하게 된다.
이러한 생성자를 구하는 방법은 간단하다. 군환체론 관련 문서에서 적절히 설명하지 않는 관계로 여기에서 설명한다. P−1을 소인수분해한다고 하자. 예제의 P=97에서 P−1=96을 소인수분해해 보자. 그렇다면 P−1=pe11×⋯×peii과 같은 형태를 띄게 된다. 예제의 경우에는 96=25×3이다. 이제 h(i)=P−1pi를 구하자. 예제의 경우에서는 p1=2, p2=3이므로 h(1)=962=48이고, h(2)=963=32이다.
이제 Z97∗의 원소 {1, 2, ⋯, 95, 96} 중 임의로 하나(여기서는 y)를 뽑아 yh(i)(mod P)≡1이 성립하지 않는지 확인한다. 가령 저 원소 중 랜덤으로 11을 뽑았다고 치자. 이 경우 1148(mod 97)≡1이므로 11은 이 군의 생성원이 아니지만, 5의 경우에는 548(mod 97)≡96, 532(mod 97)≡53이므로 5는 Z97∗의 생성원이다.
그렇다면 G 값이 적절한 생성자가 아니라면 무슨 일이 일어날까? 바로 충돌값이 생기게 된다. 가령 a 값을 1024로 정해놨는데 512로도 풀릴 수 있다는 이야기다.
그렇다면 Ka와 Kb가 같은 값이라는 것은 어떻게 증명될까? 증명은 의외로 간단하다. 다시 마법의 식을 보자(뒤에 붙은 모듈러 연산은 이해를 돕기 위해 생략한다.). A≡Ga, B≡Gb, Ka≡Ba, Kb≡Ab의 네 가지 식이 있다. 이 식을 Ka≡(Gb)a, Kb≡(Ga)b의 두 가지로 줄여보자. 제곱의 위치는 상관이 없으니 G에 a를 제곱한 뒤 b를 제곱하건 b를 제곱한 뒤 a를 제곱하건 값에는 상관이 없다.
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