치환암호

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

개요

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

종류

단일치환암호

알파벳에서 숫자(키 값)를 이용해서 다른 알파벳이 되도록 치환시키는 방식이다. 알파벳 26문자를 무작위로 나열한 집합과 원래의 알파벳 26문자를 서로 1대1 대응시킴으로써 암호문을 생성해낸다. 단일치환암호 방식은 알파벳의 수가 26개로 한정되있다는 약점이 있어, 평행이동, 빈도분석법 등과 같은 방법으로 평문을 찾을 수 있다. 단일치환암호 방식으로는 덧셈암호, 곱셈암호, 아핀암호가 있다.

덧셈암호

덧셈암호(Additional Cipher)는 암호학에서 가장 기초가 되는 방법이고, 실제로 시저 암호(Caesar Cipher)라고 많이 알려져 있는 암호 방법이다. 카이사르 암호라고도 불린다. 어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식이다. 시저라고도 불리는 고대 로마의 정치가이자 군인이었다 율리우스 카이사르는 자신의 장군들과 비밀스런 내용을 주고 받을 때 덧셈암호 방식을 사용했다. 여기에서 '카이사르 암호', '시저 암호'라는 이름이 유래되었다. 덧셈암호의 암호화 함수는 다음과 같다.

$C=(P+K)\,{\bmod {\,}}26$

예를 들어 key가 10이라고 한다면, a의 치환된 문자는 k가 될 것이다. 덧셈암호에 대한 복호화 함수는

$P=(C-K)\,{\bmod {\,}}26$

로 나타낼 수 있고, 이 방법은 k의 덧셈 역원을 사용해서 아래와 같이 표현 할 수도 있다.

$P=(C+K^{-1})\,{\bmod {\,}}26$

곱셈암호

곱셈암호(Multiplicative Cipher)는 킷 값을 곱한 값을 이용해 암호화를 시키는 암호 방법이다. 곱셈암호는 덧셈암호보다 키 공간이 작기 때문에 전수 조사 공격에 더욱 취약하며 빈도수의 특징 또한 나타나기 때문에 통계적인 공격에도 취약하다.곱셈암호도 복호화가 가능해야 하므로, 키의 도메인이 덧셈암호보다 작다. 곱셈암호를 위한 키가 되기 위해서는 곱셈 역원이 존재해야 하기 때문이다. 다시 말해 곱셈 암호의 키 도메인은 $Z_{26}*$가 된다. 곱셈암호의 암호화 함수는

$C=(P\times K)\,{\bmod {\,}}26$

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

$P=(C\times K^{-1})\,{\bmod {\,}}26$

이처럼 곱셈 역원을 사용해서 나타낼 수 있다.

아핀암호

아핀암호(Affine Cipher)는 두 개의 암호법을 합쳐놓은 기법이다. 즉 덧셈암호와 곱셉암호 두 가지를 병합하여 구현한다. 그렇기 때문에 키 또한 두 개가 존재한다. 아핀암호는 두 개의 키를 이용하기 때문에 키 도메인 역시 달라진다. 키 도메인을 표현하면 다음과 같다.

$Z_{26}*\times Z_{26}$

키 도메인의 크기는 $12\times 26=312$가 될 것이다. 아핀 변환의 암호화 함수는 아래와 같이 나타난다. K_1 을 먼저 곱하고, K_2 를 곱한다.

$C=(P\times K_{1}+K_{2})\,{\bmod {\,}}26$

이에 대한 복호화 함수는 덧셈 역원을 먼저 더하고, 곱셈 역원을 곱해준다.

$P=((C-K_{2})\times K_{1}^{-1})\,{\bmod {\,}}26$

다중치환암호

평문에서 하나의 알파벳은 여러 알파벳으로 나타낼 수 있다. 단일치환 방식에서 알파벳의 빈도 정보를 파악해서 어느 정도 유추할 수 있는 약점이 있었는데, 이 빈도 정보를 무력화시키는 방법으로 등장했다. 다중치환암호로는 자동키암호, 플레이페어암호, 비즈네르암호, 힐암호가 있다.

자동키암호

자동키암호(Autokey Cipher)는 키에 평문을 포함한 암호이다. 키는 때로 평문에서 일부 문자를 선택하거나, 주로 짧은 접두 키워드를 평문 앞에 추가하는 일부 자동화된 방식으로 평문으로부터 생성된다. 자동키암호에는 두 가지 방식이 있다. 키 자동키암호(Key-autokey cipher)는 키 스트림의 이전 요소가 키 스트림의 다음 요소를 결정하는 데 사용된다. 텍스트 자동키는 이전 평문이 키 스트림의 다음 요소를 결정하는 데 사용된다. 자동키암호에서 i번째 문자를 암호화하기 위해서 i-1번째 문자를 임시 키로 사용한다. 플레인텍스트의 문자열을 p1p2p3...로 표현하고 암호텍스트의 문자열을 c1c2c3...으로 표현하는 경우, 관계를 표현하면 다음과 같다.

$P=p1p2p3...\quad C=c1c2c3...$
$c_{i}(P_{i}+P+{i-1})\,{\bmod {\,}}26$

단, 이럴 경우 첫 번째의 문자는 사용할 키가 없게 된다. 그래서 첫 문자는 임의의 키인 k를 이용해 $p_{0-1}=k$로 사용하도록 한다. 복호화 또한 단순하다. 그 관계는 덧셈암호와 마찬가지로 i-1번째의 $p_{i-1}$을 뺀다.

$p_{i}=(c_{i}-P_{i-1})\,{\bmod {\,}}26$

