밑바닥부터 시작하는 비트코인 - 3장 타원곡선 암호

본 게시글에서는 저서 '밑바닥부터 시작하는 비트코인'의 Python으로 작성된 예제 코드를 Golang으로 컨버팅 하여 작성하였습니다.

📺 시리즈

2023.08.25 - [Go/Blockchain] - 밑바닥부터 시작하는 비트코인 - 1장 유한체

2023.08.27 - [Go/Blockchain] - 밑바닥부터 시작하는 비트코인 - 2장 타원곡선

---

🐱‍👤 전체 코드

GitHub - piatoss3612/bitcoin-from-scratch

---

🎁 들어가며

 이전 장에서 작성된 유한체와 타원 곡선과 관련된 코드에 변경된 부분이 굉장히 많습니다.

 

변경사항

1. 유한체 원소의 값을 처음에는 정수(int) 형으로 사용을 하다가 실수(float64)로 변경했고, 256비트 크기의 정수를 표현하기 위해 big number(big.Int) 형으로 최종 변경했습니다.

// 유한체의 원소를 나타내는 구조체
type fieldElement struct {
	num   *big.Int
	prime *big.Int
}

 

2. 인터페이스를 정의하고 구조체로 인터페이스를 구현하여 함수 또는 메서드에서 특정 구조체에 국한되지 않고 매개변수를 받을 수 있도록 코드를 추가하였습니다.

// 유한체의 원소 인터페이스
type FieldElement interface {
	fmt.Stringer
	Num() *big.Int
	Prime() *big.Int
	Equal(other FieldElement) bool
	NotEqual(other FieldElement) bool
	Add(other FieldElement) (FieldElement, error)
	Sub(other FieldElement) (FieldElement, error)
	Mul(other FieldElement) (FieldElement, error)
	Pow(exp *big.Int) (FieldElement, error)
	Div(other FieldElement) (FieldElement, error)
}

// 유한체의 원소를 생성하는 함수
func NewFieldElement(num, prime *big.Int) (FieldElement, error) {
	// num과 prime이 nil인 경우 유한체의 원소를 생성할 수 없음
	if num == nil || prime == nil {
		return nil, fmt.Errorf("num or prime cannot be nil")
	}

	// 유한체의 원소가 0보다 작거나 위수보다 크거나 같은 경우 유한체의 원소를 생성할 수 없음
	if !inRange(num, prime) {
		return nil, fmt.Errorf("num %s not in field range 0 to %s", num, prime.Sub(prime, big.NewInt(1)))
	}

	return &fieldElement{num, prime}, nil
}

 

3. 상위 구조체를 하위 구조체에 임베딩하여 동일한 동작에 대하여 중복된 코드 작성을 줄였습니다.

// secp256k1 유한체의 원소 구조체
type s256FieldElement struct {
	fieldElement
}

 

*2023년 9월 1일 추가*

1. 서명 메서드의 매개변수를 *big.Int 타입으로 받는 것은 범용성이 떨어진다고 판단하여 바이트 슬라이스 타입으로 변경했습니다.

// 기존 개인키 인터페이스
type PrivateKey interface {
	fmt.Stringer
	Sign(z *big.Int) (Signature, error)
}

// 변경된 개인키 인터페이스
type PrivateKey interface {
	fmt.Stringer
	Sign(z []byte) (Signature, error)
}

 

2. s256PrivateKey 구조체의 String 메서드를 호출하면 비밀키를 그대로 출력하는 대신 R을 출력하게 변경했습니다.

// 기존 메서드
func (pvk s256PrivateKey) String() string {
	return fmt.Sprintf("PrivateKey(%s)", pvk.secret.Text(16))
}

