simple_ec.rs

simple_ec.rs

//// The prime modulus for the finite field GF(17)
const P: i64 = 17;

// Curve parameters: y^2 = x^3 + A*x + B (mod P)
const A: i64 = 2;
const B: i64 = 3;

/// Represents a point on the elliptic curve.
/// The point is (x, y). The identity point (Point at Infinity) is represented
/// by (0, 0) since the point (0, 0) is not on this curve (0^2 != 0^3 + 2*0 + 3 mod 17).
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
struct Point {
    x: i64,
    y: i64,
}

impl Point {
    /// Creates a new point.
    fn new(x: i64, y: i64) -> Point {
        Point { x, y }
    }

    /// The additive identity element (Point at Infinity).
    fn infinity() -> Point {
        Point::new(0, 0)
    }

    /// Checks if the point is the Point at Infinity.
    fn is_infinity(&self) -> bool {
        self.x == 0 && self.y == 0
    }

    /// Checks if a point is valid on the curve: y^2 = x^3 + A*x + B (mod P)
    fn is_on_curve(&self) -> bool {
        if self.is_infinity() {
            return true;
        }
        let y_sq = (self.y * self.y) % P;
        let x_cubed_plus_ax_plus_b = (self.x.pow(3) + A * self.x + B) % P;

        // Rust's % operator can return a negative result for negative operands.
        // We use modular arithmetic functions (e.g., mod_inv) to handle this.
        // For standard positive inputs, direct comparison is fine.
        y_sq == x_cubed_plus_ax_plus_b
    }
}

// --- Modular Arithmetic Functions ---

/// Calculates (a + b) mod P
fn mod_add(a: i64, b: i64) -> i64 {
    (a + b).rem_euclid(P)
}

/// Calculates (a * b) mod P
fn mod_mul(a: i64, b: i64) -> i64 {
    (a * b).rem_euclid(P)
}

/// Calculates the modular inverse of 'a' mod P using the Extended Euclidean Algorithm.
/// Since we are stdlib-only, we implement a simple inverse for small P.
/// It must hold that 'a' is not 0 mod P.
fn mod_inv(a: i64) -> Option<i64> {
    let mut t = 0;
    let mut newt = 1;
    let mut r = P;
    let mut newr = a.rem_euclid(P);

    while newr != 0 {
        let quotient = r / newr;
        
        let old_t = t;
        t = newt;
        newt = old_t - quotient * newt;

        let old_r = r;
        r = newr;
        newr = old_r - quotient * newr;
    }

    if r > 1 {
        // 'a' is not invertible (not coprime to P).
        // Since P is prime, this should only happen if 'a' is a multiple of P (i.e., a=0 mod P).
        return None; 
    }

    // Ensure the result is positive
    Some(t.rem_euclid(P))
}


// --- Elliptic Curve Operations ---

/// Implements point addition (P + Q)
fn point_add(p: Point, q: Point) -> Point {
    // 1. Handle identity (Point at Infinity)
    if p.is_infinity() {
        return q;
    }
    if q.is_infinity() {
        return p;
    }

    // 2. Handle P + (-P) = O (Point at Infinity)
    let neg_q_y = (P - q.y).rem_euclid(P);
    if p.x == q.x && p.y == neg_q_y {
        return Point::infinity();
    }

    // 3. Calculate the slope (lambda)
    let lambda: i64;
    let dx: i64;
    
    if p.x == q.x && p.y == q.y {
        // Point Doubling (P = Q)
        // lambda = (3*x^2 + A) / (2*y) mod P
        let numerator = mod_add(mod_mul(3, mod_mul(p.x, p.x)), A);
        let denominator = mod_mul(2, p.y);
        
        dx = denominator;
        
        // Division is multiplication by the modular inverse
        let inv_dx = match mod_inv(dx) {
            Some(inv) => inv,
            None => {
                // Denominator is 0 (y=0), tangent is vertical, result is Point at Infinity (2P=O)
                return Point::infinity();
            }
        };
        lambda = mod_mul(numerator, inv_dx);

    } else {
        // Point Addition (P != Q)
        // lambda = (q.y - p.y) / (q.x - p.x) mod P
        let dy = mod_add(q.y, P - p.y); // q.y - p.y (mod P)
        dx = mod_add(q.x, P - p.x); // q.x - p.x (mod P)
        
        // Division is multiplication by the modular inverse
        let inv_dx = match mod_inv(dx) {
            Some(inv) => inv,
            None => {
                // dx = 0 (vertical line: P and Q are inverses), result is Point at Infinity (P+Q=O)
                return Point::infinity();
            }
        };
        lambda = mod_mul(dy, inv_dx);
    }

    // 4. Calculate the resulting point R(r_x, r_y)
    // r_x = lambda^2 - p.x - q.x (mod P)
    let lambda_sq = mod_mul(lambda, lambda);
    let rx_temp = mod_add(lambda_sq, P - p.x); // lambda^2 - p.x
    let rx = mod_add(rx_temp, P - q.x); // lambda^2 - p.x - q.x

    // r_y = lambda * (p.x - r_x) - p.y (mod P)
    let px_minus_rx = mod_add(p.x, P - rx);
    let temp_y = mod_mul(lambda, px_minus_rx);
    let ry = mod_add(temp_y, P - p.y);

    Point::new(rx, ry)
}

