디피-헬만 알고리즘(Diffie-Hellman Algorithm),취약점 - 파이썬 예제

디피 헬만 알고리즘(Diffie-Hellman Algorithm)에 대해서

디피 헬만 알고리즘(Diffie-Hellman Algorithm)은 이산대수의 어려움을 이용하여 암호키를 교환하는 알고리즘 중에 하나이며 상대방의 공개키(Public Key)와 서로 다른 자신의 비밀키(Private Key)를 사용하여 계산하면 상대방과 자신이 동일한 비밀키(Private Key) 키를 갖게 되며 이 비밀키를 사용하여 데이터를 암호화한 뒤에 데이터를 전달하면 된다

 

디피 헬만 알고리즘(Diffie-Hellman Algorithm)을 사용하여 공개키(Public Key)를 교환하면 서로의 비밀키(Private Key)를 교환하지 않아도 상대와 단둘이 아는 비밀키(Private Key)를 생성할 수 있습니다

 

 

이산대수 문제의 어려움을 이용한 방식으로 위의 식에서 g와 x와 p의 값을 알고 있다면 y를 구하기 쉽지만

g와 y와 p를 알고있을때 x를 구하기는 어렵다는 원리를 이용하여 만들어진 알고리즘입니다

이 때문에 서로 간의 키 전달 중에 공격자가 도청을 하더라도 공개키의 값이 크면 비밀키를 유추하기 어렵습니다

 

디피 헬만 알고리즘 작동 과정

공개 : p(큰 소수),g(1<=g<=p-1 원시근)
비공개 : a(A의 비밀키),b(B의 비밀키)

1. 아주 큰 소수 p, 그리고 0부터  p - 1 사이의 정수 (원시근) g을 선택합니다

이때 p와 g의 값은 A와 B와 해커 모두 알고 있습니다

 

2.A의 임의의 정수 a와 B의 임의의 정수 b를 선택합니다

이때 a와 b는 각각의 비밀키가 됩니다

A는 a, p, g의 값만 알고있으며, B는 b, p, g의 값만 알고 있으며, 해커는 p, g의 값만 알고 있습니다

 

각각 Akey와 Bkey를  Akey=g^a mod p , Bkey = g^b mod p를 계산하여 구해줍니다

이때 Akey와 Bkey는 원시근(g)의 비밀키(a, b) 제곱과 p를 나눈 나머지 값

즉, Akey = g^a mod p와 B = g^b mod p가 된다

 

Akey=g^a mod p일 때, g와 a와 p의 값을 알고 있다면 Akey를 구하기 쉽지만 g와 Akey와 p만 알고 있을 땐 a를 구하기 어렵습니다

 

그래서 Akey와 Bkey를 구한 후 누군가 도청하여 Akey, Bkey, g, p를 알더라도 역계산으로 각자의 비밀키인 a와 b의 값을 유추하기는 매우 어렵습니다

 

4. 앞서 3에서 구한 Akey와 Bkey를 전달해줍니다 A는 B에게 Akey를 전달하고 B는 A에게 Bkey를 전달합니다

서로 교환된 값을 이용하여 KA와 KB를 계산해줍니다

 

5.A는 B에게 전달받은 Bkey와 자신의 비밀키 a와 공개키 p를 사용하여 KA를 계산하며

반대로 B는 A에게 전달받은 Akey와 자신의 비밀키 b와 공개키 p 사용하여 KB를 계산합니다

KA = Bkey^a mod p #A
KB = Akey^a mod p #B

결국 KA와 KB의 값은 동일하며 이를 서로 간의 데이터를 주고받는 암호키로 사용합니다

 

 

디피 헬만 키 교환 알고리즘 파이썬 예제

위 과정을 코드로 보면 다음과 같습니다.

공개키와 비밀키를 임의로 생성하여 위 작동과정대로 수행하였습니다.

#공개키
p=2465623456 
g=1236556
 
