나무모에 미러 (일반/밝은 화면)
최근 수정 시각 : 2024-06-11 13:02:22

디피-헬만 키 교환


1. 개요2. 방식
2.1. 예제
3. 수학적 원리4. 구현 예제5. 공격 예제
5.1. 실행 결과
6. 관련 문서

1. 개요

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

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

단점도 있는데, 공개키가 믿을 수 있는 공개키인지 확인함으로써 상대방의 신원을 검증할 수 있는 RSA 방식과는 달리 디피-헬만 키 교환 방식은 그 자체만으로는 상대의 신원을 검증할 수 없고, 따라서 중간자 공격으로부터 보호할 방법이 없다. 이런 이유로 이 방식은 전자서명이 가능한 다른 암호화 방식과 섞여 사용되고 있다.

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)] 둘 중 하나도 알지 못하는 이브는 현실적으로 키 값을 알 수 없다.

2.1. 예제


앨리스와 밥은 통신에 앞서 [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)]를 계산한다.

3. 수학적 원리

개요에 짧게 기술했듯, 본 알고리즘은 이산대수의 난해함이 안전성의 기반이 된다. 앞선 예제에서 나온 마법의 식 [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)])[1]를 뽑아 [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)]를 제곱하건 값에는 상관이 없다.

4. 구현 예제

아래는 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()

5. 공격 예제

본 예제에서는 성실하고 근면하게(...) 브루트 포스로 뚫어보자. 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)

5.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

6. 관련 문서


[1] 정확하게는 1과 96을 제외한다. 생성자는 3 이상의 소수 [math(p)]가 주어졌을 때, 법 [math(p)]에 대하여 [math(\pm 1)]이 아닌 원소중에서 뽑아야 하기 때문.