Loading [MathJax]/jax/output/HTML-CSS/jax.js

디피-헬만 키 교환


1 개요

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

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

2 방식

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

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

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

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

앨리스는 이미 공개된 PB, 그리고 자신만 알고 있는 a로부터 KaBa(mod P)를 만족하는 Ka를 계산한다.

밥은 이미 공개된 PA, 그리고 자신만 알고 있는 b로부터 KbAb(mod P)를 만족하는 Kb를 계산한다.

이때의 KaKb는 같은 값이 되지만, ab 둘 중 하나도 알지 못하는 이브는 현실적으로 키 값을 알 수 없다.

3 예제

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

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

앨리스는 P 미만의 임의의 정수 a=47을 선택하고 547(mod 97)A=58를 밥에게 전송한다.

밥은 P 미만의 임의의 정수 b=51을 선택하고, 551(mod 97)B=69를 앨리스에게 전송한다.

앨리스는 이미 공개된 P=97B=69, 그리고 자신만 알고 있는 a=47로부터 Ka6947(mod 97)를 만족하는 Ka=52를 계산한다.

밥은 이미 공개된 P=97A=58, 그리고 자신만 알고 있는 b=51로부터 Kb5851(mod 97)를 만족하는 Kb=52를 계산한다.

4 수학적 원리

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

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

이러한 생성자를 구하는 방법은 간단하다. 론 관련 문서에서 적절히 설명하지 않는 관계로 여기에서 설명한다. P1소인수분해한다고 하자. 예제의 P=97에서 P1=96을 소인수분해해 보자. 그렇다면 P1=pe11××peii과 같은 형태를 띄게 된다. 예제의 경우에는 96=25×3이다. 이제 h(i)=P1pi를 구하자. 예제의 경우에서는 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이므로 5Z97의 생성원이다.

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

그렇다면 KaKb가 같은 값이라는 것은 어떻게 증명될까? 증명은 의외로 간단하다. 다시 마법의 식을 보자(뒤에 붙은 모듈러 연산은 이해를 돕기 위해 생략한다.). AGa, BGb, KaBa, KbAb의 네 가지 식이 있다. 이 식을 Ka(Gb)a, Kb(Ga)b의 두 가지로 줄여보자. 제곱의 위치는 상관이 없으니 Ga를 제곱한 뒤 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