Add Point type with addition, doubling, scalar multiplication

2 files changed, 366 insertions, 0 deletions

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)
+        }
+}