primeorder 0.14.0

//! Point arithmetic implementation optimised for different curve equations
//!
//! Support for formulas specialized to the short Weierstrass equation's
//! 𝒂-coefficient.

use elliptic_curve::{Field, subtle::ConditionallySelectable};

use crate::{AffinePoint, PrimeCurveParams, ProjectivePoint};

mod sealed {
    use crate::{AffinePoint, PrimeCurveParams, ProjectivePoint};

    /// Elliptic point arithmetic implementation
    ///
    /// Provides implementation of point arithmetic (point addition, point doubling) which
    /// might be optimized for the curve.
    pub trait PointArithmetic<C: PrimeCurveParams> {
        /// Assigns `lhs + rhs` to `lhs`.
        fn add_assign(lhs: &mut ProjectivePoint<C>, rhs: &ProjectivePoint<C>);

        /// Assigns `lhs + rhs` to `lhs`.
        fn add_assign_mixed(lhs: &mut ProjectivePoint<C>, rhs: &AffinePoint<C>);

        /// Computes `point + point` and assigns it to `point`.
        fn double_in_place(point: &mut ProjectivePoint<C>);
    }
}

/// Allow crate-local visibility
pub(crate) use sealed::PointArithmetic;

// Debug-only checks to ensure we don't accidentally use formulas specialized for a different `a`.
#[inline(always)]
fn debug_assert_equation_a_is_minus_three<C: PrimeCurveParams>() {
    debug_assert_eq!(
        C::EQUATION_A,
        -C::FieldElement::from(3),
        "this implementation is only valid for C::EQUATION_A = -3"
    );
}

#[inline(always)]
fn debug_assert_equation_a_is_zero<C: PrimeCurveParams>() {
    debug_assert_eq!(
        C::EQUATION_A,
        C::FieldElement::ZERO,
        "this implementation is only valid for C::EQUATION_A = 0"
    );
}

/// The 𝒂-coefficient of the short Weierstrass equation does not have specific properties which
/// allow for an optimized implementation.
#[derive(Clone, Copy, Debug)]
pub struct EquationAIsGeneric;

impl<C: PrimeCurveParams> PointArithmetic<C> for EquationAIsGeneric {
    /// Implements complete addition for any curve
    ///
    /// Implements the complete addition formula from [Renes-Costello-Batina 2015]
    /// (Algorithm 1). The comments after each line indicate which algorithm steps
    /// are being performed.
    ///
    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
    fn add_assign(lhs: &mut ProjectivePoint<C>, rhs: &ProjectivePoint<C>) {
        let b3 = C::FieldElement::from(3) * C::EQUATION_B;

        let t0 = lhs.x * rhs.x; // 1
        let t1 = lhs.y * rhs.y; // 2
        let t2 = lhs.z * rhs.z; // 3
        let t3 = lhs.x + lhs.y; // 4
        let t4 = rhs.x + rhs.y; // 5
        let t3 = t3 * t4; // 6
        let t4 = t0 + t1; // 7
        let t3 = t3 - t4; // 8
        let t4 = lhs.x + lhs.z; // 9
        let t5 = rhs.x + rhs.z; // 10
        let t4 = t4 * t5; // 11
        let t5 = t0 + t2; // 12
        let t4 = t4 - t5; // 13
        let t5 = lhs.y + lhs.z; // 14
        let x3 = rhs.y + rhs.z; // 15
        let t5 = t5 * x3; // 16
        let x3 = t1 + t2; // 17
        let t5 = t5 - x3; // 18
        let z3 = C::EQUATION_A * t4; // 19
        let x3 = b3 * t2; // 20
        let z3 = x3 + z3; // 21
        let x3 = t1 - z3; // 22
        let z3 = t1 + z3; // 23
        let y3 = x3 * z3; // 24
        let t1 = t0 + t0; // 25
        let t1 = t1 + t0; // 26
        let t2 = C::EQUATION_A * t2; // 27
        let t4 = b3 * t4; // 28
        let t1 = t1 + t2; // 29
        let t2 = t0 - t2; // 30
        let t2 = C::EQUATION_A * t2; // 31
        let t4 = t4 + t2; // 32
        let t0 = t1 * t4; // 33
        let y3 = y3 + t0; // 34
        let t0 = t5 * t4; // 35
        let x3 = t3 * x3; // 36
        let x3 = x3 - t0; // 37
        let t0 = t3 * t1; // 38
        let z3 = t5 * z3; // 39
        let z3 = z3 + t0; // 40

        lhs.x = x3;
        lhs.y = y3;
        lhs.z = z3;
    }

