암호학 6주차 - Diffie-Hellman 알고리즘

0. 서론

​

두 사람이 대칭키 암호 시스템을 사용해 통신하려면 데이터를 교환하기 전에 키 교환(key exchange)이 이뤄져야 한다.

• 키 교환이 이뤄저야 하는 이유: 대칭키 암호는 수신자와 송신자가 같은 키를 공유하고 있다는 전제가 필요하다.
• 안전한 키 교환이 어려운 이유: 현대 유무선 환경에서, 예를 들어, 전화로 키를 전달하면 도감청 시 알 수 있다.

--> 공개된 채널을 통해 키를 교환해도 외부인은 키를 알 수 없게 하는 공개 키 교환 알고리즘을 고안했다.

---

1. Diffie-Hellman key exchange 의 수학적 원리

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

: 임의의 합동 항등식에 대해 양변에 동일한 값을 곱해도 식은 성립

a^k ≡b 일 때, a^k X a^k ≡ a^{2k} ≡ b^2 (mod m)

​

---> square and multiply : 큰 지수에 대한 합동식을 빠르게 연산하는 알고리즘

 

​

2. 페르마의 소정리 (Fermat's Little Theorem)

: 소수 p와 정수 a에 대해 a^(p-1)≡1(mod p) 가 성립한다.

예시) 소수 37과 2, 3, 17은 페르마의 소정리에 따라 2^36≡3^36≡1(mod 37) 을 만족한다.

​

​

3. 이산 로그 문제 (Discrete Logarithm Problem)

: 자연수 a, m, 정수 b에 대해 a^x≡b(mod n)을 만족하는 정수 x 를 구하는 문제

​

--> Diffie-Hellman 알고리즘의 안전성은 이산 로그 문제의 어려움에 바탕을 두고 있다.

공격자가 키를 구하기 위해 풀어야 한느 문제는 현재의 연산능력으로 불가능하므로

Diffie-Hellman 알고리즘을 사용한다.

​

---

1. Diffie-Hellman key exchange 의 키 교환 절차

배경: 키 교환에서 통신 진행하는 가상의 인물을 Alice 와 Bob이라고 하자.

​

 

1. 키를 교환하고자 하는 Alice는 소수 p와 1≤g≤p−1을 만족하는 적당한 수 g를 정해 Bob에게 전송한다.

p는 보통 2^{1024} 이상의 큰 소수로 설정

​

2. 다시 Alice는 1≤a≤p−1을 만족하는 적당한 수 a를 정하여 A = g^a mod p 를 Bob에게 전송한다.

Alice로 부터 g와 p를 받은 Bob은 1≤b≤p−1을 만족하는 적당한 수 b를 정해 B = g^b mod p를 Alice에게

전송한다.

​

3. Alice는 bob이 보낸 B를 a제곱하여 K≡B^a≡((g^a)^b)≡g^(ba)mod p를 계산하고, 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 = g^{ab} mod p 를 구할 수 없다.

이 알고리즘을 이용하면 Ailce와 Bob은 모두에게 공개된 통신 채널을 이용하여도 서로 안전하게 키를 교환할 수 있다.

​

 

---

2. Diffie-Hellman에 대한 중간자 공격 (Man In The Middle attack, MITM)

• 공격의 특성

: 네트워크로 통신하는 주체들은 서로의 신원을 확인하기 어렵다는 특성을 이용한 공격

​

• 네트워크에서 발생하는 공격

- 수동적 공격: 공격자가 통신에 개입하지 않는 공격

수동적 공격자는 둘 사이의 통신 도청만 할 수 있다.

- 능동적 공격: 공격자가 통신에 직접 개입하는 공격

능동적 공격자는 통신을 도청하면서 중간에 데이터를 위변조할 수 있다.

중간자 공격이 해당된다.

​

---> Diffie-Hellman은 중간자 공격에 취약하다.

 

중간자 공격의 진행)

​

1. 앨리스와 밥이 통신할 때 공격자는 앨리스에게 자신을 밥이라고 속이고 밥에게는 자신이 앨리스라고 속인다.

그렇게 되면 앨리스와 밥은 통신하는 상대방이 공격자인지 신뢰하는 사람인지 알 수 없다.

​

2. 앨리스가 밥에게 키 교환을 시도하면 공격자가 이를 가로채어 둘 모두와 키 교환을 진행한다.

앨리스와는 K1이라는 키를 공유하고 밥과는 K2라는 키를 공유한다. 둘은 각각 K1, K2를 공유했다고 믿는다.

​

3. 이후 앨리스가 밥에게 K1으로 암호화된 데이터를 전송하면 공격자가 복호화해서 K2로 암호화해서 밥에게

보낸다. 밥의 응답도 마찬가지로 진행한다.

​

--> 이 과정에서 공격자는 오가는 정보를 모두 알 수 있고 변조 또한 가능하다.

--> Diffie-Hellman 키 교환은 서로의 신원을 확인할 수 있는 추가적인 매커니즘이 동반되어야 안전하게

이뤄질 수 있다.