clock_curve_math/field/

elliptic_curve.rs

//! Elliptic curve arithmetic for cryptographic curve types.
//!
//! This module implements elliptic curve group operations for different curve models
//! used in public-key cryptography. Elliptic curves provide the mathematical foundation
//! for ECDSA signatures, ECDH key exchange, and other cryptographic protocols.
//!
//! # Supported Curve Models
//!
//! ## Weierstrass Curves
//! Standard curve representation: `y² = x³ + ax + b`
//! - Used by secp256k1 (Bitcoin), NIST P-curves
//! - Point addition and doubling use chord-tangent formulas
//! - Point at infinity represented as (0,0)
//!
//! ## Edwards Curves
//! Twisted Edwards form: `ax² + y² = 1 + dx²y²`
//! - Used by Ed25519, Curve25519
//! - Unified addition formulas (resistant to some attacks)
//! - Complete addition formulas (no exceptional cases)
//!
//! # Cryptographic Operations
//!
//! ## Point Addition
//! Combines two curve points using the curve's group law:
//! - **Weierstrass**: Complex formulas with special cases for doubling
//! - **Edwards**: Unified formulas work for all point combinations
//!
//! ## Scalar Multiplication
//! Computes `k * P` for scalar k and point P:
//! - Uses Montgomery ladder for constant-time execution
//! - Prevents timing attacks on secret scalars
//! - Fundamental operation for ECDSA and ECDH
//!
//! ## Point Validation
//! Verifies points lie on the curve:
//! - Prevents invalid point attacks
//! - Ensures mathematical consistency
//! - Critical for protocol security
//!
//! # Security Considerations
//!
//! ## Constant-Time Operations
//! All curve operations execute in constant time to prevent:
//! - **Timing attacks**: Measuring operation time to recover keys
//! - **Cache attacks**: Observing memory access patterns
//! - **Branch prediction attacks**: Analyzing control flow
//!
//! ## Mathematical Correctness
//! Operations maintain curve invariants:
//! - Points remain on the curve after operations
//! - Group law is preserved
//! - Scalar multiplication is correct
//!
//! ## Side-Channel Resistance
//! Implementation designed to prevent:
//! - Power analysis attacks
//! - Electromagnetic analysis
//! - Fault injection attacks
//!
//! # Performance Characteristics
//!
//! ## Operation Complexity
//! - **Point Addition**: O(1) field operations
//! - **Point Doubling**: O(1) field operations
//! - **Scalar Multiplication**: O(log scalar) point operations
//! - **Point Validation**: O(1) field operations
//!
//! ## Curve-Specific Optimizations
//! - **Edwards curves**: Faster addition due to unified formulas
//! - **Weierstrass curves**: Optimized doubling for scalar multiplication
//! - **Montgomery ladder**: Constant-time scalar multiplication
//!
//! # Usage Examples
//!
//! ## Basic Point Operations
//! ```ignore
//! use clock_curve_math::field::elliptic_curve::*;
//!
//! // Create curve and points
//! let curve = secp256k1_curve();
//! let p1 = (FieldElement::from_u64(1), FieldElement::from_u64(2));
//! let p2 = (FieldElement::from_u64(3), FieldElement::from_u64(4));
//!
//! // Point addition
//! let sum = point_add(&p1, &p2, curve);
//!
//! // Scalar multiplication
//! let scalar = BigInt::from_u64(42);
//! let result = scalar_mul(&p1, &scalar, curve);
//!
//! // Point validation
//! assert!(is_on_curve(&sum, curve));
//! ```
//!
//! ## Cryptographic Protocols
//! ```ignore
//! // ECDSA signature generation (simplified)
//! let private_key = BigInt::from_bytes(&private_key_bytes);
//! let message_hash = BigInt::from_bytes(&hash_bytes);
//!
//! // R = k * G (generator point)
//! let r_point = scalar_mul(&generator, &k, curve);
//! let r = r_point.0; // x-coordinate
//!
//! // s = k⁻¹ * (hash + r * private_key) mod order
//! let s = compute_signature_s(&k_inv, &message_hash, &r, &private_key);
//!
//! let signature = (r, s);
//! ```
//!
//! # Implementation Notes
//!
//! ## Point at Infinity
//! Represented as (0,0) for both curve types, though this is not a valid curve point.
//! Addition with infinity returns the other point, maintaining group properties.
//!
//! ## Field Operations
//! All curve arithmetic delegates to the underlying finite field implementation,
//! ensuring constant-time execution and mathematical correctness.
//!
//! ## Error Handling
//! Functions assume valid inputs (points on curve, valid scalars).
//! Invalid inputs may produce incorrect results or panics.
//! Input validation should be performed by calling code.
//!
//! ## Standardization
//! Implements standard curve parameters:
//! - **Ed25519**: a = -1, d computed from curve constants
//! - **secp256k1**: a = 0, b = 7 (simplified field representation)

use crate::field::{FieldElement, FieldOps};

