Diffie-Hellman Key Exchange(디피헬만 키교환) [Crypto]

1976년, Diffie와 Hellman이 제안한 키교환 방식이며 최초의 공개키 알고리즘입니다. 디피헬만 키교환은 통신망이 안전하지 않다고 가정하고 제안된 방식입니다. 디피헬만 방식은 이산대수 문제가 어렵다는 점을 이용하여 지수승 연산과 로그 연산을 이용한 알고리즘입니다. 대칭키 암호화의 문제점 중 하나인 키교환에 대한 문제를 해결하기 위해 사용할 수 있습니다.

이산대수

- 통신망에서 g, p, y를 알게되어도 x를 계산하는 것은 매우 어려운 문제입니다. (단, p는 매우 큰 소수, g는 원시원소)

---

˙ 키 교환 순서

Diffie-Hellman Key Exchange

* r은 난수입니다. (a = ra, b = rb)

- A와 B가 둘만 아는 서로 같은 키를 생성하려고 합니다.

1. 매우 큰 소수 p와 (mod p) 상의 원시원소 g를 선택합니다. 해당 값들은 모두 공유하게 되는 값입니다.

2. A는 0보다 크고, p보다 작은 a를 선택합니다. (0 < a ≤ p - 1) 해당 a는 A의 비밀값입니다.

3. A는 g^a (mod p)를 계산하여 B에게 전달합니다. (A 이외에는 a를 알 수 없습니다.)

4. B는 0보다 크고, p보다 작은 b를 선택합니다. (0 < b ≤ p - 1) b는 B의 비밀값입니다.

5. B는 g^b (mod p)를 계산하여 A에게 전달합니다. (B 이외에는 b를 알 수 없습니다.)

6. A는 전달받은 g^b (mod p)를 이용하여 (g^b)^a (mod p)를 계산합니다.

7. B는 전달받은 g^a (mod p)를 이용하여 (g^a)^b (mod p)를 계산합니다.

8. g^ab가 오늘 사용할 비밀키가 됩니다.

- 공격자는 통신하는 동안 모든 숫자를 다 안다고 가정합니다.

- p, g, a, b 를 다 알고 있고 공격자는 g^a+b가 아닌 g^ab의 형태를 알아야 합니다.

- p가 엄청 큰 숫자이면 지수승을 전부다 해야하기 때문에 시간이 매우 오래걸려서 공격하기가 힘들어집니다.