3-1) 시스템소프트웨어

1. 대칭 암호화 (Symmetric Encryption) 기본 구조

Alice → E(k, m) = c → Bob → D(k, c) = m

암호화 알고리즘은 공개되어 있다. 절대로 독자적인 암호를 만들지 말 것.

키 사용 방식

• One-time key: 메시지 하나에 키 하나
• Many-time key: 여러 메시지에 동일 키 사용 → 추가적인 장치 필요

2. 역사 (History of Ciphers)

대칭 암호 (Symmetric Ciphers)

• 알파벳을 다른 알파벳으로 치환
• Caesar Cipher: 키 없이 고정된 이동값 사용
• 키 공간 크기 (26자 기준): 26! ≈ 2⁸⁸

해독 방법

• 영어 알파벳 빈도 분석 (가장 흔한 글자 → 'E')
• 두 글자 쌍(digram), 세 글자 쌍(trigram) 빈도 분석

k = C R Y P T O C R Y P T O ...
m = W H A T A N I C E D A Y ...
c = Z Z Z J U C L U D T U N ...
(+mod 26)

해독: 가장 빈번한 암호문 글자가 'H'라면, 키의 첫 글자 = 'H' - 'E' = 'C'

• 초기 예: Hebern machine (단일 로터)
• 가장 유명한 예: Enigma (3~5개 로터)
  • 키 수: 2⁶⁴ = 2¹⁸ (플러그보드 포함 시 실제 2³⁶)

• 키 수: 2⁵⁶, 블록 크기: 64 bits
• 현재는 AES (2001), Salsa20 (2008) 등 사용

3. 이산 확률 (Discrete Probability)

암호학에서 이산 확률이 왜 필요한가?

암호 알고리즘은 키를 랜덤하게 뽑는다. "얼마나 안전한가"를 수학적으로 표현하려면 확률 언어가 필요하다.

① 표본 공간 (Universe) U

U는 모든 가능한 결과의 집합 (유한 집합)

암호학에서 가장 자주 쓰이는 표본 공간:

U = {0,1}ⁿ  ← n비트 문자열 전체

n=2 이면: U = {00, 01, 10, 11}  (원소 4개)
n=3 이면: U = {000, 001, 010, 011, 100, 101, 110, 111}  (원소 8개)

② 확률 분포 (Probability Distribution)

정의: 함수 P: U → [0,1] 이고 Σ P(x) = 1 (x∈U)

예시 1 — 균등 분포 (Uniform Distribution): 모든 원소가 동일 확률

U = {00, 01, 10, 11}
P(00) = P(01) = P(10) = P(11) = 1/4

→ 일반식: P(x) = 1/|U|

예시 2 — 점 분포 (Point Distribution): 하나의 원소에 확률 1

U = {00, 01, 10, 11},  x₀ = 10 이라면
P(10) = 1,  P(00) = P(01) = P(11) = 0

암호학과의 연결: 키 k를 균등 분포로 뽑는다 = 모든 가능한 키 중 하나를 완전히 랜덤하게 선택한다는 뜻

③ 이벤트 (Event)

정의: 이벤트 A는 U의 부분집합 (A ⊆ U)

확률: Pr[A] = Σ P(x), x∈A

구체적 예시: U = {0,1}⁸ (8비트 문자열, 원소 256개), 균등 분포

A = { x ∈ U | 하위 2비트가 11인 x }
    = {00000011, 00000111, 00001011, ..., 11111111}
    → 총 64개 원소 (256 / 4)

Pr[A] = 64/256 = 1/4

직관: 8비트 중 마지막 2비트가 "11"일 확률 = (1/2)×(1/2) = 1/4

④ 합집합 경계 (Union Bound)

정리: Pr[A₁ ∪ A₂] ≤ Pr[A₁] + Pr[A₂]

왜 등호가 아닌가? A₁과 A₂가 겹치는 원소는 두 번 더해지므로 실제 확률은 이 합보다 작거나 같다.

구체적 예시: U = {0,1}ⁿ, 균등분포

A₁ = { x | lsb₂(x) = 11 }  → Pr[A₁] = 1/4
A₂ = { x | msb₂(x) = 11 }  → Pr[A₂] = 1/4

Pr[하위 2비트=11 또는 상위 2비트=11]
  = Pr[A₁ ∪ A₂]
  ≤ 1/4 + 1/4 = 1/2

암호학과의 연결: "어떤 공격이 성공할 확률"을 여러 경우로 나눠 각각 bound를 구하고 합산하는 데 쓰인다.

⑤ 확률 변수 (Random Variable)

정의: 확률 변수 X는 함수 X: U → V

• 표본 공간 U의 원소를 값 집합 V의 원소로 매핑
• X가 V 위에 새로운 분포를 유도함

구체적 예시: U = {0,1}ⁿ, V = {0,1}

X(y) = lsb(y)  ← y의 마지막 비트

U의 원소들:
  ...0  → X = 0  (절반)
  ...1  → X = 1  (절반)

Pr[X = 0] = 1/2
Pr[X = 1] = 1/2

또 다른 예시: U = {0,1}², X = r₁ + r₂ (두 비트의 합)

원소  X값
00   → 0
01   → 1
10   → 1
11   → 2

Pr[X=0] = 1/4,  Pr[X=1] = 2/4 = 1/2,  Pr[X=2] = 1/4

⑥ 균등 랜덤 변수 (Uniform Random Variable)

표기: r ←ᴿ U (r을 U에서 균등하게 뽑는다)

모든 a∈U에 대해 Pr[r = a] = 1/|U|

암호학에서 가장 중요한 개념 중 하나. 키를 "랜덤하게" 뽑는다는 것이 바로 이것.

⑦ 독립 (Independence)

이벤트 A, B가 독립: Pr[A ∩ B] = Pr[A] · Pr[B]

확률 변수 X, Y가 독립: ∀a,b∈V: Pr[X=a ∧ Y=b] = Pr[X=a] · Pr[Y=b]

구체적 예시: U = {00, 01, 10, 11}, r ←ᴿ U

