Elliptic Curve Cryptography1

[mo-c-h]

package ellipticcrypto

import (
"crypto/rand"
"math/big"
)

// Point represents a point on an elliptic curve
type Point struct {
X, Y *big.Int
}

// EllipticCurve represents the parameters of an elliptic curve
type EllipticCurve struct {
A, B, P, N *big.Int
G Point
}

// NewEllipticCurve creates a new elliptic curve with given parameters
func NewEllipticCurve(a, b, p, n *big.Int, gx, gy *big.Int) *EllipticCurve {
return &EllipticCurve{
A: a,
B: b,
P: p,
N: n,
G: Point{X: gx, Y: gy},
}
}

// IsOnCurve checks if a point satisfies the curve equation y^2 = x^3 + ax + b (mod p)
func (ec *EllipticCurve) IsOnCurve(p Point) bool {
if p.X == nil || p.Y == nil {
return false
}

// Compute left side: y^2 mod p
left := new(big.Int).Mul(p.Y, p.Y)
left.Mod(left, ec.P)

// Compute right side: x^3 + ax + b mod p
right := new(big.Int).Exp(p.X, big.NewInt(3), ec.P)

ax := new(big.Int).Mul(ec.A, p.X)
ax.Mod(ax, ec.P)
right.Add(right, ax)

right.Add(right, ec.B)
right.Mod(right, ec.P)

return left.Cmp(right) == 0

}

// PointAdd performs point addition on the elliptic curve
func (ec *EllipticCurve) PointAdd(p1, p2 Point) Point {
// Handle point at infinity
if p1.X == nil {
return p2
}
if p2.X == nil {
return p1
}

// If points are inverses, return point at infinity
if p1.X.Cmp(p2.X) == 0 && p1.Y.Cmp(new(big.Int).Neg(p2.Y)) == 0 {
	return Point{nil, nil}
}

var m *big.Int
if p1.X.Cmp(p2.X) == 0 && p1.Y.Cmp(p2.Y) == 0 {
	// Point doubling
	m = new(big.Int).Mul(big.NewInt(3), new(big.Int).Exp(p1.X, big.NewInt(2), ec.P))
	m.Add(m, ec.A)
	
	denominator := new(big.Int).Mul(big.NewInt(2), p1.Y)
	denomInverse := new(big.Int).ModInverse(denominator, ec.P)
	m.Mul(m, denomInverse)
} else {
	// Point addition
	m = new(big.Int).Sub(p2.Y, p1.Y)
	denominator := new(big.Int).Sub(p2.X, p1.X)
	denomInverse := new(big.Int).ModInverse(denominator, ec.P)
	m.Mul(m, denomInverse)
}

m.Mod(m, ec.P)

// Compute new point coordinates
x3 := new(big.Int).Exp(m, big.NewInt(2), ec.P)
x3.Sub(x3, p1.X)
x3.Sub(x3, p2.X)
x3.Mod(x3, ec.P)

y3 := new(big.Int).Sub(p1.X, x3)
y3.Mul(y3, m)
y3.Sub(y3, p1.Y)
y3.Mod(y3, ec.P)

return Point{X: x3, Y: y3}

}

// ScalarMult performs scalar multiplication of a point
func (ec *EllipticCurve) ScalarMult(k *big.Int, p Point) Point {
result := Point{nil, nil}
addend := p

for k.Cmp(big.NewInt(0)) > 0 {
	if new(big.Int).Mod(k, big.NewInt(2)).Cmp(big.NewInt(1)) == 0 {
		result = ec.PointAdd(result, addend)
	}
	addend = ec.PointAdd(addend, addend)
	k.Div(k, big.NewInt(2))
}

return result

}

// GenerateKeyPair generates a private and public key pair
func (ec *EllipticCurve) GenerateKeyPair() (*big.Int, Point) {
// Generate private key
privateKey, err := rand.Int(rand.Reader, ec.N)
if err != nil {
panic(err)
}

// Compute public key
publicKey := ec.ScalarMult(privateKey, ec.G)

return privateKey, publicKey

}

// ECDH performs Elliptic Curve Diffie-Hellman key exchange
func (ec *EllipticCurve) ECDH(privateKey *big.Int, publicKey Point) Point {
return ec.ScalarMult(privateKey, publicKey)
}