Intro

이 문서는 타원곡선 암호학(Elliptic Curve Cryptography, 이하 ECC)를 학문적으로 기술하는 문서는 아니다. 다만, 개발자들이 암호학의 원리를 잘 이해하고 실수 없이 코딩할 수 있도록 도움을 주기 위해 암호학에 대한 이해가 필요하다고 생각한다. 논문의 영역과 개발자에게 필요한 지식의 영역 그 경계선까지, 즉 어느정도 심도 깊게 내용을 다룰 예정이다.

타원곡선 암호학를 이해하는 데에 꼭 필요한 수학적 개념들

우리가 보게 될 실용화된 블록체인은 타원곡선 암호학(Elliptic Curve Cryptography, 이하 ECC)을 기반으로 하기 때문에 이를 이해하기 위해서는 ECC의 이론적 지식은 물론 ECC의 기반이 되는 수학적 지식이 꼭 필요하다. ECC를 이해하기 위해 꼭 이해해야 하는 수학적 개념은 field와 group이다. 이 중에서도 사실 ECC에서는 group이 중요하다.

Group와 Field

Group과 field는 위 그림의 조건들(axioms)을 만족하는 집합을 의미한다.

Group의 대표적인 예는 정수이다. Field의 예는 유리수(두 정수 a, b에 의해 a/b로 표현될 수 있는 집합)이다.

• Group : 1,2,3,5,7
• Field : 3, 2/5, 2.13

Field의 조건을 만족하면 group의 조건도 만족하기 때문에 모든 field는 group이기도 하다. 따라서 유리수는 group이기도 한다. 반대로 group인 정수는 field가 될 수 없는데 예를 들면 3의 역수(inverse), 즉 곱해서 곱의 항등원(identity) 1을 만드는 수가 정수에는 없기 때문이다.

group과 field는 무한한 개수를 가지는 집합이지만, 암호학에서는 유한(finite)한 개수를 가지는 finite field와 finite group을 다룬다.

무한한 수(in-finite)를 대상으로 암호 체계를 구성하면 더 안전하리라 생각할 수도 있다. 그런데 아무리 안전해도 만약 현대의 컴퓨터로 서명하거나 암호화하는 데에 너무 긴 시간이 걸린다면 그 활용 범위가 너무 제한적이다.

이를 위해서 암호학에서는 finite group, finite field와 이의 기초 연산(더하기, 곱하기)으로 modular 연산을 주로 이용한다.

📌 Modular 연산이란?

modular 연산을 한글로 ‘합동연산’이라 부른다. 쉽게 이해하자면 어떤 2 이상의 자연수 N에 대해 N보다 작은 ‘두 수의 더하기 혹은 곱하기’는 산술적인 합 혹은 곱을 N으로 나눈 나머지로 정의하는 개념이다. 이때의 N을 modulus라고 한다.

[ Example ]

우리 생활속에서 보면 20시에서 10시간이 지나면 6시가 되는데, 이 경우 20시+10시를 하루의 단위인 24시로 나눈 나머지인 6시로 계산하는 modular 24 연산을 적용한 것이다.

modular 연산을 이용하면 유한한 개수를 가진 finite group과 finite field를 어렵지 않게 만들 수 있다.

예를 들면 Z5 = {0, 1, 2, 3, 4}는 modulus 5를 적용한 더하기/곱하기 연산에 대해 finite group이자, finite field이다. 위의 group axiom과 field axiom을 체크해 보기 바란다.

위와 같이 N보다 작고 0 이상의 정수 집합을 ZN이라 표기한다. 이때 finite group 혹은 finite field의 원소 개수를 order(차수)라 하고 |ZN| 으로 표기한다. 만약 N이 prime(소수, 1과 자기 자신 외의 다른 수로는 나눌 수 없는 수)이면 ZN 자체는 언제나 finite field가 된다 (당연히 finite group 도 된다). 다행히 모든 ECC에서 다루는 기초 수 체계는 prime N인 finite field를 다룬다.

