[Crypto] 고전 암호와 현대 암호 알아보기

 

** 드림핵 cryptography 로드맵 기반으로 작성

 

 

고전 암호?

• 컴퓨터와 같은 고성능 연산 장치가 발명되기 전에, 비교적 간단한 기계와 손 등으로 암복호화를 수행하던 암호
• 대부분 컴퓨터를 사용하면 쉽게 복호화되기 때문에 현대에는 사용되지 않음
• 치환(Substitution) : 평문의 문자를 다른 문자로 바꾸는 것
• 전치 (Transposition) : 평문 문자들의 위치를 바꾸는 것

단순한 고전암호는 한 가지 원이만을 사용하는 치환 암호 또는 전치 암호이고, 복잡한 고전 암호는 두 원리를 모두 사용!

치환 암호는 여기서 단일 문자 치환 암호 (Monoalphabetic substitution cipher) 와 다중 문자 치환 암호 (Polyalphabetic substitution cipher) 로 나누어진다.

 

 

단일 문자 치환 암호 (Monoalphabetic substitution cipher)

• 평문의 각 문자를 약속된 다른 문자로 치환하는 암호
  • 복호화를 위해 치환의 대응 관계는 일대일 대응
  • 평문의 'A'가 암호문의 'B'로 치환된다면, 평문의 다른 어떤 문자도 'B'로 치환되지 않음

1) 카이사르 암호

• 단일 문자 치환 암호의 대표적인 예: 기원전 44년 줄리어스 카이사르가 사용한 카이사르 암호(Caesar cipher)

카이사르 암호는 평문의 각 알파벳을 정해진 횟수만큼 다음 순서에 해당하는 알파벳으로 치환한다.

이때 Z의 다음 알파벳의 A로 정의됨

 

이를 복호화 할때는 암호문의 각 문자를 다시 정해진 횟수만큼 이전 알파벳으로 치환시켜 평문을 구한다.

송신자와 수신자가 몇 회만큼 다음 순서의 알파벳으로 치환할 지를 사전에 합의해야 통신이 이뤄질 수 있음

 

카이사르 암호는 알파벳을 밀어낸 횟수만 알면 해독이 가능하다!

알파벳을 밀어낸 횟수를 키(Key)라고 하면, 알파벳은 총 26자이므로 가능한 키의 가짓수는 26개

 

오른쪽으로 3번 밀어내는 카이사르 암호를 도식화한 것

 

이를 이용하여 BEEF를 암호화하면 EHHI가 출력된다.

 

 

2) 춤추는 인형과 코드북 암호

 

카이사르 암호는 알파벳을 밀어서 암호화하는 특성상, 키 공간의 크기가 작기 때문에 컴퓨터를 사용하면 쉽게 복호화된다.

조금 더 복잡한 단일 치환암호로는 셜록 홈즈에 나온 춤추는 인형 암호가 있으며, 이는 사람 한 명이 글자 하나에 대응되지만 규칙성이 없어서 암호문으로부터 평문을 쉽게 유추할 수 없다.

 

춤추는 인형 암호처럼 모든 알파벳을 서로 다른 기호와 무작위로 일대일 대응시켜 치환하면 키 공간의 크기는 26!( 26×25×⋯×2×1≈4⋅10^26)이 된다. 이 정도 크기의 키 공간은 현대의 컴퓨터로도 전부 탐색하기 어려움

 

 

• 단점: 단일 치환 암호는 언어가 지닌 통계적 특성이 유지됨
  • 통계적으로, 영어 문장에서 가장 많이 사용되는 알파벳은 e
  • 따라서 단일 치환 암호가 적용된 어떤 암호문에서 b가 가장 많이 등장한다면, b는 e가 치환된 것이라 추측할 수 있다. 이 특성을 이용하면 일반적인 영문 단일 치환 암호문은 어렵지 않게 해독될 수 있음
• 난수표나 코드북을 이용한 단일 치환 암호는 현재도 종종 사용됨
• 송신자와 수신자가 책을 정하고, 송신자가 책의 페이지 x와 단어의 인덱스 y를 보내면, 수신자는 책 x페이지의 y번째 단어를 확인하여 송신자의 메세지를 해독
• 이 암호 체계는 공작원에게 지령을 전달하는 목적으로 최근에도 쓰이고 있음!

 

예를 들어 위와 같은 책을 공유하고, 송신자가 21537, 21529, 21406, 21402라는 암호문을 보내면, 수신자는 215 페이지의 37번째 단어, 215 페이지의 29번째 단어, 214 페이지의 6번째 단어, 214 페이지의 2번째 단어를 찾고, 이를 이어 붙여 come to yellow roads 라는 메세지를 구할 수 있음

 

 