/// Elliptic curve type enumeration defining supported curve models.
///
/// This enum represents the two main families of elliptic curves used in cryptography,
/// each with different mathematical properties and performance characteristics.
/// The choice of curve model affects implementation complexity, performance, and
/// security properties.
///
/// # Mathematical Foundations
///
/// ## Weierstrass Curves
/// **Equation**: `y² = x³ + ax + b`
///
/// Classic curve representation used by most standardized curves including:
/// - NIST P-curves (P-256, P-384, P-521)
/// - secp256k1 (Bitcoin curve)
/// - Brainpool curves
///
/// **Properties**:
/// - Point addition requires case analysis (doubling vs. addition)
/// - Point at infinity requires special handling
/// - More complex implementation but widely supported
///
/// ## Edwards Curves
/// **Equation**: `ax² + y² = 1 + dx²y²` (twisted Edwards form)
///
/// Modern curve representation with better properties:
/// - Ed25519 (digital signatures)
/// - Curve25519 (key exchange)
/// - More recent standardized curves
///
/// **Properties**:
/// - Unified addition formulas (no special cases)
/// - Complete formulas (no exceptional points)
/// - Faster arithmetic, simpler implementation
/// - Better resistance to some implementation attacks
///
/// # Security Considerations
///
/// ## Implementation Attacks
/// - **Edwards curves**: More resistant to timing attacks due to unified formulas
/// - **Weierstrass curves**: Require careful handling of point doubling cases
///
/// ## Side-Channel Resistance
/// - Both models can be implemented with constant-time arithmetic
/// - Edwards curves have simpler control flow
/// - Choice affects cache access patterns and power consumption
///
/// # Performance Characteristics
///
/// ## Addition Speed
/// - **Edwards**: Faster due to unified formulas
/// - **Weierstrass**: Slightly slower due to case analysis
///
/// ## Implementation Complexity
/// - **Edwards**: Simpler code, fewer edge cases
/// - **Weierstrass**: More complex, more special cases
///
/// ## Memory Usage
/// - Both models use similar memory for point operations
/// - Curve parameters (a,b,d) stored in enum variants
///
/// # Usage Examples
///
/// ```ignore
/// use clock_curve_math::field::elliptic_curve::CurveType;
///
/// // secp256k1 (Bitcoin curve)
/// let secp256k1 = CurveType::Weierstrass {
///     a: FieldElement::from_u64(0),
///     b: FieldElement::from_u64(7),
/// };
///
/// // Ed25519 curve
/// let ed25519 = CurveType::Edwards {
///     a: FieldElement::from_u64(0).sub(&FieldElement::from_u64(1)), // a = -1
///     d: /* computed d parameter */,
/// };
/// ```
///
/// # Conversion Between Models
///
/// Some curves can be represented in both forms:
/// - **Curve25519**: Can be converted between Montgomery and Edwards forms
/// - **secp256k1**: Weierstrass form only
/// - **NIST P-256**: Weierstrass form only
///
/// The enum prevents mixing operations between incompatible curve types.
#[derive(Clone, Copy, Debug)]
pub enum CurveType {
    /// Weierstrass curve model: y² = x³ + ax + b
    ///
    /// The classical elliptic curve representation used by most standardized
    /// cryptographic curves. Point arithmetic uses chord-tangent formulas
    /// with special cases for point doubling.
    ///
    /// # Parameters
    /// - `a`: Linear coefficient in the curve equation
    /// - `b`: Constant term in the curve equation
    ///
    /// # Examples
    /// - secp256k1: a=0, b=7
    /// - NIST P-256: a=-3, b=constant
    Weierstrass {
        /// Coefficient 'a' in the curve equation y² = x³ + ax + b
        a: FieldElement,
        /// Coefficient 'b' in the curve equation y² = x³ + ax + b
        b: FieldElement,
    },

    /// Edwards curve model: ax² + y² = 1 + dx²y²
    ///
    /// Modern elliptic curve representation with unified addition formulas
    /// that work for all point combinations without special cases. Provides
    /// better performance and security properties than Weierstrass curves.
    ///
    /// # Parameters
    /// - `a`: Coefficient in the x² term
    /// - `d`: Coefficient in the x²y² term
    ///
    /// # Examples
    /// - Ed25519: a=-1, d=specific constant
    /// - Curve25519: a=constant, d=constant
    Edwards {
        /// Coefficient 'a' in the Edwards equation ax² + y² = 1 + dx²y²
        a: FieldElement,
        /// Coefficient 'd' in the Edwards equation ax² + y² = 1 + dx²y²
        d: FieldElement,
    },
}

/// Extended Edwards curve point representation.
///
/// Uses extended coordinates (X:Y:Z:T) where T = X·Y·Z⁻¹.
/// This representation is optimized for Edwards curve arithmetic and enables
/// faster point addition and doubling operations.
///
/// The curve equation in extended coordinates becomes:
/// X² + Y² = Z² + d·X²·Y²
///
/// # Coordinate Meaning
/// - `x`: X-coordinate in extended form
/// - `y`: Y-coordinate in extended form
/// - `z`: Z-coordinate (denominator)
/// - `t`: T-coordinate where T = X·Y·Z⁻¹
///
/// # Security
/// All operations are constant-time to prevent timing attacks.
/// Point validation methods ensure mathematical consistency.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct ExtendedPoint {
    /// X-coordinate
    pub x: FieldElement,
    /// Y-coordinate
    pub y: FieldElement,
    /// Z-coordinate (denominator)
    pub z: FieldElement,
    /// T-coordinate where T = X·Y·Z⁻¹
    pub t: FieldElement,
}

