타원 곡선 쌍 탐색

2022-08-15 19:05:50

수집

저자: Vitalik Buterin

원제목: 《Exploring Elliptic Curve Pairings》

발표 시간: 2017년 1월 14일

암호학의 많은 기초 구조, 예를 들어 "결정론적 임계값 서명"(deterministic threshold signature, 잠정 번역), zk-SNARKs 및 기타 형태의 간단한 제로 지식 증명 등은 그 뒤에 있는 핵심 원시 모델 중 하나가 타원 곡선 쌍입니다. 타원 곡선은 30년 이상 암호화, 디지털 서명 등 암호학 응용 분야에서 널리 사용되어 왔으며, "타원 곡선 쌍(EC pairings)"(또는 이중 선형 맵)은 최근에 그 기반 위에서 새롭게 등장한 것으로, 암호 곱셈을 도입하여 타원 곡선을 기반으로 한 합의에서 할 수 있는 일이 크게 증가했습니다. 이 글에서는 타원 곡선 쌍에 대해 자세히 설명하고, 그것이 어떻게 작동하는지 간략하게 설명할 것입니다.

이 개념은 정말 이해하기 어려운 것이기 때문에, 당신이 첫 번째 또는 심지어 열 번째 읽을 때 완전히 이해할 것이라고 기대하지는 않지만, 이 글이 적어도 그 중 일부의 신비를 알려주기를 바랍니다.

타원 곡선 자체는 이해하기 어려운 주제이지만, 이 글은 대부분 당신이 그것의 작동 원리에 대해 어느 정도 알고 있다고 가정할 것입니다. 만약 기본 개념이 없다면, 이 글을 입문서로 추천합니다. 일반적으로 타원 곡선은 "점(points)"이라고 불리는 수학적 객체를 처리하며, 간단히 말해 2차원 평면의 점(x, y)과 몇 가지 특별한 덧셈 및 뺄셈 공식(예: R = P + Q 계산)입니다. 또한 점을 정수로 곱할 수 있습니다(예: P * n = P + P + … + P, 물론 n이 매우 클 때는 훨씬 더 빠른 알고리즘이 있습니다).

점의 덧셈이 그래프에서 어떻게 보이는지의 모습입니다.

그 외에 "무한 원점"(O)이라는 특별한 점이 있으며, 점의 연산 규칙에서 영 요소로 작용합니다. 즉, 모든 점에 대해 P + O = P입니다. 하나의 곡선은 "차수(order)"라는 특성을 가지며, 이는 모든 P에 대해 P * n = O가 되는 양의 정수 n이 존재함을 의미합니다(물론 P * (n + 1) = P, P * ((7*n) + 5) = P * 5 등으로 계속됩니다). 또한 미리 합의된 "생성점(generator point) G"가 있으며, 이는 덧셈 단위 요소로 선택된 점으로, 숫자 1을 나타내는 역할을 합니다. 이론적으로 모든 곡선의 점은 생성원으로 사용될 수 있지만, 중요한 것은 G가 통일적으로 선택된 것입니다.

쌍은 특정한 더 복잡한 등식을 검증할 수 있게 해줍니다: 예를 들어, P = G * p, Q = G * q, R = G * r일 때, p * q = r이 성립하는지 확인하려면 P, Q, R 세 점의 좌표만 있으면 됩니다. 이것은 겉보기에는 타원 곡선의 가장 기본적인 보안 보장이 깨진 것처럼 보일 수 있습니다. 왜냐하면 P 점의 좌표를 알면 p의 값이 유출되는 것처럼 보이기 때문입니다. 그러나 실제로 이러한 유출의 위험은 매우 제한적입니다. 정확히 말하면, 결정론적 Diffie-Hellman 문제는 매우 쉽지만, 계산적인 버전은 여전히 "계산적으로 불가능(computationally infeasible)"합니다. 최소한 그 난이도는 이 값을 모르는 것과 비슷합니다.

