ECC 와 PBC 가 뭘까

ECC는 1980년대 소개된 이후 20년 가까이 안정성 검토와 합의를 통해 표준으로 채택되었다.

ECC의 가장 중요한 장점은 더 작은 수 체계로 높은 안전성과 효율성을 보인다는것

예로 256bits ECC 개인키는 4096 bits RSA 개인키 보다 공개키에서 개인키를 유추하기 어렵다.

또한 숫자가 작은 만큼 서명,암호화 등 기본연산이 RSA 보다 빠르다.

이 글에서는

ECC사전 지식 - ECC암호 - PBC - BLS 순으로 진행된다.

어렵지 않다. 해 볼만 하다. 포기하지 않겠다 라는 마인드 컨트롤을 해야한다. (김현남 씨)

---

Group

덧셈에 대해 다음과 같은 조건을 만족해야한다.

1. Closure (닫힌 성질)→ 1+3 =4 에서 1,3,4이 같은 군에있어야한다.
2. → 덧셈을한 결과가 군에 속해야한다
3. Associativity(결합 법칙)
4. → a+b+c 에서 a+b 나 b+c를 먼저 계산해도 결과는 같아야한다
5. Identity element(항등원)→ 1+0=1 일때의 0 을 항등원 이라한다.
6. → 연산의 결과가 자기 자신이 나오게하는 원소가 있어야한다
7. Inverse element(역원)
8. →항등원이 나오게하는 원소 이다 1 + ? =0 일때 1의 역원은 -1 이다.

이런 요소가 있는걸 군 이라한다.

여기에 Commutativity (교환법칙) 이 추가되면 이를 Abelian group (아벨 군) 이라 한다.

Gruop example

정수의 집합을 수학적으로 더블Z 로 표기하며

역원을 가지게된다 1 의 역원은 -1 인데 1과 -1 모두 정수집합에 포함된다.

따라서 Gruop 조건에 만족하게 된다.

자연수의 집합은 수학적으로 더블N 으로 표기하며

이경우 1의 항등원은 0 일것이고(자기자신을 만들어야하니)

그런데 항등원을 만들기 위한 값인 -1 은 자연수의 집합에 포함되지 않는다.

따라서 Gruop 조건에 불만족 하게 된다.

 

Gruop 와 Elliptic Curves(타원 곡선)

Gruop 를 어떻게 타원곡선에 적용하는가

적용할때 또한 Group이 4가지 조건을 만족한다.

원소,항등원,역원,덧셈

 

 

원소

ECC 의 원소들은 Curves 의 점 들이다. → 닫힌 성질

 

위의 이미지에서 곡선의 점들의 집합이 원소들이된다.

 

항등원 원소

항등원 원소(혹은 무한 영점) 를 0 으로 표기한다.

 

 

역원

역원은 X축의 대칭인 점을 말한다.

p + -p = 0(무한 영점) 이 된다.

 

덧셈

덧셈 연산은 한줄에있는 P Q R 을 가지고 덧셈연산을 정의하게 된다.

P+Q+R = 0

한 직선 위에 있는 3점의 합이 0 이다.

덧셈 연산은 한줄에있는 P Q R 을 가지고 덧셈연산을 정의하게 된다.

어떤 순서로 계산해도(Associativity), 위치가 바뀌어도(Commutativity) 상관이 없다.

→ Abelian group (아벨 그룹)

 

💡P+Q+R =0 이라는 의미는 곧 P+Q = -R 이 된다. 즉 두 점을 연산하면 남은 점의 역이 나온다는 말. 이경우 예외의 경우가 여러가지 발생하여 개발시 따로 빼야한다. 어떤 경우이고 어떻게 처리하는지는 탄젠트 수식이 들어가서 자세히는 알아보지 않는다. (예로 P와 Q 가 같은 포인트인경우가 있다.)

 

 

P 와 Q 로 R 도출

 

먼저 P와 Q 를 지나는 직선을 먼저 찾고

그 직선과 타원곡선의 교점을 찾는다 이 교점이 R 이다.

