[Cryptography] Classical Ciphers, Steganography

[Cryptography] Classical Ciphers

Crpytography

용어

1. Plaintext(평문)

- 암호화되지 않은 일반 문장

2. Ciphertext(암호문)

- 평문을 암호화시킨 문장

3. Cipher

- 암호화에 사용되는 알고리즘

4. Key

- 암호화, 복호화에 사용되는 키

5. Encrypt(encipher)

- 암호화(평문 -> 암호문)

6. Decrypt(decipher)

- 복호화(암호문 -> 평문)

7. Cryptanalysis(암호해독)

- key를 모른채로 암호문을 해독

분류

1. 암호화 타입에 따른 분류

1) substitution(치환)

- 특정 문자를 다른 문자로 치환하여 암호화

2) transposition(전치)

- 문자들의 위치를 섞어 암호화

3) product

- substitution + transposition

- 현대 암호의 시작

2. Key 개수에 따른 분류

1) single-key

- private key(대칭키, 비밀키 방식)

- 암호화 키 = 복호화 키

2) two-key

- public key(비대칭키, 공개키 방식)

- 암호화 키 != 복호화 키

3. Plaintext 처리 방법에 따른 분류

1) block

- 평문을 block단위로 나누어 암호화

2) stream

- 평문을 그대로 암호화

Cryptanalysis

Definition

- 키를 모른채로 암호문을 평문으로 변환

- = 암호 깨기(code breaking)

목적

- key 획득

- 암호문을 평문으로 해독해 읽기

분류

1. Crpytanalytic attack

- 알고리즘의 특성과 평문의 특성, 평문-암호문 쌍의 특성을 이용하여 해독

1) Ciphertext Only Attack(COA)

- 암호문만 가지고 있는 상태에서의 공격

2) Known Plaintext Attack(KPA)

- 몇개의 주어진 (plaintext, ciphertext) 쌍을 이용하여 공격

3) Chosen Plaintext Attack(CPA)

- 암호화기 사용 가능

- 평문을 선택하여 해당 평문에 대한 암호문을 얻을 수 있음

4) Chosen Ciphertext Attack(CCA)

- 복호화기 사용 가능

- 암호문을 선택하여 해당 암호문에 대한 평문을 얻을 수 있음

2. Brute-force attack

- 모든 경우의 수를 시도하여 암호 해독

- 키의 길이를 늘려 경우의 수를 증가시켜 해독에 어려움이 있게 해야함

- key : bit 단위

암호학적 분류

1. Unconditional security

- 암호해독이 불가능한 보안

- 현재 존재하지만 암호화, 복호화가 비효율적이기 때문에 사용하지 않음

2. Computational security

- 컴퓨터 성능에 따라 공격이 가능

- 해커의 소모 비용과 이익의 경제성때문에 공격을 하지 않아 안전

Classical Ciphers

Substitution Cipher

1. Caesar Cipher

- 가장 오래된 치환 암호

- 각 문자에 +k을 하여 암호화

-> C = E(k, P) = (P+k) mod (26)

- 각 문자에 -k을 하여 복호화

-> P = D(k, C) = (C-k) mod (26)

ex) Key : 3, Plaintext : I AM DONGDD

1) 취약점

- 총 26개의 알파벳이기 때문에 26개의 경우의 수만 brute force로 시도하면 쉽게 해독 가능

2. Monoalphabetic Cipher

- 하나의 알파벳을 다른 알파벳으로 치환

- 1 : 1 치환

- 26!의 경우의 수

ex) Plaintext : I AM DONGDD

1) 취약점

- 26!의 경우의 수로 brtue force는 어려움이 있음

- 알파벳의 특성 중 frequency를 이용하여 해독(통계학적 특성)

-> 영어 알파벳 frequency : E > T > R > N > I >O > A > S > ...... > Z > J > K > Q > X

3. Playfair Cipher

- Monoalphabetic Cipher의 취약함때문에 2 : 2 치환을 생각했지만 갖고 있어야 할 table이 너무 컸기 때문에 사용하지 못했었음

- Playfair Cipher는 이 어려운 점을 극복 -> 효율적인 암호화, 복호화

- 5*5 행렬을 사용하여 암호화, 복호화

ex) Key : DONGKEY, Plaintext : I AM DONGDD

1) 암호화

① 5*5 행렬을 그리고 key를 왼쪽 위부터 채우고 남는 칸은 안 쓰인 알파벳으로 채움

-> 26개의 알파벳을 25칸의 행렬에 채우기 때문에 I/J와 같이 한 칸에는 두개를 써줌

② 평문의 길이가 홀수이거나 두개씩 묶었을 때, 같은 알파벳이 나오는 경우 임의의 알파벳을 넣어줌

-> 예제에서는 홀수이기때문에 마지막에 X를 붙여줌

③ 알파벳을 2개씩 묶고 2개별로 암호화 진행

④ (I A)

