디피-헬만 키 교환

역사 raw
대문 랜덤 문서 최근 토론
분류
1. 개요2. 방식3. 예제4. 수학적 원리5. 구현 예제6. 공격 예제
6.1. 실행 결과
7. 관련 문서

1. 개요[편집]

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

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

2. 방식[편집]

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

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

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

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

앨리스는 이미 공개된 PP와 BB, 그리고 자신만 알고 있는 aa로부터 Ka≡Ba(mod P)K_a \equiv B^a (mod\ P)를 만족하는 KaK_a를 계산한다.

밥은 이미 공개된 PP와 AA, 그리고 자신만 알고 있는 bb로부터 Kb≡Ab(mod P)K_b \equiv A^b (mod\ P)를 만족하는 KbK_b를 계산한다.

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

3. 예제[편집]

  • 앨리스: 통신자 1
  • 밥: 통신자 2
  • 이브: 스니퍼(=해커)

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

앨리스는 PP 미만의 임의의 정수 a=47a = 47을 선택하고 547(mod 97)≡A=585^{47} (mod\ 97) \equiv A = 58를 밥에게 전송한다.

밥은 PP 미만의 임의의 정수 b=51b = 51을 선택하고, 551(mod 97)≡B=695^{51} (mod\ 97) \equiv B = 69를 앨리스에게 전송한다.

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

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

4. 수학적 원리[편집]

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

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

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

이제 Z97∗Z97*의 원소 {1, 2, ⋯ , 95, 96}\{1,\ 2,\ \cdots,\ 95,\ 96\} 중 임의로 하나(여기서는 yy)를 뽑아 yh(i)(mod P)≡1y^{h(i)} (mod\ P) \equiv 1이 성립하지 않는지 확인한다. 가령 저 원소 중 랜덤으로 1111을 뽑았다고 치자. 이 경우 1148(mod 97)≡111^{48} (mod\ 97) \equiv 1이므로 1111은 이 군의 생성원이 아니지만, 55의 경우에는 548(mod 97)≡965^{48} (mod\ 97) \equiv 96, 532(mod 97)≡535^{32} (mod\ 97) \equiv 53이므로 55는 Z97∗Z97*의 생성원이다.

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

그렇다면 KaK_a와 KbK_b가 같은 값이라는 것은 어떻게 증명될까? 증명은 의외로 간단하다. 다시 마법의 식을 보자(뒤에 붙은 모듈러 연산은 이해를 돕기 위해 생략한다.). A≡GaA \equiv G^a, B≡GbB \equiv G^b, Ka≡BaK_a \equiv B^a, Kb≡AbK_b \equiv A^b의 네 가지 식이 있다. 이 식을 Ka≡(Gb)aK_a \equiv (G^b)^a, Kb≡(Ga)bK_b \equiv (G^a)^b의 두 가지로 줄여보자. 제곱의 위치는 상관이 없으니 GG에 aa를 제곱한 뒤 bb를 제곱하건 bb를 제곱한 뒤 aa를 제곱하건 값에는 상관이 없다.

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

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

7. 관련 문서[편집]