[암호학] 6. 힐 암호, 폴리그-헬만 암호

[암호학] 6. 힐 암호, 폴리그-헬만 암호

힐 암호

 

가환환 \(\mathbb{Z}_{n}=\{0,\,1,\,...,\,n-1\}\)의 단원군은$$\mathbb{Z}_{n}^{*}=\{a\in\mathbb{Z}_{n}\,|\,\text{gcd}(a,\,n)=1\},\,|\mathbb{Z}_{n}^{*}|=\phi(n)$$이고, 소수 \(p\)에 대해 \(\mathbb{Z}_{p}=\{0,\,1,\,...,\,p-1\}\)은 체이므로 다음이 성립한다. 

가환환 \(\mathbb{Z}_{n}\)위의 \(n\)차 정사각행렬 \(A\)가 정칙행렬일 필요충분조건은 \(\det A\in\mathbb{Z}_{n}^{*}\)이고 \(\mathbb{Z}_{n}\)에서 \(r\)차 일반선형군은 다음과 같다.$$GL(r,\,\mathbb{Z}_{n})=\{A\in M_{r}(\mathbb{Z}_{n})\,|\,\det A\in\mathbb{Z}_{n}^{*}\}$$소수 \(p\)에 대하여 \(r\)차 일반선형군은 다음과 같다.$$GL(r,\,\mathbb{Z}_{p})=\{A\in M_{r}(\mathbb{Z}_{p})\,|\,\det A\neq0\}$$가환군 \(\mathbb{Z}_{26}=\{0,\,1,\,\cdots,\,25\}\)에 대하여$$\mathbb{Z}_{26}^{*}=\{1,\,3,\,5,\,7,\,9,\,11,\,15,\,17,\,19,\,21,\,23,\,25\}$$이고 \(\mathbb{Z}_{26}\)위의 \(r\)차 정사각행렬 \(A\)가 정칙행렬일 필요충분조건은 \(\det A\in\mathbb{Z}_{26}^{*}\)이다. 

가환군 \(\mathbb{Z}_{26}\)위의 행렬$$A=\begin{pmatrix}4&5\\1&2\end{pmatrix}$$에 대하여$$\det A=4\cdot2-5\cdot1=3\in\mathbb{Z}_{26}^{*}$$이므로 \(A\)는 정칙행렬이고,$$26(-1)+3\cdot9=1$$이므로$$3\cdot9\equiv1\,(\text{mod}\,26)$$이고 따라서$$A^{-1}=9\begin{pmatrix}2&-5\\-1&4\end{pmatrix}=\begin{pmatrix}18&7\\17&10\end{pmatrix}$$이다. 

가환환 \(\mathbb{Z}_{26}\)에 대하여$$\mathbb{Z}_{26}^{n}=\{(x_{1},\,...,\,x_{n})\,|\,x_{1},\,...,\,x_{n}\in\mathbb{Z}_{26}\}$$이라 하고, \(\mathbb{Z}_{26}\)위에서 임의의 \(n\)차 정사각행렬 \(A\)에 대해 두 함수 \(E_{K}\), \(D_{K}\)를 다음과 같이 정의하자.$$\begin{align*}E_{K}:\mathbb{Z}_{26}^{n}\,\rightarrow\,\mathbb{Z}_{26}^{n}&\,(y_{1},\,...,\,y_{n})=E_{K}(x_{1},\,...,\,x_{n})\\ \begin{pmatrix}y_{1}\\ \vdots\\y_{n}\end{pmatrix}&=A\begin{pmatrix}x_{1}\\ \vdots\\x_{n}\end{pmatrix}\\D_{K}:\mathbb{Z}_{26}^{n}\,\rightarrow\,\mathbb{Z}_{26}^{n}&\,(y_{1},\,...,\,y_{n})=D_{K}(x_{1},\,...,\,x_{n})\\ \begin{pmatrix}y_{1}\\ \vdots\\y_{n}\end{pmatrix}&=A^{-1}\begin{pmatrix}x_{1}\\ \vdots\\x_{n}\end{pmatrix}\end{align*}$$\(AA^{-1}=A^{-1}A=I\)이므로 \(E_{K}^{-1}=D_{K}\)이다. 이러한 암호 함수 \(E_{K}\)로 암호화된 암호를 힐 암호(Hill cipher)라고 한다.

이 암호체계에서 평문을 암호문으로 변환하려면$$a_{1}\cdots a_{n}\vdots\cdots\vdots b_{1}\cdots b_{n}$$과 같이 처음부터 차례로 \(n\)개씩 묶어 몇 개의 블록으로 나누어 놓고 이들 각 블록에 암호화 함수 \(E_{K}:\mathbb{Z}_{26}^{n}\,\rightarrow\,\mathbb{Z}_{26}^{n}\)를 적용해 평문을 암호문으로 적용시킨다. 

가환군 \(\mathbb{Z}_{n}\)위의 임의의 정사각행렬 \(A\)에 대하여$$A^{2}=I\,(A^{-1}=A)$$일 때 이 행렬 \(A\)를 이용하는 힐 암호체계에서 \(E_{K}=D_{K}\)이므로 동일한 함수를 암호화 함수와 복호화 함수로 이용할 수 있다. 

가환환 \(\mathbb{Z}_{26}\)위의 2차 정사각행렬$$A=\begin{pmatrix}4&7\\9&22\end{pmatrix}$$에 대하여 \(A^{2}=I,\,A^{-1}=A\)이다. 실제로$$\begin{align*}&4\cdot4+7\cdot9=16+63=79\equiv1\,(\text{mod}\,26)\\&4\cdot7+7\cdot22=28+154=182\equiv0\,(\text{mod}\,26)\\&9\cdot4+22\cdot9=36+198=234\equiv0\,(\text{mod}\,26)\\&9\cdot7+22\cdot22=63+484=547\equiv1\,(\text{mod}\,26)\end{align*}$$이므로 따라서 암호 함수 \(E_{K}\)를 다음과 같이 정의하면$$\begin{align*}E_{K}:\mathbb{Z}_{26}^{2}\,\rightarrow\,\mathbb{Z}_{26}^{2}&,\,(y_{1},\,y_{2})=E_{K}(x_{1},\,x_{2})\\ \begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}=A\begin{pmatrix}4&7\\9&22\end{pmatrix}\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}\end{align*}$$알파벳-숫자 표를 이용해 평문 'cryptology'를 다음과 같이 \(\mathbb{Z}_{26}\)의 원소로 구성된 유한수열$$\begin{matrix}21&1&\vdots&23&16&\vdots&20&12&\vdots&15&12&\vdots&6&23\end{matrix}$$로 나타내고 이것을 처음부터 차례로 2개씩 묶는다. \(x_{1}=21,\,x_{2}=1\)일 때$$\begin{align*}y_{1}&=4\cdot21+7\cdot1=6+7=13\\y_{2}&=9\cdot21+22\cdot1=7+22=3\end{align*}$$이므로 cr은 nu로 변환된다. 마찬가지로 \(x_{1}=23,\,x_{2}=16\)일 때$$\begin{align*}y_{1}&=4\cdot23+7\cdot16=22\\y_{2}&=9\cdot23+22\cdot16=13\end{align*}$$이므로 yp는 vn으로 변환된다. 같은 방법으로 to(20 12) lo(15 12) gy(6 23)는 ic(8 2) oj(14 9) do(6 23)로 변환된다. 따라서 'cryptology'는 'nuvnicojdo'로 변환된다.

폴리그-헬만 암호

정리. \(p\)를 홀수 소수, 정수 \(e\)가 \(\text{gcd}(e,\,p-1)=1\), \(2\leq e\leq p-2\)를 만족하고, 정수 \(d\)가$$ed\equiv1\,(\text{mod}\,p-1),\,2\leq d\leq p-2$$라 하자. 체 \(\mathbb{Z}_{p}=\{0,\,1,\,...,\,p-1\}\)위의 두 함수 \(E,\,D\)를 다음과 같이 정의하면$$\begin{align*}E:\mathbb{Z}_{p}\,\rightarrow\,\mathbb{Z}_{p}&\,E(x)=x^{e}\\D:\mathbb{Z}_{p}\,\rightarrow\,\mathbb{Z}_{p}&\,D(x)=x^{d}\end{align*}$$모든 \(x\in\mathbb{Z}_{p}\)에 대하여 \(D(E(x))=x\)이므로 \(E^{-1}=D\)이다. 

증명: 정수 \(2\leq e\leq p-2\)에 대해 \(\text{gcd}(e,\,p-1)=1\)이므로 정수 \(d\)가 존재해서$$ed=\equiv1\,(\text{mod}\,p-1),\,2\leq d\leq p-2$$이다.

\(a\in\mathbb{Z}_{p}-\{0\}\)라 하자. \(\text{gcd}(a,\,p)=1\)이므로 페르마의 정리에 의해 \(a^{p-1}\equiv1\,(\text{mod}\,p)\)이고 앞의 결과에 의해 정수 \(k\)가 존재해서 \(ed=(p-1)k+1\)이다. 따라서$$(a^{e})^{d}=a^{ed}=a^{(p-1)k+1}\equiv1^{k}a\equiv a\,(\text{mod}\,p)$$이므로 \(D(E(a))=a^{ed}=a\)이다. 다음으로 \(D(E(0))=0^{ed}=0\)이므로 모든 \(a\in\mathbb{Z}_{p}\)에 대하여 \(D(E(a))=a\)이고 따라서 \(E^{-1}=D\)이다. 

폴리그와 헬만은 1976년에 위 정리를 기반으로 암호를 개발했다.

1. 송신자는 충분히 큰 소수 \(p\)를 선택하고 다음을 만족하는 정수 \(e\)를 선택해$$\text{gcd}(e,\,p-1)=1,\,2\leq e\leq p-2$$\(p\)의 값과 비밀 열쇠 \(e\)를 수신자에게 보낸다.

2. 송신자는 송신하려는 평문을 아래 표에 따라 \(0\leq a<p\)인 양의 정수 \(a\)로 나타낸다.

(앞 부분에 0이 들어가는 것이 허용되었다.)

문자	A	B	C	D	E	F	G	H	I	J	K	L	M
숫자	00	01	02	03	04	05	06	07	08	09	10	11	12
문자	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
숫자	13	14	15	16	17	18	19	20	21	22	23	24	25

3. 송신자는$$b\equiv a^{e}\,(\text{mod}\,p),\,0\leq b\leq p-1$$를 만족하는 정수 \(b\)를 구하고 이 \(b\)를 수신자에게 보낸다. 

4. 수신자는$$ed\equiv1\,(\text{mod}\,p-2),\,2\leq d\leq p-2$$인 정수 \(d\)를 구하고 수신한 \(b\)와 \(d\)를 이용해$$a\equiv b^{d}\,(\text{mod}\,p),\,0\leq a\leq p-1$$인 정수 \(a\)를 계산하여 평문 \(a\)를 구한다. 그리고 앞의 표를 이용해 \(a\)에 대응하는 평문을 얻는다. 

위에서와 같은 방법으로 얻게 되는 암호를 폴리그-헬만(Pohlig-Hellman)의 거듭제곱 암호(exponentiation cipher)라고 한다. 

여기서 \(a\geq p\)일 때에는 \(p\)가 \(n\)자리 수인 경우에 \(a\)를$$a=\underbrace{\bigcirc\cdots\bigcirc}_{a_{1}}\underbrace{\bigcirc\cdots\bigcirc}_{a_{2}}\cdots\underbrace{\bigcirc\cdots\bigcirc}_{a_{k}}$$와 같이 처음부터 차례로 길이가 \(n-1\)이하인 블록으로 나누어 이들 블록이 나타내는 정수 \(a_{1},\,a_{2},\,...,\,a_{k}\)가 \(p\)보다 작도록 한다(앞에 0이 붙는 것을 허용한다). 그리고 필요한 경우 평문에 적당한 문자를 첨가한다. 

홀수 소수 \(p=4578971\)에 대하여 \(e=3317271\)라 하면 \(\text{gcd}(e,\,p-1)=1\)이다. 

평문 'Begin attack.'을 앞의 표에 따라 정수로 나타내면$$a=0104060813001919000210$$이고, \(p\)는 7자리 수, \(a\)는 22자리수이므로 \(a\)를 길이가 6인 블록으로 나누면 4개가 남게 된다(2개가 모자라다).

평문의 끝에 문자 x를 첨가해 이에 대응하는 수 \(a\)를 구하면 \(a\)는 다음과 같이 4개의 블럭으로 나눌 수 있다.$$a=\underbrace{010406}_{a1}\underbrace{081300}_{a_{2}}\underbrace{191900}_{a_{3}}\underbrace{021023}_{a_{4}}$$이들 4개의 블럭$$a_{1}=010406,\,a_{2}=081300,\,a_{3}=191900,\,a_{4}=021023$$을 정수로 보면 각 \(a_{i}\)에 대하여 \(0\leq a_{i}\leq p-1\)이다. 각 \(a_{i}\)에 대하여$$b_{i}\equiv a_{i}^{e}\,(\text{mod}\,p)\,(0\leq b_{i}\leq p-1)$$인 정수 \(b_{i}\)를 구하여 이를 7자리의 정수로 나타내면$$b_{1}=4137884,\,b_{2}=0438421,\,b_{3}=2337477,\,b_{4}=3616413$$이고 이들을 차례로 연이어 놓으면 다음과 같이 암호문 \(b\)를 얻는다.$$b=\underbrace{4137884}_{b_{1}}\underbrace{0438421}_{b_{2}}\underbrace{3227477}_{b_{3}}\underbrace{3616413}_{b_{4}}$$유클리드의 알고리즘을 이용해$$ed\equiv1\,(\text{mod}\,p-1),\,2\leq d\leq p-2$$인 정수 \(d\)를 구하면 \(d=573651\)이고, 따라서 각 \(b_{i}\)에 대하여$$a_{i}\equiv b_{i}^{d}\,(\text{mod}\,p)$$인 정수 \(a_{i}\)를 구하기 위해 위의 절차를 거꾸로 밟으면 \(b\)로부터 평문 \(a\)를 얻는다.

참고자료:

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