From 9918693037dce8aa4bb6f08741b6812923486c18 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 19 Jun 2024 11:26:03 +0200 Subject: Merging upstream version 1.76.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/primeorder/.cargo-checksum.json | 2 +- vendor/primeorder/CHANGELOG.md | 32 ++++++++++ vendor/primeorder/Cargo.toml | 10 +++- vendor/primeorder/README.md | 8 ++- vendor/primeorder/src/affine.rs | 1 + vendor/primeorder/src/dev.rs | 15 +++-- vendor/primeorder/src/lib.rs | 9 ++- vendor/primeorder/src/projective.rs | 103 ++++++++++++++++++++++++++++++--- 8 files changed, 159 insertions(+), 21 deletions(-) (limited to 'vendor/primeorder') diff --git a/vendor/primeorder/.cargo-checksum.json b/vendor/primeorder/.cargo-checksum.json index ed1f795c3..fdf42be7f 100644 --- a/vendor/primeorder/.cargo-checksum.json +++ b/vendor/primeorder/.cargo-checksum.json @@ -1 +1 @@ -{"files":{"CHANGELOG.md":"0ecc29c6d0cc860974f61d8c557b81c144782993824b8e8d20322aa09b812c8d","Cargo.toml":"a3117f188eeefe53c4d16e2393930f5b00135bf12fae98484a1c203a021e74f1","LICENSE-APACHE":"a9040321c3712d8fd0b09cf52b17445de04a23a10165049ae187cd39e5c86be5","LICENSE-MIT":"233b95ccbf90dc67e32f3e8995c489f6312d9191ebd141a931c3b684f1e3be6d","README.md":"06732c041b51df2884b78f4f7124c5034cdcd27c6990e472e330bfe917b54f76","src/affine.rs":"8c8c5b7c6fd9d4a1d11d5aaf548b82b4de84643288417aff631f2ee7d555e70a","src/dev.rs":"0b0c78e500e08bce6ef19833fd0010f2e5fc0d1ba91acd2508874ab1598f9129","src/field.rs":"5a3c9bb09c21cafb56032374d99be8494d7bf482253e701cf745c0d6b4df61a5","src/lib.rs":"36feb36b273a33acc953f243003fa9ea6dc41fc41ddc85b784ce00caba2ab43a","src/point_arithmetic.rs":"7b65088237a263f7972cf59f88e7f761513d3a0ed9e687d6d429d70fa8974398","src/projective.rs":"a2a47adeeae9beeaccfb40a2746543c2db280ff47be038c39338437826f6762c"},"package":"3c2fcef82c0ec6eefcc179b978446c399b3cdf73c392c35604e399eee6df1ee3"} \ No newline at end of file +{"files":{"CHANGELOG.md":"6bbfb034a1f59e955e758d9e1d787545b2948b5349a8c7b98b81ce4a40bf2898","Cargo.toml":"b2c33028ef1a7763ac1828c3f3c009e73085773de8adbfc043a6f5ca8ba7dba7","LICENSE-APACHE":"a9040321c3712d8fd0b09cf52b17445de04a23a10165049ae187cd39e5c86be5","LICENSE-MIT":"233b95ccbf90dc67e32f3e8995c489f6312d9191ebd141a931c3b684f1e3be6d","README.md":"953232a36bb8d90d3aaa82c97314b6e21f5df48637b87fb4d7c39ad40bd085a5","src/affine.rs":"f9071d6eb656a1a98522d3a0bf9f7b8b7954e58bf4e86e90d71843d057a2a576","src/dev.rs":"da64d3e406468cc13156f8378c18d3a68c615a621eb9007939cd340b3d37a19f","src/field.rs":"5a3c9bb09c21cafb56032374d99be8494d7bf482253e701cf745c0d6b4df61a5","src/lib.rs":"1b585e745812d008c554cfb8c52ae88619ca9a3d7c481cf18283a9be3b893990","src/point_arithmetic.rs":"7b65088237a263f7972cf59f88e7f761513d3a0ed9e687d6d429d70fa8974398","src/projective.rs":"4250a404894f3f18f788bdac07c91573ff57070e5a7bea54b8422c49f53b3f15"},"package":"353e1ca18966c16d9deb1c69278edbc5f194139612772bd9537af60ac231e1e6"} \ No newline at end of file diff --git a/vendor/primeorder/CHANGELOG.md b/vendor/primeorder/CHANGELOG.md index 044c36089..be0f9ca54 100644 --- a/vendor/primeorder/CHANGELOG.md +++ b/vendor/primeorder/CHANGELOG.md @@ -4,6 +4,38 @@ All notable changes to this project will be documented in this file. The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html). +## 0.13.6 (2023-11-15) +### Removed +- `Invert` bounds on `FieldElement` ([#985]) + +[#985]: https://github.com/RustCrypto/elliptic-curves/pull/985 + +## 0.13.5 (2023-11-15) [YANKED] +### Added +- `alloc` feature ([#982]) + +[#982]: https://github.com/RustCrypto/elliptic-curves/pull/982 + +## 0.13.4 (2023-11-15) [YANKED] +### Added +- `BatchInvert` and `BatchNormalize` impls ([#971]) + +### Changed +- Bump `elliptic-curve` to v0.13.7 ([#979]) + +[#971]: https://github.com/RustCrypto/elliptic-curves/pull/971 +[#979]: https://github.com/RustCrypto/elliptic-curves/pull/979 + +## 0.13.3 (2023-11-02) +### Added +- Inline annotations on `conditional_select` ([#942]) + +### Changed +- Support field elements larger than 64-bytes in `impl_projective_arithmetic_tests!` ([#951]) + +[#942]: https://github.com/RustCrypto/elliptic-curves/pull/942 +[#951]: https://github.com/RustCrypto/elliptic-curves/pull/951 + ## 0.13.2 (2023-05-29) ### Changed - Improve decoding performance for uncompressed SEC1 points ([#891]) diff --git a/vendor/primeorder/Cargo.toml b/vendor/primeorder/Cargo.toml index bddf084bb..4906baab6 100644 --- a/vendor/primeorder/Cargo.toml +++ b/vendor/primeorder/Cargo.toml @@ -13,7 +13,7 @@ edition = "2021" rust-version = "1.65" name = "primeorder" -version = "0.13.2" +version = "0.13.6" authors = ["RustCrypto Developers"] description = """ Pure Rust implementation of complete addition formulas for prime order elliptic @@ -41,7 +41,7 @@ rustdoc-args = [ ] [dependencies.elliptic-curve] -version = "0.13" +version = "0.13.7" features = [ "arithmetic", "sec1", @@ -54,9 +54,13 @@ optional = true default-features = false [features] +alloc = ["elliptic-curve/alloc"] dev = [] serde = [ "elliptic-curve/serde", "serdect", ] -std = ["elliptic-curve/std"] +std = [ + "alloc", + "elliptic-curve/std", +] diff --git a/vendor/primeorder/README.md b/vendor/primeorder/README.md index eb2a163cd..603090434 100644 --- a/vendor/primeorder/README.md +++ b/vendor/primeorder/README.md @@ -24,9 +24,12 @@ y² = x³ + ax + b It's used to implement the following elliptic curves: +- [`p192`]: NIST P-192 - [`p224`]: NIST P-224 - [`p256`]: NIST P-256 - [`p384`]: NIST P-384 +- [`p521`]: NIST P-521 +- [`sm2`]: ShangMi 2 ## ⚠️ Security Warning @@ -85,6 +88,9 @@ dual licensed as above, without any additional terms or conditions. [RustCrypto]: https://github.com/rustcrypto/ [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060 [Weierstrass equation]: https://crypto.stanford.edu/pbc/notes/elliptic/weier.html +[`p192`]: https://github.com/RustCrypto/elliptic-curves/tree/master/p192 [`p224`]: https://github.com/RustCrypto/elliptic-curves/tree/master/p224 [`p256`]: https://github.com/RustCrypto/elliptic-curves/tree/master/p256 -[`p384`]: https://github.com/RustCrypto/elliptic-curves/tree/master/p256 +[`p384`]: https://github.com/RustCrypto/elliptic-curves/tree/master/p384 +[`p521`]: https://github.com/RustCrypto/elliptic-curves/tree/master/p384 +[`sm2`]: https://github.com/RustCrypto/elliptic-curves/tree/master/sm2 diff --git a/vendor/primeorder/src/affine.rs b/vendor/primeorder/src/affine.rs index 3fb01d905..6801c5d31 100644 --- a/vendor/primeorder/src/affine.rs +++ b/vendor/primeorder/src/affine.rs @@ -96,6 +96,7 @@ impl ConditionallySelectable for AffinePoint where C: PrimeCurveParams, { + #[inline(always)] fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self { Self { x: C::FieldElement::conditional_select(&a.x, &b.x, choice), diff --git a/vendor/primeorder/src/dev.rs b/vendor/primeorder/src/dev.rs index 77f563fa0..a70027f07 100644 --- a/vendor/primeorder/src/dev.rs +++ b/vendor/primeorder/src/dev.rs @@ -139,12 +139,15 @@ macro_rules! impl_projective_arithmetic_tests { .iter() .enumerate() .map(|(k, coords)| (<$scalar>::from(k as u64 + 1), *coords)) - .chain( - $mul_vectors - .iter() - .cloned() - .map(|(k, x, y)| (<$scalar>::from_repr(k.into()).unwrap(), (x, y))), - ) + .chain($mul_vectors.iter().cloned().map(|(k, x, y)| { + ( + <$scalar>::from_repr( + $crate::generic_array::GenericArray::clone_from_slice(&k), + ) + .unwrap(), + (x, y), + ) + })) { let p = generator * &k; assert_point_eq!(p, coords); diff --git a/vendor/primeorder/src/lib.rs b/vendor/primeorder/src/lib.rs index 8c515a148..46b1860a9 100644 --- a/vendor/primeorder/src/lib.rs +++ b/vendor/primeorder/src/lib.rs @@ -8,6 +8,10 @@ #![warn(missing_docs, rust_2018_idioms, unused_qualifications)] #![doc = include_str!("../README.md")] +#[cfg(feature = "alloc")] +#[macro_use] +extern crate alloc; + pub mod point_arithmetic; mod affine; @@ -17,7 +21,9 @@ mod field; mod projective; pub use crate::{affine::AffinePoint, projective::ProjectivePoint}; -pub use elliptic_curve::{self, point::Double, Field, FieldBytes, PrimeCurve, PrimeField}; +pub use elliptic_curve::{ + self, generic_array, point::Double, Field, FieldBytes, PrimeCurve, PrimeField, +}; use elliptic_curve::CurveArithmetic; @@ -30,6 +36,7 @@ pub trait PrimeCurveParams: + CurveArithmetic> { /// Base field element type. + // TODO(tarcieri): add `Invert` bound type FieldElement: PrimeField>; /// [Point arithmetic](point_arithmetic) implementation, might be optimized for this specific curve diff --git a/vendor/primeorder/src/projective.rs b/vendor/primeorder/src/projective.rs index 5549543fc..884b13745 100644 --- a/vendor/primeorder/src/projective.rs +++ b/vendor/primeorder/src/projective.rs @@ -17,7 +17,7 @@ use elliptic_curve::{ prime::{PrimeCurve, PrimeGroup}, Group, GroupEncoding, }, - ops::{LinearCombination, MulByGenerator}, + ops::{BatchInvert, Invert, LinearCombination, MulByGenerator}, point::Double, rand_core::RngCore, sec1::{ @@ -26,9 +26,12 @@ use elliptic_curve::{ }, subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption}, zeroize::DefaultIsZeroes, - Error, FieldBytes, FieldBytesSize, PublicKey, Result, Scalar, + BatchNormalize, Error, FieldBytes, FieldBytesSize, PublicKey, Result, Scalar, }; +#[cfg(feature = "alloc")] +use alloc::vec::Vec; + /// Point on a Weierstrass curve in projective coordinates. #[derive(Clone, Copy, Debug)] pub struct ProjectivePoint { @@ -57,16 +60,19 @@ where /// Returns the affine representation of this point, or `None` if it is the identity. pub fn to_affine(&self) -> AffinePoint { - self.z - .invert() - .map(|zinv| AffinePoint { - x: self.x * &zinv, - y: self.y * &zinv, - infinity: 0, - }) + ::invert(&self.z) + .map(|zinv| self.to_affine_internal(zinv)) .unwrap_or(AffinePoint::IDENTITY) } + pub(super) fn to_affine_internal(self, zinv: C::FieldElement) -> AffinePoint { + AffinePoint { + x: self.x * &zinv, + y: self.y * &zinv, + infinity: 0, + } + } + /// Returns `-self`. pub fn neg(&self) -> Self { Self { @@ -172,6 +178,7 @@ impl ConditionallySelectable for ProjectivePoint where C: PrimeCurveParams, { + #[inline(always)] fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self { Self { x: C::FieldElement::conditional_select(&a.x, &b.x, choice), @@ -325,6 +332,84 @@ where fn to_affine(&self) -> AffinePoint { ProjectivePoint::to_affine(self) } + + // TODO(tarcieri): re-enable when we can add `Invert` bounds on `FieldElement` + // #[cfg(feature = "alloc")] + // #[inline] + // fn batch_normalize(projective: &[Self], affine: &mut [Self::AffineRepr]) { + // assert_eq!(projective.len(), affine.len()); + // let mut zs = vec![C::FieldElement::ONE; projective.len()]; + // batch_normalize_generic(projective, zs.as_mut_slice(), affine); + // } +} + +impl BatchNormalize<[ProjectivePoint; N]> for ProjectivePoint +where + Self: Double, + C: PrimeCurveParams, + C::FieldElement: Invert>, +{ + type Output = [Self::AffineRepr; N]; + + #[inline] + fn batch_normalize(points: &[Self; N]) -> [Self::AffineRepr; N] { + let mut zs = [C::FieldElement::ONE; N]; + let mut affine_points = [C::AffinePoint::IDENTITY; N]; + batch_normalize_generic(points, &mut zs, &mut affine_points); + affine_points + } +} + +#[cfg(feature = "alloc")] +impl BatchNormalize<[ProjectivePoint]> for ProjectivePoint +where + Self: Double, + C: PrimeCurveParams, + C::FieldElement: Invert>, +{ + type Output = Vec; + + #[inline] + fn batch_normalize(points: &[Self]) -> Vec { + let mut zs = vec![C::FieldElement::ONE; points.len()]; + let mut affine_points = vec![AffinePoint::IDENTITY; points.len()]; + batch_normalize_generic(points, zs.as_mut_slice(), &mut affine_points); + affine_points + } +} + +/// Generic implementation of batch normalization. +fn batch_normalize_generic(points: &P, zs: &mut Z, out: &mut O) +where + C: PrimeCurveParams, + C::FieldElement: BatchInvert, + C::ProjectivePoint: Double, + P: AsRef<[ProjectivePoint]> + ?Sized, + Z: AsMut<[C::FieldElement]> + ?Sized, + O: AsMut<[AffinePoint]> + ?Sized, +{ + let points = points.as_ref(); + let out = out.as_mut(); + + for i in 0..points.len() { + // Even a single zero value will fail inversion for the entire batch. + // Put a dummy value (above `FieldElement::ONE`) so inversion succeeds + // and treat that case specially later-on. + zs.as_mut()[i].conditional_assign(&points[i].z, !points[i].z.ct_eq(&C::FieldElement::ZERO)); + } + + // This is safe to unwrap since we assured that all elements are non-zero + let zs_inverses = >::batch_invert(zs).unwrap(); + + for i in 0..out.len() { + // If the `z` coordinate is non-zero, we can use it to invert; + // otherwise it defaults to the `IDENTITY` value. + out[i] = C::AffinePoint::conditional_select( + &points[i].to_affine_internal(zs_inverses.as_ref()[i]), + &C::AffinePoint::IDENTITY, + points[i].z.ct_eq(&C::FieldElement::ZERO), + ); + } } impl LinearCombination for ProjectivePoint -- cgit v1.2.3