[현대암호이론] 3주차 강의노트: 3장 고전 대칭키 암호 (후반부) + 4장 암호 수학 — 대수적 구조 (군·환·체·갈로아 체)

현대암호이론 및 응용 — 3주차 강의노트

---

📋 수업 개요

• 3장 후반부: 비즈네르 암호 복습 → Hill 암호 → One-Time Pad → 로터 암호 / Enigma → 전치 암호 → 스트림/블록 암호 구분
• 4장: 대수적 구조 개념 — Group(군) → Ring(환) → Field(체) → 유한체/갈로아 체 GF(2)

---

3장 후반부. 고전 대칭키 암호 (계속)

1. Vigenère Cipher 복습 ⭐

• 폴리알파벳 암호의 대표 — 키스트림을 여러 개 사용
• 키워드 "PASCAL" → 아스키 값 순서: P=15, A=0, S=18, C=2, A=0, L=11
• 이 6개의 키가 반복 사용됨

암호화 예시 (첫 번째 문자 S, 키 P=15):
$$C = (S + P) \bmod 26 = (18 + 15) \bmod 26 = 33 \bmod 26 = 7 \to \text{H}$$

💡 Vigenère 암호는 길이 M인 키에 의해 M가지의 Caesar Cipher가 반복되는 구조. 같은 평문 문자도 위치마다 다른 암호문으로 대응되어 빈도 분석이 어려워짐.

Vigenère 표 활용:

• 행: 평문 문자, 열(헤더): 키 문자
• 평문 S ↔ 키 P → 교차점 = H
• 평문 H ↔ 키 A → 교차점 = H

---

2. Hill Cipher (힐 암호) — 소개

• 행렬 연산을 이용하는 암호 방식
• 평문 블록을 벡터로 표현하고 키 행렬을 곱하는 방식

$$C = K \cdot P \pmod{26}$$

💡 이번 수업에서는 "힐 암호가 행렬 연산을 사용한다" 는 수준으로 정리. 상세 내용은 추후 행렬 단원에서 다룸.

---

3. One-Time Pad (일회용 패드) ⭐

3.1 개념

• 매번 다른 키를 사용하는 암호 → 빈도 분석 원천 차단
• 네이버 일회용 비밀번호(OTP)와 같은 원리 (매번 다른 번호 생성)

3.2 클로드 섀넌의 완전 보안 이론 ⭐

Claude Shannon (1948년 논문)이 수학적으로 증명:

"평문의 각 문자가 무작위로 선택된 키로 암호화된다면 완벽한 보안(Perfect Secrecy)이 이루어진다."

• 이 논문은 암호학 역사의 획기적 이정표로 평가됨
• 암호의 목표 중 하나: Perfect Secrecy (완전 보안)

3.3 조건과 한계

장점	한계
이론적으로 완전한 보안	키 길이 = 평문 길이
수학적으로 해독 불가 증명됨	키 재사용 금지 (One-Time)
	키 배포 문제가 매우 어려움

---

4. 로터 암호 (Rotor Cipher)

• 회전하는 치환 디스크(로터)를 사용하는 기계식 다중 치환 암호
• 원리:
  1. 초기 상태에서 한 글자를 입력 → 로터가 회전 → 입출력 위치 변경 (=새로운 치환)
  2. 다음 글자 입력 → 두 번째 로터가 회전 → 또 다른 치환 발생
  3. 로터가 계속 돌아가면서 매 글자마다 다른 치환 암호 적용
• 실제 로터는 26개의 알파벳 문자로 구성

---

5. Enigma 기계 ⭐

• 2차 세계대전 당시 독일군이 사용한 로터 기반 기계식 암호 장치
• 구성 요소:
  • 키보드: 평문 입력
  • 로터(Rotor): 내부에서 회전하며 매번 다른 치환 생성
  • 램프 보드: 암호화된 결과 표시
  • 플러그 보드(Plug Board): 로터 결과를 반사시켜 암호화와 복호화가 대칭으로 이루어지도록 설계

💡 Enigma의 특징: 같은 키 설정으로 암호화하면 복호화도 가능한 대칭 구조. 연합군이 Enigma를 해독한 것이 2차 대전의 중요한 전환점이 됨.

---

6. 전치 암호 (Transposition Cipher) ⭐

치환(Substitution)이 값을 바꾸는 것이라면, 전치(Transposition)는 위치를 바꾸는 것.