다중 문자 치환 암호 (Polyalphabetic substitution cipher)

• 다중 문자 치환 암호(Polyalphabetic substitution cipher)는 단일 문자 치환 암호와 달리, 평문의 한 문자가 암호문에서 여러 종류의 문자로 치환될 수 있음
  • 대표적인 다중 문자 치환 암호: 비제네르 암호(Vigenere cipher)
• 비제네르 암호에서 암호화와 복호화는 미리 정해진 키워드를 통해 이루어짐
• 'SKY'라는 키워드로 평문 'DREAMHACK'을 비제네르 암호화하는 과정은 다음과 같다.

 

우선 위 비제네르 표에서 키의 각 문자에 해당하는 S, K, Y 행을 고른다.

그 뒤, 키워드를 반복하며 키워드의 각 행에서 평문의 문자에 대응되는 문자로 평문을 치환한다.

 

키	S	K	Y	S	K	Y	S	K	Y
평문	D	R	E	A	M	H	A	C	K
암호문	V	B	C	S	W	F	S	M	I

 

 

전치 암호 (Transposition cipher)

• 전치 암호(Transposition cipher): 평문을 구성하는 문자들의 순서를 재배열하여 암호문 생성
• 평문을 정해진 길이의 블록들로 나누고, 규칙을 적용하여 블록 안의 문자들을 재배치

블록의 길이가 3이고 키가 (3,1,2)일 때 평문 DREAMHACK의 암호화

 

전치 암호의 대표적인 예시로는 기원전 450년에 고대 그리스인들이 발견한 스키테일 암호(Scytale cipher)가 있다.

이 암호는 나무봉(Scytale)을 이용한 암호로, 먼저 메세지를 교환할 두 사람이 같은 크기의 나무봉을 제작한다. 그 뒤 송신자는 종이 테이프를 나무봉에 감고, 테이프 위에 세로로 메세지를 기입하여 암호문를 만든다.

종이테이프를 풀어내면 순서가 뒤섞여 메세지를 읽을 수 없지만, 같은 나무봉을 가진 수신자는 테이프를 다시 나무봉에 감아서 이를 해석할 수 있다!

 

 

고전 암호 공격

안전하다고 여겨졌던 고전 암호들은 암호 분석 도구와 기술의 발달로 쉽게 분석되었다.

고전 암호를 공격하는 방법으로는 대표적으로 전수 키 탐색 공격(Exhaustive key search attack)과 빈도수 분석(Frequency analysis)이 있다.

 

1. 전수 키 탐색 공격 (Exhaustive key search attack)

• 평문과 암호문을 알 때, 키 공간을 전부 탐색하며 주어진 암호문과 같은 암호문을 생성하는 키를 찾는 방법
• 굉장히 단순한 공격 방법이지만 키 공간의 크기가 작다면 빠른 시간안에 키를 찾고, 암호를 해독할 수 있음
• 단일 치환 암호인 카이사르 암호는 키 공간이 26으로 매우 작기 때문에 전수 키 탐색 공격에 취약

2. 빈도수 공격 (Frequency analysis)

• 단일 치환 암호는 평문의 문자와 암호문의 문자가 항상 일대일 대응을 이루기 때문에 평문의 통계적 특성이 유지됨
  • 예를 들어, 영어 문장에서 각 알파벳이 사용되는 빈도를 그래프로 표현하면 아래와 같은데, 이런 특성은 문자를 단일 치환해도 유지됨

 

• 위 그래프에 따르면 평문의 E를 A로 치환해서 암호문을 만들었다면, 암호문에서 가장 많이 등장하는 알파벳이 A일 가능성이 높음
• 이런 추측을 바탕으로 암호문을 복구하는 것이 빈도수 분석(Frequency analysis)
• 이는 암호문이 어떤 언어로 구성되어 있어도 대상 언어의 특성을 안다면 시도해볼 수 있음
• 다중 치환 암호는 이러한 통계적 특성이 사라지기 때문에, 빈도수 공격으로부터 비교적 안전하다고 알려져 있음

 

 

---

 

 

 

현대 암호?

 

많은 고전 암호에서는 송신자와 수신자가 같은 키를 갖고 있어야 했다.

ex) 카이사르 암호에서는 두 사람이 알파벳을 미는 칸의 수를 공유 / 비제네르 암호에서는 키워드를 공유

