Substitution techniques

쉽게 말하면 덮어쓰는 것이다. 평문에 쓰인 글자를 다른 글자로 대체하여 비문을 만드는 테크닉.

Monoalphabetic ciphers

평문의 알파벳 하나를 다른 알파벳 하나로 대체하는 기술이다. Ceasar cipher과 Permutation cipher에 대해 알아보자.

Ceasar cipher

Shift cipher의 일종으로 Julius Ceasar가 사용한 방법으로 알려져 있다. 평문의 알파벳을 뒤로 k개 밀려서 쓰는 기술이다.

예를 들어 k = 3일 때를 살펴보자.

plain : MEET ME AFTER THE TOGA PARTY
cipher: PHHW PH DIWHU WKH WRJD SDUWB

알파벳을 숫자로 보면 다음과 같다.

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

세 칸씩 뒤로 밀려서 매핑해보면 다음과 같다.

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C

plaintext letter을 $p$, cipher letter로 대체되는 알파벳을 $C$라고 하면 다음과 같은 식으로 표현할 수 있다.

$C=E(3,p)=(p+3) mod 26$

이를 일반식으로 나타내면 k번째로 밀려나는 경우

$C=E(k,p)=(p+k) mod 26$

반대로 복호화할 때 사용하는 식은

$p=D(k,C)=(C-k) mod 26$

이런 암호는 안전할까 ?
이전시간에 배운 Brute-force로 25가지 경우, k는 1부터 25까지 가능하니,만 살펴보면 해독하는데 무리가 없어보인다.

Permutation cipher

permutation cipher은 순서대로 letter을 밀려서 암호화하는 것이 아니라 임의적인 순열로 letter을 맵핑하는 것이다. 따라서 $26!$가지의 경우의 수가 있어 앞에서 살펴본 Ceasar cipher보다는 안전해 보인다.

하지만, relative frequency of Letters in English text를 살펴보면 영어에서 'e'가 가장 자주 나오는 통계 자료가 있다. 혹은 'the'처럼 자주 쓰이는 관사를 통해 암호문을 해독할 수 있는 여지가 생긴다. 그럼 이보다 더 나은 방법은 없을까 ?

이를 해결할 수 있는 방법은 2가지가 있다.

• chunk단위로 암호화
• 2글자 이상으로 대체

Multiple-letter ciphers

chunk(덩어리)단위로 묶어서 문자를 대체하는 방법으로 우리는 Playfair cipher에 대해 알아 볼 것이다.

Playfair cipher

2글자를 묶어서 암호화 복호화를 하는데 diagram을 이용한다고 보면 된다.
우선 key를 MONARCHY라고 정해보자. 그럼 25칸짜리 표를 만들 것인데 표를 우선 보자.

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

Key인 MONARCHY를 표에 우선 작성하고 key에서 등장하지 않은 알파벳을 순서대로 5x5 table에 작성하는 방식이다. 참고로 Key에 중복된 알파벳이 있다면 중복한 두 번째 알파벳부터 무시하고 작성한다. 총 알파벳의 개수가 26개지만 테이블의 크기를 맞추기 위해 보통 I/J를 같은 취급을 한다. 이제 표를 작성했다면 4가지 조건에 따라 암호화 복호화를 시행한다.

• 연속하는 동일 글자
• 같은 행
• 같은 열
• 일반적인 경우

하나씩 살펴보는데 암호화하고 싶은 단어가 balloon이라고 해보자.

묶인 2글자 중 연속하는 동일 글자 사이에는 잘 쓰이지 않는 글자를 추가한다.

2글자씩 묶어서 볼텐데 ba 다음 ll이 연속하는 글자를 가지므로 그 사이에 x와 같은 잘 쓰이지 않는 문자를 추가한다. 따라서 balxloon이 보내고자 하는 단어가 된다.

묶인 2글자가 표에서 같은 행에 속하면 오른쪽으로 한칸 이동했을 때의 문자로 대체한다.

balxloon 중 on을 표에서 보자.

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

같은 행에 속해 있고 O는 N으로, N은 A로 대체한다. (한칸 오른쪽)