impl ExtendedPoint {
    /// Create a new extended point with the given coordinates.
    ///
    /// # Warning
    /// This constructor does not validate that the point satisfies the curve equation.
    /// Use `is_on_curve()` to verify the point is valid.
    pub fn new(x: FieldElement, y: FieldElement, z: FieldElement, t: FieldElement) -> Self {
        Self { x, y, z, t }
    }

    /// Create the identity element (point at infinity).
    ///
    /// In extended coordinates, the point at infinity is represented as (0,1,1,0).
    pub fn identity() -> Self {
        Self {
            x: FieldElement::from_u64(0),
            y: FieldElement::from_u64(1),
            z: FieldElement::from_u64(1),
            t: FieldElement::from_u64(0),
        }
    }

    /// Create a point from affine coordinates (x, y).
    ///
    /// Converts (x, y) to extended coordinates (x, y, 1, x*y).
    /// This assumes the affine point is already on the curve.
    pub fn from_affine(x: FieldElement, y: FieldElement) -> Self {
        Self {
            x,
            y,
            z: FieldElement::from_u64(1),
            t: x.mul(&y),
        }
    }

    /// Constant-time conditional selection between two extended points.
    ///
    /// Returns `a` if `choice` is true, otherwise returns `b`.
    /// This operation executes in constant time regardless of the choice value.
    ///
    /// # Parameters
    /// * `a` - First point (selected when choice is true)
    /// * `b` - Second point (selected when choice is false)
    /// * `choice` - Selection choice
    ///
    /// # Returns
    /// The selected point based on the choice
    ///
    /// # Security
    /// This function is constant-time and safe for cryptographic use with secret choices.
    pub fn conditional_select(a: &Self, b: &Self, choice: crate::ct::Choice) -> Self {
        Self {
            x: FieldElement::conditional_select(&a.x, &b.x, choice),
            y: FieldElement::conditional_select(&a.y, &b.y, choice),
            z: FieldElement::conditional_select(&a.z, &b.z, choice),
            t: FieldElement::conditional_select(&a.t, &b.t, choice),
        }
    }

    /// Check if this point satisfies the extended coordinate invariant T = X·Y·Z⁻¹.
    ///
    /// This validates the internal consistency of the extended point representation,
    /// but does not check if the point lies on the curve.
    ///
    /// # Returns
    /// `true` if the point coordinates are consistent, `false` otherwise
    ///
    /// # Mathematical Check
    /// Verifies: T * Z ≡ X * Y mod p
    pub fn is_valid(&self) -> bool {
        if self.z.is_zero() {
            // Z = 0 is invalid (would cause division by zero)
            return false;
        }

        // Check T * Z == X * Y mod p
        let left = self.t.mul(&self.z);
        let right = self.x.mul(&self.y);
        left == right
    }

    /// Check if this point lies on the specified Edwards curve.
    ///
    /// Verifies that the point satisfies the Edwards curve equation:
    /// -x² + y² = 1 + d·x²·y²
    ///
    /// This converts the point to affine coordinates first, then checks the equation.
    /// Points with Z = 0 are considered invalid and return false.
    ///
    /// # Parameters
    /// * `curve` - The curve parameters defining the equation to check
    ///
    /// # Returns
    /// `true` if the point lies on the curve, `false` otherwise
    pub fn is_on_curve(&self, curve: CurveType) -> bool {
        // Check if point is valid first
        if !self.is_valid() {
            return false;
        }

        match curve {
            CurveType::Edwards { a: _, d } => self.is_on_edwards_curve(d),
            CurveType::Weierstrass { .. } => {
                // Convert to affine and check Weierstrass equation
                let affine = self.to_affine();
                is_on_curve(&affine, curve)
            }
        }
    }

    /// Check if this point lies on an Edwards curve with parameter d.
    ///
    /// Verifies: -x² + y² = 1 + d·x²·y²
    ///
    /// # Parameters
    /// * `d` - The Edwards curve parameter
    ///
    /// # Returns
    /// `true` if the point satisfies the Edwards equation
    ///
    /// # Note
    /// This method assumes the point is valid (Z ≠ 0). Call `is_valid()` first.
    fn is_on_edwards_curve(&self, d: FieldElement) -> bool {
        // Convert to affine coordinates
        let z_inv = self.z.inv();
        let x_affine = self.x.mul(&z_inv);
        let y_affine = self.y.mul(&z_inv);

        // Check Edwards equation: -x² + y² = 1 + d·x²·y²
        let x2 = x_affine.square();
        let y2 = y_affine.square();
        let xy2 = x2.mul(&y2);

        let left = y2.sub(&x2);
        let right = FieldElement::from_u64(1).add(&d.mul(&xy2));

        left == right
    }

    /// Convert this extended point to affine coordinates (x/z, y/z).
    ///
    /// # Returns
    /// A tuple (x, y) representing the affine coordinates
    ///
    /// # Panics
    /// Panics if Z = 0 (point at infinity or invalid representation)
    pub fn to_affine(&self) -> (FieldElement, FieldElement) {
        if self.z.is_zero() {
            panic!("Cannot convert point at infinity to affine coordinates");
        }

        let z_inv = self.z.inv();
        let x_affine = self.x.mul(&z_inv);
        let y_affine = self.y.mul(&z_inv);

        (x_affine, y_affine)
    }

