arcis_compiler/utils/

elliptic_curve.rs

use crate::{
    core::{
        circuits::{
            arithmetic::{
                sqrt,
                AffineEdwardsPointAdditionCircuit,
                ProjectiveEdwardsPointAdditionCircuit,
            },
            boolean::{boolean_value::Boolean, utils::CircuitType},
            general::edwards_mul::ProjectiveEdwards25519MultiplicationCircuit,
        },
        expressions::{domain::Domain, other_expr::OtherExpr},
        global_value::{field_array::FieldArray, value::FieldValue},
    },
    traits::{Equal, FromLeBytes, GetBit, Invert, Pow, Reveal, Select, WithBooleanBounds},
    utils::{
        curve_point::CurvePoint,
        field::{BaseField, ScalarField},
        number::Number,
    },
};
use ff::Field;
use std::ops::{Add, Mul, Neg, Sub};

// 0 in F_{2^255-19}.
pub const ZERO: [u8; 32] = [
    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
];

// 1 in F_{2^255-19}.
// ONE is in little-endian encoding.
pub const ONE: [u8; 32] = [
    0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
];

// The square-root of -1 in F_{2^255-19}.
// SQRT_NEG_ONE is in little-endian encoding.
pub const SQRT_NEG_ONE: [u8; 32] = [
    0xb0, 0xa0, 0xe, 0x4a, 0x27, 0x1b, 0xee, 0xc4, 0x78, 0xe4, 0x2f, 0xad, 0x6, 0x18, 0x43, 0x2f,
    0xa7, 0xd7, 0xfb, 0x3d, 0x99, 0x0, 0x4d, 0x2b, 0xb, 0xdf, 0xc1, 0x4f, 0x80, 0x24, 0x83, 0x2b,
];

/// 1/sqrt(a-d), where a = -1 (mod p) and d are the Edwards curve parameters.
/// INVSQRT_NEG_ONE_MINUS_D is in little-endian encoding.
pub const INVSQRT_NEG_ONE_MINUS_D: [u8; 32] = [
    0xea, 0x40, 0x5d, 0x80, 0xaa, 0xfd, 0xc8, 0x99, 0xbe, 0x72, 0x41, 0x5a, 0x17, 0x16, 0x2f, 0x9d,
    0x40, 0xd8, 0x1, 0xfe, 0x91, 0x7b, 0xc2, 0x16, 0xa2, 0xfc, 0xaf, 0xcf, 0x5, 0x89, 0x6c, 0x78,
];

// The equation of CURVE25519 is v^2 = u^3 + CURVE25519_A*u^2 + u over F_{2^255-19}.
// CURVE25519_A is in little-endian encoding.
pub const CURVE25519_A: [u8; 32] = [
    0x6, 0x6d, 0x7, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
];

// CURVE25519_T = sqrt(-CURVE25519_A - 2). This is needed to convert between the Montgomery and
// the Edwards model.
// CURVE25519_T is in little-endian encoding.
pub const CURVE25519_T: [u8; 32] = [
    0xe7, 0x81, 0xba, 0x0, 0x55, 0xfb, 0x91, 0x33, 0x7d, 0xe5, 0x82, 0xb4, 0x2e, 0x2c, 0x5e, 0x3a,
    0x81, 0xb0, 0x3, 0xfc, 0x23, 0xf7, 0x84, 0x2d, 0x44, 0xf9, 0x5f, 0x9f, 0xb, 0x12, 0xd9, 0x70,
];

// The equation of Edwards25519 is -x^2 + y^2 = 1 + EDWARDS25519_D*x^2*y^2 over
// F_{2^255-19}. Note that EDWARDS25519_D = -(CURVE25519_A-2)/(CURVE25519_A+2).
// EDWARDS25519_D is in little-endian encoding.
pub const EDWARDS25519_D: [u8; 32] = [
    0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75, 0xab, 0xd8, 0x41, 0x41, 0x4d, 0xa, 0x70, 0x0,
    0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c, 0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x3, 0x52,
];