"쌍"을 이해하는 세 번째 방법은 우리가 논의하는 대부분의 사용 상황에서 가장 영감을 주는 방법일 수 있습니다. 타원 곡선의 점을 단방향 암호 함수로 간주하면(즉, encrypt(p) = p * G = P), 전통적인 타원 곡선의 수학 원리가 변수 간의 선형 제약을 검증하게 해줍니다(예: P = G * p, Q = G * q, R = G * r, 5 * P + 7 * Q = 11 * R를 검증하는 것은 사실 5 * p + 7 * q = 11 * r를 검증하는 것입니다). 타원 곡선 쌍은 변수 간의 이차 제약을 검증하게 해줍니다(검증 e(P, Q) * e(G, G * 5) = 1은 사실 p * q + 5 = 0을 검증하는 것입니다). 이차 제약을 수행할 수 있게 되면, 결정론적 임계값 서명, QAP(이차 산술 프로그램, 일종의 제로 지식 증명) 등과 같은 흥미로운 응용을 수행할 수 있습니다.

이제 우리가 위에서 도입한 e(P, Q) 연산자가 도대체 무엇인지 질문이 생깁니다. 이것이 바로 "쌍"의 집합입니다. 수학자들은 때때로 이것을 "이중 선형 맵"이라고 부르며, 여기서 "이중 선형"은 기본적으로 다음 조건을 만족함을 의미합니다:

e(P, Q + R) = e(P, Q) * e(P, R)
e(P + S, Q) = e(P, Q) * e(S, Q)

여기서 +와 *는 임의의 연산자일 수 있습니다. 새로운 수학 객체를 만들 때, 추상 대수에서는 +와 *가 어떻게 "정의"되는지에 대해 신경 쓰지 않으며, 우리가 익숙한 연산과 일치하기만 하면 됩니다. 예를 들어 a + b = b + a, (a * b) * c = a * (b * c), (a * c) + (b * c) = (a + b) * c와 같은 것입니다.

현재 P, Q, R, S가 단순히 숫자라면, 쌍 함수는 매우 쉽게 구성할 수 있습니다: 우리는 e(x, y) = 2^(xy)로 정의할 수 있습니다. 그러면 다음과 같은 결과를 볼 수 있습니다:

e(3, 4 + 5) = 2^(3 * 9) = 2²⁷
e(3, 4) * e(3, 5) = 2^(3 * 4) * 2^(3 * 5) = 2¹² * 2¹⁵ = 2²⁷

실제로 이중 선형입니다!

그러나 이렇게 간단한 쌍은 암호학에 적합하지 않습니다. 왜냐하면 정수에서 작동하는 수학 객체를 분석하는 것은 매우 쉽기 때문입니다. 정수의 성질로 인해 나눗셈, 로그 등 많은 연산이 쉽게 이루어집니다. 정수는 "공개 키"나 "단방향 함수"의 개념도 없습니다. 더 나아가, 위에서 설명한 그런 쌍은 가역적입니다: x를 알고 e(x, y)를 알면 나눗셈과 로그를 통해 y를 계산할 수 있습니다. 우리가 원하는 수학 구조는 가능한 한 "블랙 박스"에 가깝게 만드는 것입니다: 덧셈, 뺄셈, 곱셈, 나눗셈을 할 수는 있지만, 그 이상은 할 수 없습니다. 이때 타원 곡선과 타원 곡선 쌍이 유용하게 사용됩니다.

사람들은 실제로 타원 곡선의 점에서 이중 선형 맵을 설계할 수 있다는 것을 발견했습니다. 즉, 입력이 타원 곡선의 두 점 P와 Q일 때, 함수 e(P, Q)를 F_p¹²의 요소로 매핑하는 것입니다(적어도 이 특정 경우에는 충분하며, 이 규범은 곡선의 세부 사항에 따라 다를 수 있습니다. 후에 다시 언급할 것입니다). 그러나 이 작업을 수행하는 데 필요한 수학은 매우 복잡합니다.

