[정보보안] 고전 암호 기법 (이동 암호, 치환 암호, 전치 암호)

1. Shift Cipher (이동 암호)

Shift Cipher는 평문의 알파벳을 일정한 거리만큼 밀어서 암호화하는 것을 말한다. 

예를 들면 a→d, b→e 이런식이다.

 

이를 일반화 하면 다음과 같다.  key 값을 \(k\)라고 할 때

• 암호화: \(y = (x + k) \pmod{26}\)
• 복호화: \(x = (y - k) \pmod{26}\)

\(\pmod{26}\)을 하는 이유는 알파벳이 26자이기 때문이다. z를 넘어서면 다시 a로 돌아오게끔 해준다.

 

아스키 코드 기준으로는 다음과 같이 된다.

• 대문자 암호화: \(y = 65 + \{(x - 65 + k) \pmod{26}\}\)
• 소문자 암호화: \(y = 97 + \{(x - 97 + k) \pmod{26}\}\)

 

* Shift Cipher에 대한 공격 유형

공격자가 가지는 정보 수준에 따라 4가지로 구분한다. 공격자가 어떤 정보를 가지고 있는지 분류할 수 있어야한다.

• Ciphertext only(암호문 단독 공격): 암호문만 가지고 평문을 추리
• Known plaintext(기지 평문 공격): 암호문과 이에 대응하는 평문까지 일부 가지고 추리 (한글자만 매칭해도 다 뚫린다.)
• Chosen plaintext(선택 평문 공격): 공격자가 평문을 가지고, 암호화 장치에 접근 가능한 상황 (평문을 암호화해서 암호문을 구할 수 있다.)
• Chosen ciphertext(선택 암호문 공격): 공격자가 암호문을 가지고, 복호화 장치에 접근 가능한 상황 (암호문을 복호화해서 평문을 구할 수 있다.)

 

Exhaustive Attack(전수 조사 공격)도 가능하다. 키 값이 1부터 26까지 밖에 안되기 때문에 전수 조사 공격을 해도 순식간에 뚫어버릴 수 있다.

 

즉, Shift Cipher는 매우 취약한 암호 기법이다.

---

2. Monoalphabetic Substitution Ciphers (단일 치환 암호)

Shift Cipher 보다는 조금 더 발전된 방식이다. Shift Cipher에서는 단순히 모두 동일하게 3칸을 밀었다면 이 방법은 각각에 대응되는 알파벳을 지정하는 것이다. 즉 임의의 순열로 재배치하는 것이고 순서가 랜덤이 된다. 그러나 여전히 일대일 함수인 것은 동일하다.

 

수학적으로 계산했을 때 가능한 키의 개수(키 공간, key space)가 \(26! \approx 4 \times 10^{26}\)으로 매우 크다.

 

그러나 아무리 키 공간이 커도 안전하다고 할 수 없는데 언어의 통계적 특성 때문이다.

영어에서 가장 많이 사용되는 알파벳은 'e'이다. 그래서 가장 많이 등장하는 단어가 e일 확률이 높다. 이러한 공격 방법을 빈도분석(frequency analysis) 공격이라고 한다. 

 

이러한 특성을 이용해 암호문 단독 공격(Ciphertext Only)에도 빈도 분석 방법으로 뚫릴 수 있다.

 

---

3. Playfair Cipher (Multiple-Letter Encryption)

Playfair Cipher는 단일 치환 암호의 취약점인 빈도 분석을 어렵게 만들기 위해, 한 번에 여러 글자를 암호화하는 방식이다.

Playfair Cipher는 키 행렬이라는 표를 만들고 암호화 규칙을 적용하는 방식으로 진행된다.

 

1. 키 행렬(Key Matrix) 만들기

• \(5 \times 5\) 행렬을 만들고, 특정 키워드를 먼저 채운다.(여기서는 MONARCHY)
• 나머지 칸을 중복되지 않는 알파벳으로 채운다.
• 알파벳은 26자이지만 행렬은 25칸이므로, I/J를 같은 것으로 한 칸에 채워 넣는다.
  (I/J를 한 칸에 몰아 넣는 이유는 별다른 이유가 있는 것은 아니고 그냥 관습이다.)

 

2. 암호화 규칙 적용

먼저 평문을 두 글자씩 쌍으로 묶어서 아래 규칙을 적용한다.

1. 중복 문자 처리: 같은 문자가 쌍이 되면(예: balloon -> ba, ll, oon), 중간에 'x'와 같은 채움 문자(Filler)를 삽입한다
   (예: ba, lx, lo, on)
2. 동일 행(Row): 두 글자가 같은 가로줄에 있으면, 각각 바로 오른쪽 문자로 치환한다. (끝이면 왼쪽 끝으로 순환)
   (예: ar → RM)
3. 동일 열(Column): 두 글자가 같은 세로줄에 있으면, 각각 바로 아래 문자로 치환한다. (끝이면 위쪽 끝으로 순환)
   (예: mu → CM)
4. 직사각형 규칙: 두 글자가 서로 다른 행과 열에 있으면, 두 글자를 꼭짓점으로 하는 직사각형을 가정하고, 자신의 행에 있으면서 상대방의 열에 위치한 문자로 치환한다.
   (예: hs → BP)

단일 치환 암호는 26개의 알파벳 빈도를 분석하면 되지만 Playfair는 이중 문자 단위로 암호화하므로 26x26=676개의 빈도표를 작성하고 분석해야한다. 따라서 복잡도가 더 증가했다.
(키 공간 자체는 26!에서 25!로 감소했지만 빈도분석에 의해 뚫리므로 이렇게 비교한다.)

 

하지만 여전히 평문의 구조적 특성이 남아있어 해독이 가능한 수준이다. 

---

4. Vigenere Cipher (비즈네르 암호 - 다중 치환 암호)

단일치환암호에서 약점인 빈도분석 방법을 극복하기위한 방법이다.

 

다중치환암호에서는 평문의 각 글자마다 다른 치환 알파벳을 사용하는 방법을 사용한다.

키워드라는 것이 존재해서 키워드 문자가 어떤 알파벳 치환을 할 지를 결정하는 구조이다.

 

먼저 아래와 같은 치환 표가 존재한다.

 

 

그리고 평문 길이에 맞게 키를 반복한다.이후 테이블에 맞게 글자별로 치환하면 암호문이 완성된다.

이 방법을 통해 빈도 분포를 평탄화시켜 빈도분석 공격에 대응할 수 있다.

---

5. Transposition Cipher, Permutation Cipher (전치 암호)

Transposition Cipher는 문자 자체를 바꾸는 치환(substitution)과 달리 문자의 위치만 재배열하는 것이다. 즉 순열(Permutation)이다. 실제 사용되는 문자의 종류가 평문 내에서 바뀌지 않으므로 빈도 분포가 평문과 완전히 동일하다.

 

치환 암호에도 여러가지 방법이 있다.

 

1. Rail Fence Cipher

: 주어진 평문을 지그재그로 쓴 뒤, 행 단위로 읽는 방법이다.

 

예를 들어 평문 "meet me after the toga party"를 암호화한다면 먼저 아래와 같이 지그재그로 쓴다.

이후 이걸 행단위로 적으면 

이게 암호문이 된다.

 

2. Row Transposition Cipher

1. 주어진 평문을 지정된 열 개수에 맞춰 적는다. (평문: attack postponed until two am, 지정 열 개수: 7)
2. 키에 지정된 숫자 순서대로 열을 세로로 읽어나가면 암호문이 된다. (ttna → aptm → tsuo ...)