Pairing-based Cryptography와 BLS signature의 이해 — Part 2

Part 1에서는 Pairing-Based Cryptography(이하 PBC)를 이해하기 위한 기본적인 수학과 Elliptic Curve Cryptography(이하 ECC) 개념에 대해 설명했다.

Part 2는 PBC에 대한 원리와 구성 요소에 대해 기술한다. 사실 pairing 함수는 수학에서 상당히 오래 전부터 사용된 용어이며 PBC에서 pairing 함수를 논할 때 가장 먼저 소개하는 Weil pairing도 이미 1940년대에 소개된 개념이다. 타원곡선을 만나면서 암호학에서 사용될 수 있다는 것이 밝혀진 것은 비교적 최근의 일이다. 사실 ECC의 역사 자체가 대수학의 역사에 비하면 아주 짧다.

이 글은 수학적으로 기초부터 기술하기 보다는 먼저 현대 암호학에서 중요한 개념 중 하나인 Diffie-Hellman problem의 관점에서 Gap Group을 소개하고 만약 이런 Gap Group과 Bilinear Map(즉 pairing 함수)이 있다면 할 수 있는 일을 개념적으로 설명한다.

이후 이를 가능하게 하는 G1, G2, GT 그룹과 pairing 함수를 레고 블록처럼 하나하나 기술하고 모든 레고 블록이 쌓여서 전체가 완성되어서 구동되는 모습을 보이도록 하겠다. 이 전체 모습이 바로 BLS signature이다.

그리고, BLS signature를 이용하는 개발자가 가장 잘 이해해야 하는 건 바로 이 레고 블록 각각의 구조와 특성이다.

PBC 자체가 대수학을 기초로 구성된 암호학이기 때문에 수학적 기법을 쓰지 않고 설명하는 데에는 분명히 한계가 있다. 그러나, 공부할 것이 너무나도 많은 개발자들을 위해 중요 개념들에 대해 최대한 수학적인 기법을 쓰지 않고 쉽게 설명해 보도록 노력해 보겠다.

(EC)DLP 그리고 DH Problem

Part 1의 마지막에서 개인키 sk에 대한 공개키는 타원곡선 그룹 base point인 generator G에 sk를 곱한, 즉 G를 sk번 반복적으로 더한 포인트라고 했다. 그런데 얼핏 보면 pk = sk*G에서 sk = pk / G 방식으로 sk를 쉽게 구할 수 있지 않을까라는 의문이 들 수 있다. 그러나 타원곡선이 잘 설계될 경우 현실적으로 불가능하며 이 문제를 Elliptic Curve Discrete Logarithm Problem(타원곡선 이산로그문제, 이하 ECDLP)이라고 한다. ECDLP는 DLP의 타원곡선 버전으로 이해하면 되니 먼저 DLP를 설명해보자.

Whitfield Diffie와 Martin Hellman은 1976년 ‘New Directions in Cryptography’라는 논문에서 제목처럼 암호학의 혁명이라고 할 만한 키합의(key agreement) 프로토콜을 제시했고 그 공로로 2015년 튜링상을 수상했다. 기존에는 Alice와 Bob이 보안 통신을 하기 위해서 같은 암호키를 먼저 공유하고 Alice가 암호키로 메시지를 암호화해서 보내고 Bob이 같은 암호키로 복호화해서 메시지를 읽는, 소위 ‘대칭키 암호화’ 방식을 사용했다. 이 방식의 문제는 Alice와 Bob이 원격으로 떨어져 있을 경우 암호키를 공유하는 과정이 매우 어렵고 위험하다는 것이다. [그림 1]은 이 문제를 해결한 Diffie-Hellman 프로토콜을 보여준다.

[그림 1] Diffie-Hellman 프로토콜

[그림 1]에서 (Z_p)*는 prime number p에 대한 0과 p 사이의 정수 즉 {1, 2, …, p-1}이고 두 원소의 그룹 연산을 ‘두 원소의 곱하기를 p로 나눈 나머지’로 정의한다.

주) Part2에서는 아래첨자 표기가 많은 관계로 아래 같이 아래첨자를 표기하겠다.

이런 식으로 곱하기를 이용해서 그룹 연산을 정의하는 group을 multiplicative group이라고 한다. 여기에도 generator가 있는데 예를 들면 Z5*={1, 2, 3, 4} 경우 2, 2^2=4 (mod 5), 2^3=3 (mod 5), 2^4=1 (mod 5) 형태로 순환하며 Z5*를 생성한다. 따라서 2가 generator이고, Z5*는 cyclic group이 된다.

위 [그림 1]에서 Alice와 Bob은 (Z_p)*에서 각자 개인키, a와 b를 선택한 후 g^a mod p 와 g^b mod p 형태로 공개키를 생성한다. 이후 Alice와 Bob은 서로의 공개키를 주고받으면서 각자 동일한 공유키(SHK)를 생성함을 알 수 있다

주) KDF는 Key Derivation Function으로서 hashing을 포함한 적절한 bit operation을 적용하여 암호키를 생성하는 함수이다.

그런데 여기에서 문제가 있다. 만약 Alice가 B, 즉 g^b mod p 로부터 b (Bob의 개인키)를 알 수 있지 않을까? 예를 들면 log(B)를 취하면 되지 않을까? 특히 B가 modulus p를 취한 유한한 경우의 수이니 더 쉽지 않을까?

그래서 이 문제를 Discrete Logarithm Problem(이하 DLP)이라 부른다. 다행히도 p를 아주 큰 safe prime으로 선정할 경우 DLP를 풀기는 거의 불가능하다 (정확하게 말하면 아직 효율적으로 푸는 방법이 발견되지 않았다).