6.1 키 없는 전치 암호 (Keyless Transposition)

Rail Fence 방식:

• 평문을 지그재그로 두 줄에 번갈아 기록
• 첫 번째 줄 → 두 번째 줄 순으로 읽어 암호문 생성

예시 — "MEET ME AT THE PARK":

M  E  M  A  T  E  A  K
 E  T  E  T  H  P  R

→ 암호문: MEMATEAKETETHPR

열 교환 방식:

• 평문을 4열로 기록 후 열 순서대로 읽기
• 예: MMTA → EEHR → ... (열 단위로 추출)

6.2 키 있는 전치 암호 (Keyed Transposition)

• 문자들을 5개씩 그룹으로 나눔
• 주어진 위치 변환 규칙에 따라 위치 교체

예시 — 규칙: 1→2, 2→5, 3→1, 4→4, 5→3

원래 위치	1	2	3	4	5
이동 후	2	5	1	4	3

→ 그룹 내 문자들을 규칙에 따라 재배치

6.3 전치 암호의 한계와 활용

• 단독 사용 시 빈도 분석으로 쉽게 공격 가능 (문자 자체가 바뀌지 않으므로)
• 하지만 치환+전치의 조합은 현대 암호의 핵심 구성 요소!

💡 Substitution + Transposition의 반복 조합이 복잡하고 안전한 현대 암호 시스템(예: AES)의 기반. 두 요소는 구성 요소로서 탁월하게 기능함.

---

7. 현대 암호 체계로의 전환 — 스트림/블록 암호 소개

현대의 대칭키 암호는 크게 두 가지로 분류:

구분	스트림 암호 (Stream Cipher)	블록 암호 (Block Cipher)
처리 단위	비트/바이트 단위로 연속 처리	고정 길이 블록 단위 처리
키 구조	키스트림 생성 후 XOR	블록마다 동일한 키 적용
예시	RC4, A5/1	AES, DES

💡 앞에서 배운 고전 암호들(치환, 전치)이 현대 스트림/블록 암호의 구성 요소로 발전함.

---

---

4장. 암호 수학 — 대수적 구조 (Algebraic Structures)

1. 대수적 구조 개요

대수적 구조 (Algebraic Structure): 집합(Set) + 그 집합에 정의된 연산(Operation)의 결합

암호학에서는 모듈러 덧셈, 모듈러 곱셈 등 특정 연산과 정수 집합을 결합한 구조를 활용해 안전한 통신의 수학적 기반을 마련.

1.1 대수적 구조의 계층 ⭐

$$\text{Group(군)} \subset \text{Ring(환)} \subset \text{Field(체)}$$

구조	연산	조건 난이도
군 (Group)	하나의 연산	기본
환 (Ring)	두 개의 연산 (덧셈+곱셈)	중간
체 (Field)	두 개의 연산 + 나눗셈 가능	가장 강함

💡 군 → 환 → 체로 갈수록 조건이 더 까다로워지고 더 많은 연산이 가능해짐.
연산 범위: 군(덧셈·뺄셈) → 환(+곱셈) → 체(+나눗셈)

---

2. 군 (Group) ⭐

2.1 정의

군 $G = \langle S, \circ \rangle$: 집합 $S$와 이항 연산 $\circ$로 구성된 대수적 구조

아래 4가지 성질을 모두 만족해야 군:

번호	성질	설명
1	닫힘성 (Closure)	$a, b \in G \Rightarrow a \circ b \in G$
2	결합법칙 (Associativity)	$(a \circ b) \circ c = a \circ (b \circ c)$
3	항등원 존재 (Identity)	$\exists e \in G$ s.t. $a \circ e = e \circ a = a$
4	역원 존재 (Inverse)	$\forall a \in G,; \exists a^{-1} \in G$ s.t. $a \circ a^{-1} = e$

추가로 5번째 성질까지 만족하면 가환군(Abelian Group):

번호	성질	설명
5	교환법칙 (Commutativity)	$a \circ b = b \circ a$

2.2 예시 — $\mathbb{Z}_n$ (모듈러 덧셈군)

$\langle \mathbb{Z}_n, + \rangle$: $n$으로 나눈 나머지 집합에서의 덧셈