// 변경된 메서드
func (pvk s256PrivateKey) String() string {
	return fmt.Sprintf("R = %s", pvk.point)
}

 

 아무래도 동적타입 언어(Python)로 작성된 코드를 정적타입 언어(Go)로 옮기려다 보니, 교재를 처음부터 따라가면서 부분적인 코드만 보고 있는 저에게는 변수의 타입을 어떻게 지정해야 좋을지 감이 잘 안 오는 것 같습니다. 가끔은 이런 문제 때문에 동적타입 언어가 부러워지기도 합니다(연산자 오버로딩도 부러워요).

 

 이번 장은 타원곡선 암호를 이해하기 위해 앞서 1장에서 배운 유한체와 2장에서 배운 타원곡선의 개념을 활용합니다. 타원곡선 암호는 트랜잭션 서명과 검증에 필요한 기본 알고리즘이며 서명과 검증은 비트코인 동작의 중추이니 확실히 이해하고 넘어갑시다!

---

📕 유한체에서 정의된 타원곡선

 

실수체에서 정의된 타원곡선과 유한체에서 정의된 타원곡선

 유한체에서 정의된 타원곡선은 곡선이 아니라 점들이 산재되어 있는 모습입니다. 이는 유한체의 원소들이 실수처럼 연속적이지 않기 때문에 나타난 결과입니다.

 

 공통점을 찾아보자면 먼저 유한체에서 정의된 타원곡선이 y²의 영향으로 특정한 x값을 기준으로 점들이 대칭 형태로 나타난다는 것입니다. 그러나 유한체에는 음수가 존재하지 않으므로 실수체처럼 x축을 기준으로 대칭된 형태로는 나타나지 않습니다.

 

 유한체에서 정의된 타원곡선은 유한체에서 사용되는 연산들을 점 덧셈에 사용할 수 있습니다. 따라서 실수체에서 정의된 타원곡선 상의 점 덧셈과 마찬가지로 유효한 결과를 도출할 수 있습니다.

---

✖ 타원곡선 위 점의 스칼라 곱셈

타원곡선 상의 동일한 점을 더할 수 있으므로 다음과 같이 표현할 수 있습니다.

(170, 142) + (170, 142) = 2 * (170, 142)

 점 덧셈에는 결합법칙이 성립하므로 다음과 같이 동일한 점을 얼마든지 더할 수 있습니다. 이를 스칼라 곱셈(Scalar Multiplication)이라고 합니다.

2 * (170, 142) + (170, 142) = 3 * (170, 142)
2 * (170, 142) + 3 * (170, 142) = 5 * (170, 142)

 

스칼라 곱셈의 결과는 점 덧셈이 비선형 연산이고 결과를 예측하기 어려운 것과 마찬가지로 실제 계산해보지 않고는 그 값을 예측하기 어렵습니다.

 

 스칼라 곱셈을 실행하는 것 자체는 크게 어려울 것이 없지만, 스칼라 곱셈의 결과를 가지고 초기 상태를 역산하는 것은 굉장히 어렵습니다. 이를 이산 로그 문제(DLP: Discrete Log Problem)이라고 하며 타원곡선 암호의 핵심 원리입니다.

 

스칼라 곱셈의 또 다른 성질로는, 어떤 점 G에 스칼라 값을 계속 증가시키면서 곱하다 보면 무한원점(point at infinity)에 도달한다는 것입니다. 무한원점은 덧셈의 항등원이기 때문에 무한원점에서 다시 G를 계속해서 더하다 보면 G부터 무한원점까지 반복되는 집합을 발견할 수 있습니다. 이 집합을 수학용어로 군(Group)이라 하며 덧셈 연산을 잘 지원합니다. n은 유한한 특정 값이므로 유한군(Finite Group) 또는 유한순환군(Finite Cyclic Group)입니다.

{ G, 2G, 3G, 4G, ... nG } 여기서 nG는 0 (무한원점) 

---

👨‍👨‍👦‍👦 스칼라 곱셈으로 생성된 군의 성질

 유한체에서 정의된 타원곡선 위 한 점에 스칼라 값을 곱해서 유한순환군을 생성할 수 있습니다. 이 한 점을 생성점(Generator Point)이라고 합니다.

 

 유한체와는 다르게 유한순환군에서는 점 덧셈 하나만 있습니다. 유한순환군은 점 덧셈을 위한 몇 가지 성질을 가지고 있습니다. 덧셈에 닫혀있고, 덧셈의 역원과 항등원이 존재하며, 교환법칙, 결합법칙이 성립합니다.

 