// The x-coordinate of the generator G of the cyclic subgroup of prime order ell.
// The birational map sends this point to the Montgomery point with u-coordinate = 9.
// EDWARDS25519_G_X is in little-endian encoding.
pub const EDWARDS25519_G_X: [u8; 32] = [
    0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9, 0xb2, 0xa7, 0x25, 0x95, 0x60, 0xc7, 0x2c, 0x69,
    0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0, 0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36, 0x69, 0x21,
];

// The y-coordinate of the generator G of the cyclic subgroup of prime order ell.
// The birational map sends this point to the Montgomery point with u-coordinate = 9.
// EDWARDS25519_G_Y is in little-endian encoding.
pub const EDWARDS25519_G_Y: [u8; 32] = [
    0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
    0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
];

// The x-coordinate of the point of order 8 with smallest y-coordinate.
// EDWARDS25519_Q_X is in little-endian encoding.
pub const EDWARDS25519_Q_X: [u8; 32] = [
    0x4a, 0xd1, 0x45, 0xc5, 0x46, 0x46, 0xa1, 0xde, 0x38, 0xe2, 0xe5, 0x13, 0x70, 0x3c, 0x19, 0x5c,
    0xbb, 0x4a, 0xde, 0x38, 0x32, 0x99, 0x33, 0xe9, 0x28, 0x4a, 0x39, 0x6, 0xa0, 0xb9, 0xd5, 0x1f,
];

// The smallest y-coordinate of a point of order 8 (a 251-bit number).
// EDWARDS25519_Q_Y is in little-endian encoding.
pub const EDWARDS25519_Q_Y: [u8; 32] = [
    0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2, 0xef, 0x98, 0xf0,
    0xd5, 0xdf, 0xac, 0x5, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38, 0x2, 0x88, 0x6d, 0x53, 0xfc, 0x5,
];

// The equation of Edwards25519_twist is -x^2 + y^2 = 1 + EDWARDS25519_D_TWIST*x^2*y^2
// over F_{2^255-19}. Note that EDWARDS25519_D_TWIST = EDWARDS25519_D^{-1}.
// EDWARDS25519_D_TWIST is in little-endian encoding.
pub const EDWARDS25519_D_TWIST: [u8; 32] = [
    0x43, 0xf8, 0xc9, 0xcd, 0x76, 0xf2, 0xe0, 0x25, 0x2e, 0x54, 0x79, 0x42, 0x98, 0xd6, 0x5d, 0xb,
    0x66, 0xcf, 0xb9, 0xcd, 0x14, 0x21, 0x16, 0x2b, 0x43, 0xce, 0xd5, 0x14, 0xd2, 0x7e, 0x90, 0x40,
];

// 4^{-1} mod ell.
// FOUR_INV_MOD_ELL is in little-endian encoding.
pub const FOUR_INV_MOD_ELL: [u8; 32] = [
    0xf2, 0x5e, 0xb8, 0xc5, 0x53, 0xca, 0xd, 0xc2, 0xa0, 0xb5, 0x39, 0xfa, 0x66, 0x3b, 0xa7, 0xf,
    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0xc,
];

// 8^{-1} mod ell.
// EIGHT_INV_MOD_ELL is in little-endian encoding.
pub const EIGHT_INV_MOD_ELL: [u8; 32] = [
    0x79, 0x2f, 0xdc, 0xe2, 0x29, 0xe5, 0x6, 0x61, 0xd0, 0xda, 0x1c, 0x7d, 0xb3, 0x9d, 0xd3, 0x7,
    0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x6,
];

// Lsb-to-msb binary expansion of ScalarField::modulus().
pub const ELL_BIN: &str = "1011011111001011101011110011101001011000110001100100100000011010011010110011100111101111010001010111101110011111011110110010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001";

/// A trait that represents `BaseField`-related arithmetic. Should be implemented by `BaseField`,
/// `FieldValue<BaseField>` and `FieldArray<N, BaseField>`.
pub trait F25519:
    Add<Self, Output = Self>
    + Sub<Self, Output = Self>
    + Mul<Self, Output = Self>
    + Neg<Output = Self>
    + Pow
    + Invert
    + Reveal
    + Copy
    + WithBooleanBounds
    + From<i32>
    + From<Number>
    + From<BaseField>
{
}

