計算機科学のブログ

楕円曲線暗号 ビットコイン用の曲線の定義 secp2546k1の計算 有限体、任意の大きさの整数、mathインポートパス、bigパッケージ、Int型

プログラミング・ビットコイン ―ゼロからビットコインをプログラムする方法 (Jimmy Song(著)、中川 卓俊(監修)、住田 和則(監修)、中村 昭雄(監修)、星野 靖子(翻訳)、オライリー・ジャパン)の3章(楕円曲線暗号)、3.9(ビットコイン用の曲線の定義)、3.9.1(secp256k1の計算)に出てくる大きさの整数を扱えるように有限体のコードを修正。

コード

ecc.go

// Package ecc (Elliptic Curve Cryptography, 楕円曲線暗号)
package ecc

import (
	"fmt"
	"math/big"
)

// FieldElement 有限体の要素
type FieldElement struct {
	Num, Prime *big.Int
}

func (fe FieldElement) String() string {
	return fmt.Sprintf("FieldElement_%v(%v)", fe.Prime, fe.Num)
}

// NewFieldElement ...
func NewFieldElement(n, p *big.Int) (FieldElement, error) {
	r1 := n.Cmp(p)
	r2 := n.Cmp(big.NewInt(0))
	if !(r1 == -1 && r2 == 1) {
		pSub1 := new(big.Int)
		pSub1.Sub(p, big.NewInt(1))
		return FieldElement{},
			fmt.Errorf("%v not in field range 0 to %v", n, pSub1)
	}
	return FieldElement{n, p}, nil
}

// Eq ...
func (fe FieldElement) Eq(fes ...FieldElement) bool {
	xPrime := fe.Prime
	if xPrime.Cmp(big.NewInt(0)) == 0 {
		return false
	}
	xNum := fe.Num
	for _, y := range fes {
		if xNum.Cmp(y.Num) != 0 || xPrime.Cmp(y.Prime) != 0 {
			return false
		}
	}
	return true
}

// Ne ...
func (fe FieldElement) Ne(fes ...FieldElement) bool {
	return !fe.Eq(fes...)
}

// Add ...
func (fe FieldElement) Add(fes ...FieldElement) (FieldElement, error) {
	t := new(big.Int)
	t.Set(fe.Num)
	for _, fei := range fes {
		if fe.Prime.Cmp(fei.Prime) != 0 {
			return FieldElement{}, fmt.Errorf("Cannot add two numbers in different Fields")
		}
		t.Add(t, fei.Num)
		t.Mod(t, fei.Prime)
	}
	return FieldElement{t, fe.Prime}, nil
}

// Sub ...
func (fe FieldElement) Sub(fes ...FieldElement) (FieldElement, error) {
	t := new(big.Int)
	t.Set(fe.Num)
	for _, fey := range fes {
		if fe.Prime.Cmp(fey.Prime) != 0 {
			return FieldElement{}, fmt.Errorf("Cannot sub two numbers in different Fields")
		}
		t.Sub(t, fey.Num)
		t.Mod(t, fey.Prime)
	}
	return FieldElement{Num: t, Prime: fe.Prime}, nil
}

// Mul ...
func (fe FieldElement) Mul(fes ...FieldElement) (FieldElement, error) {
	if fe.Num.Cmp(big.NewInt(0)) == 0 {
		return fe, nil
	}
	n := new(big.Int)
	n.Set(fe.Num)
	t, _ := NewFieldElement(n, fe.Prime)
	for _, fey := range fes {
		if fe.Prime.Cmp(fey.Prime) != 0 {
			return FieldElement{}, fmt.Errorf("Cannot mul two numbers in different Fields")
		}
		if fey.Num.Cmp(big.NewInt(0)) == 0 {
			return fey, nil
		}
		s := t
		one := big.NewInt(1)
		for i := big.NewInt(1); i.Cmp(fey.Num) == -1; i.Add(i, one) {
			t, _ = t.Add(s)
		}
	}
	return t, nil
}

// Div ...
func (fe FieldElement) Div(fey FieldElement) (FieldElement, error) {
	if fe.Prime.Cmp(fey.Prime) != 0 {
		return FieldElement{},
			fmt.Errorf("Cannot div two numbers in different Fields")
	}
	if fey.Num.Cmp(big.NewInt(0)) == 0 {
		return FieldElement{},
			fmt.Errorf("division by zero")
	}
	y := new(big.Int)
	y.Sub(fey.Prime, big.NewInt(2))
	return fe.Mul(fey.Pow(y))
}

// Pow ...
func (fe FieldElement) Pow(y *big.Int) FieldElement {
	if y.Cmp(big.NewInt(0)) < 0 {
		y.Add(y, fe.Prime)
		y.Sub(y, big.NewInt(1))
	}
	if y.Cmp(big.NewInt(0)) == 0 {
		t, _ := NewFieldElement(big.NewInt(0), fe.Prime)
		return t
	}
	t := fe
	one := big.NewInt(1)
	for i := big.NewInt(1); i.Cmp(y) == -1; i.Add(i, one) {
		t, _ = t.Mul(fe)
	}
	return t
}

ecc_test.go

package ecc

import (
	"math/big"
	"testing"
)

