[암호학] 13. 갈루아 체를 이용한 암호체계

[암호학] 13. 갈루아 체를 이용한 암호체계 

체 \(GF(2)=\mathbb{Z}_{2}\)에서 \(p(x)=x^{4}+x+1\)은 4차 원시다항식이다. 갈루아 체 \(GF(2^{4})\)에서 \(\alpha\)를 \(p(\alpha)=0\)인 원시원소라고 하면 다음이 성립한다.$$GF(2^{4})^{*}=\langle\alpha\rangle=\{1,\,\alpha,\,...,\,\alpha^{14}\},\,\alpha^{15}=1$$\(p(\alpha)=\alpha^{4}+\alpha+1=0\)이므로 \(GF(2^{4})\)의 원시원소는 \(\alpha,\,\alpha^{2},\,\alpha^{4},\,\alpha^{7},\,\alpha^{8},\,\alpha^{11},\,\alpha^{13},\,\alpha^{14}\)뿐이고 \(\alpha,\,\alpha^{2},\,\alpha^{4},\,\alpha^{8}\)는 \(p(x)\)의 근이고 \(\alpha^{7},\,\alpha^{11},\,\alpha^{13},\,\alpha^{14}\)는 \(q(x)=x^{4}+x^{2}+1\)의 근이며, \(GF(2)\)의 4차 원시다항식은 \(p(x),\,q(x)\)뿐이다.$$\langle\alpha\rangle,\,\langle\alpha^{3}\rangle=\{1,\,\alpha^{3},\,\alpha^{6},\,\alpha^{9},\,\alpha^{12}\},\,\langle\alpha^{5}\rangle=\{1,\,\alpha^{5},\,\alpha^{10}\},\,\langle\alpha^{15}\rangle=1$$이므로 순환군 \(\langle\alpha\rangle\)의 부분군은 다음과 같다.$$\begin{align*}\langle\alpha\rangle&=\langle\alpha^{2}\rangle=\langle\alpha^{4}\rangle=\langle\alpha^{8}\rangle\\&=\langle\alpha^{7}\rangle=\langle\alpha^{14}\rangle=\langle\alpha^{13}\rangle\\&=\langle\alpha^{11}\rangle\\ \langle\alpha^{3}\rangle&=\langle\alpha^{6}\rangle=\langle\alpha^{12}\rangle=\langle\alpha^{9}\rangle\\ \langle\alpha^{5}\rangle&=\langle\alpha^{10}\rangle\end{align*}$$임의의 소수 \(p\)와 양의 정수 \(n\)에 대하여 \(q=p^{n}\)이라고 하자. \(\alpha\)를 갈루아 체 \(GF(q)\)의 원시원소라고 하면$$GF(q)^{*}=\langle\alpha\rangle=\{1,\,\alpha,\,\alpha^{2},\,...,\,\alpha^{q-2}\},\,\alpha^{q-1}=1$$이므로 각 \(\xi\in GF(q)^{*}\)에 대하여 유일한 정수 \(i\)가 존재해서$$\xi=\alpha^{i},\,0\leq i\leq q-2$$이다. 이러한 정수 \(i\)를 \(\alpha\)를 밑으로 갖는 \(\xi\)의 이산로그(discrete logarithm)라고 하고 \(i=\text{ind}_{\alpha}\xi\)로 나타낸다. 이때 \(GF(q)^{*}\)는 위수가 \(q-1\)인 순환군이고, \(GF(p)=\mathbb{Z}_{p}\)의 원소 \(a\)를 \(GF(p)\)의 원시원소라고 하면$$GF(p)^{*}=\mathbb{Z}_{p}^{*}=\langle a\rangle=\{1,\,a,\,a^{2},\,...,\,a^{p-2}\},\,a^{p-1}=1$$이고 \(a\)는 법 \(p\)에 대한 원시근이다. 

메시-오무라(Massey-Omura) 암호체계 