cyclic group(순환군)과 generator(생성원)

ECC를 이해하기 위해 cyclic group(순환군)과 generator(생성원)를 알아보자.

2 (mod 5) = 2
2+2 (mod 5) = 4
2+2+2 (mod 5) = 1
2+2+2+2 (mod 5) = 3
2+2+2+2+2 (mod 5) = 0
2+2+2+2+2+2 (mod 5) = 2

Z5={0,1,2,3,4}에서 5에 대한 modular 더하기 연산으로 2를 하나씩 더해보자.

‘2 → 4 →1 →3 → 0’ 형태로 Z5의 모든 원소를 만들어 내고(generate), 그 후 다시 2로 회귀(cyclic)하고 있다. 즉, 예시에 대해 원소 2는 0,1,2,3,4를 만들어 내고 있다.

이렇게 자신이 속한 group을 modular 더하기 연산으로 만들어 내는(generate) 원소를 generator라고 한다. 나머지 1, 3, 4도 해보자.

1 (mod 5) = 1
1+1 (mod 5) = 2
1+1+1 (mod 5) = 3
1+1+1+1 (mod 5) = 4
1+1+1+1+1 (mod 5) = 0
1+1+1+1+1+1 (mod 5) = 1

3 (mod 5) = 3
3+3 (mod 5) = 1
3+3+3 (mod 5) = 4
3+3+3+3 (mod 5) = 2
3+3+3+3+3 (mod 5) = 0
3+3+3+3+3+3 (mod 5) = 3

4 (mod 5) = 4
4+4 (mod 5) = 3
4+4+4 (mod 5) = 2
4+4+4+4 (mod 5) = 1
4+4+4+4+4 (mod 5) = 0
4+4+4+4+4+4 (mod 5) = 4

Z5={0,1,2,3,4}의 모든 원소가 다른 Z5의 모든 원소를 만들어내고 있다. 즉, 모든 원소가 generator가 가능한 group를 cyclic group 라고 한다.

1+1+1+1+1 (mod 5) = 0
2+2+2+2+2 (mod 5) = 0
3+3+3+3+3 (mod 5) = 0
4+4+4+4+4 (mod 5) = 0

또 하나 주목할 점은 ZN의 모든 원소는 자기 자신을 N번 더할 경우 반드시 0이 된다.

Modular N을 적용하니 당연해 보이겠지만 타원곡선 등 좀 복잡한 group에서는 매우 중요한 특징이 된다.

ECC에서 사용하는 group이 바로 cyclic finite group이며 모든 원소가 generator가 될 수 있다. 물론 여기에서 사용하는 더하기 연산은 좀 복잡하다. 말한대로 수학자들이 말하는 ‘더하기’를 순진하게 초등학교에서 배우는 더하기로 생각하지 말기 바란다.

타원곡선 암호학(Elliptic Curve Cryptography:ECC)

Weierstrass equation

우리가 자주 쓰는 타원곡선은 위와 같은 공식으로 표현된다. 이러한 형태의 식을 Weierstrass equation이라고 한다.

Bitcoin과 Ethereum, 그리고 이들로부터 fork된 다른 블록체인들은 대부분 secp256k1이라는 타원곡선을 쓰고 있다.  의 식은 a와 b에 각각 0, 7을 적용한다. 이 그래프를 x-y 평면에 그려보면 다음 그림의 왼쪽과 같다.

그림 오른쪽에서 파이썬에서 secp256k1의 파라미터들을 나열했는데, a와 b에 0과 7이 지정되어 있음을 볼 수 있다. 그런데 굉장히 큰 수인 p, q는 무엇을 의미할까?

결론부터 말하자면 p는 타원곡선 base field의 order, q는 타원곡선 group의 order이다. 위의 타원곡선 일반 공식을 보다 정확히 적자면 위와 같다.

---