주) Safe prime p이란 자신도 prime이면서 (p-1)/2 도 prime인 정수를 말한다.

주) g를 2로 해도 풀기 어렵기 때문에 실제로는 2를 많이 사용한다. 믿기지 않는가? 아래 [그림 2]를 보면 openssl에서도 기본으로 generator 2를 쓰고 있다.

[그림 2] Openssl을 이용한 Diffie-Hellman 키 생성 예

그럼 이런 방식은 어떨까? 누군가 제 3자가 위의 A(=g^a mod p)와 B(=g^b mod p)를 얻어서 g^ab mod p 를 계산할 수 있지 않을까? [그림 1]에서 보듯이 Alice와 Bob이 A, B를 주고받을 때는 암호화된 통신을 하기 전이다.

바로 이 문제가 Diffie-Hellman Problem(이하 DH Problem)이다. 만약 누군가 DLP를 풀 수 있다면(B로부터 b를 계산) A^b mod p를 통해서 쉽게 DH Problem(g^ab mod p를 계산)을 풀 수 있다. 지금까지는 DLP를 푸는 방법 외에는 DH Problem에 대한 해법이 알려져 있지 않다. 다시 말하면 현재까지는 DLP를 풀지 못하면 DH Problem을 풀 수 없다.

ECDLP는 DLP의 타원곡선 버전으로 B = g^b mod p에서 b를 알기 어렵듯이, Pubkey = sk*G에서 sk를 알기 어렵다는 것으로 이해하면 된다.

DH Problem 역시 타원곡선 버전으로 해석하자면 “aG와 bG를 알 경우 abG를 계산할 수 있는가?”로 기술할 수 있다. Logarithm의 의미를 설명하기 위해서 지금까지는 g^a mod p 방식으로 기술했지만 앞으로 우리가 다룰 그룹은 타원곡선 그룹이므로 g^a mod p 방식이 아닌 aG 방식으로 기술할 것이다.

또한 p를 아주 큰 safe prime으로 잡으면 DLP를 푸는 것이 현실적으로 불가능하듯이, 타원곡선 공식과 p, q를 아주 큰 prime으로 설정하면 ECDLP와 DH Problem을 푸는 것이 불가능하다.

주) 여기서 불가능하다는 것은 현재 기술로는 거의 불가능하다는 의미이다. 미래에 퀀텀컴퓨팅이 안정적으로 작동하는 것이 정말로 가능해 진다면 비교적 단기간(수개월, 수년이 될 수도 있지만)에 DLP를 풀 수 있다는 이론이 나와 있다(Shor’s Algorithm).

주) 타원곡선도 어려운데 갑자기 (Z_p)*와 multiplicative group 이야기를 꺼내서 약간 혼란스러울 수 있다. 사실 여기에는 수학적으로도 다른 이야기가 많이 있고, 이 구조가 일반적인 DSA에 여전히 쓰인다. 미안하지만 이글 후반부에 multiplicative group이 한 번 더 나온다.

Gap Group

앞서 DH Problem을 “aG와 bG를 알 경우 abG를 계산할 수 있는가?”로 기술했다. 이를 좀 풀어서 써보면 다음과 같다.

“Alice가 개인키(a), 공개키(aG)를 가지고 Bob이 개인키(b), 공개키(bG)를 가지고 있을 때, Carol이 aG, bG를 받아서 abG를 계산할 수 있는가?”

이런 식으로 abG를 계산하는 문제를 다른 이름으로 Computational Diffie-Hellman(이후 CDH) Problem이라고 한다. 그럼 이런 방식은 어떨까?

“Eve가 Alice에게 받았다고 하면서 cG를 Carol에게 전해주었을 때 Carol은 cG가 a, b로부터 만들어진 abG와 같은지, 즉 Eve가 정말 Alice에게 받은 값을 준 게 맞는지 결정할 수 있는가? (c = ab)”

즉 Carol은 aG와 bG를 알고 있는 상태에서 abG를 계산할 능력은 없지만 Eve로부터 받은 cG (c는 모름)가 abG와 일치하는지 알 수 있는가 하는 문제이다. 이런 식의 문제를 Decisional Diffie-Hellman(이후 DDH) Problem이라고 한다. 내가 문제를 풀 능력은 없지만 채점은 할 수 있다는 것과 비슷하다.

CDH와 DDH간의 관계를 보면 CDH Problem을 풀 수 있다면 DDH Problem은 당연히 풀 수 있다. Carol이 직접 abG를 계산한 후 Eve가 준 cG와 비교하면 된다. 하지만 그 역은 성립되지 않는다. 즉 CDH Problem이 DDH Problem보다 어렵다는 뜻이다.

이때 타원곡선을 잘 정의하면 다음과 같은 특성을 가진 타원곡선 group을 만들 수 있다.

- CDH Problem을 푸는 것은 기술적으로 불가능

- DDH Problem은 효율적으로 풀 수 있음

이러한 특성을 가진 타원곡선 그룹을 ‘Gap Group’ 이라고 한다.

만약 이러한 Gap Group을 만들 수 있다면 아래 그림과 같은 디지털 사인 algorithm을 만드는 것이 가능하다. 아직 Gap Group인 타원곡선 그룹 체계도 설명하지 않았고, DDH Problem을 푸는 pairing도 설명하지 않았지만 [그림 3]에서 Gap Group을 이용한 서명의 개념을 먼저 보자.

[그림 3] Gap Group을 이용한 서명 프로토콜 예시

먼저 왼쪽 그림을 보자.

