[BitCoin] 타원 곡선 암호화

안녕하세요. 비트코인에 대해 전반적으로 공부를 하였으나 누군가에게 막상 설명하려고 하니깐 아직도 많이 부족하다는 걸 느껴서 다시 한번 더 공부하면서 좀 더 자세히 공부하고자 합니다.

 

오늘은 타원 곡선 암호화에 대해서 한번 알아볼려고 하는데요.

수학적인 개념으로 너무 깊게 파고 들면 제가 너무나도 힘들기 때문에 "이러한 개념이다"라고 말할 수 있는 정도로만 알아보고자 합니다.

 

우선 타원 곡선 암호화는 영어로 Elliptic Curve Cryptography 이라고 하며 줄여서는 ECC라고 합니다.

ECC가 나오기전 에는 RSA라는 암호화방식을 사용하였는데, RSA는 인수분해를 통한 암호화 방식이라고 생각하시면 쉬울 것 같습니다. 큰 숫자일수록 인수분해가 어렵다는 개념인데.... 보안을 더 강하게 하기 위해서는 점점 숫자가 커져가는 문제가 발생하면서 ECC가 대안으로 떠오르게 됬다고 합니다. (어디까지나 저희 주관적인 내용입니다.)

 

ECC는 비트코인에서 디지털 서명 암호기술로 사용되고 있는데 ECC의 경우 사용하는 용도에 따라 알고리즘 이름이 조금씩 다릅니다.

1. 디지털서명 용도 : ECDSA

2. 키 교환 용도 : ECDH

3. 난수 생성 용도 : Dual-EC_DRBG)

4. Encryption & Decryption 용도 : EC-KEM, EC ELGamal 등

 

위와 같이 용도에 따라 알고리즘이 이름이 다른데 저희는 블록체인 코어 개발자라면 많이 보게 되는 ECDSA에 대해서

알아보도록 하겠습니다.

 

우선 타원곡선은 특정 수학 방정식을 만족하는 점들의 집합체입니다.

식과 그래프는 다음과 같습니다.

그러나 소수(Prime)을 사용하는 유한체 상의 타원 곡선 경우 우리가 책에서 많이 보던 수식으로 변하게 됩니다.

y^2 = x^3 + ax + b over Fp  또는

y^2(mod p) = x^3 + ax + b(mod p)

 

또한 a와 b에 따라 그래프의 모양이 달라집니다.

위에 내용을 통해 대충 음 타원 곡선이 이런거구나, 이렇게 생겼구나 라는 정도는 이해하였을 것입니다.

그렇다면 이 타원 곡선을 어떻게 암호화에 사용하게 되는 것일까요? 

 

우선 ECC에는 Domain Parameter라는게 존재하는데요. 

p : Modulo Prime Number

a : 타원곡선 방정식에서 사용되는 계수

b : 타원곡선 방정식에서 사용되는 계수

G : Base point 또는 Generator Point , G 는 E(Fp)에 속해 있는 point 입니다.

n : the order of point G (G를 n번 더하면, 무한원점이 되는 값 :  nG = ∞)

H : cofactor 

가 존재합니다. 위 parameter는 각 표준 단체에서 Field size에 맞는 타원 곡선 parameter를 발표 하였습니다. 

왜 이걸 이야기 하냐면 우리가 많이 쓰는 secp256k1 역시 이러한 parameter가 정해져 있기 때문입니다.

 

secp256k1의 경우 a는 0, b는 7로 정의되어 있습니다.

즉 방정식은 Y^2 = X^3 + 7이 된다는 거죠. 이 식에 대한 다음과 같은 그래프가 나오게 됩니다.

또한 유한체 F일 경우 p = 59, 257(소수)인 경우 유한체(무한하지 않음)이기 때문에 각 점으로 나타나지게 되는데요.

이렇게 나온 점들 중 두점을 아래와 같은 더하는 연산을 정의하면, 교환 법칙과 결합법칙을 만족시키며, 항등원과 역원을 갖는 Group이 된다고 합니다.

 

두 점 P = (x1 , y1)와 Q = (x2 , y2) 가 있다고 할 때, 이들의 합 P+Q는 아래와 같이 정의합니다.

(1) 타원곡선상의 두 점 P와 Q를 잇는 직선 L이, 타원곡선과 다른 한 점 R = (x3 , y3)에서 만난다면, P+Q = -R = (x3, -y3) 이 됩니다(R 과 “P+Q”는 X축에 대하여 대칭인 점이 됩니다). 즉 타원곡선에서 두 점의 합은 기하학적으로 정의하고 있습니다. 즉 두 점을 잇는 직선과 곡선이 만나는 점의, x축 대칭점 입니다.

(2) -P 는 P의 x축 대칭점을 의미하며, P= (x , y) 라면 -P =(x , -y) 입니다. 그리고 P + (-P) = 무한원점(∞) 이 됩니다.

(3) 만약 L이 다른 한 점 R에서 만나지 않을 경우에는, L은 P 또는 Q에서 접하는 경우이며, 이 때 R은 L이 접하는 점이 됩니다.

(4) P = Q 인 경우는 L은, P 에서 그은 접선이 됩니다.

(5) 접선 L인 경우, L 이 타원곡선과 만나지 않을 경우, R 은 P 값을 가지며, 이 때 P 를 변곡점이라고 합니다.

(6) 무한원점 ∞에 대해서는 "∞을 지나는 직선은 Y축과 평행한 직선”으로 규정 합니다. 즉 L이 Y축과 평행하고 다른 점과 만나지 않는다면, R은 ∞로 규정 합니다.

(7) ∞이 항등원이 되며, “x축에 대한 대칭점”이 역원이 됩니다.

두 점 P + Q

P + P (접점)

변곡점과 R

그런데 왜 위와 같은 두점의 합 방식을 알아야 할까요? 바로 우리가 사용하는 공개키를 만드는 핵심 요소이기 때문입니다.

 

Private-key(개인키) d : P보다 적은 소수로 난수 생성기로 생성을 합니다.

Public-key(공개키) Q : "Q(x,y) = d x G(x0,y0)", 즉 타원 곡선의 "더하기 연산"으로 만들어집니다.

(G를 d번 만큼 더합니다.)

 

G는 이미 알려져 있고, 공개키 Q는 생성후 공개되어지지만 이 둘은 안다고해서 d를 유추해 내기는 매우 어렵다고 합니다. 이걸 ECDLP(Elliptic Curve Discrete Logarithm Problem)이라 부르며, 이러한 속성으로 인해 공개키 암호기술로 사용되어진다고 합니다.

 

그리고 현재 비트코인에서 사용되는 secp256k1의 Domain Parameter는 다음과 같습니다.

p :  FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFC2F

a :  00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

b :  00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007

G :  02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

  또는

G : 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

N :  FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

h : 01

 

G값은 Compressed Form( Type : 02 )과 Uncompressed Form( Type : 04 ) 2가지로 표현 할 수 있다고 합니다.

 

간단하게 개발자 입장에서 사용하는 secp256k1과 ECDSA에 대해서 알아보았는데... 

 

마지막으로 정리를 하자면

 

타원곡선 암호기술 중 디지털 서명을 하는데 사용되는 기술이 EDCSA이며 EDCSA 중 secp256k1 도메인 파라미터가 결정되어진 규격이다.

 

그리고 이러한 규격 속에서 개인키(d)는 특정 G라는 점을 d번 더하게 하여 공개키를 만드는데 사용하게 되어진다.

정도로 정리하면 될 것 같습니다. 

 

긴글 읽으시느라 고생 많으셨고 틀린 내용이 있다고 댓글로 달아주시면 감사하겠습니다.