4️⃣

개인키과 공개키

비트코인의 타원곡선

•
비트코인에서도 타원곡선을 사용하여 개인키와 공개키를 생성한다.
◦
타원곡선 함수는 다음과 같다.
y2=x3+7y^2=x^3+7
◦
소수는 다음과 같다.
p=2256−232−977p=2^{256}-2^{32}-977
◦
초기 시작점(생성점)은 다음과 같다.
Gx=0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798Gy=0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8G_x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 \\G_y= 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
◦
위수는 다음과 같다.
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
•
이를 secp256k1이라 한다.

secp256k1의 특징

•
소수 p는 256비트보다 약간 작은 수이다.
◦
256비트는 아주 큰 수이다. 다음을 참고하자.
•
다음을 여러 상수를 10진수로 비교해보자.
◦
115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 (256비트)
◦
115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,908,834,671,663 (소수 p)
◦
115,792,089,237,316,195,423,570,985,008,687,907,852,837,564,279,074,904,382,605,163,141,518,161,494,337 (위수 n)
◦
세 숫자 모두 모두 엄청난 규모에 차이가 별로 나지 않는 수이다.
•
위수 n이 우리가 추출 가능한 총 공개키의 수이고, 이는 곧 총 개인키의 수이다.
•
G가 타원 곡선 위에 있는가?
gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 p = 2**256 - 2**32 - 977 print(gy**2 % p == (gx**3 + 7) % p) #-----결과----- True
Python
복사
•
n이 위수가 맞는가?
from ecc import FieldElement, Point gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 p = 2**256 - 2**32 - 977 n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 x = FieldElement(gx, p) y = FieldElement(gy, p) seven = FieldElement(7, p) zero = FieldElement(0, p) G = Point(x, y, zero, seven) print((n+1)*G) print(G) #-----결과----- Point(55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424)_0_7 FieldElement(115792089237316195423570985008687907853269984665640564039457584007908834671663) Point(55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424)_0_7 FieldElement(115792089237316195423570985008687907853269984665640564039457584007908834671663)
Python
복사

개인키와 공개키

•
타원곡선의 스칼라 곱에 따라 개인키와 공개키를 정의할 수 있다.
•
아래의 식은 G에서 e를 스칼라 곱을 진행한 결과를 P로 표현한 것이다.
P=eGP=eG
◦
G : secp256k1의 생성점
◦
e : 스칼라 곱을 한 횟수
◦
P : 스칼라 곱의 결과 타원곡선 위의 한 좌표값(x, y)
•
위 식에서 e를 개인키(private key), P를 공개키(public key)라 한다.
•
이산로그 문제 : e와 G를 알면 P를 계산하는 것은 쉬우나, P와 G를 안다고 해서 e를 알아내는 것은 어렵다.

나만의 공개키를 만들어 보자.

•
나의 개인키를 1로 설정하면 공개키는 다음과 같다.
◦
x좌표: 55066263022277343669578718895168534326250603453777594175500187360389116729240,
◦
y좌표: 32670510020758816978083085130507043184471273380659243275938904335757337482424
from ecc import FieldElement, Point gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 p = 2**256 - 2**32 - 977 n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 x = FieldElement(gx, p) y = FieldElement(gy, p) seven = FieldElement(7, p) zero = FieldElement(0, p) G = Point(x, y, zero, seven) privateKey = 0x1 print(privateKey*G) #-----결과----- Point(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)_0_7 FieldElement(115792089237316195423570985008687907853269984665640564039457584007908834671663)
Plain Text
복사

디지털 서명

