[비트코인 구조] DER 형식 서명(Signature) 생성

미리 알아야 할 내용들

---

'비트코인/암호학' 카테고리의 글 목록

[비트코인 암호학] 4.1 디지털 서명

[비트코인 암호학] 4.2 ECDSA - 1

[비트코인 암호학] 4.3 ECDSA - 2

[비트코인 구조] 개인키(Private key), 공개키(Public key), 주소(Address) 생성

---

DER 형식 서명(Signature) 생성

 

 이번 글에서는 개인키를 이용하여 r과 s값을 구해 DER 형식의 서명을 생성해보겠습니다. 이번 글에서 사용할 개인키는 이전 글에서 생성했던 개인키입니다. 'start bitcoin' 키워드를 이용해 sha-256 해시함수로 생성한 개인키는 다음과 같았습니다.

 

개인키: 42d219444915828585a35b44849417b6eeb604bd0c7afda058c78319481d0055

 

1. r 구하기

 개인키를 이용해 s값을 구하기 위해서는 먼저 r값이 필요합니다. r 값은 다음과 같이 무작위 값 k와 secp256k1에 미리 정의된 생성점 G를 이용해 타원곡선의 스칼라 곱셈으로 구할 수 있었습니다.

 

 r값을 구하기 위해 우선 k값을 정하겠습니다. k값은 무작위로 생성해야 하지만, 서명을 테스트용으로 사용할 것이기 때문에 개인키와 마찬가지로 sha-256 해시 함수를 사용해서 k값을 생성하겠습니다. 생성 키워드는 'bitcoin sig'입니다. k를 구하는 파이썬 코드는 다음과 같습니다.

 

import hashlib

s = b'bitcoin sig'
h = hashlib.sha256(s)

print(h.hexdigest())

 생성된 k값은 다음과 같습니다.

 

k값: a0273e3fb1f0337fedb812de93199f0f255d65697155ddde2eb8c89fd72bbbbf

 

 이제 구한 k값을 사용해 r값을 구해보겠습니다. k와 G의 타원곡선 스칼라 곱셈 값의 x좌표가 바로 r입니다. 개인키를 이용해 공개키를 생성했던 방식과 비슷하게 r값을 구할 수 있습니다. 파이썬 코드는 다음과 같습니다.

# k값
k = 0xa0273e3fb1f0337fedb812de93199f0f255d65697155ddde2eb8c89fd72bbbbf

#secp256k1
p = 2**256 - 2**32 - 977 # 타원곡선의 위수 p (공개키 아님)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
g = [gx, gy]

# 점 덧셈 함수
def add(dot1, dot2, p):
    # 한 점이 무한원점일 경우
    if dot1 == None:
        return dot2
    elif dot2 == None:
        return dot1
    
    x1 = dot1[0]
    x2 = dot2[0]
    y1 = dot1[1]
    y2 = dot2[1]

	# 점 덧셈 계산
    if x1==x2 and y1!=y2:
        return None # 무한원점
    elif x1!=x2 and y1!=y2:
        m = (((y2-y1)%p) * power((x2-x1)%p,(p-2),p))%p
        x3 = (m**2-x1-x2)%p
        y3 = (m*(x1-x3)-y1)%p
        return [x3,y3]
    elif x1==x2 and y1==y2 and y1!=0:
        m = (((3*x1**2)%p) * power((2*y1)%p,p-2,p))%p
        x3 = (m**2-2*x1)%p
        y3 = (m*(x1-x3)-y1)%p
        return [x3,y3]
    else:
        return None

# 빠른 거듭제곱 계산
def power(a,b,p):
    result = 1
    while b > 0:
        if b % 2 != 0:
            result = (result*a) % p
        b //= 2
        a = (a*a) % p

    return result


# r 구하기
i = 0
g_list = []
# k는 G의 군의 위수 n에 대하여 순환하므로 n에 대한 나머지 구하기
k = k % n
while True:
    g_list.append(g)
    g = add(g,g,p)
    # 계산속도를 빠르게 하기 위한 방법 사용
    # G*G => 2G * 2G => ... => nG * nG + (n-i)G + ...
    i += 1
    if(pow(2,i+1) > k):
        t = k - pow(2,i)
        i -= 1
        while t != 0:
            if t >= pow(2,i):
                t = t - pow(2,i)
                g = add(g,g_list[i],p)
            i -= 1
        break

# 결과 출력
print(hex(g[0]))

 

 구해진 r값은 다음과 같습니다.

 

r값: 5fc7f24e7e94fce826ac463039fcdf375df54cce8fbc79ed723d8c3c260ab392

 

2. s 구하기

 r값을 구했으니 개인키를 이용하여 s값을 구할 수 있습니다. s값은 다음과 같은 식을 이용하여 구할 수 있습니다.

 k는 기존에 구한 k값, n은 secp256k1에 정의된 값, r은 k를 통해 구한 값, d는 개인키입니다. 여기에서 아직 구하지 못한 값은 메시지의 해시값인 z입니다. 해당 값은 트랜잭션 값을 이용하여야만 구할 수 있으므로 이번 생성에서는 임의의 값을 사용하겠습니다. 키워드 'message'를 이용해 sha-256 함수로 구한 z값은 다음과 같습니다.

 