impl F25519 for BaseField {}
impl F25519 for FieldValue<BaseField> {}
impl<const N: usize> F25519 for FieldArray<N, BaseField> {}

/// Affine point on the twisted Edwards25519 curve -x^2 + y^2 = 1 + d*x^2*y^2.
/// We set `is_on_curve: true` if we know the coordinates define a point on the curve.
/// We set `is_ell_torsion: true` if we know the coordinates define a \ell-torsion point.
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct AffineEdwardsPoint<T: F25519> {
    pub x: T,
    pub y: T,
    pub is_on_curve: bool,
    pub is_ell_torsion: bool,
}

#[allow(non_snake_case)]
impl<T: F25519> AffineEdwardsPoint<T> {
    pub fn new(P: (T, T), is_on_curve: bool, is_ell_torsion: bool) -> Self {
        assert!(
            is_on_curve || !is_ell_torsion,
            "A point that is not on the curve cannot be a ell-torsion point."
        );
        Self {
            x: P.0,
            y: P.1,
            is_on_curve,
            is_ell_torsion,
        }
    }

    pub fn inner(&self) -> (T, T) {
        (self.x, self.y)
    }

    pub fn identity() -> Self {
        Self::new((T::from(0), T::from(1)), true, true)
    }

    pub fn to_projective(self) -> ProjectiveEdwardsPoint<T> {
        ProjectiveEdwardsPoint::new(
            (self.x, self.y, T::from(1)),
            self.is_on_curve,
            self.is_ell_torsion,
        )
    }

    /// Convert a Montgomery point to an Edwards point.
    /// Although the birational map is not well-defined at the 2-torsion point P = (0, 0),
    /// this function sends P to the 2-torsion point (0, -1) (as long as 0.invert() = 0).
    pub fn from_montgomery(P: (T, T)) -> Self {
        let (u, v) = P;
        // send (u, v) to the Edwards curve
        let t = T::from(BaseField::from_le_bytes(CURVE25519_T));
        // v can be zero (for the 2-torsion point P = (0, 0) or for an invalid point)
        let x = t * u * v.invert(false);
        // there is no point on the curve with u-coordinate equal to -1, but P could be an invalid
        // point
        let y = (u - T::from(BaseField::ONE)) * (u + T::from(BaseField::ONE)).invert(false);
        Self::new((x, y), false, false)
    }

    /// Convert an Edwards point to a Montgomery point.
    /// Although the birational map is not well-defined at the identity and at the 2-torsion
    /// point P = (0, -1), this function sends both points to the 2-torsion point (0, 0)
    /// (as long as 0.invert() = 0).
    pub fn to_montgomery(self, is_expected_non_identity: bool) -> (T, T) {
        // send (x, y) to the Montgomery curve
        let neg_t = -T::from(BaseField::from_le_bytes(CURVE25519_T));
        // note: the only point with y-coordinate equal to 1 is the identity
        let u = (T::from(BaseField::ONE) + self.y)
            * (T::from(BaseField::ONE) - self.y)
                .invert(self.is_on_curve && is_expected_non_identity);
        // the identity and the 2-torsion point P = (0, -1) have x-coordinate 0
        let v = neg_t
            * u
            * self
                .x
                .invert(self.is_on_curve && self.is_ell_torsion && is_expected_non_identity);
        (u, v)
    }

    pub fn try_from_y<B: Boolean + Select<T, T, T>>(y: T) -> (B, Self)
    where
        T: GetBit<Output = B> + Equal<T, Output = B> + From<B>,
    {
        let y2 = y * y;
        // here, the base is non-zero (because -d * y2 is a quadratic non-residue)
        let b = (T::from(BaseField::ONE) + T::from(BaseField::from_le_bytes(EDWARDS25519_D)) * y2)
            .invert(true);
        let y2_minus_one = y2 - T::from(BaseField::ONE);
        let x2 = y2_minus_one * b;
        // x^2 could be zero, namely if y = 1 (the y-coordinate of the identity) or if y = -1 (the
        // y-coordinate of the 2-torsion point). We therefore need to set is_expected_non_zero =
        // false when calling the square-root function. However, if we mask x^2 with
        // y^2 - 1 == 0 we can set is_expected_non_zero = true and save a couple of rounds compared
        // to calling sqrt(x2, false), which would compute x^2 == 0.
        let is_zero = y2_minus_one.eq(T::from(0));
        let (is_on_curve, x) = sqrt::<BaseField, B, T>(x2 + T::from(is_zero), true);
        let x = x - T::from(is_zero);
        // we don't know the bools is_on_curve and is_ell_torsion at compile time
        (is_on_curve, Self::new((x, y), false, false))
    }