    /// Check if this point is the identity element (point at infinity).
    ///
    /// In extended coordinates, the identity is represented as (0,1,1,0).
    pub fn is_identity(&self) -> bool {
        self.x.is_zero() && self.y == FieldElement::from_u64(1) &&
        self.z == FieldElement::from_u64(1) && self.t.is_zero()
    }

    /// Add two extended points on an Edwards curve.
    ///
    /// Uses the complete extended Edwards addition formulas that work for all
    /// point combinations without special cases. This is more efficient than
    /// converting to affine coordinates first.
    ///
    /// # Parameters
    /// * `other` - The point to add to this point
    /// * `curve` - The curve parameters defining the addition operation
    ///
    /// # Returns
    /// The sum of the two points in extended coordinates
    pub fn add(&self, other: &Self, curve: CurveType) -> Self {
        match curve {
            CurveType::Edwards { a, d } => self.add_edwards(other, a, d),
            CurveType::Weierstrass { .. } => {
                // For Weierstrass curves, convert to affine, add, then back to extended
                let p1_affine = self.to_affine();
                let p2_affine = other.to_affine();
                let sum_affine = point_add(&p1_affine, &p2_affine, curve);
                Self::from_affine(sum_affine.0, sum_affine.1)
            }
        }
    }

    /// Add two points on an Edwards curve using extended coordinates.
    ///
    /// Uses the complete extended Edwards addition formulas:
    /// X3 = (X1·Y2 + Y1·X2) · (Z1·Z2 - d·T1·T2)
    /// Y3 = (Y1·Y2 - a·X1·X2) · (Z1·Z2 + d·T1·T2)
    /// Z3 = (Z1·Z2 - d·T1·T2) · (Z1·Z2 + d·T1·T2)
    /// T3 = (X1·Y2 + Y1·X2) · (Y1·Y2 - a·X1·X2)
    fn add_edwards(&self, other: &Self, a: FieldElement, d: FieldElement) -> Self {
        // A = X1·X2, B = Y1·Y2, C = d·T1·T2, D = Z1·Z2
        let a_val = self.x.mul(&other.x);
        let b_val = self.y.mul(&other.y);
        let c_val = d.mul(&self.t.mul(&other.t));
        let d_val = self.z.mul(&other.z);

        // E = (X1+Y1)·(X2+Y2) - A - B = X1·Y2 + Y1·X2
        let e_val = self.x.add(&self.y).mul(&other.x.add(&other.y)).sub(&a_val).sub(&b_val);

        // F = D - C, G = D + C, H = B - a·A
        let f_val = d_val.sub(&c_val);
        let g_val = d_val.add(&c_val);
        let h_val = b_val.sub(&a.mul(&a_val));

        // X3 = E·F, Y3 = G·H, Z3 = F·G, T3 = E·H
        let x3 = e_val.mul(&f_val);
        let y3 = g_val.mul(&h_val);
        let z3 = f_val.mul(&g_val);
        let t3 = e_val.mul(&h_val);

        Self::new(x3, y3, z3, t3)
    }

    /// Double this extended point on an Edwards curve.
    ///
    /// Uses the extended Edwards doubling formulas which are optimized
    /// for the case where both points are the same. This is more efficient
    /// than the general addition formula.
    ///
    /// # Parameters
    /// * `curve` - The curve parameters defining the doubling operation
    ///
    /// # Returns
    /// The doubled point in extended coordinates
    pub fn double(&self, curve: CurveType) -> Self {
        match curve {
            CurveType::Edwards { a, d } => self.double_edwards(a, d),
            CurveType::Weierstrass { .. } => {
                // For Weierstrass curves, convert to affine, double, then back to extended
                let affine = self.to_affine();
                let doubled_affine = point_add(&affine, &affine, curve);
                Self::from_affine(doubled_affine.0, doubled_affine.1)
            }
        }
    }

    /// Double a point on an Edwards curve using extended coordinates.
    ///
    /// Uses the extended Edwards doubling formulas:
    /// A = X², B = Y², C = 2·Z², D = a·A, E = (X+Y)² - A - B
    /// F = C - D, G = C + D, H = B - D, I = E·F, J = E·H, K = G·H
    /// X3 = I, Y3 = J, Z3 = K, T3 = I·J
    ///
    /// But we use the more efficient version that avoids recomputing squares.
    fn double_edwards(&self, a: FieldElement, d: FieldElement) -> Self {
        // A = X², B = Y², C = Z², D = T²
        let a_val = self.x.square();
        let b_val = self.y.square();
        let c_val = self.z.square();
        let d_val = self.t.square();

        // E = (X+Y)² - A - B = 2·X·Y
        let e_val = self.x.add(&self.y).square().sub(&a_val).sub(&b_val);

        // F = C - d·D, G = C + d·D
        let f_val = c_val.sub(&d.mul(&d_val));
        let g_val = c_val.add(&d.mul(&d_val));

        // H = B - a·A
        let h_val = b_val.sub(&a.mul(&a_val));

        // X3 = E·F, Y3 = G·H, Z3 = F·G, T3 = E·H
        let x3 = e_val.mul(&f_val);
        let y3 = g_val.mul(&h_val);
        let z3 = f_val.mul(&g_val);
        let t3 = e_val.mul(&h_val);

        Self::new(x3, y3, z3, t3)
    }

