diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-18 02:49:50 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-18 02:49:50 +0000 |
commit | 9835e2ae736235810b4ea1c162ca5e65c547e770 (patch) | |
tree | 3fcebf40ed70e581d776a8a4c65923e8ec20e026 /vendor/primeorder/src/projective.rs | |
parent | Releasing progress-linux version 1.70.0+dfsg2-1~progress7.99u1. (diff) | |
download | rustc-9835e2ae736235810b4ea1c162ca5e65c547e770.tar.xz rustc-9835e2ae736235810b4ea1c162ca5e65c547e770.zip |
Merging upstream version 1.71.1+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/primeorder/src/projective.rs')
-rw-r--r-- | vendor/primeorder/src/projective.rs | 696 |
1 files changed, 696 insertions, 0 deletions
diff --git a/vendor/primeorder/src/projective.rs b/vendor/primeorder/src/projective.rs new file mode 100644 index 000000000..5549543fc --- /dev/null +++ b/vendor/primeorder/src/projective.rs @@ -0,0 +1,696 @@ +//! Projective curve points. + +#![allow(clippy::needless_range_loop, clippy::op_ref)] + +use crate::{point_arithmetic::PointArithmetic, AffinePoint, Field, PrimeCurveParams}; +use core::{ + borrow::Borrow, + iter::Sum, + ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign}, +}; +use elliptic_curve::{ + bigint::{ArrayEncoding, Integer}, + generic_array::ArrayLength, + group::{ + self, + cofactor::CofactorGroup, + prime::{PrimeCurve, PrimeGroup}, + Group, GroupEncoding, + }, + ops::{LinearCombination, MulByGenerator}, + point::Double, + rand_core::RngCore, + sec1::{ + CompressedPoint, EncodedPoint, FromEncodedPoint, ModulusSize, ToEncodedPoint, + UncompressedPointSize, + }, + subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption}, + zeroize::DefaultIsZeroes, + Error, FieldBytes, FieldBytesSize, PublicKey, Result, Scalar, +}; + +/// Point on a Weierstrass curve in projective coordinates. +#[derive(Clone, Copy, Debug)] +pub struct ProjectivePoint<C: PrimeCurveParams> { + pub(crate) x: C::FieldElement, + pub(crate) y: C::FieldElement, + pub(crate) z: C::FieldElement, +} + +impl<C> ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + /// Additive identity of the group a.k.a. the point at infinity. + pub const IDENTITY: Self = Self { + x: C::FieldElement::ZERO, + y: C::FieldElement::ONE, + z: C::FieldElement::ZERO, + }; + + /// Base point of the curve. + pub const GENERATOR: Self = Self { + x: C::GENERATOR.0, + y: C::GENERATOR.1, + z: C::FieldElement::ONE, + }; + + /// Returns the affine representation of this point, or `None` if it is the identity. + pub fn to_affine(&self) -> AffinePoint<C> { + self.z + .invert() + .map(|zinv| AffinePoint { + x: self.x * &zinv, + y: self.y * &zinv, + infinity: 0, + }) + .unwrap_or(AffinePoint::IDENTITY) + } + + /// Returns `-self`. + pub fn neg(&self) -> Self { + Self { + x: self.x, + y: -self.y, + z: self.z, + } + } + + /// Returns `self + other`. + pub fn add(&self, other: &Self) -> Self { + C::PointArithmetic::add(self, other) + } + + /// Returns `self + other`. + fn add_mixed(&self, other: &AffinePoint<C>) -> Self { + C::PointArithmetic::add_mixed(self, other) + } + + /// Returns `self - other`. + pub fn sub(&self, other: &Self) -> Self { + self.add(&other.neg()) + } + + /// Returns `self - other`. + fn sub_mixed(&self, other: &AffinePoint<C>) -> Self { + self.add_mixed(&other.neg()) + } + + /// Returns `[k] self`. + fn mul(&self, k: &Scalar<C>) -> Self + where + Self: Double, + { + let k = Into::<C::Uint>::into(*k).to_le_byte_array(); + + let mut pc = [Self::default(); 16]; + pc[0] = Self::IDENTITY; + pc[1] = *self; + + for i in 2..16 { + pc[i] = if i % 2 == 0 { + Double::double(&pc[i / 2]) + } else { + pc[i - 1].add(self) + }; + } + + let mut q = Self::IDENTITY; + let mut pos = C::Uint::BITS - 4; + + loop { + let slot = (k[pos >> 3] >> (pos & 7)) & 0xf; + + let mut t = ProjectivePoint::IDENTITY; + + for i in 1..16 { + t.conditional_assign( + &pc[i], + Choice::from(((slot as usize ^ i).wrapping_sub(1) >> 8) as u8 & 1), + ); + } + + q = q.add(&t); + + if pos == 0 { + break; + } + + q = Double::double(&Double::double(&Double::double(&Double::double(&q)))); + pos -= 4; + } + + q + } +} + +impl<C> CofactorGroup for ProjectivePoint<C> +where + Self: Double, + C: PrimeCurveParams, + FieldBytes<C>: Copy, + FieldBytesSize<C>: ModulusSize, + CompressedPoint<C>: Copy, + <UncompressedPointSize<C> as ArrayLength<u8>>::ArrayType: Copy, +{ + type Subgroup = Self; + + fn clear_cofactor(&self) -> Self::Subgroup { + *self + } + + fn into_subgroup(self) -> CtOption<Self> { + CtOption::new(self, 1.into()) + } + + fn is_torsion_free(&self) -> Choice { + 1.into() + } +} + +impl<C> ConditionallySelectable for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self { + Self { + x: C::FieldElement::conditional_select(&a.x, &b.x, choice), + y: C::FieldElement::conditional_select(&a.y, &b.y, choice), + z: C::FieldElement::conditional_select(&a.z, &b.z, choice), + } + } +} + +impl<C> ConstantTimeEq for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn ct_eq(&self, other: &Self) -> Choice { + self.to_affine().ct_eq(&other.to_affine()) + } +} + +impl<C> Default for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn default() -> Self { + Self::IDENTITY + } +} + +impl<C> DefaultIsZeroes for ProjectivePoint<C> where C: PrimeCurveParams {} + +impl<C: PrimeCurveParams> Double for ProjectivePoint<C> { + fn double(&self) -> Self { + C::PointArithmetic::double(self) + } +} + +impl<C> Eq for ProjectivePoint<C> where C: PrimeCurveParams {} + +impl<C> From<AffinePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn from(p: AffinePoint<C>) -> Self { + let projective = ProjectivePoint { + x: p.x, + y: p.y, + z: C::FieldElement::ONE, + }; + Self::conditional_select(&projective, &Self::IDENTITY, p.is_identity()) + } +} + +impl<C> From<&AffinePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn from(p: &AffinePoint<C>) -> Self { + Self::from(*p) + } +} + +impl<C> From<PublicKey<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn from(public_key: PublicKey<C>) -> ProjectivePoint<C> { + AffinePoint::from(public_key).into() + } +} + +impl<C> From<&PublicKey<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn from(public_key: &PublicKey<C>) -> ProjectivePoint<C> { + AffinePoint::<C>::from(public_key).into() + } +} + +impl<C> FromEncodedPoint<C> for ProjectivePoint<C> +where + C: PrimeCurveParams, + FieldBytes<C>: Copy, + FieldBytesSize<C>: ModulusSize, + CompressedPoint<C>: Copy, +{ + fn from_encoded_point(p: &EncodedPoint<C>) -> CtOption<Self> { + AffinePoint::<C>::from_encoded_point(p).map(Self::from) + } +} + +impl<C> Group for ProjectivePoint<C> +where + Self: Double, + C: PrimeCurveParams, +{ + type Scalar = Scalar<C>; + + fn random(mut rng: impl RngCore) -> Self { + Self::GENERATOR * <Scalar<C> as Field>::random(&mut rng) + } + + fn identity() -> Self { + Self::IDENTITY + } + + fn generator() -> Self { + Self::GENERATOR + } + + fn is_identity(&self) -> Choice { + self.ct_eq(&Self::IDENTITY) + } + + #[must_use] + fn double(&self) -> Self { + Double::double(self) + } +} + +impl<C> GroupEncoding for ProjectivePoint<C> +where + C: PrimeCurveParams, + FieldBytes<C>: Copy, + FieldBytesSize<C>: ModulusSize, + CompressedPoint<C>: Copy, + <UncompressedPointSize<C> as ArrayLength<u8>>::ArrayType: Copy, +{ + type Repr = CompressedPoint<C>; + + fn from_bytes(bytes: &Self::Repr) -> CtOption<Self> { + <AffinePoint<C> as GroupEncoding>::from_bytes(bytes).map(Into::into) + } + + fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption<Self> { + // No unchecked conversion possible for compressed points + Self::from_bytes(bytes) + } + + fn to_bytes(&self) -> Self::Repr { + self.to_affine().to_bytes() + } +} + +impl<C> group::Curve for ProjectivePoint<C> +where + Self: Double, + C: PrimeCurveParams, +{ + type AffineRepr = AffinePoint<C>; + + fn to_affine(&self) -> AffinePoint<C> { + ProjectivePoint::to_affine(self) + } +} + +impl<C> LinearCombination for ProjectivePoint<C> +where + Self: Double, + C: PrimeCurveParams, +{ +} + +impl<C> MulByGenerator for ProjectivePoint<C> +where + Self: Double, + C: PrimeCurveParams, +{ + fn mul_by_generator(scalar: &Self::Scalar) -> Self { + // TODO(tarcieri): precomputed basepoint tables + Self::generator() * scalar + } +} + +impl<C> PrimeGroup for ProjectivePoint<C> +where + Self: Double, + C: PrimeCurveParams, + FieldBytes<C>: Copy, + FieldBytesSize<C>: ModulusSize, + CompressedPoint<C>: Copy, + <UncompressedPointSize<C> as ArrayLength<u8>>::ArrayType: Copy, +{ +} + +impl<C> PrimeCurve for ProjectivePoint<C> +where + Self: Double, + C: PrimeCurveParams, + FieldBytes<C>: Copy, + FieldBytesSize<C>: ModulusSize, + CompressedPoint<C>: Copy, + <UncompressedPointSize<C> as ArrayLength<u8>>::ArrayType: Copy, +{ + type Affine = AffinePoint<C>; +} + +impl<C> PartialEq for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn eq(&self, other: &Self) -> bool { + self.ct_eq(other).into() + } +} + +impl<C> ToEncodedPoint<C> for ProjectivePoint<C> +where + C: PrimeCurveParams, + FieldBytesSize<C>: ModulusSize, + CompressedPoint<C>: Copy, + <UncompressedPointSize<C> as ArrayLength<u8>>::ArrayType: Copy, +{ + fn to_encoded_point(&self, compress: bool) -> EncodedPoint<C> { + self.to_affine().to_encoded_point(compress) + } +} + +impl<C> TryFrom<ProjectivePoint<C>> for PublicKey<C> +where + C: PrimeCurveParams, +{ + type Error = Error; + + fn try_from(point: ProjectivePoint<C>) -> Result<PublicKey<C>> { + AffinePoint::<C>::from(point).try_into() + } +} + +impl<C> TryFrom<&ProjectivePoint<C>> for PublicKey<C> +where + C: PrimeCurveParams, +{ + type Error = Error; + + fn try_from(point: &ProjectivePoint<C>) -> Result<PublicKey<C>> { + AffinePoint::<C>::from(point).try_into() + } +} + +// +// Arithmetic trait impls +// + +impl<C> Add<ProjectivePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn add(self, other: ProjectivePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::add(&self, &other) + } +} + +impl<C> Add<&ProjectivePoint<C>> for &ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn add(self, other: &ProjectivePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::add(self, other) + } +} + +impl<C> Add<&ProjectivePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn add(self, other: &ProjectivePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::add(&self, other) + } +} + +impl<C> AddAssign<ProjectivePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn add_assign(&mut self, rhs: ProjectivePoint<C>) { + *self = ProjectivePoint::add(self, &rhs); + } +} + +impl<C> AddAssign<&ProjectivePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn add_assign(&mut self, rhs: &ProjectivePoint<C>) { + *self = ProjectivePoint::add(self, rhs); + } +} + +impl<C> Add<AffinePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn add(self, other: AffinePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::add_mixed(&self, &other) + } +} + +impl<C> Add<&AffinePoint<C>> for &ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn add(self, other: &AffinePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::add_mixed(self, other) + } +} + +impl<C> Add<&AffinePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn add(self, other: &AffinePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::add_mixed(&self, other) + } +} + +impl<C> AddAssign<AffinePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn add_assign(&mut self, rhs: AffinePoint<C>) { + *self = ProjectivePoint::add_mixed(self, &rhs); + } +} + +impl<C> AddAssign<&AffinePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn add_assign(&mut self, rhs: &AffinePoint<C>) { + *self = ProjectivePoint::add_mixed(self, rhs); + } +} + +impl<C> Sum for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn sum<I: Iterator<Item = Self>>(iter: I) -> Self { + iter.fold(ProjectivePoint::IDENTITY, |a, b| a + b) + } +} + +impl<'a, C> Sum<&'a ProjectivePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn sum<I: Iterator<Item = &'a ProjectivePoint<C>>>(iter: I) -> Self { + iter.cloned().sum() + } +} + +impl<C> Sub<ProjectivePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn sub(self, other: ProjectivePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::sub(&self, &other) + } +} + +impl<C> Sub<&ProjectivePoint<C>> for &ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn sub(self, other: &ProjectivePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::sub(self, other) + } +} + +impl<C> Sub<&ProjectivePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn sub(self, other: &ProjectivePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::sub(&self, other) + } +} + +impl<C> SubAssign<ProjectivePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn sub_assign(&mut self, rhs: ProjectivePoint<C>) { + *self = ProjectivePoint::sub(self, &rhs); + } +} + +impl<C> SubAssign<&ProjectivePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn sub_assign(&mut self, rhs: &ProjectivePoint<C>) { + *self = ProjectivePoint::sub(self, rhs); + } +} + +impl<C> Sub<AffinePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn sub(self, other: AffinePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::sub_mixed(&self, &other) + } +} + +impl<C> Sub<&AffinePoint<C>> for &ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn sub(self, other: &AffinePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::sub_mixed(self, other) + } +} + +impl<C> Sub<&AffinePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn sub(self, other: &AffinePoint<C>) -> ProjectivePoint<C> { + ProjectivePoint::sub_mixed(&self, other) + } +} + +impl<C> SubAssign<AffinePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn sub_assign(&mut self, rhs: AffinePoint<C>) { + *self = ProjectivePoint::sub_mixed(self, &rhs); + } +} + +impl<C> SubAssign<&AffinePoint<C>> for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + fn sub_assign(&mut self, rhs: &AffinePoint<C>) { + *self = ProjectivePoint::sub_mixed(self, rhs); + } +} + +impl<C, S> Mul<S> for ProjectivePoint<C> +where + Self: Double, + C: PrimeCurveParams, + S: Borrow<Scalar<C>>, +{ + type Output = Self; + + fn mul(self, scalar: S) -> Self { + ProjectivePoint::mul(&self, scalar.borrow()) + } +} + +impl<C> Mul<&Scalar<C>> for &ProjectivePoint<C> +where + C: PrimeCurveParams, + ProjectivePoint<C>: Double, +{ + type Output = ProjectivePoint<C>; + + fn mul(self, scalar: &Scalar<C>) -> ProjectivePoint<C> { + ProjectivePoint::mul(self, scalar) + } +} + +impl<C, S> MulAssign<S> for ProjectivePoint<C> +where + Self: Double, + C: PrimeCurveParams, + S: Borrow<Scalar<C>>, +{ + fn mul_assign(&mut self, scalar: S) { + *self = ProjectivePoint::mul(self, scalar.borrow()); + } +} + +impl<C> Neg for ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn neg(self) -> ProjectivePoint<C> { + ProjectivePoint::neg(&self) + } +} + +impl<'a, C> Neg for &'a ProjectivePoint<C> +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint<C>; + + fn neg(self) -> ProjectivePoint<C> { + ProjectivePoint::neg(self) + } +} |