use super::{AffinePoint, FieldElement, Scalar, CURVE_EQUATION_B};
use crate::NistP256;
use core::{
iter::Sum,
ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
};
use elliptic_curve::{
ff::Field,
group::{Curve, Group},
point::ProjectiveArithmetic,
rand_core::RngCore,
subtle::{Choice, ConditionallySelectable, ConstantTimeEq},
};
impl ProjectiveArithmetic for NistP256 {
type ProjectivePoint = ProjectivePoint;
}
#[derive(Clone, Copy, Debug)]
#[cfg_attr(docsrs, doc(cfg(feature = "arithmetic")))]
pub struct ProjectivePoint {
x: FieldElement,
y: FieldElement,
z: FieldElement,
}
impl Group for ProjectivePoint {
type Scalar = Scalar;
fn random(mut rng: impl RngCore) -> Self {
Self::generator() * Scalar::random(&mut rng)
}
fn identity() -> Self {
ProjectivePoint::identity()
}
fn generator() -> Self {
ProjectivePoint::generator()
}
fn is_identity(&self) -> Choice {
self.ct_eq(&Self::identity())
}
#[must_use]
fn double(&self) -> Self {
ProjectivePoint::double(self)
}
}
impl Curve for ProjectivePoint {
type AffineRepr = AffinePoint;
fn to_affine(&self) -> AffinePoint {
ProjectivePoint::to_affine(self)
}
}
impl From<AffinePoint> for ProjectivePoint {
fn from(p: AffinePoint) -> Self {
let projective = ProjectivePoint {
x: p.x,
y: p.y,
z: FieldElement::one(),
};
Self::conditional_select(&projective, &Self::identity(), p.infinity)
}
}
impl ConditionallySelectable for ProjectivePoint {
fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
ProjectivePoint {
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),
}
}
}
impl ConstantTimeEq for ProjectivePoint {
fn ct_eq(&self, other: &Self) -> Choice {
self.to_affine().ct_eq(&other.to_affine())
}
}
impl PartialEq for ProjectivePoint {
fn eq(&self, other: &Self) -> bool {
self.ct_eq(other).into()
}
}
impl Eq for ProjectivePoint {}
impl ProjectivePoint {
pub const fn identity() -> ProjectivePoint {
ProjectivePoint {
x: FieldElement::zero(),
y: FieldElement::one(),
z: FieldElement::zero(),
}
}
pub fn generator() -> ProjectivePoint {
AffinePoint::generator().into()
}
pub fn to_affine(&self) -> AffinePoint {
self.z
.invert()
.map(|zinv| AffinePoint {
x: self.x * &zinv,
y: self.y * &zinv,
infinity: Choice::from(0),
})
.unwrap_or_else(AffinePoint::identity)
}
fn neg(&self) -> ProjectivePoint {
ProjectivePoint {
x: self.x,
y: self.y.neg(),
z: self.z,
}
}
fn add(&self, other: &ProjectivePoint) -> ProjectivePoint {
let xx = self.x * &other.x;
let yy = self.y * &other.y;
let zz = self.z * &other.z;
let xy_pairs = ((self.x + &self.y) * &(other.x + &other.y)) - &(xx + &yy);
let yz_pairs = ((self.y + &self.z) * &(other.y + &other.z)) - &(yy + &zz);
let xz_pairs = ((self.x + &self.z) * &(other.x + &other.z)) - &(xx + &zz);
let bzz_part = xz_pairs - &(CURVE_EQUATION_B * &zz);
let bzz3_part = bzz_part.double() + &bzz_part;
let yy_m_bzz3 = yy - &bzz3_part;
let yy_p_bzz3 = yy + &bzz3_part;
let zz3 = zz.double() + &zz;
let bxz_part = (CURVE_EQUATION_B * &xz_pairs) - &(zz3 + &xx);
let bxz3_part = bxz_part.double() + &bxz_part;
let xx3_m_zz3 = xx.double() + &xx - &zz3;
ProjectivePoint {
x: (yy_p_bzz3 * &xy_pairs) - &(yz_pairs * &bxz3_part),
y: (yy_p_bzz3 * &yy_m_bzz3) + &(xx3_m_zz3 * &bxz3_part),
z: (yy_m_bzz3 * &yz_pairs) + &(xy_pairs * &xx3_m_zz3),
}
}
fn add_mixed(&self, other: &AffinePoint) -> ProjectivePoint {
let xx = self.x * &other.x;
let yy = self.y * &other.y;
let xy_pairs = ((self.x + &self.y) * &(other.x + &other.y)) - &(xx + &yy);
let yz_pairs = (other.y * &self.z) + &self.y;
let xz_pairs = (other.x * &self.z) + &self.x;
let bz_part = xz_pairs - &(CURVE_EQUATION_B * &self.z);
let bz3_part = bz_part.double() + &bz_part;
let yy_m_bzz3 = yy - &bz3_part;
let yy_p_bzz3 = yy + &bz3_part;
let z3 = self.z.double() + &self.z;
let bxz_part = (CURVE_EQUATION_B * &xz_pairs) - &(z3 + &xx);
let bxz3_part = bxz_part.double() + &bxz_part;
let xx3_m_zz3 = xx.double() + &xx - &z3;
ProjectivePoint {
x: (yy_p_bzz3 * &xy_pairs) - &(yz_pairs * &bxz3_part),
y: (yy_p_bzz3 * &yy_m_bzz3) + &(xx3_m_zz3 * &bxz3_part),
z: (yy_m_bzz3 * &yz_pairs) + &(xy_pairs * &xx3_m_zz3),
}
}
pub fn double(&self) -> ProjectivePoint {
let xx = self.x.square();
let yy = self.y.square();
let zz = self.z.square();
let xy2 = (self.x * &self.y).double();
let xz2 = (self.x * &self.z).double();
let bzz_part = (CURVE_EQUATION_B * &zz) - &xz2;
let bzz3_part = bzz_part.double() + &bzz_part;
let yy_m_bzz3 = yy - &bzz3_part;
let yy_p_bzz3 = yy + &bzz3_part;
let y_frag = yy_p_bzz3 * &yy_m_bzz3;
let x_frag = yy_m_bzz3 * &xy2;
let zz3 = zz.double() + &zz;
let bxz2_part = (CURVE_EQUATION_B * &xz2) - &(zz3 + &xx);
let bxz6_part = bxz2_part.double() + &bxz2_part;
let xx3_m_zz3 = xx.double() + &xx - &zz3;
let y = y_frag + &(xx3_m_zz3 * &bxz6_part);
let yz2 = (self.y * &self.z).double();
let x = x_frag - &(bxz6_part * &yz2);
let z = (yz2 * &yy).double().double();
ProjectivePoint { x, y, z }
}
fn sub(&self, other: &ProjectivePoint) -> ProjectivePoint {
self.add(&other.neg())
}
fn sub_mixed(&self, other: &AffinePoint) -> ProjectivePoint {
self.add_mixed(&other.neg())
}
fn mul(&self, k: &Scalar) -> ProjectivePoint {
let mut ret = ProjectivePoint::identity();
for limb in k.0.iter().rev() {
for i in (0..64).rev() {
ret = ret.double();
ret.conditional_assign(&(ret + self), Choice::from(((limb >> i) & 1u64) as u8));
}
}
ret
}
}
impl Default for ProjectivePoint {
fn default() -> Self {
Self::identity()
}
}
impl Add<ProjectivePoint> for ProjectivePoint {
type Output = ProjectivePoint;
fn add(self, other: ProjectivePoint) -> ProjectivePoint {
ProjectivePoint::add(&self, &other)
}
}
impl Add<&ProjectivePoint> for &ProjectivePoint {
type Output = ProjectivePoint;
fn add(self, other: &ProjectivePoint) -> ProjectivePoint {
ProjectivePoint::add(self, other)
}
}
impl Add<&ProjectivePoint> for ProjectivePoint {
type Output = ProjectivePoint;
fn add(self, other: &ProjectivePoint) -> ProjectivePoint {
ProjectivePoint::add(&self, other)
}
}
impl AddAssign<ProjectivePoint> for ProjectivePoint {
fn add_assign(&mut self, rhs: ProjectivePoint) {
*self = ProjectivePoint::add(self, &rhs);
}
}
impl AddAssign<&ProjectivePoint> for ProjectivePoint {
fn add_assign(&mut self, rhs: &ProjectivePoint) {
*self = ProjectivePoint::add(self, rhs);
}
}
impl Add<AffinePoint> for ProjectivePoint {
type Output = ProjectivePoint;
fn add(self, other: AffinePoint) -> ProjectivePoint {
ProjectivePoint::add_mixed(&self, &other)
}
}
impl Add<&AffinePoint> for &ProjectivePoint {
type Output = ProjectivePoint;
fn add(self, other: &AffinePoint) -> ProjectivePoint {
ProjectivePoint::add_mixed(self, other)
}
}
impl Add<&AffinePoint> for ProjectivePoint {
type Output = ProjectivePoint;
fn add(self, other: &AffinePoint) -> ProjectivePoint {
ProjectivePoint::add_mixed(&self, other)
}
}
impl AddAssign<AffinePoint> for ProjectivePoint {
fn add_assign(&mut self, rhs: AffinePoint) {
*self = ProjectivePoint::add_mixed(self, &rhs);
}
}
impl AddAssign<&AffinePoint> for ProjectivePoint {
fn add_assign(&mut self, rhs: &AffinePoint) {
*self = ProjectivePoint::add_mixed(self, rhs);
}
}
impl Sum for ProjectivePoint {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(ProjectivePoint::identity(), |a, b| a + b)
}
}
impl<'a> Sum<&'a ProjectivePoint> for ProjectivePoint {
fn sum<I: Iterator<Item = &'a ProjectivePoint>>(iter: I) -> Self {
iter.cloned().sum()
}
}
impl Sub<ProjectivePoint> for ProjectivePoint {
type Output = ProjectivePoint;
fn sub(self, other: ProjectivePoint) -> ProjectivePoint {
ProjectivePoint::sub(&self, &other)
}
}
impl Sub<&ProjectivePoint> for &ProjectivePoint {
type Output = ProjectivePoint;
fn sub(self, other: &ProjectivePoint) -> ProjectivePoint {
ProjectivePoint::sub(self, other)
}
}
impl Sub<&ProjectivePoint> for ProjectivePoint {
type Output = ProjectivePoint;
fn sub(self, other: &ProjectivePoint) -> ProjectivePoint {
ProjectivePoint::sub(&self, other)
}
}
impl SubAssign<ProjectivePoint> for ProjectivePoint {
fn sub_assign(&mut self, rhs: ProjectivePoint) {
*self = ProjectivePoint::sub(self, &rhs);
}
}
impl SubAssign<&ProjectivePoint> for ProjectivePoint {
fn sub_assign(&mut self, rhs: &ProjectivePoint) {
*self = ProjectivePoint::sub(self, rhs);
}
}
impl Sub<AffinePoint> for ProjectivePoint {
type Output = ProjectivePoint;
fn sub(self, other: AffinePoint) -> ProjectivePoint {
ProjectivePoint::sub_mixed(&self, &other)
}
}
impl Sub<&AffinePoint> for &ProjectivePoint {
type Output = ProjectivePoint;
fn sub(self, other: &AffinePoint) -> ProjectivePoint {
ProjectivePoint::sub_mixed(self, other)
}
}
impl Sub<&AffinePoint> for ProjectivePoint {
type Output = ProjectivePoint;
fn sub(self, other: &AffinePoint) -> ProjectivePoint {
ProjectivePoint::sub_mixed(&self, other)
}
}
impl SubAssign<AffinePoint> for ProjectivePoint {
fn sub_assign(&mut self, rhs: AffinePoint) {
*self = ProjectivePoint::sub_mixed(self, &rhs);
}
}
impl SubAssign<&AffinePoint> for ProjectivePoint {
fn sub_assign(&mut self, rhs: &AffinePoint) {
*self = ProjectivePoint::sub_mixed(self, rhs);
}
}
impl Mul<Scalar> for ProjectivePoint {
type Output = ProjectivePoint;
fn mul(self, other: Scalar) -> ProjectivePoint {
ProjectivePoint::mul(&self, &other)
}
}
impl Mul<&Scalar> for &ProjectivePoint {
type Output = ProjectivePoint;
fn mul(self, other: &Scalar) -> ProjectivePoint {
ProjectivePoint::mul(self, other)
}
}
impl Mul<&Scalar> for ProjectivePoint {
type Output = ProjectivePoint;
fn mul(self, other: &Scalar) -> ProjectivePoint {
ProjectivePoint::mul(&self, other)
}
}
impl MulAssign<Scalar> for ProjectivePoint {
fn mul_assign(&mut self, rhs: Scalar) {
*self = ProjectivePoint::mul(self, &rhs);
}
}
impl MulAssign<&Scalar> for ProjectivePoint {
fn mul_assign(&mut self, rhs: &Scalar) {
*self = ProjectivePoint::mul(self, rhs);
}
}
impl Neg for ProjectivePoint {
type Output = ProjectivePoint;
fn neg(self) -> ProjectivePoint {
ProjectivePoint::neg(&self)
}
}
impl<'a> Neg for &'a ProjectivePoint {
type Output = ProjectivePoint;
fn neg(self) -> ProjectivePoint {
ProjectivePoint::neg(self)
}
}
#[cfg(test)]
mod tests {
use super::{AffinePoint, ProjectivePoint, Scalar};
use crate::test_vectors::group::{ADD_TEST_VECTORS, MUL_TEST_VECTORS};
use elliptic_curve::ff::PrimeField;
#[test]
fn affine_to_projective() {
let basepoint_affine = AffinePoint::generator();
let basepoint_projective = ProjectivePoint::generator();
assert_eq!(
ProjectivePoint::from(basepoint_affine),
basepoint_projective,
);
assert_eq!(basepoint_projective.to_affine(), basepoint_affine);
assert!(!bool::from(basepoint_projective.to_affine().is_identity()));
assert!(bool::from(
ProjectivePoint::identity().to_affine().is_identity()
));
}
#[test]
fn projective_identity_addition() {
let identity = ProjectivePoint::identity();
let generator = ProjectivePoint::generator();
assert_eq!(identity + &generator, generator);
assert_eq!(generator + &identity, generator);
}
#[test]
fn projective_mixed_addition() {
let identity = ProjectivePoint::identity();
let basepoint_affine = AffinePoint::generator();
let basepoint_projective = ProjectivePoint::generator();
assert_eq!(identity + &basepoint_affine, basepoint_projective);
assert_eq!(
basepoint_projective + &basepoint_affine,
basepoint_projective + &basepoint_projective
);
}
#[test]
fn test_vector_repeated_add() {
let generator = ProjectivePoint::generator();
let mut p = generator;
for i in 0..ADD_TEST_VECTORS.len() {
let affine = p.to_affine();
let (expected_x, expected_y) = ADD_TEST_VECTORS[i];
assert_eq!(affine.x.to_bytes(), expected_x.into());
assert_eq!(affine.y.to_bytes(), expected_y.into());
p += &generator;
}
}
#[test]
fn test_vector_repeated_add_mixed() {
let generator = AffinePoint::generator();
let mut p = ProjectivePoint::generator();
for i in 0..ADD_TEST_VECTORS.len() {
let affine = p.to_affine();
let (expected_x, expected_y) = ADD_TEST_VECTORS[i];
assert_eq!(affine.x.to_bytes(), expected_x.into());
assert_eq!(affine.y.to_bytes(), expected_y.into());
p += &generator;
}
}
#[test]
fn test_vector_double_generator() {
let generator = ProjectivePoint::generator();
let mut p = generator;
for i in 0..2 {
let affine = p.to_affine();
let (expected_x, expected_y) = ADD_TEST_VECTORS[i];
assert_eq!(affine.x.to_bytes(), expected_x.into());
assert_eq!(affine.y.to_bytes(), expected_y.into());
p = p.double();
}
}
#[test]
fn projective_add_vs_double() {
let generator = ProjectivePoint::generator();
assert_eq!(generator + &generator, generator.double());
}
#[test]
fn projective_add_and_sub() {
let basepoint_affine = AffinePoint::generator();
let basepoint_projective = ProjectivePoint::generator();
assert_eq!(
(basepoint_projective + &basepoint_projective) - &basepoint_projective,
basepoint_projective
);
assert_eq!(
(basepoint_projective + &basepoint_affine) - &basepoint_affine,
basepoint_projective
);
}
#[test]
fn projective_double_and_sub() {
let generator = ProjectivePoint::generator();
assert_eq!(generator.double() - &generator, generator);
}
#[test]
fn test_vector_scalar_mult() {
let generator = ProjectivePoint::generator();
for (k, coords) in ADD_TEST_VECTORS
.iter()
.enumerate()
.map(|(k, coords)| (Scalar::from(k as u64 + 1), *coords))
.chain(
MUL_TEST_VECTORS
.iter()
.cloned()
.map(|(k, x, y)| (Scalar::from_repr(k.into()).unwrap(), (x, y))),
)
{
let res = (generator * &k).to_affine();
assert_eq!(res.x.to_bytes(), coords.0.into());
assert_eq!(res.y.to_bytes(), coords.1.into());
}
}
}