    /// Implements complete mixed addition for curves with any `a`
    ///
    /// Implements the complete mixed addition formula from [Renes-Costello-Batina 2015]
    /// (Algorithm 2). The comments after each line indicate which algorithm
    /// steps are being performed.
    ///
    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
    fn add_assign_mixed(lhs: &mut ProjectivePoint<C>, rhs: &AffinePoint<C>) {
        let b3 = C::EQUATION_B * C::FieldElement::from(3);

        let t0 = lhs.x * rhs.x; // 1
        let t1 = lhs.y * rhs.y; // 2
        let t3 = rhs.x + rhs.y; // 3
        let t4 = lhs.x + lhs.y; // 4
        let t3 = t3 * t4; // 5
        let t4 = t0 + t1; // 6
        let t3 = t3 - t4; // 7
        let t4 = rhs.x * lhs.z; // 8
        let t4 = t4 + lhs.x; // 9
        let t5 = rhs.y * lhs.z; // 10
        let t5 = t5 + lhs.y; // 11
        let z3 = C::EQUATION_A * t4; // 12
        let x3 = b3 * lhs.z; // 13
        let z3 = x3 + z3; // 14
        let x3 = t1 - z3; // 15
        let z3 = t1 + z3; // 16
        let y3 = x3 * z3; // 17
        let t1 = t0 + t0; // 18
        let t1 = t1 + t0; // 19
        let t2 = C::EQUATION_A * lhs.z; // 20
        let t4 = b3 * t4; // 21
        let t1 = t1 + t2; // 22
        let t2 = t0 - t2; // 23
        let t2 = C::EQUATION_A * t2; // 24
        let t4 = t4 + t2; // 25
        let t0 = t1 * t4; // 26
        let y3 = y3 + t0; // 27
        let t0 = t5 * t4; // 28
        let x3 = t3 * x3; // 29
        let x3 = x3 - t0; // 30
        let t0 = t3 * t1; // 31
        let z3 = t5 * z3; // 32
        let z3 = z3 + t0; // 33

        lhs.x.conditional_assign(&x3, !rhs.is_identity());
        lhs.y.conditional_assign(&y3, !rhs.is_identity());
        lhs.z.conditional_assign(&z3, !rhs.is_identity());
    }

    /// Implements point doubling for curves with any `a`
    ///
    /// Implements the exception-free point doubling formula from [Renes-Costello-Batina 2015]
    /// (Algorithm 3). The comments after each line indicate which algorithm
    /// steps are being performed.
    ///
    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
    fn double_in_place(point: &mut ProjectivePoint<C>) {
        let b3 = C::EQUATION_B * C::FieldElement::from(3);

        let t0 = point.x.square(); // 1
        let t1 = point.y.square(); // 2
        let t2 = point.z.square(); // 3
        let t3 = point.x * point.y; // 4
        let t3 = t3 + t3; // 5
        let z3 = point.x * point.z; // 6
        let z3 = z3 + z3; // 7
        let x3 = C::EQUATION_A * z3; // 8
        let y3 = b3 * t2; // 9
        let y3 = x3 + y3; // 10
        let x3 = t1 - y3; // 11
        let y3 = t1 + y3; // 12
        let y3 = x3 * y3; // 13
        let x3 = t3 * x3; // 14
        let z3 = b3 * z3; // 15
        let t2 = C::EQUATION_A * t2; // 16
        let t3 = t0 - t2; // 17
        let t3 = C::EQUATION_A * t3; // 18
        let t3 = t3 + z3; // 19
        let z3 = t0 + t0; // 20
        let t0 = z3 + t0; // 21
        let t0 = t0 + t2; // 22
        let t0 = t0 * t3; // 23
        let y3 = y3 + t0; // 24
        let t2 = point.y * point.z; // 25
        let t2 = t2 + t2; // 26
        let t0 = t2 * t3; // 27
        let x3 = x3 - t0; // 28
        let z3 = t2 * t1; // 29
        let z3 = z3 + z3; // 30
        let z3 = z3 + z3; // 31

        point.x = x3;
        point.y = y3;
        point.z = z3;
    }
}

