천천히, 제대로

핵심을 한 문장으로 요약하면, 전통적인 DLP를 푸는 데에는 '지름길' 같은 효율적인 공격 알고리즘이 존재하지만, ECDLP에는 아직 그런 '지름길'이 발견되지 않았기 때문입니다. 문제의 구조적 차이: 왜 '지름길'이 없을까? 두 문제의 난이도 차이는 이들이 정의된 수학적 공간의 근본적인 구조 차이에서 비롯됩니다. 사람 찾기 비유 전통적인 DLP: 잘 정돈된 격자 도시에서 특정 번지수(h)를 가진 집을 찾는 것과 같습니다. 이 도시에는 g라는 '이동 규칙'(예: 동쪽으로 1칸, 북쪽으로 2칸)이 있고, 이 규칙을 몇 번(x) 반복하면 목표(h)에 도착하는지 알아내는 것이 문제입니다. 도시가 매우 규칙적이기 때문에, 우리는 지도를 활용하고, 구역을 나누어 탐색하는 등 효율적인 탐색 전략(지름길)을 사용할 수 있습니다. 타원 곡선 DLP (ECDLP): 아무런 규칙 없이 점들이 흩어져 있는 광활한 우주에서 특정 좌표(점 Q)를 찾는 것과 같습니다. '이동 규칙'(점 덧셈)은 있지만, 한 점에서 다음 점으로의 이동이 예측 불가능하고 무작위처럼 보입니다. 이 우주에는 지름길이나 효율적인 탐색 전략이 없어서, 목표를 찾으려면 시작점(점 P)에서부터 규칙을 무작정 반복 적용해보는(brute-force) 수밖에 없습니다. 기술적 설명: 공격 알고리즘의 차이 이 '지름길'의 유무는 실제 공격 알고리즘의 효율성 차이로 나타납니다. 전통적 DLP (유한체): 주요 공격법: 인덱스 칼큘러스 (Index Calculus Method) 원리: 이 방법은 유한체의 매끄러운(smooth) 구조를 이용합니다. 문제를 더 작은 소인수들의 조합으로 쪼개서(factor base), 미리 계산된 로그 값을 이용해 선형대수 문제로 변환하여 풀어냅니다. 즉, 큰 문제를 잘게 쪼개서 효율적으로 푸는 '분할 정복' 전략이 가능합니다. 계산 복잡도: 이 알고리즘의 시간 복잡도는 준지수 시간(Sub...

암호학에서 사용되는 타원 곡선 이산 로그 문제(Elliptic Curve Discrete Logarithm Problem, ECDLP)는 반드시 유한체(Finite Field) 위에서 정의됩니다. 우리가 개념을 설명할 때 흔히 보는 부드러운 곡선 그래프는 실수(Real Numbers) 위에서 그려진 것이지만, 이를 직접 암호에 사용하지는 않습니다. 실수 위가 아닌, 유한체 위의 점들 암호학에 타원 곡선을 사용하기 위해서는 곡선을 이산적이고 유한한 공간으로 가져와야 합니다. 이는 모든 계산을 특정 소수 p로 나눈 나머지, 즉 모듈러 연산(Modular Arithmetic)을 통해 수행함으로써 이루어집니다. 개념 (실수 위): y2 = x3 + ax + b 방정식의 해가 되는 무한히 많은 점 (x, y)들의 집합입니다. 부드러운 곡선을 이룹니다. 암호학 (유한체 위): y2 ≡ x3 + ax + b (mod p) 방정식의 해가 되는 유한한 개수의 정수 좌표 (x, y)들의 집합입니다. 모든 좌표는 0과 p-1 사이의 정수입니다. 유한체 위의 타원 곡선 점들 (출처: 위키피디아 ) 유한체 위의 타원 곡선은 연속적인 곡선이 아니라, 위 그림처럼 특정 패턴을 가진 점들의 집합(scatter plot)처럼 보입니다. 왜 유한체를 사용해야 하는가? 컴퓨터 연산: 컴퓨터는 무한한 실수를 다룰 수 없습니다. 정수로 이루어진 유한체는 컴퓨터가 정확하게 계산할 수 있게 해줍니다. 보안성 확보: 점들의 좌표가 유한체 안에서 "흩어져" 있고 예측 불가능하게 연결(덧셈 연산)되기 때문에 이산 로그 문제가 어려워집니다. 만약 실수 위에서 계산한다면, 일반적인 대수학으로 문제를 훨씬 쉽게 풀 수 있어 암호로 사용할 수 없습니다. '이산(Discrete)'의 의미: '이산 로그 문제'라는 이름 자체가 값이 연속적이지 않고 뚝뚝 떨어져 있는 이산적인 공간을 전제로 합니다. 유한체가 바로 그 이산적인 공간을 제공하는 것입니다. 따라서 우리...

타원 곡선(Elliptic Curve)은 이름과 달리 타원 모양이 아니며, 특정 수학 방정식을 만족하는 점들의 집합으로 정의됩니다. 이 곡선은 독특한 성질을 가지고 있어 현대 암호학에서 매우 중요한 역할을 합니다. 타원 곡선이란? 타원 곡선은 일반적으로 다음과 같은 형태의 방정식으로 정의됩니다. $$y^2=x^3+ax+b$$ 여기서 a와 b는 상수이며, 곡선이 특이점(뾰족한 점이나 교차점)을 갖지 않도록 $$4a^3+27b^2\ne 0$$ 이라는 조건을 만족해야 합니다. 이 방정식의 해가 되는 모든 점 (x, y)와 무한 원점(point at infinity, O)이라고 불리는 특별한 점을 포함하여 타원 곡선을 구성합니다. 타원 곡선 예시(출처: 위키피디아 ) 특별한 성질: 점의 덧셈 법칙 타원 곡선이 암호학에 사용될 수 있는 가장 핵심적인 이유는 곡선 위의 점들 사이에 덧셈이라는 특별한 연산을 정의할 수 있다는 점 입니다. 이 연산은 기하학적으로 다음과 같이 정의됩니다. 두 점의 덧셈 (P + Q): 타원 곡선 위의 서로 다른 두 점 P와 Q를 더하려면, 두 점을 지나는 직선을 긋습니다. 이 직선은 타원 곡선과 또 다른 한 점(-R)에서 만나게 됩니다. 이 점을 x축에 대해 대칭시킨 점이 바로 R이며, P와 Q의 합, 즉 P + Q = R이 됩니다. $$ \begin{align} & m = \frac{{y}_Q-{y}_P}{{x}_Q-{x}_P} \\ & {x}_R = {m}^2 - {x}_P - {x}_Q \\​​ & {y}_R=m\left({x}_R-{x}_P\right)+{y}_P \end{align} $$ 여기서, $m$: 직선의 기울기 $x_R, y_R$: 점 R의 x, y 좌표 한 점의 두 배 (P + P 또는 2P): 한 점 P를 두 배 하려면, 점 P에서의 접선을 긋습니다. 이 접선은 타원 곡선과 다른 한 점(-R)에서 만나게 됩니다. 이 점을 x축에 대칭시킨 점 R이 2P가 됩니다. $$ \begin{align} ...

이 문제의 어려움은 간단한 지름길이나 공식이 없어서, 답을 찾으려면 사실상 거의 모든 가능성을 하나하나 확인해야 한다는 데 있습니다. 시계 위에서의 점프 게임 먼저, 모듈러 연산을 거대한 눈금을 가진 시계라고 상상해 보겠습니다. 일반 시계는 눈금이 12개지만, 암호학에서 사용하는 시계(법, p)는 그 눈금의 수가 상상도 할 수 없을 만큼 많습니다. 쉬운 문제 (앞으로 점프하기) 3을 5번 곱하고 17로 나눈 나머지(3^5 mod 17)를 구하는 것은 쉽습니다. 이는 "17칸짜리 시계에서, 3배씩 점프하는 규칙으로 5번 뛰어라. 최종 위치는 어디인가?"와 같습니다. 3^1 → 3 3^2 → 9 3^3 → 27 ≡ 10 (mod 17) 3^4 → 10 * 3 = 30 ≡ 13 (mod 17) 3^5 → 13 * 3 = 39 ≡ 5 (mod 17) 컴퓨터는 이처럼 정해진 규칙대로 앞으로 점프하는 것은 눈 깜짝할 사이에 해냅니다. 어려운 문제: 몇 번 점프했는지 맞히기 "17칸짜리 시계에서, 3배씩 점프하는 규칙으로 뛰었더니 최종 위치가 5였다. 총 몇 번 점프했을까?" (즉, 3^x ≡ 5 (mod 17)을 만족하는 x를 찾아라) 우리는 위에서 답이 5라는 것을 알지만, 결과값 5만 보고 어떻게 x를 찾을 수 있을까요? 점프 결과는 시계 위에서 무작위처럼 보입니다. 3 → 9 → 10 → 13 → 5 → 15 → 11 → 16 → 14 → 8 → 7 → 4 → 12 → 2 → 6 → 1 결과값 5가 나왔다고 해서 x가 5라는 것을 바로 알 수 있는 방법이 없습니다. 이전 값이 13이라는 것을 알지 못하면 역추적이 불가능합니다. 결국, 우리는 x가 1일 때, 2일 때, 3일 때... 모든 가능성을 하나씩 시도해보는 수밖에 없습니다. "경우의 수가 많다"의 진짜 의미 작은 17칸짜리 시계에서는 최대 16번만 시도하면 답을 찾을 수 있습니다. 하지만 실제 암호학에서는 어떨까요? 암호학에서 사용하는 시계의 눈금 수(소수...