📂정수론

디피-헬만 키 교환 알고리즘 증명

빌드업

왼쪽부터 순서대로 앨리스 , 밥 , 이브라 하자. 앨리스와 밥은 메세지를 주고받을 당사자고, 이브는 메세지에 관심이 있는 소극적 공격자다. 주황색 상자는 앨리스만 알고 있는 정보를, 하늘색 상자는 밥만 알고 있는 정보를, 검은색 상자는 공개된(이브도 알고 있는) 정보를 나타낸다.

앨리스와 밥이 암호체계 $( \mathcal{K} , \mathcal{M} , \mathcal{C} , e_{k} , d_{k} )$ 하에서 메세지를 주고받으려고 한다. 안타깝게도 이브는 암호체계의 복호화 함수 $d_{k}$ 를 알고 있으며, 키 $k$ 를 이브에게 들키지 않고서는 직접 전달할 수 없는 상황이다. 단, 이런 상황에서도 앨리스와 밥 두 사람만이 공유하는 키 $K$ 를 각자 생성할 수 있다면 이브는 $d_{k}$ 를 알고 있음에도 키 $K$ 를 몰라서 비문을 해독할 수 없을 것이다. 이러한 해법이 바로 디피-헬만 키 교환 알고리즘^{diffie Hellman Key Exchange Algorithm}이다.

알고리즘 ¹

$\mathbb{F}_{p}^{ \ast } = \mathbb{F}_{p} \setminus \left\{ 0 \right\} = \left\{ 1, g , g^2 , \cdots , g^{p-2} \right\}$ 는 원소의 수가 $(p-1)$ 개인 시클릭 그룹이라고 하자.

---

Step 1.

아주 큰 소수 $p$ 와 $\text{ord}_{p} (g)$ 가 큰 소수인 $g \in \mathbb{F}_{p}^{ \ast }$ 를 선택해서 공개한다.

---

Step 2.

앨리스는 임의의 정수 $a$ 를 선택하고, 밥은 임의의 정수 $b$ 를 선택한다.

---

Step 3. 암호화

$A \equiv g^{a} \pmod{p}$ 와 $B \equiv g^{b} \pmod{p}$ 를 계산해서 공개한다.

---

Step 4. 복호화

$K \equiv B^{a} \equiv A^{b} \pmod{p}$ 를 계산해서 $K$ 를 키로 암호화한 비문 $c = e_{K} (m)$ 을 사용하면 이브는 현실적으로 $K$ 를 알 수 없기 때문에 $m = d_{K} (c)$ 를 알 수 없다.

설명

Step 1. 에서 $\text{ord}_{p} (g)$ 는 위수로써, 가능한 한 큰 소수여야 $g_{n}$ 이 $n$ 의 값에 따라 예측하기 어렵게 변한다. 만약 $\text{ord}_{p} (g) = 3$ 정도밖에 안된다면 $K$ 를 계산하는 게 너무 쉽다. 만약 $\text{ord}_{p} (g) = nm$ 이 합성수라면 $g^{nm} \equiv 1 \pmod{p}$ 라고 할 때 $( g^{n} ) ^{m} \equiv 1 \pmod{p}$ 이므로 사실상 위수가 작은 $G:=g^{n}$ 을 사용하는 것이나 마찬가지다.

주의해야 할 사항은 디피-헬만 키 교환 알고리즘 자체가 어떤 암호체계가 되는 것이 아니라, 그냥 소극적 공격자가 있는 상태에서 비밀 키 $K$ 를 만들어내는 방법이라는 점이다. 이렇게 얻게 되는 $K$ 자체는 메세지와 관계가 없으며, 암호체계도 전혀 달라지지 않는다.

증명

복호화

$a$ 와 $b$ 를 알고 있는 앨리스와 밥은 $$ \begin{align*} K & \equiv A^{b} \\ & \equiv \left(g^{a} \right)^{b} \\ & \equiv g^{ab} \\ & \equiv \left(g^{b} \right)^{a} \\ & \equiv B^{a} \pmod{p} \end{align*} $$ 을 쉽게 계산할 수 있다. 따라서 공개된 $g$ 만 있으면 $a$, $b$ 둘 중 하나만 알아도 $K$ 를 구할 수 있다.

■

암호화

이브는 $A$ 와 $B$ 만 알고 있을 뿐 $a$ 와 $b$ 를 모르기 때문에 이산로그문제 $A^{x} \equiv K \pmod{p}$ 혹은 $B^{x} \equiv K \pmod{p}$ 을 풀어야한다. 이는 아주 어려우므로, 앨리스와 밥은 $K$ 를 키로 써서 이브에게서 안전하게 통신이 가능하다.

■

같이보기

• 이산로그 문제

이산로그 문제의 어려움을 이용한 보안 알고리즘

• 디피-헬만 키 교환 알고리즘
• 엘가말 공개 키 암호체계

이산로그 문제에 대한 공격 알고리즘

• 샹크스 알고리즘
• 폴리그-헬맨 알고리즘
• 이산로그 문제가 쉽게 풀리는 조건