개요
암호는 정수론, 선형대수, 대수구조등 수학을 기반으로 만들어진다.
암호화, 복호화에 필요한 기본적인 암호 수학에 대해서 알아보겠다.
가분성
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) 특수 해
- d로 양변을 나누어 (a/d)x + (b/d)y = (c/d)의 식으로 만든다.
- 확장 유클리드 알고리즘으로 (a/d)s + (b/d)t = 1을 만족하는 s와 t를 계산한다.
- 특수해는 다음과 같다.
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)가 있다.