[암호학] 5. 아핀 암호, 치환 암호, 비즈네르 암호

[암호학] 5. 아핀 암호, 치환 암호, 비즈네르 암호

아핀 암호

영문자로 작성된 평문을 암호문으로 변환시킬 때 먼저 평문 속 대문자는 소문자로 고치고 구두점이나 문자와 문자 사이의 간격을 없앤다. 

알파벳은 A부터 Z까지 총 26개가 있으므로 A부터 Z까지의 문자에 0부터 25까지의 정수를 대응시키면 영문자 전체의 집합은 $\mathbb{Z}_{26}$과 일대일로 대응한다.

문자	A	B	C	D	E	F	G	H	I	J	K	L	M
숫자	0	1	2	3	4	5	6	7	8	9	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

위의 표로부터 평문 작성에 사용되는 문자의 종류에 따라 문자 전체의 집합은 그 집합의 개수가 $n$일 때, $\mathbb{Z}_{n}=\{0,\,1,\,...,\,n-1\}$과 일대일로 대응한다.   

카이사르(Caesar, 시저)는 평문의 문자 A, B, ..., X, Y, Z를 순서를 유지한 채 3 단계씩 옮겨(shift) 각각 D, E, ..., A, B, C로 바꾸어 놓는 방법으로 평문을 암호문으로 변환시켰다. 즉 다음의 표대로 각 문자를 순서에 따라 그 다음 세 번째 알파벳으로 암호화한다.

문자

A

B

C

D

E

F

G

H

I

J

K

L

M

암호문

D

E

F

G

H

I

J

K

L

M

N

O

P

문자

N

O

P

W

R

S

T

U

V

W

X

Y

Z

암호문

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

 

평문 $$\text{VENI VIDI VICI}$$ (뜻: 왔노라, 보았노라, 이겼노라)를 암호화하면 $$\text{YHQLYLGLYLFL}$$ 이고, 문자-숫자 표에 따라 각 문자를 $\mathbb{Z}_{26}$의 원소로 나타내면 평문과 암호문은 각각 다음과 같은 유한수열로 나타낼 수 있다. $$\begin{matrix}21&4&13&8&21&8&3&8&21&8&2&8\\|&|&|&|&|&|&|&|&|&|&|&|\\24&7&16&11&24&11&6&11&24&11&5&11\end{matrix}$$ 이처럼 평문과 암호문을 각각 $\mathbb{Z}_{26}$의 원소로 이루어진 유한수열 $$x_{1}x_{2}\cdots x_{n},\,y_{1}y_{2}\cdots y_{n}$$ 으로 나타내면 $\mathbb{Z}_{26}$에서 각 $i\,(1\leq i\leq n)$에 대하여 등식 $y_{i}=x_{i}+3$이 성립하고, 이 등식은 다음의 합동식을 뜻한다. $$y_{i}\equiv x_{i}+3\,(\text{mod}\,26),\,(0\leq x_{i},\,y_{i}\leq25)$$ 여기서 $K=3$은 열쇠이고, 다음의 두 함수 $$\begin{align*}E_{K}:\mathbb{Z}_{26}\,\rightarrow\,\mathbb{Z}_{26}&\,E_{K}(x)=x+3\\D_{K}:\mathbb{Z}_{26}\,\rightarrow\,\mathbb{Z}_{26}&\,D_{K}(x)=x-3\end{align*}$$ 는 각각 암호화 함수, 복호 함수이다. 위와 같이 정의된 암호화 함수 $E_{K}$로 작성된 암호문을 카이사르 암호문(Caesar cipher)이라고 한다.  

*참고: 영어 알파벳의 사용 빈도

알파벳	a	b	c	d	e	f	g	h	i
빈도	082	015	028	043	127	022	020	061	070
알파벳	j	k	l	m	n	o	p	q	r
빈도	002	008	040	024	067	075	019	001	060
알파벳	s	t	u	v	w	x	y	z	총합
빈도	063	091	028	010	023	001	020	001	1000

 

앞에서 다루었던 카이사르 암호를 다음과 같이 일반화할 수 있다. 

