들어가며

1. 서론

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

1.1 고전 암호의 설계 원리

• 고전 암호는 일반적으로 치환(Substitution)과 전치(Transposition)의 방법으로 설계되는 것이다.
  • 치환은 평문의 문자를 다른 문자로 바꾸는 것을 말하며, 전치는 평문 문자들의 위치를 바꾸는 것을 말하는 것이다.

1.3 고전 암호의 유형

• 단순한 고전 암호는 한 가지 원리만을 사용하는 치환 암호(Substitution cipher) 또는 전치 암호(Transposition cipher)인 것이다.
  • 복잡한 고전 암호는 두 원리를 모두 사용하는 것이다.
  • 치환 암호는 단일 문자 치환 암호(Monoalphabetic substitution cipher)와 다중 문자 치환 암호(Polyalphabetic substitution cipher)로 나누어지는 것이다.

1.4 강의 목표

• 이번 강의에서는 치환 암호와 전치 암호의 개념, 이들의 예, 그리고 간단한 공격 방법을 소개하는 것이다.

2. 고전 암호의 분류

---

고전 암호

1. 단일 문자 치환 암호

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

1.1 카이사르 암호

• 단일 문자 치환 암호의 대표적인 예로 기원전 44년 줄리어스 카이사르가 사용한 카이사르 암호(Caesar cipher)가 있는 것이다.
  • 카이사르 암호는 평문의 각 알파벳을 정해진 횟수만큼 다음 순서에 해당하는 알파벳으로 치환하는 것이다.
  • 이때, 'Z'의 다음 알파벳은 'A'로 정의되는 것이다.
  • 이를 복호화할 때는 암호문의 각 문자를 다시 정해진 횟수만큼 이전 알파벳으로 치환시켜 평문을 구한다.
  • 송신자와 수신자가 몇 회만큼 다음 순서의 알파벳으로 치환할지를 사전에 합의해야 통신이 이뤄질 수 있다.
• 카이사르 암호는 알파벳을 밀어낸 횟수만 알면 해독할 수 있다.
  • 알파벳을 밀어낸 횟수를 키(Key)라고 한다면, 알파벳은 총 26자이므로 가능한 키의 가짓수는 26개다.
• 아래 사진은 오른쪽으로 3번 밀어내는 카이사르 암호를 도식화한다.
  • 이를 이용하여 “BEEF”를 암호화하면 “EHHI”가 출력된다.

1.2 춤추는 인형과 코드북 암호

• 카이사르 암호는 알파벳을 밀어서 암호화하는 특성상, 키 공간의 크기가 작기 때문에 컴퓨터를 사용하면 쉽게 복호화된다.

  • 조금 더 복잡한 단일 치환암호로는 셜록 홈즈에 나온 춤추는 인형 암호가 있다.
  • 이 암호는 사람 한 명이 글자 하나에 대응되지만 규칙성이 없어서 암호문으로부터 평문을 쉽게 유추할 수 없다.
  

• 춤추는 인형 암호처럼 모든 알파벳을 서로 다른 기호와 무작위로 일대일 대응시켜 치환하면 키 공간의 크기는  26!(26×25×⋯×2×1≈4⋅${10}^{26}$1026)이 된다.

  • 이 정도 크기의 키 공간은 현대의 컴퓨터로도 전부 탐색하기 어렵다.

• 그러나 단일 치환 암호는 언어가 지닌 통계적 특성이 유지된다는 단점이 있다.

  • 통계적으로, 영어 문장에서 가장 많이 사용되는 알파벳은 e다.
  • 따라서 단일 치환 암호가 적용된 어떤 암호문에서 b가 가장 많이 등장한다면, b는 e가 치환된 것이라 추측할 수 있다.
  • 이 특성을 이용하면 일반적인 영문 단일 치환 암호문은 어렵지 않게 해독될 수 있다.

• 난수표나 코드북을 이용한 단일 치환 암호는 현재도 종종 사용된다.

  • 송신자와 수신자가 책을 정하고, 송신자가 책의 페이지 _x_와 단어의 인덱스 _y_를 보내면, 수신자는 책 _x_페이지의  _y_번째 단어를 확인하여 송신자의 메세지를 해독한다.
  • 이 암호 체계는 공작원에게 지령을 전달하는 목적으로 최근에도 쓰이고 있다.

