📂정수론

엘가말 공개 키 암호체계 증명

빌드업

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

앨리스는 밥에게 받아야할 메세지 $m \in \mathbb{N}$ 이 있다.

알고리즘 ¹

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

---

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

앨리스는 혼자만 알고 있는 키 $1 \le a \le p-1$ 를 정하고 $A \equiv g^{a} \pmod{p}$ 를 계산해서 공개한다.

---

암호화 : 일회용 랜덤 키 $k$ 를 생성한다.밥은 $c_{1} \equiv g^{k} \pmod{p}$ 와 $c_{2} \equiv m A^{k} \pmod{p}$ 를 계산해서 $(c_{1} , c_{2})$ 를 앨리스에게 전송한다.

---

복호화 : 앨리스가 $(c_{1} , c_{2})$ 를 이용해 $x \equiv (c_{1}^{a} )^{-1} c_{2} \equiv m \pmod{p}$ 를 계산하면 $x = m$ 를 얻는다. 이브는 현실적으로 $a$ 를 알 수 없기 때문에 $m$ 을 알 수 없다.

설명

사실 체계 자체에서 $g$ 의 오더 $\text{ord}_{p} (g)$ 가 커야할 이유는 없으나, 그냥 무식하게 계산하다가 얻어걸릴 가능성을 내리기 위해서는 오더가 큰 수를 고르는 게 좋다.

증명

복호화

앨리스는 $a$ 를 알고 있고 $c_{1} \equiv g^{k} \pmod{p}$ 이고 $c_{2} \equiv m A^{k} \pmod{p}$ 이므로 $k$ 를 몰라도 $$ \begin{align*} (c_{1}^{a} )^{-1} c_{2} & \equiv \left( g^{ak} \right)^{-1} \cdot c_{2} \\ & \equiv \left( g^{ak} \right)^{-1} \cdot \left( m A^{k} \right) \\ & \equiv \left( g^{ak} \right)^{-1} \cdot \left( m \left( g^{a} \right)^{k} \right) \\ & \equiv m \left( g^{ak} \right)^{-1} \cdot g^{ak} \\ & \equiv m \pmod{p} \end{align*} $$ 을 쉽게 계산할 수 있다.

■

암호화

이브는 $c_{1}$ 과 $c_{2}$ 만 알고 있을 뿐 $a$ 와 $k$ 를 모르기 때문에 이산로그문제 ${g}^{x} \equiv c_{1}^{a} \pmod{p}$ 을 알 수 없고, 알더라도 직접 풀어내야한다. 이는 아주 어려우므로, 밥은 앨리스에게 메세지 $m$ 을 안전하게 전달할 수 있다.

■

같이보기

• 이산로그 문제

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

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

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

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