Signature Algorithm

비트코인에서 사용하는 타원곡선은 무엇일까?

비트코인에서 사용하는 타원 곡선

• 지금까지는 타원곡선에 들어가는 유한체의 위수를 작은 소수를 사용했다.
• 하지만 실전에서는 매우 큰 소수를 사용하여 컴퓨터로 탐색이 불가능하게 만든다.
• 지금까지 배운 내용으로 공개키 암호를 위해 몇개의 파라미터를 정해야 하는지 알아보자.

공개키 암호를 위한 매개변수

• $y^2=x^3+ax+b$에서 $a$, $b$
• 유한체의 위수인 소수 $p$
• 생성점 $G$의 $x$, $y$ 좌표값
• G로 생성한 군의 위수 $n$
  • 무한대로 곱하면 무한 원점이나, 프로그래밍에서는 이를 처리할 수 없어 유한한 수로 치환해야함

비트코인에서 사용하는 타원 곡선

• $a=0$, $b=7$, 즉, $y^2=x^3+7$을 사용함
• $p=2^{256}-2^{32}-977$
• $G\_x=0x79be667ef9dcbbac55a06295ce870607029bfcdb2dce28d959f2815b16f81798$
• $G\_y=0x483ada7726a3c4655da4fbfcOe1108a8fd17b448a68554199c47d08ffb10d4b8$
• $n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141$

비트코인 타원 곡선의 특징

1. 방정식이 상대적으로 간단하다.
   • 다른 타원 곡선의 파라미터의 경우 굉장히 복잡한 경우가 많다.
   • 타원곡선으로 제안된 곡선 예시
2. 유한체의 위수인 $p$가 $2^{256}$에 매우 가까운 값이다.
   • 이렇게 되면, $2^{256}$보다 작은 대부분의 숫자가 유한체를 형성할 수 있게 된다.
     • 즉, 군에 속하는 곡선 위 점도 256비트 안으로 표현가능하다.
     • 군의 위수 역시 표현가능하다. 즉, 스칼라 곱셈에서 스칼라 값도 256비트 안으로 표현가능하다.
       • $p>n$이어야 하기 때문
       • 유한체의 원소는 군의 원소보다 많다.
   • 이것이 왜 중요할까?
   • 32 byte내로 저장할 수 있으면서, 표현가능한 숫자는 어마무시하게 크기 때문이다.
   • $2^{256}$은 우주의 원자 개수 정도에 해당되는 큰 숫자다. 선형탐색이 가능할까?

타원 곡선위의 점 확인하기

• 앞에서 나열한 비트코인에서 사용하는 생성점은 정말 위에 있을까?
• 간단하게 확인해보자.

gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
p = 2**256 - 2**32 - 977
print(gy**2 % p == (gx**3 + 7) % p) # True

scep256k1만을 위한 Wrapping 클래스 정의

• 이제 모든 파라미터가 정해졌기 때문에, 일일히 값을 넣어가면서 처리할 필요가 없다.
• 내가 사용할 타원 곡선에 대해 국한된 클래스를 정의하고 이를 사용하자.

# 상수 목록
A = 0
B = 7
P = 2**256 - 2**32 - 977
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
 
class S256Field(FieldElement): # 유한체 상속
 
    def __init__(self, num, prime=None):
        super().__init__(num=num, prime=P) # 초기화시 전역 변수로 빠져있는 P를 넣어버림
 
    def __repr__(self):
        return '{:x}'.format(self.num).zfill(64) # 출력시 빈자리를 0으로 채우도록 함
 
class S256Point(Point): # 타원 곡선 위 점 상속
 
    def __init__(self, x, y, a=None, b=None):
        a, b = S256Field(A), S256Field(B) # a, 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)  # 무한 원점으로 초기화하는 경우 (x == None)을 위해 분기
 
    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  # nG가 0이니, 유환순환군안에서 나머지로 나누어 처리해도 무방하다. 
        return super().__rmul__(coef)
 