    /// The point of order 8 with smallest y-coordinate (a 251-bit number).
    pub fn eight_torsion_point() -> Self {
        Self::new(
            (
                T::from(BaseField::from_le_bytes(EDWARDS25519_Q_X)),
                T::from(BaseField::from_le_bytes(EDWARDS25519_Q_Y)),
            ),
            true,
            false,
        )
    }
}

impl<T: F25519> Add for AffineEdwardsPoint<T> {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        let addition_circuit = AffineEdwardsPointAdditionCircuit::<BaseField>::new(
            BaseField::from_le_bytes(EDWARDS25519_D),
        );
        Self::new(
            addition_circuit.add(
                (self.inner(), self.is_on_curve),
                (rhs.inner(), rhs.is_on_curve),
            ),
            self.is_on_curve && rhs.is_on_curve,
            self.is_ell_torsion && rhs.is_ell_torsion,
        )
    }
}

impl<T: F25519> Sub for AffineEdwardsPoint<T> {
    type Output = Self;

    fn sub(self, rhs: Self) -> Self::Output {
        self + (-rhs)
    }
}

impl Mul<AffineEdwardsPoint<BaseField>> for ScalarField {
    type Output = AffineEdwardsPoint<BaseField>;

    fn mul(self, rhs: AffineEdwardsPoint<BaseField>) -> Self::Output {
        (self * rhs.to_projective()).to_affine()
    }
}

impl Mul<AffineEdwardsPoint<FieldValue<BaseField>>> for FieldValue<ScalarField> {
    type Output = AffineEdwardsPoint<FieldValue<BaseField>>;

    fn mul(self, rhs: AffineEdwardsPoint<FieldValue<BaseField>>) -> Self::Output {
        (self * rhs.to_projective()).to_affine()
    }
}

impl<T: F25519> Neg for AffineEdwardsPoint<T> {
    type Output = Self;

    fn neg(self) -> Self::Output {
        Self::new((-self.x, self.y), self.is_on_curve, self.is_ell_torsion)
    }
}

impl<T: F25519> Reveal for AffineEdwardsPoint<T> {
    fn reveal(self) -> Self {
        Self::new(
            (self.x.reveal(), self.y.reveal()),
            self.is_on_curve,
            self.is_ell_torsion,
        )
    }
}

/// Conversion from CurvePoint to affine coordinates.
/// Note: this clears the 4-torsion component of the representative of value, i.e.,
/// it returns a point of order ell.
impl From<CurvePoint> for AffineEdwardsPoint<BaseField> {
    fn from(value: CurvePoint) -> Self {
        let x = BaseField::unwrap(
            OtherExpr::PlaintextCurveToExtendedEdwards(value, 0)
                .eval()
                .unwrap(),
        );
        let y = BaseField::unwrap(
            OtherExpr::PlaintextCurveToExtendedEdwards(value, 1)
                .eval()
                .unwrap(),
        );
        Self::new((x, y), true, true)
    }
}

/// Projective point on the twisted Edwards25519 curve -X^2*Z^2 + Y^2*Z^2 = Z^4 + d*X^2*Y^2.
/// We set `is_on_curve: true` if we know the coordinates define a non-singular point on the curve.
/// We set `is_ell_torsion: true` if we know the coordinates define a \ell-torsion point.
/// Note: in the PP^2 closure, the points at infinity (1:0:0) and (0:1:0) satisfy the curve
/// equation, but they are singularities and the addition law is not well-defined.
#[derive(Debug, Clone, Copy)]
#[allow(non_snake_case)]
pub struct ProjectiveEdwardsPoint<T: F25519> {
    pub X: T,
    pub Y: T,
    pub Z: T,
    pub is_on_curve: bool,
    pub is_ell_torsion: bool,
}

