암호수학에 대해서 공부해보자:)

개요

암호는 정수론, 선형대수, 대수구조등 수학을 기반으로 만들어진다.

암호화, 복호화에 필요한 기본적인 암호 수학에 대해서 알아보겠다.

---

가분성

---

Divisibility라고 부르며 간단한 개념이지만 암호에서 자주접하는 개념이다.

a | b라고 표현한 식은 b는 a로 나누어 떨어진다라는 의미이다.

---

유클리드 알고리즘

---

gcd(Greatest Common Divisor)라고 불리는 최대 공약수를 찾을 때 필요한 알고리즘이다.

gcd(a, 0) = a , gcd(a, b) = gcd(b, r), 이때 r은 a를 b로 나눈 나머지이다. , gcd(a, b) = 1이면 서로소이다.

위의 세 조건을 기반으로 한 알고리즘이다.

예를 들어 36과 10의 최대공약수를 찾아보자

gcd(36, 10) = gcd(10, 6) = gcd(6, 4) = gcd(4, 2) = gcd(2, 0) = 2

---

확장 유클리드 알고리즘

---

두개의 정수 a, b가 주어질 때 s * a + t * b = gcd(a,b)를 만족하는 s와 t를 알아낼 수 있다.

gcd(161, 28)의 s,t를 구해보겠다.

아래의 표에서 q는 r1/r2의 몫을 의미한다. s는 1과 0으로 t는 0과 1로 시작하여 내려가는 알고리즘이다.

q	r1	r2	r	s1	s2	s	t1	t2	t
5	161	28	21	1	0	1	0	1	-5
1	28	21	7	0	1	-1	1	-5	6
3	21	7	0	1	-1	4	-5	6	-23
.	7	0	.	-1	4	.	6	-23	.

gcd(161, 28) = 7, s = -1, t = 6이 나오며

-1 * 161 + 6 * 28 = 7으로 검증할 수 있다.

---

선형 디오판투스 방정식

---

ax + by = c 형태의 방정식의 해를 구할 때 사용한다.

d = gcd(a, b)라고 할 때 d | c이면 무수히 많은 해가 존재하며 d !| c이면 해는 존재하지 않는다.

특수해와 일반해를 구하는데 구하는 방법은 다음과 같다.

1) 특수 해

1. d로 양변을 나누어 (a/d)x + (b/d)y = (c/d)의 식으로 만든다.
2. 확장 유클리드 알고리즘으로 (a/d)s + (b/d)t = 1을 만족하는 s와 t를 계산한다.
3. 특수해는 다음과 같다. x = (c/d)s, y = (c/d)t

2) 일반해

x = 특수해x + k(b/d), y = 특수해y + k(b/d)

14x + 21y = 77의 해를 구해보겠다.

---

모듈로 연산

---

mod라고 표기하는 모듈로 연산자는 %라고 생각하면 된다.

a mod n = r의 형태로 사용하며 a를 n으로 나눈 나머지는 r이다라는 의미이다.

---

역원

---

어떤 수의 역원을 계산하는 경우가 있다. 덧셈과 곱셈에 대한 역원이 있다.

---

덧셈에 대한 역원

---

a + b = 0 mod n를 만족하는 경우 곱셈에 대한 역원이라고 말한다.

Z10에서 덧셈에 대한 역원을 찾아보면 (0,0), (1,9), (2,8), (3,7), (4,6), (5,5)이다.

---

곱셈에 대한 역원

---

a * b = 1 mod n를 만족하는 경우 곱셈에 대한 역원이라고 말한다.

Z10에서 곱셈에 대한 역원을 찾아보면 (1,1), (3,7), (9,9)가 있다.