이렇게 송신자와 수신자가 같은 키를 공유해야 하는 암호 시스템을 대칭키 암호 시스템이라고 함

 

• ​같은 키를 갖고 있어야 하는 특성상, 대칭키 암호 시스템은 사전에 서로 키를 공유하는 과정이 반드시 필요하다.
• 그런데 현대에 많은 데이터가 오가는 네트워크는 도청에 매우 취약하므로 키를 평문으로 공유하기는 부적절함
• 그래서 학자들은 외부인이 키가 공유되는 과정을 도청해도, 공유되는 키는 알지 못하게 하는 키 공유 알고리즘(Key exchange algorithm)을 연구함
  • 송신자와 수신자가 서로 다른 키를 상요하는 공개키 암호 시스템 (Public key cryptosystem)의 개념을 창안
  • 이는 대칭키와 대비되어 비대칭키 암호 시스템이라고도 불림

 

케르크호프스의 원리 (Kerchhoffs' principle)

• 키를 제외한 시스템의 다른 모든 내용이 알려지더라도 암호 체계는 안전해야 한다는 원리 
  • 오귀스트 케르크호프스(Auguste Kerckhoffs)가 집필한 군사용 암호의 원칙 중에서 2번째 항목으로, 현대 암호 체계에서 중요한 의미를 가지고 있음
  • 앞으로 배울 AES, RSA 또한 암/복호화 알고리즘이 공개되어 있지만, 키 혹은 비밀키 없이는 현대 기술로 복호화가 불가능한 암호 체계의 예시

 

혼돈과 확산

1945년에 암호학자 클로드 섀넌(Claude Shannon)은 안전한 암호 시스템은 혼돈(Confusion)과 확산(Diffusion)의 성질을 만족해야한다고 발표했으며, 현대의 많은 암호 시스템이 두 성질을 따르고 있음

 

1. 혼돈

• 혼돈 : 암호문에서 평문의 특성을 알아내기 힘든 성질

단일 치환 암호를 사용하여 같은 평문을 두 번 암호화하면 출력된 두 암호문은 서로 같다.

공격자는 암호문을 보고 평문이 무엇인지 유추하지는 못하더라도 암호문을 생성한 두 평문이 같다는 사실은 알 수 있음

=> 따라서 단일 치환 암호는 "혼돈" 성질을 만족하지 못하는 암호!

 

2. 확산

• 확산 : 평문의 작은 변화가 암호문의 큰 변화로 이어지는 성질 (대부분의 고전 암호에서 찾아보기 힘듦)
• 카이사르 암호 => 평문의 한 글자를 다른 글자로 변경하면 암호문에서도 해당하는 위치의 글자만 변함
• BUT 위 그림의 경우, 평문의 첫 글자를 A에서 B로 변경함으로서 암호문은 암호문 전체에서 큰 변화가 생긴 것을 확인할 수 있음

 

---

 

 

<대칭키 암호 시스템>

• 암호화와 복호화에 같은 키를 사용하는 암호 시스템
  • 크게 블록 암호와 스트림 암호로 구분

1. 블록 암호 (Block cipher)

: 평문을 정해진 크기의 블록 단위로 암호화하는 암호

ex) DES 대칭키 암호, AES 대칭키 암호

 

예를 들어 블록의 크기가 4byte라면 평문을 4byte의 블록으로 쪼개어 각 블록마다 암호화를 진행한다.

만약 평문의 크기가 블록 크기의 배수가 아니어서 블록으로 균등하게 쪼갤 수 없다면, 평문 뒤에 데이터를 추가하는 패딩(Padding)을 먼저 수행하며 평문이 블록 크기의 배수가 될 때까지 데이터를 추가하게 된다.

 

2. 스트림 암호 (Stream cipher)

: 송신자와 수신자가 공유하는 데이터 스트림을 생성하고 이를 평문과 특정한 연산을 수행하여 암호문을 생성하는 암호

복호화 과정은 암호화 과정의 연산을 역으로 수행하여 진행됨

 

대부분의 상황에서는 암호화 과정과 복호화 과정에 XOR 연산을 사용한다.

⊕ XOR 연산은 비트 단위의 연산이며, 다음 테이블과 같이 수행됨

 

a	b	a⊕b
0	0	0
0	1	1
1	0	1
1	1	0

 

XOR 연산은 다음의 중요한 특징으로 인해 스트림 암호에 사용이 적합하다.

• a⊕b의 값으로부터 a에 대한 정보를 알아낼 수 없다.
• a=(a⊕b)⊕b가 성립해 역연산이 동일하고, 정보 손실이 없다.

 