일반적으로 가환환 $\mathbb{Z}_{n}=\{0,\,1,\,\cdots,\,n-1\}$에서 곱셈에 대해 역원을 갖는 원소 전체의 집합은 다음과 같다. $$\mathbb{Z}_{n}^{*}=\{a\in\mathbb{Z}_{n}\,|\,\text{gcd}(a,\,n)=1\}$$ 두 원소 $a\in\mathbb{Z}_{n}^{*}$, $b\in\mathbb{Z}_{n}$으로 이루어진 순서쌍을 $K$라 하고 두 함수 $E_{K},\,D_{K}$를 다음과 같이 정의하자. $$\begin{align*}E_{K}:\mathbb{Z}_{n}\,\rightarrow\,\mathbb{Z}_{n}&\,E_{K}(x)=ax+b\\D_{K}:\mathbb{Z}_{n}\,\rightarrow\,\mathbb{Z}_{n}&\,D_{K}(x)=a^{-1}(x-b)\end{align*}$$ 이때 임의의 $x\in\mathbb{Z}_{n}$에 대하여 $$D_{K}(E_{K}(x))=D_{K}(ax+b)=a^{-1}((ax+b)-b)=x$$ 이므로 $E_{K}^{-1}=E_{K}$이고, 이러한 함수 $E_{K}$를 아핀 암호(affine cipher)라고 한다. 

가환환 $\mathbb{Z}_{26}=\{0,\,1,\,...,\,24,\,25\}$에서 $$\mathbb{Z}_{26}^{*}=\{1,\,3,\,5,\,7,\,9,\,11,\,15,\,17,\,19,\,21,\,23,\,25\}$$ 이므로 $K=(7,\,10)$일 때 가환환 $\mathbb{Z}_{26}$에서의 아핀암호는 $$\begin{align*}E_{K}:\mathbb{Z}_{26}\,\rightarrow\,\mathbb{Z}_{26}&\,E_{K}(x)=7x+10\\D_{K}:\mathbb{Z}_{26}\,\rightarrow\,\mathbb{Z}_{26}&\,D_{K}(x)=15x+6\end{align*}$$ 인데 $$7^{-1}=15,\,7^{-1}(-10)=15(-10)=6$$ 이기 때문이다. $$7\cdot11+10=87\equiv9\,(\text{mod}\,26)$$ 이므로 $\mathbb{Z}_{26}$에서 $E_{K}(11)=9$이다. 

평문 'VENI VIDI VICI'를 $\mathbb{Z}_{26}$상의 수열로 나타내면 다음과 같고 $$\begin{matrix}21&4&13&8&21&8&3&8&21&8&2&8\end{matrix}$$ 이 아핀암호에 의해 다음과 같은 암호문으로 변환되며 $$\begin{matrix}1&12&23&14&1&14&5&14&1&14&24&14\end{matrix}$$ 여기에 대응하는 암호문은 BMXOBOFOBOYO이다.    

앞서 다루었던 카이사르 암호는 아핀 암호문이고, 일반적으로 가환환 $\mathbb{Z}_{n}$위의 아핀 암호체계에서 열쇠 전체의 집합은 $$\mathcal{K}=\{(a,\,b)\,|\,a\in\mathbb{Z}_{n}^{*},\,\mathbb{Z}_{n}\}$$ 이므로 전체 키(열쇠)의 개수는 $|\mathbb{Z}_{n}^{*}||\mathbb{Z}_{n}|=n\phi(n)$이다. 

영문자를 이용해 평문을 암호문으로 바꾸는 경우 $n=26$이므로 키 전체의 개수는 $26\phi(26)=26\cdot12=312$이다.    

$\mathbb{Z}_{26}$에서의 아핀암호 $E_{K}(x)$에 대해 $E_{K}(4)=11$, $E_{K}(19)=20$일 때, $$\begin{cases}4a+b\equiv11\,(\text{mod}\,26)\\19a+b\equiv20\,(\text{mod}\,26)\end{cases}$$ 이므로 $$a\det\begin{pmatrix}4&1\\19&1\end{pmatrix}\equiv\det\begin{pmatrix}11&1\\20&1\end{pmatrix}\,(\text{mod}\,26),\,b\det\begin{pmatrix}4&1\\19&1\end{pmatrix}\equiv\det\begin{pmatrix}4&11\\19&20\end{pmatrix}\,(\text{mod}\,26)$$ 즉 $$-15a\equiv-9\,(\text{mod}\,26),\,-15b\equiv1\,(\text{mod}\,26)$$ 이고 $$11a\equiv17\,(\text{mod}\,26),\,11b\equiv1\,(\text{mod}\,26)$$ 이므로 이 두 합동식의 해는 $$a\equiv11\,(\text{mod}\,26),\,b\equiv19\,(\text{mod}\,26)$$ 따라서 아핀암호는 $E_{K}(x)=11x+19$이다. 