갈루아 체 \(GF(q)\)에서 임의의 \(\xi\in GF(q)^{*}\)에 대하여 \(\xi^{q-1}=1\)이다. \(\text{gcd}(e,\,q-1)=1\)이고 \(1<e<q-1\)인 정수 \(e\)에 대하여 \(d\)를$$ed\equiv1\,(\text{mod}\,q-1),\,1<d<q-1$$인 정수라고 하면 작당한 양의 정수 \(k\)에 대하여$$ed=(q-1)k+1$$이므로 임의의 \(\xi\in GF(q)^{*}\)에 대하여 다음이 성립한다.$$\xi^{ed}=\xi^{(q-1)k+1}=(\xi^{q-1})^{k}\xi=\xi$$메시-오무라 암호체계는 위의 수학적 성질을 기반으로 하여 1983년에 만들어진 암호체계이다. 

메시-오무라 암호체계 프로토콜

송신자 U가 수신자 A에게 비밀 전문을 보내려면, 먼저 적당한 갈루아 체 \(GF(q)\)를 선택해 \(GF(q)\)를 공개하고 다음의 순서를 따른다.

1단계: A는 \(\text{gcd}(e_{A},\,q-1)=1\), \(1<e_{A}<q-1\)인 정수 \(e_{A}\)를 임의로 고르고$$e_{A}d_{A}\equiv1\,(\text{mod}\,q-1),\,1<d_{A}<q-1$$인 정수 \(d_{A}\)를 구하고 \(e_{A},\,d_{A}\)는 비공개한다. 

U는 \(\text{gcd}(e_{U},\,q-1)=1\), \(1<e_{U}<q-1\)인 정수 \(e_{U}\)를 임의로 고르고$$e_{U}d_{U}\equiv1\,(\text{mod}\,q-1),\,1<d_{U}<q-1$$인 정수 \(d_{U}\)를 구하고 \(e_{U},\,d_{U}\)는 비공개한다. 

2단계: 송신자 U는 A에게 보내려는 평문을 체 \(GF(q)\)의 원소 \(\xi(\neq0)\)로 나타내고, 비밀 키 \(e_{U}\)를 이용해 \(\xi^{e_{U}}\)를 계산한 결과를 A에게 전송한다.

3단계: 수신자 A는 수신된 \(\xi^{e_{U}}\)와 자신의 비밀 키 \(e_{A}\)를 이용하여 \((\xi^{e_{U}})^{e_{A}}\)를 계산하고 이 결과를 U에게 전송한다. 

4단계: 송신자 U는 수신된 \(\xi^{e_{U}e_{A}}\)와 자신의 비밀 키 \(d_{U}\)를 이용하여$$(\xi^{e_{U}e_{A}})^{d_{U}}=(\xi^{e_{U}d_{U}})^{e_{A}}=\xi^{e_{A}}$$를 계산하고 이 결과를 A에게 보낸다. 

5단계: 수신자 A는 수신된 \(\xi^{e_{A}}\)와 자신의 비밀 키 \(d_{A}\)를 이용하여$$(\xi^{e_{A}})^{d_{A}}=\xi^{e_{A}d_{A}}=\xi$$를 계산하여 평문 \(\xi\)를 얻는다.   

이 암호체계에서는 평문을 전송하기 위해 두 사용자 사이에 3번씩 송수신해야 하므로 평문을 전송하는 속도가 느리고, 평문을 탈취당할 가능성이 높다. 이를 보완하기 위해 엘 가멀이 1985년에 개발한 것이다. 앞에서 다루었던 엘-가말 암호는 체 \(GF(p)=\mathbb{Z}_{p}\)를 이용한 프로토콜이었고, 여기서 소개할 프로토콜은 갈루아 체 \(GF(q)\)를 이용한 프로토콜로 나타낸 것이다. 

엘-가말 암호체계 프로토콜

