서명, 검증 알고리즘을 알았으니 필요한 클래스들을 작성해보자.

Signature

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)

• 서명의 경우 서명하는 사람이 넣어서 주는 값이다.

Verify

• 타원 곡선 위에 있는 점을 나타내는 S256Point에 검증 메서드를 추가한다.

class S256Point(Point): # 타원 곡선 위 점 상속
    ...

    def verify(self, z, sig):
        s_inv = pow(sig.s, N - 2, N)  # <1>
        u = z * s_inv % N  # <2>
        v = sig.r * s_inv % N  # <3>
        total = u * G + v * self  # <4>
        return total.x.num == sig.r  # <5>

1. 페르마의 소공식을 통해 inverse를 0을 포함한 정수 지수로 변경한다.
2. u, v를 구한다.
3. u, v 둘다 위수인 N으로 변경해주어야 한다.
4. 좌변을 계산한다. ($uG + vP$)
5. 결과값과 $r$을 비교한다.

PrivateKey

• 서명을 생성한 PrivateKey 클래스를 만들자.
• 비밀키를 보관하는 클래스를 하나 만들어주고, 거기서 서명을 생성하여 검증자에게 전달하자.
• 검증자는 Public Key에 해당하는 타원위의 점(S256Point)$P$에 있는 메서드인 verify로 그 서명을 넘겨주면 끝이다.

class PrivateKey:

    def __init__(self, secret):
        self.secret = secret
        self.point = secret * G  # 공개키를 계산 후 보관한다.

    def hex(self):
        return '{:x}'.format(self.secret).zfill(64)
    # end::source13[]

    # tag::source14[]
    def sign(self, z):
        k = self.deterministic_k(z)  # 그냥 무작위로 결정하면 안된다. k가 들키면 e도 털린다. 서명마다 k도 달라야한다. 아니면 털린다.
        r = (k * G).x.num
        k_inv = pow(k, N - 2, N)
        s = (z + r * self.secret) * k_inv % N
        if s > N / 2: # 가변성 문제로 N/x보다 작은 s값을 사용한다.
            s = N - s
        return Signature(r, s)

    def deterministic_k(self, z): # 서명 마다 다른 k값을 명시적으로 사용하기 위한 코드
        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()
    # end::source14[]

가변성 문제

• 위에서 s가 N/2보다 작은 s를 서명에 포함했다.
• 왜 굳이 이러는 걸까?
• 우리가 서명을 만든다는 것은 어떠한 이산 로그 문제를 해결하는 변수를 준다는 것과 같다.
• 그리고 그 이산 로그 문제는 근본적으로 타원 곡선 위에 있게 된다.
• 타원 곡선의 특징으로는 x축 대칭이 있는데, 그렇기 때문에 같은 x값에 대해 곡선위에 있는 점은 2개가 되게 된다.
• 이는 서명으로 $r, s$값을 생성할 때도 같은 특성을 띈다.
• 즉, $r$에 대해 이산 로그 문제를 만족하는 해는 $s$, $N-s$로 두개라는 것이다. 두개의 유효한 서명이 있는 것.
• 이렇게 2개가 되어 발생하는 문제 (이건 아직 모르겠다.)를 막기 위해 작은 s를 사용한다.

Reference

• Programming Bitcoin by Jimmy Song(O'Reilly). Copyright 2019 Jimmy Song, 978-1-492-03149-9
• programmingbitcoin