묶인 2글자가 표에서 같은 열에 속하면 아래로 한칸 이동한 문자로 대체한다.

balxloon 중 BA를 표에서 보자.

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

같은 열에 속해 있고 A는 B로, B는 I/J로 대체한다.

일반적인 경우에는 표에서 사각형이 만들어지고 같은 행 반대편의 문자로 대체한다.

예를 들어 이해하는게 훨씬 바를 것이다.
balxloon 중 LX를 표에서 보자.

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

---

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

L은 S로 X는 U로 대체한다.
이 4가지 규칙을 종합해서 balloon을 암호화 하면 IBSUPMNA가 된다. 복호화는 반대로 진행하면 된다.

확실히 앞의 Monoalphabetic cipher보다는 안전해 보인다. 하지만 영어 문자의 통계적 특징을 활용하면 풀어내지 못할 암호방식은 아니다.

Polyalphabetic ciphers

이제 문자 하나당 2개 이상의 문자로 대체할 수 있는 Polyalphabetic ciphers에 대해 알아보자.

Vigenere

Shift cipher의 진화된 형태(?)라고 볼 수 있는 방식이다. Key값을 평문의 글자수만큼 이어붙여서 Key의 문자만큼 평문의 문자를 뒤로 미는 방식이다. 예를 살펴보자.
Key를 deceptive라고 하자.

~
key	d	e	c	e	p	t	i	v	e	d	e	c	e	p	t	i	v	e	d	e	c	e	p	t	i	v	e
plaintext	w	e	a	r	e	d	i	s	c	o	v	e	r	e	d	s	a	v	e	y	o	u	r	s	e	l	f
ciphertext	Z	I	C	V	T	W	Q	N	G	R	Z	G	V	T	W	A	V	Z	H	C	Q	Y	G	L	M	G	J

we are discovered save yourself에서 w는 key 중 d를 만나 3번째 뒤로 밀려나 Z가 됐고 e는 키 e를 만나 4번 뒤로 밀려 I가 됐다. 다음 표를 통해 빠르게 살펴보자.

~
key	3	4	2	4	15	19	8	21	4	3	4	2	4	15
plaintext	22	4	0	17	4	3	8	18	2	14	21	4	17	4
ciphertext	25	8	2	21	19	22	16	13	6	17	25	6	21	19

~
key	19	8	21	4	3	4	2	4	15	19	8	21	4
plaintext	3	18	0	21	4	24	14	20	17	18	4	11	5
ciphertext	22	0	21	25	7	2	16	24	6	11	12	6	9

이렇게 키값에 따라 뒤로 밀리는 정도가 달라져 한 문자를 대체하는 문자가 여러개가 될 수 있는 것이다. 그런데 이 방법은 과연 안전할까 ?
우연히 대체된 VTW가 반복됐다. 같은 key값과 같은 평문이 만난 것인데 이는 해독의 여지를 주는 일이다.

Kasiski attack (Babbage attack)
1. Guess the period length.
2. Analyze the statistics for that period length.

키의 주기를 예측하고 통계적 특성을 활용하면 암호를 해독할 수 있다는 것이다.

Autokey

autokey system은 기존 key는 한번 사용하고 부족한 key 자리는 plaintext로부터 메꾸는 방식이다. 기존 key 뒤에 plaintext가 concatenate되는 방식이다.

~
key	d	e	c	e	p	t	i	v	e	w	e	a	r	e	d	i	s	c	o	v	e	r	e	d	s	a	v
plaintext	w	e	a	r	e	d	i	s	c	o	v	e	r	e	d	s	a	v	e	y	o	u	r	s	e	l	f
ciphertext	Z	I	C	V	T	W	Q	N	G	R	Z	G	V	T	W	A	V	Z	H	C	Q	Y	G	L	M	G	J

기존 key deceptive는 한번만 나오고 그 뒤로는 we are discovered sav까지가 붙어서 계산되는 방식이다. 이러면 앞에서 주기가 생기는 문제점이 사라진다. 하지만 통계학적 특성(key나 plaintext에 e가 자주 나오는)을 숨기기에는 역부족이다.