X = lsb(r)  (마지막 비트)
Y = msb(r)  (첫 번째 비트)

Pr[X=0 ∧ Y=0] = Pr[r=00] = 1/4
Pr[X=0] · Pr[Y=0] = 1/2 · 1/2 = 1/4  ✓

→ X와 Y는 독립!

독립이 아닌 예시: X = lsb(r), Z = X (당연히 Z=X와 연동됨)

Pr[X=0 ∧ Z=1] = 0  (불가능)
Pr[X=0] · Pr[Z=1] = 1/2 · 1/2 = 1/4 ≠ 0  → 독립 아님

⑧ XOR의 핵심 성질

XOR란?: 두 비트열의 비트 단위 덧셈 (mod 2)

  0 1 1 0 1 1 1
⊕ 1 0 1 1 0 1 0
= 1 1 0 1 1 0 1

[핵심 정리] Y가 {0,1}ⁿ 위의 임의 확률변수, X가 독립적인 균등 확률변수일 때:

Z := Y ⊕ X 는 균등 확률변수

증명 (n=1 경우):

Pr[Z=0] = Pr[Y⊕X = 0]
         = Pr[Y=0 ∧ X=0] + Pr[Y=1 ∧ X=1]   ← Y⊕X=0이 되려면 Y=X
         = Pr[Y=0]·Pr[X=0] + Pr[Y=1]·Pr[X=1]   ← 독립성 사용
         = Pr[Y=0]·(1/2) + Pr[Y=1]·(1/2)
         = (1/2)·(Pr[Y=0] + Pr[Y=1])
         = (1/2)·1  =  1/2  ✓

→ Z=0과 Z=1이 각각 1/2 확률 → 균등분포

암호학과의 연결: OTP의 완전 비밀성이 바로 이 성질에서 나온다.

m(평문)이 어떤 분포든, k(키)가 균등하면 c = m⊕k 도 균등 → 암호문에서 평문 정보를 얻을 수 없음

⑨ 생일 역설 (Birthday Paradox)

상황: r₁, r₂, ..., rₙ ∈ U 를 독립적·균등하게 뽑을 때, 같은 값이 두 번 나올 확률

정리: n = 1.2 × |U|^(1/2) 이면 Pr[∃i≠j: rᵢ = rⱼ] ≥ 1/2

직관적 이해: 1년 365일 중 생일이 같은 사람 두 명이 있으려면 몇 명이 필요할까?

|U| = 365
√365 ≈ 19.1
1.2 × 19.1 ≈ 23명

→ 23명만 모여도 생일이 같은 쌍이 있을 확률 ≥ 50%

암호학에서의 중요성:

|U| = {0,1}¹²⁸  →  |U| = 2¹²⁸
√(2¹²⁸) = 2⁶⁴

→ 2⁶⁴개만 샘플링해도 같은 값이 나올 확률 ≥ 50%

이것이 실제로 중요한 이유: 예를 들어 128비트 난수를 키로 쓸 때, 2⁶⁴번 이상 키를 재생성하면 충돌(같은 키 재사용) 가능성이 높아진다. 암호 시스템 설계 시 반드시 고려해야 한다.

1. 대칭 암호 정의 (Symmetric Cipher)

정의: (K, M, C) 위에서 정의된 암호는 "효율적" 알고리즘 쌍 (E, D)

• E는 종종 확률적(randomized), D는 항상 결정론적(deterministic)
• ∀m∈M, k∈K: D(k, E(k, m)) = m (정확성 조건)

2. One Time Pad (OTP)

Vernam (1917) — 최초의 "안전한" 암호

• 키 = 메시지와 같은 길이의 랜덤 비트 문자열
• 암호화: c = m ⊕ k
• 복호화: m = c ⊕ k

예시

msg: 0 1 1 0 1 1 1
key: 1 0 1 1 0 1 0
CT:  1 1 0 1 1 0 1

OTP 키 복원: k = m ⊕ c (평문과 암호문을 알면 키를 바로 구할 수 있음)

OTP의 특징

• 매우 빠른 암호화/복호화
• 단점: 키가 평문만큼 길어야 함

3. 완전 비밀성 (Perfect Secrecy)

Shannon (1949) 정보이론적 보안

정의: 암호 (E,D)가 (K,M,C)에서 완전 비밀성을 가진다.

∀m₀, m₁ ∈ M (|m₀| = |m₁|) 이고 ∀c∈C:

Pr[E(k, m₀) = c] = Pr[E(k, m₁) = c] (k ←ᴿ K)

→ 암호문으로부터 평문에 대한 어떤 정보도 얻을 수 없음

보조정리: OTP는 완전 비밀성을 가진다.

나쁜 소식: 완전 비밀성 → 키 길이 ≥ 메시지 길이

4. 스트림 암호 (Stream Ciphers)

아이디어: OTP에서 "랜덤" 키를 "유사난수(pseudorandom)" 키로 대체

PRG (Pseudorandom Generator): G: K → {0,1}ⁿ

• 시드(seed) k에서 긴 유사난수 시퀀스 생성
• 스트림 암호: E(k, m) = m ⊕ G(k), D(k, c) = c ⊕ G(k)

스트림 암호는 완전 비밀성을 가질 수 없다! (키가 메시지보다 짧으므로)

→ 다른 보안 정의 필요

5. PRG 보안 요건

PRG는 예측 불가능해야 함 (Unpredictable)

정의: G: K → {0,1}ⁿ이 예측 가능하다면:

어떤 효율적 알고리즘 A가 존재하여, G(k)의 첫 i 비트로 (i+1)번째 비트를 non-negligible 확률로 예측

PRG가 예측 불가능 ⟺ ∀i: 어떤 효율적인 공격자도 (i+1)번째 비트를 non-negligible ε로 예측 불가능

약한 PRG 예시 (사용 금지)

• glibc random(): r[i] ← (r[i-3] + r[i-31]) % 2³² 출력 r[i] >> 1

6. Negligible vs Non-negligible

이론적 정의 (ε는 보안 파라미터 λ의 함수):

