이번 포스팅에서는 정보보호, 암호화방식 등 앞으로 배우게 될 DES, AES, RSA, ECC 등을 이해하는 데 필수가 되는 정수론(수론) 기반 개념을 정리해보겠다! 내용은 학교 수업 교재를 바탕으로 작성하였다. 난 공부하면서 암호학을 위한 이 정수론 개념을 이해하는게 제일제일 어려웠었다...
암호화를 배우려면 정수론을 왜 알아야될까?? 현대 암호 알고리즘들은 모두 수학적 성질에 기반한다.
- RSA → 소수, 오일러 φ(n), 모듈러 연산
- Diffie-Hellman → 이산대수
- ECC → 유한체 GF(p), GF(2ᵐ)
즉, 정수론을 모르면 공개키 암호의 핵심 수학이 이해되지 않는다. RSA, DH, ECC 등은 이후에 다룰 것이다! 일단 정수론에 대해 알아봐보자.
가분성과 약수
정의
정수 a가 b로 나누어떨어질 때,
a | b (a divides b)라고 적는다.
예시:
- 3 | 12
- 6 | 30
소수들의 관점에서 a | b의 의미
정수는 모두 소수들의 곱으로 유일하게 표현된다.
예시:
- 12 = 2² × 3¹
- 36 = 2² × 3²
12 | 36 이 성립하는 이유:
각 소수의 지수가 b에서 더 크거나 같기 때문이다.
→ 모든 소수 p에 대해: aₚ ≤ bₚ 이면 a | b
최대공약수(GCD) — 유클리드 호제법
정의
아마 모르는 사람이 없을 듯한데,, 최대공약수는 a와 b의 공통된 약수 중 가장 큰 값이다.
가장 빠른 구하는 방법
유클리드 호제법(Euclidean algorithm)
gcd(a, b)
→ gcd(b, a mod b)
→ 나머지가 0이 될 때까지 반복
예시:
gcd(300, 18)
300 mod 18 = 12
18 mod 12 = 6
12 mod 6 = 0
=> gcd = 6
잘 보면, 나누는애랑 나머지가 앞으로 땡겨져서 다음단계에는 나누어지는애랑 나누는애로 된다!
모듈러(Mod) 연산
mod 연산 또한 많이 들어봤을텐데, 암호학에서 가장 중요한 연산이다. RSA, DH, ECC 모두 mod 연산을 기반으로 한다.
기본 규칙
a ≡ b (mod n) ↔ n으로 나눈 나머지가 동일함
여기서 ≡라는 기호가 있는데 이것은 합동 기호로, a랑 b의 mod연산한 값이 동일하다, 즉 합동이다 라는 의미이다.
덧셈/곱셈 성질
모듈러 연산은 중간 결과를 계속 mod 해도 동일하다.
(a + b) mod n = (a mod n + b mod n) mod n
(a × b) mod n = (a mod n × b mod n) mod
지금까진 다들 알던 개념이었을 것이다. 아래부턴,,, 진짜 이해하기 너무너무 힘들었던 개념들을 간단하게 정리해보겠다. 유한체는 군,환,체라는 개념이후에 나오는 개념인데, 군환체까지 정리하기엔 과해서,, 그리고 내가 군,환,체를 정리할 자신이 없어서(너무어려움) 바로 중요개념인 체와 유한체부터 봐보겠다.
체
체(Field)는 아주 간단히 말하면 “덧셈·뺄셈·곱셈·나눗셈이 모두 가능한 수의 집합”이다.
- 실수 ℝ
- 유리수 ℚ
- 복소수 ℂ
- 유한체 GF(p), GF(2ᵐ)
즉, 체의 핵심 요구사항은 딱 하나다:
어떤 두 원소를 골라도
덧셈, 뺄셈, 곱셈, 나눗셈이 항상 정의되어 있어야 한다.
이 조건을 만족해야 암호 알고리즘 내부 연산이 항상 유효하고, 연산 중간에 “나눗셈 불가” 같은 오류가 발생하지 않는다.
그럼 유한체는 뭘까?
유한체
유한체는 말 그대로 원소의 개수가 유한한(Field)이다.
예:
체 원소 개수 예시
| 유한체 GF(5) | 5개 | {0,1,2,3,4} |
| 유한체 GF(7) | 7개 | {0~6} |
| 유한체 GF(2⁸) | 256개 | AES에서 사용 |
유한체의 가장 큰 특징은 모든 연산이 “모듈러 연산”(mod)을 기반으로 만들어진다는 것이다. 즉, 값이 커져도 다시 mod p로 줄여서
원소 개수가 유한하게 유지된다.
유한체 GF(p)
가장 기본적인 유한체는 GF(p) 형태이다.
- p는 반드시 "소수"
- 원소는 0부터 p−1까지 총 p개
예: GF(7)
원소 = {0,1,2,3,4,5,6}
덧셈 = (a + b) mod 7
곱셈 = (a × b) mod 7
나눗셈 = a × b⁻¹ mod 7 ← b⁻¹(곱셈 역원)이 반드시 존재!
➡ “곱셈 역원이 모두 존재한다 = 나눗셈이 가능하다”
➡ 그래서 소수 p를 사용할 때만 실제로 체(Field)가 성립한다.
유한체 GF(2ᵐ)
GF(2ᵐ)은 암호 알고리즘에서 가장 중요한 체이다. AES, SHA-3, ECC의 일부 구현은 GF(2)라는 작은 유한체를 확장한 다항식 기반 체 GF(2ᵐ)을 사용한다.
여기서 GF(2)는 가장 다루기 쉬운 체이다. 원소가 두개니 0과 1로만 이루어진 체라서 덧셈은 XOR, 곱셈은 AND해서 디지털 회로, 비트연산, 컴퓨터 연산에 최적화됨. 근데 GF(2) 자체로는 너무 작기 때문에 이를 확장한 GF(2⁸)(256개의 원소) 등으로 넓히고, 연산은 “다항식 모듈러 연산”으로 수행한다.
예: 10110101(2진수)는
x⁷ + x⁵ + x⁴ + x² + 1
같은 다항식으로 표현된다.
AES의 S-box·MixColumns는 바로 이 GF(2⁸) 다항식 연산으로 동작한다.
그럼 왜 암호학에서 굳이 “유한체”를 사용할까??
암호 알고리즘에서 요구되는 특성들은
(1) 모든 연산이 항상 정의되어야 함
→ 나눗셈 불가능 같은 오류가 발생하면 암호화가 깨짐
→ Field(체)에서는 모든 연산이 꺾이지 않고 연결됨
(2) 값 크기를 무한히 키울 수 없음
→ 컴퓨터는 유한한 비트만 저장 가능
→ 유한체는 mod 기반이라 항상 고정된 범위에 머무름
(3) 역원이 항상 존재해야 함
→ AES S-box 생성, ECC 점 연산, RSA 역원 계산 등에 필수
(4) 좋은 난수성 / 균등 분포
→ 암호 공격이 어렵고 안전한 구조를 만들기 좋음
따라서 유한체는
안전한 암호 시스템의 수학적 기반이 된다.
유한체에 대한 얘기가 끝났으니 다른 정수론, 연산 이야기를 이어서 해보겠다!
다항식 연산 (AES, ECC에서 필수)
유한체 GF(2⁸)는
“8비트 숫자”를 “다항식”으로 생각해서 계산한다.
예:
10110101 = x⁷ + x⁵ + x⁴ + x² + 1
AES에서 MixColumns, SubBytes 과정이 바로 이 다항식 연산을 기반으로 한다.
오일러의 Totient 함수 φ(n)
RSA를 이해하는 핵심 수학이다.
정의
n과 서로소인 양의 정수의 개수.
예:
- φ(p) = p − 1 (p가 소수일 때)
- φ(pq) = (p − 1)(q − 1)
예시:
p=7, q=17 -> n = pq = 119
φ(119) = (7–1)(17–1) = 96
즉, 119와 서로소인 양의 정수의 개수는 119를 소수 두개의 곱으로 표현한다음 그 오일러값을 곱한 값인 96개이다!
오일러 정리 & 페르마 정리
페르마의 소정리
소수 p에 대해:
a^(p−1) ≡ 1 (mod p)
오일러 정리
a와 n이 서로소일 때:
a^φ(n) ≡ 1 (mod n)
이산대수(Discrete Logarithm)
정의
밑 g, 모듈러 p가 있을 때
g^x ≡ y (mod p)
여기서 x를 구하는 문제 = 이산대수 문제
이 x를 찾는 것이 매우 어렵기 때문에 공개키 암호가 안전하다!
마무리
개념 암호 알고리즘에서의 역할을 표로 정리해보겠다.
| 소수 / 인수분해 | RSA 기반 수학 |
| 모듈러 연산 | RSA, DH, ECC 기본 구조 |
| 오일러 φ(n) | RSA 키 생성 필수 공식 |
| 이산대수 | DH, ElGamal, ECC 안전성의 핵심 |
| 유한체 GF(p), GF(2⁸) | ECC, AES 연산 체계 |
| 다항식 연산 | AES MixColumns / SubBytes |
정수론은 단순한 수학이 아니라 현대 암호 알고리즘 전체의 기반이 되는 “언어”다!
다음 포스팅부턴 RSA, DES 등등등을 정리해보겠다.
'CS > 정보보호' 카테고리의 다른 글
| [정보보호] 블록암호와 DES (0) | 2025.11.24 |
|---|