計算機科学のブログ

楕円曲線 点の加算、加法逆元の関係、無限遠点、Goでコーディング

プログラミング・ビットコイン ―ゼロからビットコインをプログラムする方法 (Jimmy Song(著)、中川 卓俊(監修)、住田 和則(監修)、中村 昭雄(監修)、星野 靖子(翻訳)、オライリー・ジャパン)の2章(楕円曲線)、2.5(点の加算のコーディング)の練習問題3の解答をPythonではなくGoで求めてみる。

コード

ecc.go

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

import "fmt"

// ここには有限体についてのコード

// Point 楕円曲線 y^2 = x^3 + Ax + B上の点
type Point struct {
	A, B     int
	Infinity bool
	X, Y     int
}

// NewPoint ...
func NewPoint(inf bool, x, y, a, b int) (Point, error) {
	if inf {
		return Point{Infinity: true, A: a, B: b}, nil
	}
	if y*y != x*x*x+a*x+b {
		return Point{}, fmt.Errorf("(%v, %v) is not on the curve", x, y)
	}
	return Point{A: a, B: b, X: x, Y: y}, nil
}

// Eq ...
func (p Point) Eq(p1 Point) bool {
	return p.X == p1.X && p.Y == p1.Y && p.A == p1.A && p.B == p1.B
}

// Ne ...
func (p Point) Ne(p1 Point) bool {
	return !p.Eq(p1)
}

// Add ...
func (p Point) Add(p1 Point) (Point, error) {
	if p.A != p1.A || p.B != p1.B {
		return Point{},
			fmt.Errorf("Points %v, %v are not on the same curve", p, p1)
	}
	if p.Infinity {
		return p1, nil
	}
	if p1.Infinity {
		return p, nil
	}
	if p.X == p1.X && p.Y != p1.Y {
		return NewPoint(true, 0, 0, p.A, p.B)
	}
	return Point{}, nil
}

ecc_test.go

package ecc

import "testing"

// 有限体についてのコード

func TestPointErr(t *testing.T) {
	_, err := NewPoint(false, -1, -2, 5, 7)
	if err == nil {
		t.Errorf("NewPoint(-1, -1, 5, 7) got (_, nil), want (_, %v)", err)
	}
}

func TestPointAdd(t *testing.T) {
	p1, _ := NewPoint(false, -1, -1, 5, 7)
	p2, _ := NewPoint(false, -1, 1, 5, 7)
	inf, _ := NewPoint(true, 0, 0, 5, 7)
	tests := []struct {
		p1, p2, want Point
	}{
		{p1, p2, inf},
	}
	for _, test := range tests {
		got, _ := test.p1.Add(test.p2)
		if got.Ne(test.want) {
			t.Errorf("%v.Add(%v) got %v, want %v", p1, p2, got, test.want)
		}
	}
}

入出力結果

 % go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:119:12: too many arguments in call to NewPoint
	have (bool, number, number, number, number)
	want (int, int, int, int)
./ecc_test.go:119:12: multiple-value NewPoint() in single-value context
./ecc_test.go:120:12: too many arguments in call to NewPoint
	have (bool, number, number, number, number)
	want (int, int, int, int)
./ecc_test.go:120:12: multiple-value NewPoint() in single-value context
./ecc_test.go:121:12: too many arguments in call to NewPoint
	have (bool, number, number, number, number)
	want (int, int, int, int)
./ecc_test.go:121:12: multiple-value NewPoint() in single-value context
./ecc_test.go:125:22: test.p1.Add undefined (type Point has no field or method Add)
./ecc_test.go:127:43: undefined: p1
./ecc_test.go:127:47: undefined: p2
FAIL	bitcoin/ecc [build failed]
% go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:108:20: not enough arguments in call to NewPoint
	have (number, number, number, number)
	want (bool, int, int, int, int)
./ecc_test.go:119:12: multiple-value NewPoint() in single-value context
./ecc_test.go:120:12: multiple-value NewPoint() in single-value context
./ecc_test.go:121:12: multiple-value NewPoint() in single-value context
./ecc_test.go:125:22: test.p1.Add undefined (type Point has no field or method Add)
./ecc_test.go:127:43: undefined: p1
./ecc_test.go:127:47: undefined: p2
FAIL	bitcoin/ecc [build failed]
% go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:124:22: test.p1.Add undefined (type Point has no field or method Add)
FAIL	bitcoin/ecc [build failed]
% go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc.go:135:6: p.Infinity undefined (type Point has no field or method Infinity)
./ecc.go:138:1: missing return at end of function
FAIL	bitcoin/ecc [build failed]
% go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc.go:143:1: missing return at end of function
FAIL	bitcoin/ecc [build failed]
% go test
# bitcoin/ecc [bitcoin/ecc.test]
./ecc_test.go:124:8: err declared but not used
FAIL	bitcoin/ecc [build failed]
% go test
--- FAIL: TestPointAdd (0.00s)
    ecc_test.go:126: {5 7 false -1 -1}.Add({5 7 false -1 1}) got {0 0 false 0 0}, want {5 7 true 0 0}
FAIL
exit status 1
FAIL	bitcoin/ecc	0.369s
% go test
PASS
ok  	bitcoin/ecc	0.327s
%