• Non-neg: ∃d: ε(λ) ≥ 1/λᵈ (무한히 자주)
• Negligible: ∀d, λ≥λ_d: ε(λ) ≤ 1/λᵈ

예시

• ε(λ) = 1/2^λ → Negligible
• ε(λ) = 1/λ¹⁰⁰⁰ → Non-negligible

7. OTP 및 스트림 암호 공격

공격 1: Two Time Pad (키 재사용 금지!)

같은 키로 두 메시지를 암호화하면:

C₁ = m₁ ⊕ PRG(k)
C₂ = m₂ ⊕ PRG(k)
C₁ ⊕ C₂ = m₁ ⊕ m₂

→ 영어/ASCII의 중복성으로 m₁, m₂ 복원 가능

실제 사례

• Project Venona (소련 첩보 해독)
• MS-PPTP (Windows NT): 클라이언트→서버, 서버→클라이언트에 다른 키 필요
• 802.11b WEP 취약점: IV = 24비트 → 2²⁴ ≈ 16M 프레임 후 IV 재사용

공격 2: 무결성 없음 (OTP는 malleable)

enc(⊕k): m  →  m⊕k
⊕p             ↓
dec(⊕k): (m⊕k)⊕p = m⊕p

암호문에 대한 수정이 감지되지 않고, 평문에 예측 가능한 영향을 미침

예: "From: Bob" → "From: Eve" 로 변조 가능

스트림 암호 키는 절대 두 번 사용하지 말 것!

- 네트워크: 세션마다 새 키 협상 (e.g. TLS)

- 디스크 암호화: 스트림 암호 사용 지양

8. 실제 스트림 암호들

RC4 (1987, Software)

• 시드: 128비트 → 1바이트/라운드 출력
• HTTPS, WEP에 사용
• 취약점:
  • 두 번째 바이트 편향: Pr[2nd byte = 0] = 2/256
  • (0,0) 연속 확률 이상
  • 연관 키(related key) 공격

CSS (Hardware, 취약)

• DVD 암호화: 2개의 LFSR(Linear Feedback Shift Register)
• GSM A5/1,2: 3개 LFSR
• Bluetooth E0: 4개 LFSR
• CSS 공격: 2¹⁷ 시간복잡도로 해독 가능

eStream: Salsa20 (현대)

• Salsa20: {0,1}¹²⁸ or ²⁵⁶ × {0,1}⁶⁴ → {0,1}ⁿ (최대 n = 2⁷³ bits)
• Nonce: 주어진 키에 대해 반복되지 않는 값
• E(k, m; r) = m ⊕ PRG(k; r) ← (k, r) 쌍은 한 번만 사용

성능 비교 (AMD Opteron 2.2GHz)

9. PRG 보안 정의

통계적 테스트 (Statistical Test)

A: {0,1}ⁿ → {0, 1} (출력이 랜덤처럼 보이는지 판단)

Advantage (우위)

Adv_PRG[A, G] = | Pr[A(G(k))=1] - Pr[A(r)=1] |

• A(x) = 0이면 항상 → Adv = 0
• G의 편향이 있으면 Adv > 0

안전한 PRG 정의

G: K → {0,1}ⁿ이 안전한 PRG ⟺ 모든 효율적 통계 테스트 A에 대해 Adv_PRG[A,G]가 negligible

