7. Diffie-Hellman 알고리즘

 

저번 시간에는 운영모드에 대하여 공부하였다.

이번 시간은 공개 키 교환 알고리즘인 Diffie-Hellman 알고리즘에 대하여 공부할 것이다.

밑에 링크는 공개 키 교환 알고리즘을 공부하기 위해 합동식에 대한 참고 자료 링크이다.

1. 암호학 개념

 

---

1. Diffie-Hellman 알고리즘 배경

 대칭키 암호는 안전하게 암호화할 수 있는 암호 기술이지만, 수신자와 송신자가 같은 키를 공유해야 한다. 그러므로 수신자와 송신자가 대칭키 암호 시스템을 사용하여 통신하려면 데이터를 교환하기 전에 키 교환이 이뤄져야 한다. 대칭키 암호의 안전성은 키에서 비롯되므로, 키를 안전하게 공유할 수 없는 환경에서 대칭키 암호는 무용지물이다. 그래서 네트워크 같은 공개된 채널을 통해 키를 교환해도 외부인은 키를 알 수 없게 하는 최초의 공개 키 교환 알고리즘인 Diffie-Hellman 알고리즘을 개발하였다.

 

2. Diffie-Hellman 알고리즘 수학적 원리

1) 모듈로 연산에서의 거듭제곱

합동식은 양변에 동일한 값을 곱해도 식은 성립한다. 

a ≡ b 일 때,  an ≡ bn(mod m)이 성립한다.

이를 이용하여 큰 지수에 대한 합동식을 빠르게 연산하는 알고리즘을 square and multiply라고 부른다. Diffie-Hellman 키 교환 알고리즘을 사용하려면 2²⁰⁴⁸번 가까이 제곱된 수의 모듈러 값을 구해야 하는데, 이 방법을 사용하면 2048번 정도만 연산하면 구할 수 있다.

2) 이산 로그 문제

이산 로그 문제는 "자연수 a, m, 정수 b에 대해 a^x ≡ b (mod m)을 만족하는 정수 x를 구하는 문제"이다. a, b, m이 간단하면 무차별 대입으로 쉽게 찾을 수 있다. 하지만 b와 m이 매우 커지면, 식이 성립하는 무차별 대입으로 찾기가 어렵다. 이산 로그 문제를 푸는 방법이 여럿 연구되었지만, 현재까지 알려진 최선의 방법으로도 이 문제를 푸려면  √m번 정도 연산을 해야 한다. 

Diffie-Hellman  알고리즘의 안정성은 이산 로그 문제의 어려움에서 나온다. 키를 모르는 공격자가 키를 구하려면 m이 2²⁰⁴⁸정도 되는 이산 로그 문제를 풀어야 한다. 현재로써 불가능하다.

 

3. 키 교환 절차

1. 키를 교환하고자 하는 Alice는 소수 p와 1 ≤ g ≤ p-1을 만족하는 적당한 수 g를 정해 Bob에게 전송한다.(p는 2¹⁰²⁴ 이상의 큰 소수)
2. Alice는 1 ≤ a ≤ p-1을 만족하는 적당한 수 a를 정하여 A = g^a mod p를 Bob에게 전송한다.
3. Alice로부터 g와 p를 받은 Bob은 1 ≤ b ≤ p-1을 만족하는 적당한 수 b를 정해 B = g^b mod p를 Alice에게 전송한다.
4. Alice는 Bob이 보낸 B를 a 제곱하여 K ≡ B^a ≡ (g^b)^a ≡ g^ba mod p를 계산한다.
5. Bob은 Alice가 보낸 A를 b 제곱하여 K ≡ A^b ≡ (g^a)^b ≡ g^ab mod p를 계산한다.

 a와 b의 값이 크지만, square and multiply를 이용하면 쉽게 K를 구할 수 있다. Alice와 Bob은 계산한 K를 통신의 키로 사용하게 된다. 

공격자는 둘 사이의 통신을 도청하여 p, g, g^a mod p, g^b mod p를 알아낼 수 있다. 그러나 이산 로그 문제의 어려움으로 인해 g^a mod p로부터 a를 알아내거나 g^b mod p로부터 b를 알아내는 것은 불가능하며, 결과적으로 K를 구할 수 없다.

 

키 교환 방법

 

---

 

이번 시간은 공개키 교환 알고리즘에 대하여 공부하였다.

다음 시간은 RSA에 대하여 공부할 것이다.