1. 항등원 존재

 항등원은 표기를 0으로 하고 무한원점으로 정의됩니다.

0 + A = A

2. 덧셈에 닫혀 있음

 군을 생성할 때 생성점 G를 반복해서 더하다 보면 결국은 유한순환군 { G, 2G, 3G, ... nG = 0 } 안에서 값이 반복된다는 것을 알 수 있습니다.

3. 덧셈의 역원 존재

 수학적으로 만약 aG가 군에 속하면 (n - a)G도 군에 속합니다. 이 둘을 더하면 aG + (n - a)G = nG = 0으로 무한원점이 됩니다.

4. 교환법칙

 점 덧셈의 정의로부터 aG + bG = bG + aG가 성립합니다.

5. 결합법칙

 점 덧셈의 정의로부터 A + (B + C) = (A + B) + C가 성립합니다.

---

💻 스칼라 곱셈 코딩하기

// 타원곡선 점의 스칼라 곱셈 함수
func (p point) Mul(coefficient *big.Int) (Point, error) {
	current := Point(&p) // 시작점으로 초기화

	result, err := NewPoint(nil, nil, p.a, p.b)
	if err != nil {
		return nil, err
	}

	return p.mul(coefficient, current, result)
}

// 타원곡선 점의 스칼라 곱셈 내부 함수
func (p point) mul(coefficient *big.Int, current, result Point) (Point, error) {
	coef := coefficient // 계수

	var err error

	// 이진수 전개법을 이용하여 타원곡선의 점 곱셈
	for coef.Cmp(big.NewInt(0)) == 1 {
		// 가장 오른쪽 비트가 1인지 확인
		if coef.Bit(0) == 1 {
			result, err = result.Add(current) // 현재 점을 결과에 더하기
			if err != nil {
				return nil, err
			}
		}
		current, err = current.Add(current) // 현재 점을 두 배로 만들기
		if err != nil {
			return nil, err
		}

		coef.Rsh(coef, 1) // 비트를 오른쪽으로 한 칸씩 이동
	}

	return result, nil
}

이진수 전개법 예시

coef = 13, result = 0, current = G라고 했을 때, coef를 2진수로 표현하면 1101₍₂₎

이진수로 표현한 coef의 최하위 비트부터 살펴보면서 반복문을 돌려봅니다.

[Round 1]
1. coef의 최하위 비트가 1이므로 result에 current를 더해줍니다. => result + current = 0 + current = 0 + G = G
2. current에 current를 더해줍니다. => current + current = G + G = 2G
3. coef의 비트를 오른쪽으로 한 칸씩 이동합니다. => coef = 110

[Round2]

1. coef의 최하위 비트가 0이므로 넘어갑니다.

2. current에 current를 더해줍니다. => current + current = 2G + 2G = 4G

3. coef의 비트를 오른쪽으로 한 칸씩 이동합니다. => coef = 11

 

[Round3]

1. coef의 최하위 비트가 1이므로 result에 current를 더해줍니다. => result + current = G + 4G = 5G

2. current에 current를 더해줍니다. => current + current = 4G + 4G = 8G

3. coef의 비트를 오른쪽으로 한 칸씩 이동합니다. => coef = 1

 

[Round4]

1. coef의 최하위 비트가 1이므로 result에 G를 더해줍니다. => result + current = 5G + 8G = 13G

2. current에 current를 더해줍니다. => current + current = 8G + 8G = 16G

3. coef의 비트를 오른쪽으로 한 칸씩 이동합니다. => coef = 0

 

[Round5]

1. coef가 0이 되었으므로 반복문을 종료하고 result = 13G를 반환합니다.

 

 결과적으로, 이진수 전개법을 사용하여 O(N)이던 시간복잡도를 O(logN)으로 줄일 수 있습니다. N이 작을 때는 큰 차이가 없어 보이지만, N이 2의 256승이라면 2의 256승 번 실행해야 하는 연산을 256번으로 획기적으로 줄일 수 있습니다. 뭐 그렇게까지 돌릴 일은 없겠지만 말이죠 😎