/// The 𝒂-coefficient of the short Weierstrass equation is `-3`.
#[derive(Clone, Copy, Debug)]
pub struct EquationAIsMinusThree;

impl<C: PrimeCurveParams> PointArithmetic<C> for EquationAIsMinusThree {
    /// Implements complete addition for curves with `a = -3`
    ///
    /// Implements the complete addition formula from [Renes-Costello-Batina 2015]
    /// (Algorithm 4). The comments after each line indicate which algorithm steps
    /// are being performed.
    ///
    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
    fn add_assign(lhs: &mut ProjectivePoint<C>, rhs: &ProjectivePoint<C>) {
        debug_assert_equation_a_is_minus_three::<C>();

        let xx = lhs.x * rhs.x; // 1
        let yy = lhs.y * rhs.y; // 2
        let zz = lhs.z * rhs.z; // 3
        let xy_pairs = ((lhs.x + lhs.y) * (rhs.x + rhs.y)) - (xx + yy); // 4, 5, 6, 7, 8
        let yz_pairs = ((lhs.y + lhs.z) * (rhs.y + rhs.z)) - (yy + zz); // 9, 10, 11, 12, 13
        let xz_pairs = ((lhs.x + lhs.z) * (rhs.x + rhs.z)) - (xx + zz); // 14, 15, 16, 17, 18

        let bzz_part = xz_pairs - (C::EQUATION_B * zz); // 19, 20
        let bzz3_part = bzz_part.double() + bzz_part; // 21, 22
        let yy_m_bzz3 = yy - bzz3_part; // 23
        let yy_p_bzz3 = yy + bzz3_part; // 24

        let zz3 = zz.double() + zz; // 26, 27
        let bxz_part = (C::EQUATION_B * xz_pairs) - (zz3 + xx); // 25, 28, 29
        let bxz3_part = bxz_part.double() + bxz_part; // 30, 31
        let xx3_m_zz3 = xx.double() + xx - zz3; // 32, 33, 34

        lhs.x = (yy_p_bzz3 * xy_pairs) - (yz_pairs * bxz3_part); // 35, 39, 40
        lhs.y = (yy_p_bzz3 * yy_m_bzz3) + (xx3_m_zz3 * bxz3_part); // 36, 37, 38
        lhs.z = (yy_m_bzz3 * yz_pairs) + (xy_pairs * xx3_m_zz3); // 41, 42, 43
    }

    /// Implements complete mixed addition for curves with `a = -3`
    ///
    /// Implements the complete mixed addition formula from [Renes-Costello-Batina 2015]
    /// (Algorithm 5). The comments after each line indicate which algorithm
    /// steps are being performed.
    ///
    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
    fn add_assign_mixed(lhs: &mut ProjectivePoint<C>, rhs: &AffinePoint<C>) {
        debug_assert_equation_a_is_minus_three::<C>();

        let xx = lhs.x * rhs.x; // 1
        let yy = lhs.y * rhs.y; // 2
        let xy_pairs = ((lhs.x + lhs.y) * (rhs.x + rhs.y)) - (xx + yy); // 3, 4, 5, 6, 7
        let yz_pairs = (rhs.y * lhs.z) + lhs.y; // 8, 9 (t4)
        let xz_pairs = (rhs.x * lhs.z) + lhs.x; // 10, 11 (y3)

        let bz_part = xz_pairs - (C::EQUATION_B * lhs.z); // 12, 13
        let bz3_part = bz_part.double() + bz_part; // 14, 15
        let yy_m_bzz3 = yy - bz3_part; // 16
        let yy_p_bzz3 = yy + bz3_part; // 17

        let z3 = lhs.z.double() + lhs.z; // 19, 20
        let bxz_part = (C::EQUATION_B * xz_pairs) - (z3 + xx); // 18, 21, 22
        let bxz3_part = bxz_part.double() + bxz_part; // 23, 24
        let xx3_m_zz3 = xx.double() + xx - z3; // 25, 26, 27

        let x = (yy_p_bzz3 * xy_pairs) - (yz_pairs * bxz3_part); // 28, 32, 33
        let y = (yy_p_bzz3 * yy_m_bzz3) + (xx3_m_zz3 * bxz3_part); // 29, 30, 31
        let z = (yy_m_bzz3 * yz_pairs) + (xy_pairs * xx3_m_zz3); // 34, 35, 36

        lhs.x.conditional_assign(&x, !rhs.is_identity());
        lhs.y.conditional_assign(&y, !rhs.is_identity());
        lhs.z.conditional_assign(&z, !rhs.is_identity());
    }

