빈도별 치환암호

가. 기존의 치환암호

치환암호란 평문의 각 문자를 다른 문자로 바꾸는 암호화 방식이다. 가장 잘 알려진 치환 암호로는 카이사르 암호(이동 암호)가 있다.

카이사르 암호

율리우스 카이사르가 이용했던 이 암호는 문자를 일정한 간격으로 이동하는 암호다. 예를 들어 키를 3으로 하면 다음과 같이 알파벳 순서를 3칸 밀어서 대응표를 만들 수 있다.

이 대응표에 따라 다음 평문을 암호화하면 다음과 같다.

NEVER TRUSH BRUTUS KBSBO QORPQ YORQRP

그런데 이 암호문은 25가지 종류의 키만 대입해보면 평문을 금방 복원할 수 있다.

일반적인 단일치환암호

꼭 일정한 규칙에 따라 대응표를 만들 필요는 없다. 규칙없이 임의로 대응표를 만들 수도 있다. 예를 들면 다음과 같다.

A	B	C	D	E	F	G	H	I	J	K	L	M
E	D	P	U	Q	R	J	G	S	N	O	W	Z
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
T	F	K	B	M	Y	H	X	A	L	I	C	V

위 대응표에 따라 다음 평문을 암호화하면 이렇게 된다.


					PURE MATHEMATICIANS JUST LOVE TO TRY UNSOLVED PROBLEMS - THEY LOVE A CHALLENGE.


					KXMQ ZEHGQZEHSPSETY NXYH WFAQ HF HMC XTYFWAQU KMFDWQZY - HGQC WFAQ E PGEWWQTJQ.

반드시 평문자와 암호문자가 같을 필요는 없다. 영어 알파벳을 한글, 숫자, 그림, 평면좌표, 이차함수, 색상 등으로 암호화하여도 무방하다. 그러나 일반적인 단일치환암호도 빈도수 분석법을 이용해 비교적 쉽게 풀 수 있다.

빈도수 분석법

알파벳은 모든 문자가 같은 빈도로 쓰이지 않는다. E는 알파벳 사용량의 12% 넘게 차지하는 반면 J, Q, X, Z는 1%도 차지하지 않는다. 그러므로 암호문에서 가장 많이 쓰이는 문자를 ‘E’로 다시 치환하는 것으로 해독을 시작할 수 있다. 또한, 단어 ‘THE’나 ‘THIS’가 가장 많이 쓰인다는 것과 한 글자 단어는 ‘A’나 ‘I’가 많다는 것도 이용할 수 있다. 이러한 여러가지 힌트를 따라서 풀다 보면 완전히 해독할 수 있다.

나. 빈도별 치환암호

빈도수분석법으로 해독될 수 있다는 단일치환암호의 취약점은 암호문에서 각 문자의 빈도가 다르게 나타난다는 점에 있다. 그렇다면 암호문의 문자 빈도를 모두 같게 하면 어떨까? 이런 발상으로 빈도별치환암호를 제안한다. 이 암호화방식은 사용빈도가 많은 문자일수록 많은 암호문 문자를 대응시키는 것이다. 예를 들어 ‘Q’, ‘J’ 등과 같이 사용빈도가 적은 문자는 비교적 적은 수의 문자를 대응시킨다. 반면 ‘E’와 같이 사용빈도가 많은 문자는 훨씬 많은 문자를 대응시킨다.

A	H4 B8 L3 H1 G4 C6 F4 A7	N	K3 D6 K6 C8 K5 I3
B	E2	O	D3 C5 I4 D7 J4 F2 K4
C	I8 K8	P	F1
D	B7 A6 A4 G3	Q	C3
E	B6 D4 H8 E8 L5 F3 A3 H3 C1 K2 A8 I2	R	E4 J8 I1 F5 J7
F	G8 B3	S	L8 L7 D8 J2 G6 I6
G	H7 D2	T	E3 G7 J6 D5 C7 E5 H6 I7 C4
H	J3 A5 J5 L4 H5 K1	U	D1 F6
I	C2 L2 E7 E1 K7 E6	V	A1
J	L6	W	A2 F8
K	L1	X	B5
L	G5 G2 I5 J1	Y	F7
M	H2 B1	Z	B4

위의 표를 보면 X, Q 등은 하나의 기호로만 대응되지만 E는 12개, T는 9개 기호로 대응되는 것을 볼 수 있다. 이는 E나 T가 X나 Q에 비해 훨씬 자주 나오는 문자이기 때문이다. 복호화할 때는 다음의 표를 사용하는 것이 더 유용하다.

	A	B	C	D	E	F	G	H	I	J	K	L
1	V	M	E	U	I	P		A	R	L	H	K
2	W		I	G	B	O	L	M	E	S	E	I
3	E	F	Q	O	T	E	D	E	N	H	N	A
4	D	Z	T	E	R	A	A	A	O	O	O	H
5	H	X	O	T	T	R	L	H	L	H	N	E
6	D	E	A	N	I	U	S	T	S	T	N	J
7	A	D	T	O	I	Y	T	G	T	R	I	S
8	E	A	N	S	E	W	F	E	C	R	C	S

다. 빈도별치환암호 적용

