ECC-5. 유한체 위의 타원 곡선 이산 로그 문제(ECDLP)

암호학에서 사용되는 타원 곡선 이산 로그 문제(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)'의 의미: '이산 로그 문제'라는 이름 자체가 값이 연속적이지 않고 뚝뚝 떨어져 있는 이산적인 공간을 전제로 합니다. 유한체가 바로 그 이산적인 공간을 제공하는 것입니다.

따라서 우리가 '타원 곡선 암호' 또는 '타원 곡선 DLP'라고 말할 때는, "유한체 위에서 정의된 타원 곡선에서의 이산 로그 문제"를 의미하는 것입니다.

만약 타원 곡선을 실수 위에서 정의하고 "로그 문제"를 푼다고 가정해 봅시다.

타원 곡선 이산 로그 문제는 점 P와 Q가 주어졌을 때 Q = k * P를 만족하는 정수 k를 찾는 것입니다.

유한체 위 (암호): 덧셈 연산(+ P)을 할 때마다 모듈러 연산 때문에 점의 좌표가 예측 불가능하게 "점프"합니다. 그래서 Q의 좌표를 보고 k가 얼마인지 역추적하는 것이 매우 어렵습니다.
실수 위 (단순 계산): 곡선이 연속적이므로, k를 찾는 것은 일반적인 대수학 문제로 변해버립니다. k는 더 이상 비밀스러운 정수가 아니며, 로그 함수 같은 해석적인 방법으로 쉽게 계산할 수 있습니다. 즉, 암호학적인 '어려움'이 완전히 사라집니다.

즉, 암호학의 기반이 되는 타원 곡선 문제의 난이도는 유한체라는 이산적인 공간의 특성에서 비롯됩니다. 따라서 '실수 위의 타원 곡선 이산 로그 문제'라는 말은 성립하지 않는, 틀린 표현입니다.