CDH Problem은 어렵고, DDH Problem은 쉬운 타원곡선 그룹 Gap Group을 GG라고 하고 GG의 generator(base point)를 G라고 하자. 이 때 Alice의 개인키를 x라 하고 공개키로 xG를 생성하고 공개키를 Bob에게 미리 전달한다.

주) ECDSA, EdDSA, EC-Schnorr, BLS Signature 등 대부분의 타원곡선 기반 암호 알고리즘에서는 같은 방식으로 공개키를 생성한다.

Alice는 서명할 메시지를 hash해서 GG안의 포인트 H로 매핑한다. 대부분의 hash 함수는 메시지를 숫자(sha256의 경우 32bytes)로 매핑하는데, 이 경우에는 (x, y) 형태의 포인트로 매핑한다.

G가 GG의 generator라는 건 G, 2G, 3G, … 형태로 GG 전체 원소를 generate하는 것을 의미하므로 반드시 어떤 h라는 숫자로 hG = H 가 된다. 물론 ECDLP 가정에 의해서 Alice와 Bob은 h가 어떤 숫자인지 알 수 없다. 다시 말하면 H에서 h를 도출할 수 없다.

Alice는 H에 개인키 x를 곱한 서명(xH)과 메시지를 Bob에게 전달한다 (xH는 실제로 xhG이다. 그러나 Bob은 x, h, xh를 알 수 없다).

이제 Bob이 알고 있는 내용은 xG (Alice의 공개키), H (메시지의 해싱, 실제로는 hG), 그리고 S (서명, 실제로는 xH = xhG)이다. 이제 남은 일은 Alice가 보낸 서명 S가 Alice의 개인키로 서명된 건지 여부를 검증(verify)하는 것이다.

정리하자면 알고 있는 xG, hG, S로부터 xhG = S 인지를 ‘결정’하는 문제, 즉 DDH Problem을 푸는 것이다.

주) 좀 더 설명하자면 서명 S 역시 GG 상의 포인트이므로 어떤 c라는 숫자로 cG = S가 된다. 역시 ECDLP 가정에 의해서 S로부터 c는 도출할 수 없다. Bob이 서명을 검증한다는 것은 xG, hG, cG만 가지고(x, h, c는 모름) xh = c 임을 결정하는 DDH Problem을 푸는 것을 의미한다.

Gap Group에서는 DDH Problem을 효율적으로 풀 수 있다고 했으니 Bob은 서명을 효율적으로 검증하는 것이 가능하다.

[그림 3]의 오른쪽 그림을 보자. Eve가 Alice의 공개키(xG)를 알고 있고 자신이 보내고 싶은 메시지의 해싱 값 H’ (H’=h’G인 h’이 존재)을 Alice인척하고 서명하고 싶다고 해보자. 물론 Eve는 Alice의 개인키 x를 가지고 있지 않다.

만약 Eve가 CDH Problem을 풀 수 있다면 xG, h’G에 대한 서명 xh’G을 만들 수 있고 이걸 Bob에게 메시지와 함께 보내면 Bob은 유효한 서명으로 검증한다. 그런데 Gap Group에서는 CDH Problem을 푸는 것이 기술적으로 불가능하므로 Eve와 같은 제3자가 Alice의 개인키 x가 없이는 유효한 서명(xh’G)을 만드는 것이 불가능하다.

요약하자면 만약 Gap Group을 만들 수 있다면 메시지의 hash에 개인키를 곱하는 것만으로 서명을 할 수 있게 된다. 이 구조로 signature aggregation을 포함해서 상당히 유용한 사인 알고리즘이 만들어질 수 있고 이것이 바로 Part3에서 설명할 BLS signature이다.

이 그림에서는 공개키 xG와 서명 S가 동일한 타원곡선 그룹 GG의 포인트이다. 이런 방식을 symmetric pairing이라 한다. 그런데 대부분의 실용화된 타원곡선 그룹과 BLS signature는 G1, G2라는 서로 다른 두 개의 타원곡선 그룹(그러나 order는 같은)으로 공개키와 서명을 표현한다. 이를 asymmetric pairing이라 한다.

Notation을 asymmetric pairing 방식으로 완전히 다시 정의해 보자.

G1이 공개키의 타원곡선 그룹이고 G2를 서명의 타원곡선 그룹이라고 하자. 그리고, 각각의 base point를 P, Q라고 하자.

이때 Alice의 개인키는 sk (scalar), 공개키는 sk*P (G1 안의 포인트)가 되고, 서명할 메시지 msg의 hash 값은 H(msg) (G2 안의 포인트이며 어떤 h에 대해 h*Q가 됨)가 된다고 하자. Alice는 서명 S = sk*H(msg)을 만들어서 메시지 msg와 S를 Bob에게 보낸다.

이제 Bob이 가진 정보는 Alice의 공개키 sk*P, 메시지 msg의 hash 값 H(msg) = h*Q, 서명 S이다.

Bob은 sk와 h를 모르는 상태에서 위 정보들(sk*P, h*Q)만으로 ‘Alice가 적법한 개인키 sk로 서명했는지’를 검증, 즉 S = sk*h*Q임을 확인하게 된다. 조금 복잡해지기는 했지만 위의 DDH problem을 푸는 것과 같은 구조이다. 그리고 sk를 모르는 상태에서는 적법한 서명 S를 만들 수 없어야 되는 가정도 동일하다.

이때 DDH problem을 풀기 위해 쓰는 쓰이는 함수가 pairing 함수이며 e: G1 X G2 → GT 형태로 G1과 G2에서 각각 하나의 포인트를 인수로 받아서 GT에 속하는 값을 산출한다. GT에 대해서는 뒤에서 설명하겠다.