• 평문을 P, 암호문을 C, 스트림을 X라고 할 때, 암호문 C는 C=P⊕X로 생성됨
• X⊕X=0이므로 수신자는 C⊕X=P⊕X⊕X=P로 암호문을 복호화할 수 있음
  • 여기서의 ⊕는 P와 X의 같은 위치의 모든 비트를 XOR 연산을 수행하는 것을 의미
  • 예를 들어 “AB“ ⊕”qu” = [65, 66] ⊕ [113, 117] = [01000001, 01000010] ⊕ [01110001, 01110101]의 결과는 [00110000, 00110111] = [48, 55] = “07“으로 표현됨

 

 

만약 송신자와 수신자가 평문 길이만큼의 스트림을 매번 공유할 수 있다면, 스트림을 모르는 공격자는 암호문을 복호화할 수 없다. 하지만 평문과 같은 길이의 스트림을 안전하게 공유할 수 있다면, 스트림을 공유하는 채널로 평문을 공유하면 되므로 암호화가 필요하지 않은 환경임을 의미함

 

그래서 일반적으로 송신자와 수신자는 스트림을 공유하는 대신, 시드(seed)라 불리는 값을 공유하고, 이를 사전에 합의된 함수의 인자로 넣어 스트림을 각자 생성한다.

스트림 암호는 단순한 연산으로만 구현되므로 속도가 매우 빨라 연산 능력이 부족한 임베디드 기기나 속도가 중요한 환경에서 사용된다.

 

 

대칭키 암호 시스템의 장단점?

장점: 일반적으로 공개키 암호 시스템에 비해 속도가 빠름 (키 하나만 쓰니까)

단점 : 송신자와 수신자가 사전에 키를 교환해야 한다는 제약이 있음

• 또한 그룹 내에 여러 명이 있을 경우, 두 사람마다 서로 다른 키를 생성해서 사용해야 함
• 즉, N명의 사람이 있을 때 총 nC2=N(N−1)/2개의 키가 필요
• 이후에도 새로운 상대와 통신할 때마다 계속 키를 생성해야 함
• 공개키 암호 시스템에는 이와 같은 키 생성의 불편함이 없음!

 

 

---

 

<공개키(비대칭키) 암호 시스템>

• 공개키 암호 시스템에서 송신자는 수신자의 공개키(Public Key)로 데이터를 암호화하여 수신자에게 전송하고, 수신자는 자신의 비밀키(Private Key)로 이를 복호화
  • 같은 시스템에서 사용되는 공개키와 비밀키를 키 쌍(Key Pair)이라고 부름

명칭에서 알 수 있듯 공개키는 모두에게 공개되어 있어 공개키를 아는 사람은 누구나 수신자에게 암호문을 보낼 수 있다.

그러나 개인키는 수신자만 알고 있으므로, 공격자는 암호문을 도청해도 이를 복호화할 수 없음

 

공개키 암호 시스템은 우체통에 비유될 수 있다.

누구나 수신자의 우체통으로 편지를 보낼 수 있지만, 편지를 꺼내서 볼 수 있는 사람은 열쇠를 가지고 있는 수신자뿐이다.

 

대칭키 암호의 경우 송신자와 수신자가 같은 키를 사용해야 하지만, 공개키 암호 시스템의 경우 서로 다른 키를 사용하는 점에서 차이가 존재한다. 이에 따라 공개키 암호 시스템을 비대칭키 암호 시스템이라고 부르기도 한다.

 

 

비대칭키 암호 시스템의 장단점?

• 공개키 암호 시스템에서는 그룹 내의 사람들이 각자의 공개키와 비밀키를 만든 후 공개키만 공개하면 되므로 N명의 사람이 있을 때 N개의 키 쌍만 필요
  • 이는 nC2개의 키가 필요했던 대칭키 암호 시스템보다 훨씬 적음
  • 또한 한 번 키를 생성하고 나면, 새로운 상대와 통신하더라도 자신이 키를 다시 만들어야 할 필요가 없음
• 반면, 공개키 암호 시스템은 일반적으로 대칭키 암호 시스템에 비해 다소 복잡한 연산이 필요하므로 속도가 느림
  • 또한 대칭키 암호와 같은 안전성을 제공하려면, 대칭키 암호보다 긴 키를 사용해야 함
  • 예를 들어 대칭키 암호 시스템인 AES는 192 비트 이상의 키를 사용하면 충분히 안전하지만, 공개키 암호 시스템인 RSA는 2048 비트 이상의 키를 사용할 것이 권장됨