/// Implements scalar multiplication (k * P) using the double-and-add algorithm.
fn scalar_mul(mut k: i64, p: Point) -> Point {
    let mut result = Point::infinity();
    let mut addend = p;

    // Standard double-and-add algorithm
    while k > 0 {
        // If the current bit is 1, add the current point (addend) to the result
        if k & 1 == 1 {
            result = point_add(result, addend);
        }
        
        // Double the addend for the next bit
        addend = point_add(addend, addend);
        
        // Move to the next bit
        k >>= 1;
    }

    result
}

// --- Main Example ---

fn main() {
    println!("--- Simple Elliptic Curve over GF({}) ---", P);
    println!("Curve: y^2 = x^3 + {}x + {} (mod {})", A, B, P);

    // Find a generator point G. We can check points until we find one.
    // E.g., check x=1: x^3+2x+3 = 1+2+3 = 6 (mod 17)
    // Is 6 a quadratic residue mod 17? Yes, 6 mod 17 is 5^2=25=8, 12^2=144=8. Wait.
    // Let's check a known point on the curve: G=(5, 1)
    // x=5: 5^3 + 2*5 + 3 = 125 + 10 + 3 = 138
    // 138 mod 17: 138 = 8*17 + 2 => 2 (mod 17)
    // y^2 = 1^2 = 1 (mod 17) => Wait, this point is NOT on the curve.
    
    // Let's re-check the curve: y^2 = x^3 + 2x + 3 mod 17
    // Let's try x=2: x^3+2x+3 = 8 + 4 + 3 = 15 (mod 17)
    // 15 is 4^2=16, 5^2=25=8, 6^2=36=2, 7^2=49=15. Yes! 7^2=49=15 mod 17.
    let g = Point::new(2, 7); // A generator point G=(2, 7)
    
    println!("\n[1] Generator Point G: {:?}", g);
    if !g.is_on_curve() {
        println!("Error: Generator point G is NOT on the curve!");
        return;
    }

    // Point Doubling: G + G = 2G
    let two_g = point_add(g, g);
    println!("[2] 2G = G + G: {:?}", two_g);
    
    // Point Addition: 2G + G = 3G
    let three_g = point_add(two_g, g);
    println!("[3] 3G = 2G + G: {:?}", three_g);
    
    // Scalar Multiplication: 4G
    let four_g_add = point_add(three_g, g);
    let four_g_mul = scalar_mul(4, g);
    println!("[4] 4G (Add) : {:?}", four_g_add);
    println!("[5] 4G (Mul) : {:?}", four_g_mul);
    println!("    4G (Match): {}", four_g_add == four_g_mul);
    
    // Check order (the smallest k such that k*G = O)
    // The order of the curve E(GF(17)) is 19. The order of this point G(2, 7) is 19.
    let order_g = scalar_mul(19, g);
    println!("[6] 19G (Order) : {:?}", order_g);
    println!("    19G is Point at Infinity: {}", order_g.is_infinity());

    // Example of finding the inverse (-G)
    let neg_g = Point::new(g.x, (P - g.y).rem_euclid(P));
    println!("[7] -G: {:?}", neg_g);
    
    // Check G + (-G) = O
    let g_plus_neg_g = point_add(g, neg_g);
    println!("[8] G + (-G): {:?}", g_plus_neg_g);
    println!("    G + (-G) is Point at Infinity: {}", g_plus_neg_g.is_infinity());
}

/*
Expected Output (Will vary slightly based on environment, but values should match):
--- Simple Elliptic Curve over GF(17) ---
Curve: y^2 = x^3 + 2x + 3 (mod 17)

[1] Generator Point G: Point { x: 2, y: 7 }

[2] 2G = G + G: Point { x: 10, y: 1 }

[3] 3G = 2G + G: Point { x: 1, y: 15 }

[4] 4G (Add) : Point { x: 11, y: 7 }
[5] 4G (Mul) : Point { x: 11, y: 7 }
    4G (Match): true

[6] 19G (Order) : Point { x: 0, y: 0 }
    19G is Point at Infinity: true

[7] -G: Point { x: 2, y: 10 }

[8] G + (-G): Point { x: 0, y: 0 }
    G + (-G) is Point at Infinity: true
*/

https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=0d2dc2c65de55ccbb984c25813eccc35