먼저, 소수 체(prime fields)와 확장 체(extension fields)를 소개하겠습니다. 위의 그림에 그려진 곡선은 아름답지만, 이는 곡선의 방정식이 일반적으로 사용되는 실수에서 정의된다고 가정할 때 그렇게 보입니다. 만약 우리가 실제로 암호학에서 실수를 사용한다면, 로그를 "되돌릴" 수 있으므로 모든 것이 무용지물이 됩니다. 게다가 실수를 저장하는 데 필요한 공간은 무한히 커질 수 있습니다. 따라서 우리는 실수 체 대신 소수 체의 숫자를 사용합니다.

소수 체는 숫자 0, 1, 2, …, (p−1)로 구성된 집합이며, 여기서 p는 소수이고, 연산은 다음과 같이 정의됩니다:

a + b: (a + b) % p
a * b: (a * b) % p
a - b: (a - b) % p
a / b: (a * b^(p-2)) % p

기본적으로 모든 연산은 모듈로(modulo) p 하에서 수행됩니다(여기서 모듈로 연산의 소개 참조). 나눗셈은 특별한 경우입니다. 일반적으로 3/2는 정수가 아니지만, 우리는 정수만 처리하고 싶기 때문에 x를 찾아야 합니다. x * 2 = 3이 되도록 하며, 여기서 *는 위에서 정의한 모듈로 곱셈을 의미합니다. 다행히도 페르마 소정리에 따라 나눗셈의 지수 정의가 필요를 충족할 수 있지만, 더 빠른 방법은 확장 유클리드 알고리즘을 사용하는 것입니다. p = 7일 때 몇 가지 예를 보겠습니다:

2 + 3 = 5 % 7 = 5
4 + 6 = 10 % 7 = 3
2 - 5 = -3 % 7 = 4
6 * 3 = 18 % 7 = 4
3 / 2 = (3 * 2^5) % 7 = 5
5 * 2 = 10 % 7 = 3

이러한 연산을 시도해보면 일관성이 있으며 모든 일반적인 규칙을 만족하는 것을 알 수 있습니다. 마지막 두 예는 (a / b) * b = a를 보여주며, (a + b) + c = a + (b + c), (a + b) * c = a * c + b * c와 같은 고등학교에서 알고 사랑했던 대수 방정식이 계속 작동함을 알 수 있습니다. 실제로 사용되는 타원 곡선, 점 및 방정식은 일반적으로 소수 체에서 연산됩니다.

이제 확장 체에 대해 이야기해 보겠습니다. 당신은 이전에 확장 체를 보았을 수도 있습니다. 수학 교과서에서 가장 흔히 접하는 예는 복소수 체입니다. 실수 체를 기반으로 sqrt(-1) = i라는 새로운 요소를 추가하여 확장한 것입니다. 간단히 말해, 확장 체는 기존의 체 위에 "새로운 요소"를 "발명"하고, 이 새로운 요소와 기존 요소 간의 관계를 정의하는 것입니다(방금 예에서 i^2 + 1 = 0); 이 관계식은 기존 숫자로 만족할 수 없으며, 이 새로운 요소를 "기존 요소의 모든 선형 조합(linear combination)"으로 구성된 집합에 추가하여 만들어진 집합입니다.

우리는 소수 체를 확장할 수도 있습니다. 예를 들어, 모듈로 7의 소수 체에 우리가 방금 언급한 i를 추가하면 다음과 같습니다:

(2 + 3i) + (4 + 2i) = 6 + 5i
(5 + 2i) + 3 = 1 + 2i
(6 + 2i) * 2 = 5 + 4i
4i * (2 + i) = 3 + i

마지막 등식은 이해하기 어려울 수 있습니다. 사실 그 등식의 첫 번째 단계는 왼쪽의 곱셈을 분배하여 4i * 2 + 4i * i로 변환하여 8i - 4를 얻는 것입니다. 우리는 모듈로 7의 환경에서 연산을 수행하고 있으므로 이 숫자는 i + 3이 됩니다. 나눗셈 부분은 다음과 같습니다:

a / b : (a * b^(p²-2)) % p