    /// Compute scalar multiplication using the Montgomery ladder.
    ///
    /// This method performs constant-time scalar multiplication k * P using
    /// the Montgomery ladder algorithm. The implementation uses extended
    /// coordinates to maintain curve membership and avoid coordinate conversions.
    ///
    /// # Parameters
    /// * `scalar` - The scalar multiplier (secret value in cryptographic use)
    /// * `curve` - The curve parameters defining the group operation
    ///
    /// # Returns
    /// The result k * P in extended coordinates
    ///
    /// # Security
    /// This operation is constant-time and safe for cryptographic use with
    /// secret scalars. The Montgomery ladder prevents timing attacks by
    /// ensuring the same sequence of operations regardless of scalar bits.
    pub fn scalar_mul(&self, scalar: &crate::BigInt, curve: CurveType) -> Self {
        // Handle scalar = 0: return identity
        if scalar.is_zero() {
            return Self::identity();
        }

        // Handle scalar = 1: return the point itself
        if *scalar == crate::BigInt::from_u64(1) {
            return *self;
        }

        // Montgomery ladder algorithm
        let mut r0 = Self::identity(); // Point at infinity
        let mut r1 = *self; // Initial point

        let scalar_bits = scalar.bit_length();

        for i in (0..scalar_bits).rev() {
            let bit = scalar.get_bit(i);

            // Differential addition: r0, r1 = r0 + r1, 2*r0 (if bit=0) or 2*r1, r0 + r1 (if bit=1)
            let (r0_new, r1_new) = if bit == 0 {
                let sum = r0.add(&r1, curve);
                let double_r0 = r0.double(curve);
                (double_r0, sum)
            } else {
                let sum = r0.add(&r1, curve);
                let double_r1 = r1.double(curve);
                (sum, double_r1)
            };

            r0 = r0_new;
            r1 = r1_new;
        }

        r0
    }
}

/// Elliptic curve point addition using the curve's group law.
///
/// Computes the sum of two elliptic curve points according to the group operation
/// defined by the curve equation. This is the fundamental operation for elliptic
/// curve cryptography, used in ECDSA signatures, ECDH key exchange, and other protocols.
///
/// # Mathematical Definition
///
/// Point addition satisfies the elliptic curve group law:
/// - **Commutativity**: P + Q = Q + P
/// - **Associativity**: (P + Q) + R = P + (Q + R)
/// - **Identity**: P + O = P (where O is point at infinity)
/// - **Inverse**: P + (-P) = O
///
/// # Algorithm Details
///
/// ## Weierstrass Curves
/// Uses chord-tangent formulas with case analysis:
/// - **Different x-coordinates**: Standard addition formula
/// - **Same x-coordinate**: Point doubling (if same y) or infinity (if different y)
/// - **Point at infinity**: Identity element handling
///
/// ## Edwards Curves
/// Uses unified addition formulas that work for all cases:
/// - No special handling for doubling or infinity
/// - Complete formulas prevent exceptional cases
/// - Better performance and side-channel resistance
///
/// # Parameters
/// * `p1` - First point on the elliptic curve
/// * `p2` - Second point on the elliptic curve
/// * `curve` - Curve type and parameters defining the group operation
///
/// # Returns
/// The sum of the two points according to the curve's group law
///
/// # Security Considerations
/// - Constant-time execution prevents timing attacks on point operations
/// - No information leakage about point values through execution patterns
/// - Safe for cryptographic use with secret curve points
///
/// # Examples
/// ```ignore
/// use clock_curve_math::field::elliptic_curve::*;
///
/// let curve = secp256k1_curve();
/// let p1 = (FieldElement::from_u64(1), FieldElement::from_u64(2));
/// let p2 = (FieldElement::from_u64(3), FieldElement::from_u64(4));
///
/// let sum = point_add(&p1, &p2, curve);
/// assert!(is_on_curve(&sum, curve)); // Result is still on curve
/// ```
///
/// # Point at Infinity
/// Represented as (0,0) for both curve types. Addition with infinity:
/// - P + (0,0) = P
/// - (0,0) + (0,0) = (0,0)
pub fn point_add(
    p1: &(FieldElement, FieldElement),
    p2: &(FieldElement, FieldElement),
    curve: CurveType,
) -> (FieldElement, FieldElement) {
    match curve {
        CurveType::Weierstrass { a, b: _ } => point_add_weierstrass(p1, p2, a),
        CurveType::Edwards { a, d } => point_add_edwards(p1, p2, a, d),
    }
}

