楕円曲線 x1 ≠ x2のときの点の加算、方程式、解、係数、ヴィエトの公式、Goによるコーディング
プログラミング・ビットコイン ―ゼロからビットコインをプログラムする方法 (Jimmy Song(著)、中川 卓俊(監修)、住田 和則(監修)、中村 昭雄(監修)、星野 靖子(翻訳)、オライリー・ジャパン)の2章(楕円曲線)、2.6(x1 ≠ x2のときの点の加算)の練習問題4、2.7(x1 ≠ x2のときの点の加算のコーディング)の練習問題5の解答をPythonではなくGoで求めてみる。
4
2点
を通る直線の傾きは、
で、
なので、
5
コード
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)
}
s := (p1.Y - p.Y) / (p1.X - p.X)
x := s*s - p.X - p1.X
y := s*(p.X-x) - p.Y
return NewPoint(false, x, y, p.A, p.B)
}
ecc_test.go
package ecc
import (
"fmt"
"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, err1 := NewPoint(false, -1, -1, 5, 7)
p2, err2 := NewPoint(false, -1, 1, 5, 7)
inf, errInf := NewPoint(true, 0, 0, 5, 7)
p3, err3 := NewPoint(false, 2, 5, 5, 7)
p4, err4 := NewPoint(false, -1, -1, 5, 7)
want1, errWant1 := NewPoint(false, 3, -7, 5, 7)
tests := []struct {
p1, p2, want Point
err1, err2, err3 error
}{
{p1, p2, inf, err1, err2, errInf},
{p3, p4, want1, err3, err4, errWant1},
}
for _, test := range tests {
flag := false
for _, err := range []error{test.err1, test.err2, test.err3} {
if err != nil {
fmt.Println(err)
flag = true
break
}
}
if flag {
break
}
got, _ := test.p1.Add(test.p2)
if got.Ne(test.want) {
t.Errorf("%v.Add(%v) got %v, want %v", test.p1, test.p2, got, test.want)
}
}
}
入出力結果
% go test
--- FAIL: TestPointAdd (0.00s)
ecc_test.go:145: {5 7 false 2 5}.Add({5 7 false -1 -1}) got {0 0 false 0 0}, want {5 7 false 3 -7}
FAIL
exit status 1
FAIL bitcoin/ecc 0.217s
% go test
--- FAIL: TestPointAdd (0.00s)
ecc_test.go:145: {5 7 false 2 5}.Add({5 7 false -1 -1}) got {0 0 false 0 0}, want {5 7 false 3 -7}
FAIL
exit status 1
FAIL bitcoin/ecc 0.276s
% go test
PASS
ok bitcoin/ecc 0.219s
%