[암호학] 2. 이산 로그 문제

이번 글에서는 이산 로그 문제에 대해 설명하겠습니다.

이산 로그 문제

이산 로그 문제(Discrete Logarithm Problem, DLP)는 $a^x = b$를 계산하는 것은 쉽지만 $x = \log_ab$를 만족하는 $x$를 구하기는 어렵다는 것에서 나온 문제입니다.

$\textrm{Given}\ g,x,p \xrightarrow{\text{easy}} y=g^x\ \text{mod}\; p$
$x = \log_gy \xleftarrow{\textrm{hard}} \text{Given}\ g, y, p$

실수에서는 $x$를 간단히 구할 수 있습니다. 그렇다면 왜 DLP는 어려운 문제로 알려져 있으며, 암호에 사용될만큼 어려운지 알아보겠습니다.

군

두 원소가 하나로 대응되는 연산을 이항연산이라고 합니다.

이항연산은 $*:S \times S \rightarrow S$로 정의되는 함수이며, 집합 $M \neq \empty$의 원소 $a$, $b$와 이항연산 $*$에 대해 $a * b\in M$이면 $\langle M, *\rangle$를 마그마라고 정의합니다.

마그마의 연산이 결합법칙을 만족한다면 반군이라고 합니다.

반군 $\langle M, *\rangle$의 모든 원소 $a$에 대해 $a * e = e * a = a$를 만족하는 어떤 $e$를 항등원이라고 합니다.
항등원이 존재하는 반군을 모노이드이라고 합니다.

모노이드 $\langle M, *\rangle$의 원소 $a$와 항등원 $e$에 대해 $a * a' = a' * a = e$ 를 만족하는 $a'$ 을 역원이라고 합니다.
역원이 존재하는 모노이드를 군이라고 합니다.

군 $\langle G, *\rangle$ 의 연산에 대해 교환법칙이 성립하면 그것을 가환군이라고 합니다. 교환법칙이 성립하지 않는 나머지 군은 비가환군이 됩니다.

군에 대한 더 자세한 설명은 생략하겠습니다. 군은 간단하게 연산에 대해 대칭성을 가지는 수의 집합이라고 생각하면 되겠습니다.
군의 정의는 대칭성에서 시작하였습니다. 연산에 대해 닫혀있고, 결합법칙, 항등원의 존재성, 역원의 존재성이 성립하는 이항연산구조라면 모두 군이라고 할 수 있습니다.

군 $G$의 어떤 원소 $a$와 임의의 $x \in G$ 에 대해 $x = a^n$ 을 만족하는 정수 $n$이 존재하면 군 $G$를 순환군이라고 하고, $a$를 생성원이라고 합니다.

원시근

이 생성원은 체론에서 원시근이 됩니다.
원시근에 대해서 알아보기 전에, 위수에 대해 알아보겠습니다.

양의 정수 $k$가 $\gcd(a,n)=1$인 어떤 정수 $a$에 대해 $a^k ≡1\ (\text{mod}\ n)$ 을 만족하는 최소의 양의 정수일 때 $a$는 $\text{mod}\ n$ 에 대해 $k$의 위수를 가진다고 하고 $\text{ord}_n(a) = k$ 라고 씁니다.
$\text{mod}\ n$에서 $a$를 거듭제곱해서 1이 될 때 거듭제곱의 횟수가 $a$의 위수, $\text{ord}_n(a)$라고 볼 수 있습니다.

오일러 정리에 의해 모든 수는 위수를 가지고 그 수는 $\phi (n)$ 이하인 $\phi (n)$의 약수입니다.

위수가 $\phi (n)$인 수 $a$가 $\text{mod}\ n$의 정수론에서의 원시근이 됩니다. ($\text{ord}_n(a) = \phi (n)$이면 $\text{mod}\ p$의 원시근)

원시근은 거듭제곱을 통해 1과 $n$ 사이의 수를 모두 표현할 수 있는데, 이 성질이 추후 설명할 이산 로그 문제의 시작점이 됩니다.

환

환의 정의는 가환군에서 시작됩니다. 덧셈에 대한 가환군 $R$이 곱셈에 대해 닫혀있으며 결합법칙과 분배법칙을 만족할 때 $R$을 환이라고 합니다. 또한 곱셈에 추가적으로 교환법칙도 성립한다면 그것을 가환환이라고 합니다.

체

체는 덧셈에 대한 가환군이며, 동시에 환이고, 곱셈에 대해서도 가환군입니다. 간단하게, 덧셈에 대한 항등원을 제외한 모든 원소가 역원을 갖는 가환환입니다.
체 중에서 유한체는 모두 소수 $p$와 자연수 $n$에 대해 원소의 개수가 $p^n$인 유한집합이며 갈루아 체라고도 부릅니다. 모든 유한체 $\mathbb{F}_q^{\times}$는 항상 순환군인데, 특수한 경우로 $p = q$ 일 때 위에서 설명한 체론에서의 원시근과 정수론에서의 원시근과 일치하게 됩니다.

원시근과 체를 이용한 이산 로그 문제 정의

유한체는 곱셈에 대해 잘 정의되어 있습니다. 간단하게 유한체 위의 $\log$를 생각해보면 원시근의 거듭제곱으로 만들어진 유한집합 안의 임의의 원소 $a$, $b$에 대해서 $a$의 거듭제곱으로 $b$를 표현할 수 있으며 역도 마찬가지입니다. 따라서 유한체는 모두 $\log$ 라는 연산에 대해 닫혀있고, 또한 원시근을 사용해서 연산의 결과값도 모두 다릅니다.

앞서 로그 문제는 실수에서는 쉽게 값을 구할 수 있다고 했습니다. 하지만 유한체에서는 그 값을 구하기 어렵습니다.
예시를 하나 들어보겠습니다.

$\Z_7$을 정수의 무한집합 $\mathbb{Z}$의 $\text{mod}\ 7$ 시스템이라고 생각하겠습니다.
$\Z_7$은 $\{0,1,2,3,4,5,6\}$이 됩니다.
$\Z_7$는 유한체입니다. (체의 성질을 모두 만족하고 있습니다)
여기서 $\log_{3}5$는 무엇일까요?
$3^5 \equiv 243 \equiv 5\pmod 7$ 이기 때문에 5가 됩니다.

순환군의 원소수가 작을 때는 실제로 로그 연산의 값을 구하는 것이 어렵지 않지만 원소수가 늘어날수록 로그 연산값을 구하는 것이 매우 어려워집니다. 실제로 그 값을 구하는 효율적인 계산법은 아직 알려져 있지 않습니다. 1부터 차례로 모두 조사하는 전수조사 말고도 Shanks' Baby Step Giant Step Algorithm, Pohlig-Hellman Algorithm 등을 통해 값을 찾아낼 수 있지만 다항 시간 안에 값을 찾아내는 알고리즘은 아직 없습니다. 그러나 양자컴퓨터에서는 다항 시간 내에 풀 수 있는 것이 증명되어 있습니다.

다음 글에서는 DLP를 이용한 암호 시스템인 ElGamal에 대해 설명하겠습니다.