[정보보호개론] Week_2 : 여러가지 암호 알고리즘

이전에 Caesar's Cipher에 대해서 포스팅을 했었다

[정보보호개론] Week_1 : Caesar's Cipher

 

더 많은 암호 알고리즘에 대한 포스팅

---

1) Substitution Cipher : 치환 암호

- Caesar's Cipher는 Shift를 통해서 암호화를 하기 때문에 "Exhaustive Key Search"를 통해서 파악이 가능하다

- Substitution Cipher는 어떤 알파벳을 임의의 알파벳으로 치환하는 알고리즘이다

 

Key

원래 알파벳 : 치환 알파벳을 1:1로 Mapping

 

Key Space

- 26자리 각각에 26개의 알파벳이 들어갈 수 있다

→ 26! > 2⁸⁸ : 매우 큰 key space를 보유하고 있으므로 "Exhaustive Search"로 사실상 암호해독이 불가능하다

- 이 경우, "Be Clever"하게 '알파벳 사용 빈도'를 통해서 해독을 하는 방법이 존재한다

1. Cipher Text에 나오는 알파벳 빈도수를 계산

2. 각 알파벳 빈도수별로 치환

 

암호체계의 안전성에 대한 정의

가장 이상적인 것은 "해당 암호체계에 대한 적합한 공격방법이 없음을 수학적으로 증명"하는 것이다

 

하지만 "전수 조사"의 경우 어떠한 암호체계에 대해서 공격은 가능하다

 

>> 여기서 그 암호체계에 대해서 알려진 최선의 공격방법이 "전수조사" 뿐일 때, 그 암호체계는 안전성이 있다고 정의한다

 

 

---

2) Transposition Cipher

- 알파벳이 나오는 위치를 변환하는 암호 알고리즘이다.

• 알파벳을 다른 알파벳으로 변환하는게 아니라, plaintext내에서 알파벳의 위치를 서로 바꿈으로써 ciphertext로 변환하는 방식이다

Example) Plaintext : "attack at dawn"

1. "Matrix Size"를 먼저 결정 : 5 X 3

2. 각 row & column을 섞는다

PlainText				→	CipherText
	c1	c2	c3			c1	c3	c2
r1	a	t	t		r3	x	t	a
r2	a	c	k		r5	w	x	n
r3	x	a	t		r1	a	t	t
r4	x	d	a		r4	x	a	d
r5	w	n	x		r2	a	k	c

>> "xtawxnattxadakc"라는 ciphertext로 변환이 되었다

 

Key

- "Matrix Size" & row/column의 순서

 

- 빈도수 공격이 소용이 없는 암호 알고리즘이다.

- 하지만 Transposition cipher에도 단점이 존재한다

>> 따라서, Substitution과 Transposition을 섞어서 사용하는게 좋다

 

---

3) One - Time Pad (일회성 암호)

- 안전성이 수학적으로 증명이 된 암호 알고리즘

- "Exclusive-OR"을 통해서 암호화 한다 (XOR)

 

※ XOR 연산의 특징

 

1. 문장의 단어(알파벳)들을 각각 binary code로 변환해준다

2. key는 random하게 매번 생성해주고, 길이는 반드시 plaintext와 동일해야한다

• 그리고 해당 key는 반드시 receiver에게 안전하게 전달 되어야 한다

 

※ Example) heilhitler

	h	e	i	l	h	i	t	l	e	r
Plain Text	001	000	010	100	001	010	111	100	000	101
Key	111	101	110	101	111	100	000	101	110	000
Cipher Text	110	101	100	001	110	110	111	001	110	101
	s	r	l	h	s	s	t	h	s	r

>> plaintext인 "heilhitler"를 key를 사용한 XOR 연산을 통해서 ciphertext인 "srlhssthsr"로 변환되었다

 

Key는 반드시 random해야 하고, 한번 사용한 key는 버리고 다른 random한 key를 새로 생성해서 사용해야 한다

 

※ key를 재사용하게 된다면?

"p1, p2를 각각 c1, c2로 암호화 할 때, 동일한 key를 사용한다면?"

>> 여기서 Attacker가 (p1, c1)의 관계를 알아냈다고 가정하게 되면