#[allow(non_snake_case)]
impl<T: F25519> ProjectiveEdwardsPoint<T> {
    pub fn new(P: (T, T, T), is_on_curve: bool, is_ell_torsion: bool) -> Self {
        assert!(
            is_on_curve || !is_ell_torsion,
            "A point that is not on the curve cannot be a ell-torsion point."
        );
        Self {
            X: P.0,
            Y: P.1,
            Z: P.2,
            is_on_curve,
            is_ell_torsion,
        }
    }

    pub fn inner(&self) -> (T, T, T) {
        (self.X, self.Y, self.Z)
    }

    pub fn identity() -> Self {
        Self::new((T::from(0), T::from(1), T::from(1)), true, true)
    }

    /// Generator of the cryptographic prime order group.
    pub fn generator() -> Self {
        Self::new(
            (
                T::from(BaseField::from_le_bytes(EDWARDS25519_G_X)),
                T::from(BaseField::from_le_bytes(EDWARDS25519_G_Y)),
                T::from(1),
            ),
            true,
            true,
        )
    }

    /// The point of order 8 with smallest y-coordinate (a 251-bit number).
    pub fn eight_torsion_point() -> Self {
        Self::new(
            (
                T::from(BaseField::from_le_bytes(EDWARDS25519_Q_X)),
                T::from(BaseField::from_le_bytes(EDWARDS25519_Q_Y)),
                T::from(1),
            ),
            true,
            false,
        )
    }

    /// Random 8-torsion point.
    pub fn random_eight_torsion_point<B: Boolean + Select<T, T, T>>() -> Self {
        let rand = (0..3).map(|_| B::random()).collect::<Vec<B>>();
        ProjectiveEdwardsPoint::eight_torsion_point().mul_bits(rand)
    }

    pub fn to_affine(self) -> AffineEdwardsPoint<T> {
        let Z_inv = self.Z.invert(self.is_on_curve);
        AffineEdwardsPoint::new(
            (self.X * Z_inv, self.Y * Z_inv),
            self.is_on_curve,
            self.is_ell_torsion,
        )
    }

    pub fn mul_str(&self, k: &str) -> Self {
        let multiplication_circuit = ProjectiveEdwards25519MultiplicationCircuit::new();
        Self::new(
            multiplication_circuit.mul_str(k, self.inner(), CircuitType::default()),
            self.is_on_curve,
            self.is_ell_torsion,
        )
    }

    /// Performs the multiplication k * P, where k_bits is an array of secret-shared bits and P is a
    /// projective point on Edwards25519.
    pub fn mul_bits<B: Boolean + Select<T, T, T>>(&self, k_bits: Vec<B>) -> Self {
        let multiplication_circuit = ProjectiveEdwards25519MultiplicationCircuit::new();
        Self::new(
            multiplication_circuit.mul_bits(k_bits, self.inner(), CircuitType::default()),
            self.is_on_curve,
            self.is_ell_torsion,
        )
    }

    /// Performs the multiplication k * G, where k_bits is an array of secret-shared bits and G is
    /// the fixed generator of the cyclic subgroup of Edwards25519 of prime order ell.
    pub fn mul_bits_generator<B: Boolean + Select<T, T, T>>(k_bits: Vec<B>) -> Self {
        let multiplication_circuit = ProjectiveEdwards25519MultiplicationCircuit::new();
        Self::new(
            multiplication_circuit.mul_bits_generator(k_bits, CircuitType::default()),
            true,
            true,
        )
    }

    /// Performs the clamped multiplication (2^251 + k) * 8 * self, where k is a 251-bit number.
    pub fn mul_clamped<B: Boolean + Select<T, T, T>>(
        &self,
        k: [B; 251],
    ) -> ProjectiveEdwardsPoint<T>
    where
        T: GetBit<Output = B>,
    {
        let mut k_bits = vec![B::from(false); 3];
        k_bits.extend(k.iter());
        k_bits.push(B::from(true));
        self.mul_bits(k_bits)
    }
}

impl ProjectiveEdwardsPoint<BaseField> {
    /// Verifies if self is the identity.
    fn is_identity(&self) -> bool {
        self.is_on_curve && self.Z != BaseField::ZERO && self.Y == self.Z
    }
}

