[정보보안] 보안 수학 (소수, 페르마 소정리, 오일러 함수, DLP)

1. 소수 (Prime Number)

• 소수 (Primes): 약수가 1과 자기 자신 두 개인 수
• 합성수 (Composites): 약수가 세 개 이상인 수

소수 판정은 루트를 씌워서 판정한다. 만약 $n$이 합성수라면, $n$은 $\sqrt{n}$보다 작거나 같은 소수 약수를 반드시 가지게 된다. 따라서 $\sqrt{n}$보다 작은 소수로 나눠서 나눠떨어지지 않으면 소수라고 판정하면 된다. 예를 들어보면 아래와 같다.

• 97: $\lfloor \sqrt{97} \rfloor = 9$이므로, 9보다 작은 소수(2, 3, 5, 7)로 나누어떨어지지 않아 소수이다.
• 301: $\lfloor \sqrt{301} \rfloor = 17$이므로 2부터 17까지의 소수를 체크하며, 7로 나누어떨어지므로 합성수이다.

---

2. 페르마 소정리 (Fermat's Little Theorem)

소수 $p$에는 특이한 거듭제곱 성질이 있다.

$$a^{p-1} = 1 \pmod p$$

$$a^{p} = a \pmod p$$

$p$가 소수이고 $a$가 $p$로 나누어지지 않는 양의 정수($gcd(a, p)=1$, 서로소)일 때, $a^{p-1} \equiv 1 \pmod{p}$가 성립한다. 이 정리는 공개키 암호 및 소수 판별 테스트에서 중요하게 사용된다. 예시는 아래와 같다.

 

$a=7, p=19$인 경우의 연산 과정:

• $7^2 = 49 \equiv 11 \pmod{19}$
• $7^4 \equiv 11^2 = 121 \equiv 7 \pmod{19}$
• $7^8 \equiv 7^2 = 49 \equiv 11 \pmod{19}$
• $7^{16} \equiv 11^2 = 121 \equiv 7 \pmod{19}$
• 결론: $7^{18} = 7^{16} \times 7^2 = 7 \times 11 = 77 \equiv 1 \pmod{19}$

---

3. 오일러 함수 (Euler's Totient Function)

$$ \phi(n) = \text{n보다 작거나 같으면서 n과 서로소인 양의 정수 개수}$$

예를 들어 $n=10$일 때, 집합은 ${1, 3, 7, 9}$이며 $\phi(10)=4$이다.

 

이 오일러 함수는 소수인 경우 더 쉽게 계산 방법이 있다.

• $p$가 소수일 때: $\phi(p) = p-1$.
• $n = p \times q$ ($p, q$는 서로 다른 소수): $\phi(n) = \phi(p) \times \phi(q) = (p-1)(q-1)$

예를 들어 $\phi(37) = 36$이고, $\phi(21) = \phi(3) \times \phi(7) = (3-1) \times (7-1) = 12$가 된다.

 

페르마 정리에 이 오일러 함수를 대입해 일반화한 오일리 정리라는 것이 있다.

$gcd(a, n) = 1$인 임의의 $a, n$에 대해 즉, 서로소인 두 수 a, n에 대해 아래 식을 만족한다.

$$ a^{\phi(n)} = 1 \pmod{n}  $$

 

예를 들어 아래와 같다. (중요)

• $a=3, n=10$일 때, $\phi(10)=4$이므로 $3^4 = 81 \equiv 1 \pmod{10}$
• $a=2, n=11$일 때, $\phi(11)=10$이므로 $2^{10} = 1024 \equiv 1 \pmod{11}$

 

변형식으로 아래와 같이 쓸 수도 있다. 서로소인 두 수 a, n에 대해

$$a^{\phi(n)+1} \equiv a \pmod{n}$$

---

4. 이산 로그 문제 (Discrete Logarithm Promblem)

일반적인 실수 연산에서 로그 함수는 거듭제곱의 역연산으로 정의된다. Discrete Logarithm Problem은 주어진 소수 $p$, 원시근 $g$, 그리고 값 $y$에 대하여 다음 식을 만족하는 지수 $x$를 찾는 문제이다.

$$y = g^x \pmod{p}$$

이를 이산 로그 기호를 사용해서 아래와 같이 표기한다.

$$x = \log_g y \pmod{p}$$

 

이 DLP 문제는 암호학에서 매우 중요한데 연산의 비대칭성 때문이다. 순방향 연산 거듭제곱은 $g, x, p$를 알 때 $y = g^x \pmod{p}$를 구하는 것은 매우 빠르게 계산이 가능하다. 그러나 역방향 연산 DLP는 $y, g, p$가 주어졌을 때 $x$를 찾아내는 것은 일반적인 상황에서 매우 어렵다. 이 문제를 다항시간 내에 해결할 수 있는 알고리즘은 현재로써 없으며 이를 통해 암호의 안전성을 보장한다.