Generalized Elliptic Curve Rust Library without Dependencies

A generalized zero-dependency elliptic curve implementation in Rust with support for custom elliptic curves over custom fields with performance, type-safety, and memory-safety guarantees of Rust.

This library implements its own big integer arithmetic, modular arithmetic, and polynomials to remain dependency-free.

Note

This library does not guarantee constant-time operations.

Feature Support Status

Fields:

• 32-bit to 256-bit Prime fields ($\mathbb{F}_p$)
• 512-bit Prime fields ($\mathbb{F}_p$)
• Generic type of inner PrimeFieldValue (requires not yet supported feature(generic_const_parameter_types))
• Finite Extension fields ($\mathbb{F}_{p^m}$)
• Real field ($\mathbb{R}$)
• Rational field ($\mathbb{Q}$)
• Complex field ($\mathbb{C}$)

Elliptic Curve Point Counting:

• Schoof's Algorithm
• Schoof-Elkies-Atkin Algorithm
• Cornacchia's Algorithm
• Skip the final steps of Schoof with Pollard's Kangaroo

Elliptic Curve Point Coordinate Forms:

• Affine
• Projective
• ProjectiveXZ (used by Montgomery curves)
• Jacobian

Elliptic Curve Forms:

• Short Weierstrass curves
• Montgomery curves
• Edwards curves
• General Weierstrass curves

Elliptic Curve Isomorphisms:

• Short Weierstrass -> Montgomery
• Montgomery -> Short Weierstrass
• Short Weierstrass -> General Weierstrass
• General Weierstrass -> Short Weierstrass
• Montgomery -> General Weierstrass
• General Weierstrass -> Montgomery

Polynomials:

• Univariate Polynomials
• Bivariate Polynomials
• Quotient Rings

Polynomial Root Finding:

• Cantor-Zassenhaus Algorithm (over $\mathbb{F}_p$)
• Cardano's Formula (over $\mathbb{R}$)
• Finding roots of polynomials with $\deg > 3$ over $\mathbb{R}$

Prerequisites

This library relies on unstable Rust features only available in the Nightly release channel. Additionally, the unmerged feature(get_set_bit) and const Iterator for Range pull requests are required. Until they are merged, the Rust toolchain with these PRs applied must be built from source. For build instructions refer to Installing from Source.

Run tests

To run the tests with the test profile use:

cargo test

This ignores some tests that would take a long time to execute. Use --include-ignored to also run these ignored tests. Switch to the release profile with --release for significantly better performance.

cargo test --release -- --include-ignored

Run benchmarks

cargo bench

Documentation

To generate the API documentation from the code and view it in a web browser, run:

cargo doc --open

Usage

Add the library to Cargo.toml:

[dependencies]
ec-genesis = { git = "https://github.com/Filiprogrammer/ec-genesis.git" }

Example 1: Basic Arithmetic on a Prime Field

1. Instantiate an elliptic curve $y^2 = x^3 + 2x + 16$ over $\mathbb{F}_{19}$
2. Define a point on the elliptic curve: $P = (3, 7)$
3. Multiply the point by $9$

#![feature(const_convert, const_trait_impl)]

use ec_genesis::elliptic_curve::point::AffineEllipticCurvePoint;
use ec_genesis::elliptic_curve::point::EllipticCurvePointOps;
use ec_genesis::elliptic_curve::ShortWeierstrassEllipticCurve;
use ec_genesis::field::prime_field::PrimeField;
use ec_genesis::field::Field;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Instantiate the field F_19.
    let field = PrimeField::<{ 19.into() }>::new()?;

    // Define the elliptic curve coefficients.
    let a = field.value(2);
    let b = field.value(16);

    // Instantiate the elliptic curve.
    let ec = ShortWeierstrassEllipticCurve::new(field, a, b)?;

    // Define the point P = (3, 7)
    let p = AffineEllipticCurvePoint::finite(field.value(3), field.value(7));

    // Calculate 9 * P
    let r = p.mul(&9.into(), &ec);

    println!("9P = {r}");

    Ok(())
}

Output: 9P = (13, 4)

Example 2: Private-Public key pair generation on Curve25519