여기서 페르마 소정리의 지수가 p에서 p²로 변경되며, 물론 확장 유클리드 알고리즘을 사용하여 더 효율적으로 계산할 수 있습니다. 체의 모든 요소 x에 대해 x^(p² − 1) = 1이 성립하므로, 우리는 (p² − 1)를 "체의 곱셈 군의 차수"라고 부릅니다.

실수 체에 대해 대수 기본 정리는 그 이차 확장(quadratic extension): 복소수 체가 완전하다는 것을 보장합니다(번역자 주: 대수적으로 닫혀 있다는 의미이며, 실수 체는 완전성을 가지지만 확장될 수 있습니다). 이 체는 더 이상 확장될 수 없습니다. 왜냐하면 모든 가능한 새로운 요소 j와 기존 복소수 간에 만족해야 할 수학적 관계(엄밀히 말하면 다항식으로 정의된 수학적 관계)가 이미 체 내의 요소에 의해 만족되기 때문입니다. 그러나 소수 체에서는 이러한 문제가 없으며, 우리는 삼차 확장(cubic extension)(새로운 요소 w와 기존 요소 간의 관계식이 삼차 다항식이므로 1, w, w²가 선형 독립(linear independent)입니다), 고차 확장, 심지어 확장된 확장 등을 수행할 수 있습니다. 타원 곡선은 이러한 모듈로 연산의 복소수 위에 세워집니다.

이러한 수학이 어떻게 코드로 구현되는지에 관심이 있다면, 소수 체 및 확장 체의 예제가 있습니다.

타원 곡선 쌍으로 돌아가 보겠습니다. 타원 곡선 쌍(우리가 논의하는 쌍은 그 중 하나일 뿐이며, 쌍의 논리는 유사합니다)은 G2 × G1 → Gt의 매핑입니다. 여기서:

G1은 타원 곡선이며, 선상의 점은 y² = x³ + b 형태의 방정식을 만족하며, 점의 x, y 좌표는 F_p의 요소입니다(즉, 그들은 일반적인 숫자일 뿐이며, 산술 연산은 특정 소수로 모듈로 수행됩니다).
G2 또한 타원 곡선이며, G1의 곡선을 만족하지만 G2의 요소의 x, y 좌표는 F_p¹²의 요소입니다(우리가 방금 언급한 복소수입니다; 우리는 12차 다항식 w¹² − 18 w⁶ + 82 = 0을 만족하는 신비로운 숫자 w를 정의합니다).
Gt는 타원 곡선의 연산 결과로 형성된 집합입니다. 우리가 논의하는 곡선에서 Gt는 F_p¹²입니다(여기서 G2와 같은 복소수를 사용합니다).

그것이 주로 만족해야 하는 특성은 이중 선형성입니다. 이 맥락에서 다음과 같이 나타냅니다:

e(P, Q + R) = e(P, Q) * e(P, R)
e(P + Q, R) = e(P, R) * e(Q, R)

(번역자 주: 여기서 이중 선형성은 정확히 말하면 "정수 위의 이중 선형성(bilinearity over ℤ)"이며, 여기서 논의되는 타원 곡선의 점은 모두 정수 점이며, 곱셈과 덧셈의 정의는 정수 연산 후 모듈로를 취하므로 자연스럽게 일부 선형 성질을 만족합니다.)

쌍 함수 선택에는 두 가지 중요한 기준이 있습니다:

연산이 충분히 효율적이어야 합니다(예를 들어, 모든 점에 대해 이산 로그를 취한 다음 모두 곱하는 방법은 간단한 쌍 방법이지만, 이로 인해 필요한 연산 비용은 타원 곡선 암호학을 해독하는 것과 동일하게 어렵기 때문에 이는 고려되지 않습니다).
비퇴화(당연히 e(P, Q) = 1로 단순히 정의할 수 있지만, 이는 특별히 유용한 쌍이 아닙니다).

그렇다면 우리는 이 작업을 어떻게 수행할 수 있을까요?