이 R의 역원을 구하면 덧셈의 결과가 된다.

 

Field

Fp 로 표현하며 p는 소수를 의미한다.

다음과 같은 조건을 만족해야한다.

덧셈과 곰셈에 대한 닫힌 성질

교환법칙 , 결합법칙 , 항등원,역원 , 분배법칙

 

여기서

중요한점은 field의 조건을 만족하면 동시에 Group의 조건도 만족하기에 모든Field는 Group(아벨)이기도하다.

 

이 Group 와 Field는 무한한 개수를 가지는 집합이지만

암호학에서는 유한(Finite) 개수를 가지는 Finite Field 와 Finite Group를 사용한다.

무한한 수를 사용하면 암호가 더 안전할수있지만 아무리 안전해도 서명,암호화에 너무 많은 시간이 걸리면 안되기에

Finite Field ,Ginite Group와 함께 기초연산으로 modular연산을 사용한다.

 

💡 modular 연산을 통해 Finite Field ,Ginite Group 를 만들어 낼수있다.

💡Z5 = {0,1,2,3,4} 를 보면 modulus 5 를 적용한 Finite Field ,Finite Group 로써 즉 범위를 제한할수있다.

💡 위의 ZN(Z5) 에서 N이 prime(소수)라면 N 자체는 언제나 finite field(물론 Finite Group 가능)가된다.

 

Finite Field 의 조건은 교환법칙 , 결합법칙 , 항등원,역원 , 분배법칙, 소수가 된다.

---

Cyclic Group(순환군) 과 Generator(생성원)

-- Z5 --
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
2+2+2+2+2+2+2 (mod 5) = 4

----
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

2→4→1→3→0→반복

Z5에 해당하는 원소 중 2 를 가지고 0,1,2,3,4 라는 Z5 의 모든 원소를 만들어 내는것을 볼수있는데

이렇게 자신이 속한 그룹을 모듈러더하기 연산을 통해 모두 표현하는 값을 Generator 라 하며

0 이후부터 다시 반복 되는 것 처럼 반복 하는 그룹을 cyclic group 라고 한다.

💡 ZN의 모든 원자는 자신을 N번 더할경우 반드시 0이 된다 (타원곡선에서 매우 중요한 특징으로 사용)

0+0+0+0+0 (mod 5) = 0
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

요약

1. field, group는 특정한 조건에 해당하는 집합을 의미
2. field 는 대표적으로 유리수 그룹 , gruop는 대표적으로 정수 그룹이다.
3. field의 조건을 만족하면 동시에 Group의 조건도 만족하기에 모든Field는 Group이기도하다.
4. Group 와 Field는 무한한 개수를 가지는 집합이지만 암호학에서는 유한(Finite) 개수를 가지는 Finite Field 와 Finite Group를 사용한다.
5. ECC 에서 다루는 대부분의 형태에서는 prime N 인 finite field 를 사용한다.
6. group를 모듈러 연산으로 모든원소를 만들어내는 원소를 Generator 이라한다.
7. Generator이 존재하는 group를 cyclic group라 한다.
8. ECC 에서 사용되는 group는 cyclic finite group이다.

 

---

ECC

타원곡선은 x축 상에서 y의 값이 정확히 일치하는 특징과

또한 두점 P,Q 를 연결하는 직선은 반드시 다른 한점R 이 연결된다.

주로 사용되는 타원곡선은

의 식으로 표현하며 이를 바이어슈트라스 방적식(Weierstrass equation) 이라 한다.

 

이 외에도 다른 식도 존재하지만 비트코인, 이더리움등 대부분의 블록체인들은 secp256k1 이라는 타원곡선을 사용하고 secp256k1 의 식은 a와 b에 각각 0,7 을 적용한

이다.

→ 파이썬에서 secp256k1 의 파라미터 출력 a = 0 , b = 7 확인

 

p 는 타원곡선 base field 의 order(차수, 원소의 개수)

q 는 타원곡선 group 의 order이다.

 

