Cryptanalysis - Simple ciphers 정리 및 복습

1. Introduction

1) The Topic of Cryptanalysis

- Cryptanalysis(암호분석)은 컴퓨터 발전으로 인해 1980년대 후-1990년대 초부터 급격히 발달하기 시작.

- 암호분석을 잘하기 위해서는 breaking codes를 연습하는 방법뿐!

 

2) Concepts of security

- Security (=Safety) : freedom from danger 위험하지 않은 것, 즉 안전한 것.

- Information security : 정보를 인가되지 않은 접근으로부터 지키는 것, 세 가지 원칙 CIA (confidentiality 기밀성, integrity 무결성, availability 가용성)

 

3) Cryptology = Cryptography + Cryptanalysis

- Cryptography : 설계자 입장, 암호화에 포커스, 알고리즘 측면에서 암복호화

- Cryptanalysis : 공격자 입장, 분석적인 측면에서 공격과 방어, Information security를 더 강하게 하기 위해! (수업에서 배울 것.)

 

4. Principles of good cryptography - by Claude Shannon

- 비용 발생 불가피, B, 원래 지키고자 하는 데이터보다 보호하는 데 더 많은 비용이 들면 X

- 암호문의 크기 <= 평문의 크기

- be simple 불필요한 복잡성 X

- 에러는 전파되지 X

 

 

2. Simple Ciphers

1) Monoalphabetic ciphers - 한 글자 한 글자

   (1) Ceasar cipher : 키 25개만 대입하면 끝남. 대표적인 key는 3

   (2) ROT13 : key=13

   (3) Keyed Alphabets

   (4) single-letter substitution cipher 단순 치환 암호 : possible keys = 26! = 2^89

 

2) Polyalphabetic ciphers - 여러 글자 씩

  (1) Vigenere Tableau

  (2) Transposition cipher (=permutation cipher) : 글자 위치 바꾸기, 섞어놓기

    (2-1) Columnar transpositions

           - Set row length k = key. 평문을 설정한 key만큼 나눠서 쓰고 암호문은 세로로 읽기.

    (2-2) Double columnar transpositions

           - key = (k1, k2)

 

 

3. Breaking monoalphabetic ciphers

1) Frequency analysis 통계적 특성

    - e의 빈도수가 가장 높고, 그 다음 a, t ..

2) Index of coincigence I_c

    - 랜덤하게 알파벳 2개 뽑았을 때(비복원 추출) 같은 문자가 나올 확률

    - I_c(plaintext) = I_c(ciphertext)   //자리만 바꿨을 뿐 개수들은 똑같으니까.

    - I_c의 최솟값 = 0.038 (랜덤하게 알파벳이 섞여 있을 때. 흩어져 있다면 0.038보다 커지겠지.)

 

 

4. Breaking ployalphabetic ciphers

1) Attack strategy for Vigenere cipher

(1) key length 추측

• Method1 -  I_c 이용: 1부터 쭉 해보면서 몇 번째 key length를 했을 때 index of coincidence가 가장 높은지 찾기 = 랜덤한 것보다는 영문에 가까워 지는 것 = key length 추측 성공
• Method2 - 흔한 단어들이 얼마나 반복되는가?

(2) 추측한 key length를 바탕으로 각각 key에 대한 것 끼리 모아서 문제 풀기

        ex. key = word word word ... 1번째, 4번째, 8번째는 w에 대해서 암호화 되었군! 을 알 수 있다.

 

 

5. Breaking Transposition Ciphers

- diagaph(연속된 2개 - th, he 같은.. ), trigraph(연속된 3개 - the, and 같은.. ) 이용

 

 

6. Attack Columner Transposition Ciphers

- Sliding window technique

 

 

 

---

 

위에 정리했듯이, 고전암호들은 언어적 특성을 이용해 공격 할 수 있다. 그렇기에 고전암호는 취약하다. 따라서 현대암호는 암호문에 통계적 특성이 전혀 나타나지 않게끔 한다.(랜덤한 output의 암호문으로.) 고전암호를 공부하는 것에 너무 많은 힘을 들이지 말고, 시저 암호, 단순 치환 암호의 코딩 정도만 할 수 있으면 되겠다.

 

p.s 여기서 말하는 '언어적 특성'이란

1. 알파벳 빈도 e > a, t > ...

2. index of coincidence

3. digraph, trigraph (연속된!)