    /// Implements point doubling for curves with `a = -3`
    ///
    /// Implements the exception-free point doubling formula from [Renes-Costello-Batina 2015]
    /// (Algorithm 6). The comments after each line indicate which algorithm
    /// steps are being performed.
    ///
    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
    fn double_in_place(point: &mut ProjectivePoint<C>) {
        debug_assert_equation_a_is_minus_three::<C>();

        let xx = point.x.square(); // 1
        let yy = point.y.square(); // 2
        let zz = point.z.square(); // 3
        let xy2 = (point.x * point.y).double(); // 4, 5
        let xz2 = (point.x * point.z).double(); // 6, 7

        let bzz_part = (C::EQUATION_B * zz) - xz2; // 8, 9
        let bzz3_part = bzz_part.double() + bzz_part; // 10, 11
        let yy_m_bzz3 = yy - bzz3_part; // 12
        let yy_p_bzz3 = yy + bzz3_part; // 13
        let y_frag = yy_p_bzz3 * yy_m_bzz3; // 14
        let x_frag = yy_m_bzz3 * xy2; // 15

        let zz3 = zz.double() + zz; // 16, 17
        let bxz2_part = (C::EQUATION_B * xz2) - (zz3 + xx); // 18, 19, 20
        let bxz6_part = bxz2_part.double() + bxz2_part; // 21, 22
        let xx3_m_zz3 = xx.double() + xx - zz3; // 23, 24, 25

        let y = y_frag + (xx3_m_zz3 * bxz6_part); // 26, 27
        let yz2 = (point.y * point.z).double(); // 28, 29
        let x = x_frag - (bxz6_part * yz2); // 30, 31
        let z = (yz2 * yy).double().double(); // 32, 33, 34

        point.x = x;
        point.y = y;
        point.z = z;
    }
}

/// The 𝒂-coefficient of the short Weierstrass equation is `0`.
#[derive(Clone, Copy, Debug)]
pub struct EquationAIsZero;

impl<C: PrimeCurveParams> PointArithmetic<C> for EquationAIsZero {
    /// Implements complete addition for curves with `a = 0`
    ///
    /// Implements the complete addition formula from [Renes-Costello-Batina 2015]
    /// (Algorithm 7). The comments after each line indicate which algorithm steps
    /// are being performed.
    ///
    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
    fn add_assign(lhs: &mut ProjectivePoint<C>, rhs: &ProjectivePoint<C>) {
        debug_assert_equation_a_is_zero::<C>();

        let b3 = C::FieldElement::from(3) * C::EQUATION_B;

        let t0 = lhs.x * rhs.x; // 1
        let t1 = lhs.y * rhs.y; // 2
        let t2 = lhs.z * rhs.z; // 3
        let t3 = lhs.x + lhs.y; // 4
        let t4 = rhs.x + rhs.y; // 5
        let t3 = t3 * t4; // 6
        let t4 = t0 + t1; // 7
        let t3 = t3 - t4; // 8
        let t4 = lhs.y + lhs.z; // 9
        let x3 = rhs.y + rhs.z; // 10
        let t4 = t4 * x3; // 11
        let x3 = t1 + t2; // 12
        let t4 = t4 - x3; // 13
        let x3 = lhs.x + lhs.z; // 14
        let y3 = rhs.x + rhs.z; // 15
        let x3 = x3 * y3; // 16
        let y3 = t0 + t2; // 17
        let y3 = x3 - y3; // 18
        let x3 = t0.double(); // 19
        let t0 = x3 + t0; // 20
        let t2 = b3 * t2; // 21
        let z3 = t1 + t2; // 22
        let t1 = t1 - t2; // 23
        let y3 = b3 * y3; // 24
        let x3 = t4 * y3; // 25
        let t2 = t3 * t1; // 26
        let x3 = t2 - x3; // 27
        let y3 = y3 * t0; // 28
        let t1 = t1 * z3; // 29
        let y3 = t1 + y3; // 30
        let t0 = t0 * t3; // 31
        let z3 = z3 * t4; // 32
        let z3 = z3 + t0; // 33

        lhs.x = x3;
        lhs.y = y3;
        lhs.z = z3;
    }

