디피-헬만 키 교환

1. 개요

2. 방식

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

2.1. 예제

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

3. 수학적 원리

4. 구현 예제

#!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. 공격 예제

#!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. 일반화

7. 관련 문서

• 암호 알고리즘