예를 들어 다음의 평문을 위의 대응표로 암호화해보자.


					PURE MATHEMATICIANS JUST LOVE TO TRY UNSOLVED PROBLEMS - THEY LOVE A CHALLENGE.


				F1F6F5F3 B1G4D5K1A3B1H1C4E6K8E7C6K6I6 L6D1I6C4 G2F2A1A3 J6D7 D5F5F7 F6K3D8I4G5A1K2G3 F1E4J4E2J1A8B1L8 - H6J3K2F7 J1J4A1E8 A7 I8H5L3G2J1L5K3H7K2.

라. 보완할 점

구두점과 공백문자도 해독할 때 큰 힌트가 된다. 이 문자들도 모두 다른 문자로 치환하면 대응표 없이 해독하기가 더욱 어려울 것이다.
이러한 암호화 방식은 암호문에 쓰이는 문자들이 평문에 쓰이는 문자들에 비해 더 많이 필요하다는 단점이 있다.

마. 참고자료

바. 붙임

위에서 만든 단일치환암호를 빈도수분석법으로 직접 풀어보자.

KXMQ ZEHGQZEHSPSETY NXYH WFAQ HF HMC XTYFWAQU KMFDWQZY - HGQC WFAQ E PGEWWQTJQ.

‘Q’가 9번으로 가장 많이 나왔으므로 ‘E’로 치환한다.

KXME ZEHGEZEHSPSETY NXYH WFAE HF HMC XTYFWAEU KMFDWEZY - HGEC WFAE E PGEWWETJE.

단어 ‘E’는 ‘A’ 또는 ‘I’가 치환된 암호일 것이다. ‘I’는 주로 맨 앞에 나오므로 ‘A’로 치환한다.

KXME ZAHGEZAHSPSATY NXYH WFAE HF HMC XTYFWAEU KMFDWEZY - HGEC WFAE A PGAWWETJE.

‘--E-‘가 주어로 오는 것은 ‘THEY’를 생각해 볼 수 있다.

KXME ZATHEZATSPSATY NXYT WFAE TF TMY XTYFWAEU KMFDWEZY - THEY WFAE A PHAWWETJE.

‘T-‘는 ‘TO’, ‘T-Y’는 ‘TRY’가 될 것으로 생각할 수 있다.

KXRE ZATHEZATSPSATY NXYT WOAE TO TRY XTYOWAEU KRODWEZY - THEY WOAE A PHAWWETJE.

‘-ATHE-AT---A--‘에 ‘MATHEMATICIANS’를 넣으면 단어 길이가 딱 맞다.

KXRE MATHEMATICIANS NXST WOAE TO TRY XNSOWAEU KRODWEMS - THEY WOAE A CHAWWENJE.

‘CHA--EN-E’에 ‘CHALENGE’, ‘-RO--EMS’에 ‘PROBLEMS’를 넣으면 딱 맞다.

PXRE MATHEMATICIANS NXST LOAE TO TRY XNSOLAEU PROBLEMS - THEY LOAE A CHALLENGE.

‘LO-E’에 ‘LOVE’, ‘P-RE’에 ‘PURE’를 넣으면 딱 맞다.

PURE MATHEMATICIANS NUST LOVE TO TRY UNSOLVEU PROBLEMS - THEY LOVE A CHALLENGE.

‘UNSOLVE-‘에 ‘UNSOLVED’를 넣으면 딱 맞다. ‘-UST’에는 ‘MUST’나 ‘JUST’를 생각할 수 있는데, ‘M’은 이미 사용했으므로 ‘J’로 치환한다.

PURE MATHEMATICIANS JUST LOVE TO TRY UNSOLVED PROBLEMS - THEY LOVE A CHALLENGE.

	A	B	C	D	E	F	G	H	I	J	K	L
1	V	M	E	U	I	P		A	R	L	H	K
2	W		I	G	B	O	L	M	E	S	E	I
3	E	F	Q	O	T	E	D	E	N	H	N	A
4	D	Z	T	E	R	A	A	A	O	O	O	H
5	H	X	O	T	T	R	L	H	L	H	N	E
6	D	E	A	N	I	U	S	T	S	T	N	J
7	A	D	T	O	I	Y	T	G	T	R	I	S
8	E	A	N	S	E	W	F	E	C	R	C	S

	A	B	C	D	E	F	G	H	I	J	K	L
1	V	M	E	U	I	P		A	R	L	H	K
2	W		I	G	B	O	L	M	E	S	E	I
3	E	F	Q	O	T	E	D	E	N	H	N	A
4	D	Z	T	E	R	A	A	A	O	O	O	H
5	H	X	O	T	T	R	L	H	L	H	N	E
6	D	E	A	N	I	U	S	T	S	T	N	J
7	A	D	T	O	I	Y	T	G	T	R	I	S
8	E	A	N	S	E	W	F	E	C	R	C	S

	A	B	C	D	E	F	G	H	I	J	K	L
1	V	M	E	U	I	P		A	R	L	H	K
2	W		I	G	B	O	L	M	E	S	E	I
3	E	F	Q	O	T	E	D	E	N	H	N	A
4	D	Z	T	E	R	A	A	A	O	O	O	H
5	H	X	O	T	T	R	L	H	L	H	N	E
6	D	E	A	N	I	U	S	T	S	T	N	J
7	A	D	T	O	I	Y	T	G	T	R	I	S
8	E	A	N	S	E	W	F	E	C	R	C	S