[암호학] 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}$$참고자료:

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

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