📂정수론

이산로그

정의 ¹

소수 $p$ 에 대해 갈루아 필드 $\mathbb{F}_{p} := \mathbb{Z} / p \mathbb{Z}$ 의 항등원이 $0$ 이라고 하자.

$\mathbb{F}_{p}$ 의 원시근 $g \ne 0$ 에 대해 시클릭 그룹 $\mathbb{F}_{p} ^{ \ast } := \mathbb{F}_{p} \setminus \left\{ 0 \right\} = \left< g \right>$ 상에서 정의된 함수 $\log_{g} : \mathbb{F}_{p}^{ \ast } \to \mathbb{Z} / (p-1) \mathbb{Z}$ 가 다음을 만족하면 이산로그^{discrete Logarithm}라 한다. $$ g^{ \log_{g} (h) } \equiv h \pmod{p} $$

설명

$\mathbb{F}_{p} ^{ \ast }$ 의 존재성은 원시근 정리에 의해 보장된다.

사실 이산로그는 모든 $a,b \in \mathbb{F}_{p}^{ \ast }$ 에 대해 $\log_{g} (ab) = \log_{g} (a) + \log_{g} (b)$ 이라서 아이소멀피즘이 된다.

일반적인 로그와 달리 암호론에서의 로그는 그 계산의 어려움 때문에 유용한데, 주어진 $k$ 에 대해 $$ g^{k} \equiv x \pmod{p} $$ 를 만족하는 $x$ 를 찾는 일은 연속제곱법을 사용하면 별로 어렵지 않은 것에 반해 주어진 $h$ 에 대해서 $$ g^{x} \equiv h \pmod{p} $$ 를 만족하는 $x$ 를 찾는 일은 어렵다. 이를 이산로그문제^{discrete Logarithm Problem}라 하며, 암호의 필수적인 성질을 갖추고 있어 암호학 전반에서 널리 쓰이고 있다.

한편 이산로그문제는 그룹 $\left( G , \ast\ \right)$ 상으로 일반화될 수도 있다. 문제 자체는 여전히 $$ g \ast\ \cdots \ast\ g = h $$ 를 만족하려면 $g \ast\ g$ 를 몇 번 해야하는가를 물을 뿐이다. 이는 암호론의 한계가 정수론이 아님을 의미한다.

같이보기

• 이산로그 문제

이산로그 문제의 어려움을 이용한 보안 알고리즘

• 디피-헬만 키 교환 알고리즘
• 엘가말 공개 키 암호체계

이산로그 문제에 대한 공격 알고리즘

• 샹크스 알고리즘
• 폴리그-헬맨 알고리즘
• 이산로그 문제가 쉽게 풀리는 조건