위의 공식을 사용하는 암호 타원곡선 암호에서는 모듈러를 하여 유한한 크기를 사용한다.

 

{0,1,2,...p-1}과 같이 0 이상 이고 p 보다 작은 정수의 집합을 ZN이라 표시하고

N이 prime 라면 finite field(prime 인 finite field = Fp) 라고한다.

위의 식을 만족하는 x,y 좌표들의 집합이 타원곡선 group이 되어

E(Fp)로 명시 된다.

 

Fp 에 속하는 원소로

식을 만족하는 모든 집합과 한 원소를 타원 곡선 그룹이라 하며

이때 x ,y 는 Fp에 속한 원소이기때문에 Fp는 타원곡선 그룹 E(Fp) 의 base field라고 한다.

→ 즉 타원곡선 그룹의 포인트를 가리키는 시작점이라 이해 할 수 있다.

💡같은 Fq 를 사용한다고 해도 타원곡선의 식에서의 a,b를 어떻게 설정하느냐에 따라 결과가 다르다→ 곡선의 모양이 달라진다

 

타원곡선 이산로그 문제

ECDSA 는 비트코인 , 이더리움등 블록체인 그리고 공인인증서 등에서 가장 많이 쓰이는 타원곡선 기반 디지털 서명 알고리즘이다.

 

개인키 sk 는 {1,...,q-1} 사이에서 랜덤하게 선택 하고

개인키에 타원곡선 generator 인 G를 곱하면 공개키가 된다.

 

pk = sk*G 에서 pk/G = sk 를 얻을수 없을까?

이게 현대 공개키 기반 알고리즘에서 가장 중요한 DLP(이산 로그 문제) 와 비슷한 타원곡선 이산로그 문제 이다.

 

이산로그 문제

→ 3^6 mod7 =1 의 식에서 3 이라는 값과 mod 7 이라는 값을 알아도 지수를 찾으려면 결국 하나씩 모두 시도할수밖에없는 문제(효율적인 알고리즘이 없다.)

→ G를 2 로 해도 풀기 어렵기에 디피헬만 키 생성에서 openssl은 g를 기본적으로 2 로 사용하고있다.

→ secp256k1은 엄청 큰 으로 사용중이다.

 

타원곡선 이산 로그 문제

→ aG = b 에서 G 와 b 값이 주어졌을때 a값을 구하는 효율적인 알고리즘이 없다.

타원곡선 이산 로그 문제의 설명

💡 동일점 덧셈을 스칼라 곱셉을 나타낸다 P+P+P = 3P

 

2g,3g,4g 를 구하는 모습을 알아보면

먼저 g point 상에서 탄젠트 위치상에 선을 구하면 어떤 한 점(point) 를 만나게 되는데

이곳의 역원값이 2g 가된다.

기존의 g와 위에서 구한 2g에 선을 구하면 한 점을 만나게 되는데

이곳의 역원값이 3g 가된다.

기존의 g와 위에서 구한 3g에 선을 구하면 한 점을 만나게 되는데

이곳의 역원값이 4g 가된다.

 

다시 이산로그 문제로 가서

결과인 aG는 결국 타원곡선상에 어떠한 점이 될텐데

이는 G를 도대체 몇번을 해서 해당 위치에 가게됬는지 알기가 어렵다

---

Gap Group

CDH (Computational Diffie-Hellman Problem)

Alice 는 개인키 a 공개키 aG

Bob 는 개인키 b 공개키 bG 일때

Caral 은 aG 와 bG 를 가지고 abG를 구할수 있을까 하는 문제를 말한다.

DDH (Decisional Diffie-Hellman Problem)

Caral 은 aG 와 bG 를 가지고 abG 를 구할 능력은 없지만

누군가가 준 값이 abG 와 같은지 결정할수 있는가 에 대한 문제를 말한다.

→ 문제를 풀 능력은 없지만 채점은 할수있는 능력(상태)

 

이 두개의 문제를 보았을때 CDH 를 풀수있다면 DDH 또한 당연하게 풀수있게된다.