---

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

 비트코인은 secp256k1 곡선을 사용합니다. secp256k1 곡선의 매개변수는 다음과 같습니다.

곡선의 계수 a = 0, b = 0이며, 곡선은 y² = x³ + 7
유한체의 위수 p는 2²⁵⁶ - 2³² - 977
생성점 G의 x좌표는 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
생성점 G의 y좌표는 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
생성점 G로 생성한 유한순환군의 위수 n은 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

 

📈 타원곡선 secp256k1을 위한 구조체 정의

var (
	A = 0      // secp256k1 타원곡선의 a 계수
	B = 7      // secp256k1 타원곡선의 b 계수
	G Point    // secp256k1 타원곡선의 생성점
	N *big.Int // secp256k1 타원곡선 유한군의 위수
	P = big.NewInt(0).Sub(
		big.NewInt(0).Sub(
			big.NewInt(0).Exp(big.NewInt(2), big.NewInt(256), nil),
			big.NewInt(0).Exp(big.NewInt(2), big.NewInt(32), nil)),
		big.NewInt(977)) // secp256k1 타원곡선의 유한체의 위수
)

// 타원곡선의 점을 생성하는 함수 타입
type PointGenerator func(x, y, a, b FieldElement) (Point, error)

// secp256k1 타원곡선의 생성점과 위수를 초기화
func init() {
	bigGx, _ := new(big.Int).SetString("79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798", 16)
	bigGy, _ := new(big.Int).SetString("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16)
	n, _ := new(big.Int).SetString("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141", 16)

	gx, _ := NewS256FieldElement(bigGx)
	gy, _ := NewS256FieldElement(bigGy)
	g, _ := NewS256Point(gx, gy)

	G = g
	N = n
}

// secp256k1 타원곡선의 점 구조체
type s256Point struct {
	point // 상위 구조체를 임베딩하여 기능 상속, 필드 재사용
}

// secp256k1 타원곡선의 점 생성 함수
func NewS256Point(x, y FieldElement) (Point, error) {
	a, err := NewS256FieldElement(big.NewInt(int64(A)))
	if err != nil {
		return nil, err
	}

	b, err := NewS256FieldElement(big.NewInt(int64(B)))
	if err != nil {
		return nil, err
	}

	if isInfinity(x, y) {
		return &s256Point{point{x: x, y: y, a: a, b: b}}, nil
	}

	if !isOnCurve(x, y, a, b) {
		return nil, fmt.Errorf("(%s, %s) is not on the curve", x, y)
	}

	return &s256Point{point{x: x, y: y, a: a, b: b}}, nil
}

// secp256k1 타원곡선의 점을 더하는 PointGenerator 함수
func (p s256Point) Add(other Point) (Point, error) {
	// 같은 타원곡선 위에 있는지 확인
	if !sameCurve(p.a, p.b, other.A(), other.B()) {
		return nil, fmt.Errorf("points %s and %s are not on the same curve", p, other)
	}

	/* case1: 두 점이 x축에 수직인 직선 위에 있는 경우 */

	// p가 무한원점인지 확인
	if isInfinity(p.x, p.y) {
		return other, nil
	}

	// other가 무한원점인지 확인
	if isInfinity(other.X(), other.Y()) {
		return &p, nil
	}

	// 한 점에 그의 역원을 더하는 경우, 무한원점을 반환
	if areInverse(p.x, other.X(), p.y, other.Y()) {
		return NewS256Point(nil, nil)
	}

	// secp256k1 타원곡선의 점을 생성하는 함수
	gen := func(x, y, _, _ FieldElement) (Point, error) {
		return NewS256Point(x, y)
	}

	/* case2: 두 점이 서로 다른 경우 */

	if p.x.NotEqual(other.X()) {
		return p.addDifferentPoint(other, gen)
	}

	/* case3: 두 점이 같은 경우 */

	// p와 other가 같은 점인지 확인
	if samePoint(p.x, p.y, other.X(), other.Y()) {
		return p.addSamePoint(other, gen)
	}

	return nil, fmt.Errorf("unhandled case, (%s, %s) + (%s, %s)", p.x, p.y, other.X(), other.Y())
}

// secp256k1 타원곡선의 점의 스칼라 곱셈 함수
func (p s256Point) Mul(coefficient *big.Int) (Point, error) {
	// 계수가 N보다 큰 경우, 계수를 N으로 나눈 나머지를 계수로 사용
	// 왜? N*G = O, 무한원점 이기 때문에 N보다 큰 계수는 N으로 나눈 나머지를 계수로 사용해도 결과는 같음
	coef := new(big.Int).Mod(coefficient, N)
	current := Point(&p) // 시작점으로 초기화

	result, err := NewS256Point(nil, nil)
	if err != nil {
		return nil, err
	}

	return p.mul(coef, current, result)
}

package main

import (
	"chapter03/ecc"
	"chapter03/hash256"
	"fmt"
	"math/big"
)

func main() {
	nG, err := ecc.G.Mul(ecc.N)
	if err != nil {
		panic(err)
	}

	fmt.Println(nG)
}

$ go run main.go 
Point(infinity)

 생성점 G와 N을 곱한 결과가 무한원점이므로, N이 G로 생성한 군의 위수임을 확인할 수 있습니다.

---

🔑 공개키 암호

  공개키 암호 연산에 필요한 비대칭 방정식은 다음과 같습니다.

P = eG

 

 여기서 G는 생성점, e는 개인키, P는 공개키입니다. 앞서 살펴봤듯이 e와 G의 스칼라 곱셈으로 P를 구하는 것은 어렵지 않지만, P와 G를 가지고 e를 알아내는 것은 이산 로그 문제로, 해결하기 쉽지 않습니다. 특히 유한순환군의 위수가 n처럼 아주아주 클 때 말이죠.

---

🔨 서명 생성과 서명 검증

1. 서명이 왜 필요한가?

• 식별할 수 있는 신원을 정의해야 합니다.
• 불특정 다수에게 신원을 증명할 수 있어야 합니다.
• 신원 증명을 위해 비밀키를 드러내지 않고 비밀키의 소유를 증명해야 합니다.
• 위변조 여부를 파악할 수 있어야 합니다.

 위의 조건을 만족하는 것이 디지털 서명입니다. 디지털 서명과 검증은 비트코인을 다른 주소로 보내는 사람이 필요한 비밀키를 소유하고 있다는 것을 증명하는 용도로 사용됩니다.

2. 디지털 서명 알고리즘

 비트코인에서 사용하는 서명 알고리즘은 타원곡선 서명 알고리즘-ECDSA(Elliptic Curve Digital Signature Algorithm)입니다.

 

 서명자는 임의의 값 k와 이에 대응하는 R을 정의합니다.

kG = R

 

 그리고 다음의 방정식을 정의합니다. 서명자는 k를 임의의 값으로, u, v≠ 0인 값으로 선정합니다. G는 생성점, P는 공개키로 알려져 있는 값들이므로 이는 곧 u와 v를 구하는 이산 로그 문제와 동일합니다.

uG + vP = kG = R

 

 방정식을 P에 관해 정리하면 다음과 같습니다.

P = ((k - u) / v)G

 

 여기서 서명자가 e를 알고 있다면 P를 eG로 대치할 수 있습니다. e를 알고 있는 서명자는 아래의 식을 만족하는 모든 (u, v) 조합 중 한 가지를 선정할 수 있습니다.

P = eG = ((k - u) / v)G
e = (k - u) / v)

 

 그러나 만약 서명자가 e를 모른다면 e를 구하기 위해 식을 만족하는 (u, v)를 찾을 때까지 무차별 대입(Brute Force)을 해야 하며, 유한체의 위수가 크면 클수록 그만큼 많은 값을 대입해봐야 하므로 (u, v)를 찾는 것이 굉장히 어렵습니다. 따라서 (u, v)를 제공하는 서명자가 비밀키 e를 알고 있다고 가정하는 것이 타당하며, 이러한 방식으로 서명자는 e를 공개하지 않고 e를 소유하고 있음을 증명할 수 있습니다.

 

 서명자가 e를 알고 있는 상태에서 u와 v는 다음과 같이 선정합니다. 여기서 z는 서명해시로 비트코인에서 트랜잭션 데이터를 직렬화한 후 해싱한 값입니다. r은 R의 x좌표입니다.