Bob이 pairing 함수를 써서 서명을 검증하는 식은 다음과 같다:

Check e(sk*P, h*Q) == e(P, S)

서명 S가 적법한 서명이라면 오른쪽 식은 e(P, sk*h*Q)가 된다. 얼핏 보면 함수 첫번째 인수의 sk가 두번째 인수 쪽으로 옮겨간 것으로 보이는데 이게 바로 bilinearity 라는 특성이다.

Asymmetric pairing 형태로 notation을 바꿔서 설명한 서명 과정이 바로 BLS signature이며 글 후반부에 그림으로 다시 보이겠다.

주) Gap Group은 Gap Diffie-Hellman Group이라고도 부르며, asymmetric pairing인 경우에는 Co-gap (Diffie-Hellman) group이라고도 부른다. 어떤 이름이든지 CDH problem이 어렵고 DDH problem이 쉽다는 개념은 같다.

Bilinear Map

위에서 설명한 대로 PBC에서의 pairing 함수 e는 두 타원곡선 그룹의 포인트를 입력 받아서 하나의 값(scalar)을 출력하는 함수이다. 이를 수학적으로 표현하자면 두 타원곡선 그룹, G1과 G2에서 다른 그룹 GT로 매핑하는 아래의 함수를 의미한다:

e: G1 X G2 → GT

P가 G1에 속하는 원소이고, Q가 G2에 속하는 원소라고 하자.

이때 bilinearity 특성을 가진 함수는 e(2P, Q) = e(P+P, Q) = e(P, Q)*e(P, Q) 혹은 e(P, 2Q) = e(P, Q+Q) = e(P, Q)*e(P, Q) 라는 성격을 가진다. aP가 P를 a번 더한 값이므로 위 식을 좀 더 일반화해서 표현하자면 다음과 같다.

e(aP, bQ) = e(P, bQ)^a = e(P, Q)^ab = e(P, aQ)^b = e(bP, aQ)

결과적으로 이 식의 a, b가 입력값의 왼쪽 오른쪽으로 자유롭게 이동 가능하다(e(aP, bQ) = e(bP, aQ)). 위에서 Bob이 검증에 쓰는 식을 예로 들면 다음과 같다:

e(sk*P, h*Q) = e(P, h*Q)^sk = e(P, sk*h*Q)

Pairing의 다른 조건으로는 non-degeneracy가 있다.

G1의 모든 P에 대해서 e(P, Q) = 1 (GT의 항등원)이면 Q는 𝒪 (타원곡선 그룹의 항등원)이다. 또한 G2의 모든 Q에 대해서 e(P, Q) = 1이면 P는 𝒪 이다.

주) 쉽게 말하면 모든 P, Q에 대해서 e(P, Q) = 1 로 정의해도(constant map) bilinearity가 성립되는데, 이러지는 말자는 얘기다.

레고 블록들: PBC의 전체 구조

Part 1에서는 ECC를 잘 쓰기 위해서 p와 q를 이해하는 것이 중요하다고 말했는데 같은 맥락으로 타원곡선 기반 PBC를 적용한 개발을 위해서는 [그림 4]에 나온 p와 G1/G2/GT의 구조(사이즈 및 order)에 대해 이해하는 것이 정말 중요하다.

주) [그림 4]는 BLS12–381 커브의 주요 정보를 golang과 herumi 라이브러리를 써서 인쇄한 내용이다. Herumi 라이브러리에 대해서는 Part 3에서 간략하게 소개하겠다.

물론 이것들을 이해하려면 pairing-friendly 타원곡선 그룹과 pairing 함수의 이론적 배경에 대해 어느 정도는 숙지해야 한다.

[그림 4] BLS12–381 커브의 F_p, G1, G2, GT 구조

일단 F_p, 즉 base field는 Part 1에서 설명한 secp256k1에서의 역할과 같다. 즉 타원곡선 그룹의 포인트를 구성하는 x, y 좌표값이 F_p에 속하며 x, y는 modular p의 연산으로 타원곡선 식(위 그림의 BLS12–381의 경우 y^2 = x^3 + 4 (mod p))을 만족한다. BLS12–381의 경우 p의 크기를 381 bits로 한다. 그래서 커브의 이름에 381이 붙었다.

주) 위 그림에서 F_p의 크기가 384 bits로 나오는데 바이트 단위로 하다 보니 3 bits가 남는다. 그런데 이걸 BLS signature에서는 아주 요긴하게 쓴다. Part 3에서 간단히 소개하겠다.

그런데 [그림 4]에서 주목할 점은 G1, G2, GT가 같은 order를 가진다는 것이다. 또 하나 주목할 점은 같은 order를 가지면서도 숫자의 크기가 다르다는 것이다(Size를 보라). 즉 이들을 구성하는 숫자가 속하는 수학적 구조가 다르다는 의미이다. 그리고 마지막 GT의 경우에는 타원곡선 그룹의 포인트가 아닌 scalar 값이다.

독자들의 이해를 돕기 위해서 G1, G2, GT 들의 도출 과정과 상관 관계를 BLS12–381 커브의 예를 들어서 [그림 5]와 같이 도식화해 보았다. Part 2의 이후 상당 부분은 이 그림의 설명이 될 것이다.

[그림 5] G1, G2, GT의 도출 과정과 상관관계 (BLS12–381 예)

레고 블록: G1

그럼 먼저 pairing 함수에서 사용하는 타원곡선 그룹 G1에 대해 설명해보자. Part 1에서는 주로 타원곡선 그룹의 order 자체가 prime인 경우를 다뤘다. 비트코인과 이더리움이 이용하는 secp256k1이 바로 그렇다.