• 닫힘성: $a + b \bmod n$ 의 결과는 항상 $\mathbb{Z}_n$ 안에 속함 ✓
• 결합법칙: 덧셈 순서 상관없음 ✓
• 항등원: $0$ (어떤 수에 0을 더해도 자기 자신) ✓
• 역원: 원소 $a$의 역원 = $n - a$ (단, $\bmod n$ 적용)
  • 예: $\mathbb{Z}_5$에서 2의 역원 = $5 - 2 = 3$ (왜냐하면 $2 + 3 = 5 \equiv 0 \pmod 5$) ✓
• 교환법칙: 덧셈은 교환법칙 성립 ✓

→ $\langle \mathbb{Z}_n, + \rangle$는 가환군 (Abelian Group) ✓

$\mathbb{Z}_5$ 덧셈표에서 역원 확인:

원소	역원	검증
0	0	$0+0=0$
1	4	$1+4=5\equiv 0$
2	3	$2+3=5\equiv 0$
3	2	$3+2=5\equiv 0$
4	1	$4+1=5\equiv 0$

---

3. 유한군, 위수, 부분군

용어	영어	의미
유한군	Finite Group	원소의 개수가 유한한 군
위수	Order	군의 원소 개수 ($|G|$)
부분군	Subgroup	군의 부분 집합이 같은 연산에 대해 군의 성질을 만족

예시 — $\mathbb{Z}_5$:

• 유한군: 원소 수 = 5 → 유한군 ✓
• 위수: $|\mathbb{Z}_5| = 5$
• 부분군: ${0}$ (자명 부분군), ${0,1,2,3,4}$ (자기 자신) — 이 두 가지뿐

💡 ${0, 2}$ 같은 집합은 부분군이 아님. $2 + 2 = 4$ 인데 4가 집합 안에 없어서 닫힘성 불만족.