u = z / s, v = r / s

 

  s는 다음과 같이 구할 수 있습니다.

eG = P
uG + vP = R = kG
uG + veG = kG
u + ve = k
 z / s + re / s = k
(z + re)/k = s

 

 방정식은 최종적으로 다음과 같습니다. G는 생성점, z는 트랜잭션 데이터로 생성한 서명해시, P는 공개키로 알려져 있는 값들입니다. 서명자는 r과 s를 서명 데이터로 검증자에게 제공함으로써 비밀키 e를 드러내지 않고도 전자서명이 유효하다는 것을 검증할 수 있습니다.

(z / s) * G + (r / s) * P = R
R의 x좌표는 r과 동일

 

k를 공개하지 않는 이유

kG = uG + vP = R

kG = uG + veG

k = u + ve

(k - u) / v = e

 

k가 공개되면 u와 v는 r / s, z / s로 구할 수 있으므로 비밀키 e가 드러나게 됩니다!

3. 서명 검증 절차

1. 트랜잭션 데이터에 sha256 함수를 두 번 적용하여 32바이트 크기의 서명 해시 z를 구합니다. z를 서명에 포함시키는 이유는 트랜잭션의 위변조를 감지하고 무결성을 보장하기 위해서입니다.
2. 서명 (r, s)가 주어집니다. 이 값들을 사용해 u = z / s와 v = r / s를 정의합니다.
3. uG + vP = R을 계산합니다.
4. 만약 R의 x좌표가 r과 같다면 서명은 유효합니다.