그런데 PBC에서 주로 쓰는 타원곡선의 경우에는 불행하게도 타원곡선 그룹 order가 prime이 아니다. 그리고 타원곡선 그룹 전체를 사용하는 것이 아니고 이의 subgroup을 선택해서 쓰게 된다. 이 subgroup이 바로 G1이며 prime order r을 가진다. 물론 r이 충분히 큰 수가 되게 해서 ECDLP를 푸는 것이 현실적으로 불가능하도록 해야 한다. BLS12–381의 경우 G1의 order인 r의 크기는 255 bits이다.

주) secp256k1의 경우 타원곡선 그룹의 order(Part 1의 q)가 256 bits인데 G1의 경우 이 1 bits의 차이로 고려해야 할 사항들이 생긴다. 이 문제에 대해서는 아톰릭스랩의 다른 분이 좋은 글을 준비중이다. 기대해도 좋다.

그렇다면 타원곡선의 subgroup은 무엇을 의미할까? 설명을 위해서 Part 1에서 소개한 작은 타원곡선 그룹 예를 다시 가져와 보자.

F23 = {0, 1, 2, …, 22}을 base field로 할 때 y^2 = x^3 + 6x + 8 (mod 23)의 타원곡선 그룹 order는 26이다. 이때 타원곡선 그룹은 26의 prime divisor(약수)인 13을 order로 가지는 cyclic subgroup을 가지게 된다. [그림 6]은 이를 도식화 했는데 먼저 26개의 타원곡선 그룹을 파란색 점으로 표시한 후 이중 13개의 subgroup을 빨간 원으로 표시했다. 점선은 P = (4, 21)을 generator로 해서 2P, 3P, …, 13P (= 𝒪)로 subgroup을 generate하는 모습을 보여준다.

[그림 6] 타원곡선 그룹 및 subgroup 예시

좀 더 일반적으로 설명하자면 타원곡선 그룹의 order가 prime이 아닐 경우 타원곡선 그룹은 order의 prime divisor(약수)를 order로 가지는 cyclic subgroup을 가지게 된다. prime divisor가 타원곡선 그룹의 order를 나누고, prime divisor의 제곱은 order를 나누지 않을 경우 prime divisor를 order로 가지는 subgroup은 유일하게 하나다.

[그림 6]의 예에서는 26 = 2*13이 prime divisor 13으로는 나눠지지만 13²으로는 나눠지지 않는다. 따라서 타원곡선 그룹은 위 그림에서 빨간 원으로 표기한 13개 포인트들의 집합을 order 13의 유일한 subgroup으로 가진다. 또한 13이 prime이므로 이 subgroup은 cyclic이다.

BLS12–381의 경우 E(F_p)의 order가 prime이 아니고 아래 r을 prime divisor로 가진다. 또한 r^2은 divisor가 아니므로 r을 order로 가지는 유일한 subgroup을 가지는데 이것이 G1이다.

r = 52435875175126190479447740508185965837690552500527637822603658699938581184513

주) E(F_p)의 order를 r로 나눈 값을 cofactor라고 하는데 ECC에서 아주 중요한 역할을 한다. 더 알고 싶은 분은 이 링크를 참고하시길 바란다: http://loup-vaillant.fr/tutorials/cofactor EdDSA를 설명하기 위한 글이기는 하지만 내가 아는 한 가장 친절하게 cofactor를 설명한 글이다.

그렇다면 이미 타원곡선 그룹의 order가 prime인 다른 curve(secp256k1 같은)를 쓰지 않고 왜 이렇게 복잡하게 subgroup을 뽑아서 쓰는 걸까?

앞에서 Gap Group의 핵심 요건인 DDH Problem이 쉽고, CDH Problem이 어려운 절묘한 난이도의 타원곡선 그룹이 필요하다고 했다. 이 난이도를 나타내는 중요한 지표가 있는데 그 지표가 바로 embedding degree k이다. Embedding degree는 base field의 order인 p에 대해 p^k — 1 = 0 (mod r)을 만족하는 가장 작은 정수를 말한다 (즉 p^k -1 이 r의 배수가 되는 가작 작은 k).

위의 타원곡선 예에서 p = 23, r = 13이고 23⁶ -1 = 148035888 = 0 (mod 13) 이므로 6이 embedding degree k이다.

Embedding degree가 작으면 (1에 가까우면) CDH Problem이 풀기 쉬워진다. 즉 MOV attack 등으로 ECDLP가 쉽게 풀어진다는 의미이다. 반대로 embedding degree가 너무 크면 DDH Problem을 풀기가 굉장히 어려워진다. 여기에서 ‘굉장히 어려워진다’는 것은 연산 시간이 너무 오래 걸려서 실제 시스템에 적용하기 어려워지는 것을 의미한다.

주) 정확히 표현하자면 지금까지 알려진 Weil and Tate pairing이나 이를 개선한 방식들로는 연산 시간이 너무 오래 걸린다는 뜻이다. 그리고 이 방식들 말고는 딱히 다른 방법이 발견된 바 없다.

[그림 3]의 서명/검증 예에서 본 바와 같이 DDH problem은 pairing 함수로 푸는 것이었으므로 다시 말하면 k가 너무 크면 pairing 함수의 연산이 너무 오래 걸린다는 얘기다.

Secp256k1의 경우 불행하게도 k가

192986815395526992372618308347813175472927379845817397100860523586360249056 라고 한다. PBC에 쓰기에는 완전히 불합격이다.