>> 결국 XOR의 성질에 의해서 p2를 알아낼 수 있다

 

따라서, One-Time Pad 방식은 매번 암호화할때마다 새로운 key를 생성해줘야 한다. 이것은 현실적으로 One-Time Pad 암호 알고리즘이 사용하기 힘든 이유이기도 하다

 

 

---

4) CodeBook

"Februar" : 13605
"Fest" : 13732
"Frieden" : 17142
"Fridenschluss" : 17149
....
....

이런식으로 암호문의 숫자를 "CobeBook"에서 찾아서 대응되는 문자열로 변경하는 방식이다

 

---

Claude Shannon - Information Theroy of Secrecy Systems

좋은 암호 알고리즘의 특성

▶ Confusion : 혼돈

- Plaintext & CipherText의 내용들 간에 연관성이 파악되지 않도록 분리해야 한다 (값 변환)

>> Substitution Ciphers & One-Time Pad & ....

 

▶ Diffusion : 확산

- Plaintext의 통계적 값들을 CipherText에서는 퍼뜨려 놓아야 한다 (글자 분산)

>> Double Transposition Cipher

---

암호화 분류

Symmetric Key

- 대칭키 암호 알고리즘

- Stream Ciphers & Block Ciphers

 

Public Key

- 키가 2개가 존재한다

• 암호화 = public key
• 복호화 = private key

▶ Digital Signature (전자 서명)

• 서명은 누구나 읽을 수 있다
• 하지만 서명한 사람만이 그 서명을 만들 수 있다

---

암호해석 분류 (Attacker 기준)

1) Ciphertext Only Attack

"커크호프 원칙"에 따르면 Attacker는 암호 알고리즘의 내부 작동에 대해서 완전히 알고 있다고 가정한다

그리고 Attacker가 암호문을 획득하였다고 하자

 

이 때 Trudy가 암호문을 해석하기 위해서 Ciphertext Attack을 시도한다

 

하지만 Trudy는 알고있는 정보가 어차피 모두가 아는 정보인 알고리즘 & 암호문이므로 가장 불리한 공격 시나리오이다

 

2) Known Plaintext Attack

만약 Trudy가 "Known Plaintex"에 대한 지식이 있다면 공격이 성공할 확률이 높아진다

이 말은 즉, (P, K) → C의 조합 몇개를 알고 있다는 의미이다

 

>> 이러한 경우 (P, C)를 통해서 K에 대한 정보를 획득할 수 있다는 소리이다

 

예를 들어서 많은 종류의 데이터가 일정하게 형식화된 이메일 같은 경우 이 이메일을 암호화했다면 Trudy는 "Header"에 해당하는 Plaintext의 일부분을 추측할 수 있고 그에 따라서 해당하는 Ciphertext를 함께 볼 수 있다

 

3) Chosen Plaintext Attack

이 공격방법은 Trudy가 "Plaintext를 임의로 선택해서 그에 해당하는 Ciphertext를 볼 수 있다"는 가정하에 이루어지는 공격이다

 

예를 들어서 어떤 임의의 메시지를 전송하면 해당하는 암호문이 되돌아오는 프로토콜이 있다. 그리고 Trudy는 해당 암호체계에 일시적으로 접근할 수 있어서 자신이 임의로 선택한 Plaintext에 대한 Ciphertext를 볼 수 있다

 

Alice가 점심식사를 하러 나갈 때 컴퓨터를 끄지 않았다면 이 사이에 Trudy가 Alice의 컴퓨터에 접근해서 자신이 임의로 선택한 메시지를 암호화해서 본인한테 전송할 수 있을 것이다

 

이런 "Lunch Time Attack"은 여러가지 형태로 존재한다

 

 

4) Adaptively Chosen Plaintext Attack

이 공격방법은 Attacker에게 굉장히 유리한 방법이다

 

Trudy가 Plaintext에 대한 Ciphertext를 보고 해당 Ciphertext에 의거해서 다음 Plaintext를 선택한다

이렇게 하면 서로 관련이 되어 있기 때문에 "키가 특별한 방법으로 생성되어 있는 시스템의 약점"을 이용하는 것이다