impl<T: F25519> Add for ProjectiveEdwardsPoint<T> {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        let addition_circuit = ProjectiveEdwardsPointAdditionCircuit::<BaseField>::new(
            BaseField::from_le_bytes(EDWARDS25519_D),
        );
        Self::new(
            addition_circuit.add(self.inner(), rhs.inner()),
            self.is_on_curve && rhs.is_on_curve,
            self.is_ell_torsion && rhs.is_ell_torsion,
        )
    }
}

impl<T: F25519> Sub for ProjectiveEdwardsPoint<T> {
    type Output = Self;

    fn sub(self, rhs: Self) -> Self::Output {
        self + (-rhs)
    }
}

impl Mul<ProjectiveEdwardsPoint<BaseField>> for ScalarField {
    type Output = ProjectiveEdwardsPoint<BaseField>;

    fn mul(self, rhs: ProjectiveEdwardsPoint<BaseField>) -> Self::Output {
        let multiplication_circuit = ProjectiveEdwards25519MultiplicationCircuit::new();
        Self::Output::new(
            multiplication_circuit.mul(self, rhs.inner(), CircuitType::default()),
            rhs.is_on_curve,
            rhs.is_ell_torsion,
        )
    }
}

impl Mul<ProjectiveEdwardsPoint<FieldValue<BaseField>>> for FieldValue<ScalarField> {
    type Output = ProjectiveEdwardsPoint<FieldValue<BaseField>>;

    fn mul(self, rhs: ProjectiveEdwardsPoint<FieldValue<BaseField>>) -> Self::Output {
        let multiplication_circuit = ProjectiveEdwards25519MultiplicationCircuit::new();
        Self::Output::new(
            multiplication_circuit.mul(self, rhs.inner(), CircuitType::default()),
            rhs.is_on_curve,
            rhs.is_ell_torsion,
        )
    }
}

impl<T: F25519> Neg for ProjectiveEdwardsPoint<T> {
    type Output = Self;

    fn neg(self) -> Self::Output {
        Self::new(
            (-self.X, self.Y, self.Z),
            self.is_on_curve,
            self.is_ell_torsion,
        )
    }
}

impl<T: F25519> Reveal for ProjectiveEdwardsPoint<T> {
    fn reveal(self) -> Self {
        Self::new(
            (self.X.reveal(), self.Y.reveal(), self.Z.reveal()),
            self.is_on_curve,
            self.is_ell_torsion,
        )
    }
}

impl PartialEq for ProjectiveEdwardsPoint<BaseField> {
    fn eq(&self, other: &Self) -> bool {
        self.is_on_curve
            && other.is_on_curve
            && self.X * other.Z == other.X * self.Z
            && self.Y * other.Z == other.Y * self.Z
    }
}

pub fn decompress_montgomery_u<
    T: F25519 + GetBit<Output = B> + Equal<T, Output = B> + From<B>,
    B: Boolean + Select<T, T, T>,
>(
    u: T,
) -> (B, (T, T)) {
    let (is_on_curve, v) = sqrt::<BaseField, B, T>(
        u * u * u + T::from(BaseField::from_le_bytes(CURVE25519_A)) * u * u + u,
        // u is the only root of the polynomial
        false,
    );
    (is_on_curve, (u, v))
}

