計算機科学のブログ

楕円曲線 P1 = P2のときの点の加算、方程式、解、係数、ヴィエトの公式、特殊な場合、x軸上の点、無限遠点、Goによるコーディング

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

6

s = 3 ( - 1 ) 2 + 5 2 ( - 1 ) = 8 - 2 = - 4 x 3 = s 2 - 2 ( - 1 ) = 16 + 2 = 18 y 3 = s ( - 1 - x 3 ) - ( - 1 ) = - 4 ( - 1 - 18 ) + 1 = 77

よって、

( - 1 , - 1 ) + ( - 1 , - 1 ) = ( 18 , 77 )

楕円曲線、点(-1, -1)における直線(接線)を描画してみる。

コード(Wolfram Language)

ContourPlot[
    {y^2 == x^3 + 5 x + 7,
     y == -4(x+1)-1},
    {x, -2, 20},
    {y, -80, 80}
]
Output

7

コード

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)
	}
	if p.Eq(p1) && p.Y == 0 {
		return NewPoint(true, 0, 0, p.A, p.B)
	}
	if p.Eq(p1) {
		s := (3*p.X*p.X + p.A) / (2 * p.Y)
		x := s*s - 2*p.X
		y := s*(p.X-x) - p.Y
		return NewPoint(false, x, y, 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)
	p5, err5 := NewPoint(false, -1, -1, 5, 7)
	want5, errWant5 := NewPoint(false, 18, 77, 5, 7)
	p6, err6 := NewPoint(false, 2, 0, 5, -18)
	want6, errWant6 := NewPoint(true, 0, 0, 5, -18)
	tests := []struct {
		p1, p2, want     Point
		err1, err2, err3 error
	}{
		{p1, p2, inf, err1, err2, errInf},
		{p3, p4, want1, err3, err4, errWant1},
		{p5, p5, want5, err5, err5, errWant5},
		{p6, p6, want6, err6, err6, errWant6},
	}
	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)
panic: runtime error: integer divide by zero [recovered]
	panic: runtime error: integer divide by zero

goroutine 14 [running]:
testing.tRunner.func1.1(0x1125f40, 0x1222420)
	/opt/local/lib/go/src/testing/testing.go:1072 +0x30d
testing.tRunner.func1(0xc000106180)
	/opt/local/lib/go/src/testing/testing.go:1075 +0x41a
panic(0x1125f40, 0x1222420)
	/opt/local/lib/go/src/runtime/panic.go:969 +0x1b9
bitcoin/ecc.Point.Add(0x5, 0x7, 0x0, 0xffffffffffffffff, 0xffffffffffffffff, 0x5, 0x7, 0x0, 0xffffffffffffffff, 0xffffffffffffffff, ...)
	/.../go/src/bitcoin/ecc/ecc.go:149 +0x4b1
bitcoin/ecc.TestPointAdd(0xc000106180)
	/.../go/src/bitcoin/ecc/ecc_test.go:146 +0x82e
testing.tRunner(0xc000106180, 0x1151ad0)
	/opt/local/lib/go/src/testing/testing.go:1123 +0xef
created by testing.(*T).Run
	/opt/local/lib/go/src/testing/testing.go:1168 +0x2b3
exit status 2
FAIL	bitcoin/ecc	0.092s
% go test
--- FAIL: TestPointAdd (0.00s)
    ecc_test.go:148: {5 7 false -1 -1}.Add({5 7 false -1 -1}) got {0 0 false 0 0}, want {5 7 false 18 77}
FAIL
exit status 1
FAIL	bitcoin/ecc	0.271s
% go test
PASS
ok  	bitcoin/ecc	0.211s
% go test
(0, 2) is not on the curve
PASS
ok  	bitcoin/ecc	0.294s
% go test
--- FAIL: TestPointAdd (0.00s)
panic: runtime error: integer divide by zero [recovered]
	panic: runtime error: integer divide by zero

goroutine 26 [running]:
testing.tRunner.func1.1(0x1126360, 0x1223420)
	/opt/local/lib/go/src/testing/testing.go:1072 +0x30d
testing.tRunner.func1(0xc000083380)
	/opt/local/lib/go/src/testing/testing.go:1075 +0x41a
panic(0x1126360, 0x1223420)
	/opt/local/lib/go/src/runtime/panic.go:969 +0x1b9
bitcoin/ecc.Point.Add(0x5, 0xffffffffffffffee, 0x0, 0x2, 0x0, 0x5, 0xffffffffffffffee, 0x0, 0x2, 0x0, ...)
	/.../go/src/bitcoin/ecc/ecc.go:150 +0x6ca
bitcoin/ecc.TestPointAdd(0xc000083380)
	/.../go/src/bitcoin/ecc/ecc_test.go:149 +0xa2e
testing.tRunner(0xc000083380, 0x1151ef0)
	/opt/local/lib/go/src/testing/testing.go:1123 +0xef
created by testing.(*T).Run
	/opt/local/lib/go/src/testing/testing.go:1168 +0x2b3
exit status 2
FAIL	bitcoin/ecc	0.220s
% go test
PASS
ok  	bitcoin/ecc	0.269s
%