타원곡선 base field는 위 식을 만족시키는 a, b, x, y가 속한 finite field를 의미한다. 앞에서 {0, 1, 2, …, p-1}과 같이 0 이상이고 p보다 작은 정수의 집합을 Zp로 표기하고 p가 prime(실수)이면 finite field라고 했다.

지금부터는 field임을 표시하기 위해 Fp로 표기한다. a와 b의 경우 타원곡선 종류에 따라 지정*(a와 b에 각각 0, 7을 적용한다.)되어 있다. 위 식을 만족하는 (x, y) 좌표들의 집합이 타원곡선 group이 되며 E(Fp)로 명시한다.

• ECC Finite Field (base field) : Fp
• ECC group(Cyclic Group) : E(Fp)

Modular 연산을 통해서  $y^2=x^3+ax+b~(mod~p)$을 만족하는 모든 (x, y) 집합과 한 원소(point of infinity)를 타원곡선 그룹이라 한다. 이때 x, y는 Fp에 속하는 원소이기 때문에 Fp는 타원곡선 그룹 E(Fp)의 base field라고 부른다. Point of infinity는 타원곡선 group의 더하기 연산의 항등원 역할을 한다.

타원곡선 group이 prime order인 것으로 가정(즉 q가 prime)하고 설명을 진행하겠다.*아닌 경우도 많음. 이더리움과 비트코인에서 사용하는 ECC의 secp256k1의 타원곡선 그룹 order도 prime이며 이게 바로 위 파이썬 코드의 q이다. 즉 타원곡선 group 원소의 차수(order)가 q이며, 0보다 크고 11579….4337(=q)보다 작은 소수(prime) 집합을 갖는다.

예를 들면 F23 = {0, 1, 2, …, 22}을 base field로 할 때 $y^2 = x^3 + 20x + 8~(mod~23)$ 의 경우 타원곡선 Group의 order는 31이 된다. F23의 원소를 x와 y에 대입하여 모든 경우의 수를 비교해보면( 23 * 23 회 ) 공식에 만족하는 좌표의 개수는 31개이다.

너무 큰 수의 base filed는 Schoof’s algorithm을 적용해서 타원곡선 그룹 order를 도출해 낸다.

위 그림은 F23을 base field로 할 때 $y^2 = x^3 + 20x + 8~(mod~23)$ 를 만족시키는 (x, y) 원소 좌표 31개를 표시한 그래프를 보여준다. 이중 한 점 (16, 13)에 자기 자신을 하나씩 더했을 때 31번째에 항등원(point of infinity)이 나오고 전체 타원곡선 그룹을 만들어 내는 것을 보여주고 있다. 앞에서 말한 cyclic group과 generator의 바로 3번째 항등원의 특징이다. 정리하자면 order q가 prime일 경우 타원곡선 그룹은 다음의 성질을 만족하는 cyclic group이 된다. 여기서 두 포인트를 더한다는 것은 무엇을 의미할까?

어떤 수의 더하기에 대한 역원(inverse)은 더했을 때, 항등원을 만드는 수이다. Example. 1의 역원은 -1. 위 세 그림을 보면 P + (-P) = 𝒪 (직선이 y축에 평행인 수직선), P1 + P2 + P3 = 𝒪 (직선이 타원곡선의 세 점을 지나는 사선), 2P1 + P2 = 𝒪 (직선이 타원곡선의 접선, 즉 두 점을 지나는 사선; 이때 접점을 두 번 더함)으로 생각하면 된다. 따라서 P1 + P2 = -P3 그리고 2P1 = -P2 로 계산된다.

위에서 다뤘던 $y^2 = x^3 + 20x + 8~(mod~23)$의 타워 선형 Group의 order이다. 그중 (16, 13)의 역순을 찾아보자.

(1) Nagation 형태 : P + (-P) = 𝒪 (직선이 y축에 평행인 수직선)