#[allow(non_snake_case)]
/// Returns the affine Montogmery coordinates if bytes is a valid x25519 public key, and None
/// otherwise.
pub fn is_valid_x25519_public_key(bytes: [u8; 32]) -> Option<(BaseField, BaseField)> {
    match BaseField::from_le_bytes_checked(bytes) {
        Some(u) => {
            if u == BaseField::ZERO {
                // In this case `u` corresponds to the point at infinity or to the point of order 2.
                // Note that `u` cannot be the identity since the public key is obtained by a
                // clamped multiplication between 32 random bytes and the generator.
                // The clamped scalar is a 255-bit multiple of 8. Yet, the lcm of 8
                // and \ell is 8 * \ell and is 256 bits long.
                None
            } else if u == BaseField::ONE {
                // In this case `u` corresponds to a point of order 4.
                None
            } else if u
                == BaseField::from_le_bytes([
                    0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae, 0x16, 0x56, 0xe3, 0xfa, 0xf1,
                    0x9f, 0xc4, 0x6a, 0xda, 0x9, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd, 0x86, 0x62,
                    0x5, 0x16, 0x5f, 0x49, 0xb8, 0x0,
                ])
                || u == BaseField::from_le_bytes([
                    0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24, 0xb1, 0xd0, 0xb1, 0x55, 0x9c,
                    0x83, 0xef, 0x5b, 0x4, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86, 0xd8, 0x22,
                    0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57,
                ])
            {
                // In this case `u` corresponds to a point of order 8.
                None
            } else if u == BaseField::from(9) {
                // In this case `u` corresponds to the generator G. This is not possible since the
                // public key is obtained by a clamped multiplication between 32
                // random bytes and the generator. The clamped scalar is a 255-bit
                // multiple of 8. None of the 255-bit numbers 4 * \ell + 1, .., 7 *
                // \ell + 1 is a multiple of 8.
                None
            } else {
                let (is_on_curve, (u, v)) = decompress_montgomery_u(u);
                if is_on_curve {
                    let mut P =
                        AffineEdwardsPoint::<BaseField>::from_montgomery((u, v)).to_projective();
                    P.is_on_curve = true;
                    if P.mul_str(ELL_BIN).is_identity() {
                        Some((u, v))
                    } else {
                        None
                    }
                } else {
                    None
                }
            }
        }
        None => None,
    }
}

#[allow(non_snake_case)]
/// Verify that `bytes` is a valid ed25519 signature.
pub fn is_valid_signature(bytes: [u8; 64]) -> bool {
    let mut R_encoded = bytes.to_vec();
    let S = R_encoded.split_off(32);
    let x_lsb = R_encoded[31] >> 7;
    // clear the bit x_lsb
    R_encoded[31] &= 127;
    match (
        BaseField::from_le_bytes_checked(R_encoded.try_into().unwrap_or_else(|v: Vec<u8>| {
            panic!("Expected a Vec of length 32 (found {})", v.len())
        })),
        ScalarField::from_le_bytes_checked(S.try_into().unwrap_or_else(|v: Vec<u8>| {
            panic!("Expected a Vec of length 32 (found {})", v.len())
        })),
    ) {
        (Some(y), Some(_)) => {
            if y == BaseField::ONE && x_lsb == 1u8 {
                // In this case `y` corresponds to the identity, whose x-coordinate has lsb = 0.
                false
            } else if y == -BaseField::ONE {
                // In this case `y` corresponds to the point of order 2.
                false
            } else if y == BaseField::ZERO {
                // In this case `y` corresponds to a point of order 4.
                false
            } else if y
                == BaseField::from_le_bytes([
                    0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2,
                    0xef, 0x98, 0xf0, 0xd5, 0xdf, 0xac, 0x5, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38,
                    0x2, 0x88, 0x6d, 0x53, 0xfc, 0x5,
                ])
                || y == -BaseField::from_le_bytes([
                    0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2,
                    0xef, 0x98, 0xf0, 0xd5, 0xdf, 0xac, 0x5, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38,
                    0x2, 0x88, 0x6d, 0x53, 0xfc, 0x5,
                ])
            {
                // In this case `y` corresponds to a point of order 8.
                false
            } else {
                let (is_on_curve, mut P) = AffineEdwardsPoint::try_from_y(y);
                if is_on_curve {
                    P.is_on_curve = true;
                    P.to_projective().mul_str(ELL_BIN).is_identity()
                } else {
                    false
                }
            }
        }
        _ => false,
    }
}