Generate a private-public key pair on Curve25519 specified in RFC 7748.

#![feature(const_ops, const_trait_impl, random)]

use ec_genesis::bigint::U256;
use ec_genesis::elliptic_curve::MontgomeryEllipticCurve;
use ec_genesis::elliptic_curve::point::EllipticCurvePointOps;
use ec_genesis::elliptic_curve::point::ProjectiveXZEllipticCurvePoint;
use ec_genesis::field::Field;
use ec_genesis::field::prime_field::PrimeField;
use std::random::random;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Define constants specified in RFC 7748
    const P: U256 = (U256::ONE << 255) - 19u32;
    const EC_ORDER: U256 = ((U256::ONE << 252) + 0x14def9dea2f79cd65812631a5cf5d3edu128) * 8u32;

    // Instantiate the field F_{2^255 - 19}.
    let field = PrimeField::<P>::new()?;

    // Define the elliptic curve coefficients.
    let a = field.value(486662);
    let b = field.value(1);

    // Instantiate the Montgomery curve.
    let ec = MontgomeryEllipticCurve::new(field, a, b)?;

    // Define the generator point G = (9 : 1) as specified in RFC 7748
    let g = ProjectiveXZEllipticCurvePoint::new(field.value(9), field.value(1));

    // Generate a random private key scalar according to RFC 7748 page 8
    let private_key = U256::from((random::<u128>(..) << 3, random::<u128>(..) >> 1 | 1 << 126));

    // public_key = private_key * G
    let public_key = g.mul(&private_key, &ec);

    // Normalize the X-coordinate of the public key
    let public_key_x_affine = (public_key.x() / public_key.z()).unwrap();

    println!("private_key:\t{private_key:064x}");
    println!("public_key:\t{public_key_x_affine:064x}");

    Ok(())
}

Output:

private_key:    7a154dc4e7379515da1dfbde96ed9190b96bae689784ab40d4cc77599f165570
public_key:     164ebdd07d10ca35d535b4c74243d28eb3445a4415033600867fc8b2cde9e376

Verify with OpenSSL:

$ PRIVKEY_BIG_ENDIAN=7a154dc4e7379515da1dfbde96ed9190b96bae689784ab40d4cc77599f165570
$ printf 302e020100300506032b656e04220420$(echo $PRIVKEY_BIG_ENDIAN | fold -w2 | tac | tr -d \\n) | xxd -r -p | openssl pkey -inform DER -pubout -text -noout
X25519 Public-Key:
pub:
    76:e3:e9:cd:b2:c8:7f:86:00:36:03:15:44:5a:44:
    b3:8e:d2:43:42:c7:b4:35:d5:35:ca:10:7d:d0:bd:
    4e:16

The output from OpenSSL matches our public key. (Note: OpenSSL uses little-endian format, so the bytes are reversed.)

Example 3: Point Counting on secp128r1

Count the number of points on the secp128r1 elliptic curve specified in SEC2v1.

#![feature(const_convert, const_trait_impl)]

use ec_genesis::elliptic_curve::EllipticCurveOrder;
use ec_genesis::elliptic_curve::ShortWeierstrassEllipticCurve;
use ec_genesis::field::Field;
use ec_genesis::field::prime_field::PrimeField;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Instantiate the field F_{2^128 - 2^97 - 1}
    let field = PrimeField::<{ (u128::MAX - 2u128.pow(97)).into() }>::new()?;

    // Instantiate the elliptic curve
    let a = field.value(0xFFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFC);
    let b = field.value(0xE87579C11079F43DD824993C2CEE5ED3);
    let ec = ShortWeierstrassEllipticCurve::new(field, a, b)?;

    // Count the points on the elliptic curve
    let order = ec.order();

    println!("Number of points on the curve: {order:#x}");

    Ok(())
}

Output:

Number of points on the curve: 0xfffffffe0000000075a30d1b9038a115

According to SEC2v1 (section 2.3.1, Recommended Parameters secp128r1):

Finally the order n of G and the cofactor are:

n = FFFFFFFE 00000000 75A30D1B 9038A115
h = 01

Our output does indeed match $n * h$.