이산 로그의 수학적 정의
유한 순환군(cyclic group) G가 n개의 원소를 가지며, 군 연산이 곱셈으로 표기된다고 가정해 봅시다. b를 G의 생성원(generator)이라 하면, G의 모든 원소 g는 어떤 정수 k에 대해 g = bk 형태로 표현할 수 있습니다.
또한 g를 정의하는 두 정수는 법(modulo) n에 대해 서로 합동입니다. 따라서 각 원소 g에 대해 k의 법 n 합동류(congruence class)를 대응시키는 함수 logb: G → Zn(여기서 Zn은 법 n의 정수환)를 정의할 수 있습니다. 이 함수는 군의 동형 사상(isomorphism)으로, 밑 b에 대한 이산 로그(discrete logarithm)라고 불립니다.
수학, 특히 추상대수학과 그 응용 분야에서 이산 로그는 일반적인 로그의 집합론적 유사체입니다. 일반적인 로그 loga(b)는 실수 또는 복소수 위에서 방정식 ax = b의 해를 의미합니다.
마찬가지로 g와 h가 유한 순환군 G의 원소일 때, 방정식 gx = h의 해 x를 '군 G에서 h의 밑 g에 대한 이산 로그'라고 합니다.
이산 로그의 역사와 암호학적 중요성
이산 로그는 정수론(number theory)에서 오랜 역사를 지니고 있습니다. 처음에는 주로 유한체(finite field)에서의 계산에 활용되었지만, 소인수분해 문제(Integer Factorization Problem, IFP)만큼이나 풀기 어려운 난제로 여겨졌습니다.
공개키 암호 시스템(public-key cryptosystem) 구현에 필수적인 핵심 도구가 바로 이산 로그 문제(Discrete Log Problem, DLP)입니다. 현대의 대표적인 암호 알고리즘 상당수가 이 문제의 계산 복잡성에 기반해 보안을 확보합니다. 대표적으로 디피(Diffie)와 헬먼(Hellman)이 1976년에 제안한 디피-헬먼 키 교환(Diffie-Hellman key agreement) 방식이 있습니다.
예시
이산 로그는 군 (Zp)에서 가장 쉽게 이해할 수 있습니다. 이는 소수 p에 대해 곱셈 법 p 아래의 합동류 (1, …, p − 1)로 이루어진 군입니다.
이 군에서 어떤 수의 k제곱을 구하려면, 우선 정수로서 k제곱을 계산한 뒤 p로 나눈 나머지를 구하면 됩니다.
이 과정을 이산 거듭제곱(discrete exponentiation)이라고 합니다.
예를 들어 군 (Z17)x에서 34를 계산해 봅시다. 먼저 34 = 81을 구하고, 81을 17로 나누면 나머지가 13입니다.
따라서 군 (Z17)x에서 34 = 13입니다. 이산 로그는 바로 이 연산의 역연산입니다. 즉, 3k = 13 (mod 17)을 만족하는 k를 찾는 문제입니다.
이 경우 k = 4가 해입니다. 316 ≡ 1 (mod 17)이므로, n이 임의의 정수일 때 34+16n ≡ 13 × 1n ≡ 13 (mod 17)도 성립합니다.
따라서 이 방정식은 4 + 16n 꼴의 무한히 많은 해를 갖습니다. 더구나 16은 3m ≡ 1 (mod 17)을 만족하는 가장 작은 양의 정수 m, 즉 (Z17)x에서 3의 위수(order)이므로, 이것들이 곧 유일한 해들입니다. 따라서 해는 k ≡ 4 (mod 16)로 정의할 수 있습니다.
일반적인 이산 로그 logb(g)를 효율적으로 계산하는 알고리즘은 아직 알려져 있지 않습니다.
마무리
요약하자면, 이산 로그 문제는 '거듭제곱 계산은 쉽지만 그 역연산인 로그 계산은 어렵다'는 비대칭성에 기반합니다. 이러한 일방향성(one-way property) 덕분에 DLP는 디피-헬먼 키 교환, ElGamal 암호, DSA(디지털 서명 알고리즘) 등 현대 공개키 암호 시스템의 이론적 토대가 되고 있습니다.