Vernam

이 방법은 plaintext 문자를 bit나열로 바꾸고 key bit stream과 XOR 연산으로 암호화하고 복호화 하는 방식이다. 기본적으로 XOR을 두번하면 원본값이 나온다.

하지만 이 방법 역시 주기가 생기는 문제점이 있다.

One-time pad

우리가 마지막으로 살펴볼 Substitution technique이다. 미 육군에서 개발한 방법으로 암호화할 Key를 그때마다 Random하게 생성하고 한번 사용한 Key는 폐기하는 방법이다. 이론적으로 Unconditionally secure한 방법이다.

하지만 Key의 양이 plaintext와 같다는 치명적 단점이 있다. 잘 생각해보면 plaintext를 통신하고 안전한 channel에 key를 보내야만 한다. 그런데 이럴거면 안전한 채널에 plaintext를 보내는 것이 훨씬 더 효율적이다.

따라서 굉장히 중요한 통신인데 보낼 양이 적다면 사용할만한 방법이다.

---

지금까지 글자를 대체하여 암호화하는 방법들을 살펴봤다. 이제 다른 방법으로 글자의 위치를 바꾸는 테크닉을 살펴보자.

Transposition techniques

앞에서 설명했듯이 문자 자체를 바꾸는 것이 아니라 서로의 위치를 바꿔 암호화 하는 기술이다.

Rail fence technique

--
m		e		m		a		t		r		h		t		g		p		r		y
	e		t		e		f		e		t		e		o		a		a		t

철도처럼 위 아래로 읽으면 meet me after the toga party가 된다.
비문은 아래와 같다.

MEMATRHTGPRYETEFETEOAAT

수신자는 절반으로 나눠서 위의 표처럼 재배치하고 읽으면 된다.

Row technique

key의 숫자 순서대로 같은 열의 문자들을 써서 암호화하는 것이다. 표를 통해 보자.

key : 4312567
plaintext : Attack postponed until two AM
이라고 할 때
key의 길이를 열의 개수로 잡고 plaintext를 전개한다.

~
key	4	3	1	2	5	6	7
plaintext 1행	a	t	t	a	c	k	p
plaintext 2행	o	s	t	p	o	n	e
plaintext 3행	d	u	n	t	i	l	t
plaintext 4행	w	o	a	m	x	y	z

x,y,z는 그냥 padding이다.
여기서 1,2,3,4,5,6,7 순서로 모든 열을 읽는다.
그럼 비문은 TTNAAPTMTSUCAODWCOIXKNLYPETZ가 된다.

여기까지 간단하게 Transposition technique에 대해 알아봤다.

Rotor Machines

독일이 2차 세계대전 당시 사용하던 암호 기계로 그림과 같이 생겼다.

이 안에 있는 3개의 톱니가 맞물려 평문을 비문으로 바꾸어준다.
한 문자를 바꾸면 톱니가 돌아간다.
초침, 분침, 시침처럼 $26^2, 26, 1$의 비율로 톱니가 움직이는 방식이다.

Steganography

스테가노그래피는 우리가 지금까지 배운 Cryptography랑은 다른 개념이다. 추리 소설이나 스파이 영화에서 나오는 것처럼 편지에서 문장 끝의 단어들을 모으면 전달하고자 하는 진짜 메시지가 들어있는 것을 steganography라고 한다.

전달하고자 하는 내용이 메시지에 포함되는 것으로 지금까지 문자를 대체하고 위치를 바꾸는 것과는 많이 다른 것 같고 훨씬 안전하지 못하다. 하지만 서로 비밀 통신을 한다는 사실 자체를 숨기고 싶을 때 쓸 수 있는 기술이다.

결론

과거에 쓰여진 암호화 기법들을 지금까지 살펴봤다. 좋은 방법들이라고 생각하지만 해독하려고 마음 먹은 현대 공격자들에게는 조금 쉬운 문제로 다가올 수 있을 것 같다. 그 중 글자 대체 방식과 순서 바꾸는 방식을 혼합해서 사용하면 좀 더 효율적이지 않을까 생각한다.