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

1. 정의

전치 암호(Transposition Cipher)는 치환 암호(Substitution Cipher)와 다르게 특정 글자를 다른 글자로 치환하지 않는다. 그 대신 글자들의 순서를 변경하여 암호화한다. 예를 들어 Plaintext의 첫 글자와 열 번째 글자를 바꾸고, 두 번째 글자를 다섯 번째와 바꿔서 암호화할 수 있다. 이렇게 단순히 순서를 변경하는 것만으로도, Ciphertext로부터 Plaintext를 한눈에 알기는 어려워진다. Transposition Cipher는 이러한 점을 이용해서 위치 변경의 규칙을 정하고, 그 규칙에 맞추어 Plaintext를 암호화한다. 복호화는 어렵지 않다. 암호화한 규칙을 역으로 Ciphertext로부터 Plaintext를 찾을 수 있을 것이다. 간단히, Transpositon Chipher는 문자들을 재순서한다고 생각하면 된다.

2. Keyless Transposition Cipher

간단한 Transposition Cipher로, 상호간에 Key를 정하지 않고 사용할 수 있는 암호이다. Transposition을 하는 규칙만으로 암호화/복호화가 가능한 Cipher이다.

1) Rail Fence Cipher

Plaintext의 문자를 n개의 rail에 한글자씩 놓는 방법으로 Transposition을 수행하는 암호이다. n개의 rail에 한글자씩 두고, 한 rail씩 적는다. 이렇게 한줄씩 적어 Ciphertext를 완성할 수 있다. 예를 들어보자. 3개의 rail에 Plaintext는 We are discovered flee at once라고 해보자. 아래 그림과 같이 암호화를 수행할 수 있다.

이를 Ciphertext로 변환하면, WECRLTEERDSOEEFEAOCAIVDEN이 될 것이다. Decrypt시에는 Ciphertext를 위와 같은 rail에 적는 방법을 통해서 가능하다.

2) Decide the table's the number of columns

이 방법은 Cipher에 사용될 Table의 Column 수를 정해두고, Encrypt하는 방법이다. Column의 수를 정하고, 평문을 Column 수로 계속 나누어 Table에 한 row씩 쓴다. 작성된 Table을 Column 순서대로 읽자. 이를 통해서 Ciphertext를 생성할 수 있다. 그 예로 Meet me at the park라는 Plaintext를 Encrypt해보자.

위의 Table을 통해서 MMTAEEHREAEKTTP라는 Ciphertext가 수행된다. Decrypt하는 과정은 위의 Table을 Column순으로 채우면 된다. Column의 수를 미리 정해두었으므로, Ciphertext의 전체길이를 Column 수로 나누어 그 개수만큼 하나의 Column에 쓰고, 작성된 Table을 Row순서로 읽으면 Plaintext를 완성할 수 있다.

3. Keyed Transposition Cipher

앞서 Keyless Transposition Cipher는 보통 plaintext를 한 row씩 쓰고 한 column씩 읽듯 쓰는 방법과 읽는 방법을 변경해서 Ciphertext를 완성시켰다. Keyed Transpositon Cipher에서는 이와 달리 Plaintext를 일정한 조각으로 나누어 나누어진 조각을 특정한 규칙에 맞게 글자간 순서를 변경하는 것으로 수행된다. 이 때 나눠진 조각을 Block이라하며, 결국 Plaintext를 Block단위로 나누어 Block에서 Permutation을 수행하게 되는 것이다.

예를 들어 Enemy attacks Tonight라는 문장을 Encrypt해보자. Block의 크기는 5이고, Block의 Permutation Key는 31452라고 해보자. Key는 아래와 같은 그림으로도 나타낸다. 한 글자가 부족하므로 Plaintext의 마지막에 Bogus Character X를 이용하자.

이를 해석해보면, 각 Block에서 3번째 글자를 가장먼저 쓰고, 1번째 글자를 두번째로, 4번째 글자를 세번째로 쓰면서 Encrypt를 진행하라는 말이다. 즉 Enemy라는 단어는 EEMYN으로 Encrypt될 것이다. 앞선 예시의 문장은 EEMYNTAACKTKONSHITXG라는 Ciphertext가 된다. Decrypt를 위한 Key의 생성은 위의 표에서 첫 번째 row가 12345가 되도록 수정하자. 아래의 Decrypt Key 그림을 통해서 다시 설명해보면,

2번째 글자가 1번째 글자가 되고, 5번째 글자가 2번째 글자가 되고 하는 방식이 되는 것이다. 즉 EEMYN이라는 Block은 ENEMY가 되는 것이다. 이 때 우리가 사용한 Decrypt Key는 25134가 된다. 이러한 방식으로 Key를 사용해서 Transposition Cipher를 수행할 수 있다.

4. Combined Transposition Cipher

이 방법은 단순히 앞선 두개의 방법을 합쳐서 만들어진 Cipher이다. Keyless Transpositon Cipher의 Table의 Column을 결정해 Table을 생성한 뒤, Table Column간에 Keyed Transposition Cipher의 Key를 통해서 Permutate한다. 그리고 완성된 Table을 Column by Column의 순서로 읽어 Ciphertext를 완성한다.

예제로 위의 Enemy attacks tonight을 Encrypt해보자. 사용되는 key는 마찬가지로 31452로 하며, Block size는 5이다. Block Size가 5이기 때문에 자동적으로 Column의 수도 5가 된다. 우선은 Plaintext를 Column이 5인 Table에 채워넣자. 한글자가 부족하므로 Bogus Character X를 끝에 집어넣었다.

완성된 기존의 Table에서 31452 Key를 이용해 Column간 순서를 Permute했다. 이후에 완성된 Table을 Column by Column 순서로 읽으면 된다. 즉 Ciphertext는 ETTHEAKIMAOTYCNXNTSG가 된다. Decrypt의 경우에는 Column by Column 순서로 Table에 Ciphertext를 채워넣고, Decrypt Key인 25134를 이용해 Table의 Column을 Permute한다. 완성된 Table을 Row by Row로 읽으면 Plaintext를 완성할 수 있다.