현대암호학 #3

케이요·2021년 10월 23일

대학원 수학 암호학 현대암호학

현대 암호학

목록 보기

3/6

2021-09-20-현대암호학-3주차.md

Traditional symmetric ciphers

Symmetric Cryptosystem

Definition.대칭키 암호 시스템은 $(M,C,K,Enc,𝐷𝑒𝑐)$ 로 구성된다.
- $M$ : 평문(=메시지) 집합
- $C$ : 암호문 집합
- $K$ : 키 집합
- $Enc: K \times M \rightarrow C$ : 암호화 알고리즘
- $Dec: K × C → M$ : 복호화 알고리즘
  - 두 알고리즘을 다음과 같이 표기하기도 함:
    
    $𝐸𝑛𝑐(𝑘,𝑚) ≔ 𝐸𝑛𝑐_𝑘(𝑚)$ and $𝐷𝑒𝑐(𝑘,𝑐) ≔ 𝐷𝑒𝑐_𝑘(𝑐)$

Classical Cryptography

고전 암호 설계 방법
- 치환(substitution): 평문의 문자를 다른 문자로 바꾸는 방식
- 전치(transposition): 평문의 문자의 위치를 바꾸는 방식
- 암호 분석 도구들과 기술의 발달로 쉽게 분석됨
  - 전사적 공격(brute force attack): 가능한 모든 키를 조사 (=exhaustive search)
  - 빈도수 분석(frequency analysis): 빈도수가 높은 정보를 이용하여 공격
  - 이론적 공격: 차분 공격, 선형 공격 등

Caesar Cipher

시저 암호(Caesar Cipher)
- 평문의 한 문자가 오른쪽 세 자리 뒤에 위치한 문자로 치환됨
- 덧셈 암호(additive cipher)에서 $𝑘 = 3$ 인 특수한 경우
- 단일 문자 치환 암호(Monoalphabetic substitution cipher)의 가장 간단한 형태
  - 평문의 한 문자와 암호문의 한 문자는 언제나 일대일 대응
- Definition.
  - $M=C=\mathbb Z_{26}$ , $K=\{3\}$
  - $𝐸𝑛𝑐_𝑘(𝑚) ≡ 𝑚+3 \pmod {26}$
  - $𝐷𝑒𝑐_𝑘( 𝑐) ≡𝑐 − 3 \pmod{26}$

Additive & Multiplicative Cipher

덧셈 암호(additive cipher)
- 평문의 한 문자가 오른쪽 $𝑘(∈\mathbb Z_{26})$ 자리 뒤에 위치한 문자로 치환됨
- Definition.
  - $M=C=K=\mathbb Z_{26}$
  - $𝐸𝑛𝑐_𝑘(𝑚) ≡𝑚+𝑘 \pmod{26}$
  - $𝐷𝑒𝑐_𝑘(𝑐) ≡𝑐−𝑘 \pmod{26}$
곱셈 암호(multiplicative cipher)
- 복호화를 위해서는 곱셈상의 역원이 존재하는 값을 키로 사용
- Definition.
  - $M = C = \mathbb Z_{26}$
  - $K = \mathbb Z^*_{26} = \{1,3,5,7,9,11,15,17,19,21,23,25\}$
  - $𝐸𝑛𝑐_𝑘(𝑚) ≡ 𝑚×𝑘 \pmod{26}$
  - $𝐷𝑒𝑐_𝑘(𝑐) ≡𝑐×𝑘^{−1} \pmod{26}$

Affine Cipher

아핀 암호(affine cipher)
- 덧셈 암호와 곱셈 암호의 결합
- 가능한 키의 가짓수는 $26$ (덧셈) $\times$ $12$ (곱셈) $=312$ 가지
- Definition.
  - $M = C = \mathbb Z_{26}$
  - $K = \{(k_1, k_2) \in \mathbb Z^*_{26} \times \mathbb Z_{26}\}$
  - $Enc_k(m) \equiv k_1 \times m + k_2 \pmod {26}$
  - $Dec_k(c) \equiv k_1^{-1} \times (c - k_2) \pmod {26}$