4. 서명 검증 코딩하기

// secp256k1 타원곡선의 점의 서명 검증 함수
func (p s256Point) Verify(z *big.Int, sig Signature) (bool, error) {
	sInv := invBN(sig.S(), N)    // s^-1
	u := mulBN(z, sInv, N)       // u = z * s^-1
	v := mulBN(sig.R(), sInv, N) // v = r * s^-1

	uG, err := G.Mul(u) // uG
	if err != nil {
		return false, err
	}

	vP, err := p.Mul(v) // vP
	if err != nil {
		return false, err
	}

	R, err := uG.Add(vP) // uG + vP
	if err != nil {
		return false, err
	}

	x := R.X().Num() // res의 x좌표

	return x.Cmp(sig.R()) == 0, nil // x좌표가 r과 같은지 확인
}

5. 서명 생성 절차

1. 서명해시 z가 주어지고 비밀키 e를 알고 있는 상태에서 임의의 k를 선택합니다.
2. kG = R을 계산하여 x좌푯값 r을 구합니다.
3. s = (z + re) / k를 계산합니다.
4. 서명 (r, s)를 반환합니다.

6. 서명 생성 코딩하기

package ecc

import (
	"bytes"
	"crypto/hmac"
	"crypto/sha256"
	"fmt"
	"hash"
	"math/big"
)

// 서명 인터페이스
type Signature interface {
	fmt.Stringer
	R() *big.Int
	S() *big.Int
}

// 개인키 인터페이스
type PrivateKey interface {
	fmt.Stringer
	Sign(z *big.Int) (Signature, error)
}

// secp256k1 서명 구조체
type s256Signature struct {
	r *big.Int
	s *big.Int
}

// secp256k1 서명을 생성하는 함수
func NewS256Signature(r, s *big.Int) Signature {
	return &s256Signature{r, s}
}

// secp256k1 서명의 r값을 반환하는 함수
func (sig s256Signature) R() *big.Int {
	return sig.r
}

// secp256k1 서명의 s값을 반환하는 함수
func (sig s256Signature) S() *big.Int {
	return sig.s
}

