[ Cryptography ] 고전 암호학 정리

고전 암호

---

고전 암호는 컴퓨터와 같은 고성능 연산 장치가 발명되기 전,

비교적 간단한 기계와 손 등으로 암복호화를 수행하던 암호를 말합니다.

 

고전 암호는 치환(Substitution)과 전치(Transposition)를 사용합니다.

- 치환(Substitution) : 평문의 문자를 다른 문자로 바꾸는 것

- 전치(Transposition) : 평문 문자들의 위치를 바꾸는 것

 

고전 암호의 종류는 다음과 같이 분류됩니다.

 

출처 : Dreamhack / 고전 암호

단일 문자 치환 암호

평문의 각 문자를 약속된 다른 문자로 치환하는 암호 방식입니다. ( 대응 관계는 일대일 대응입니다. )

예를 들어, 평문의 'A'가 암호문의 'B'로 치환된다면, 평문의 'C'와 같은 다른 문자는 'B'로 치환될 수 없습니다.

카이사르 암호 ( Caesar Cipher )

단일 문자 치환 암호의 대표적인 예시로 기원전 44년 줄리어스 카이사르가 사용한 카이사르 암호가 있습니다.

평문의 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 치환

출처 : Dreamhack / 고전 암호

 

Ex) 오른쪽으로 3번 밀어내는 카이사르 암호

APPLE => DSSOH

BANANA => EDQDQD

JUHONG => MXKRQJ

 

카이사르 암호를 사용하게 되면 위와 같이 암호화됩니다.

 

카이사르 암호는 알파벳을 밀어낸 횟수만 알면 해독할 수 있습니다.

따라서 알파벳을 밀어낸 횟수를 Key라고 한다면 알파벳은 총 26자이기 때문에 키의 개수는 26개입니다.

 

암호학에서 가능한 모든 키의 집합을 Key Space라고 합니다.

카이사르 암호는 총 26개의 키를 가지고 있기 때문에, Key Space의 크기는 26입니다.

 

또한 알파벳 A ~ Z를 0 ~ 25에 대입한다면 n글자씩 밀어내는 카이사르 암호를 다음과 같이 나타낼 수 있습니다.

 

출처 : Dreamhack / 고전 암호

 

다중 문자 치환 암호

단일 문자 치환 방식과는 달리, 평문의 한 문자가 암호문에서 여러 종류의 문자로 치환 가능합니다.

예를 들어 평문의 'A'가 암호문에서 'B'가 될 수도 있고 'K'가 될 수도 있습니다.

비제네르 암호 ( Vigenere Cipher )

대표적인 예시로 프랑스 외교관이었던 블레즈 드 비즈네르에 의하여 1586년에 발표된 비제네르 암호가 있습니다.

비제네르 표를 이용하여 미리 정해진 키워드로 암복호화

출처 : Dreamhack / 고전 암호 ( 비즈네르 표 )

 

예를 들어서,'SKY'라는 키워드로 'JUHONG' 이라는 평문을 암호화해보겠습니다.

 

먼저 키워드의 각 문자인 S, K, Y 행을 찾습니다.

그 뒤 키워드의 한 문자씩 반복하며 각 행에서 평문에 대응되는 문자로 평문을 치환합니다.

 

키	S	K	Y	S	K	Y
평문	J	U	H	O	N	G
암호문	B	E	F	G	X	E

 

비제네르 암호 또한 수식으로 나타낼 수 있습니다.

알파벳 A ~ Z를 0 ~ 25에 대응시키면 다음과 같은 합동식이 나옵니다. ( C = 암호문 / M = 평문 / K = 키워드 )

 

출처 : Dreamhack / 고전 암호

 

전치 암호

평문을 구성하는 문자들의 순서를 재배열하여 암호문을 만드는 방식입니다.

평문을 정해진 길이의 블록들로 나누고, 규칙을 적용하여 암호문을 만듭니다.

 

예를 들어서 블록의 길이가 4이고 키가 (4,2,3,1) 일 때 평문 'GYEONGSU'를 암호화해보겠습니다.

먼저 블록의 길이대로 평문을 나눠줍니다.

GYEO       NGSU

그리고 G = 1, Y = 2, E = 3... 와 같이 나눠진 블록의 각 문자에 인덱스를 부여합니다.

이후 키 (4,2,3,1)에 맞게 각 블록의 문자를 재배열합니다.

OYEG       UGSN

위와 같은 결과값이 나오게 됩니다.

따라서 평문 'GYEONGSU'의 암호문은 'OYEGUGSN' 입니다.

 

고전 암호 공격

안전하다고 여겨졌던 고전 암호들은 암호 분석 도구와 기술의 발달로 쉽게 해독되었습니다.

고전 암호를 공격하는 방법으로는 대표적으로 다음과 같은 방법이 있습니다.

전수 키 탐색 공격 ( Exhaustive Key Search Attack )

해당 공격은 평문과 암호문을 알고 있을 때,

Key Space를 전부 탐색하며 주어진 암호문과 같은 암호문을 생성하는 키를 찾는 방법입니다.

 

굉장히 단순한 공격이지만, Key Space의 크기가 작다면 빠른 시간 안에 해독이 가능합니다.

하지만 Key Space의 크기가 크다면 매우 오랜 시간이 소요됩니다.

빈도수 분석 ( Frequency Analysis )

단일 치환 암호는 평문의 문자와 암호문의 문자가 일대일 대응을 이루기 때문에,

암호화를 해도 평문의 통계적 특성이 유지됩니다.

 

예를 들어보겠습니다.

다음은 영어 문장에서 각 알파벳이 사용되는 빈도를 그래프로 나타낸 통계입니다.

 

출처 : Dreamhack / 고전 암호

그래프를 보면 'e'가 가장 많이 사용되는 것을 알 수 있습니다.

이러한 특성은 단일 치환 암호화를 해도 똑같이 적용됩니다.

 

따라서 'E'를 'A'로 치환해서 암호화를 했다면,

암호문에 가장 많이 등장하는 알파벳이 'A'일 가능성이 높습니다.

 

이러한 추측을 바탕으로 암호문을 복구하는 것을 빈도수 분석 ( Frequency Analysis ) 이라고 합니다.