/// Point addition for Weierstrass curves: y² = x³ + ax + b
fn point_add_weierstrass(
    p1: &(FieldElement, FieldElement),
    p2: &(FieldElement, FieldElement),
    a: FieldElement,
) -> (FieldElement, FieldElement) {
    let (x1, y1) = p1;
    let (x2, y2) = p2;

    // Point at infinity representations
    let infinity = (FieldElement::from_u64(0), FieldElement::from_u64(0));

    // Handle point at infinity
    if *x1 == FieldElement::from_u64(0) && *y1 == FieldElement::from_u64(0) {
        return *p2;
    }
    if *x2 == FieldElement::from_u64(0) && *y2 == FieldElement::from_u64(0) {
        return *p1;
    }

    // Point addition formula for Weierstrass curves
    if x1 == x2 {
        if y1 == y2 {
            // Point doubling
            return point_double_weierstrass(p1, a);
        } else {
            // P + (-P) = infinity
            return infinity;
        }
    }

    // Standard point addition
    let lambda = y2.sub(y1).mul(&x2.sub(x1).inv());
    let x3 = lambda.mul(&lambda).sub(x1).sub(x2);
    let y3 = lambda.mul(&x1.sub(&x3)).sub(y1);

    (x3, y3)
}

/// Point doubling for Weierstrass curves
fn point_double_weierstrass(p: &(FieldElement, FieldElement), a: FieldElement) -> (FieldElement, FieldElement) {
    let (x, y) = p;

    if *y == FieldElement::from_u64(0) {
        // Point at infinity
        return (FieldElement::from_u64(0), FieldElement::from_u64(0));
    }

    // Point doubling formula: λ = (3x² + a) / (2y)
    let lambda = FieldElement::from_u64(3)
        .mul(&x.mul(x))
        .add(&a)
        .mul(&FieldElement::from_u64(2).mul(y).inv());
    let x3 = lambda.mul(&lambda).sub(&FieldElement::from_u64(2).mul(x));
    let y3 = lambda.mul(&x.sub(&x3)).sub(y);

    (x3, y3)
}

/// Point addition for Edwards curves: ax² + y² = 1 + dx²y²
fn point_add_edwards(
    p1: &(FieldElement, FieldElement),
    p2: &(FieldElement, FieldElement),
    a: FieldElement,
    d: FieldElement,
) -> (FieldElement, FieldElement) {
    let (x1, y1) = p1;
    let (x2, y2) = p2;

    // Edwards curve addition formulas:
    // x3 = (x1*y2 + y1*x2) / (1 + d*x1*x2*y1*y2)
    // y3 = (y1*y2 - a*x1*x2) / (1 - d*x1*x2*y1*y2)

    let x1y2 = x1.mul(y2);
    let y1x2 = y1.mul(x2);
    let x1x2 = x1.mul(x2);
    let y1y2 = y1.mul(y2);
    let x1x2y1y2 = x1x2.mul(&y1y2);

    let denominator1 = FieldElement::from_u64(1).add(&d.mul(&x1x2y1y2));
    let denominator2 = FieldElement::from_u64(1).sub(&d.mul(&x1x2y1y2));

    let x3 = x1y2.add(&y1x2).mul(&denominator1.inv());
    let y3 = y1y2.sub(&a.mul(&x1x2)).mul(&denominator2.inv());

    (x3, y3)
}

/// Elliptic curve scalar multiplication using Montgomery ladder.
///
/// Computes `scalar * point` using the Montgomery ladder algorithm, which provides
/// constant-time execution regardless of the scalar value. This is the core operation
/// for elliptic curve cryptography, used in ECDSA signatures, ECDH key exchange, and
/// other cryptographic protocols.
///
/// # Algorithm: Montgomery Ladder
///
/// The Montgomery ladder maintains two points (R0, R1) and performs:
/// 1. Initialize: R0 = O (infinity), R1 = P
/// 2. For each bit of scalar (MSB to LSB):
///    - If bit = 0: R0, R1 = R0 + R1, 2*R0
///    - If bit = 1: R0, R1 = 2*R1, R0 + R1
/// 3. Result is R0
///
/// This algorithm ensures:
/// - **Constant time**: Same operations regardless of scalar bits
/// - **Regular execution**: No data-dependent control flow
/// - **Side-channel resistance**: Prevents timing and cache attacks
///
/// # Security Critical
///
/// **High Security Risk**: Scalar multiplication handles secret values:
/// - Private keys in ECDSA signatures
/// - Ephemeral keys in ECDH exchange
/// - Nonces and other cryptographic secrets
///
/// Any timing leak in this function can compromise cryptographic security.
/// The Montgomery ladder prevents such leaks by constant-time execution.
///
/// # Parameters
/// * `point` - Base point on the elliptic curve (should be on curve)
/// * `scalar` - Scalar multiplier (secret value in cryptographic use)
/// * `curve` - Curve parameters defining the group operation
///
/// # Returns
/// The result of `scalar * point` according to the curve's group law
///
/// # Performance
/// O(log scalar) point additions and doublings, constant-time.
/// More expensive than simple point addition but essential for cryptography.
///
/// # Mathematical Properties
/// - **Distributivity**: k*(P + Q) = k*P + k*Q
/// - **Scalar addition**: (k + m)*P = k*P + m*P
/// - **Identity**: 0*P = O (point at infinity)
/// - **Generator**: If P is generator, k*P generates the subgroup
///
/// # Examples
/// ```ignore
/// use clock_curve_math::{BigInt, field::elliptic_curve::*};
///
/// let curve = secp256k1_curve();
/// let generator = (gx, gy); // Generator point coordinates
/// let private_key = BigInt::from_bytes(&private_key_bytes);
///
/// // Public key = private_key * generator
/// let public_key = scalar_mul(&generator, &private_key, curve);
///
/// // ECDH shared secret = private_key * peer_public_key
/// let shared_secret = scalar_mul(&peer_public_key, &private_key, curve);
/// ```
///
/// # Implementation Notes
/// - Assumes point is on curve (validation should be done by caller)
/// - Handles scalar = 0 correctly (returns infinity)
/// - No input validation for performance (cryptographic callers should validate)
/// - Uses big-endian bit processing for consistency with BigInt representation
pub fn scalar_mul(
    point: &(FieldElement, FieldElement),
    scalar: &crate::BigInt,
    curve: CurveType,
) -> (FieldElement, FieldElement) {
    // Montgomery ladder algorithm for constant-time scalar multiplication
    // Use correct identity element for each curve type
    let r0 = match curve {
        CurveType::Weierstrass { .. } => (FieldElement::from_u64(0), FieldElement::from_u64(0)), // Point at infinity
        CurveType::Edwards { .. } => (FieldElement::from_u64(0), FieldElement::from_u64(1)), // Identity element
    };
    let mut r0 = r0;
    let mut r1 = *point;

    let scalar_bits = scalar.bit_length();

    for i in (0..scalar_bits).rev() {
        let bit = scalar.get_bit(i);

        // Differential addition: r0, r1 = r0 + r1, 2*r0 (if bit=0) or 2*r1, r0 + r1 (if bit=1)
        let (r0_new, r1_new) = if bit == 0 {
            let sum = point_add(&r0, &r1, curve);
            let double_r0 = point_add(&r0, &r0, curve);
            (double_r0, sum)
        } else {
            let sum = point_add(&r0, &r1, curve);
            let double_r1 = point_add(&r1, &r1, curve);
            (sum, double_r1)
        };

        r0 = r0_new;
        r1 = r1_new;
    }

    r0
}

