楕円曲線暗号 ビットコイン用の曲線の定義 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
%