[Dreamhack] 고전 암호

[Dreamhack] 고전 암호

---

# 서론

• 고전 암호: 컴퓨터와 같이 고성능 연산 장치가 발명되기 전에, 비교적 간단하게 기계와 손 등으로 암복호화를 수행하던 암호를 말한다.
• 대부분 컴퓨터를 사용하면 쉽게 복호화되기 때문에 현대에는 사용되지 않는다.
• 고전 암호의 분류

 

 

# 단일 문자 치환 암호

• 단일 문자 치환 암호(Monoalphabetic Substitution): 평문의 각 문자를 약속된 다른 문자로 치환하는 암호이다.
• 복호화를 위해 치환의 대응 관계는 일대일 대응이다.
• 평문의 'A'가 암호문의 'B'로 치환된다면, 평문의 다른 어떤 문자도 'B'로 치환되지 않는다.

 

1. 카이사르 암호

• 카이사르 암호: 평문의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 치환한다.
• 이를 복호화할 때는 암호문의 각 문자를 다시 원래 위치로 밀어서 평문을 구한다.
• 송신자와 수신자가 몇 칸을 밀 것인지를 사전에 합의해야 통신이 이뤄질 수 있다.
• 카이사르 암호는 알파벳을 밀어낸 횟수만 알면 해독할 수 있다.
• 알파벳을 밀어낸 횟수를 키(Key)라고 한다면, 알파벳은 총 26자이므로 가능한 키의 개수는 26개이다.
• 암호학에서 가능한 모든 키의 집합을 키 공간(Key Space)라고 하는데, 이를 이용하여 다시 표현하면, 카이사르 암호에서 키 공간의 크기는 26이다.
• 알파벳 A부터 Z를 0부터 25까지 대응 시키면, n글자씩 밀어내는 카이사르 암호를 다음과 같은 합동식으로 표현할 수 있다.

• 다음 사진은 오른쪽으로 3번 밀어내는 카이사르 암호를 도식화한 것이며, 'BEEF'를 암호화하면 'EHHI'가 출력되는 것을 확인할 수 있다.

 

2. 춤추는 인형과 코드북 암호

• 춤추는 인형 암호: 사람 한 명이 글자 하나에 대응된다.
• 춤추는 인형 암호처럼 모든 알파벳을 서로 다른 기호와 무작위로 일대일 대응시켜 치환하면 키 공간의 크기는 26!이 된다.
• 이 정도 크기의 키 공간은 현대의 컴퓨터로도 전부 탐색하기 어렵다.
• 그러나 단일 치환 암호는 언어가 지닌 통계적 특성이 유지된다는 단점이 있다.
• 통계적으로, 영어 문장에서 가장 많이 사용되는 알파벳은 e이다.
• 따라서 단일 치환 암호가 적용된 어떤 암호문에서 b가 가장 많이 등장한다면, b는 e가 치환된 것이라 추측할 수 있다.
• 이 특성을 이용하면 일반적인 영문 단일 치환 암호문은 어렵지 않게 해독될 수 있다.

• 난수표나 코드북을 이용한 단일 치환 암호는 현재도 종종 사용되는 방식이다.
• 송신자와 수신자가 책을 정하고, 송신자가 책의 페이지 x와 단어의 인덱스 y를 보내면, 수신자는 책 x 페이지의 y 번째 단어를 확인하여 송신자의 메시지를 해독한다.
• 이 암호 체계는 공작원에게 지령을 전달하는 목적으로 최근에도 쓰이고 있다.
• 예를 들어 아래와 같은 책을 공유하고, 송신자가 21537, 21529, 21406, 21402라는 암호문을 보내면, 수신자는 215 페이지의 37번째 단어, 214 페이지의 6번째 단어, 214 페이지의 2번째 단어를 찾고, 이를 이어 붙여 come to yellow roads라는 메시지를 구할 수 있다.

 

 

# 다중 문자 치환 암호

• 다중 문자 치환 암호(Polyalphabetic Substitution Cipher): 단일 문자 치환 암호와 달리, 평문의 한 문자가 암호문에서 여러 종류의 문자로 치환될 수 있다.
• 대표적인 다중 문자 치환 암호로는 비제네르 암호(Vigenere Cipher)가 있다.
• 비제네르 암호에서 암호화와 복호화는 미리 정해진 키워드를 통해 이루어진다.
• 'SKY'라는 키워드로 평문 'DREAMHACK'을 비제네르 암호화하는 과정은 다음과 같다.
• 우선 아래와 같은 비제네르 표에서, 키의 각 문자인 'S', 'K', 'Y' 행을 고른다.

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

• A부터 Z를 0부터 25까지 대응시키면 비제네르 암호를 다음의 합동식으로 표현할 수 있다.
  • 여기서 C는 암호문, M은 평문, K는 키워드를 의미하고, Xi는 X의 i번째 요소를 나타낸다.

 

 

# 전치 암호

• 전치 암호(Transposition Cipher)는 평문을 구성하는 문자들의 순서를 재배열하여 암호문을 만든다.
• 평문을 정해진 길이의 블록들로 나누고, 규칙을 적용하여 블록 안의 문자들을 재배치한다.
• 예를 들어, 블록의 길이가 3이고 키가 (3, 1, 2)일 때 평문 DREAM HACK의 암호화는 다음과 같이 이루어진다.

• 전치 암호의 대표적인 예시로는 기원전 450년에 고대 그리스인들이 발견한 스키테일 암호(Scytale Cipher)가 있다.
• 이 암호는 나무봉(Scytale)을 이용한 암호로, 먼저 메시지를 교환할 두 사람이 같은 크기의 나무봉을 제작한다.
• 그 뒤, 송신자는 종이 테이프를 나무봉에 감고, 테이프 위에 세로로 메시지를 기입하여 암호문을 만든다.
• 종이테이프를 풀어내면 순서가 뒤섞여 메시지를 읽을 수 없지만, 같은 나무봉을 가진 수신자는 테이브를 다시 나무봉에 감아서 이를 해석할 수 있다.

 

 

# 고전 암호 공격

1. 전수 키 탐색 공격

• 전수 키 탐색 공격(Exhaustive Key Search Attack)은 평문과 암호문을 알 때, 키 공간을 전부 탐색하며 주어진 암호문과 같은 암호문을 생성하는 키를 찾는 방법이다.
• 키 공간의 크기가 작다면 빠른 시간 안에 키를 찾고, 암호를 해독할 수 있다.
• 단일 치환 암호인 카이사르 암호는 키 공간이 26으로 매우 작기 때문에 전수 키 탐색 공격에 취약하다.

 

2. 빈도수 공격

• 단일 치환 암호는 평문의 문자와 암호문의 문자가 항상 일대일 대응을 이루기 때문에 평문의 통계적 특성이 유지된다.
• 예를 들어, 영어 문장에서 각 알파벳이 사용되는 빈도를 그래프로 표현하면 다음과 같은데, 이런 특성은 단일 치환해도 유지된다.

영문에서 알파벳의 사용 빈도

• 위 사진에 따르면 평문의 E를 A로 치환해서 암호문을 만들었다면, 암호문에서 가장 많이 등장하는 알파벳이 A일 가능성이 높다.
• 이런 추측을 바탕으로 암호문을 복구하는 것을 빈도수 분석(frequency analysis)이라고 한다.
• 이는 암호문이 어떤 언어로 구성되어 있어도 대상 언어의 특성을 안다면 시도해볼 수 있다.
• 다중 치환 암호는 이러한 통계적 특성이 사라지기 때문에, 빈도수 공격으로부터 비교적 안전하다고 알려져있다.

 

 

# Quiz