From 56a59d990f865a6e40e58ee335ee2efe2c0a8a40 Mon Sep 17 00:00:00 2001 From: Clawd Date: Thu, 19 Feb 2026 20:55:43 -0800 Subject: Add Point type with addition, doubling, scalar multiplication --- point.go | 171 ++++++++++++++++++++++++++++++++++++++++++++++++++ point_test.go | 195 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 366 insertions(+) create mode 100644 point.go create mode 100644 point_test.go diff --git a/point.go b/point.go new file mode 100644 index 0000000..e8fb440 --- /dev/null +++ b/point.go @@ -0,0 +1,171 @@ +package main + +import ( + "fmt" + "math/big" +) + +// secp256k1 curve: y² = x³ + 7 +// The 'a' coefficient is 0, 'b' is 7 +var curveB = NewFieldElementFromInt64(7) + +// Generator point G for secp256k1 +var ( + Gx, _ = new(big.Int).SetString("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16) + Gy, _ = new(big.Int).SetString("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 16) + G = &Point{ + x: NewFieldElement(Gx), + y: NewFieldElement(Gy), + infinity: false, + } +) + +// Curve order (number of points on the curve) +var N, _ = new(big.Int).SetString("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16) + +// Point represents a point on the secp256k1 curve +type Point struct { + x, y *FieldElement + infinity bool // true if this is the point at infinity (identity) +} + +// NewPoint creates a point from x, y coordinates +// Returns error if the point is not on the curve +func NewPoint(x, y *FieldElement) (*Point, error) { + p := &Point{x: x, y: y, infinity: false} + if !p.IsOnCurve() { + return nil, fmt.Errorf("point (%s, %s) is not on the curve", x.String(), y.String()) + } + return p, nil +} + +// Infinity returns the point at infinity (identity element) +func Infinity() *Point { + return &Point{infinity: true} +} + +// IsInfinity returns true if this is the point at infinity +func (p *Point) IsInfinity() bool { + return p.infinity +} + +// IsOnCurve checks if the point satisfies y² = x³ + 7 +func (p *Point) IsOnCurve() bool { + if p.infinity { + return true + } + // y² = x³ + 7 + left := p.y.Square() // y² + right := p.x.Square().Mul(p.x).Add(curveB) // x³ + 7 + return left.Equal(right) +} + +// Equal checks if two points are the same +func (p *Point) Equal(q *Point) bool { + if p.infinity && q.infinity { + return true + } + if p.infinity || q.infinity { + return false + } + return p.x.Equal(q.x) && p.y.Equal(q.y) +} + +// Add returns p + q using the elliptic curve addition formulas +func (p *Point) Add(q *Point) *Point { + // Handle infinity (identity element) + if p.infinity { + return q + } + if q.infinity { + return p + } + + // If points are inverses (same x, opposite y), return infinity + if p.x.Equal(q.x) && !p.y.Equal(q.y) { + return Infinity() + } + + // If points are the same, use doubling formula + if p.Equal(q) { + return p.Double() + } + + // Standard addition formula for P ≠ Q: + // slope = (y2 - y1) / (x2 - x1) + // x3 = slope² - x1 - x2 + // y3 = slope * (x1 - x3) - y1 + + slope := q.y.Sub(p.y).Div(q.x.Sub(p.x)) + x3 := slope.Square().Sub(p.x).Sub(q.x) + y3 := slope.Mul(p.x.Sub(x3)).Sub(p.y) + + return &Point{x: x3, y: y3, infinity: false} +} + +// Double returns 2P (point added to itself) +func (p *Point) Double() *Point { + if p.infinity { + return Infinity() + } + + // If y = 0, tangent is vertical, return infinity + if p.y.IsZero() { + return Infinity() + } + + // Doubling formula: + // slope = (3x² + a) / (2y) -- for secp256k1, a = 0 + // x3 = slope² - 2x + // y3 = slope * (x - x3) - y + + three := NewFieldElementFromInt64(3) + two := NewFieldElementFromInt64(2) + + slope := three.Mul(p.x.Square()).Div(two.Mul(p.y)) + x3 := slope.Square().Sub(two.Mul(p.x)) + y3 := slope.Mul(p.x.Sub(x3)).Sub(p.y) + + return &Point{x: x3, y: y3, infinity: false} +} + +// ScalarMul returns k * P (point multiplied by scalar) +// Uses double-and-add algorithm +func (p *Point) ScalarMul(k *big.Int) *Point { + result := Infinity() + addend := p + + // Clone k so we don't modify the original + scalar := new(big.Int).Set(k) + + for scalar.Sign() > 0 { + // If lowest bit is 1, add current addend + if scalar.Bit(0) == 1 { + result = result.Add(addend) + } + // Double the addend + addend = addend.Double() + // Shift scalar right by 1 + scalar.Rsh(scalar, 1) + } + + return result +} + +// Negate returns -P (same x, negated y) +func (p *Point) Negate() *Point { + if p.infinity { + return Infinity() + } + // -y mod P + negY := NewFieldElement(new(big.Int).Sub(P, p.y.value)) + return &Point{x: p.x.Clone(), y: negY, infinity: false} +} + +// String returns a readable representation +func (p *Point) String() string { + if p.infinity { + return "Point(infinity)" + } + return fmt.Sprintf("Point(%s, %s)", p.x.String()[:8]+"...", p.y.String()[:8]+"...") +} diff --git a/point_test.go b/point_test.go new file mode 100644 index 0000000..ba12977 --- /dev/null +++ b/point_test.go @@ -0,0 +1,195 @@ +package main + +import ( + "math/big" + "testing" +) + +func TestGeneratorIsOnCurve(t *testing.T) { + if !G.IsOnCurve() { + t.Error("generator point G should be on the curve") + } +} + +func TestInfinityIsOnCurve(t *testing.T) { + inf := Infinity() + if !inf.IsOnCurve() { + t.Error("point at infinity should be considered on curve") + } +} + +func TestPointNotOnCurve(t *testing.T) { + // (1, 1) is not on y² = x³ + 7 + // y² = 1, x³ + 7 = 8, so 1 ≠ 8 + x := NewFieldElementFromInt64(1) + y := NewFieldElementFromInt64(1) + _, err := NewPoint(x, y) + if err == nil { + t.Error("(1, 1) should not be on the curve") + } +} + +func TestAddInfinity(t *testing.T) { + inf := Infinity() + + // G + infinity = G + result := G.Add(inf) + if !result.Equal(G) { + t.Error("G + infinity should equal G") + } + + // infinity + G = G + result = inf.Add(G) + if !result.Equal(G) { + t.Error("infinity + G should equal G") + } + + // infinity + infinity = infinity + result = inf.Add(inf) + if !result.IsInfinity() { + t.Error("infinity + infinity should be infinity") + } +} + +func TestAddInverseGivesInfinity(t *testing.T) { + // G + (-G) = infinity + negG := G.Negate() + result := G.Add(negG) + if !result.IsInfinity() { + t.Error("G + (-G) should be infinity") + } +} + +func TestDoubleGenerator(t *testing.T) { + // 2G should be on the curve + twoG := G.Double() + if !twoG.IsOnCurve() { + t.Error("2G should be on the curve") + } + + // 2G should not be infinity + if twoG.IsInfinity() { + t.Error("2G should not be infinity") + } + + // 2G should not equal G + if twoG.Equal(G) { + t.Error("2G should not equal G") + } +} + +func TestAddEqualsDouble(t *testing.T) { + // G + G should equal G.Double() + sum := G.Add(G) + doubled := G.Double() + if !sum.Equal(doubled) { + t.Error("G + G should equal 2G") + } +} + +func TestScalarMulByOne(t *testing.T) { + // 1 * G = G + one := big.NewInt(1) + result := G.ScalarMul(one) + if !result.Equal(G) { + t.Error("1 * G should equal G") + } +} + +func TestScalarMulByTwo(t *testing.T) { + // 2 * G = G + G + two := big.NewInt(2) + result := G.ScalarMul(two) + expected := G.Double() + if !result.Equal(expected) { + t.Error("2 * G should equal G.Double()") + } +} + +func TestScalarMulByThree(t *testing.T) { + // 3 * G = G + G + G + three := big.NewInt(3) + result := G.ScalarMul(three) + expected := G.Double().Add(G) + if !result.Equal(expected) { + t.Error("3 * G should equal 2G + G") + } + + // Result should be on curve + if !result.IsOnCurve() { + t.Error("3G should be on the curve") + } +} + +func TestScalarMulByN(t *testing.T) { + // N * G = infinity (curve order) + result := G.ScalarMul(N) + if !result.IsInfinity() { + t.Error("N * G should be infinity (curve order)") + } +} + +func TestScalarMulAssociative(t *testing.T) { + // (a * b) * G = a * (b * G) + a := big.NewInt(7) + b := big.NewInt(11) + ab := new(big.Int).Mul(a, b) // 77 + + left := G.ScalarMul(ab) + right := G.ScalarMul(b).ScalarMul(a) + + if !left.Equal(right) { + t.Error("scalar multiplication should be associative") + } +} + +func TestNegateOnCurve(t *testing.T) { + negG := G.Negate() + if !negG.IsOnCurve() { + t.Error("-G should be on the curve") + } +} + +func TestDoubleNegateEqualsOriginal(t *testing.T) { + // -(-G) = G + result := G.Negate().Negate() + if !result.Equal(G) { + t.Error("-(-G) should equal G") + } +} + +func TestPointEquality(t *testing.T) { + // Same point should be equal + if !G.Equal(G) { + t.Error("G should equal itself") + } + + // Different points should not be equal + twoG := G.Double() + if G.Equal(twoG) { + t.Error("G should not equal 2G") + } + + // Infinity equals infinity + inf1 := Infinity() + inf2 := Infinity() + if !inf1.Equal(inf2) { + t.Error("infinity should equal infinity") + } +} + +// Known test vector from Bitcoin +func TestKnownVector2G(t *testing.T) { + // 2G has known coordinates (verified against bitcoin wiki) + expectedX, _ := new(big.Int).SetString("C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5", 16) + expectedY, _ := new(big.Int).SetString("1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A", 16) + + twoG := G.Double() + + if twoG.x.value.Cmp(expectedX) != 0 { + t.Errorf("2G.x = %s, want %x", twoG.x.String(), expectedX) + } + if twoG.y.value.Cmp(expectedY) != 0 { + t.Errorf("2G.y = %s, want %x", twoG.y.String(), expectedY) + } +} -- cgit v1.2.3