하지만 그 반대는 안된다.

 

이렇게 두가지 문제에 대해 CDH 를 푸는것을 불가능 하고 DDH는 효율적으로 풀수있는 group 를 Gap Group 라 한다.

 

 

이러한 Gap Group 를 만들어 낸다면 이를 이용한 서명이 가능하게되는데

CDH 는 어렵고 DDH는 쉬운 타원곡선 그룹인 Gap Gruop 의 generator(base potint) 가지고

1. Alice 는 개인키 a 와 공개키 aG를 생성하고 공개키를 Bob에게 미리 전달한다.
2. Alice는 서명할 메시지를 hash하여 Gap Group 안의 포인트 H로 매핑한다.(x,y형태의 포인트)
3. generator는 generator, 2generator, 3generator.. 의 형태로 Gap Group 전체의 원소를 generator를 한다는것이 가능하기에 어떠한 h라는 값은 h*generator 를 하여 H가 된다.
   1. 하지만 Bob은 h를 알 수 없다.(타원곡선 이산로그 문제)
4. Alice 는 H , 개인키 a 와 해시포인트 hG(=H) 를 곱한 S(ahG) 와 메시지를 Bob에게 전달한다.→ Bob이 알고있는것은 aG(Alice공개키), H(메시지의 해싱 hG 이기도하다. ) , ahG(서명, S로 부름)
   1. Bob는 a(개인키), h(H를 만들수있는 값), ah 를 알수 없다.
5. Bob 는 Alice가 보낸 서명이 Alice의 개인키로 서명된것인지 검증한다.→ aG에서 a를 제거해낼수없다. (CDH 문제)
   1. aG, H(hG), ahG(S) 로 부터 ahG =S 인지를 검증(결정)하는 문제

 

검증 과 Pairing

공개키 aG와 서명 S는 동일한 타원곡선 그룹 Gap Group 안의 포인트이다.

이러한 방식을 symmetric pairing(대합 짝짓기) 라하며

실용화된 타원곡선 그룹 방식(BLS signature) 에서는 G1,G2라 하는 서로 다른 두개의 타원곡선 그룹(같은 order) 으로 공개키와 서명을 표현하는데 이것을 asymmetric pairing(비대칭 짝짓기) 라 한다.

 

💡Pairing 에 의존하는 암호학을 페어링기반 암호화 라고 한다.(Pairing-Based Cryptography = PBC)

 

G1을 공개키의 타원곡선, G2를 서명의 타원곡선이라 하고

각각의 base point 를 P,Q 라 할때

 

Alice의 개인키가 sk 일때 공개키는 sk*P(= G1 의 포인트) 가 되고

서명할 메시지의 해시 H(h*Q)는 G2안의 포인트가 된다.

Alice는 서명 S = sk*H 를 만들어서 msg, S 를 Bob에게 전달한다.

 

Bob가 가지는 정보는 Alice의 공개키 skP, 메시지 해시 hQ , 서명 S이다.

Bob는 sk,h를 모르는 상태에서 S= skhQ 를 검증한다.

 

이때 사용되는 함수가 pairing(짝짓기) 함수라 부르며

e: G1 X G2 → GT 의 형태로 G1과 G2에서 각각 하나의 포인트를 받아 GT에 속하는 값을 산출한기도 하며

이를 사용하여 검증도 하게된다.

 

이때 S가 정상적인 Alice의 서명이라면 e(P,S)는

e(P, skhQ) 일것이다.

→ e : (공개키, 해시) == e : (G1포인트, 서명)

→ P 의 위치가 서로 다른것을 볼수있는데 bilinearity(양면성) 이라는 특징이있어 값이 자유롭게이동해도 상관이없다.

bilinearity Pairing 특징의 사용

234 * 7 = 1638 으로 예를 보면

234 * x = 1638 일때 x를 공개하지않고 나는 x를 알고있어를 보이고싶을때

e(2^234,x) == e(2,2)^1638 로 하는것으로 내가 알고있지만 숨길수있다.