01.3 Classical Encryption

정보보호이론 강의 중 고전 암호(Classical Encryption) 파트를 정리 및 해설한 요약본입니다. 

---

🏛️ 고전 암호 (Classical Encryption)

---

📌 기본 표기법

• Zₘ = {0, 1, ..., m-1}
• 예시:
  • 10 mod 3 = 1
  • 729 mod 31 = 16 → (729 = 23×31 + 16)
  • 7 mod 26 = 19 → (-7 = -1×26 + 19)
• 문자 공간: Z₂₆ 사용 (az → 025로 매핑)
  • 예: a → 0, b → 1, ..., z → 25

---

📌 1. 시저/이동 암호 (Shift Cipher = Caesar Cipher)

• 암호화: Enc(K, x) = (x + K) mod 26
• 복호화: Dec(K, y) = (y - K) mod 26
• 예시: K = 9, "shift" → "BQROC"

🔓 공격

• 무차별 대입: 가능한 K = 0~25 → 26개
• 평문 기반 공격: "shift"와 "BQROC" 쌍을 통해 K = 9 계산 가능

---

📌 2. 아핀 암호 (Affine Cipher)

• 암호화: Enc(K, x) = (αx + β) mod 26
• 복호화: Dec(K, y) = α⁻¹(y − β) mod 26
• (단, gcd(α, 26) = 1 이어야 함 → α는 26과 서로소)
• 예시: K = (7, 3)
• "hot" → "AXG" (α = 7, β = 3)

🔓 공격

• 무차별 대입: α 후보 12개 × β 후보 26개 → 총 312가지
• 평문 기반 공격으로 α, β 도출 가능 (연립방정식 사용)

---

📌 3. 치환 암호 (Substitution Cipher)

• 알파벳 전체에 대해 π라는 임의의 순열을 적용
• Enc(K, x) = π(x), Dec(K, y) = π⁻¹(y)

🔓 공격

• 무차별 대입: 26! (≈ 2.88×10²⁶) → 거의 불가능
• 선택 평문 공격: n개의 평문 쌍 알면, 남은 경우의 수 = (26 - n)!

---

📌 4. 통계 분석 (Statistical Test)

• 영어 텍스트 평균 문자 빈도수를 기반으로 암호문을 분석
• Z가 가장 많다면 → Z → E로 추측할 수 있음
• 대표적인 방법: 빈도 분석 (frequency analysis)

---

📌 5. 비제네르 암호 (Vigenère Cipher)

• 다중 알파벳 치환 방식
• 암호화: Enc(K, x₁,...,xₘ) = (x₁+k₁, ..., xₘ+kₘ) mod 26
• 복호화: Dec(K, y₁,...,yₘ) = (y₁−k₁, ..., yₘ−kₘ) mod 26

🔓 공격

• 무차별 대입: 키 길이 m일 때, 26^m
• 통계 분석: Kasiski Test 등으로 키 길이 유추
• 알려진 평문 공격: 키 길이 알면 간단히 복호화 가능

---

📌 6. 순열 암호 (Permutation Cipher)

• 키 K는 자리 바꾸기 순열: π = (1, ..., m)의 순열
• 암호화: 입력 순서 바꿈 → Enc(K, x₁,...,xₘ) = (xπ(1), ..., xπ(m))
• 복호화: Dec(K, y₁,...,yₘ) = (yπ⁻¹(1), ..., yπ⁻¹(m))

❗ Hill Cipher는 순열 행렬이 가역적일 때의 일반화된 형태

🔓 공격

• 무차별 대입: m! (자리 순열 수)
• 선택 평문 공격: m개의 독립된 평문/암호문 쌍 필요

---

📌 7. 선형 피드백 시프트 레지스터 (LFSR)

• 현재 상태의 선형 조합으로 다음 비트 생성
• 예: xₙ₊₅ = xₙ + xₙ₊₂ mod 2
• → 초기 상태: (x₁, x₂, x₃, x₄, x₅) → 일련의 시퀀스 생성

---

📌 8. LFSR 기반 암호 (LFSR Cipher)

• 키 K = (k₁,...,kₗ) 와 선형함수 f 사용
• 암호화: Enc(K, xᵢ) = xᵢ ⊕ kᵢ
• 복호화: Dec(K, yᵢ) = yᵢ ⊕ kᵢ

⛏️ 키 스트림은 이전 k값들을 이용한 선형 생성기로 생성

🔓 공격

• 알려진 평문 공격:
  1. (x, y)로부터 k값 추정
  2. 선형방정식 계열로 행렬 K 구성
  3. 가역 행렬이면 전체 키 복원 가능

---

📌 9. 일회용 패드 (One-Time Pad, OTP)

• 1918년, Gilbert Vernam & Joseph Mauborgne 개발
• 키 K는 한 번만 사용하고 폐기

✅ 장점: 완전한 보안 제공 (통계학적으로 해독 불가)

❌ 단점: 효율성 떨어짐 → 키를 매번 새로 생성해야 함

• Plaintext space = Ciphertext space = Key space = Z₂ᵐ
• Enc(K, x) = x ⊕ K, Dec(K, y) = y ⊕ K

---