#비밀키 
a=4562  #A
b=153  #B
 
print(f"공개키 : p: {p}, g: {g}") 
print(f"A의 비밀키 :{a}") 
print(f"B의 비밀키 :{b}\n") 
 
#공개키 생성 (원시근,비밀키,큰소수 p)
#Akey=(g**a) % p   , Bkey=(g**b) % p
Akey=pow(g,a,p) 
Bkey=pow(g,b,p)
print("A는 비밀키를 사용하여 Akey=p**a % g의 계산결과를 B에게 전달") #A>b
print("B는 비밀키를 사용하여 Bkey=p**b % g의 계산결과를 A에게 전달\n") #B>A
 
 
print(f"A는 B로부터 계산된 Bkey: {Bkey}를 전달받음") #A
print(f"B는 A로부터 계산된 Akey: {Akey}를 전달받음\n") #B
 
#공개용 비밀키 생성
KA=pow(Bkey,a,p)#B에게 받은 Bkey와 자신의 비밀키 a와 공개키 P를 사용하여 계산한다
print(f"B에게 받은 Bkey와 자신의 비밀키,공개키를 사용하여 계산한결과: {KA}")  #A
 
KB=pow(Akey,b,p)#A에게 받은 Akey와 자신의 비밀키 b와 공개키 p를 사용하여 계산한다
print(f"A에게 받은 Akey와 자신의 비밀키,공개키를 사용하여 계산한결과: {KB}\n") #B
 
 
print(f"KA : {KA}\nKB : {KB}")
print("KA와 KB의 결과는 일치하며 이값을 데이터를 주고받는 암호키로 사용한다") 

디피헬만 알고리즘 코드

위에 예제에서 사용된 공개키와 비밀키를 직접 대입하여 코드를 다시한번 설명해드리면 이런 결과가 나옵니다.

#공개키
p = 2465623456
g = 1236556

#비밀키
a = 4562  # A의 비밀키
b = 153   # B의 비밀키

#공개키 : p: 2465623456, g: 1236556
#A의 비밀키 : 4562
#B의 비밀키 : 153

# A가 계산할 키 (공개키로 전달)
Akey = pow(g, a, p) = pow(1236556, 4562, 2465623456)
#계산결과 Akey = 2051955328 

# B가 계산할 키 (공개키로 전달)
Bkey = pow(g, b, p) = pow(1236556, 153, 2465623456)
#계산결과 Bkey = 1564384640

#과정 1. 서로에게 공개 키를 전달
#- A는 자신의 열쇠 Akey를 B에게 전달한다.
#- B는 자신의 열쇠 Bkey를 A에게 전달한다.

#A는 B로부터 계산된 Bkey를 전달받는다.
#B는 A로부터 계산된 Akey를 전달받는다.

# 공유 암호를 생성하기 위해 서로 받은 키와 자신의 비밀키를 사용

# A가 생성하는 공유암호 (KA)
KA = pow(Bkey, a, p) = pow(Bkey, 4562, 2465623456)
#계산결과 Ka =1583373664

# B가 생성하는 공유암호 (KB)
KB = pow(Akey, b, p) = pow(Akey, 153, 2465623456)
#계산결과 Ka =1583373664

#결과:
#KA, KB의 값은 같으므로, 이 값을 암호 데이터 교환에 사용하는 공유 암호키로 사용한다.

 

취약점

해커가 비밀키인 a와 b를 찾으면 알고리즘은 쉽게 해독할 수 있게 됩니다 이산 로그 문제를 푼다면 a와 b의 값을 찾을 수 있지만 이산대수의 어려움으로 사실상 매우 힘듭니다

하지만 다른 취약점으로는 해당 알고리즘은 중간자 공격에 매우 취약합니다

 

예를 들어서 A와 B는 A=g**a % p와 B=g**b % p의 연산을 수행한 뒤 해커는 H=g**h % p 연산으로 공개키를 생성한 뒤