PBC에 잘 맞는 타원곡선을 pairing-friendly elliptic curve라고 한다. 이런 종류의 타원곡선이 가져야 하는 특징은 embedding degree k 가 100 이하이면서 적정 수준의 크기를 가져야 한다. k가 너무 크면 DDH problem이 너무 어려워지고, k가 너무 낮으면 (1, 2 정도) CDH problem이 너무 쉬워진다. 우리가 원하는 상황은 CDH problem이 어렵고 DDH problem이 쉬운 것이었다.

암호학자들이 발견한 적절한 크기의 k를 가진 유명한(특히 블록체인 업계에서) 타원곡선은 BN (Barreto-Naehrig) curve와 BLS curve가 있다. 둘 다 k가 12 정도로 CDH Problem은 매우 어렵고, DDH Problem은 효율적으로 계산이 가능하다. 두 커브 모두 Zcash 팀이 발견과 실용화를 주도했으며, BLS curve의 경우 이더리움 2.0에서 공식적으로 사용하는 타원곡선으로 지정되었다.

앞으로 우리가 자주 보게 될 BLS curve의 경우 여러 가지가 있는데 그 공식 명칭은 BLS[embedding degree]-[prime field size]로 구분된다. 이 글에서 우리가 예시로 사용할 BLS12–381의 경우 embedding degree가 12이고, 타원곡선 base field order의 크기가 381 bits이다.

주) BLS curve와 BLS signature 모두 발명자들의 이름 첫 자를 따서 명명되었다. 재미있는 사실은 같은 BLS 임에도 불구하고 L을 제외하면 다른 사람들이라는 것이다. BLS curve는 Barreto, Lynn, Scott이 발견자이고, BLS signature는 Boneh, Lynn, Shacham이 발견자이다.

G1은 F_p를 base field로 하므로 G1의 원소들인 포인트의 x, y 좌표가 F_p에 속하는 값이다. 따라서 G1의 원소는 F_p 사이즈의 두배인 사이즈를 갖는다. 그런데 x, y좌표는 Point compressed form으로 x좌표와 1 bit로도 표현이 가능하다.

주) y^2 = x^3 +ax + b 타원곡선 식에서는 y가 2차항이므로 x값으로 y값을 추출하면 두 값이 나온다. 다시 말하면 타원곡선 그룹에서는 대부분의 경우 하나의 x 값에 대해 (x, y), (x, -y) 형태의 두 원소를 가진다. y가 양수인 경우 -y = p — y (mod p)가 되는데 prime p는 홀수이므로 y와 -y는 홀수와 짝수 혹은 짝수와 홀수가 된다. 따라서 y가 홀수인지 짝수인지를 나타내는 1 bit tag만 알면 x 값만으로 (x, y)과 (x, -y) 중 하나로 포인트를 찾을 수 있다. 같은 방식으로 비트코인과 이더리움 모두 ANSI X9.62 가이드라인에 따른 point compressed form을 준용하고 있다.

BLS12–381에서 F_p를 48 bytes로 표현하면 3 bits가 남는다고 했는데 이 남는 공간에 위의 1 bit 정보를 넣는다. 따라서 G1의 원소는 48 bytes로 표현된다([그림 4]).

레고 블록: G2

적절한 크기의 k를 가진 타원곡선 그룹에서 G1이 찾아졌으니 이제 k를 이용해서 G2를 결정한다.

F_p^k를 base field로 하는 타원곡선 그룹도 역시 order r을 가지는 subgroup을 가진다. G1을 설명하기 전에 삽입한 [그림 5]를 참고하기 바란다. 타원곡선 공식은 G1을 찾을 때와 같은 공식을 사용한다.

좀 신기하게 들릴 수 있겠지만 k 보다 작고 1보다 큰 i 로 만든 F_p^i를 base field로 할 경우 생성된 타원곡선 그룹은 order r을 가진 subgroup을 가지지 않는다. 즉 F_p^k에서 최초로 order r을 가진 subgroup이 발견된다.

주) F_p², F_p³, F_p⁴, … 방식으로 field를 확장해 나가는 것을 field extension이라 한다.

주) F_p^k를 base field로 하는 타원곡선 그룹에는 이전에 없던 order r subgroup이 갑자기 r+1개 출현한다. 놀랍지 않은가.

그런데 p도 굉장히 큰 숫자인데, p^12은 우리가 사용하기에는 너무나도 큰 숫자이고 연산에 상당한 시간이 걸린다. 이를 해결하기 위해서 쓰는 좋은 도구로 twist라는게 있는데 복잡한 base field 상의 group 연산을 보다 단순한 base field 상의 group 연산으로 전환시킬 수 있다 (수학적으로 두 group을 isomorphic하다고 한다).

Twist는 타원곡선의 구조에 따라 F_p^k에서의 연산을 F_p^(k/2), F_p^(k/3), F_p^(k/4), F_p^(k/6)로 이동시켜서 할 수 있게 해준다. 특히 y² = x³ + ax + b에서 a가 0일 경우 F_p^(k/6)로 이동시킬 수 있는데 BLS12–381에서는 공식이 y² = x³ + 4 이므로 적용이 가능하다. 따라서 k = 12 임에도 결국 F_p¹²에서의 연산을 F_p²에서 하는게 가능해진다. 다만 이때 타원곡선 식이 y² = x³ + 4*(1 + i) 약간 바뀐다.

주) i는 복소수(complex number)에서 쓰는 허수의 단위이다 (i² + 1 = 0). 그리고 F_p²의 수 연산 체계는 복소수 연산 체계를 쓴다.

Base field F_p¹²로 y² = x³ + 4에서 order r을 가지는 subgroup은 바로 이 twist를 통해서 F_p²로 y² = x³ + 4*(1 + i)에서 order r을 가지는 subgroup으로 전환되는데 이게 바로 G2이다. 그리고 G2도 order r을 가진다 ([그림 5] 참조).