z값: ab530a13e45914982b79f9b7e3fba994cfd1f3fb22f71cea1afbf02b460c6d1d

 

 이제 모든 값을 구했으니 s를 구해보겠습니다. 먼저 1/k를 구해보겠습니다. 유한체에서의 연산이기 때문에 위 공식을 사용하여 계산합니다. 파이썬 코드는 다음과 같습니다.

 

k = 0xa0273e3fb1f0337fedb812de93199f0f255d65697155ddde2eb8c89fd72bbbbf
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

k_i = pow(k, n-2, n)
print(hex(k_i))

 

결괏값은 다음과 같습니다.

 

1/k 값: cb356c348d7f53fa19c216be116674c2b41cd96f182224020e5d49c9951c7519

 

 마지막으로 이 값을 이용해 s값을 구합니다. 파이썬 코드는 다음과 같습니다.

 

k_i = 0xcb356c348d7f53fa19c216be116674c2b41cd96f182224020e5d49c9951c7519
r = 0x5fc7f24e7e94fce826ac463039fcdf375df54cce8fbc79ed723d8c3c260ab392
d = 0x42d219444915828585a35b44849417b6eeb604bd0c7afda058c78319481d0055
z = 0xab530a13e45914982b79f9b7e3fba994cfd1f3fb22f71cea1afbf02b460c6d1d
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

s = (k_i*(z+r*d)) % n

print(hex(s))

 

 최종적으로 구해진 s값은 다음과 같습니다.

 

s값: d87b372b5b51fb47791c13d487e100435fbfae4691fee9d9d8cbc51ab1be1278

 

3. DER 형식 서명 구하기

 최종적으로 r과 s를 이용하여 DER 형식의 서명을 생성해보겠습니다.

 

1. r값의 첫 바이트(첫 16진수 두 자리)가 0x80보다 같거나 크면 r값 앞에 00을 붙입니다.

 

 0x5f는 0x80보다 작으므로 아무 값도 붙이지 않습니다.

5fc7f24e7e94fce826ac463039fcdf375df54cce8fbc79ed723d8c3c260ab392

 

2. 1번에서 구한 값의 바이트 단위 길이를 16진수로 1번 값 앞에 붙입니다. 바이트 단위 길이를 구하는 코드는 다음과 같습니다.

 

i = '5fc7f24e7e94fce826ac463039fcdf375df54cce8fbc79ed723d8c3c260ab392'
print(hex(len(bytes.fromhex(i))))

 

구해진 길이가 0x20이므로 2번의 결괏값은 다음과 같습니다.

205fc7f24e7e94fce826ac463039fcdf375df54cce8fbc79ed723d8c3c260ab392

 

3. r값의 시작이라는 뜻의 '02'를 맨 앞에 붙입니다.

 

02205fc7f24e7e94fce826ac463039fcdf375df54cce8fbc79ed723d8c3c260ab392

 

4. s값을 r값 대신 1~3번 방식을 그대로 적용하여 결과를 구합니다.

 

 0xd8은 0x80보다 크므로 '00'을 앞에 붙입니다.

00d87b372b5b51fb47791c13d487e100435fbfae4691fee9d9d8cbc51ab1be1278

 

 길이가 0x21이므로 '21'을 앞에 붙입니다.

2100d87b372b5b51fb47791c13d487e100435fbfae4691fee9d9d8cbc51ab1be1278

 

 '02'까지 붙인 결괏값은 다음과 같습니다.

022100d87b372b5b51fb47791c13d487e100435fbfae4691fee9d9d8cbc51ab1be1278

 

5. 3번에서 구한 값 뒤에 4번에서 구한 값을 붙입니다.

 

02205fc7f24e7e94fce826ac463039fcdf375df54cce8fbc79ed723d8c3c260ab392022100d87b372b5b51fb47791c13d487e100435fbfae4691fee9d9d8cbc51ab1be1278

 

6. 5번 값의 바이트 길이를 16진수로 구해 맨 앞에 붙입니다.

 

 5번 값의 길이가 0x45이므로 '45'를 맨 앞에 붙입니다.

4502205fc7f24e7e94fce826ac463039fcdf375df54cce8fbc79ed723d8c3c260ab392022100d87b372b5b51fb47791c13d487e100435fbfae4691fee9d9d8cbc51ab1be1278

 

7. '30'을 맨 앞에 붙입니다. 이 결괏값이 바로 DER 형식 서명입니다.

 

304502205fc7f24e7e94fce826ac463039fcdf375df54cce8fbc79ed723d8c3c260ab392022100d87b372b5b51fb47791c13d487e100435fbfae4691fee9d9d8cbc51ab1be1278

 

 

 지금까지 r값과 s값을 구하고, DER 형식의 서명을 구해봤습니다. 감사합니다.

 

 

이어지는 글들

---

[비트코인 구조] 잠금 스크립트(scriptPubkey)와 해제 스크립트(scriptSig) 기초