[학습목표]
- 암호의 발전과정을 살펴본다.
- 고전암호를 통해, 간단하게 만들어진 암호들이 왜 안전하지 않은 지 알 수 있다.
1. Recall 시저 암호
⚠️ 케르크호프스의 원리(Kerckhoffs's principle)와 맞지 않음
- 키가 없기 때문에, 암호화 방법을 알면 복호화 가능
- 케르크호스프의 원리 : 암호의 안전성은 오직 키의 비밀성에만 의존,
2. 시저 암호의 일반화 : 덧셈 암호 (Shift cipher)
- 🔑 키 생성 : 0~25까지의 랜덤한 후 k 선택
- 🔒 암호화 : x -> x + k (mod 26)
- 🔓 복호화 : Y -> Y - k (mod 26)
1) 덧셈 암호 해독해보기
2) 덧셈 암호에 대한 공격 방법
- COA (Ciphertext Only Attack)
- 26개의 가능한 키 모두 시도
- 암호문이 충분히 길다면, 통계적 분석을 통해 해독 가능
- KPA (Known Plaintext Attack)
- 한 쌍의 평문, 암호문만 있어도 키 알 수 있음
- CPA (Chosen Plaintext Attack) / CCA (Chosen Ciphertext Attack)
- KPA 와 유사하게 한 번의 암호화(or 복호화) 질의로 키를 얻을 수 있음
3) Improved COA : 자동화 공격
- 자동화 공격 : 사람의 주관 개입 X, 자동 실행 가능한 공격
- 공격법 ...
3. 곱셈 암호
- 🔑 키 생성 : 26과 서로소인 수 k를 선택
- 🔒 암호화 : m -> m x k (mod 26)
- 🔓 복호화
- x x k = 1 (mod 26) 인 x를 찾기
- 복호화 키를 찾는 알고리즘
- x x k = 1 (mod 26) 인 x를 어떻게 찾을 수 있을까.
- 유클리드 호제법 (Euclidean Algorithm)
- 최대공약수를 찾기 위한 효율적인 알고리즘
- k와 26에 대해 유클리드 호제법 적용 -> x를 찾을 수 있음
4. 아핀 암호 (Affine Cipher)
- 배경 : 덧셈 암호/곱셈 암호는 키에 가능한 모든 경우(26가지, 12가지) 대입- 해독 가능 : 전수조사 공격 (Brute force attack)
- 아핀 암호 : 곱셈 암호와 덧셈 암호를 한 번씩 적용
- 𝑥 → 𝛼 ⋅ 𝑥 + 𝛽 (𝑚𝑜𝑑 26)
- 총 가능한 키의 개수 = (𝛼, 𝛽)의 개수 = 12 * 26 = 312개
1) 아핀 암호에 대한 공격 방법
- COA (Ciphertext Only Attack)
- 312개의 가능한 키 모두 시도
- KPA (Known Plaintext Attack)
- 두 쌍의 평문, 암호문만 있어도 (높은 확률로) 키를 알 수 있음
- 연립방정식 이용, 𝛼, 𝛽를 얻을 수 있음
- CPA (Chosen Plaintext Attack)
- 0(a)에 대한 암호화 질의 던지면 𝛽를 알 수 있음
- 1(b)에 대한 암호화 질의를 던지면 𝛼+𝛽를 알 수 있고 따라서 𝛼 얻음
- CCA (Chosen Ciphertext Attack)
- KPA와 유사하게 두 번의 질의 던져서 연립방정식
5. 비즈네르 암호 (The Vigenere Cipher)
- 덧셈 암호의 🔑키가 여러 개인 일반화
- 메시지 속 문자의 위치에 따라서 치환 규칙이 달라짐
- 🔑 키 생성
- 🔒 암호화
- 🔓 복호화
1) 비즈네르 암호의 장점
- 하나의 알파벳이 항상 똑같은 암호문으로 암호화 X -> 통계적 특성 약화
- 키 공간도 N을 설정함에 따라 크게 설정 가능
2) 비즈네르 암호에 대한 공격 방법
- COA
- 암호 키의 길이(N)를 알아냄 : 카지스키 테스트
- 도수 분석 (frequency analysis) 수행
- KPA
- 충분한 길이의 평문, 암호문 쌍을 알면 -> 둘의 차이로 키를 알 수 있음
- CPA : aaaa... 의 암호문을 통해 키 알 수 있음
- CCA : AAAA... 의 평문을 통해 키 알 수 있음
6. 힐 암호 (Hill Cipher)
- 메시지를 일정한 크기의 블록으로 쪼개어 암호화
- 🔑 키 생성
- 🔒 암호화
- 🔓 복호화
7. 아핀 힐 암호 (Affine Hill Cipher)
- 아핀 암호와 힐 암호의 결합 (블록 단위로 암복호화)
- 🔑 키 생성
- 🔒 암호화
- 🔓 복호화
8. 고전암호 한계
1) 단일문자 치환 암호 (monoalphabetic substitution cipher) [시저암호, 덧셈 암호, 아핀 암호]
- 알파벳끼리 1:1 대응
- 문자 빈도 분석법 등 통계적 분석 방법에 취약
2)복수문자 치환 암호 (Polyalphabetic substitution cipher) [비즈네르, 힐 암호]
- 평문을 블록 단위로 나눠서 치환
- 하나의 알파벳 - 여러 개의 알파벳들로 암호화
- 통계적 특성 약화
9. 확산과 혼돈
- 암호가 가져야 할 두 가지 '좋은' 성질
- 확산 (Diffusion) : 평문과 암호문의 관계
- 혼돈 (Confusion) : 암호문과 키의 관계에 대한 성질
