단순 치환 암호

Simple substitution cipher. 고전암호 기법, 더 나아가서는 치환암호단자 치환 암호의 한 종류로 평문에 쓰인 글자가 암호문에 쓰인 문자가 항상 일대일대응되는 암호이다. 이 대응은 전체 평문에 걸쳐 적용되기 때문에 평문에서의 문자 분포와 암호문에서의 문자 분포 역시 일대일로 대응하고, 따라서 빈도분석에 매우 취약하다.

쉬운 예로 글자를 각각 다음 글자로 대응시켜서 (맨 마지막 글자는 맨 처음 글자로 대응) 암호문을 만드는 것을 들 수 있다. 이 경우, ATTACK AT DAWN이라는 평문은 BUUBDL BU EBXO가 된다. 당연히 암호를 풀려면 반대로, 즉 글자를 각각 이전 글자(나 맨 마지막 글자)로 대응시키면 된다.

수학적으로 말하면, 단순 치환 암호의 키 K는 그 크기가 사용 가능한 문자의 갯수와 같은 대칭군의 원소(즉, 순열)로, 암호화 E_K와 복호화 D_K는 다음과 같이 기술된다:

E_K(P) = K(P)
D_K(C) = K^{-1}(C)

당연한 얘기이지만 모든 키에는 그 키와 반대 역할(암호화와 복호화를 뒤집는)을 하는 키 K^{-1}가 존재하며, 암호화를 (같거나 서로 다른 키로) 몇 번이고 반복해도 실질적으로는 하나의 키로 암호화하는 것과 차이가 없다(E_{K_1} * E_{K_2} = E_{K_1 * K_2}). 이는 키가 을 이루기 때문에 생기는 자연스러운 현상이다.

종류

단순 치환 암호는 고전 암호 중에서도 특히 오래된 부류로, 임의의 대응을 사용할 수 있는 구조임에도 불구하고 편의를 위해 대응에 큰 제약을 가하여 만드는 경우가 많다(사실 몰랐다고 해야 옳은 일이겠지만). 덕택에 깨기 쉬운 암호 주제에 종류는 엄청나게 많은데, 몇 가지 주요한 예만 나열한다. (아래에서 n은 알파벳의 갯수이다.)

이름 실제 순열
카이사르 암호 k \in [0,n) \footnotesize \begin{pmatrix} 0 & \cdots & i & \cdots & n-1 \\ k & \cdots & (i+k)\mod n & \cdots & (k-1)\mod n \end{pmatrix}
ROT13 (그따위 거 없다) \footnotesize \begin{pmatrix} 0 & 1 & \cdots & 24 & 25 \\ 13 & 14 & \cdots & 11 & 12 \end{pmatrix}
아트바쉬(Atbash) 암호 (있을까보냐) \footnotesize \begin{pmatrix} 0 & 1 & \cdots & n-2 & n-1 \\ n-1 & n-2 & \cdots & 1 & 0 \end{pmatrix}
아핀 암호 a \in [1,n),~b \in [0,n)
(단, \gcd(a,n)=1)
\footnotesize \begin{pmatrix} 0 & \cdots & i & \cdots & n-1 \\ b & \cdots & (ai+b)\mod n & \cdots & (b-a)\mod n \end{pmatrix}

공격

앞에서 설명했듯, 평문의 문자 분포를 알고 있다면 (예를 들어 영어에서는 가장 많이 나오는 글자가 보통 E, T, A 순서이다) 암호문의 문자 분포를 보고 대응을 추측하는 게 가능하다(빈도분석). 특히 공백도 포함되어 있을 경우 공백의 빈도가 다른 문자보다 훨씬 높고, 낱말 길이로부터 추가적인 정보를 얻을 수 있기 때문에 훨씬 빠르게 암호를 풀어 낼 수 있다.

의도적으로 평문의 문자 분포가 왜곡되어 있을 경우에도 (예를 들어 Q, X, Z 따위가 많이 나오는 문장이라거나), 평문의 국지적인 패턴이 보존되기 때문에 여전히 어렵지 않게 푸는 것이 가능하다. 이를테면 아무리 문자 분포를 왜곡해도 "the"라는 3-그램 문자열은 자주 나타날 것이며, "the" 같이 자주 나오는 문자열을 아예 쓰지 않는다고 하더라도 "ABBCADB"와 같은 패턴이 하나라도 있을 경우 몇 개의 문자를 특정할 수 있다1).

1) 영어에서 이런 패턴을 가진 낱말은 attract와 osseous 밖에 없다.

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-09-22 01:33 | 작성자 lifthrasiir