[암호학] 2. 고전암호학(Traditional Ciphers) - 치환 암호(Substitution Cipher)

1. 정의

치환 암호(Substitution Cipher)는 특정 글자를 다른 글자로 치환함으로서 암호를 생성하는 방법이다. 예를 들어 알파벳 A를 임의로 H로 지정하듯이 특정 문자를 다른 문자로 치환하면 된다. 치환 암호에는 크게 두 가지 방법이 있는데, 단일 문자 치환(Monoalphabetic Cipher)과 다중 문자 치환(Polyalphabetic Cipher)가 있다. Monoalphabetic은 항상 한 문자에 대해서는 같은 문자로 치환 되는 것이다. 예를 들어, 앞서 A를 H로 치환했다면, 하나의 key를 통해 암호화 된 문서에서 나타나는 모든 H는 Plaintext의 A가 된다. 반면에 Polyalphabetic에서는 하나의 문자가 여러 다른 문자로 바뀔 수 있다. 즉 Plaintext의 A가 H가 될 수도, Y가 될 수도 있다는 말이다. 이 말은 일반적으로 Polyalphabetic이 Monoalphabetic 방법보다 더욱 알아내기 어렵다고 생각할 수 있다.

2. 단일 문자 치환(Monoalphabetic Cipher)

1) 덧셈 암호(Additional Cipher)

가장 암호학에서 기초가 되는 방법이고, 실제로 Caesar Cipher라고 우리말로 시저 암호라고 많이 알려져 있는 암호 방법이다.

 

 

위의 표처럼 앞으로 Plaintext의 문자를 소문자, 그리고 Ciphertext의 문자를 대문자로 쓰자. 그리고 각 알파벳이 대표하는 숫자는 가장 아랫줄에서 나타내고 있다. 즉, 알파벳의 순서에 맞추어 각 알파벳을 의 원소에 대응시키는 것이라고 생각하면 된다. 알파벳 이외에 숫자나 또 다른 문자를 추가하고 싶다면, 대응되는 원소를 늘리면 되므로, 집합을 더 크게 잡아주면 된다.

 

덧셈 암호에서는 원래 문자의 값에 key를 더해 그에 대응하는 문자로 치환하는 방법으로 암호를 만든다. key의 값을 k라 하면, 암호화 함수는 다음과 같다.

 

예를 들어, key가 10이라고 한다면, a의 치환된 문자는 K가 될 것이다.

Addtivie Cipher에 대한 복호화 함수는

 

 

로 나타낼 수 있고, 이 방법은 k의 Additive Inverse를 사용해서 아래와 같이 표현 할 수도 있다. 

 

2) 곱셈 암호(Multiplicative Cipher)

덧셈 암호에서 암호화를 위해 원래 문자에 key 값을 더해 암호를 생성했다면, 곱셈 암호에서는 원래 문자에 key를 곱해서 생성한다. 단, 곱셈 암호 또한 복호화가 가능해야하므로, Key의 Domain이 덧셈 암호보다 작다. 곱셈 암호를 위한 key가 되기 위해서는 Muliiplicative Inverse가 존재해야 하기 때문이다. 다시 말해 곱셈 암호의 Key Domain은

가 된다. 참고로,

 

 

 이다. 곱셈 암호의 암호화 함수는

 

 

로 나타낼 수 있으며, 복호화 함수는

 

 

이처럼 Multiplicative Inverse를 사용해서 나타낼 수 있다. 

 

3) 아핀 암호(Affine Cipher)

아핀 암호는 덧셈 암호와 곱셈 암호를 합쳐 생성한 방법이다. 즉 Multiplicative key와 Addictive key의 쌍을 이용해 key를 생성한다. K=(k1, k2)처럼 나타낼 수 있고, 보통 k1이 Multiplicate key, k2가 Addictive key를 말한다. 두 개의 key를 이용하기 때문에 Key Domain 역시 달라진다. 그 Key Domain을 표현하면 다음과 같다.

 

 Key Domain의 크기는 12X26=312가 될 것이다.

 

아핀 변환의 암호화 함수는 아래와 같이 나타난다. k1을 먼저 곱하고, k2를 곱한다.

 

 

이에 대한 복호화 함수는 Addictive Inverse를 먼저 더하고, Multiplicative Inverse를 곱해준다.

 

* Atbash Cipher

 

 

3. 복수 문자 치환(Polyalphabetic Cipher)

1) 자동 키 암호(Autokey Cipher)

가장 간단한 Polyalphabetic cipher로 Addictive Cipher와 그 방식이 비슷하다. 다만, Addictive Cipher는 그 Key가 고정되어 있는데 반해, Autokey Cipher는 그렇지 않다. Autokey Cipher에서 i번째 문자를 암호화하기 위해서 i-1번째 문자를 임시 key로 사용한다. Plaintext의 문자열을 p1p2p3...로 표현하고 Ciphertext의 문자열을 c1c2c3...으로 표현하는 경우, 관계를 표현하면 다음과 같다.

 

단, 이럴 경우 첫번째의 문자는 사용할 key가 없게 된다. 그래서 첫 문자는 임의의 key인 k를 이용해 p_0-1=k로 사용하도록 한다.

복호화 또한 단순하다. 그 관계는 Addictive Ciper와 마찬가지로 i-1번째의 p_i-1을 뺀다.

마찬가지로, 첫 번쨰 문자에 대해서는 key k를 사용한다. Autokey Cipher도 Addictive Cipher와 마찬가지로 Brute-force Attack에 매우 취약하다. 다만 Addictive Cipher보다 조금 나은 점이 있다면, 통계를 이용한 Attack에는 비교적 강하다. 같은 문자를 다른 문자로 암호화하기 때문에 문자와 문자의 관계를 숨길 수 있다.

