[암호학] 9. 엘 가말 암호

[암호학] 9. 엘 가말 암호

홀수 소수 $p$에 의해 $\mathbb{Z}_{p}=\{0,\,1,\,...,\,p-1\}$은 체이므로 $\mathbb{Z}_{p}^{*}=\mathbb{Z}_{p}-\{0\}$는 곱셈에 대한 군이고 $a\in\mathbb{Z}_{p}^{*}$를 법 $p$에 대한 원시근이라고 하면 다음이 성립한다. $$\begin{align*}&Z_{p}^{*}=\{a^{0},\,a^{1},\,...,\,a^{p-1}\},\,a^{p-1}=1\\&a^{p-2}\cdot a=a^{p-1}=1,\,a^{-1}=a^{p-2}\end{align*}$$ 임의의 양의 정수 $r$에 대하여 $a^{-r}=(a^{-1})^{r}$라 하면 모든 정수 $s$에 대하여 $(a^{s})^{-r}=a^{-sr}=(a^{-1})^{sr}$이며 이것은 다음의 합동식이 성립함을 뜻한다. $$a\cdot a^{-1}\equiv1\,(\text{mod}\,p),\,(a^{s})^{-r}\equiv a^{-sr}\equiv(a^{-1})^{sr}\,(\text{mod}\,p)$$ 정리. 홀수 소수 $p$에 대하여 곱셈군 $\mathbb{Z}_{p}^{*}=\{1,\,2,\,...,\,p-1\}$에서 $a\in\mathbb{Z}_{p}^{*}$를 법 $p$에 대한 원시근이라 하고, 양의 정수 $r$에 대하여 $d=a^{r}$이라 할 때, 양의 정수 $k$에 대하여 두 함수 $E$, $D$를 다음과 같이 정의하자. $$\begin{align*}&E:\mathbb{Z}_{p}^{*}\,\rightarrow\,\{a^{k}\}\times\mathbb{Z}_{p}^{*}\,E(x)=(a^{k},\,xd^{k})\\&D:\{a^{k}\}\times\mathbb{Z}_{p}^{*}\,\rightarrow\,\mathbb{Z}_{p}^{*},\,D(a^{k},\,x)=(a^{k})^{-r}x\end{align*}$$ $E,\,D$는 일대일 대응이고 $E^{-1}=D$이다. 

증명: 임의의 $g\in\mathbb{Z}_{p}^{*}$에 대하여 다음이 성립한다. $$\begin{align*}D(E(g))&=D(a^{k},\,gd^{k})\\&=(a^{k})^{-r}gd^{k}\\&=a^{-rk}a^{rk}g\\&=g\end{align*}$$ 따라서 두 함수 $E,\,D$는 일대일 대응이고 $E^{-1}=D$이다. 

엘 가말(ElGamal) 암호체계는 1985년에 엘 가말이 개발한 것으로 앞의 정리에 기반을 두고 있다. 

엘 가말 암호체계 프로토콜 

1단계: 수신자 A는 충분히 큰 소수 $p$와 법 $p$에 대한 원시근 $a\,(2\leq a\leq p-2)$를 고르고, $1\leq r\leq p-2$인 정수 $r$을 선택해 $$d\equiv a^{r}\,(\text{mod}\,p)\,1\leq d\leq p-1$$ 인 $d$의 값을 구하고 $p,\,a,\,d$는 공개하고 $r$은 공개하지 않는다. 

즉, 사용자 A의 공개 키는 $p,\,a,\,d$이고, $r$은 비공개 키이다. 

2단계: 송신자 U는 평문을 $0\leq g\leq p-1$인 정수 $g$로 나타낸다. 

3단계: 송신자 U는 $1\leq k\leq p-1$인 정수 $k$를 임의로 고르고 $$h\equiv gd^{k}\,(\text{mod}\,p),\,0\leq h\leq p-1$$ 인 정수 $h$를 구해 암호문 $(a^{k},\,h)$를 A에게 송신한다.

4단계: 수신자 A는 암호문 $(a^{k},\,h)$와 비밀 키 $r$을 이용해 $$(a^{k})^{-r}h\equiv(a^{k})^{-r}gd^{k}\equiv(a^{k})^{-r}ga^{rk}\equiv g\,(\text{mod}\,p)$$ 이고 $0\leq g\leq p-1$인 정수 $g$를 구한다.

2단계에서 $s$를 임의로 선택하는 이유는 암호문이 노출되는 경우 통계적 분석에 의한 공격의 가능성을 줄이려 하기 때문이다. 평문 $g$에 대한 암호문 $(a^{k},\,h)$의 길이는 $a$의 길이의 2배 정도이다. 

홀수 소수 $p=37$에 대하여 $a=2$는 법 $p$에 대한 원시근이고 $2$를 밑으로 갖는 법 37에 대한 이산로그표는 다음과 같다.

$r=31$이라 하면 $$d=a^{r}\equiv2^{31}\equiv22\,(\text{mod}\,37)$$ 이고 $k=7$이라 하면 평문 $g=19$에 대하여 다음이 성립한다. $$\begin{align*}&a^{k}\equiv2^{7}\equiv17\,(\text{mod}\,37)\\&h\equiv gd^{k}\equiv19\cdot22^{7}\equiv19\cdot2\equiv1\,(\text{mod}\,37)\\&(a^{k})^{-r}\equiv17^{-31}\equiv17^{5}\,(\text{mod}\,37)\\&(a^{k})^{-r}h\equiv17^{5}\cdot1\equiv19\equiv g\,(\text{mod}\,37)\end{align*}$$ 앞에서 보았듯이 엘 가말 암호체계는 이산로그 문제에 근거를 두고 있다. $$d\equiv a^{r}\,(\text{mod}\,p)\,1\leq d\leq p-1$$ 이므로 공개된 $d$를 이용하여 비밀 키 $r\,(1\leq r\leq p-2)$를 구하는 것은 상당히 어렵다. 

엘 가말 암호체계에서 임의의 정수 $k$를 선택할 때 여러 개의 평문에 동일한 $k$를 사용하면 특정한 한 평문의 내용을 알 때 다른 평문의 내용을 모두 알아낼 수 있기 때문에 서로 다른 평문에 대하여 동일한 $k$를 사용하는 것을 피해야 한다. 

참고자료:

암호학과 부호이론, 박승안, 경문사