사용자 U가 사용자 A에게 비밀 전문을 보내려면 먼저 적당한 갈루아 체 \(GF(q)\)와 체 \(GF(q)\)의 원소 중 위수가 가장 큰 원소 \(\beta\)를 골라 \(GF(q)\)와 \(\beta\)를 공개하고 다음의 순서를 따른다. 

1단계: 수신자 A는 \(1<r<q-1\)인 정수 \(r\)을 고르고 \(\delta=\beta^{r}\)을 계산하여 \(\delta\)는 공개하고 \(r\)은 비공개한다.  

2단계: 송신자 U는 A에게 보내려는 평문을 \(GF(q)\)의 원소 \(\xi(\neq0)\)로 나타낸다. 그리고 \(1<s<q-1\)인 정수 \(s\)를 임의로 택하고, 공개된 \(\beta\)를 이용하여 \(\beta^{s}\)와 \(\xi\beta^{s}\)를 계산하고 \(\xi\)의 암호문 \((\beta^{s},\,\xi\delta^{s})\)를 A에게 보낸다. 

3단계: 수신자 A는 수신된 암호문과 자신의 비밀 키 \(r\)을 이용하여$$(\beta^{s})^{-r}(\xi\delta^{s})=(\beta^{s})^{-r}(\xi\beta^{rs})=\xi$$를 계산하여 평문 \(\xi\)를 얻는다.  

5차다항식 \(p(x)=x^{5}+x^{2}+1\)은 \(GF(2)=\mathbb{Z}_{2}\)위에서 원시다항식이다. \(GF(2^{5})\)의 원소 \(\alpha\)를 \(p(\alpha)=0\)$$\{a_{0}+a_{1}\alpha+\alpha_{2}\alpha^{2}+a_{3}\alpha^{3}+a_{4}\alpha^{4}\,|\,a_{0},\,a_{1},\,a_{2},\,a_{3},\,a_{4}\in GF(2)\}$$이므로$$GF(2^{5})^{*}=\langle\alpha\rangle=\{1,\,\alpha,\,\alpha^{2},\,...,\,\alpha^{30}\alpha\},\,\alpha^{31}=1$$이고 \(\alpha^{5}+\alpha^{2}+1=0\)이다. 

갈루아 체 \(GF(2^{5})\)와 그 원소 \(\beta=\alpha+1\)을 공개하자.

1단계: 수신자 A는 \(r=2\)를 고르고$$\delta=\beta^{r}=(\alpha^{18})^{2}=\alpha^{5}=1+\alpha^{2}$$를 계산하고 \(\delta\)는 공개, \(r\)은 비공개한다.  

2단계: 송신자 U가 A에게 보내려는 평문이 \(\xi=1+\alpha+\alpha^{3}\)이라고 할 때, \(s=10\)을 선택해$$\begin{align*}\beta^{s}&=(1+\alpha)^{10}=(\alpha^{18})^{10}=\alpha^{25}=1+\alpha^{3}+\alpha^{4}\\ \xi\delta^{s}&=(\alpha^{27})(\alpha^{5})^{10}=\alpha^{15}=1+\alpha+\alpha^{2}+\alpha^{3}+\alpha^{4}\end{align*}$$를 계산하고 암호문 \((\beta^{s},\,\xi\delta^{s})\)를 A에게 보낸다.   

3단계: 수신자 A는 수신된 암호문과 자신의 비밀 키 \(r\)을 이용하여$$(\beta^{s})^{-r}(\xi\delta^{s})=(\alpha^{25})^{-2}(\alpha^{15})=\alpha^{27}=\xi$$를 계산하고 평문 \(\xi\)를 얻는다. 

여기서 \(GF(2^{5})\)의 원소 \(a_{0}+a_{1}\alpha+a_{2}\alpha^{2}+a_{3}\alpha^{3}+a_{4}\alpha^{4}\)를 \(a_{0},\,a_{1},\,a_{2},\,a_{3},\,a_{4}\)로 나타내면 \(\delta\)와 평문, 암호문을 각각$$10100,\,11010,\,(10011,\,11111)$$로 나타내어진다. 

참고자료:

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