3.1 라그랑주 정리 (Lagrange's Theorem)

유한군 $G$의 부분군 $H$에 대해, $|H|$는 반드시 $|G|$를 나눈다.

$$|H| \mid |G|$$

예시: $|\mathbb{Z}_5| = 5$, 부분군의 위수는 1 또는 5만 가능 (5는 소수이므로) → 자명 부분군과 자기 자신뿐.

---

4. 순환군 (Cyclic Group)

군 $G$의 어떤 원소 $a$가 $G$의 모든 원소를 $a$의 반복 연산으로 생성할 수 있으면 $G$를 순환군이라 하고, $a$를 생성원(Generator)이라 함.

$$G = \langle a \rangle$$

• 연산이 곱셈인 경우: $G = {a^n \mid n \in \mathbb{Z}}$
• 연산이 덧셈인 경우: $G = {na \mid n \in \mathbb{Z}}$

예시 — $\langle \mathbb{Z}_6, + \rangle$, 생성원 1과 5:

반복 횟수	생성원 = 1	생성원 = 5
1회	1	5
2회	2	$10 \bmod 6 = 4$
3회	3	$15 \bmod 6 = 3$
4회	4	$20 \bmod 6 = 2$
5회	5	$25 \bmod 6 = 1$
6회	$6 \bmod 6 = 0$	$30 \bmod 6 = 0$

→ 1과 5 모두 ${0,1,2,3,4,5}$ 전체를 생성 → $\mathbb{Z}_6$은 순환군

---

5. 환 (Ring) ⭐

$R = \langle S, +, \times \rangle$: 두 개의 연산 (덧셈 $+$, 곱셈 $\times$)이 정의된 대수적 구조

연산	만족해야 할 성질
덧셈 $+$	5가지 군의 성질 모두 (닫힘, 결합, 항등원=0, 역원, 교환법칙)
곱셈 $\times$	닫힘성, 결합법칙, (교환법칙 — 가환환일 때만)
분배법칙	$a \times (b + c) = a \times b + a \times c$

💡 정수 집합 $\mathbb{Z}$는 덧셈과 곱셈이 정의된 가환환(Commutative Ring).
환은 군보다 조건이 강화된 구조 — 곱셈이 추가되었지만 곱셈 역원은 요구하지 않음.

---

6. 체 (Field) ⭐

$F = \langle S, +, \times \rangle$: 환에서 곱셈 역원까지 존재하는 구조 → 나눗셈 가능

연산	만족해야 할 성질
덧셈	5가지 — 아벨군(가환군)
곱셈	5가지 — 단, 덧셈의 항등원(0)은 곱셈 역원 제외
분배법칙	성립

핵심 추가 조건: 0을 제외한 모든 원소가 곱셈 역원을 가짐

💡 체 = 덧셈·뺄셈·곱셈·나눗셈이 모두 가능한 집합. 환보다 조건이 더 강화됨.
왜 0은 제외? 0 × (어떤 수) = 0이지 1이 될 수 없으므로 곱셈 역원이 존재할 수 없음.

대수 구조 비교 정리 ⭐

구조	덧셈	곱셈	분배법칙	곱셈역원
군 (Group)	✓ 아벨군	✗	✗	✗
환 (Ring)	✓ 아벨군	✓ 일부	✓	✗
체 (Field)	✓ 아벨군	✓ 전부	✓	✓ (0 제외)

---

7. 유한체 = 갈로아 체 (Galois Field, GF) ⭐

7.1 정의

유한체 (Finite Field): 원소의 개수가 유한한 체

• 수학자 갈로아(Galois)가 처음 발견 → 갈로아 체(Galois Field) 또는 GF로 표기

$$GF(q) \text{ — 원소의 개수가 } q \text{인 갈로아 체}$$

7.2 GF(2) — 가장 단순한 갈로아 체

집합: ${0, 1}$, 연산: 덧셈 + 곱셈

덧셈표 (= XOR 연산):

$+$	0	1
0	0	1
1	1	0

곱셈표 (= AND 연산):

$\times$	0	1
0	0	0
1	0	1

역원:

• 덧셈 역원: 0의 역원 = 0, 1의 역원 = 1 (왜냐하면 $1 + 1 = 2 \equiv 0 \pmod 2$)
• 곱셈 역원: 1의 역원 = 1 ($1 \times 1 = 1$), 0은 제외

💡 주의: GF(2)에서 $1 + 1 = 0$ (비트 XOR와 동일)

7.3 GF(2$^n$) — 암호학에서 핵심

• 원소 개수: $2^n$개
• 각 원소는 n비트 워드로 표현
• 덧셈, 뺄셈, 곱셈, 나눗셈 4가지 연산 모두 수행 가능

💡 AES(Advanced Encryption Standard) 등 현대 블록 암호는 GF($2^8$)에서 연산 수행. 나중에 AES 단원에서 자세히 다룸.

---

---

📌 이번 주차 핵심 요약

개념	한 줄 정리
Vigenère Cipher	키워드 길이만큼 서로 다른 Caesar Cipher를 반복 적용
One-Time Pad	매 문자마다 무작위 키 사용 → Shannon의 완전 보안 이론
Enigma	로터 회전으로 매 글자마다 치환 암호가 바뀌는 기계식 암호
Transposition Cipher	문자의 위치를 바꾸는 암호 (값은 유지)
Substitution + Transposition	현대 암호의 두 가지 핵심 구성 요소
군 (Group)	닫힘·결합·항등원·역원 만족 (교환법칙 추가 시 아벨군)
부분군과 라그랑주 정리	부분군의 위수는 전체 군의 위수를 나눔
순환군	하나의 생성원으로 모든 원소를 생성 가능한 군
환 (Ring)	군 + 곱셈 연산 (곱셈 역원 불필요)
체 (Field)	환 + 곱셈 역원 존재 (0 제외) → 4칙 연산 모두 가능
GF(2)	집합 {0,1}, 덧셈=XOR, 곱셈=AND, 가장 기본적인 갈로아 체
GF($2^n$)	n비트 워드 연산 체계, AES 등 현대 암호의 수학적 기반

---

⭐ 시험 대비 강조 포인트

1. Vigenère 암호화 계산 — 키워드의 반복 순서를 정확히 맞추고 mod 26 계산
2. Shannon의 완전 보안 — One-Time Pad의 이론적 근거. 1948년 논문
3. 군의 4가지 성질 — 닫힘·결합·항등원·역원. 가환군(아벨군)은 교환법칙까지 5가지
4. 라그랑주 정리 — "부분군의 위수는 전체 군의 위수를 나눈다" ($|H| \mid |G|$)
5. 환 vs 체의 차이 — 환은 곱셈 역원 불필요, 체는 곱셈 역원 필요 (0 제외)
6. GF(2) 연산표 — 덧셈(XOR)과 곱셈(AND) 표 암기
7. Substitution + Transposition — 현대 암호의 핵심 구성 요소임을 이해. 단독 사용 시 취약하지만 조합하면 강력함
8. 대수 구조 계층 — Group ⊂ Ring ⊂ Field 순서와 각 조건 차이 숙지