#[test]
#[allow(non_snake_case)]
fn test_is_valid_public_key() {
    // The below input is randomly generated and the outcome is validated against a sagemath
    // implementation.

    let bytes1 = [
        0xe5, 0xb5, 0xd4, 0xd0, 0x79, 0x1f, 0xe5, 0xe3, 0x5d, 0x6, 0x17, 0x1c, 0xda, 0x3d, 0x8,
        0xe, 0x8f, 0x5f, 0x8c, 0xe9, 0xc7, 0x97, 0xbe, 0x5f, 0x10, 0x1a, 0xa, 0x64, 0x52, 0x29,
        0x2d, 0x55,
    ];
    // point is on the curve but of order 4 * ell
    assert!(is_valid_x25519_public_key(bytes1).is_none());

    let bytes2 = [
        0x7c, 0xd, 0x4a, 0x2f, 0xa9, 0x5d, 0x5e, 0x3d, 0x8e, 0xc, 0xcc, 0xdd, 0x7, 0xb3, 0x14,
        0xcb, 0x6, 0x40, 0x56, 0x5a, 0xe5, 0xd, 0x1c, 0xc9, 0x67, 0xa7, 0xf2, 0xbc, 0x18, 0x46,
        0x4e, 0x69,
    ];
    // u2 does not correspond to a point on the curve
    assert!(is_valid_x25519_public_key(bytes2).is_none());

    let bytes3 = [
        0x9f, 0x5b, 0xe0, 0xf0, 0x6c, 0xea, 0xa2, 0x33, 0xcc, 0x1f, 0x64, 0xae, 0x36, 0xfa, 0x52,
        0x99, 0x8a, 0x1f, 0x23, 0xe, 0x3b, 0x8e, 0xd0, 0x29, 0x2d, 0x9e, 0x11, 0xff, 0x89, 0x33,
        0xcd, 0xd,
    ];
    // point is of prime order ell
    assert!(is_valid_x25519_public_key(bytes3).is_some());

    // generator G
    let bytes_G = [
        0x9, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
        0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
    ];
    assert!(is_valid_x25519_public_key(bytes_G).is_none());

    // generator G plus the 2-torsion point P = (0, 0)
    let bytes_G_plus_P = [
        0x12, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71,
        0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71, 0x1c, 0xc7, 0x71,
        0x1c, 0x47,
    ];
    assert!(is_valid_x25519_public_key(bytes_G_plus_P).is_none());
}

#[test]
#[allow(non_snake_case)]
fn test_is_valid_signature() {
    let mut sig1 = [
        0x31, 0xa1, 0x2d, 0x8e, 0x69, 0xcf, 0x4, 0xd3, 0xf9, 0x64, 0x1d, 0x3a, 0xee, 0x59, 0x1d,
        0xca, 0x45, 0x5a, 0x3f, 0xcf, 0xc4, 0xa7, 0x3c, 0x58, 0x8a, 0x8, 0xbb, 0x33, 0xae, 0x46,
        0xd7, 0x1f, 0x61, 0x70, 0xba, 0xed, 0x32, 0x88, 0x30, 0xb9, 0x95, 0x45, 0x3b, 0x6e, 0xc0,
        0xcc, 0x9e, 0xfc, 0xd, 0xd6, 0x1b, 0x94, 0xd9, 0xef, 0x1, 0xa2, 0xfa, 0xe9, 0xac, 0x69,
        0xf, 0x7a, 0x91, 0x5,
    ];
    assert!(is_valid_signature(sig1));

    // this makes S greater than ell
    sig1[63] |= 64;
    assert!(!is_valid_signature(sig1));

    let mut sig2 = [
        0xc1, 0xf7, 0xe5, 0x88, 0x54, 0x6d, 0x72, 0xb, 0xd2, 0xb9, 0x1, 0x98, 0xc8, 0x8d, 0xf3,
        0xd0, 0x67, 0x78, 0x4, 0x25, 0x84, 0xb9, 0xd5, 0xab, 0x5c, 0x8a, 0xd, 0x48, 0x4f, 0xac,
        0x5d, 0x30, 0x45, 0x7, 0x15, 0xaa, 0xbf, 0xd0, 0x7, 0x48, 0x49, 0xf, 0xb, 0xb1, 0x96, 0xb8,
        0x28, 0x36, 0x22, 0xdd, 0xf9, 0xb9, 0xe0, 0xe6, 0x2b, 0x21, 0x36, 0x57, 0x9b, 0xc5, 0x5c,
        0xa2, 0x26, 0x5,
    ];
    assert!(is_valid_signature(sig2));

    // this makes S greater than ell
    sig2[63] |= 128;
    assert!(!is_valid_signature(sig2));
}