• 예를 들어 아래와 같은 책을 공유하고, 송신자가 21536, 21528, 21406, 21402라는 암호문을 보내면, 수신자는 215 페이지의 36번째 단어, 215 페이지의 28번째 단어, 214 페이지의 6번째 단어, 214 페이지의 2번째 단어를 찾고, 이를 이어 붙여 come to yellow roads 라는 메세지를 구할 수 있다.

2. 다중 문자 치환 암호

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

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

3. 전치 암호

• 전치 암호(Transposition cipher)는 평문을 구성하는 문자들의 순서를 재배열하여 암호문을 만든다.

  • 평문을 정해진 길이의 블록들로 나누고, 규칙을 적용하여 블록 안의 문자들을 재배치한다.

• 예를 들어, 블록의 길이가 3이고 키가 (3,1,2)일 때 평문 DREAMHACK의 암호화는 아래와 같이 이루어진다.

  

• 전치 암호의 대표적인 예시로는 기원전 450년에 고대 그리스인들이 발견한 스키테일 암호(Scytale cipher)가 있다.

  • 이 암호는 나무봉(Scytale)을 이용한 암호로, 먼저 메세지를 교환할 두 사람이 같은 크기의 나무봉을 제작한다.
  • 그 뒤 송신자는 종이 테이프를 나무봉에 감고, 테이프 위에 세로로 메세지를 기입하여 암호문를 만든다.
  • 종이테이프를 풀어내면 순서가 뒤섞여 메세지를 읽을 수 없지만, 같은 나무봉을 가진 수신자는 테이프를 다시 나무봉에 감아서 이를 해석할 수 있다.

4. 고전 암호 공격

• 안전하다고 여겨졌던 고전 암호들은 암호 분석 도구와 기술의 발달로 쉽게 분석되었다.
  • 고전 암호를 공격하는 방법으로는 대표적으로 전수 키 탐색 공격(Exhaustive key search attack)과 빈도수 분석(Frequency analysis)이 있다.

4.1 전수 키 탐색 공격

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

4.2 빈도수 공격

• 단일 치환 암호는 평문의 문자와 암호문의 문자가 항상 일대일 대응을 이루기 때문에 평문의 통계적 특성이 유지된다.
  • 예를 들어, 영어 문장에서 각 알파벳이 사용되는 빈도를 그래프로 표현하면 아래와 같은데, 이런 특성은 문자를 단일 치환해도 유지된다.
• 아래 그래프에 따르면 평문의 E를 A로 치환해서 암호문을 만들었다면, 암호문에서 가장 많이 등장하는 알파벳이 A일 가능성이 높다.
  • 이런 추측을 바탕으로 암호문을 복구하는 것을 빈도수 분석(Frequency analysis)이라고 한다.
  • 이는 암호문이 어떤 언어로 구성되어 있어도 대상 언어의 특성을 안다면 시도해볼 수 있다.
• 다중 치환 암호는 이러한 통계적 특성이 사라지기 때문에, 빈도수 공격으로부터 비교적 안전하다고 알려져 있다.

---

마치며

1. 마치며

• 이번 강의에서는 여러 종류의 고전 암호들과 고전 암호를 공격하는 방법들에 대해서 알아보았다.
  • 고전 암호의 주요 원리인 치환과 전치는 현대 암호에서도 종종 사용되니 기억해두시면 좋을 것 같다. 🚩

2. 키워드

• 치환(Substitution):
  • 평문의 각 문자를 다른 문자로 치환하는 기법이다.
  • 평문의 문자와 암호문의 문자가 이루는 대응 관계에 따라 단일 치환 암호, 다중 치환 암호로 구분된다.
• 전치(Transposition):
  • 평문을 구성하는 문자들의 순서를 바꾸는 기법이다.
• 전수 키 탐색 공격(Exhaustive key search attack):
  • 키 공간을 전부 탐색하는 공격 방법이다. 가능한 키의 수가 적으면 효과적일 수 있으나, 현대 암호는 키 공간의 크기가 매우 넓으므로 이를 대상으로 사용하기 어렵다.
• 빈도수 분석(Frequency analysis):
  • 암호문에서 단어가 등장하는 빈도를 분석하여 통계적으로 복호화하는 공격 기법이다.
  • 특수한 경우에서만 사용될 수 있다.