CMATH-07. 로그 문제, 이산 로그 문제, 타원 곡선 이산 로그 문제

수학적 원리에서 현대 암호학의 정수까지, 로그(Logarithm)라는 개념이 어떻게 진화하며 난이도를 쌓아왔는지 핵심 위주로 정리합니다.

1. 로그 문제 (Logarithm Problem)

우리가 흔히 아는 실수 체계에서의 로그입니다. 연속적인 공간에서의 연산을 다룹니다.

• 정의: $b^x = y$ 일 때, 지수 $x$를 찾는 문제입니다 ($x = \log_b y$).
• 특징: 공간이 연속적입니다.
• 난이도: 매우 쉬움. 수치 해석적인 방법(Newton's method 등)이나 테일러 급수 전개를 통해 소수점 아래 수만 자리까지도 순식간에 계산할 수 있습니다.
• 비유: 매끄러운 오르막길에서 특정 높이에 도달하기 위해 몇 미터를 걸어야 하는지 찾는 것과 같습니다.

2. 이산 로그 문제 (Discrete Logarithm Problem, DLP)

실수의 연속성을 버리고, 유한체(Finite Field)라는 격리된 정수들의 세계로 들어온 문제입니다.

• 정의: $g^x \equiv h \pmod{p}$를 만족하는 정수 $x$를 찾는 문제입니다.
• 특징: 공간이 이산적입니다. 모듈러 연산($\pmod{p}$) 때문에 $g^x$의 값은 예측하기 어렵게 널뛰기하며, "연속성"이 없으므로 미분이나 근사치를 사용할 수 없습니다.
• 난이도: 어려움. 하지만 인덱스 칼큘러스(Index Calculus) 같은 준지수 시간(Sub-exponential) 공격 방법이 존재하여, 보안을 위해 키 크기를 매우 키워야 합니다 (예: 2048비트 이상).
• 비유: 일정한 규칙으로 번호가 뒤섞인 돌계단 위에서, 몇 번을 점프해야 특정 번호의 돌에 도착하는지 찾는 것과 같습니다.

3. 타원 곡선 이산 로그 문제 (ECDLP)

유한체라는 배경은 유지하되, 연산의 대상을 '숫자'에서 '타원 곡선 위의 점'으로 바꾼 문제입니다.

• 정의: 타원 곡선 위의 점 $P$와 $Q$에 대해, $Q = kP$ (점 $P$를 $k$번 더함)를 만족하는 정수 $k$를 찾는 문제입니다.
• 특징: DLP의 일종이지만, 군(Group)의 구조가 훨씬 복잡한 기하학적 규칙을 따릅니다.
• 난이도: 매우 어려움. 전통적인 DLP를 깨는 '인덱스 칼큘러스'가 여기서는 통하지 않습니다. 현재까지 알려진 가장 효율적인 공격법도 완전 지수 시간(Fully Exponential)이 걸리기 때문에, 아주 짧은 키(256비트)로도 극강의 보안을 제공합니다.
• 비유: 3차원 미로처럼 얽힌 타원 곡선의 점들 사이를 복잡한 규칙으로 워프(Warp)했을 때, 몇 번의 워프를 거쳤는지 알아내는 것과 같습니다.

요약 및 비교

항목	로그 문제	이산 로그 문제 (DLP)	타원 곡선 이산 로그 문제 (ECDLP)
연산 공간	실수 ($\mathbb{R}$, 연속)	유한체 ($\mathbb{Z}_p$, 이산)	유한체 위 타원 곡선 군 ($E(\mathbb{F}_p)$)
기본 연산	지수 ($b^x$)	모듈러 지수 ($g^x \pmod{p}$)	스칼라 곱 ($kP$)
해결 난이도	하 (순식간에 해결)	중 (키가 크면 안전)	상 (짧은 키로도 매우 안전)
공격 복잡도	-	준지수 시간 (Sub-exponential)	완전 지수 시간 (Exponential)
주요 용도	일반 공학 계산	RSA, Diffie-Hellman	현대 암호(ECC), 블록체인, 보안 모듈

참고: 로그라는 용어를 사용하는 이유

'이산 대수 문제' 혹은 '이산 로그 문제'에서 로그(Logarithm)라는 용어를 사용하는 이유는, 이 문제가 근본적으로 지수 함수(Exponentiation)의 역연산을 찾는 구조를 가지고 있기 때문입니다.

 

타원 곡선에서는 점의 덧셈을 반복하지만, 수학적 구조(Group Theory) 측면에서 보면 이는 전통적인 곱셈 기반의 이산 로그 문제와 완벽하게 대칭을 이룹니다.

1. 전통적인 로그와의 연결고리

우리가 아는 일반적인 대수학(Algebra)에서의 로그 정의는 다음과 같습니다.

 

$$a^x = y \quad \Rightarrow \quad x = \log_a y$$

 

여기서 $x$를 찾는 것은 $y$를 만들기 위해 $a$를 몇 번 곱했는지를 알아내는 과정입니다. 암호학의 '이산 로그 문제(DLP)'도 이와 형식이 같습니다.

• 유한체 위의 DLP: $g^k \equiv H \pmod{p}$
  • 여기서 $k$를 찾는 과정이 로그 연산과 같으므로 '이산 로그'라고 부릅니다.

2. 왜 타원 곡선(덧셈)에서도 '로그'라고 부를까?

타원 곡선에서의 연산은 기하학적으로 정의되다 보니 '덧셈(+)' 기호를 사용합니다.

 

$$P + P + \dots + P \text{ (k번)} = kP = Q$$

 

이 식만 보면 "이건 곱셈(k배)인데 왜 로그라고 하지?"라고 의문이 생길 수 있습니다. 하지만 이는 수학적인 표기법(Notation)의 차이일 뿐, 근본적인 군(Group)의 구조는 동일합니다.

구분	유한체 암호 (DSA, DH)	타원 곡선 암호 (ECC)
연산 표기	곱셈적 군 (Multiplicative Group)	가법적 군 (Additive Group)
반복 연산	지수 승 ($g^k$)	스칼라 곱 ($kP$)
문제 정의	$g$를 몇 번 곱했는가?	$P$를 몇 번 더했는가?
수학적 본질	이산 로그 문제	이산 로그 문제

 

수학자들은 추상 대수학의 관점에서 이 둘을 구분하지 않습니다. 어떤 원소(Generator)를 여러 번 반복해서 연산했을 때 결과값이 나왔다면, 그 반복 횟수 $k$를 찾는 행위를 관례적으로 '로그를 구한다'고 부르기 때문입니다.