    /// Implements complete mixed addition for curves with `a = 0`
    ///
    /// Implements the complete mixed addition formula from [Renes-Costello-Batina 2015]
    /// (Algorithm 8). The comments after each line indicate which algorithm
    /// steps are being performed.
    ///
    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
    fn add_assign_mixed(lhs: &mut ProjectivePoint<C>, rhs: &AffinePoint<C>) {
        debug_assert_equation_a_is_zero::<C>();

        let b3 = C::EQUATION_B * C::FieldElement::from(3);

        let t0 = lhs.x * rhs.x; // 1
        let t1 = lhs.y * rhs.y; // 2
        let t3 = rhs.x + rhs.y; // 3
        let t4 = lhs.x + lhs.y; // 4
        let t3 = t3 * t4; // 5
        let t4 = t0 + t1; // 6
        let t3 = t3 - t4; // 7
        let t4 = rhs.y * lhs.z; // 8
        let t4 = t4 + lhs.y; // 9
        let y3 = rhs.x * lhs.z; // 10
        let y3 = y3 + lhs.x; // 11
        let x3 = t0.double(); // 12
        let t0 = x3 + t0; // 13
        let t2 = b3 * lhs.z; // 14
        let z3 = t1 + t2; // 15
        let t1 = t1 - t2; // 16
        let y3 = b3 * y3; // 17
        let x3 = t4 * y3; // 18
        let t2 = t3 * t1; // 19
        let x3 = t2 - x3; // 20
        let y3 = y3 * t0; // 21
        let t1 = t1 * z3; // 22
        let y3 = t1 + y3; // 23
        let t0 = t0 * t3; // 24
        let z3 = z3 * t4; // 25
        let z3 = z3 + t0; // 26

        lhs.x.conditional_assign(&x3, !rhs.is_identity());
        lhs.y.conditional_assign(&y3, !rhs.is_identity());
        lhs.z.conditional_assign(&z3, !rhs.is_identity());
    }

    /// Implements point doubling for curves with `a = 0`
    ///
    /// Implements the exception-free point doubling formula from [Renes-Costello-Batina 2015]
    /// (Algorithm 9). The comments after each line indicate which algorithm
    /// steps are being performed.
    ///
    /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060
    fn double_in_place(point: &mut ProjectivePoint<C>) {
        debug_assert_equation_a_is_zero::<C>();

        let b3 = C::EQUATION_B * C::FieldElement::from(3);

        let t0 = point.y.square(); // 1
        let z3 = t0.double(); // 2
        let z3 = z3.double(); // 3
        let z3 = z3.double(); // 4
        let t1 = point.y * point.z; // 5
        let t2 = point.z.square(); // 6
        let t2 = b3 * t2; // 7
        let x3 = t2 * z3; // 8
        let y3 = t0 + t2; // 9
        let z3 = t1 * z3; // 10
        let t1 = t2.double(); // 11
        let t2 = t1 + t2; // 12
        let t0 = t0 - t2; // 13
        let y3 = t0 * y3; // 14
        let y3 = x3 + y3; // 15
        let t1 = point.x * point.y; // 16
        let x3 = t0 * t1; // 17
        let x3 = x3.double(); // 18

        point.x = x3;
        point.y = y3;
        point.z = z3;
    }
}