타원곡선의 점 개수는 왜 소수 p와 비슷할까

유한체(finite field)의 원소가 p개일 때 그 위의 타원곡선 점 개수는 대략 p개다. 암호학에서 쓰이는 큰 소수 p의 경우에도 점 개수가 p와 비슷한 이유를 직관적인 설명과 하세 정리(Hasse’s theorem), P-384 사례로 살펴본다.

타원곡선 E는 유한체 F에서 다음 식을 만족하는 점 (x, y)의 집합이다.

y² = x³ + ax + b

암호학에서는 보통 F를 큰 소수 p를 법으로 하는 정수로 구성한다. 이때 타원곡선의 점 개수는 F의 원소 개수와 비슷하다.

직관적으로 보기

소수 p를 법으로 할 때 0이 아닌 정수 가운데 절반가량은 제곱근을 가지며, 제곱근이 있는 수에는 제곱근이 두 개씩 있다. 예를 들어 7을 법으로 하면 1, 2, 4는 제곱근이 있고 3, 5, 6은 없다. 다음 파이썬 코드로 확인할 수 있다.

>>> [x**2 % 7 for x in range(1,7)]
[1, 4, 2, 2, 4, 1]

식 y² = x (mod p)의 해 개수를 세면 p개다. (0, 0)이 해이고, x 값 중 (p − 1)/2개에는 y 값이 두 개씩 대응하며 나머지에는 y 값이 없다.

즉, x를 무작위로 고르면 제곱근이 두 개 있거나 하나도 없는 경우가 대략 같은 확률로 나타난다. x를 고른 뒤 x³ + ax + b를 계산할 때도 제곱수가 나올 가능성과 제곱수가 아닌 값이 나올 가능성이 비슷하다고 예상할 수 있다. 실제로는 대체로 맞지만, 제곱수나 제곱수가 아닌 값 쪽으로 약간 치우칠 수 있다.

하세 정리의 경계

하세 정리는 타원곡선 E의 점 개수에 대해 다음과 같은 정확한 경계를 준다.

#E = p + 1 − t

|t| ≤ 2√p

p가 대략 2ⁿ의 크기라면 E의 점 개수도 대략 2ⁿ의 크기다. √p가 p보다 훨씬 작기 때문이다.

P-384 사례

NIST의 P-384 곡선은 최근 뉴스에 등장했다. 이 곡선의 기저 유한체는 384비트 소수 p를 법으로 하는 정수로 이루어져 있으므로 곡선의 점 개수도 384비트다. 구체적으로는 다음과 같다.

p = 2³⁸⁴ − 2¹²⁸ − 2⁹⁶ + 2³² − 1

따라서 곡선의 점 개수는 사전에 2³⁸⁴에서 2¹⁹³보다 작은 값만큼 차이 난다고 알 수 있다. 점 개수 n은 NIST SP 800-186 §3.2.1.4에 명시돼 있다.

>>> n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
>>> p = 2**384 - 2**128 - 2**96 + 2**32 - 1
>>> t = p + 1 - n
>>> t
1388124618062372383606759648309780106643088307173319169677

t가 양수이므로 곡선의 점 개수 n은 p보다 조금 작다. 여기서 ‘조금’은 p에 견준 표현이다. p − n은 큰 수지만 p에 비하면 작다.

다음 코드로 |t|가 사전에 구한 경계 2√p보다 작은지 확인할 수 있다.

>>> from math import sqrt
>>> t/(2*sqrt(p))
0.11057050503394951

따라서 실제 t는 경계보다 약 9배 작다. P-384에 대한 자세한 내용은 곡선 설명에서 확인할 수 있다.