주목할 점은 G2의 원소(포인트)를 구성하는 x와 y는 F_p²에 속하므로 2 X 381 bits로 표현된다는 점이다. 그러므로 G1의 원소에 비해 2배의 공간을 필요로 한다. Part 3에서 언급하겠지만 G1과 G2의 역할을 정할 때 이 부분을 고려하게 된다.

어쨌든 G2의 경우 G1보다 두배의 공간인 96 bytes로 compressed form 형식의 포인트 원소를 표현한다 ([그림 4]).

레고 블록: GT

F_p^k에서 0을 빼면 거대한 multiplicative group이 된다. Order는 p^k — 1이 된다(0을 빼므로). 그런데 k가 embedding degree라면, 즉 order인 p^k — 1가 r로 나눠진다면 F_p^k 안에서 order r인 multiplicative cyclic subgroup을 만들 수 있다. 이게 바로 GT이다. GT의 order인 r이 prime이므로 GT의 원소들이 모두 generator가 될 수 있다 (즉 GT의 원소 a는 a, a², a³, …, a^r = 1 (mod F_p^k)형태로 GT를 generate 한다). 또한 GT의 모든 원소들은 r 제곱을 했을 때 곱셈의 항등원인 1이 된다.

주) r 제곱을 했을 때 항등원 1을 만드는 수를 r-th root of unity라고 한다. 예를 들면 복소수의 경우 {1, -1, i, -i}가 4-th root of unity가 된다((-i)⁴=1). GT 안의 모든 원소는 r 제곱(modular F_p^k 연산으로)을 할 경우 1이 되므로 GT는 F_p^k 내부의 r-th root of unity 집합이다. Root of unity 개념은 이 글을 이해하는 데에는 몰라도 되지만 다른 문서를 읽을 때 자주 등장하므로 알아두면 좋다.

G1과 G2의 order가 각각 r이므로 G1 X G2의 경우의 수는 r^2이 되는데 pairing 함수의 결과값인 공간 GT의 order가 r이라는게 이상하게 느껴질 수 있다. 그런데 모든 a, b에 대해 e(aP, bQ) = e(P, abQ)이므로 결국 왼쪽 입력 P를 고정한 상태에서 a와 b의 조합으로 가질 수 있는 결과값의 수가 e함수의 전체 결과값 수와 같아진다. 바로 r이다. 반대로 e(abP, Q)로 Q를 고정한 상태에서 가질 수 있는 결과값의 수도 r이다. 그래서 bilinearity 속성을 가지기 위한 G1, G2, GT의 order가 같아지는 것이다.

GT의 원소들은 scalar 값이기는 하지만 F_p^k에 속하므로 F_p의 원소들에 비해 k배의 size를 가지게 된다. BLS12–381에서 F_p는 48 bytes로 표현되므로 F_p¹²속의 GT는 48X12 = 576 bytes로 표현된다 ([그림 4]).

레고 블록: pairing 함수

그렇다면 Bilinearity 속성을 가진 pairing 함수 e는 어떤 모습일까?

1940년에 Andre Weil이 Weil pairing을, 1960년 전후로 John Tate가 Tate pairing을 제시하여 e가 만들어질 수 있음을 증명했다. 현재는 Tate pairing을 개선한 optimal Ate paring을 많이 쓰고 있고 상황별로 더 빠른 paring 함수를 찾는 연구는 현재진행형이다.

Weil and Tate pairing 함수를 설명하려면 torsion, divisor, coset 등등, 뭐 이런 수학적 기법들을 동원해야 하는데, 이것들 하나하나가 만만치 않고 자칫 잘못 설명하면 글이 더 난해해진다. 더 깊이 공부하고 싶은 분들은 아래 글들을 읽으시기 바란다:

http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf

수학적인 설명을 예시와 함께 가장 친절하게 설명한 문서로 보인다. 필자도 이글을 쓰면서 많이 참고한 문서이다. 다만 문서 제목이 Pairings for Beginners라고 해서 아주 쉽다고 생각하면 오산이다.

https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

비탈릭이 divisor 하나만 가지고 설명을 시도한 글도 있다. 참고하시기 바란다.

Tate pairing 함수의 모양은 이렇게 생겼다:

D_Q를 제외하고는 우리가 앞에서 본 notation과 같다. D_Q는 Q에 대한 degree zero divisor라는 건데 그냥 그런 게 있다고 생각하고 넘어가자.

이 함수를 계산하려면 f_1,P → f_2,P → f_3,P → … → f_r,P 방식으로 loop를 돌면서 P에 맞는 함수를 찾아가는 연산을 해야 한다. 문제는 r이 위에서 본 것처럼 255 bits 크기의 굉장히 큰 숫자이기 때문에 이런 식으로 loop를 돌면 실용적으로 쓰기에는 계산이 너무 오래 걸린다.

2000년대 초에 Miller’s Algorithm이 소개된 후에 실제 쓸 수 있는 수준의 pairing 함수 연산 방법이 개발되기 시작했다. 이 algorithm에서는 f_n,P → f_2n,P 방식을 통해서 loop 수를 획기적으로 줄이는 것을 가능하게 한다 (O(r) → O(log(r)).

주) Millier’s algorithm을 만든 Victor S. Miller는 Neal Koblitz와 같은 시기에 ECC를 발명한 분이기도 하다.