G = S256Point(
    0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
    0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
print(N*G) # S256Point(infinity)

공개키 암호

• 이제 모든 도구를 학습했다.
• 핵심은 비대칭 방정식 $P=eG$이다.
• $P$는 계산하기 쉽지만, $e$를 계산하는 것은 어렵다.
• 여기서 $e$를 비밀키, $P$를 공개키라 한다.
• 앞에서 배운 스칼라가 비밀키에 대응(하나의 숫자: 256비트),
• 공개키는 연산 결과에 대응된다. (좌표값 (x, y): 각각 256비트)

서명 생성과 서명 검증

마술의 예

• 카드 마술을 한다고 생각해보겠다.
• 하나의 카드를 뽑고, 그게 다른 사람의 주머니 속에 들어있도록 하는 마술을 시연할 것이다.
• 이 마술은 그 마술사의 능력을 규정할 정도로 높은 중요성을 갖는 자리라 하자.
  • 하냐 못하냐에 따라 마술사의 자격을 박탈당할 수도 있는 중요한 자리
• 여기서 1:1로 마술을 시연하느냐, 1:n으로 시연하느냐에 차이가 있다고 해보겠다.
  • 1:1 - 가까이서 보기 때문에 신뢰성이 있다고 판단하는 가능성이 높음
  • 1:n - 멀리서 보기 때문에 그걸 어떻게 믿냐고 따질 가능성이 높음
• 이런 상황은 실제로 우리가 마술을 볼 때도 많이 발생한다.
• 예를 들어 하트 7이 그려진 카드를 청중 C에게 넘기는 마술을 시연했는데, 다른 청중들이 “저 사람이 그 카드를 들고 있었을 수도 있는데 어떻게 믿죠?”라고 하는 경우가 되겠다.
• 이렇게 다수의 사람들에게 Abusing이 없는 상황에서 기술을 시연했다는 것을 증명하는 것은 쉽지 않다.
• 그래서 마술사들이 사용하는 방식은 카드에 표식을 새기는 것이다.
• 즉, 특정 카드를 뽑고, 그 카드에 자신만이 그릴 수 있는 글씨를 새기고, 이를 청중들에게 보여준다.
• 그 작업을 통해 모두의 합의를 얻는 것이다.
• 그 뒤에 마술을 시연하게 되면, 사람들은 할 말이 없어진다.

디지털 서명/검증

• 이러한 방식은 서명과 검증에서 사용하는 것과 동일한 방법이다.
• 달라지는 것이 있다면, 증명방법이 마술의 결과가 아니고 비밀키를 소유했느냐의 여부로 바뀐다는 것이다.
• 즉, “이런 마술을 성공했어!”로 끝나는 것이 아니고, “내가 비밀키를 갖고있어! 그러니까 이건 나야”를 말하고 싶은 것이다.
• 이러한 과정을 하기 위해서는 다음의 과정을 거쳐야 한다.
  • 카드에 표식을 새기기: 서명 생성
  • 그 카드가 청중 C의 호주머니에서 나오게 하기: 서명 검증
• 어렴풋이 알겠지만, 비밀키의 소유여부를 통해 A가 B에게 비트코인을 보낸다는 것을 검증한다.

서명 알고리즘

• 비트코인에서 사용하는 알고리즘은 ECDSA(Elliptic Curve Digital Signature Algorithm)이라 한다.

$$eG=P$$

• 첫번째 필요한 식은 위와 같다.
  • $e$: private key
  • $P$: public key
  • $G$: 유한환원군에서의 생성점

$$kG=R$$

• 두번째 필요한 식은 위와 같다.
• $R=(r,y)$ 은 이렇게 표현되며, x좌표만이 중요하기 때문에 $r$을 써서 나타내겠다.
  • $r$은 random 이란 의미이다.
  • x좌표만 중요한 이유는 x좌표를 타원곡선에 넣어 y값을 알 수 있기 때문이다.
• $R$을 선정하는 것이 곧 “마술의 증명”을 위해 표식을 하는 행위와 유사하다고 생각하면 되겠다.

$$uG+vP=kG(=R)$$

• 위의 두 식을 조합해서 위와 같은 식을 만들 수 있을 것이다.
• 스칼라 곱셈을 한 두개의 식을 엮어 하나의 방정식을 만들었을 뿐, 여전히 이산 로그 문제 종류중 하나이다.
• $G,P,R$이 주어진 상황($R$은 목표물로 우리가 정함)에서 $u,v$를 구하는 문제이기 때문이다.
• 다만, 변수가 2개로 확장되어 유일하게 $(u,v)$가 정해지지는 않는다.
• 위 상태에서 서명알고리즘이 동작한다.

방법

1. 서명자는 k를 임의의 값으로 설정한다.
   • 이 때, $u,v\ne 0$
   • $G,P$는 아는 값
2. $vP=(k-u)G$
3. $P=((k-u)/v)G$, ($v\ne 0$)
4. 여기서 Private Key($e$)를 알고 있다면 $P$를 $eG$로 대체할 수 있다.
5. $eG=((k-u)/v)G$
6. 즉, $e=(k-u)/v$

의문

• 그런데 이게 무슨 의미일까?
• 변수의 의미를 고려해서 말을 풀어보면..
• “$e$(비밀키)는 $(u,v)$의 조합으로 만들어진다”라고 생각할 수 있다.
• “$(u,v)$쌍을 제공하는 사람은 비밀키 $e$를 알고 있다.”
  • 이산 로그 문제의 해를 찾는 것은 어렵기 때문
• 근데 사실 이를 만족하는 $u,v$는 무수히 많다.
• 내가 비밀키 소유자임과 동시에 이 메시지를 내가 발신했다라는 정보를 넣을 필요가 있다.
• 이를 위해 메세지의 해시값($z$)을 계산에 추가하여 의미를 포함한다.

해시 추가하기

$$u=z/s,v=r/s$$

• $u,v$를 위와 같이 정의하고, s를 통해 값을 조절하도록 하자.

$$\begin{gathered} uG+vP=R(=kG) \\ uG+veG=kG \\ u+ve=k \\ z/s+re/s=k \\ (z+re)/s=k \\ s=(z+re)/k \end{gathered}$$

• 원래는 $(u,v)$쌍을 알려줌으로써 비밀키 소유자임을 증명했다.
• 그런데 메시지의 내용을 넣은 값(해시($z$)와 나임을 증명하기 위한 값($r$)을 넣어 식을 변형했기 때문에
• 이제 증명하기 위해 필요한 변수 쌍이 변경된다. ($(s,r)$)
• 즉, $(s,r)$을 공개할 수 있다면,
  1. 비밀키를 가지고 있다.
  2. 메시지의 발신자이다.
• 위의 두 사실을 증명할 수 있게 된다.

왜 k를 공개하지 않는가?

• 그러면 의문이 들 수 있다.
• 보니까 $R$의 x좌표인 $r$을 공개하긴 하는데, 왜 굳이 그래야 하지?
• 왜 굳이 이 복잡한 과정을 거쳐야 할까?
• $k$같은 값을 공개하면 안될까?

$$\begin{gathered} uG+vP=R \\ uG+veG=kG \\ (k-u)G=veG \\ e=(k-u)/v \end{gathered}$$

• 위의 식을 만족하는 $(u,v)$은 무수히 많다.
• $k$값이 모르는 값으로 남아있지 않으면, 탐색을 통해 비밀키를 알 수 있게 된다.
• 즉, 위의 이산 로그 문제의 특징을 통해 식을 조합하는 행위는,
  1. 보안
  2. 발신자 확인
• 두가지 목적을 위해 어쩔 수 없이 도입된 값들이라 이해하는 것이 좋겠다.

서명 알고리즘 쉽게 설명

• 위의 설명이 오히려 복잡한 것 같아 다시 정리한다.
• 우리는 일반적으로 사용하는 서명 알고리즘에 대해 배우고 있다.
• 서명 알고리즘의 핵심은 비밀키의 소지 여부, 해당 내용의 작성자 확인을 비밀키를 보여주지 않고 가능케하는 것이다.
• 즉, 비밀키 소유여부를 수학적 기술을 통해 간접적으로 확인하는 것에 그 목적이 있다.
• $e$를 공개하지 않고, $u,v$를 맞추는 것으로 내가 비밀키를 가지고 있다는 것을 간접적으로 증명하는 것이다.
• 이 때, $k$라는 문자 역시 사용하게 되는데, 이 역시 $e$를 알리지 않고 증명하기 위한 변수라 생각하면 되겠다.
  • 즉, 보호 장치다.
• 그런데 여기서 문제는 뭐냐면, $u,v$를 맞추는 것으로 나임은 쉽게 증명이 가능하나, 내가 이 문서에 서명했다는 사실은 알 수 없다.
• 문서에 대한 내용이 어디에도 없기 때문이다.
• 그래서 $u,v$ 변수를 조작하여, 문서에 대한 요약본(서명해시)를 만들어 변수에 추가하는 트릭을 사용한다.
  • $u=z/s,v=r/s$ 여기서 $z$는 서명해시, $r$은 $R$의 x값이다.
• 이렇게 되는 순간, 이제는 $u,v$를 공개해서 비밀키가 있다고 증명하는 문제에서
• $s,r$를 보여주고 내가 비밀키도 있고, 이 문서에도 서명했음을 증명하는 문제로 바뀌었다.

$$\begin{gathered} uG+vP=R=kG \\ uG+veG=kG \\ u+ve=k \\ z/s+re/s=k \\ (z+re)/s=k \\ s=(z+re)/k \end{gathered}$$

• 이렇게 굳이 식을 왜 정리하나 싶을 것이다.
• $s,r$을 알더라도 의미가 있는 식인가? 싶을 것이다.
• 그런데, 위 식은 각 변수간의 관계에 대해 서술한 것이다.
• 이는 검증에서 $s,r$만 알더라도 수식을 풀 수 있음을 확인하기 위해 필요한 관계이다.

검증 알고리즘

• 자 이제 검증자는 $s,r$을 받았다.
• 검증자는 이 값을 통해 $uG+vP=kG=R$의 수식을 만족할 수 있는지 확인하면 된다.
• 여기서 $R$의 x값은 $r$로 주어졌으니, $s$를 대입하여 계산 후, $r$로 떨어지는지 확인하자.

$$\begin{gathered} uG+vP=(z/s)G+(r/s)P \\ =(z/s)G+(re/s)G \\ =((z+re)/s)G \\ =((z+re)/((z+re)/k))G \\ =kG \\ =R \end{gathered}$$

• 수식이 동작하는 것을 확인하여 검증이 완료되었다.

검증 알고리즘 정리

1. 서명으로 $(s,r)$, 메시지의 해시값 $z$, 공개키 $P$가 주어진다.
2. 검증자는 $u=z/s,v=r/s$를 계산한다.
3. $uG+vP=R$을 계산한다.
4. 결과값의 $R$의 x좌표인 $r$이 같다면 유효한 서명이다.

Reference

• Programming Bitcoin by Jimmy Song(O’Reilly). Copyright 2019 Jimmy Song, 978-1-492-03149-9
• programmingbitcoin
• 타원 곡선 암호
• 일방향 함수
• 이산 로그
• 이산 로그 문제
• 타원곡선으로 제안된 곡선 예시