치환 암호

집합 $X$위의 일대일 대응 $\sigma:X\,\rightarrow\,X$를 집합 $X$위의 치환(permutation)이라 하고, $\sigma$의 역함수 $\sigma^{-1}:X\,\rightarrow\,X$를 $\sigma$의 역치환이라고 한다. 특히 유한집합 $X_{n}=\{1,\,2,\,...,\,n\}$위의 치환 $\sigma$에 대하여 $$\sigma(1)=i_{1},\,\sigma(2)=i_{2},\,...,\,\sigma(n)=i_{n}$$ 일 때, 이 치환을 다음과 같이 나타낸다. $$\sigma=\begin{pmatrix}1&2&\cdots&n\\i_{1}&i_{2}&\cdots&i_{n}\end{pmatrix}$$ 여기서 첫째 줄에는 $X_{n}$의 원소를 임의로 배열할 수 있으나 둘째 줄에는 첫째 줄에 있는 원소 $x$의 바로 아래에 $\sigma(x)$를 적어야 한다. 이때 치환 $\sigma$의 역치환 $\sigma^{-1}$는 다음과 같다. $$\sigma^{-1}=\begin{pmatrix}i_{1}&i_{2}&\cdots&i_{n}\\1&2&\cdots&n\end{pmatrix}$$ 집합 $\mathbb{Z}_{6}=\{0,\,1,\,2,\,3,\,4,\,5\}$의 치환이 $$\sigma=\begin{pmatrix}0&1&2&3&4&5\\3&1&5&0&2&4\end{pmatrix}$$ 일 때 그 역치환 $\sigma^{-1}$는 다음과 같다. $$\sigma^{-1}=\begin{pmatrix}3&1&5&0&2&4\\0&1&2&3&4&5\end{pmatrix}=\begin{pmatrix}0&1&2&3&4&5\\3&1&4&0&5&2\end{pmatrix}$$ 집합 $\mathbb{Z}_{26}$위의 치환 $\sigma$를 열쇠로 하여 $K=\sigma$라 할 때 두 함수 $$\begin{align*}E_{K}:\mathbb{Z}_{26}\,\rightarrow\,\mathbb{Z}_{26}&\,E_{K}(x)=\sigma(x)\\D_{K}:\mathbb{Z}_{26}\,\rightarrow\,\mathbb{Z}_{26}&\,D_{K}(x)=\sigma^{-1}(x)\end{align*}$$ 는 일대일 대응이고 $E_{K}^{-1}=D_{K}^{-1}$이다. 이러한 암호를 대치 암호(substitution cipher)라고 한다. 이 암호체계에서 키(열쇠) 전체의 집합은 $\mathbb{Z}_{n}$위의 치환 전체의 집합이므로, 키의 총 개수는 $n!$이다. 

양의 정수 $n$에 대하여 $\mathbb{Z}_{26}^{n}=\{(x_{1},\,...,\,x_{n})\,|\,x_{1},\,...,\,x_{n}\in\mathbb{Z}_{26}\}$라 하고 $X_{n}=\{1,\,2,\,...,\,n\}$위의 치환 $\sigma$를 선택하여 열쇠를 $K=\sigma$라 할 때 $$\begin{align*}E_{K}:\mathbb{Z}_{26}^{n}\,\rightarrow\,\mathbb{Z}_{26}^{n}&\,E_{K}(x_{1},\,...,\,x_{n})=(x_{\sigma(1)},\,...,\,x_{\sigma(n)})\\D_{K}:\mathbb{Z}_{26}^{n}\,\rightarrow\,\mathbb{Z}_{26}^{n}&\,D_{K}(x_{1},\,...,\,x_{n})=(x_{\sigma^{-1}(1)},\,...,\,x_{\sigma^{-1}(n)})\end{align*}$$ 는 $\mathbb{Z}_{26}^{n}$위의 일대일 대응이고 $E_{K}^{-1}=D_{K}$이다. 이러한 암호 $E_{K}$를 치환 암호문(permutation cipher)이라고 한다.   