(16,13)에서 y의 역수만 찾아주면 된다. 13의 역수는 -13이지만 우리는 모듈러 연산으로 도출되는 값임으로 아래와 같이 연산된다.

Nagation 역순으로 (16,-13)은 (16,10)이다. 기하학적으로도 같은 방식으로 역수를 찾는다. 제일 오른쪽 코드에서 보면 (16, 13) + (16, 10) = 𝒪 가 됨을 알 수 있다.

(2) Addition 형태 : P1 + P2 + P3 = 𝒪 (직선이 타원곡선의 세 점을 지나는 사선)

두 다른 점의 합(addition)의 경우 실수 평면 곡선과 같은 기하학적 구조로 산출할 수 있다. 중간 그림에서도 두 점 (11, 8)과 (16, 13)을 연결한 선과 만나는 점 (20, 17)의 역수인 (20, 6)을 합으로 도출함을 알 수 있다.

(3) Doubling 형태 : 2P1 + P2 = 𝒪 (직선이 타원곡선의 접선, 즉 두 점을 지나는 사선; 이때 접점을 두 번 더함)

한 점의 두 배(doubling)를 생각해보면 실수 평면에서는 이해가 쉽다. 그런데 중간 그림과 같이 이산적인 점의 집합일 경우에는 어떻게 접선을 구할까? 이 때는 아래 수식의 도움을 받는다.

중간 그림과 같이 (16, 13)을 지나는 기울기 2의 직선은 (18, 17)을 만나고 이의 역수인 (18, 6)이 바로 2x(16, 13)이 된다.

타원곡선 그룹에서는 그룹 원소들 간의 더하기와 함께 그룹 원소와 숫자(scalar)의 곱을 지원한다.

그런데 사실은 이게 그룹 원소를 숫자만큼 반복적으로 더하는 것이라고 생각하면 된다. 즉 3*(16,13) = (16,13) + (16,13) + (16,13) 이다 (위 세 그림의 오른쪽 숫자들을 보면 이해하기 쉽다).

secp256k1

이제 위 사진의 ECC의 secp256k1의 타원곡선에 대한 p(base field의 order)와 q(ECC group의 order)를 이해할 수 있게 됬다. 이더리움과 비트코인에서 사용하는 ECC secp256k1의 타원곡선은 base point(Generator:G) = (gx, gy)를 상수로 정해 두고 사용한다.

앞에서 말한 바와 같이 prime order를 가진 cyclic group인 타원곡선 그룹에서는 모든 원소가 generator가 될 수 있다. 그런데 secp256k1에서는(모든 표준 타원곡선도 마찬가지로) 유독 한 포인트를 base point인 generator로 지정하고 있다. 대부분의 타원곡선 기반 전자서명 알고리즘에서는 랜덤하게 개인키(scalar)를 선택한 후 여기에 generator를 곱해서 포인트 형태의 공개키를 추출한다. 따라서 많은 사람이 공유하고 사용해야 하는 타원곡선 표준에서는 모두가 동일하게 사용할 기준점(base point)인 generator를 표준화해야 한다.

우리는 이제 ECC secp256k1를 통해 개인키(sk)과 공개키(pk)가 생성되는 원리를 이해할 수 있다. 개인키(sk)는 {1, …, q-1} 사이에서 랜덤하게 선택되고, 개인키에 타원곡선의 generator인 G를 곱하면 공개키가 된다.

Reference:

• Pairing-based Cryptography와 BLS signature의 이해 — Part 1 - https://medium.com/atomrigslab/pairing-based-cryptography%EC%99%80-bls-signature%EC%9D%98-%EC%9D%B4%ED%95%B4-part-1-f4ec67d69940
• 타원곡선암호(이상엽 | youtube) - https://www.youtube.com/watch?v=cVUp0Bnve4s&t=1819s
• 타원곡선암호 알고리즘( 최희준교수 | youtube) - https://www.youtube.com/watch?v=7jscDr000DI