-> 두 개의 알파벳이 같은 열에 있을 경우, 한 칸 밑의 알파벳들로 치환

-> R I

⑤ (M D)

-> 두 개의 알파벳이 대각선 형태를 이루면 해당 대각선을 가지는 사각형을 그림

-> 사각형의 다른 대각선의 알파벳으로 치환

-> F K

⑥ (O N)

-> 두 개의 알파벳이 같은 행에 있을 경우, 한 칸 오른쪽의 알파벳들로 치환

-> N G

⑦ (G D)

-> 두 개의 알파벳이 같은 행에 있을 경우, 한 칸 오른쪽의 알파벳들로 치환

-> K O

⑧ (D X)

-> 두 개의 알파벳이 대각선 형태를 이루면 해당 대각선을 가지는 사각형을 그림

-> 사각형의 다른 대각선의 알파벳으로 치환

-> G U

⑨ 예제에서는 없었지만 행렬 범위를 벗어나는 경우, 순환 큐와 같이 처리

2) 취약점

- Monoalphabetic cipher에서는 26개의 frequency로 공격했지만, playfiar는 26^2 = 676개의 frequency를 찾아야함

- 하지만 2개씩 하더라도 frequnecy가 나타남(그래프로 표현했을 때, monoalphabetic보다는 완만한 기울기를 가짐)

- 개수를 점점 늘려서 frequnecy가 나타나지 않도록 해야함(일반적으로 10 : 10인 경우 frequency가 사라짐)

4. Polyalphabetic Cipher - Vigenere Cipher

- N개의 알파벳을 N개로 치환

- 26^n이기 때문에 table의 크기가 늘어나 사용하기 어려웠음

- 효율성을 해결하는 Vigenere Ciper 출현

- key의 길이 = block의 크기

- plaintext의 길이만큼 key를 반복해서 사용

ex) Key : deceptive, Plaintext : wearediscoverdsaveyourself

1) 암호화

- plaintext의 길이만큼 key를 반복해서 사용

- key와 plaintext를 더하여 암호화

2) 취약점

① Kasiski Method

- 예제에서 VTW가 두번 나오는 것을 볼 수 있음

- 이것을 이용해 key의 길이를 파악(3 or 9)

- 유추한 키의 길이를 이용해 길이의 첫번째 글자를 이용해 frequency attack

-> key의 길이 : 9(1번째 글자, 10번째 글자, 19번째 글자)

-> monoalphabetic cipher의 취약점과 비슷

5. Autokey Cipher

- key를 정하고 해당 키 이후에 plaintext의 길이만큼 plaintext를 붙여 key 생성

ex) Key : deceptive, Plaintext : wearediscoverdsaveyourself

1) 암호화

- key = key+ plaintext 일부

- key와 plaintext를 더하여 암호화

2) 취약점

- 평문을 key로 사용한다고 볼 수 있어 키의 길이를 유추해 암호 해독이 가능

6. Vernam Cipher(One Time Pad)

- Unconditional Cipher 중 하나

- 평문의 길이를 가진 random한 key를 생성

- 평문 xor 키 = 암호문

- 암호문 xor 키 = 평문

- key의 길이가 평문의 길이이기 때문에 유지해야 할 key의 길이가 너무 크기때문에 unconditional cipher

-> 평문의 1TB라면 key의 길이 1TB

Transposition Cipher

1. Rail Fence Cipher

- key가 없는 전치 암호

ex) Plaintext : I AM DONGDD

1) 암호화

- 평문을 위와 같이 대각선으로 배치

- 대각선으로 배치한 후 이어붙여 암호화

2) 취약점

- 암호문을 반으로 나누어 읽으면 암호 해독 가능

2. Row Transposition Cipher

- Key를 설정하고 Key의 길이로 하는 열을 가진 행렬 구성

- Key에는 열의 Index가 들어있고 행렬에는 평문을 배치

ex) Key : 2 4 3 1 5, Plaintext : IAMDONGDDIAMDONGDD

1) 암호화

- key의 길이 5를 열의 길이로 하여 행렬 생성

- 행렬에 평문을 차례대로 배치

- Key의 순서대로 각 열을 써서 암호화

Product Cipher

- Substitution cipher와 Transposition cipher가 취약한 부분이 있기 때문에 고안

- Substitution과 Transposition을 섞어 암호화 수행

- 현대 암호의 시작

Steganography

Definition

- 그림 파일, 음악 파일 등 일반적인 파일에 평문을 숨김

- 이미지의 경우 보이지 않는 색을 변경할 수 있고, 파일의 LSB bit를 수정하여 평문을 숨김

장점, 단점

1. 장점

- 암호문을 전송할 경우, 해커가 암호문을 해독하려는 의지가 생길 수 있지만 일반 그림 파일의 경우 평문이 숨겨있는지 알기 어렵기 때문에 해독하려는 의지를 막을 수 있음

2. 단점

- 정보가 담긴 bit를 파일에 넣기 때문에 overhead가 큼