func TestFieldElementEq(t *testing.T) {
	p := big.NewInt(13)
	a, _ := NewFieldElement(big.NewInt(7), p)
	b, _ := NewFieldElement(big.NewInt(6), p)
	got := a.Eq(b)
	want := false
	if got {
		t.Errorf("%v.Eq(%v) got %v, want false", a, b, got)
	}
	got = a.Eq(a)
	want = true
	if !got {
		t.Errorf("%v.Eq(%v) got %v, want true", a, a, want)
	}
}

func TestFieldElementNe(t *testing.T) {
	p := big.NewInt(13)
	a, _ := NewFieldElement(big.NewInt(7), p)
	b, _ := NewFieldElement(big.NewInt(6), p)
	got := a.Ne(b)
	if !got {
		t.Errorf("%v.Ne(%v) got %v, want true", a, b, got)
	}
	got = a.Ne(a)
	if got {
		t.Errorf("%v.Ne(%v) got %v, want false", a, a, got)
	}
}

func TestFieldElementAdd(t *testing.T) {
	p := big.NewInt(13)
	a, _ := NewFieldElement(big.NewInt(7), p)
	b, _ := NewFieldElement(big.NewInt(12), p)
	c, _ := NewFieldElement(big.NewInt(6), p)
	d, _ := a.Add(b)
	if d.Ne(c) {
		t.Errorf("%v.Add(%v) got %v, want %v", a, b, d, c)
	}
}

func TestFieldElementSub(t *testing.T) {
	p := big.NewInt(19)
	tests := []struct {
		x, y, want int64
	}{
		{11, 9, 2},
		{6, 13, 12},
	}
	for _, test := range tests {
		x, _ := NewFieldElement(big.NewInt(test.x), p)
		y, _ := NewFieldElement(big.NewInt(test.y), p)
		got, _ := x.Sub(y)
		want, _ := NewFieldElement(big.NewInt(test.want), p)
		if got.Ne(want) {
			t.Errorf("%v.Sub(%v) got %v, want %v", x, y, got, want)
		}
	}
}

func TestFieldElementMul(t *testing.T) {
	p := big.NewInt(13)
	x, _ := NewFieldElement(big.NewInt(3), p)
	y, _ := NewFieldElement(big.NewInt(12), p)
	got, _ := x.Mul(y)
	want, _ := NewFieldElement(big.NewInt(10), p)
	if got.Ne(want) {
		t.Errorf("%v.Mul(%v) got %v, want %v", x, y, got, want)
	}
}

func TestFieldElementDiv(t *testing.T) {
	p := big.NewInt(19)
	tests := []struct {
		num, den, want int64
	}{
		{2, 7, 3},
		{7, 5, 9},
	}
	for _, test := range tests {
		num, _ := NewFieldElement(big.NewInt(test.num), p)
		den, _ := NewFieldElement(big.NewInt(test.den), p)
		got, _ := num.Div(den)
		want, _ := NewFieldElement(big.NewInt(test.want), p)
		if got.Ne(want) {
			t.Errorf("%v.Div(%v) got %v, want %v", num, den, got, want)
		}
	}
}

func TestFieldElementPow(t *testing.T) {
	p := big.NewInt(13)
	tests := []struct {
		x, y, want int64
	}{
		{3, 3, 1},
		{7, -3, 8},
	}
	for _, test := range tests {
		x, _ := NewFieldElement(big.NewInt(test.x), p)
		got := x.Pow(big.NewInt(test.y))
		want, _ := NewFieldElement(big.NewInt(test.want), p)
		if got.Ne(want) {
			t.Errorf("%v.Pow(%v) got %v, want %v", x, test.y, got, want)
		}
	}
}

入出力結果

 % go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:10:36: cannot use big.NewInt(7) (type *big.Int) as type int in argument to NewFieldElement
./ecc_test.go:10:36: cannot use p (type *big.Int) as type int in argument to NewFieldElement
./ecc_test.go:11:36: cannot use big.NewInt(6) (type *big.Int) as type int in argument to NewFieldElement
./ecc_test.go:11:36: cannot use p (type *big.Int) as type int in argument to NewFieldElement
./ecc_test.go:12:10: a.Eq undefined (type FieldElement has no field or method Eq)
./ecc_test.go:17:9: a.Eq undefined (type FieldElement has no field or method Eq)
FAIL	bitcoin/ecc [build failed]
% go test
PASS
ok  	bitcoin/ecc	0.387s
% go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:28:10: a.Ne undefined (type FieldElement has no field or method Ne)
./ecc_test.go:32:9: a.Ne undefined (type FieldElement has no field or method Ne)
FAIL	bitcoin/ecc [build failed]
% go test
PASS
ok  	bitcoin/ecc	0.277s
% go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:43:11: a.Add undefined (type FieldElement has no field or method Add)
FAIL	bitcoin/ecc [build failed]
% go test
PASS
ok  	bitcoin/ecc	0.221s
% go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:60:14: x.Sub undefined (type FieldElement has no field or method Sub)
FAIL	bitcoin/ecc [build failed]
% go test
PASS
ok  	bitcoin/ecc	0.068s
% go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:72:13: x.Mul undefined (type FieldElement has no field or method Mul)
FAIL	bitcoin/ecc [build failed]
% go test
PASS
ok  	bitcoin/ecc	0.223s
% go test
PASS
ok  	bitcoin/ecc	0.222s
%