해커(H)가 A와 B의 사이에서 생성한 공개키 A, B를 가로채어 A, B에게 해커의 공개키인 H를 전달하고 A와 B를 이를 눈치채지 못한다고 가정합니다

 

A는 해커에게 받은 공개키(H)를 사용하여 공개용 비밀키(Akey)를 생성하고, 해커는 가로챈 A의 공개키를 사용하여 공개용 비밀키(AHkey)를 생성합니다

이로써 A와 해커는 동일한 키를 가지며 해커가 내용을 조작하거나 중간에 데이터를 엿볼 수 있습니다

 

B도 마찬가지로 해커에게 받은 공개키 (H)를 사용하여 공개용 비밀키(Bkey)를 생성하고, 해커는 가로챈 B의 공개키를 사용하여 공개용 비밀키(BHkey)를 생성합니다

B와 해커는 동일한 키를 가지며 해커가 A와 B사이의 내용을 조작하여 전송하거나 중간에 데이터를 엿볼 수 있습니다

취약점 예제 코드

 
#공개키
p = 564646416516
g = 2
 
 
#비밀키
a = 6456
b = 1561
h = 546
 
 
print(f"공개키 p : {p}, g:{g}")
print(f"A의 비밀키: {a}\nB의 비밀키: {b}\n해커의 비밀키: {h}")
 
#각자 A,B,H의 공개키 생성
print()
print('A와 B는 비밀키를 사용하여 y=g^a mod p 계산하고 h도 비밀키를 사용하여 공개키를 계산하였다')
A = pow(g, a, p)
B = pow(g, b, p)
H = pow(g, h, p)
print("이때 해커가 메세지를 가로채어 A와 B의 키는 자신이 받고 해커의 공개키H를 A와 B에게 전송한다")
 
 
#공개용 비밀키 생성 (전달받은 공개 키,자신의 비밀키, mod p)
#A와 해커
print()
print("A는 이 사실을 모르고 해커에게 받은 공개키(H)로 공개용 비밀키를 생성한다")
Akey = pow(H, a, p)#A
print("해커는 A의 가로챈 공개키를 사용하여 공개용 비밀키를 생성한다 ")
AHkey = pow(A, h, p) #H
 
 
print()
#B와 해커
print("B는 이 사실을 모르고 해커에게 받은 공개키(h)로 공개용 비밀키를 생성한다")
Bkey = pow(H, b, p)#B
print("해커는 B의 가로챈 공개키를 사용하여 비밀키를 생성한다 ")
BHkey = pow(B, h, p)#H
 
 
print()
print(f"Akey: {Akey}\nAHkey :{AHkey}")
print("Akey와 AHkey의 결과값이 일치하며 해커는 A의 내용을 옅볼수있다")
 
print()
print(f"Bkey: {Bkey}\nAHkey :{BHkey}")
print("Bkey와 BHkey의 결과값이 일치하며 해커는 B의 내용을 옅볼수있다")
 

 

GITHUB

파이썬 디피 헬만 예제

GitHub - Blue-B/Diffie-Hellman-Algorithm

 

파이썬 디피 헬만 취약점 예제

GitHub - Blue-B/Diffie-Hellman-Algorithm

 

 

 

 

참고자료

디피헬만 (Diffie-Hellman) 공식 초간단 (ㅎㅎ)

디피헬만 공개키 암호화 알고리즘

GitHub - ht3886/Diffie-Hellman_Python: Python code for Diffie-Hellman key exchange

Diffie-Hellman 키 교환

디피-헬만(Diffie-Hellman) 키 교환 > 도리의 디지털라이프

디피 헬만 알고리즘(Diffie-Hellman Algorithm)

디피-헬만 키 교환 알고리즘(Diffie-Hellman key exchange)

Diffie-Hellman Man-in-the-middle attack