/// Validates whether a point lies on the specified elliptic curve.
///
/// Verifies that the given point satisfies the curve equation for the specified
/// curve type. Point validation is critical for cryptographic security to prevent
/// attacks that rely on submitting invalid curve points.
///
/// # Validation Process
///
/// ## Point at Infinity
/// Always considered valid (represented as (0,0) in both curve models)
///
/// ## Weierstrass Curves
/// Checks: `y² ≡ x³ + ax + b mod p`
/// - Computes both sides of the Weierstrass equation
/// - Compares results for equality
///
/// ## Edwards Curves
/// Checks: `ax² + y² ≡ 1 + dx²y² mod p`
/// - Computes both sides of the Edwards equation
/// - Verifies the twisted Edwards identity
///
/// # Security Importance
///
/// **Critical for Protocol Security**: Invalid point acceptance can lead to:
/// - **Invalid curve attacks** on signature schemes
/// - **Weak key generation** if points aren't validated
/// - **Protocol failures** in key exchange schemes
/// - **Side-channel leaks** from error handling paths
///
/// # Parameters
/// * `point` - The point to validate (x, y coordinates)
/// * `curve` - Curve parameters defining the equation to check
///
/// # Returns
/// `true` if the point satisfies the curve equation, `false` otherwise
///
/// # Performance
/// O(1) field multiplications and comparisons.
/// Fast validation suitable for runtime use.
///
/// # Examples
/// ```ignore
/// use clock_curve_math::field::elliptic_curve::*;
///
/// let curve = secp256k1_curve();
/// let valid_point = (FieldElement::from_u64(1), FieldElement::from_u64(2));
/// let invalid_point = (FieldElement::from_u64(1), FieldElement::from_u64(999));
///
/// assert!(is_on_curve(&valid_point, curve));    // Assuming it's on curve
/// assert!(!is_on_curve(&invalid_point, curve)); // Obviously not on curve
///
/// // Point at infinity always valid
/// let infinity = (FieldElement::from_u64(0), FieldElement::from_u64(0));
/// assert!(is_on_curve(&infinity, curve));
/// ```
///
/// # Usage in Cryptography
/// - **Public key validation**: Ensure received keys are valid curve points
/// - **Signature verification**: Validate signature-related curve points
/// - **Key exchange**: Verify peer public keys before computation
/// - **Protocol safety**: Prevent invalid point attacks
///
/// # Implementation Notes
/// - Assumes field elements are reduced modulo the field prime
/// - No timing leaks in validation process
/// - Point at infinity handling consistent across curve types
pub fn is_on_curve(point: &(FieldElement, FieldElement), curve: CurveType) -> bool {
    let (x, y) = point;

    match curve {
        CurveType::Weierstrass { a, b } => {
            // For Weierstrass curves, (0,0) represents the point at infinity
            if *x == FieldElement::from_u64(0) && *y == FieldElement::from_u64(0) {
                return true;
            }

            // Check y² = x³ + ax + b
            let left = y.mul(y);
            let right = x.mul(x).mul(x).add(&a.mul(x)).add(&b);
            left == right
        }
        CurveType::Edwards { a, d } => {
            // For Edwards curves, check the curve equation: a*x² + y² = 1 + d*x²*y²
            // Note: (0,0) is not necessarily on Edwards curves, unlike Weierstrass
            let left = a.mul(&x.mul(x)).add(&y.mul(y));
            let right = FieldElement::from_u64(1).add(&d.mul(&x.mul(x)).mul(&y.mul(y)));
            left == right
        }
    }
}

