[암호학] 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\)를 사용하는 것을 피해야 한다. 

참고자료:

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