쌍 함수가 작동할 수 있도록 하는 수학은 매우 어렵고, 우리가 지금까지 본 것보다 더 고급 대수가 필요하지만, 대략적으로 설명하겠습니다. 먼저 "인자(divisor)"의 개념을 정의해야 합니다. 기본적으로 이는 타원 곡선 위의 점에 작용하는 함수들을 나타내는 또 다른 방법입니다. 함수의 인자는 기본적으로 함수가 얼마나 많은 영점과 무한대의 값을 가지는지를 계산합니다. 이를 이해하기 위해 몇 가지 예를 살펴보겠습니다. 점 P = (Px, Py)를 선택하고 다음 함수를 고려해 보겠습니다:

f(x, y) = x − P_x

그 인자는 [P] + [−P] − 2 * [O]입니다(여기서 대괄호는 특정 점이 함수의 영점과 무한대의 값으로 나타나는 집합을 나타내며, 그 점 자체가 아닙니다; [P] + [Q]와 [P + Q]는 다릅니다). 이유는 다음과 같습니다:

이 함수는 P 점에서 값이 0이 됩니다. 왜냐하면 x가 Px를 취하기 때문에 x − Px = 0입니다.
이 함수는 −P 점에서 값이 0이 됩니다. 왜냐하면 −P와 P의 x 좌표가 동일하기 때문입니다.
이 함수는 x가 무한대로 갈 때도 무한대로 가므로, 우리는 이 함수가 O 점에서 무한대의 값을 가진다고 말합니다. 이 무한 원점을 계산할 때 두 번 계산해야 하므로 O는 계수 -2로 곱해집니다(부호는 무한 원점이기 때문에 영점과 다르며, 2는 두 번 계산해야 하기 때문입니다).

계산의 이유는 다음과 같습니다: 이 곡선의 방정식은 x³ = y² + b이므로, x가 증가함에 따라 y²가 비슷한 규모에 도달하기 위해 y가 증가하는 속도는 대략 x의 1.5배가 필요합니다. 따라서 선형 함수가 x만 포함한다면, 그 무한대 항의 계수는 2가 되지만, y를 포함한다면 계수는 3이 되어야 합니다.

이제 선의 함수를 고려해 보겠습니다:

ax + by + c = 0

여기서 a, b, c는 이 선이 점 P와 점 Q를 통과하도록 선택됩니다. 타원 곡선 덧셈의 작동 방식에 따라, 이 선은 반드시 −P−Q 점을 통과해야 합니다. 무한대로 갈 때 x와 y 모두에 의존하므로 인자는 [P] + [Q] + [−P−Q] − 3 * [O]입니다.

우리는 모든 "유리 함수"(즉, 점 좌표가 유한 번의 덧셈, 뺄셈, 곱셈, 나눗셈 연산으로 정의된 함수)가 특정 인자에 고유하게 대응된다는 것을 알고 있습니다. 최대한으로는 상수 하나를 곱하는 것뿐입니다(즉, 두 함수 F와 G가 동일한 인자를 가지면, 반드시 상수 k가 존재하여 F = G * k가 됩니다).

임의의 두 함수 F와 G에 대해, (F * G)의 인자는 F와 G의 인자의 합과 같습니다(수학 교과서에서는 (F * G) = (F) + (G)로 볼 수 있습니다). 따라서 예를 들어 f(x, y) = P_x − x라면, (f³) = 3 * [P] + 3 * [−P] − 6 * [O]입니다. P와 −P는 세 번 계산됩니다. 이는 특정 수학적 의미에서 f³가 "세 배 빠르게" 0에 접근하기 때문입니다.

어떤 인자의 "대괄호"를 제거하면, 그 점의 연산 결과는 반드시 O가 된다는 정리가 있습니다([P] + [Q] + [−P−Q] − 3 * [O]를 따라가면 P + Q − P − Q − 3 * O = O가 됩니다). 그리고 이러한 성질을 가진 인자는 그 함수의 인자가 됩니다.

이제 우리는 테이트 쌍(Tate pairing)을 살펴볼 수 있습니다. 다음과 같은 인자로 정의된 함수를 고려해 보겠습니다:

(F_P) = n * [P] − n * [O], 여기서 n은 G1의 차수이며, 즉 모든 P에 대해 n * P = O입니다.
(F_Q) = n * [Q] − n * [O]
(g) = [P + Q] − [P] − [Q] + [O]

