[보안] 디피-헬먼 키 교환 1편

 

Introduction

우리가 통신을 할 때 패킷은 누가 보지않게 암호화 시켜야한다. 이러한 암호화 방식을 위해 key라는 것이 존재하고 이러한 key를 이용해서 암복호화등을 진행하게 된다.

 여기서 내가 예전부터 궁금해했던 부분은

키는 어떻게 암호화해서 교환하는 걸까?

라는 질문이다.

 이러한 키교환에 사용되는 유명한 키 교환 알고리즘인 디피-헬먼의 키 교환에 대해서 오늘 글을 써보려고 한다.

 

Background

디피-헬먼 알고리즘을 이해하기 위해서는 수학적인 배경지식이 필요하다.

> Euler's totient function 

Φ(n) : n보다 작은 수 중에 n과 서로소인 숫자의 갯수

p가 만약 소수라고 한다면 Φ(p) = p - 1이다.

 

> Euler's Theorem

n이 소수이고 a와 n가 서로소 인 경우 다음 식을 만족한다.

$$. a^{pi(n)} =  1(mod n). $$

 

> Primitive Root

a의 제곱수가 mod n상의 모든 나머지를 가지고 있다면 a는 n의 primitive root라고 한다.

 

> Discrete Logarithm

소수인 p 에 대해서 다음 식을 만족하는 i를 찾는 문제를 Discrete Logarithm problem이라고 한다.

$$ b ≡  a^i (mod p) $$

이 문제의 특성을 이해하는 것이 매우 중요한데 우리가 a, i, p를 알고 있으면 b를 구하는 것은 매우 쉽다.

하지만 우리가 p, a 그리고 b만 알면 i를 구하는 것은 p가 매우 크다면 알기 어려운 문제이다.

예를 들어

case (1) p = 9 , a= 2, i = 6일 때 b를 구하는 코드는 다음과 같을 것이다.

p = 9
a = 2
i = 6

b = (a ** i) % 9

case (2) p = 9, a = 2, b = 7

p = 9
a = 2
b = 1

for i in range(1, 9) :
	if (a ** i) % p == b :
    	print("Answer :", i)
    else :
    	continue

만약 p가 정말 큰 수라면 i를 찾아내는데 걸리는 시간은 O(n) 일것이다.

 

Diffle and Hellman

디프 헬먼 키 교환 알고리즘은 위에서 말한 Discrete Logarithm을 바탕으로 만들어졌다.

$$ Y = a^{X} mod p $$

1) A씨와 B씨가 서로 a, p를 공유한다.

여기서 p는 매우 큰 소수이며

a는 mod p의 primitive root이다.

 

2) A씨와 B씨는 서로 p보다 작은 난수를 생성한다. 이를 X라고 하고 이는 A씨와 B씨의 private key이다.

 

3) A씨와 B씨는 다음 공식을 이용해 public key를 생성한다.

$$ Y_A = a^{X_A} mod p $$

$$ Y_B = a^{X_B} mod p $$

 

4) 이렇게 생성한 public key $$ Y_A, Y_B $$ 를 A씨와 B씨가 서로 나누어 가진다.

누군가 이때 public key를 탈취한다고 해도 private key를 찾아내기란 computational cost가 크다.

 

5) A와 B는 다음과 같은 수식을 이용해 Session key를 생성할 수 있다.

$$ K_{AB} = (Y_B)^{X_A} mod p = (Y_A)^{X_B} mod p $$

 

이렇게 만들어진 session key 교환을 Diffle-Hellman 알고리즘을 통해 할 수 있는 것이다.

 

다음 글에서는 해당 방식이 어떠한 점에 취약한지, 이를 위한 해결책이 무엇인지 정리하겠다.

 

---

출처

 

성균관대학교 최형기 교수님 정보보호개론 강의(SWE3025)

---

긴 글 읽어주셔서 감사합니다.

 

틀린 부분이 있으면 댓글을 달아주시면 감사하겠습니다.

 

📧 : may3210@g.skku.edu

🔗 : https://github.com/RicardoKim