Monoalphabetic Substitution Cipher

치환 암호(substitution cipher)
- 각 문자에 적용되는 $𝑘$ 가 같거나 다름
- 사용 가능한 키의 개수는 총 $26 × 25 × ⋯ × 1 = 26!$ (약 $10^{26}$ 가지)
  - 전사적 공격을 이용하여 키를 찾는 것은 사실상 불가능
  - 1초에 $10^9$ 개의 키를 조사해도 120억년 이상 시간이 필요
- Definition.
  - $M = C = \mathbb Z_{26}$
  - $K = \{ 𝑘: \mathbb Z_{26}$ 상의 순열(permutation) 함수 $\pi_𝑘 \}$
  - $𝐸𝑛𝑐_k(𝑚) ≡ \pi_k(𝑚)$
  - $𝐷𝑒𝑐_k(𝑐) ≡\pi^{-1}(𝑐)$
치환 암호 분석
- 평문을 특정 의미를 갖도록 구성하면 그 문장은 사용 언어의 통계적인 특성을 갖게 됨.
  - 988,968개의 영어 단어 중 "E"가 사용되는 횟수는 12.7%
- 암호문은 평문을 단순 치환한 형태이므로 통계적 특성을 그대로 유지함.

Vigenère Cipher

비제네르 암호(=비장느르 암호, Vigenère Cipher, 1586)
- 특정 길이의 키워드를 비밀키로 사용
- 다중 문자 치환 암호 (polyalphabetic substitution cipher)
  - 하나의 문자가 여러 개의 문자로 치환됨
- Definition.
  - $M=C=K=\mathbb Z^l_{26}$
  - $𝐸𝑛𝑐_𝑘(𝑚) = [𝑚_1+𝑘_1 \pmod{26}, 𝑚_2+𝑘_2 \pmod{26}, ..., 𝑚_l+𝑘_l \pmod{26}]$
  - $𝐷𝑒𝑐_𝑘(𝑐) ≡ [𝑐_1−𝑘_1 \pmod{26},𝑐_2−𝑘_2 \pmod{26}, ..., 𝑐_l−𝑘_l \pmod{26}]$
비제네르 암호 분석
- Kasiski method(1863): 키워드의 길이를 찾아내는 방법
- 암호문 내 반복되는 문자열이 있을 경우
  1. 평문의 같은 문자가 키워드의 동일한 부분과 만나 같은 문자로 치환
  2. 서로 다른 문자이지만 키워드의 다른 부분과 각각 만나 같은 문자로 치환
- 반복된 거리의 약수가 키워드의 길이가 될 확률이 높음
  - 각각의 문자열이 반복된 거리를 찾은 후 최대공약수를 구함
- 키워드 길이를 주기로 단일 문자 치환 암호와 같은 특성을 가지게 됨

Transposition Cipher

전치 암호(transposition cipher)
- 길이 $l$ 의 블록으로 나눠진 평문의 문자열을 재배열하여 암호화 ( $l!$ 개의 키가 존재)
  - 평문의 길이를 통해 블록의 길이를 유추할 수 있어 효율적으로 전사적 공격가능.
- 빈도수 분석에 취약함
  - 두 문자, 세 문자에 대한 빈도수는 변경되지만 한문자에 대한 빈도수는 유지됨.
- Definition.
  - $M = C = \mathbb Z^l_{26}$
  - $K= \{ 𝑘:$ 길이가 $l$ 인 문자열의 순열(permutation) 함수 $\pi_k \}$
  - $𝐸𝑛𝑐_k(𝑚) ≡ \pi_k(𝑚)$
  - $𝐷𝑒𝑐_k(𝑐) ≡ \pi^{−1}(𝑐)$