이제 이 곱 FP * FQ * g^n의 인자를 살펴보겠습니다. 그 인자는 다음과 같습니다:

n * [P] − n * [O] + n * [Q] − n * [O] + n * [P + Q] − n * [P] − n * [Q] + n * [O]

정리하면 다음과 같은 깔끔한 결과를 얻습니다:

n * [P + Q] − n * [O]

이 인자의 형식이 FP와 FQ의 인자와 일치하는 것을 주목하십시오. 따라서 FP * FQ * g^n = F_(P + Q)입니다.

이제 "최종 지수(final exponentiation)"라는 작업을 추가하여 앞서 언급한 연산의 결과(FP, FQ 등)를 z = (p¹² − 1) / n의 지수로 제곱합니다. 여기서 p¹² − 1은 Fp¹²의 곱셈 군의 차수입니다(다시 말해 모든 x ϵ Fp¹²에 대해 x^(p¹² − 1) = 1입니다). 이 지수를 이미 n 차수의 결과에 적용하면, 어떤 요소의 (p¹² − 1) 차수가 되어 결과는 1이 됩니다. 따라서 마지막 지수 단계 후 g^n은 사라지고, 우리는 FP^z * FQ^z = F_(P + Q)^z를 얻게 됩니다. 이렇게 해서 이중 선형성의 일부 속성을 얻었습니다.

이제 두 매개변수에서 모두 이중 선형인 함수를 구성하려면 더 복잡한 수학이 필요합니다. 따라서 FP를 계산하는 것뿐만 아니라 FP의 인자를 계산해야 하며, 계속 진행하면 완전한 테이트 쌍을 얻을 수 있습니다. 더 많은 결론을 증명하려면 "선형 동등성(linear equivalence)" 및 와일 상관성(Weil reciprocity)과 같은 개념을 이해해야 합니다. 이러한 개념에 대한 자세한 내용은 여기와 여기에서 확인할 수 있습니다.

여기서는 테이트 쌍의 수정된 버전을 구현했습니다── Optimal Ate Pairing. 이 코드에서는 밀러 알고리즘을 사용하여 F_p를 계산하는 것도 구현되어 있습니다.

사실, 이러한 쌍을 사용하는 것은 양날의 검과 같습니다. 한편으로는 이러한 쌍을 사용하여 다양한 합의를 구현할 수 있음을 의미하며, 다른 한편으로는 어떤 타원 곡선을 선택할 때 특별히 주의해야 함을 의미합니다.

각 타원 곡선에는 embedding degree라는 값이 있습니다. 이는 p^k − 1이 n의 배수가 되는 최소 정수 k입니다(p는 체에서 사용하는 소수이고, n은 곡선의 차수입니다). 위에서 언급한 체에서 k = 12이며, 전통적인 타원 곡선 암호학에서(쌍을 고려하지 않을 때) 사용되는 체의 embedding degree는 일반적으로 매우 큽니다. 이는 쌍을 계산하는 것이 계산적으로 불가능하게 만듭니다. 그러나 우리가 주의하지 않으면 k = 4 또는 심지어 k = 1인 체를 구축할 가능성이 높습니다.

k = 1일 때, 타원 곡선上的 "이산 로그 문제"(P = G * p라는 점만 알고 p의 값을 계산하는 것; 즉, 타원 곡선의 개인 키를 "해독"할 때 해결해야 하는 문제)는 F_p에서 상대적으로 간단한 문제로 퇴화할 수 있습니다(이 방법을 MOV 공격이라고 합니다). embedding degree가 12 이상인 타원 곡선을 사용하면 이러한 퇴화가 불가능하다는 것을 보장하며, 또는 퇴화된 문제의 복잡성이 적어도 "정상적인" 방법으로 공개 키에서 개인 키를 계산하는 것만큼 어렵게 됩니다. 현재 모든 표준 곡선 매개변수는 면밀히 검토되어 이 문제의 영향을 받지 않습니다.