// secp256k1 서명을 문자열로 반환하는 함수 (Stringer 인터페이스 구현)
func (sig s256Signature) String() string {
	return fmt.Sprintf("Signature(%s, %s)", sig.r.Text(16), sig.s.Text(16))
}

// secp256k1 개인키 구조체
type s256PrivateKey struct {
	secret *big.Int
	point  Point
}

// secp256k1 개인키를 생성하는 함수
func NewS256PrivateKey(secret *big.Int) (PrivateKey, error) {
	point, err := G.Mul(secret)
	if err != nil {
		return nil, err
	}
	return &s256PrivateKey{secret, point}, nil
}

// secp256k1 개인키로 서명을 생성하는 함수
func (pvk s256PrivateKey) Sign(z *big.Int) (Signature, error) {
	k, err := pvk.deterministicK(z) // RFC6979 표준에 따라 k값을 생성
	if err != nil {
		return nil, err
	}

	kG, err := G.Mul(k) // kG를 계산
	if err != nil {
		return nil, err
	}

	r := kG.X().Num() // kG의 x좌표를 r값으로 사용

	kInv := invBN(k, N) // k의 역원

	s := mulBN(addBN(z, mulBN(r, pvk.secret, N), N), kInv, N) // s = (z + r * pvk.secret) * k^-1 mod N

	// s가 N/2보다 큰 경우, s = N - s로 사용
	if s.Cmp(big.NewInt(0).Div(N, big.NewInt(2))) == 1 {
		ns := big.NewInt(0).Sub(N, s)
		return NewS256Signature(r, ns), nil
	}

	// 서명 생성
	return NewS256Signature(r, s), nil
}

// secp256k1 개인키를 문자열로 반환하는 함수 (Stringer 인터페이스 구현)
func (pvk s256PrivateKey) String() string {
	return fmt.Sprintf("PrivateKey(%s)", pvk.secret.Text(16))
}

// RFC6979 표준에 따라 k값을 생성하는 함수
// reference: https://github.com/codahale/rfc6979/blob/master/rfc6979.go
func (pvk s256PrivateKey) deterministicK(z *big.Int) (*big.Int, error) {
	k := bytes.Repeat([]byte{0x00}, 32)
	v := bytes.Repeat([]byte{0x01}, 32)

	if z.Cmp(N) == 1 {
		z.Sub(z, N)
	}

	zBytes := z.Bytes()
	secreteBytes := pvk.secret.Bytes()

	alg := sha256.New

	k = pvk.mac(alg, k, append(append(v, 0x00), append(secreteBytes, zBytes...)...), k)
	v = pvk.mac(alg, k, v, v)

	k = pvk.mac(alg, k, append(append(v, 0x01), append(secreteBytes, zBytes...)...), k)
	v = pvk.mac(alg, k, v, v)

	for {
		v = pvk.mac(alg, k, v, v)
		candidate := big.NewInt(0).SetBytes(v)

		if candidate.Cmp(big.NewInt(0)) == 1 && candidate.Cmp(N) == -1 {
			return candidate, nil
		}

		k = pvk.mac(alg, k, append(v, 0x00), k)
		v = pvk.mac(alg, k, v, v)
	}
}

func (pvk s256PrivateKey) mac(alg func() hash.Hash, k, m, buf []byte) []byte {
	h := hmac.New(alg, k)
	h.Write(m)
	return h.Sum(buf[:0])
}

---

📍 더 찾아볼 거리

1. 이산 로그 문제
2. 비트코인은 왜 secp256k1을 사용하는가?
3. 공개키 암호에 대한 이해
4. 서명해시 z에 sha256 해시 함수를 두 번 적용하는 이유
5. 서명 과정에서 s가 N / 2보다 작아야 하는 이유
6. k값 선정의 중요성

---

📖 참고자료

밑바닥부터 시작하는 비트코인

GitHub - jimmysong/programmingbitcoin: Repository for the book

Chapter 3. 타원곡선 암호

GitHub - codahale/rfc6979: A Go implementation of RFC 6979's deterministic DSA/ECDSA signature scheme.

글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!