Security of Cryptosystems

암호 시스템의 안전성
- 암호 시스템이 안전하다의 의미?
- 안전성 개념을 위해서 공격자를 정의하는 것이 선행되어야 함
  - 공격 목표: 비밀키 복구, 평문 유추, ...
  - 공격 유형 (attack type):
    - COA: Ciphertext Only Attack, 암호문 단독 공격
    - KPA: Known Plaintext Attack, 알려진 평문 공격
    - CPA: Chosen Plaintext Attack, 선택 평문 공격
    - CCA: Chosen Ciphertext Attack, 선택 암호문 공격
  - 보안 목표 (security goals):
    - UBK: unbreakable, 복호화 키를 알아내는 것에 대한 내성
    - OW: one-way, 암호문에 대한 평문을 유추해 내는 것에 대한 내성
    - IND: indistinguishability, 암호문이 자신이 선택한 평문 2개 중 어떤 것으로 암호화 되었는지 구별하는 공격에 내성
    - NM: non-malleability, 주어진 암호문 $c=Enc(m)$ 을 이용해 $m$ 을 몰라도 새로운 암호문 $c'=Enc(f(m))$ 을 만들어 낼 수 있는지에 대한 내성
  - 관계(여기서 PCA는 Plaintext-Checking Attack)
  - 계산 능력: 무한한 계산능력, 현실적으로 가능한 수준, ...
    - 현실적이란? 현 시점의 컴퓨팅 파워를 고려하여 수 개월, 수 년, ...
암호문 단독 공격(Ciphertext Only Attack, COA)
- 암호문 샘플 있음
- 공격자가 얻을 수 있는 정보가 암호문인 경우
  - 대표적인 수동적 공격 (e.g. 도청 공격)
  - 공격자의 목표는 다양하게 정의할 수 있음
  - 복호화 키를 알아냄 (UBK)
  - 암호문에 대한 평문을 유추해 냄 (OW)
  - 암호문이 자신이 선택한 평문 2개 중 어떤것으로 암호화 되었는지 구별함 (IND)
알려진 평문 공격 (Known Plaintext Attack, KPA)
- (평문,암호문) 샘플 있음
- 공격자가 암호문뿐만 아니라 이에 대응하는 평문도 가지고 있는 경우
  - 평문/암호문 쌍 $(𝑚_1,𝑐_1), ..., (𝑚_𝑛,𝑐_𝑛)$ 을 가지고 있음
- 새로운 암호문 $𝑐^∗$ 에 대하여 공격을 수행함
- 수동적 공격
선택 평문 공격(Chosen Plaintext Attack, CPA)
- 암호화 마음대로 가능
- 공격자가 원하는 평문 $𝑚_1,...,𝑚_𝑛$ 에 대하여 암호문 $𝑐_1,...,𝑐_𝑛$ 을 얻을 수 있는 경우
  - ex. 송신자의 컴퓨터를 해킹해서 암호화 프로그램을 사용할 수 있는 환경
- 암호화 오라클(encryption oracle): 평문을 입력하면 대응하는 암호문을 출력함
- 오라클에게 답변받지 않은 새로운 암호문 $𝑐^∗$ 에 대하여 공격 수행
- 능동적 공격
선택 암호문 공격(Chosen Ciphertext Attack, CCA)
- 복호화 마음대로 가능
- 공격자가 선택한 $𝑐_1,...,𝑐_𝑛$ 에 대하여 $𝑚_1,...,𝑚_𝑛$ 를 알아낼 수 있는 경우
  - ex. 수신자의 복호화 프로그램을 (제한적으로) 사용할 수 있는 환경
- 복호화 오라클(decryption oracle): 암호문을 입력하면 대응하는 평문을 출력함
- 오라클에 질의하지 않은 새로운 암호문 $𝑐^∗$ 에 대하여 공격 수행
- 능동적 공격