ECC-6. ECDLP가 DLP보다 풀기 어려운 이유

핵심을 한 문장으로 요약하면, 전통적인 DLP를 푸는 데에는 '지름길' 같은 효율적인 공격 알고리즘이 존재하지만, ECDLP에는 아직 그런 '지름길'이 발견되지 않았기 때문입니다.

문제의 구조적 차이: 왜 '지름길'이 없을까?

두 문제의 난이도 차이는 이들이 정의된 수학적 공간의 근본적인 구조 차이에서 비롯됩니다.

사람 찾기 비유

전통적인 DLP: 잘 정돈된 격자 도시에서 특정 번지수(h)를 가진 집을 찾는 것과 같습니다. 이 도시에는 g라는 '이동 규칙'(예: 동쪽으로 1칸, 북쪽으로 2칸)이 있고, 이 규칙을 몇 번(x) 반복하면 목표(h)에 도착하는지 알아내는 것이 문제입니다. 도시가 매우 규칙적이기 때문에, 우리는 지도를 활용하고, 구역을 나누어 탐색하는 등 효율적인 탐색 전략(지름길)을 사용할 수 있습니다.
타원 곡선 DLP (ECDLP): 아무런 규칙 없이 점들이 흩어져 있는 광활한 우주에서 특정 좌표(점 Q)를 찾는 것과 같습니다. '이동 규칙'(점 덧셈)은 있지만, 한 점에서 다음 점으로의 이동이 예측 불가능하고 무작위처럼 보입니다. 이 우주에는 지름길이나 효율적인 탐색 전략이 없어서, 목표를 찾으려면 시작점(점 P)에서부터 규칙을 무작정 반복 적용해보는(brute-force) 수밖에 없습니다.

이 '지름길'의 유무는 실제 공격 알고리즘의 효율성 차이로 나타납니다.

주요 공격법: 인덱스 칼큘러스 (Index Calculus Method)
원리: 이 방법은 유한체의 매끄러운(smooth) 구조를 이용합니다. 문제를 더 작은 소인수들의 조합으로 쪼개서(factor base), 미리 계산된 로그 값을 이용해 선형대수 문제로 변환하여 풀어냅니다. 즉, 큰 문제를 잘게 쪼개서 효율적으로 푸는 '분할 정복' 전략이 가능합니다.

계산 복잡도: 이 알고리즘의 시간 복잡도는 준지수 시간(Sub-exponential Time)입니다. 키 길이가 늘어나도 문제의 어려움이 순수 지수적으로 증가하지는 않습니다.

주요 공격법: 폴라드의 로 (Pollard's Rho) 알고리즘, 제곱근 알고리즘
원리: 타원 곡선 군(group)은 인덱스 칼큘러스처럼 문제를 '잘게 쪼갤' 수 있는 구조적 특징이 알려져 있지 않습니다. 따라서 공격자는 점들을 하나씩 더해보며 패턴을 찾는 것과 같은 일반적인(generic) 알고리즘에 의존해야 합니다. 이는 사실상 무차별 대입 공격을 약간 개선한 수준입니다.

계산 복잡도: 이 알고리즘들의 시간 복잡도는 완전 지수 시간(Fully Exponential Time)입니다. 키 길이가 조금만 늘어나도 문제의 어려움이 기하급수적으로 폭증합니다.

이 계산 복잡도의 차이가 바로 키 크기의 차이를 만듭니다. 암호 시스템의 안전성은 '보안 비트(bits of security)'로 측정됩니다. 예를 들어 '128비트 보안'은 공격자가 최소 $2^{128}$번의 연산을 해야 암호를 깰 수 있음을 의미합니다.

ECC: 공격이 완전 지수 시간이므로, 128비트 보안을 달성하려면 단순히 256비트 키가 필요합니다. (공격 복잡도가 대략 sqrt{N}이므로, 키 길이를 n이라 할 때 $2^{n/2}$의 복잡도를 가짐. $2^{256/2} = 2^{128}$)
DLP/RSA: 공격이 준지수 시간이므로, 공격 알고리즘의 효율을 상쇄하기 위해 훨씬 더 긴 키가 필요합니다. 128비트 보안을 달성하려면 약 3072비트의 키가 필요합니다.

키 크기(입력 크기)가 증가함에 따라 완전 지수 시간(Exponential) 알고리즘의 계산량은 준지수 시간(Sub-exponential)에 비해 훨씬 가파르게 증가합니다. 이것이 바로 ECC가 훨씬 짧은 키로도 동일한 보안 강도를 유지할 수 있는 이유입니다.

보안 수준 별 키 크기 비교

타원 곡선 이산 로그 문제는 알려진 구조적 약점이 없어 '지름길' 공격이 불가능하므로, 순수하게 지수적인 복잡도로만 해결할 수 있습니다. 반면, 전통적인 이산 로그 문제는 구조적 특징을 이용한 '준지수 시간'의 지름길 공격이 가능합니다.

이러한 근본적인 난이도 차이 때문에 타원 곡선 암호(ECC)는 훨씬 짧고 효율적인 키를 사용하면서도 동등하거나 더 높은 수준의 보안을 제공할 수 있는 것입니다.