치환암호 편집하기

'''치환암호'''<!--치환 암호-->(substitution cipher)란 비트, 문자 또는 문자의 블록을 다른 비트, 문자 또는 블록으로 대체하는 방법이다. 즉, 평문의 문자를 다른 문자로 교환하는 규칙이다. '''대체암호'''<!--대체 암호--> 또는 '''환자암호'''<!--환자 암호-->라고도 한다.

==개요==
치환암호는 특정 글자를 다른 글자로 치환함으로써 암호를 생성하는 방법이다. 예를 들어 알파벳 A를 임의로 H로 지정하듯이 특정 문자를 다른 문자로 치환하면 된다. 치환 암호에는 단일치환암호와 다중치환암호라는 두 가지 방식이 있다. 단일치환암호는 '단일문자치환암호'라고도 하며, 항상 문자에 대해서는 같은 문자로 치환하는 방식이다. 예를 들어, 앞서 A를 H로 치환했다면 하나의 키를 통해 [[암호화]]된 문서에서 나타나는 모든 H는 평문의 A가 된다. 반면에 '다중문자치환암호'라고도 불리는 다중치환암호는 하나의 문자가 여러 다른 문자로 바뀔 수 있다. 즉 평문의 A가 H가 될 수도, Y가 될 수도 있다는 말이다. 이 말은 일반적으로 다중치환암호가 단일치환암호 방식보다 더욱 알아내기 어렵다고 생각할 수 있다.