마찬가지로, 첫 번째 문자에 대해서는 키 k를 사용한다. 자동키암호도 덧셈암호와 마찬가지로 무차별 대입 공격에 매우 취약하다. 다만 통계를 이용한 공격에는 덧셈암호에 비해 비교적 강하다. 같은 문자를 다른 문자로 암호화하기 때문에 문자와 문자의 관계를 숨길 수 있다.

플레이페어암호

플레이페어암호(Playfair Cipher)는 영국의 물리학자인 휘트스톤(Charles Wheatstone)과 영국의 수학자 및 지질학자인 플레이페어(John Playfair)가 만든 암호화 방식이다. 하지만, 휘트스톤이 죽고 플레이페어는 이 암호화 방식을 자신의 이름을 본떠 발표했다. 이 암호는 5x5 알파벳 행렬을 이용하고, 킷 값을 사용한다. 플레이페어암호의 암호화 알고리즘은 다음과 같다.

• 키 제곱(5x5)을 생성 : 키 사각형은 일반 텍스트를 암호화하기 위한 키 역할을 하는 5x5 알파벳의 격자이다. 25개의 알파벳 각각은 고유해야 하며 알파벳의 한 글자(보통 J)는 테이블에서 생략된다. 평문에 J가 있으면 I로 바뀐다. 키 스퀘어의 초기 알파벳은 순서대로 알파벳의 나머지 문자가 나오는 순서대로 키의 고유 알파벳이다.
• 일반 텍스트를 암호화하는 알고리즘 : 일반 텍스트는 두 글자의 쌍으로 나뉜다. 홀수개의 문제가 있으면 마지막 문자에 Z가 추가된다.

5x5 알파벳 격자를 만든 뒤에는 암호화 규칙에 따라서 암호화를 진행한다.

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

비즈네르암호

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

예) 암호 알파벳 4번 사용

• a->E로 대체
• g->K로 대체

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

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

$C_{i}=E_{k}(M_{i})=(M_{i}+K_{i})\,{\bmod {\,}}26$

복호화 D는

$M_{i}=D_{i}(C_{i})=(C_{i}-K_{i})\,{\bmod {\,}}26$

여기서 $M_{1}...M_{n}$은 평문이고, $C=C_{1}...Cn$은 암호문이다. $K=K_{1}...K_{n}$은 열쇠를 $[n/m]$만큼 반복해서 얻는다. 여기서 n은 평문의 길이이고, m은 열쇠의 길이다. 예를 들어 평문 $M_{i}$가 T이고, 열쇠 $K_{i}$가 E이면 각각 ${\displaystyle T{\widehat {=}}19}$와 ${\displaystyle E{\widehat {=}}4}$이다. 계산하면

$23=(19+4)\,{\bmod {\,}}26$

그러므로 암호문 $C_{i}$는 ${\displaystyle X{\widehat {=}}23}$이다. 복호화 암호문 $C_{i}$인 ${\displaystyle X{\widehat {=}}23}$에서 열쇠 $K_{i}$인 ${\displaystyle E{\widehat {=}}4}$를 빼면

$19=(23-4)\,{\bmod {\,}}26$

로 다시 평문 $M_{i}$인 ${\displaystyle T{\widehat {=}}19}$를 얻을 수 있다.

힐암호

힐암호(Hill Cipher)는 행렬을 이용한 치환암호의 일종이다. 1929년 레스터 힐이라는 미국 수학자에 의해 발명되었으며, 단순 치환암호와는 달리 둘 이상의 알파벳을 함께 다른 문자로 바꾸기 때문에 빈도 분석에 쉽게 깨지지 않는다는 특징이 있다. 힐암호 역시 26을 법으로 하는 연산을 바탕으로 한다. 힐암호는 플레인텍스트를 일정한 길이의 문자열로 나누어 암호화한다. 힐암호에서 사용하는 행렬은 임의의 크기 $m\times m$의 정사각행렬이다.

${\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}}$

위의 행렬 k를 이용해서 암호화를 진행한다. 복호화를 하기 위해서 힐암호에 사용되는 키 k는 곱셈 역원을 가져야 할 필요가 있다. 암호화와 복호화의 관계를 나타내면 다음과 같다.

$C=PK$
$P=CK^{-1}$

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

참고자료

• 치토스맨, 〈(정보보안기사) 치환 암호, 전치 암호〉, 《네이버 블로그》, 2018-03-14
• ITqom, 〈단일치환 암호방식과 다중치환 암호방식〉, 《개인블로그》, 2018-04-14
• FlameSlash, 〈(암호학)2.고전암호학(Traditional Ciphers)-치환 암호(Substitution Cipher)〉, 《티스토리》, 2016-04-02
• 〈Simple Substitution Cipher(단일치환암호)〉, 《티스토리》, 2019-04-20
• 월혼지주, 〈곱셈 암호(Multiplicative Cipher)〉, 《네이버 블로그》, 2010-09-24
• 〈Affine Cipher - 아핀 암호〉, 《이글루스》
• Notchicken, 〈플레이페어 암호 (Playfair cipher)〉, 《티스토리》, 2013-08-08
• 〈비즈네르암호〉, 《이글루스》
• 적분의 수학 이야기, 〈힐 암호〉, 《개인블로그》
• delliot, 〈(0x02) Autokey Cipher〉, 《개인블로그》
• 〈카이사르 암호〉, 《리브레위키》
• 〈비즈네르 암호〉, 《위키백과》
• 〈Playfair Cipher with Examples〉, 《geeksforgeeks》

같이 보기

• 전치암호
• 대칭키

이 치환암호 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반