이때 평문을 암호문으로 변환하려면 알파벳-숫자 표를 이용해 알파벳들을 $\mathbb{Z}_{26}$의 원소로 바꾸고 적당한 양의 정수 $n$을 선택해 $$a_{1}\cdots a_{n}\vdots\cdots\vdots b_{1}\cdots b_{n}$$ 과 같이 처음부터 차례로 $n$개씩 묶어 몇 개의 블럭으로 나누고 이들 각 블럭에 $E_{K}$를 적용시켜 암호문을 만든다. 평문에 들어있는 문자의 개수가 $n$의 배수가 아니면 평문의 마지막에 적당한 문자를 첨가한다.    

평문 'VENI VIDI VICI'를 집합 $\mathbb{Z}_{26}$의 원소를 값으로 갖는 유한수열로 나타내고 이것을 다음과 같이 처음부터 4개로 3개씩 묶는다. $$\begin{matrix}21&4&13&8&\vdots&21&8&3&8&\vdots&21&8&2&8\end{matrix}$$ 열쇠 $K$를 치환 $$\sigma=\begin{pmatrix}1&2&3&4\\3&1&4&2\end{pmatrix}$$ 택하여 함수 $$E_{K}:\mathbb{Z}_{26}^{4}\,\rightarrow\,\mathbb{Z}_{26}^{4}\,E_{K}(x_{1},\,x_{2},\,x_{3},\,x_{4})=(x_{3},\,x_{1},\,x_{4},\,x_{2})$$ 를 이용하면 위의 평문을 다음과 같이 암호화할 수 있다. $$\begin{matrix}13&21&8&4&\vdots&3&21&8&8&\vdots&2&21&8&8\end{matrix}$$ 암호화된 문자는 NVIEDVIICVII이다.   

비즈네르 암호

양의 정수 $n$에 대하여 $\mathbb{Z}_{n}$의 $n$개의 원소 $k_{1},\,k_{2},\,...,\,k_{n}$로 이루어진 $K=(k_{1},\,...,\,k_{n})$를 열쇠로 택할 때, 두 함수 $$\begin{align*}E_{K}:\mathbb{Z}_{26}^{n}\,\rightarrow\,\mathbb{Z}_{26}^{n}&\,E_{K}(x_{1},\,...,\,x_{n})=(x_{1}+k_{1},\,...,\,x_{r}+k_{n})\\D_{K}:\mathbb{Z}_{26}^{n}\,\rightarrow\,\mathbb{Z}_{26}^{n}&\,D_{K}(x_{1},\,...,\,x_{n})=(x_{1}-k_{1},\,...,\,x_{n}-k_{n})\end{align*}$$ 는 집합 $\mathbb{Z}_{26}^{n}$위의 일대일 대응이고 $E_{K}^{-1}=D_{K}$이다. 

위와 같이 정의된 함수 $E_{K}$를 이용하여 작성된 암호문을 비즈네르 암호(Vigenere cipher)라고 한다. 

이 암호체계에서 평문을 암호문으로 변화시키려면 평문을 $$a_{1}\cdots a_{n}\vdots\cdots\vdots b_{1}\cdots b_{n}$$ 과 같이 처음부터 차례로 $n$개씩 묶어 몇 개의 블록으로 나눈 다음 이들 각 블록에 $E_{K}$를 적용해 암호문을 얻는다. 

평문 'VENI VIDI VICI'를 다음과 같이 $\mathbb{Z}_{26}$의 원소로 나타낼 수 있고 $$\begin{matrix}21&4&3&8&\vdots&21&8&3&8&\vdots&21&8&2&8\end{matrix}$$ 열쇠를 $K=(2, 8, 15, 7)$라 하고 암호화를 $$E_{K}(x_{1},\,x_{2},\,x_{3},\,x_{4})=(x_{1}+2,\,x_{2}+8,\,x_{3}+15,\,x_{4}+7)$$ 라 하면 다음과 같이 암호화된다. $$\begin{matrix}23&12&2&15&\vdots&23&16&18&15&\vdots&23&16&17&15\end{matrix}$$ 참고자료:

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

수리암호학개론, 김명환, 경문사