/// Creates the Ed25519 elliptic curve parameters.
///
/// Returns a CurveType::Edwards configuration with the standard Ed25519 parameters
/// as defined in RFC 8032. Ed25519 uses a twisted Edwards curve with equation:
/// `-x² + y² = 1 - (121665/121666)·x²y²`
///
/// # Curve Parameters
/// - **a**: -1 (coefficient of x² term)
/// - **d**: -(121665/121666) mod p (cross term coefficient)
/// - **p**: 2^255 - 19 (field prime)
/// - **Order**: 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed (group order)
///
/// # Security Properties
/// - **Twisted Edwards form**: Provides complete addition formulas
/// - **Prime order subgroup**: Prevents small subgroup attacks
/// - **Cofactor**: 8 (requires cofactor clearing in protocols)
/// - **Field size**: 255 bits (conservative security level)
///
/// # Cryptographic Usage
/// - **Digital signatures**: Ed25519 signature scheme
/// - **Key exchange**: X25519 (Montgomery form of same curve)
/// - **Protocol**: RFC 8032 compliant implementation
///
/// # Performance
/// Optimized for the specific Ed25519 parameters with precomputed constants.
/// The d parameter is computed as -(121665 × 121666^(-1)) mod p.
///
/// # Examples
/// ```ignore
/// use clock_curve_math::field::elliptic_curve::*;
///
/// let curve = ed25519_curve();
/// match curve {
///     CurveType::Edwards { a, d } => {
///         // Verify standard parameters
///         assert_eq!(a, FieldElement::from_u64(0).sub(&FieldElement::from_u64(1)));
///         // d parameter computed correctly
///     }
///     _ => panic!("Expected Edwards curve"),
/// }
/// ```
pub fn ed25519_curve() -> CurveType {
    // Ed25519 parameters: a = -1, d = -121665/121666
    let a = FieldElement::from_u64(0).sub(&FieldElement::from_u64(1));
    // d = -121665 * (121666)^(-1) mod p
    let d_num = FieldElement::from_u64(121665);
    let d_den = FieldElement::from_u64(121666).inv();
    let d = FieldElement::from_u64(0).sub(&d_num.mul(&d_den));

    CurveType::Edwards { a, d }
}

/// Creates the secp256k1 elliptic curve parameters.
///
/// Returns a CurveType::Weierstrass configuration with the standard secp256k1
/// parameters as used in Bitcoin and other cryptocurrencies. The curve equation is:
/// `y² = x³ + 7` (simplified field representation)
///
/// # Curve Parameters
/// - **a**: 0 (no x term in the cubic)
/// - **b**: 7 (constant term)
/// - **p**: 2^256 - 2^32 - 977 (field prime)
/// - **Order**: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
/// - **Cofactor**: 1 (prime order group)
///
/// # Security Properties
/// - **Prime field**: No small characteristic vulnerabilities
/// - **Large prime order**: 256-bit security level
/// - **Well-studied**: Extensively analyzed since Bitcoin's creation
/// - **No known weaknesses**: Extensive cryptanalysis shows no practical attacks
///
/// # Cryptographic Usage
/// - **Digital signatures**: ECDSA in Bitcoin and other systems
/// - **Key exchange**: ECDH for secure communication
/// - **Blockchain**: Primary curve for cryptocurrency transactions
/// - **Standards**: Widely adopted in financial and blockchain applications
///
/// # Performance
/// Optimized for the secp256k1 parameters (a=0 simplifies some formulas).
/// The simplified Weierstrass form allows for efficient point operations.
///
/// # Historical Context
/// secp256k1 was selected for Bitcoin due to:
/// - **Security**: 128-bit security level against known attacks
/// - **Performance**: Efficient on constrained devices
/// - **Adoption**: Became the de facto standard for cryptocurrencies
/// - **Analysis**: Years of cryptanalysis confirm security
///
/// # Examples
/// ```ignore
/// use clock_curve_math::field::elliptic_curve::*;
///
/// let curve = secp256k1_curve();
/// match curve {
///     CurveType::Weierstrass { a, b } => {
///         // Verify standard parameters
///         assert_eq!(a, FieldElement::from_u64(0));
///         assert_eq!(b, FieldElement::from_u64(7));
///     }
///     _ => panic!("Expected Weierstrass curve"),
/// }
///
/// // Use for Bitcoin-style ECDSA
/// let generator = (gx, gy); // Standard generator point
/// let private_key = BigInt::from_bytes(&private_key_bytes);
/// let public_key = scalar_mul(&generator, &private_key, curve);
/// ```
pub fn secp256k1_curve() -> CurveType {
    // secp256k1: y² = x³ + 7
    let a = FieldElement::from_u64(0);
    let b = FieldElement::from_u64(7);

    CurveType::Weierstrass { a, b }
}

#[cfg(all(test, feature = "alloc"))]
include!("elliptic_curve/tests.rs");