2) 플레이페어 암호(Playfair Cipher)

Playfair Cipher는 세계 1차 대전 당시 영국 육군이 실제로 사용하던 암호이다. Playfair Cipher의 경우 25개의 알파벳으로 구성된 5X5 Matrix를 이용해서 암호화/복호화를 진행한다. 26개의 알파벳에 25칸은 하나의 알파벳이 부족하므로 보통 I와 J를 같은 문자로 보거나 Q와 Z를 같은 문자로 본다. Playfair Cipher의 암호화 Table의 하나의 예는 다음과 같다.

Playfair Table을 이용해서 암호화 하기 이전에, 문자열에 같은 문자가 있으면 그 사이에 Bogus letter를 넣어준다. 모두 넣어준 뒤에 문자열의 길이가 홀수라면, 제일 끝에 Bogus Letter를 넣어 문자열의 길이가 짝수가 되도록 한다. 이 과정이 끝난 뒤에 본격적으로 암호화를 시작한다. Playfair Cipher에서는 두 글자씩 짝을 지어 암호화를 한다. 우선, 한 쌍의 두 문자가 같은 행에 있는지 살펴보고, 두 문자가 같은 행인 경우 대응 되는 문자를 그 바로 오른쪽 문자로 대치시킨다.(가장 오른쪽의 문자는 1열의 문자로 대치한다.) 그렇지 않고 두 문자가 같은 열에 존재하는 경우, 대응 되는 두 문자를 각각 바로 아래 글자로 대치한다.(마찬가지로 가장 아래의 문자는 1행의 문자로 대치한다.) 두 경우가 모두 아닌 경우, 두 문자 각각의 행에서 자신과 다른 문자와 같은 열에 있는 문자를 선택해 치환한다. 좀 더 이해하기 쉽도록 예를 들어보자.

이런 방식으로 진행되므로, 복호화는 암호화의 반대 방법으로 진행하면 된다. Playfair 암호의 장점은 Brute-force Attack이 어렵다는 것이다. Key의 Domain이 25!이 된다. 그 이유는 Matrix의 Size가 5X5이므로, 모든 경우를 생각하면 25!이 되기 때문이다. 또한 Polyalphabetic Cipher이므로 같은 문자가 서로 다른 문자로 치환되어 문자간의 관계를 쉽게 숨길 수 있다. 다만, 두 문자를 짝을 이루어 암호화를 진행하므로, Digram의 Frequency는 숨기기 어렵다. 이로 인해 Digram Frequency를 기반으로 한 Cipher-text Attack에는 취약하다.

3) 비즈네르 암호(Vigenere Cipher)

Vigenere Cipher는 16세기 프랑스 수학자, Blaise de Vigenere에 의해 고안된 방법이다. Vigenere Cipher에서는 Key Stream에서 길의 m의 문자열을 만들어 반복해 사용하는 방법을 이용한다. 즉 임의의 문자열을 만들어 그것을 암호화의 Key로 사용하는 셈이다. 예를 들어 happy birthday라는 평문을 CAKE라는 key로 암호화한다고 가정해보자.

위와 같이 Plaintext의 Value의 Key의 Value를 더해 26으로 나누어 Ciphertext를 구성한다. Key인 CAKE는 반복적으로 사용한다.

이를 좀 더 쉽게 Vigenere Table을 이용할수도 있다. Vigenere Table은 다음과 같다.

Table의 사용법은 Plaintext의 현재 문자와 Key의 현재 문자를 통해서 Table의 문자를 찾는다. 찾아진 문자가 Cipehrtext의 문자가 될 것이다. 복호화의 경우에는 암호화와는 반대로 Cipertext와 Key를 이용해 Plaintext를 찾을 수 있을 것이다. Viegenere Cipher에서 Key의 길이 m이 1인 경우는 Addictive Cipher와 동일하게 생각 할 수 있다. Vigenere Cipher 또한 Brute-force Attack에 강하며, 문자간의 관계를 숨기기 때문에 Attack이 쉽지 않다. 다만, Kasiski test라는 방법을 통해서 Vigenere Cipher의 Key를 유추할 수 있는 방법이 있다.

*Kasiski text

4) 힐 암호(Hill Cipher)

Hill Cipher는 Lester S. Hill에 의해서 고안된 암호이다. Hill Cipher는 행렬을 key로 이용하며, Plaintext를 일정한 길이의 문자열로 나누어 암호화한다. Hill Cipher에서 사용하는 행렬은 임의의 크기 mXm의 정사각행렬이다.

위의 행렬 K를 이용해서 암호화를 진행한다. 복호화를 하기 위해서 Hill Cipher에 사용되는 key K는 multiplicative inverse를 가져야 할 필요가 있다. Encrypt와 Decrypt의 관계를 나타내면 다음과 같다.(K^-1은 단순 역행렬이 아니라 multiplicative inverse를 의미한다.)

이런 방식으로 암호화는 Plaintext를 m길이로 잘라 m열의 행렬을 만든다. 만들어진 Plaintext의 행렬에 남는 부분은 Bogus Letter로 채운다. 모두 채운 뒤, Key Matrix와 곱해 암호화를 만들 수 있다. 이 경우에 Hill Cipher의 Key의 Domain은 무려 26^(mXm)이 된다. 하지만, 실제 Domain에는 multiplicative inverse가 존재하지 않는 행렬이 있으므로, 이를 제외해 26^(mXm)보다는 조금 작을것이다. 다만 Hill Cipher는 Known-Plaintext Attack에는 취약할 수 있다. P가 multiplicative inverse를 가지고 있는 경우, K=P^(-1)C를 이용해 Key Matrix를 유추할 수 있기 때문이다.