차이점

이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.

@@ 줄 1: / 줄 1: @@
+====== 단순 치환 암호 ======
+Simple substitution cipher. [[고전암호]] 기법, 더 나아가서는 [[치환암호]] 및 [[단자치환암호]]의 한 종류로 [[평문]]에 쓰인 글자가 [[암호문]]에 쓰인 문자가 항상 [[일대일대응]]되는 암호이다. 이 대응은 전체 평문에 걸쳐 적용되기 때문에 평문에서의 문자 분포와 암호문에서의 문자 분포 역시 일대일로 대응하고, 따라서 [[빈도분석]]에 매우 취약하다.
+쉬운 예로 글자를 각각 다음 글자로 대응시켜서 (맨 마지막 글자는 맨 처음 글자로 대응) 암호문을 만드는 것을 들 수 있다. 이 경우, ''ATTACK AT DAWN''이라는 평문은 ''BUUBDL BU EBXO''가 된다. 당연히 암호를 풀려면 반대로, 즉 글자를 각각 이전 글자(나 맨 마지막 글자)로 대응시키면 된다.
+수학적으로 말하면, 단순 치환 암호의 키 $$K$$는 그 크기가 사용 가능한 문자의 갯수와 같은 [[대칭군]]의 원소(즉, [[순열]])로, 암호화 $$E_K$$와 복호화 $$D_K$$는 다음과 같이 기술된다:
+<.center>$$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$$은 알파벳의 갯수이다.)
+^  이름  ^  키  ^  실제 순열  ^
+|  **[[Julius Caeser|카이사르]] 암호**  |  $$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"라는 [[n-그램|3-그램]] 문자열은 자주 나타날 것이며, "the" 같이 자주 나오는 문자열을 아예 쓰지 않는다고 하더라도 "ABBCADB"와 같은 패턴이 하나라도 있을 경우 몇 개의 문자를 특정할 수 있다((영어에서 이런 패턴을 가진 낱말은 attract와 osseous 밖에 없다.)).
+{{tag>암호학}}

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