==암호방식==
===단일치환암호===
알파벳에서 숫자(키 값)를 이용해서 다른 알파벳이 되도록 치환시키는 방식이다. 알파벳 26문자를 무작위로 나열한 집합과 원래의 알파벳 26문자를 서로 1대1 대응시킴으로써 암호문을 생성해낸다.<ref>〈[https://jaebworld.tistory.com/5 Simple Substitution Cipher(단일치환암호)]〉, 《티스토리》, 2019-04-20</ref> 단일치환암호 방식은 알파벳의 수가 26개로 한정되있다는 약점이 있어, [[평행이동]], [[빈도분석법]] 등과 같은 방법으로 [[평문]]을 찾을 수 있다.<ref>ITqom, 〈[http://itqomcom.blogspot.com/2018/04/blog-post_14.html 단일치환 암호방식과 다중치환 암호방식]〉, 《개인블로그》, 2018-04-14</ref> 단일치환암호 방식으로는 덧셈암호, 곱셈암호, 아핀암호가 있다.

====덧셈암호====
[[덧셈암호]](Additional Cipher)는 암호학에서 가장 기초가 되는 방법이고, 실제로 시저 암호(Caesar Cipher)라고 많이 알려져 있는 암호 방법이다. 카이사르 암호라고도 불린다. 어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 [[암호화]] 방식이다. 시저라고도 불리는 고대 로마의 정치가이자 군인이었다 율리우스 카이사르는 자신의 장군들과 비밀스런 내용을 주고 받을 때 덧셈암호 방식을 사용했다. 여기에서 '카이사르 암호', '시저 암호'라는 이름이 유래되었다. 덧셈암호의 암호화 함수는 다음과 같다.
 <math>C=(P+K)\,\bmod\,26</math>
예를 들어 key가 10이라고 한다면, a의 치환된 문자는 k가 될 것이다. 덧셈암호에 대한 복호화 함수는
 <math>P=(C-K)\,\bmod\,26</math>
로 나타낼 수 있고, 이 방법은 k의 덧셈 역원을 사용해서 아래와 같이 표현 할 수도 있다.
 <math>P=(C+K^{-1})\,\bmod\,26</math>

====곱셈암호====
[[곱셈암호]](Multiplicative Cipher)는 킷 값을 곱한 값을 이용해 [[암호화]]를 시키는 암호 방법이다. 곱셈암호는 덧셈암호보다 키 공간이 작기 때문에 전수 조사 공격에 더욱 취약하며 빈도수의 특징 또한 나타나기 때문에 통계적인 공격에도 취약하다.<ref>월혼지주, 〈[http://blog.naver.com/PostView.nhn?blogId=darknata&logNo=70094375354 곱셈 암호(Multiplicative Cipher)]〉, 《네이버 블로그》, 2010-09-24</ref>곱셈암호도 [[복호화]]가 가능해야 하므로, 키의 도메인이 덧셈암호보다 작다. 곱셈암호를 위한 키가 되기 위해서는 곱셈 역원이 존재해야 하기 때문이다. 다시 말해 곱셈 암호의 키 도메인은 <math>Z_{26}*</math>가 된다. 곱셈암호의 암호화 함수는

 <math>C=(P \times K)\,\bmod\,26</math>
로 나타낼 수 있으며, 복호화 함수는
 <math>P=(C \times K^{-1})\,\bmod\,26</math>
이처럼 곱셈 역원을 사용해서 나타낼 수 있다.

====아핀암호====
[[아핀암호]](Affine Cipher)는 두 개의 암호법을 합쳐놓은 기법이다. 즉 [[덧셈암호]]와 [[곱셉암호]] 두 가지를 병합하여 구현한다. 그렇기 때문에 키 또한 두 개가 존재한다.<ref>〈[http://egloos.zum.com/eyestorys/v/3544631 Affine Cipher - 아핀 암호]〉, 《이글루스》</ref> 아핀암호는 두 개의 키를 이용하기 때문에 키 도메인 역시 달라진다. 키 도메인을 표현하면 다음과 같다.
 <math>Z_{26}*\times Z_{26}</math>
키 도메인의 크기는 <math>12\times 26=312</math>가 될 것이다. 아핀 변환의 암호화 함수는 아래와 같이 나타난다. K_1 을 먼저 곱하고, K_2 를 곱한다.
 <math>C=(P\times K_1+K_2)\,\bmod\,26</math>
이에 대한 복호화 함수는 덧셈 역원을 먼저 더하고, 곱셈 역원을 곱해준다.
 <math>P=((C-K_2)\times K^{-1}_1)\,\bmod\,26</math>

===다중치환암호===
[[평문]]에서 하나의 알파벳은 여러 알파벳으로 나타낼 수 있다. 단일치환 방식에서 알파벳의 빈도 정보를 파악해서 어느 정도 유추할 수 있는 약점이 있었는데, 이 빈도 정보를 무력화시키는 방법으로 등장했다. 다중치환암호로는 [[자동키암호]], [[플레이페어암호]], [[비즈네르암호]], [[힐암호]]가 있다.
====자동키암호====
[[자동키암호]](Autokey Cipher)는 키에 [[평문]]을 포함한 암호이다. 키는 때로 평문에서 일부 문자를 선택하거나, 주로 짧은 접두 키워드를 평문 앞에 추가하는 일부 자동화된 방식으로 평문으로부터 생성된다. 자동키암호에는 두 가지 방식이 있다. 키 자동키암호(Key-autokey cipher)는 키 스트림의 이전 요소가 키 스트림의 다음 요소를 결정하는 데 사용된다. 텍스트 자동키는 이전 평문이 키 스트림의 다음 요소를 결정하는 데 사용된다.<ref>delliot, 〈[https://delliot.dev/?p=367 (0x02) Autokey Cipher]〉, 《개인블로그》</ref> 자동키암호에서 i번째 문자를 암호화하기 위해서 i-1번째 문자를 임시 키로 사용한다. 플레인텍스트의 문자열을 p1p2p3...로 표현하고 암호텍스트의 문자열을 c1c2c3...으로 표현하는 경우, 관계를 표현하면 다음과 같다.
 <math>P=p1p2p3...\quad C=c1c2c3...</math>
 <math>c_i(P_i+P+{i-1})\,\bmod\,26</math>
단, 이럴 경우 첫 번째의 문자는 사용할 키가 없게 된다. 그래서 첫 문자는 임의의 키인 k를 이용해 <math>p_{0-1}=k</math>로 사용하도록 한다. [[복호화]] 또한 단순하다. 그 관계는 덧셈암호와 마찬가지로 i-1번째의 <math>p_{i-1}</math>을 뺀다.
 <math>p_i=(c_i-P_{i-1})\,\bmod\,26</math>
마찬가지로, 첫 번째 문자에 대해서는 키 k를 사용한다. 자동키암호도 덧셈암호와 마찬가지로 무차별 대입 공격에 매우 취약하다. 다만 통계를 이용한 공격에는 덧셈암호에 비해 비교적 강하다. 같은 문자를 다른 문자로 암호화하기 때문에 문자와 문자의 관계를 숨길 수 있다.

====플레이페어암호====
[[플레이페어암호]](Playfair Cipher)는 영국의 물리학자인 휘트스톤(Charles Wheatstone)과 영국의 수학자 및 지질학자인 플레이페어(John Playfair)가 만든 암호화 방식이다. 하지만, 휘트스톤이 죽고 플레이페어는 이 암호화 방식을 자신의 이름을 본떠 발표했다. 이 암호는 5x5 알파벳 행렬을 이용하고, 킷 값을 사용한다.<ref>Notchicken, 〈[https://jookting.tistory.com/36 플레이페어 암호 (Playfair cipher)]〉, 《티스토리》, 2013-08-08</ref> 플레이페어암호의 암호화 알고리즘은 다음과 같다.
*'''키 제곱(5x5)을 생성''' : 키 사각형은 일반 텍스트를 암호화하기 위한 키 역할을 하는 5x5 알파벳의 격자이다. 25개의 알파벳 각각은 고유해야 하며 알파벳의 한 글자(보통 J)는 테이블에서 생략된다. 평문에 J가 있으면 I로 바뀐다. 키 스퀘어의 초기 알파벳은 순서대로 알파벳의 나머지 문자가 나오는 순서대로 키의 고유 알파벳이다.
*'''일반 텍스트를 암호화하는 알고리즘''' : 일반 텍스트는 두 글자의 쌍으로 나뉜다. 홀수개의 문제가 있으면 마지막 문자에 Z가 추가된다.
5x5 알파벳 격자를 만든 뒤에는 암호화 규칙에 따라서 암호화를 진행한다.

*'''두 글자가 같은 열에 있는 경우''' : 각 글자 아래에 있는 글자를 가져온다. 맨 아래에 있는 경우 맨 위로 이동한다.
*'''두 글자가 모두 같은 줄에 있는 경우''' : 각 글자의 오른쪽으로 글자를 가져간다. 가장 오른쪽에 있는 경우 가장 왼쪽으로 돌아간다.
*'''위의 규칙 중 어느 것도 해당하지 않는 경우''' : 두 글자로 사각형을 만들고 사각형의 가로 반대쪽 모서리에 있는 글자를 사용한다.

====비즈네르암호====
[[비즈네르암호]](Vigenere Cipher)는 가장 오래된 다중치환암호 중 하나이다. 가장 많이 알려진 방식의 비즈네르암호는 카이사르 코드 26개, 즉 26x26 대응 표를 사용한다. 추가로 비즈네르 암호체계에서는 사전에 약속된 키가 필요하다.  비즈네르암호의 장점은 언어의 특성에 따른 통계적인 글자의 빈도수를 숨길 수 있다는 것이다.<ref>〈[http://egloos.zum.com/pmh9960/v/1638413 비즈네르암호]〉, 《이글루스》</ref> 비즈네르암호는 프랑스 외교관이었던 비즈네르에 의하여 1586년에 발표되었다.
비즈네르 암호는 암호문 제작을 위해서 먼저 '비즈네르 표'를 만들어야 한다. 이 '베즈네르 표'는 원문 알파벳 아래에 26가지 암호 알파벳이 나열되어 있다. 암호 알파벳은 한 줄 내려갈 때마다 한 자씩 뒤로 이동하게 되며, 1번 줄은 1칸 이동한 덧셈암호 알파벳과 동일하다. 이런 식으로 2번 줄은 2칸 이동, 3번 줄은 3칸 이동한 암호 알파벳과 같다.

예) 암호 알파벳 4번 사용
* a->E로 대체
* g->K로 대체

암호문 작성 시 한가지 암호 알파벳만 사용하게 되면 보안성이 낮은 알파벳과 동일하여 빈도분석법으로 충분히 해독이 가능하게 된다. 이를 보완하기 위해 키워드(열쇠)를 이용한다. 키워드는 수신자와 송신자가 아무 단어나 선택할 수 있다. 비즈네르암호를 수학적 설명으로 하면 다음과 같다.

A-Z를 0~25의 수로 바꾸고, 26으로 나누어 나머지를 구하는 방법이면 대수학으로 설명된다. 열쇠로 K를 사용하는 비즈네르암호 E는 이렇게 쓸 수 있다.

 <math>C_i=E_k(M_i)=(M_i+K_i)\,\bmod\,26</math>

복호화 D는

 <math>M_i=D_i(C_i)=(C_i-K_i)\,\bmod\,26</math>

여기서 <math>M_1...M_n</math>은 평문이고, <math>C=C_1...Cn</math>은 암호문이다. <math>K=K_1...K_n</math>은 열쇠를 <math>[n/m]</math>만큼 반복해서 얻는다. 여기서 n은 평문의 길이이고, m은 열쇠의 길이다. 예를 들어 평문 <math>M_i</math>가 T이고, 열쇠 <math>K_i</math>가 E이면 각각 <math> {\displaystyle T{\widehat {=}}19}</math>와 <math>{\displaystyle E{\widehat {=}}4}</math>이다. 계산하면

 <math>23=(19+4)\,\bmod\,26</math>

그러므로 암호문 <math>C_i</math>는 <math> {\displaystyle X{\widehat {=}}23}</math>이다. 복호화 암호문 <math>C_i</math>인 <math>{\displaystyle X{\widehat {=}}23}</math>에서 열쇠 <math>K_i</math>인 <math>{\displaystyle E{\widehat {=}}4}</math>를 빼면

 <math>19=(23-4)\,\bmod\,26</math>

로 다시 평문 <math>M_i</math>인 <math>{\displaystyle T{\widehat {=}}19}</math>를 얻을 수 있다.

====힐암호====
[[힐암호]](Hill Cipher)는 행렬을 이용한 치환암호의 일종이다. 1929년 레스터 힐이라는 미국 수학자에 의해 발명되었으며, 단순 치환암호와는 달리 둘 이상의 알파벳을 함께 다른 문자로 바꾸기 때문에 빈도 분석에 쉽게 깨지지 않는다는 특징이 있다. 힐암호 역시 26을 법으로 하는 연산을 바탕으로 한다.<ref>적분의 수학 이야기, 〈[https://math.bab2min.pe.kr/hill 힐 암호]〉, 《개인블로그》</ref> 힐암호는 플레인텍스트를 일정한 길이의 문자열로 나누어 암호화한다. 힐암호에서 사용하는 행렬은 임의의 크기 <math>m\times m</math>의 정사각행렬이다.
 <math>\begin{bmatrix} K_{11} & K_{12} & \cdots & K_{1m} \\ K_{21} & K_{22} & \cdots & K_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ K_{m1} & K_{m2} & \cdots & K_{mm} \end{bmatrix}</math>

위의 행렬 k를 이용해서 암호화를 진행한다. [[복호화]]를 하기 위해서 힐암호에 사용되는 키 k는 곱셈 역원을 가져야 할 필요가 있다. 암호화와 복호화의 관계를 나타내면 다음과 같다.
 <math>C=PK</math>
 <math>P=CK^{-1}</math>

이런 방식으로 암호화는 플레인텍스트를 m길이로 잘라 m열의 행렬을 만든다. 만들어진 플레인텍스트는 행렬에 남는 부분을 보고스 레터(Bogus Letter)로 채운다. 모두 채운 뒤, 키 행렬과 곱해 암호화를 만들 수 있다.

{{각주}}

==참고자료==
* 치토스맨, 〈[https://hjleesm.blog.me/221228856514 (정보보안기사) 치환 암호, 전치 암호]〉, 《네이버 블로그》, 2018-03-14
* ITqom, 〈[http://itqomcom.blogspot.com/2018/04/blog-post_14.html 단일치환 암호방식과 다중치환 암호방식]〉, 《개인블로그》, 2018-04-14
* FlameSlash, 〈[https://ieatt.tistory.com/21 (암호학)2.고전암호학(Traditional Ciphers)-치환 암호(Substitution Cipher)]〉, 《티스토리》, 2016-04-02
* 〈[https://jaebworld.tistory.com/5 Simple Substitution Cipher(단일치환암호)]〉, 《티스토리》, 2019-04-20
* 월혼지주, 〈[http://blog.naver.com/PostView.nhn?blogId=darknata&logNo=70094375354 곱셈 암호(Multiplicative Cipher)]〉, 《네이버 블로그》, 2010-09-24
* 〈[http://egloos.zum.com/eyestorys/v/3544631 Affine Cipher - 아핀 암호]〉, 《이글루스》
* Notchicken, 〈[https://jookting.tistory.com/36 플레이페어 암호 (Playfair cipher)]〉, 《티스토리》, 2013-08-08
* 〈[http://egloos.zum.com/pmh9960/v/1638413 비즈네르암호]〉, 《이글루스》
* 적분의 수학 이야기, 〈[https://math.bab2min.pe.kr/hill 힐 암호]〉, 《개인블로그》
* delliot, 〈[https://delliot.dev/?p=367 (0x02) Autokey Cipher]〉, 《개인블로그》
* 〈[https://librewiki.net/wiki/%EC%B9%B4%EC%9D%B4%EC%82%AC%EB%A5%B4_%EC%95%94%ED%98%B8 카이사르 암호]〉, 《리브레위키》
* 〈[https://ko.wikipedia.org/wiki/%EB%B9%84%EC%A6%88%EB%84%A4%EB%A5%B4_%EC%95%94%ED%98%B8 비즈네르 암호]〉, 《위키백과》
* 〈[https://www.geeksforgeeks.org/playfair-cipher-with-examples/ Playfair Cipher with Examples]〉, 《geeksforgeeks》

==같이 보기==
* [[전치암호]]
* [[대칭키]]

{{암호 알고리즘|검토 필요}}