주) 이 loop 축소 기법은 타원곡선에서 scalar to point multiplication에도 적용 가능하다. Part 1에서도 소개한 링크 https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Double-and-add 를 참고하면 쉽게 이해될 것이다. 아무리 큰 scalar와 포인트의 곱도 point doubling과 point addition의 조합을 최대 256회(타원곡선 그룹 order가 256 bits일 경우) loop 내에서 연산이 가능하다.

이후로 이 Miller’s algorithm의 단위 연산과 loop 수를 줄이는 데에 연구가 집중되었고 지금 쓰이는 알고리즘은 optimal Ate algorithm이라 한다.

주) Ate pairing은 Tate pairing에 대한 오마주인데 더 빠르므로 T를 뺐고, 다른 의미로는 그전에 나왔던 Eta pairing의 입력값과 역순으로 입력 받는다고 해서 Eta의 알파벳 역순을 썼다고 한다. 이후 Ate pairing을 더 최적화한 optimal Ate pairing이 나왔다.

Pairing 함수는 ECC가 나오기 한참 전에 수학자들이 이미 만들어 놓은 개념이다. 다만 ECC를 만나서 실용적으로 암호학에서 쓸 수 있는 상황이 만들어졌다고 볼 수 있다. 반대로 현대의 pairing-friendly 타원곡선을 설계할 때 지금까지 연구된 pairing 함수에서 보안성이 높으면서도 빠른 연산이 가능하도록 설계한다.

PBC와 ECC의 관계는 일종의 천생연분이라고 볼 수 있겠다.

지금까지 나온 G1, G2, GT, pairing 함수를 모아서 연산 메커니즘을 정리해 보자. Pairing 함수 e(∙, ∙) 가 bilinear한 속성을 가진다면 G1, G2, GT 간의 매핑을 [그림 7]과 같이 도식화할 수 있다.

[그림 7] Pairing 연산 메커니즘 예시

[그림 7]의 1번 그림에서 e(P, Q) = m이라고 할 때(P∈G1, Q∈G2, m∈GT) 2, 3번 그림을 보면 P를 aP로 치환하거나, Q를 aQ로 치환하면 m이 m^a로 움직이는 걸 볼 수 있다. 따라서 e(aP, Q) = e(P, aQ)가 성립된다. 또 4번 그림을 보면 e(aP, bQ) = m^ab = e(P, Q)^ab 형태로 움직이는 걸 볼 수 있다.

레고블록을 모은 전체 그림

[그림 8]은 지금까지 소개한 레고 블록들(G1, G2, GT, e)을 모아서 [그림 3]을 재구성했다.

[그림 8] 레고 블록, G1, G2, GT, e를 이용한 [그림 3]의 재구성

Bob이 검증하는 방법은 바로 e(xP, hQ)와 e(P, S)의 비교이며 S가 Alice의 개인키 x로 서명된 것이 맞다면(즉 S=xhQ) 오른쪽 그림에서 보는 바와 같이 두 pairing 함수의 결과값이 같아질 것이다.

어플리케이션: Joux’s One round Three Party Key Exchange

마지막으로 PBC를 이용한 재미있는 프로토콜을 하나 소개하고 Part 2를 마칠까 한다. 2000년에 소개된 Joux의 프로토콜로 삼자가 한번의(one round) 교신으로 키합의를 이루는 프로토콜이다. 이 프로토콜이 2000년대 초에 PBC를 주목받게 하고 급격한 알고리즘 발전을 촉발한 계기가 되기도 했다.

[그림 1]에서 소개한 Diffie-Hellman 프로토콜은 양자간 키합의가 목적이었기 때문에 세 명의 키합의를 구성하는 데에 여러 단계를 거치게 된다. 2000년에 Antoine Joux는 PBC를 이용해서 세 명의 키합의를 한 번에 실행하는 알고리즘을 공개한다. 그 구성은 [그림 9]와 같다.

주) Joux의 원래 버전은 G1과 G2가 같은, 즉 symmetric pairing을 이용했는데 앞 글과의 일관성을 맞추기 위해 G1과 G2가 다른 asymmetric pairing을 이용한 약간 수정한 버전으로 소개한다.

[그림 9] One-round, Three Party Key Exchange (modified version from Joux’s original protocol)

Alice, Bob, Carol은 각각 a, b, c의 개인키를 만든 후 시계 방향으로는 G1의 base point P에 개인키를 곱한 포인트를 보내고, 반시계 방향으로는 G2의 base point Q에 개인키를 곱한 포인트를 보낸다 (one round). 이후 각 참여자는 받은 두 개의 공개키로 pairing 함수를 실행한 후 여기에 자신의 개인키를 제곱한다. 예를 들면 Alice는 Bob이 보낸 bP와 Carol이 보낸 cQ로 pairing 함수를 실행한 후 자신의 개인키 a를 제곱하여 e(bP, cQ)^a = e(P, Q)^abc를 계산한다. 결과적으로 삼자 모두 같은 값을 갖게 되고 이후 이 값(실제로는 이로부터 유도된 암호키)을 공유 암호키로 사용하여 암호화된 보안통신을 하게 된다.

긴 글을 인내심을 가지고 읽어준 독자분들에게 감사드린다. 되도록이면 수학적인 내용을 줄이고 개념적으로 설명하려 했으나 Part 2는 아무래도 딱딱하고 재미없게 느껴졌으리라 생각된다. 그러나 BLS signature, 나아가 PBC를 제대로 사용하기 위해서 꼭 알아야 하는 개념들을 축약해서 정리했으니 가급적이면 Part 3를 읽기 전에 Part 2를 천천히 읽어보기를 권한다.

Part 3에서는 Part 2에서 설명한 내용을 바탕으로 BLS signature의 기술적 특성과 적용 사례에 대해 설명하겠다.