안전한 PRG ⇒ 예측 불가능 (Yao'82: 그 역도 성립)

10. 의미론적 보안 (Semantic Security)

직관: 암호문은 평문에 대한 어떤 정보도 노출하지 않아야 함

정의 (one-time key):

• Challenger가 m_b를 E(k, m_b)로 암호화
• 공격자 A가 b'을 추측
• Adv_SS[A, E] = |Pr[W₀] - Pr[W₁]|

E가 의미론적으로 안전 ⟺ 모든 효율적 공격자 A에 대해 Adv_SS[A, E]가 negligible

OTP는 의미론적으로 안전하다 (완전 비밀성에서 직접 따름)

핵심 정리:

G가 안전한 PRG이면 G에서 유도된 스트림 암호 E는 의미론적으로 안전하다.

∀sem.sec. 공격자 A에 대해 ∃PRG 공격자 B s.t.:

Adv_SS[A, E] ≤ 2 · Adv_PRG[B, G]

1. 블록 암호란? (What is a Block Cipher?)

블록 암호는 암호학의 핵심 도구(crypto workhorse)다.

n비트 평문 블록 → [E / D, 키 k] → n비트 암호문 블록

대표 예시

2. 반복 구조 (Block Ciphers Built by Iteration)

블록 암호는 라운드 함수(Round Function) R(k, m)을 반복 적용해 만든다.

키 k → [키 확장] → k₁, k₂, ..., kₙ

평문 m → R(k₁,·) → R(k₂,·) → ... → R(kₙ,·) → 암호문 c

3. PRF와 PRP (추상적 정의)

PRF (Pseudo Random Function)

정의: F: K × X → Y

• (K, X, Y) 위에서 정의
• F(k, x)를 효율적으로 계산할 수 있는 알고리즘 존재

PRP (Pseudo Random Permutation) = 블록 암호

정의: E: K × X → X

1. E(k, x)를 효율적으로 계산 가능
2. E(k, ·)는 일대일(one-to-one) 함수
3. 역함수 D(k, y)도 효율적으로 계산 가능

Note: 관계: PRP는 X=Y이고 역함수가 존재하는 PRF다. 즉 모든 PRP는 PRF이기도 하다.

운영 예시

• AES: K = X = {0,1}¹²⁸
• 3DES: X = {0,1}⁶⁴, K = {0,1}¹⁶⁸

안전한 PRF란?

• Funs[X,Y]: X→Y인 모든 함수의 집합, 크기 = |Y|^|X| (천문학적으로 큼)
• S_F = { F(k,·) | k∈K } ⊆ Funs[X,Y], 크기 = |K|

직관: S_F의 랜덤 함수와 Funs[X,Y]의 랜덤 함수를 구별할 수 없으면 안전

게임으로 표현하면:

주의할 예시 — 안전하지 않은 PRF:

→ x=0을 질의하면 항상 0이 나오므로 랜덤 함수와 즉시 구별 가능. 안전하지 않음.

안전한 PRP (Secure PRP = Secure Block Cipher)

• Perms[X]: X 위의 모든 일대일 함수(순열)의 집합
• S_E = { E(k,·) | k∈K } ⊆ Perms[X]

직관: 적(adversary)이 다음 두 상황을 구별할 수 없으면 안전

즉, S_E에서 뽑은 랜덤 함수와 Perms[X]에서 뽑은 진짜 랜덤 순열을 구별할 수 없으면 안전한 PRP.

Note: 안전한 PRF와의 차이는 비교 대상이 Funs[X,Y] 대신 Perms[X]라는 것. PRP는 역함수가 존재하는 순열이므로 비교 대상도 순열 집합으로 좁혀짐.

4. DES (Data Encryption Standard)

Feistel 네트워크

DES의 핵심 아이디어. 임의 함수 f₁,...,f_d로 가역(invertible) 함수를 만드는 구조.

입력: (L₀, R₀)  ← 2n비트

각 라운드 i:
  Rᵢ = f_i(Rᵢ₋₁) ⊕ Lᵢ₋₁
  Lᵢ = Rᵢ₋₁

출력: (L_d, R_d)

역함수 (복호화):

Rᵢ₋₁ = Lᵢ
Lᵢ₋₁ = f_i(Lᵢ) ⊕ Rᵢ

Luby-Rackoff 정리 (1985): f가 안전한 PRF이면, 3-라운드 Feistel은 안전한 PRP(블록 암호)다.

DES는 이를 16라운드로 사용.

DES의 라운드 함수 F(kᵢ, x)

• S-box: {0,1}⁶ → {0,1}⁴ 의 룩업 테이블 (8개)
• P-box: 비트 순열

나쁜 S-box의 예 (선형 함수):

S(x) = Aᵢ·x (mod 2) 형태면 → DES 전체가 선형

• DES(k, m₁) ⊕ DES(k, m₂) ⊕ DES(k, m₃) = DES(k, m₁⊕m₂⊕m₃) 가 성립
• 이러면 매우 쉽게 해독 가능!

좋은 S/P-box 설계 원칙:

• 출력 비트가 입력 비트의 선형 함수에 가깝지 않을 것
• S-box는 4-to-1 매핑

5. 전수 탐색 공격 (Exhaustive Search)

목표: 입출력 쌍 (mᵢ, cᵢ) 몇 개가 주어졌을 때 키 k 찾기

보조정리: DES가 이상적 암호라면, 평문-암호문 쌍이 주어질 때 조건을 만족하는 키는 높은 확률로 유일하다.

• DES: 입출력 쌍 2개면 키 유일 (확률 ≈ 1 - 1/2⁷¹)
• AES-128: 입출력 쌍 2개면 키 유일 (확률 ≈ 1 - 1/2¹²⁸)

DES Challenge 결과

Warning: 결론: 56비트 키 암호는 절대 사용하지 말 것! (128비트 키면 → 2⁷² 일 소요)

DES 강화: Triple-DES (3DES)

3E((k₁,k₂,k₃), m) = E(k₁, D(k₂, E(k₃, m)))

• 키 크기: 3 × 56 = 168비트
• DES보다 3배 느림
• 최선 공격: ≈ 2¹¹⁸ (Double-DES의 Meet-in-the-Middle 공격보다 안전)

Double DES를 쓰지 않는 이유: Meet-in-the-Middle 공격

• 2E((k₁,k₂), m) = E(k₁, E(k₂, m))
• 키 길이는 112비트지만 실제 보안은 56비트 수준 (각 방향에서 절반씩 탐색)

6. AES (Advanced Encryption Standard)

• 키 크기: 128 / 192 / 256 비트
• 블록 크기: 128 비트

AES 구조: Substitution-Permutation Network

DES(Feistel)와 달리 Subs-Perm 네트워크 사용.

AES-128: 10라운드, 각 라운드에서 3가지 연산

1. ByteSub: 1바이트 S-box (256-byte 룩업 테이블)
2. ShiftRow: 행 단위 순환 시프트
3. MixColumn: 열 단위 선형 변환

k₀ → [ByteSub + ShiftRow + MixColumn + ⊕k₁] → ... → [ByteSub + ShiftRow + ⊕k₁₀] → 출력
키 확장: 16 bytes → 176 bytes

7. PRG로 PRF/PRP 만들기

PRG → 1비트 PRF

G: K → K²  (안전한 PRG)

F(k, x∈{0,1}) = G(k)[x]
              = G(k)[0]  (x=0일 때)
              = G(k)[1]  (x=1일 때)

도메인 확장: GGM PRF

G: K → K²

F(k, x₀x₁...xₙ₋₁ ∈ {0,1}ⁿ) =
  k₀ = G(k)[x₀]
  k₁ = G(k₀)[x₁]
  ...
  kₙ = G(kₙ₋₁)[xₙ₋₁]

• G가 안전한 PRG → F는 {0,1}ⁿ 위의 안전한 PRF
• 이론적으로 중요하지만 실제로는 느려서 잘 안 씀

결론: 안전한 PRG → 안전한 PRF (GGM) → 안전한 PRP (Luby-Rackoff, 3라운드 Feistel)

1. ECB (Electronic Code Book) - 잘못된 방식

평문: m₁ | m₂
      ↓     ↓
     E(k) E(k)
      ↓     ↓
암호문: c₁ | c₂

문제점: m₁ = m₂이면 c₁ = c₂ → 패턴이 그대로 노출!

ECB가 의미론적으로 안전하지 않음을 증명:

공격자 A:
m₀ = "Hello World"  (두 블록이 다름)
m₁ = "Hello Hello"  (두 블록이 같음)

암호화 후 c₁ = c₂이면 → m₁으로 판단
→ Adv_SS[A, ECB] = 1  (완전히 안전하지 않음)

유명한 예: Linux 펭귄 이미지를 ECB로 암호화하면 펭귄 윤곽이 그대로 보임

3. 결정론적 카운터 모드 (Det. Counter Mode)

PRF F를 이용한 구성:

E_DETCTR(k, m):

m[0]  m[1]  m[2]  ...  m[L]
 ⊕     ⊕     ⊕          ⊕
F(k,0) F(k,1) F(k,2) ... F(k,L)
 ↓     ↓     ↓          ↓
c[0]  c[1]  c[2]  ...  c[L]

→ PRF(예: AES)로 만든 스트림 암호

보안 정리: F가 안전한 PRF이면 E_DETCTR는 one-time key 하에서 의미론적으로 안전하다.

• Adv_SS[A, E_DETCTR] = 2 · Adv_PRF[B, F]

4. Many-time Key: CPA 보안

문제: 같은 평문 → 같은 암호문이면 안 됨

같은 키로 같은 평문을 두 번 암호화할 때 항상 같은 암호문이 나오면:

• 공격자가 두 암호화된 파일이 동일한지 알 수 있음
• 작은 메시지 공간에서 치명적

핵심 원칙: 같은 키로 같은 평문을 두 번 암호화하면 반드시 다른 암호문이 나와야 한다.

CPA (Chosen-Plaintext Attack) 보안 정의

• 공격자가 원하는 평문의 암호문을 여러 번 얻을 수 있음
• 그래도 의미론적 보안이 유지되어야 함

for i=1,...,q:
  공격자가 (mᵢ,₀, mᵢ,₁) 선택
  챌린저가 cᵢ = E(k, mᵢ,ᵦ) 반환

Adv_CPA[A,E] = |Pr[EXP(0)=1] - Pr[EXP(1)=1]| 이 negligible이어야 함

해결책 1: 무작위 암호화 (Randomized Encryption)

• E(k, m)이 확률적 알고리즘 → 같은 평문을 두 번 암호화해도 다른 암호문
• 단점: 암호문이 평문보다 길어짐 (CT 크기 = PT 크기 + 랜덤 비트 수)

해결책 2: Nonce 기반 암호화

Alice                              Bob
m, nonce n → E(k, m, n) = c → c, n → D(k, c, n) = m

• nonce: 메시지마다 바뀌는 값. (키, nonce) 쌍은 절대 재사용 금지
• 방법 1: nonce = 카운터 (상태 유지 시)
• 방법 2: nonce = 랜덤 값 (n ←ᴿ N)

5. CBC 모드 (Cipher Block Chaining)

랜덤 IV를 사용한 CBC

IV  m[0]   m[1]   m[2]   m[3]
    ⊕       ⊕      ⊕      ⊕
   E(k,·) E(k,·) E(k,·) E(k,·)
    ↓       ↓      ↓      ↓
IV  c[0]   c[1]   c[2]   c[3]

• IV (Initialization Vector): 매번 랜덤하게 선택
• 암호문에 IV가 포함되어 전송됨

복호화:

m[0] = D(k, c[0]) ⊕ IV
m[i] = D(k, c[i]) ⊕ c[i-1]

CBC 보안 정리

정리: E가 (K,X)에서 안전한 PRP이면, E_CBC는 (K, X^L, X^(L+1))에서 CPA 의미론적 보안을 가진다.

Adv_CPA[A, E_CBC] ≤ 2·Adv_PRP[B, E] + 2q²L²/|X|

• q: 동일 키로 암호화한 메시지 수
• L: 메시지 최대 길이 (블록 수)
• 안전 조건: q²L² << |X|

예시 (Adv ≤ 1/2³²를 원할 때):

• AES (|X|=2¹²⁸): q·L < 2⁴⁸ → 2⁴⁸ AES 블록 후 키 교체 필요
• 3DES (|X|=2⁶⁴): q·L < 2¹⁶

CBC 주의사항: IV 예측 가능하면 안 됨!

공격자가 다음 IV를 예측할 수 있으면 CPA 공격 가능:

공격자:
  m₀ = IV₁ ⊕ IV  (IV₁: 다음 예측 IV, IV: 현재 IV)
  → 결과적으로 E(k, 0⊕IV₁)이 되어 패턴 노출

실제 버그: SSL/TLS 1.0에서 레코드 i의 IV = 레코드 (i-1)의 마지막 암호문 블록 → 예측 가능 → 공격 가능!

Nonce 기반 CBC

키 = (k, k₁) 사용
nonce → E(k₁, nonce) → IV → CBC 진행

CBC 패딩

메시지가 블록 크기의 배수가 아닐 때:

• TLS: n바이트 패딩 = n n n ... n (n개)
• 패딩이 필요 없는 경우에도 더미 블록 추가

6. CTR 모드 (Counter Mode)

랜덤 IV를 사용한 CTR

IV  m[0]    m[1]    ...  m[L]
     ⊕        ⊕               ⊕
F(k,IV) F(k,IV+1) ... F(k,IV+L)
     ↓        ↓               ↓
IV  c[0]    c[1]    ...  c[L]

• F는 PRF (복호화 시 역함수 불필요, 암호화만 사용)
• 병렬 처리 가능 (CBC와 달리)

Nonce 기반 CTR

IV = [64비트 nonce | 64비트 카운터(0부터 시작)]

→ (k, IV) 쌍이 절대 겹치지 않도록 보장

CTR 보안 정리

Adv_CPA[A, E_CTR] ≤ 2·Adv_PRF[B, F] + 2q²L/|X|

• CBC보다 더 나은 안전 한계 (q²L vs q²L²)
• AES (|X|=2¹²⁸): q·L^(1/2) < 2⁴⁸ → 총 2⁶⁴ AES 블록 후 키 교체

7. CBC vs CTR 비교

💡 실용적으로는 CTR 모드가 더 유연하고 효율적이다.

8. 전체 요약

⚠️ 중요: 위 모드들은 모두 기밀성(confidentiality)만 보장. 무결성(integrity)은 별도 메커니즘 필요!

참고 논문:

• Bellare et al., "Analysis of the DES modes of operation", FOCS 1997
• Rogaway, "Nonce-Based Symmetric Encryption", FSE 2004

1. 해시 함수란?

해시 함수: H: M → T (|M| >> |T|)

• 임의 길이 입력 → 고정 길이 출력(digest)
• 큰 집합 M을 작은 집합 T로 압축 → 비둘기집 원리에 의해 충돌은 반드시 존재

두 가지 주요 종류

2. 충돌 저항성 (Collision Resistance)

충돌(Collision): m₀, m₁ ∈ M이 충돌 ⟺ H(m₀) = H(m₁) 이고 m₀ ≠ m₁

충돌 저항 정의: H가 충돌 저항적이다

⟺ 모든 효율적 알고리즘 A에 대해

Adv_CR[A, H] = Pr[A가 H의 충돌을 출력] 이 negligible

예: SHA-256 (출력 256비트)

3. 해시 함수의 세 가지 조건

좋은 암호학적 해시 함수가 만족해야 할 조건:

① 계산 용이성 (Easy to compute)

• M이 주어지면 H(M)을 쉽게 계산 가능

② 역상 저항성 (One-wayness / Preimage Resistance)

• 어떤 h가 주어져도, H(M) = h인 M을 찾는 것이 어려워야 한다

③ 충돌 저항성 (Collision Resistance)

• M₁이 주어졌을 때, H(M₁) = H(M₂)인 M₂를 찾는 것이 어려워야 한다

구체적 예시

// 나쁜 예 — 너무 단순한 해시
H("Elvis") = (E+L+V+I+S) mod 26
           = (5+12+22+9+19) mod 26
           = 67 mod 26 = 15

// 충돌 예시
H("Viva")  = (V+I+V+A) mod 26 = 2
H("Vegas") = (V+E+G+A+S) mod 26 = 2
→ 다른 입력, 같은 출력 → 충돌!

이런 단순 해시는 의도적 충돌을 만들기 너무 쉬워서 암호학적으로 사용 불가.

4. 생일 역설과 충돌 공격

생일 역설 복습

r₁, ..., rₙ ∈ {1, ..., B}가 균등 독립 정수일 때:

n = 1.2 × B^(1/2) 이면 Pr[∃i≠j: rᵢ = rⱼ] ≥ 1/2

해시 함수에 대한 일반적 충돌 공격

H: M → {0,1}ⁿ 에 대해 O(2^(n/2)) 시간에 충돌을 찾는 알고리즘:

알고리즘:
1. 랜덤 메시지 2^(n/2)개 선택: m₁, ..., m_{2^(n/2)}
2. 각각에 대해 tᵢ = H(mᵢ) 계산
3. tᵢ = tⱼ인 쌍을 찾는다 (충돌!)
   → 못 찾으면 1번으로 돌아가 반복

기대 반복 횟수: ≈ 2회
전체 시간복잡도: O(2^(n/2))
공간복잡도:     O(2^(n/2))

직관: 출력 공간이 2ⁿ개이고, 2^(n/2)개를 샘플링하면 생일 역설에 의해 충돌이 1/2 이상 확률로 발생

결론: n비트 출력 해시는 n/2비트 수준의 충돌 저항성만 가진다.

→ 128비트 충돌 저항을 원하면 256비트 출력 해시가 필요!

메시지 무결성이란? (Message Integrity)

MAC

메시지가 중간에 변조되지 않았고, 정해진 비밀키를 아는 사람이 만든 메시지인지 확인하는 값

무결성 vs 기밀성

지금까지 배운 암호화(CBC, CTR)는 기밀성 — "내용을 숨기는 것"이 목적이었음

이번 챕터는 무결성(Integrity) — "내용이 변조되지 않았음을 증명하는 것"이 목적이다.

중요한 점: 무결성은 비밀로 숨길 필요가 없다. 예를 들어, 공개된 프로그램 파일이 진짜 원본인지 확인하는 게 목적일 때는 파일 내용을 숨길 필요가 없기 때문이다.

안전한 MAC의 정의

공격자가 할 수 있는 것: 원하는 메시지들의 tag를 서버에 요청할 수 있음 (Chosen Message Attack)

공격자의 목표: 한 번도 요청 안 한 새로운 메시지의 유효한 tag를 위조 (Existential Forgery)

안전한 MAC = 이 위조가 불가능한 MAC

tag가 5비트면 왜 안 되냐? → 공격자가 32가지 경우를 다 찍어볼 수 있어서 1/32 확률로 맞힐 수 있음. 이건 "negligible"하지 않으므로 안전하지 않다.

PRF → MAC

ECBC MAC

NMAC

CMAC (standard)

PMAC (Parallel MAC)

One time MAC

Many time MAC

1부. CPA-Secure 암호화의 한계 (Active Attacks)

CPA만으로는 부족한 이유

CPA 보안은 도청(eavesdropping) 만 막는다. 공격자가 직접 패킷을 조작하는 능동적 공격(active attack) 에는 무력하다.

실제 공격 예시 1: TCP/IP 패킷 조작

• 앨리스가 dest=80 (웹 서버)으로 암호화된 패킷을 전송
• 공격자가 패킷을 가로채서 dest=25 (Bob의 포트)로 목적지를 바꿔 전송
• CBC 암호화는 IV만 바꿔도 첫 번째 블록의 내용을 조작할 수 있음

왜 IV만 바꾸면 되냐?

CBC 복호화: m[0] = D(k, c[0]) ⊕ IV

따라서 IV' = IV ⊕ ("...80...") ⊕ ("...25...") 로 설정하면 복호화 결과가 dest=25로 바뀜

실제 공격 예시 2: CTR 모드에서 키스트로크 탈취

• SSH처럼 키 입력 하나하나를 CTR 모드로 암호화해서 전송하는 경우
• 공격자가 암호문을 변조해서 서버로 보내고, 서버의 ACK 응답을 관찰
• checksum(hdr, D) = t ⊕ checksum(hdr, D⊕s) 관계를 이용해 평문 D를 유추 가능

교훈

CPA 보안은 능동적 공격(active attack) 하에서 기밀성을 보장하지 못한다.

• 무결성만 필요하면 → MAC 사용
• 기밀성 + 무결성 둘 다 필요하면 → Authenticated Encryption (AE) 사용

2부. Authenticated Encryption 정의

AE 시스템의 구조

일반 암호화와 다른 점은 복호화 결과에 ⊥(거부) 가 추가된다는 것:

• 암호화: E: K × M × N → C (평소와 동일)
• 복호화: D: K × C × N → M ∪ {⊥} ← ⊥는 암호문이 거부되었다는 의미

공격자가 만들어낸 가짜 암호문이 들어오면 → ⊥ 출력 → 자동으로 거부

AE의 보안 조건 (두 가지 모두 만족해야 함)

1. CPA 보안: 의미론적 보안 (도청 방어)
2. 암호문 무결성 (Ciphertext Integrity, CI): 공격자가 새로운 유효한 암호문을 만들어낼 수 없음

CI 정의 (공식):

• 공격자가 암호화 오라클을 이용해 c₁, ..., cₙ을 얻음
• 새로운 암호문 c (기존 목록에 없는)를 제출했을 때 D(k,c) ≠ ⊥이 되면 공격 성공
• Adv_CI[A, E]가 negligible해야 안전

나쁜 예: CBC with random IV

CBC는 AE를 제공하지 않는다. 이유: D(k, ·)가 절대로 ⊥를 출력하지 않는다. → 공격자가 아무 암호문이나 제출해도 다 받아들임 → CI 게임을 쉽게 이길 수 있음

AE의 의미 (두 가지 함의)

함의 1: 진정성(Authenticity)

• 공격자가 앨리스 행세를 하며 가짜 메시지를 보낼 수 없음
• D(k,c) ≠ ⊥이면 밥은 "이 메시지는 k를 아는 사람이 보냈다"고 확신 가능
• 단, 리플레이 공격은 막지 못함 (이전에 보낸 유효한 암호문을 다시 보내는 것)

함의 2: CCA 보안

• AE를 제공하면 → CCA(선택 암호문 공격)에도 안전
• 정리: Adv_CCA[A,E] ≤ 2q · Adv_CI[B₁,E] + Adv_CPA[B₂,E]

3부. CCA (Chosen Ciphertext Attack)

CCA란?

공격자가 다음 두 가지 모두 가능한 상황:

1. CPA: 원하는 메시지의 암호문을 얻을 수 있음
2. CCA: 원하는 암호문의 복호화 결과를 얻을 수 있음 (단, challenge 암호문 제외)

목표: 여전히 어떤 메시지가 암호화됐는지 구별하지 못해야 함

CBC with random IV는 CCA에 취약

공격 방법:

1. m₀, m₁을 제출 → 암호문 c = (IV, c[0])을 받음
2. 변조된 암호문 c' = (IV ⊕ 1, c[0]) 을 복호화 요청
3. D(k, c') = m_b ⊕ 1 을 받으면 b를 알 수 있음

→ challenge 암호문이 아닌 살짝 바꾼 암호문으로 복호화 오라클을 악용

AE → CCA 안전성 (증명 스케치)

CI 덕분에, 공격자가 새로 만든 암호문을 복호화 요청해도 → ⊥ 반환 → 유용한 정보를 얻을 수 없음

따라서 CCA 오라클이 있어도 실질적으로 도움이 안 됨 → CCA 안전

4부. AE 구성 방법 (MAC + 암호화 조합)

역사적 배경

2000년 이전에는 AE라는 개념이 없었음. MS-CAPI 같은 API는 CPA 암호화와 MAC을 별도로 제공했고, 개발자가 직접 조합해야 했는데 잘못 조합하면 AE가 보장되지 않음.

세 가지 조합 방법

키: 암호화 키 k_E, MAC 키 k_I (서로 다른 독립적인 키 사용)

AE 정리

• (E,D)가 CPA 안전, (S,V)가 안전한 MAC이면:
  1. Encrypt-then-MAC: 항상 AE 제공 ✅
  2. MAC-then-Encrypt: CCA 공격에 취약할 수 있음. 단, (E,D)가 rand-CTR 또는 rand-CBC이면 AE 제공

5부. 표준 AE 모드

모두 nonce 기반, AEAD(Associated Data와 함께 인증된 암호화) 지원

AEAD (Authenticated Encryption with Associated Data):

• 일부 데이터는 암호화하고, 나머지 데이터는 암호화 없이 인증만 함
• 예: 네트워크 패킷에서 헤더는 인증만, 본문은 암호화+인증

OCB: PRP로부터 직접 구성

• 블록 암호를 한 번만 사용해서 암호화와 인증을 동시에 수행
• c[i] = E(k, m[i] ⊕ P(N,k,i)) ⊕ P(N,k,i)
• 마지막에 checksum 블록을 추가해서 무결성 태그 생성
• 패특허 문제로 실제 배포에 제약이 있었으나 현재는 해소됨

6부. 사례 연구: TLS (1.2)

TLS Record Protocol 구조

• 브라우저 ↔ 서버 간 안전한 통신의 기반
• 단방향 키: k_{b→s} (브라우저→서버), k_{s→b} (서버→브라우저)
• 상태 기반(Stateful) 암호화: 64비트 카운터 ctr_{b→s}, ctr_{s→b} 유지
  • 세션 시작 시 0으로 초기화, 레코드마다 1씩 증가
  • 목적: 리플레이 공격 방어 (이전 패킷을 다시 보내면 카운터가 맞지 않아 거부)

핵심 요약

💡 AE의 한계: 리플레이 공격은 막지 못함 (TLS는 카운터로 별도 방어). 사이드 채널 공격(타이밍 등)도 고려하지 않음.

1. 표기법

• $N$: 양의 정수
• $p$: 소수
• $\mathbb{Z}_N = \{0, 1, 2, \ldots, N-1\}$

$\mathbb{Z}_N$에서는 덧셈과 곱셈을 mod $N$으로 수행한다.

2. 모듈러 연산

2-1. 기본 연산

$N = 12$일 때 다음과 같은 연산이 이루어진다.

$\mathbb{Z}_N$의 연산은 분배법칙 등 일반적인 연산 규칙을 따른다.

2-2. 최대공약수 (GCD)

정수 $x, y$에 대해 $\gcd(x, y)$는 두 수의 최대공약수이다.

예: $\gcd(12, 18) = 6$

베주 항등식 (Bézout's Identity)

임의 정수 $x, y$에 대해 다음을 만족하는 정수 $a, b$가 존재한다.

$a \cdot x + b \cdot y = \gcd(x, y)$

$a, b$는 확장 유클리드 알고리즘으로 효율적으로 구할 수 있다.

$\gcd(x, y) = 1$이면 $x$와 $y$는 서로소(coprime)라 한다.

2-3. 모듈러 역원

$x \in \mathbb{Z}_N$의 역원은 $x \cdot y \equiv 1 \pmod{N}$를 만족하는 $y \in \mathbb{Z}_N$이며, $x^{-1}$로 표기한다.

보조정리

$x \in \mathbb{Z}_N$가 역원을 가진다 $\iff \gcd(x, N) = 1$

증명:

• ($\Rightarrow$) $\gcd(x, N) = 1$이면 베주 항등식으로 $a \cdot x + b \cdot N = 1$을 만족하는 $a, b$가 존재. mod $N$을 취하면 $a \cdot x \equiv 1 \pmod{N}$이므로 $a = x^{-1}$.
• ($\Leftarrow$) $\gcd(x, N) > 1$이면 모든 $a$에 대해 $\gcd(a \cdot x, N) > 1$이므로 $a \cdot x \not\equiv 1 \pmod{N}$.

2-4. 가역 원소의 집합 $\mathbb{Z}_N^*$

역원은 확장 유클리드 알고리즘으로 $O(\log^2 N)$ 시간에 계산 가능하다.

2-5. 모듈러 일차방정식

$a \cdot x + b \equiv 0 \pmod{N}$의 해:

$a^{-1}$은 확장 유클리드로 구한다. 전체 수행시간 $O(\log^2 N)$.

3. 페르마의 소정리

3-1. 정리

$p$가 소수이면

$\forall x \in \mathbb{Z}_p^*, \quad x^{p-1} \equiv 1 \pmod{p}$

예: $p = 5$일 때 $3^4 = 81 = 16 \cdot 5 + 1 \equiv 1 \pmod{5}$

3-2. 역원 계산 용도

$x \in \mathbb{Z}_p^*$일 때 $x \cdot x^{p-2} = x^{p-1} \equiv 1$이므로:

하지만 확장 유클리드가 더 효율적이다.

3-3. 응용: 랜덤 소수 생성

1024 비트 소수를 생성하는 간단한 알고리즘:

1. Step 1: $p \in [2^{1024}, 2^{1025} - 1]$을 무작위로 선택
2. Step 2: $2^{p-1} \equiv 1 \pmod{p}$인지 테스트
3. 성공하면 $p$ 출력, 아니면 Step 1로

소수가 아닌지 잘못 알릴 확률 $< 2^{-60}$. 실제로는 밀러-라빈 테스트 등 더 정교한 알고리즘을 사용한다.

4. $\mathbb{Z}_p^*$의 구조

4-1. 정리 (Euler)

$\mathbb{Z}_p^*$는 순환군이다. 즉, $\mathbb{Z}_p^* = \{1, g, g^2, g^3, \ldots, g^{p-2}\}$를 만족하는 $g \in \mathbb{Z}_p^*$가 존재한다. 이 $g$를 $\mathbb{Z}_p^*$의 생성원(generator)이라 한다.

예: $p = 7$, $g = 3$

모든 원소가 생성원은 아니다. 예: $g = 2$일 때 $\{1, 2, 4\}$만 생성되며 $\mathbb{Z}_7^*$ 전체가 아니다.

4-2. 원소의 위수

$g \in \mathbb{Z}_p^*$가 생성하는 군을 $\langle g \rangle$이라 하고, $g$의 위수(order)는:

예 ($p = 7$): $\text{ord}_7(3) = 6$, $\text{ord}_7(2) = 3$, $\text{ord}_7(1) = 1$

4-3. 라그랑주 정리

$\forall g \in \mathbb{Z}_p^*$에 대해 $\text{ord}_p(g) \mid p - 1$

5. 오일러 피 함수와 오일러 정리

5-1. 오일러 피 함수

5-2. 오일러 정리 (Euler, 1736)

페르마 소정리의 일반화

$\forall x \in \mathbb{Z}_N^*, \quad x^{\varphi(N)} \equiv 1 \pmod{N}$

예: $5^{\varphi(12)} = 5^4 = 625 = 52 \cdot 12 + 1 \equiv 1 \pmod{12}$

RSA 암호 시스템의 수학적 기반이 바로 이 정리이다.

6. 산술 알고리즘

6-1. 큰 수 표현

$n$ 비트 정수(예: $n = 2048$)를 64비트 머신에서 표현할 때, 32비트 블록 $n / 32$개로 나눠 저장한다. (일부 프로세서는 128비트 레지스터 및 곱셈을 지원)

6-2. 기본 연산의 시간 복잡도

$n$비트 정수 두 개에 대해:

6-3. 제곱을 통한 거듭제곱 (Repeated Squaring)

유한 순환군 $G$에서 $g \in G$와 $x \in \mathbb{Z}$가 주어졌을 때 $g^x$을 계산한다.

핵심 아이디어: $x$를 이진수로 전개해 $g$의 $2^k$ 거듭제곱들을 조합.

예: $x = 53 = (110101)_2 = 32 + 16 + 4 + 1$

알고리즘:

Input: g ∈ G, x > 0
Output: g^x

x = (x_n x_{n-1} ... x_1 x_0)_2
y ← g, z ← 1
for i = 0 to n do:
    if x[i] == 1: z ← z · y
    y ← y²
return z

예제 실행 ($g^{53}$):

6-4. 모듈러 연산의 종합 복잡도

$n$비트 $N$에 대해: