[암호학] 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$를 얻는다.

참고자료:

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