•
타원곡선 알고리즘은 비트코인 이외의 여러 분야에서 디지털 서명에 활용된다.
•
디지털 서명은 자신이 공개키의 합당한 주인이라는 것을 타인에게 검증하는 과정이다.
•
비트코인에서는 자신의 공개키에게 할당된 돈을 서명을 통해 다른 사람에게 송신한다.
•
디지털 서명 절차
◦
서명할 메시지를 해시하여 (z)를 구한다.
◦
임의값(k) 하나를 고른다.
◦
스칼라 곱 kG를 한 결과 타원곡선 위의 점 R(r: R의 x값)을 구한다.
◦
나만 알고 있는 개인키(e)와 임의의 수(k)를 이용하여 s를 만든다. (s는 나만 만들 수 있다)
s=z+reks=\frac{z+re}{k}
◦
z, s, r을 검증자에게 보낸다.
•
디지털 서명 검증 절차
◦
u, v 값을 만든다.
u=zs, v=rsu=\frac{z}{s}, ~v=\frac{r}{s}
◦
이렇게 만든 u, v는 다음을 만족한다는 것을 확인한다.
uG+vP=RuG+vP=R
•
증명
◦
내가 만들어낸 값
kG=R=((z+re)/s)GkG=R=((z+re)/s)G
◦
사람들이 검증하는 값
R=uG+vPR=uG+vP
◦
u, v에 유도공식을 대입하고, 공개키와 개인키의 유도공식을 대입하면 다음과 같다.
uG+vP=(z/s)G+(r/s)P=(z/s)G+(re/s)G=((z+re)/s)GuG+vP=(z/s)G+(r/s)P=(z/s)G+(re/s)G=((z+re)/s)G
◦
s에 유도공식을 대입하면 다음과 같다.
uG+vP=((z+re)/((z+re)/k))G=kG=RuG+vP=((z+re)/((z+re)/k))G=kG=R
•
서명의 메커니즘을 이해해보자.
◦
감춰지는 수 : e(개인키), k(임의의 수)
◦
공개되는 수 : r, s, z(메시지), P(공개키)
◦
다음 식을 가정하였다.
uG+vP=R=kGuG+vP=R=kG
▪
이 식은 이산로그 문제이므로 이를 만족하는 G, P, R을 안다고 해서 u, v는 찾을 수 없다.
•
식이 스칼라 곱을 포함하기 때문에 역시 이산로그 문제이기 때문이다.
▪
하지만, k를 안다면 찾을 수 있다. 더 이상 이산로그 문제가 아니기 때문이다.
uG+vP=kGuG+veG=kGu+ve=kuG+vP=kG\\ uG+veG=kG\\ u+ve=k
▪
따라서, u, v를 만들어 냈다는 것은 e를 알고 있다는 뜻이다. 하지만 u, v를 서명값으로 쓰면 문제가 있다.
•
내가 u, v를 만들어 냈다는 것만 증명하면, 내가 어떤 값(z)을 증명하고자 했는지 알 수 없다.
•
그리고 내가 임의의 u, v를 공개하면, u, v를 아는 다른 사람도 나인척 할 수 있다.
•
따라서, 어떤 값(z)에 따라 매번 달라지는 서명값을 제시할 수 있어야 한다.
◦
위의 수식이 1개인데, 미지수가 2개이므로 저 식을 만족하는 u, v는 무수히 많다.
◦
저 중 하나를 특정하기 위해 메시지의 해시값(z)를 포함한다.
▪
수 많은 u, v의 조합 중 z를 넣은 유일한 u, v를 선택할 수 있는 것도 나만 할 수 있어야 한다.
▪
따라서 다음을 만족하는 s를 가정한다.
u=zs, v=rsu=\frac{z}{s}, ~v=\frac{r}{s}
▪
여러 u, v 조합 중에 z를 넣은 s는 유일하다. (s를 제외한 모든 수가 상수이기 때문이다.)
u+ve=kz/s+re/s=ku+ve=k\\z/s+re/s=k
▪
따라서 아래의 식을 만족하는 s를 찾아낸다.
▪
이렇게 계산이 가능하다.
s=z+reks=\frac{z+re}{k}
공식 유도
z/s+re/s=k(z+re)/s=ks=(z+re)/kz/s+re/s=k\\(z+re)/s=k\\s=(z+re)/k
◦
z를 넣은 유일한 u, v 조합을 찾으려면, e(개인키)를 알아야 한다.

구현: secp256k1

A = 0 B = 7 P = 2**256 - 2**32 - 977 N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 G = S256Point( 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8) #FieldElement를 상속받아 secp256k1을 위한 유한체 원소 클래스를 정의한다. class S256Field(FieldElement): #더이상 prime를 생성자 인수로 받지 않는다. def __init__(self, num, prime=None): super().__init__(num=num, prime=P) #통일성을 위해 표현법의 변화를 준다. #숫자의 빈자리가 생기면 0으로 채우도록 하였다. def __repr__(self): return '{:x}'.format(self.num).zfill(64) #Point를 상속받은 secp256k1의 공개키 포인트를 정의한다. class S256Point(Point): def __init__(self, x, y, a=None, b=None): #모든 구성원소는 유한체의 원소가 되어야 한다. a, b = S256Field(A), S256Field(B) if type(x) == int: super().__init__(x=S256Field(x), y=S256Field(y), a=a, b=b) else: super().__init__(x=x, y=y, a=a, b=b) # <1> def __repr__(self): if self.x is None: return 'S256Point(infinity)' else: return 'S256Point({}, {})'.format(self.x, self.y) def __rmul__(self, coefficient): coef = coefficient % N # <1> return super().__rmul__(coef) #서명 검증하기 def verify(self, z, sig): #self:공개키, z:메시지의 해시, sig:r,s 서명값 #1/s를 먼저 구한다. 페르마 소정리를 활용한다. s_inv = pow(sig.s, N - 2, N) #u, v를 구한다. 위수 N을 나머지 연산하여 계산 낭비를 줄인다. u = z * s_inv % N v = sig.r * s_inv % N total = u * G + v * self return total.x.num == sig.r #서명을 저장하는 클래스이다. r, s를 전달하는데 사용한다. class Signature: def __init__(self, r, s): self.r = r self.s = s def __repr__(self): return 'Signature({:x},{:x})'.format(self.r, self.s) #개인키를 저장하는 클래스이다. class PrivateKey: def __init__(self, secret): #개인키, 공개키 self.secret = secret self.point = secret * G def hex(self): return '{:x}'.format(self.secret).zfill(64) #서명하기 def sign(self, z): #임의성이 높은 k를 선정한다. k = self.deterministic_k(z) #r을 선정한다. r = (k * G).x.num #1/k k_inv = pow(k, N - 2, N) #s 생성 s = (z + r * self.secret) * k_inv % N #(r,s)와 (r,N-s) 둘 다 유효한 서명이다. # 이 중 작은수를 보낸다. if s > N / 2: s = N - s return Signature(r, s) #합리적으로 k를 선정하는 방법이다. 임의성을 위하 z를 사용하여 추출한다. def deterministic_k(self, z): k = b'\x00' * 32 v = b'\x01' * 32 if z > N: z -= N z_bytes = z.to_bytes(32, 'big') secret_bytes = self.secret.to_bytes(32, 'big') s256 = hashlib.sha256 k = hmac.new(k, v + b'\x00' + secret_bytes + z_bytes, s256).digest() v = hmac.new(k, v, s256).digest() k = hmac.new(k, v + b'\x01' + secret_bytes + z_bytes, s256).digest() v = hmac.new(k, v, s256).digest() while True: v = hmac.new(k, v, s256).digest() candidate = int.from_bytes(v, 'big') if candidate >= 1 and candidate < N: return candidate # <2> k = hmac.new(k, v + b'\x00', s256).digest() v = hmac.new(k, v, s256).digest()
Python
복사

참고자료