이산수학 및 암호학 기초
Discrete Math & Crypto
이산수학 & 암호학 기초 — 1단계: 그래프·조합론·부울 대수
0. 들어가기 전에: 왜 "이산(離散)"인가?
수학 하면 떠오르는 것이 연속적인 곡선, 미분, 적분일 것이다. 고등학교에서 배우는 수학의 대부분이 "끊기지 않고 이어지는" 세계를 다룬다. 그런데 컴퓨터는 어떤가? 컴퓨터 안의 정보는 0과 1로 딱딱 끊어진다. 인터넷 망은 도시와 도시를 잇는 선의 집합이고, 암호는 특정한 정수들의 관계에서 태어난다. 이산수학(Discrete Mathematics) 은 이처럼 "끊어진(이산된)" 구조들을 다루는 수학이다. 구체적으로는 그래프, 집합, 논리, 조합, 정수론이 그 핵심 재료가 된다.
이 분야가 왜 중요한지는 지금 당장 암호학과 직결되기 때문만이 아니다. Google의 검색 알고리즘, GPS 내비게이션의 경로 탐색, 카카오톡 메시지 암호화, 심지어 자율주행차의 물류 경로 — 이 모든 것이 이산수학 위에 세워져 있다. 이 과목을 배운다는 것은 디지털 세계의 설계도를 읽는 언어를 배우는 것이다. 본격적으로 시작하기 전에, 이 단계에서 우리가 걸어갈 세 개의 기둥을 먼저 확인하자. 첫 번째는 점과 선의 세계인 그래프 이론, 두 번째는 경우의 수를 세는 전략인 조합론과 복잡도, 세 번째는 디지털 논리의 수학적 언어인 부울 대수다. 이 셋은 서로 독립적으로 보이지만, 마지막 프로젝트에서 하나의 엔진 안에서 맞물리게 된다.
1부. 이론적 기초 — 배경지식
1-1. 집합과 관계: 그래프의 씨앗
그래프를 이해하려면 먼저 집합(Set) 과 관계(Relation) 를 알아야 한다. 집합은 '구별 가능한 원소들의 모임'이다(Cantor, 1895). 예를 들어 서울, 부산, 대전이라는 도시들의 집합 V가 있고, "서울-부산 사이에 고속도로가 있다"는 관계 E가 있다면, 이 두 가지를 합쳐 그래프 G = (V, E) 라고 부른다. 이것이 그래프의 가장 원초적인 정의다.
집합 위에서 관계를 따질 때 중요한 세 가지 성질이 있다: 반사성(reflexive) — a는 a 자신과 관계가 있다, 대칭성(symmetric) — a와 b가 관계가 있으면 b와 a도 관계가 있다, 전이성(transitive) — a-b, b-c가 관계가 있으면 a-c도 관계가 있다. 이 세 성질을 모두 만족하면 동치 관계(equivalence relation) 가 된다. 이 개념은 나중에 암호학에서 모듈러 연산을 이해할 때 정확히 다시 등장하므로, 지금 확실히 새겨두어야 한다. [노트 기록: 반사성·대칭성·전이성의 정의와 예시를 직접 써보자.]
1-2. 알고리즘이란 무엇인가 — 복잡도를 이해하기 위한 준비
"알고리즘(Algorithm)"이라는 단어는 9세기 페르시아 수학자 알-콰리즈미(al-Khwārizmī)의 이름에서 유래했다. 알고리즘이란 문제를 해결하는 명확하고 유한한 단계적 절차다. 그런데 모든 알고리즘이 동등하게 빠른 건 아니다. 100명의 학생 명단을 뒤지는 방법이 두 가지 있다고 하자. 하나는 처음부터 한 명씩 훑는 것, 다른 하나는 이름이 알파벳 순으로 정렬되어 있다면 가운데를 먼저 펼쳐보고 반씩 줄여나가는 것. 앞의 방법은 최악의 경우 100번 확인해야 하고, 뒤의 방법은 최악의 경우 log₂(100) ≈ 7번만 확인하면 된다. 이 차이를 수학적으로 표현하는 언어가 빅-오 표기법(Big-O Notation) 이며, 이것이 조합론 파트의 중심 도구가 된다.
1-3. 논리 — 부울 대수의 씨앗
아리스토텔레스 이후 논리학은 참(True)과 거짓(False), 두 값만으로 세상을 표현하려 했다. 19세기 영국의 수학자 조지 부울(George Boole)은 이 논리를 수학적으로 대수화했다(Boole, 1854, The Laws of Thought). 그는 "논리 연산도 덧셈, 곱셈처럼 계산할 수 있다"는 것을 보였다. 이것이 부울 대수(Boolean Algebra) 의 탄생이다. 100년 뒤, 클로드 섀넌(Claude Shannon)은 이 부울 대수가 전기 스위치 회로와 정확히 대응한다는 것을 그의 석사 논문(1937)에서 증명했다. 이 한 편의 논문이 현대 컴퓨터 하드웨어 설계의 토대가 되었다. 즉, 지금 배우는 논리 회로는 단순한 수학 장난감이 아니라 실제로 CPU 안에서 살아 움직이는 것이다.
2부. 본 내용 — 그래프 이론
2-1. 그래프의 해부학
그래프 G = (V, E)에서 V는 정점(Vertex, 노드) 의 집합이고, E는 간선(Edge) 의 집합이다. 간선에 방향이 있으면 방향 그래프(Directed Graph, Digraph), 없으면 무방향 그래프(Undirected Graph) 다. 간선에 숫자(거리, 비용, 용량 등)가 붙으면 가중 그래프(Weighted Graph) 라고 한다.
정점 v에 연결된 간선의 수를 차수(Degree) 라 한다. 여기서 아름다운 정리 하나가 나온다: 모든 정점의 차수의 합은 간선의 수의 두 배다. 왜냐하면 간선 하나는 항상 두 정점에 동시에 닿기 때문이다. [노트 기록: |E| = (1/2)Σdeg(v) 공식과 그 이유를 직접 증명해보자.] 이것은 단순해 보이지만, 그래프의 많은 성질을 증명할 때 기초로 쓰이는 악수 보조정리(Handshaking Lemma) 다.
그래프를 탐색하는 두 가지 기본 방법이 있다. 깊이 우선 탐색(DFS, Depth-First Search) 은 한 방향으로 갈 수 있는 데까지 가다가 막히면 되돌아오는 방식이다. 미로를 탈출할 때 오른손으로 벽을 짚고 걷는 것과 같은 원리다. 너비 우선 탐색(BFS, Breadth-First Search) 은 현재 정점에서 거리가 1인 모든 정점을 먼저 방문하고, 그 다음 거리 2인 정점들을 방문하는 방식이다. 물에 돌을 던졌을 때 파문이 퍼지는 모양을 상상하면 된다.
2-2. 트리 — 그래프의 뼈대
트리(Tree) 는 사이클(순환)이 없는 연결된 무방향 그래프다. n개의 정점을 가진 트리는 정확히 n-1개의 간선을 가진다는 것이 증명 가능하다. 생각해보라: 정점이 n개 있는데 연결을 유지하면서 사이클을 만들지 않으려면, 간선 하나가 정점 하나를 새로 연결해야 하므로, 첫 번째 정점 이후 n-1번의 연결이 필요하다.
트리 중에서 특별히 중요한 것이 신장 트리(Spanning Tree) 다. 임의의 연결 그래프 G에서 모든 정점을 포함하되, 간선의 수를 최소화한 트리다. 그런데 여기서 흥미로운 질문이 생긴다: 가중 그래프에서 간선 가중치의 합이 최소인 신장 트리를 어떻게 찾을까? 이것이 최소 신장 트리(MST, Minimum Spanning Tree) 문제이며, 크루스칼(Kruskal) 알고리즘이나 프림(Prim) 알고리즘으로 해결된다. 실제로 이 알고리즘은 통신 네트워크를 최소 비용으로 구축하는 문제에 직접 적용된다.
2-3. 최단 경로 — 다익스트라 알고리즘
자율주행차가 창고에서 목적지까지 이동할 때 어떤 경로를 택해야 가장 빠를까? 이것이 최단 경로 문제(Shortest Path Problem) 다. 가중 방향 그래프에서 음수 가중치가 없을 때, 1956년 네덜란드 컴퓨터 과학자 에츠허르 다익스트라(Edsger Dijkstra)가 제안한 알고리즘이 가장 효율적인 해답 중 하나다.
다익스트라 알고리즘의 핵심 아이디어는 탐욕적 선택(Greedy Choice) 이다. 출발 정점에서 시작해서, 현재 알려진 최단 거리가 가장 짧은 정점을 다음으로 방문하고, 그 정점을 통해 이웃 정점들의 거리를 갱신한다. 이 과정을 모든 정점을 방문할 때까지 반복한다. 핵심은 "이미 확정된 최단 거리는 다시 바뀌지 않는다"는 불변 조건(invariant)이다. 왜 그럴까? 모든 가중치가 양수이면, 이미 방문한 정점보다 더 짧은 경로가 나중에 나타날 수 없기 때문이다. [노트 기록: 다익스트라 알고리즘의 단계를 의사코드(pseudocode)로 직접 써보자 — 초기화, 방문 처리, 거리 갱신.]
시간 복잡도를 분석해보면, 우선순위 큐(Priority Queue)를 사용할 경우 O((V + E) log V)가 된다. 여기서 V는 정점 수, E는 간선 수다. 이 표기법이 바로 앞서 언급한 빅-오이며, 조합론 파트와 자연스럽게 연결된다.
2-4. 네트워크 흐름 — 최대 유량
이제 한 단계 더 나아가 네트워크 흐름(Network Flow) 을 다루자. 수도관 망을 생각해보라. 각 파이프는 특정 용량(capacity)을 가지고, 물은 수원지(source)에서 수요처(sink)로 흐른다. 파이프의 용량을 넘지 않으면서 보낼 수 있는 물의 최대량은 얼마인가? 이것이 최대 유량 문제(Maximum Flow Problem) 다.
이 문제의 핵심 정리가 바로 맥스-플로 민-컷 정리(Max-Flow Min-Cut Theorem, Ford & Fulkerson, 1956) 이다: 네트워크의 최대 유량은 최소 컷의 용량과 같다. 여기서 '컷(Cut)'이란 그래프를 소스 쪽과 싱크 쪽으로 나누는 간선들의 집합이다. 이 정리는 단순히 수도관 문제를 넘어서 공급망 최적화, 인터넷 트래픽 라우팅, 심지어 이분 매칭(Bipartite Matching) 문제 — 예를 들어 구직자를 일자리에 최적으로 배치하는 것 — 에도 그대로 적용된다.
포드-풀커슨 알고리즘의 아이디어는 "잔여 용량이 있는 경로(augmenting path)를 찾아서 유량을 계속 추가한다"는 것이다. 여기서 핵심은 역방향 간선(reverse edge) 이다. 이미 흐르고 있는 유량을 '되돌릴' 수 있다는 유연성이 알고리즘을 올바르게 만든다. 이 아이디어가 직관적으로 이상하게 느껴진다면 옳게 생각하고 있는 것이다. 왜 역방향 간선이 필요한지 스스로 예를 들어 납득해보는 것이 이 파트의 가장 중요한 학습 포인트다.
3부. 본 내용 — 조합론과 알고리즘 복잡도
3-1. 경우의 수를 세는 기술
조합론(Combinatorics)은 한마디로 똑똑하게 세는 수학이다. 브루트 포스(brute force), 즉 하나하나 다 세는 방법은 원소가 많아지면 금방 한계에 부딪힌다. 100명 중 2명을 뽑는 경우의 수를 일일이 나열하면 4,950가지인데, 이것을 손으로 셀 수는 없다. 그래서 원리가 필요하다.
곱의 법칙(Multiplication Principle): 사건 A가 m가지, 사건 B가 n가지 방식으로 일어날 수 있고 두 사건이 독립적이라면, A와 B가 함께 일어나는 경우의 수는 m × n이다. 합의 법칙(Addition Principle): 두 사건이 동시에 일어날 수 없을 때, A 또는 B가 일어나는 경우의 수는 m + n이다. [노트 기록: 이 두 원리를 각각 예시를 들어 정의를 직접 써보자.]
이 두 원리 위에서 순열(Permutation) 과 조합(Combination) 이 정의된다. 순열 P(n, r) = n! / (n-r)! 은 순서가 중요할 때, 조합 C(n, r) = n! / (r! × (n-r)!) 은 순서가 중요하지 않을 때 쓴다. 비밀번호를 설정할 때와 팀을 구성할 때를 비교하면 차이가 명확하다. 비밀번호 1234와 4321은 다르지만(순열), 팀에서 홍길동·김철수와 김철수·홍길동은 같은 팀이다(조합).
암호학에서 조합론이 왜 중요한가? 공격자가 비밀번호를 모두 시도해보는 브루트 포스 공격을 막으려면, 경우의 수가 천문학적으로 커야 한다. 256비트 키를 브루트 포스로 뚫으려면 2²⁵⁶ ≈ 10⁷⁷가지를 시도해야 하는데, 이는 우주 전체의 원자 수(약 10⁸⁰)에 맞먹는다. 조합론이 곧 보안 강도의 언어인 셈이다.
3-2. 알고리즘 복잡도 — 빅-오 표기법
알고리즘의 효율성을 측정할 때 실제 실행 시간보다 입력 크기 n에 대한 성장률을 분석한다. 이것을 점근적 분석(Asymptotic Analysis) 이라 한다. 빅-오 표기법 O(f(n))은 "n이 충분히 클 때, 실행 시간이 c·f(n)을 절대 초과하지 않는다"는 상한(upper bound)을 나타낸다.
주요 복잡도 클래스를 성장 속도 순으로 나열하면: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) 이다. O(1)은 배열에서 인덱스로 바로 접근하는 것, O(log n)은 이진 탐색, O(n)은 선형 탐색, O(n²)는 이중 반복문, O(2ⁿ)은 피보나치 수를 재귀로 구하는 것이 전형적 예다. 앞서 다익스트라의 복잡도가 O((V+E) log V)라고 했는데, 이 표기가 이제 의미를 갖기 시작할 것이다.
여기서 컴퓨터 과학 최대의 미해결 문제인 P vs NP 문제를 살짝 들여다보자. P는 다항식 시간(Polynomial time) 안에 풀 수 있는 문제들의 집합, NP는 답이 주어졌을 때 다항식 시간 안에 검증할 수 있는 문제들의 집합이다. 모든 P 문제는 NP에 속하지만, NP가 P에 속하는지는 아직 모른다. 이 문제를 푼다면 100만 달러의 클레이 수학 연구소 상금을 받게 된다. 암호학의 많은 부분이 "NP이지만 P가 아닐 것"이라는 가정 위에 세워져 있다는 사실이 중요하다.
4부. 본 내용 — 부울 대수와 논리 회로
4-1. 부울 대수의 기본 연산
부울 대수에서 변수는 오직 두 값, 0(거짓)과 1(참)만 가진다. 기본 연산은 세 가지다: AND (논리곱, ·) — 둘 다 참이어야 참, OR (논리합, +) — 하나라도 참이면 참, NOT (부정, ‾) — 참은 거짓으로, 거짓은 참으로. [노트 기록: 세 연산의 진리표(Truth Table)를 직접 그려보자.]
부울 대수에서 성립하는 법칙들을 확인하자. 드 모르간의 법칙(De Morgan's Laws): NOT(A AND B) = (NOT A) OR (NOT B), NOT(A OR B) = (NOT A) AND (NOT B). 이것은 단순한 수학 규칙이 아니라 논리 회로 설계를 단순화하는 핵심 도구다. 예를 들어, AND 게이트와 NOT 게이트만으로 OR 연산을 구현할 수 있다는 의미이기도 하다. 실제로 NAND 게이트(NOT-AND) 하나만으로 모든 논리 연산을 구현할 수 있다는 기능 완전성(Functional Completeness) 이 여기서 나온다.
또 중요한 것이 XOR (배타적 논리합, ⊕) 연산이다. A ⊕ B는 A와 B가 다를 때만 1이다. 이 연산은 암호학에서 특히 많이 등장한다. XOR의 아름다운 성질: A ⊕ A = 0, A ⊕ 0 = A, 그리고 A ⊕ B ⊕ B = A. 마지막 성질은 "XOR로 암호화한 것을 같은 키로 XOR하면 복호화된다"는 원타임 패드(One-Time Pad)의 수학적 근거가 된다.
4-2. 논리 회로 설계와 카르노 맵
논리식을 전기 회로로 구현한 것이 논리 게이트(Logic Gate) 다. AND, OR, NOT, XOR, NAND, NOR 게이트들의 조합으로 임의의 계산을 수행하는 회로를 만들 수 있다. 가장 기본적인 예가 1비트 두 수의 합을 구하는 반가산기(Half Adder) 다. 1+1을 2진법으로 표현하면 10(이진수)인데, 합의 비트(Sum)는 XOR 게이트로, 올림 비트(Carry)는 AND 게이트로 구현된다. 이 두 게이트의 조합이 CPU 내부에서 덧셈을 수행하는 가장 원초적인 단위다.
논리식을 최소화하는 도구가 카르노 맵(Karnaugh Map, K-map) 이다. 진리표를 2차원 격자 형태로 배열하고, 인접한 1들을 묶어 공통 항을 제거함으로써 논리식을 간단하게 만든다. 이것이 왜 중요한가? 트랜지스터 하나가 게이트 하나에 해당하고, 게이트 수가 곧 칩의 면적과 전력 소비에 직결되기 때문이다. [노트 기록: 4변수 카르노 맵을 그리고, 인접 셀이 그레이 코드(Gray Code) 순서로 배열되는 이유를 생각해보자.]
논리식의 두 가지 표준형이 있다. SOP(Sum of Products, 곱의 합) 는 AND 항들을 OR로 연결한 것이고, POS(Product of Sums, 합의 곱) 는 OR 항들을 AND로 연결한 것이다. 어떤 진리표든 SOP 또는 POS 형태로 표현 가능하다는 것이 부울 대수의 완전성이다.
5부. 프로젝트 — 예제 문제
이제 이론의 세 기둥을 실제 문제에 적용해볼 시간이다. 아래 세 문제는 단계별로 이어지며, 마지막에는 하나의 통합적 시나리오를 구성한다. 정답 없이 40분 안에 최대한 깊이 고민해보라. 풀다 막히는 지점을 기록하는 것도 중요한 학습이다.
[프로젝트 1] 자율주행 물류 경로 탐색 엔진 (20점)
스마트 물류 스타트업 'GridRoute'는 도심 6개 물류 거점(A, B, C, D, E, F)을 운용한다. 아래는 각 거점 간 이동 시간(분)을 나타낸 가중 방향 그래프다. 자율주행 로봇은 출발 거점 A에서 모든 거점까지의 최단 이동 시간을 미리 계산해 메모리에 저장해야 한다.
A → B : 4
A → C : 2
B → C : 1
B → D : 5
C → B : 1
C → D : 8
C → E : 10
D → E : 2
D → F : 6
E → F : 3
(1) 다익스트라 알고리즘을 직접 손으로 시뮬레이션하라. 각 단계에서 방문 처리된 정점, 현재까지 알려진 최단 거리 테이블, 다음으로 방문할 정점을 표 형태로 기록하라.
(2) A에서 F까지의 최단 경로와 이동 시간을 구하고, 그 경로에 해당하는 간선들을 역추적(backtracking)하는 방법을 서술하라.
(3) 만약 거점 D가 시스템 오류로 사용 불가(해당 정점과 연결된 모든 간선 제거)가 된다면, A에서 F까지의 최단 경로는 어떻게 바뀌는가? D를 제거한 새로운 그래프에서 다익스트라를 다시 실행하라.
(4, 심화) 이 그래프에 '비용(cost)'이라는 제2의 가중치를 추가하고 싶다. 시간과 비용을 동시에 최소화하는 경로를 찾으려면 어떤 방식이 필요할지 아이디어를 제안하라. 정확한 알고리즘 구현이 아니어도 되고, 어떤 방향으로 접근할 수 있는지 논리적으로 서술하면 된다.
[프로젝트 2] 창고 네트워크 최대 유량 분석 (10점)
같은 회사 GridRoute가 이번엔 중앙 창고(S, Source)에서 최종 배달 허브(T, Sink)로 드론 패키지를 보내는 파이프라인 용량을 분석하려 한다. 각 구간의 용량(단위: 패키지/시간)은 다음과 같다.
S → A : 10
S → B : 8
A → C : 6
A → D : 4
B → C : 5
B → D : 7
C → T : 9
D → T : 11
(1) 이 네트워크에서 최대 유량을 찾아라. 포드-풀커슨 방식으로 증가 경로(augmenting path)를 BFS로 탐색(에드몬즈-카프 방법)하여 단계별로 유량이 어떻게 증가하는지 기록하라.
(2) 최종 최대 유량을 결정하는 최소 컷(Min-Cut) 을 찾고, 맥스-플로 민-컷 정리가 실제로 성립함을 확인하라.
(3) S→C 구간에 용량 3짜리 새 파이프를 추가했을 때 최대 유량이 얼마나 증가하는지 분석하고, 이를 통해 어느 구간이 전체 네트워크의 병목(bottleneck)인지를 설명하라.
[프로젝트 3] 논리 회로로 구현하는 패리티 체커 (10점)
데이터 전송 중 오류를 감지하는 가장 단순한 방법 중 하나가 패리티 비트(Parity Bit) 다. 4비트 데이터 (A, B, C, D)를 전송할 때, 전체 1의 개수가 짝수가 되도록 패리티 비트 P를 추가한다. 수신측은 도착한 5비트(A, B, C, D, P)에서 1의 개수가 홀수면 오류가 발생했다고 판단한다.
(1) 4비트 입력 (A, B, C, D)에 대해 짝수 패리티 비트 P를 생성하는 논리식을 진리표 없이 XOR 연산의 성질만으로 유도하라. (힌트: XOR의 성질 A ⊕ A = 0을 어떻게 확장할 수 있는가?)
(2) 수신된 5비트 (A, B, C, D, P)를 입력받아 오류가 있으면 1, 없으면 0을 출력하는 오류 검출기(Error Detector) 의 논리식을 설계하고, 이를 최소한의 XOR 게이트만으로 구현한 회로도를 그려라.
(3) 만약 두 비트에서 동시에 오류가 발생한다면, 이 패리티 체커가 오류를 감지할 수 있는가? 그 이유를 XOR의 성질을 이용해 수학적으로 설명하라.
(4, 심화) 오류 감지를 넘어 오류 수정까지 하려면 어떻게 해야 할까? 해밍 코드(Hamming Code)의 아이디어(중복 패리티 비트를 위치별로 배치)를 스스로 추론해보고, 7비트 해밍 코드 H(7,4)의 구조를 논리적으로 설계해보라. (정확한 정답보다는 아이디어의 논리적 일관성을 본다.)
마무리: 세 기둥이 하나로
이 세 프로젝트가 따로따로처럼 보이지만 사실 한 방향을 가리키고 있다는 것을 눈치챘는가? 그래프는 현실 네트워크를 모델링하고, 조합론과 복잡도는 알고리즘의 효율성을 보장하며, 논리 회로는 그 알고리즘이 실제로 실행되는 물리적 기반이다. 다음 단계인 정수론과 암호학에서 다익스트라의 구조는 키 교환 프로토콜의 그래프 모형으로, 빅-오 분석은 암호 알고리즘의 안전성 논거로, XOR 연산은 스트림 암호의 핵심 연산으로 다시 등장한다. 지금 배운 것들은 끝난 것이 아니라 앞으로 쌓아올릴 구조물의 토대다.
참고 문헌: Rosen, K. H. (2018). Discrete Mathematics and Its Applications (8th ed.). McGraw-Hill. / Cormen, T. H. et al. (2022). Introduction to Algorithms (4th ed.). MIT Press. / Boole, G. (1854). An Investigation of the Laws of Thought. Walton & Maberly. / Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399–404.