diff options
Diffstat (limited to 'vendor/elliptic-curve/src/hash2curve')
7 files changed, 210 insertions, 130 deletions
diff --git a/vendor/elliptic-curve/src/hash2curve/group_digest.rs b/vendor/elliptic-curve/src/hash2curve/group_digest.rs index dbcb1512b..ea7f0471f 100644 --- a/vendor/elliptic-curve/src/hash2curve/group_digest.rs +++ b/vendor/elliptic-curve/src/hash2curve/group_digest.rs @@ -1,11 +1,11 @@ //! Traits for handling hash to curve. use super::{hash_to_field, ExpandMsg, FromOkm, MapToCurve}; -use crate::{ProjectiveArithmetic, ProjectivePoint, Result}; +use crate::{CurveArithmetic, ProjectivePoint, Result}; use group::cofactor::CofactorGroup; /// Adds hashing arbitrary byte sequences to a valid group element -pub trait GroupDigest: ProjectiveArithmetic +pub trait GroupDigest: CurveArithmetic where ProjectivePoint<Self>: CofactorGroup, { @@ -48,10 +48,10 @@ where /// [`ExpandMsgXof`]: crate::hash2curve::ExpandMsgXof fn hash_from_bytes<'a, X: ExpandMsg<'a>>( msgs: &[&[u8]], - dst: &'a [u8], + dsts: &'a [&'a [u8]], ) -> Result<ProjectivePoint<Self>> { let mut u = [Self::FieldElement::default(), Self::FieldElement::default()]; - hash_to_field::<X, _>(msgs, dst, &mut u)?; + hash_to_field::<X, _>(msgs, dsts, &mut u)?; let q0 = u[0].map_to_curve(); let q1 = u[1].map_to_curve(); // Ideally we could add and then clear cofactor once @@ -88,10 +88,10 @@ where /// [`ExpandMsgXof`]: crate::hash2curve::ExpandMsgXof fn encode_from_bytes<'a, X: ExpandMsg<'a>>( msgs: &[&[u8]], - dst: &'a [u8], + dsts: &'a [&'a [u8]], ) -> Result<ProjectivePoint<Self>> { let mut u = [Self::FieldElement::default()]; - hash_to_field::<X, _>(msgs, dst, &mut u)?; + hash_to_field::<X, _>(msgs, dsts, &mut u)?; let q0 = u[0].map_to_curve(); Ok(q0.clear_cofactor().into()) } @@ -109,12 +109,15 @@ where /// /// [`ExpandMsgXmd`]: crate::hash2curve::ExpandMsgXmd /// [`ExpandMsgXof`]: crate::hash2curve::ExpandMsgXof - fn hash_to_scalar<'a, X: ExpandMsg<'a>>(msgs: &[&[u8]], dst: &'a [u8]) -> Result<Self::Scalar> + fn hash_to_scalar<'a, X: ExpandMsg<'a>>( + msgs: &[&[u8]], + dsts: &'a [&'a [u8]], + ) -> Result<Self::Scalar> where Self::Scalar: FromOkm, { let mut u = [Self::Scalar::default()]; - hash_to_field::<X, _>(msgs, dst, &mut u)?; + hash_to_field::<X, _>(msgs, dsts, &mut u)?; Ok(u[0]) } } diff --git a/vendor/elliptic-curve/src/hash2curve/hash2field.rs b/vendor/elliptic-curve/src/hash2curve/hash2field.rs index 6cd0723aa..67ede111c 100644 --- a/vendor/elliptic-curve/src/hash2curve/hash2field.rs +++ b/vendor/elliptic-curve/src/hash2curve/hash2field.rs @@ -6,7 +6,7 @@ mod expand_msg; pub use expand_msg::{xmd::*, xof::*, *}; -use crate::Result; +use crate::{Error, Result}; use generic_array::{typenum::Unsigned, ArrayLength, GenericArray}; /// The trait for helping to convert to a field element. @@ -32,12 +32,12 @@ pub trait FromOkm { /// [`ExpandMsgXmd`]: crate::hash2field::ExpandMsgXmd /// [`ExpandMsgXof`]: crate::hash2field::ExpandMsgXof #[doc(hidden)] -pub fn hash_to_field<'a, E, T>(data: &[&[u8]], domain: &'a [u8], out: &mut [T]) -> Result<()> +pub fn hash_to_field<'a, E, T>(data: &[&[u8]], domain: &'a [&'a [u8]], out: &mut [T]) -> Result<()> where E: ExpandMsg<'a>, T: FromOkm + Default, { - let len_in_bytes = T::Length::to_usize() * out.len(); + let len_in_bytes = T::Length::to_usize().checked_mul(out.len()).ok_or(Error)?; let mut tmp = GenericArray::<u8, <T as FromOkm>::Length>::default(); let mut expander = E::expand_message(data, domain, len_in_bytes)?; for o in out.iter_mut() { diff --git a/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg.rs b/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg.rs index dfb3bab9c..96a659b9a 100644 --- a/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg.rs +++ b/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg.rs @@ -25,8 +25,11 @@ pub trait ExpandMsg<'a> { /// /// Returns an expander that can be used to call `read` until enough /// bytes have been consumed - fn expand_message(msgs: &[&[u8]], dst: &'a [u8], len_in_bytes: usize) - -> Result<Self::Expander>; + fn expand_message( + msgs: &[&[u8]], + dsts: &'a [&'a [u8]], + len_in_bytes: usize, + ) -> Result<Self::Expander>; } /// Expander that, call `read` until enough bytes have been consumed. @@ -47,54 +50,66 @@ where /// > 255 Hashed(GenericArray<u8, L>), /// <= 255 - Array(&'a [u8]), + Array(&'a [&'a [u8]]), } impl<'a, L> Domain<'a, L> where L: ArrayLength<u8> + IsLess<U256>, { - pub fn xof<X>(dst: &'a [u8]) -> Result<Self> + pub fn xof<X>(dsts: &'a [&'a [u8]]) -> Result<Self> where X: Default + ExtendableOutput + Update, { - if dst.is_empty() { + if dsts.is_empty() { Err(Error) - } else if dst.len() > MAX_DST_LEN { + } else if dsts.iter().map(|dst| dst.len()).sum::<usize>() > MAX_DST_LEN { let mut data = GenericArray::<u8, L>::default(); - X::default() - .chain(OVERSIZE_DST_SALT) - .chain(dst) - .finalize_xof() - .read(&mut data); + let mut hash = X::default(); + hash.update(OVERSIZE_DST_SALT); + + for dst in dsts { + hash.update(dst); + } + + hash.finalize_xof().read(&mut data); + Ok(Self::Hashed(data)) } else { - Ok(Self::Array(dst)) + Ok(Self::Array(dsts)) } } - pub fn xmd<X>(dst: &'a [u8]) -> Result<Self> + pub fn xmd<X>(dsts: &'a [&'a [u8]]) -> Result<Self> where X: Digest<OutputSize = L>, { - if dst.is_empty() { + if dsts.is_empty() { Err(Error) - } else if dst.len() > MAX_DST_LEN { + } else if dsts.iter().map(|dst| dst.len()).sum::<usize>() > MAX_DST_LEN { Ok(Self::Hashed({ let mut hash = X::new(); hash.update(OVERSIZE_DST_SALT); - hash.update(dst); + + for dst in dsts { + hash.update(dst); + } + hash.finalize() })) } else { - Ok(Self::Array(dst)) + Ok(Self::Array(dsts)) } } - pub fn data(&self) -> &[u8] { + pub fn update_hash<HashT: Update>(&self, hash: &mut HashT) { match self { - Self::Hashed(d) => &d[..], - Self::Array(d) => *d, + Self::Hashed(d) => hash.update(d), + Self::Array(d) => { + for d in d.iter() { + hash.update(d) + } + } } } @@ -103,13 +118,28 @@ where // Can't overflow because it's enforced on a type level. Self::Hashed(_) => L::to_u8(), // Can't overflow because it's checked on creation. - Self::Array(d) => u8::try_from(d.len()).expect("length overflow"), + Self::Array(d) => { + u8::try_from(d.iter().map(|d| d.len()).sum::<usize>()).expect("length overflow") + } } } #[cfg(test)] pub fn assert(&self, bytes: &[u8]) { - assert_eq!(self.data(), &bytes[..bytes.len() - 1]); + let data = match self { + Domain::Hashed(d) => d.to_vec(), + Domain::Array(d) => d.iter().copied().flatten().copied().collect(), + }; + assert_eq!(data, bytes); + } + + #[cfg(test)] + pub fn assert_dst(&self, bytes: &[u8]) { + let data = match self { + Domain::Hashed(d) => d.to_vec(), + Domain::Array(d) => d.iter().copied().flatten().copied().collect(), + }; + assert_eq!(data, &bytes[..bytes.len() - 1]); assert_eq!(self.len(), bytes[bytes.len() - 1]); } } diff --git a/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg/xmd.rs b/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg/xmd.rs index 876b012f5..50edb648b 100644 --- a/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg/xmd.rs +++ b/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg/xmd.rs @@ -1,5 +1,8 @@ //! `expand_message_xmd` based on a hash function. +// TODO(tarcieri): checked arithmetic +#![allow(clippy::integer_arithmetic)] + use core::marker::PhantomData; use super::{Domain, ExpandMsg, Expander}; @@ -10,7 +13,7 @@ use digest::{ typenum::{IsLess, IsLessOrEqual, Unsigned, U256}, GenericArray, }, - Digest, + FixedOutput, HashMarker, }; /// Placeholder type for implementing `expand_message_xmd` based on a hash function @@ -22,14 +25,14 @@ use digest::{ /// - `len_in_bytes > 255 * HashT::OutputSize` pub struct ExpandMsgXmd<HashT>(PhantomData<HashT>) where - HashT: Digest + BlockSizeUser, + HashT: BlockSizeUser + Default + FixedOutput + HashMarker, HashT::OutputSize: IsLess<U256>, HashT::OutputSize: IsLessOrEqual<HashT::BlockSize>; /// ExpandMsgXmd implements expand_message_xmd for the ExpandMsg trait impl<'a, HashT> ExpandMsg<'a> for ExpandMsgXmd<HashT> where - HashT: Digest + BlockSizeUser, + HashT: BlockSizeUser + Default + FixedOutput + HashMarker, // If `len_in_bytes` is bigger then 256, length of the `DST` will depend on // the output size of the hash, which is still not allowed to be bigger then 256: // https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html#section-5.4.1-6 @@ -42,7 +45,7 @@ where fn expand_message( msgs: &[&[u8]], - dst: &'a [u8], + dsts: &'a [&'a [u8]], len_in_bytes: usize, ) -> Result<Self::Expander> { if len_in_bytes == 0 { @@ -54,26 +57,26 @@ where let b_in_bytes = HashT::OutputSize::to_usize(); let ell = u8::try_from((len_in_bytes + b_in_bytes - 1) / b_in_bytes).map_err(|_| Error)?; - let domain = Domain::xmd::<HashT>(dst)?; - let mut b_0 = HashT::new(); - b_0.update(GenericArray::<u8, HashT::BlockSize>::default()); + let domain = Domain::xmd::<HashT>(dsts)?; + let mut b_0 = HashT::default(); + b_0.update(&GenericArray::<u8, HashT::BlockSize>::default()); for msg in msgs { b_0.update(msg); } - b_0.update(len_in_bytes_u16.to_be_bytes()); - b_0.update([0]); - b_0.update(domain.data()); - b_0.update([domain.len()]); - let b_0 = b_0.finalize(); + b_0.update(&len_in_bytes_u16.to_be_bytes()); + b_0.update(&[0]); + domain.update_hash(&mut b_0); + b_0.update(&[domain.len()]); + let b_0 = b_0.finalize_fixed(); - let mut b_vals = HashT::new(); + let mut b_vals = HashT::default(); b_vals.update(&b_0[..]); - b_vals.update([1u8]); - b_vals.update(domain.data()); - b_vals.update([domain.len()]); - let b_vals = b_vals.finalize(); + b_vals.update(&[1u8]); + domain.update_hash(&mut b_vals); + b_vals.update(&[domain.len()]); + let b_vals = b_vals.finalize_fixed(); Ok(ExpanderXmd { b_0, @@ -89,7 +92,7 @@ where /// [`Expander`] type for [`ExpandMsgXmd`]. pub struct ExpanderXmd<'a, HashT> where - HashT: Digest + BlockSizeUser, + HashT: BlockSizeUser + Default + FixedOutput + HashMarker, HashT::OutputSize: IsLess<U256>, HashT::OutputSize: IsLessOrEqual<HashT::BlockSize>, { @@ -103,7 +106,7 @@ where impl<'a, HashT> ExpanderXmd<'a, HashT> where - HashT: Digest + BlockSizeUser, + HashT: BlockSizeUser + Default + FixedOutput + HashMarker, HashT::OutputSize: IsLess<U256>, HashT::OutputSize: IsLessOrEqual<HashT::BlockSize>, { @@ -118,12 +121,12 @@ where .zip(&self.b_vals[..]) .enumerate() .for_each(|(j, (b0val, bi1val))| tmp[j] = b0val ^ bi1val); - let mut b_vals = HashT::new(); - b_vals.update(tmp); - b_vals.update([self.index]); - b_vals.update(self.domain.data()); - b_vals.update([self.domain.len()]); - self.b_vals = b_vals.finalize(); + let mut b_vals = HashT::default(); + b_vals.update(&tmp); + b_vals.update(&[self.index]); + self.domain.update_hash(&mut b_vals); + b_vals.update(&[self.domain.len()]); + self.b_vals = b_vals.finalize_fixed(); true } else { false @@ -133,7 +136,7 @@ where impl<'a, HashT> Expander for ExpanderXmd<'a, HashT> where - HashT: Digest + BlockSizeUser, + HashT: BlockSizeUser + Default + FixedOutput + HashMarker, HashT::OutputSize: IsLess<U256>, HashT::OutputSize: IsLessOrEqual<HashT::BlockSize>, { @@ -165,7 +168,7 @@ mod test { len_in_bytes: u16, bytes: &[u8], ) where - HashT: Digest + BlockSizeUser, + HashT: BlockSizeUser + Default + FixedOutput + HashMarker, HashT::OutputSize: IsLess<U256>, { let block = HashT::BlockSize::to_usize(); @@ -183,8 +186,8 @@ mod test { let pad = l + mem::size_of::<u8>(); assert_eq!([0], &bytes[l..pad]); - let dst = pad + domain.data().len(); - assert_eq!(domain.data(), &bytes[pad..dst]); + let dst = pad + usize::from(domain.len()); + domain.assert(&bytes[pad..dst]); let dst_len = dst + mem::size_of::<u8>(); assert_eq!([domain.len()], &bytes[dst..dst_len]); @@ -205,13 +208,14 @@ mod test { domain: &Domain<'_, HashT::OutputSize>, ) -> Result<()> where - HashT: Digest + BlockSizeUser, + HashT: BlockSizeUser + Default + FixedOutput + HashMarker, HashT::OutputSize: IsLess<U256> + IsLessOrEqual<HashT::BlockSize>, { assert_message::<HashT>(self.msg, domain, L::to_u16(), self.msg_prime); + let dst = [dst]; let mut expander = - ExpandMsgXmd::<HashT>::expand_message(&[self.msg], dst, L::to_usize())?; + ExpandMsgXmd::<HashT>::expand_message(&[self.msg], &dst, L::to_usize())?; let mut uniform_bytes = GenericArray::<u8, L>::default(); expander.fill_bytes(&mut uniform_bytes); @@ -227,8 +231,8 @@ mod test { const DST_PRIME: &[u8] = &hex!("515555582d5630312d435330322d776974682d657870616e6465722d5348413235362d31323826"); - let dst_prime = Domain::xmd::<Sha256>(DST)?; - dst_prime.assert(DST_PRIME); + let dst_prime = Domain::xmd::<Sha256>(&[DST])?; + dst_prime.assert_dst(DST_PRIME); const TEST_VECTORS_32: &[TestVector] = &[ TestVector { @@ -299,8 +303,8 @@ mod test { const DST_PRIME: &[u8] = &hex!("412717974da474d0f8c420f320ff81e8432adb7c927d9bd082b4fb4d16c0a23620"); - let dst_prime = Domain::xmd::<Sha256>(DST)?; - dst_prime.assert(DST_PRIME); + let dst_prime = Domain::xmd::<Sha256>(&[DST])?; + dst_prime.assert_dst(DST_PRIME); const TEST_VECTORS_32: &[TestVector] = &[ TestVector { @@ -377,8 +381,8 @@ mod test { const DST_PRIME: &[u8] = &hex!("515555582d5630312d435330322d776974682d657870616e6465722d5348413531322d32353626"); - let dst_prime = Domain::xmd::<Sha512>(DST)?; - dst_prime.assert(DST_PRIME); + let dst_prime = Domain::xmd::<Sha512>(&[DST])?; + dst_prime.assert_dst(DST_PRIME); const TEST_VECTORS_32: &[TestVector] = &[ TestVector { diff --git a/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg/xof.rs b/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg/xof.rs index 107ac5e06..9a5ff19e9 100644 --- a/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg/xof.rs +++ b/vendor/elliptic-curve/src/hash2curve/hash2field/expand_msg/xof.rs @@ -27,7 +27,7 @@ where fn expand_message( msgs: &[&[u8]], - dst: &'a [u8], + dsts: &'a [&'a [u8]], len_in_bytes: usize, ) -> Result<Self::Expander> { if len_in_bytes == 0 { @@ -36,18 +36,17 @@ where let len_in_bytes = u16::try_from(len_in_bytes).map_err(|_| Error)?; - let domain = Domain::<U32>::xof::<HashT>(dst)?; + let domain = Domain::<U32>::xof::<HashT>(dsts)?; let mut reader = HashT::default(); for msg in msgs { reader = reader.chain(msg); } - let reader = reader - .chain(len_in_bytes.to_be_bytes()) - .chain(domain.data()) - .chain([domain.len()]) - .finalize_xof(); + reader.update(&len_in_bytes.to_be_bytes()); + domain.update_hash(&mut reader); + reader.update(&[domain.len()]); + let reader = reader.finalize_xof(); Ok(Self { reader }) } } @@ -87,8 +86,8 @@ mod test { &bytes[msg_len..len_in_bytes_len] ); - let dst = len_in_bytes_len + domain.data().len(); - assert_eq!(domain.data(), &bytes[len_in_bytes_len..dst]); + let dst = len_in_bytes_len + usize::from(domain.len()); + domain.assert(&bytes[len_in_bytes_len..dst]); let dst_len = dst + mem::size_of::<u8>(); assert_eq!([domain.len()], &bytes[dst..dst_len]); @@ -111,7 +110,7 @@ mod test { assert_message::<HashT>(self.msg, domain, L::to_u16(), self.msg_prime); let mut expander = - ExpandMsgXof::<HashT>::expand_message(&[self.msg], dst, L::to_usize())?; + ExpandMsgXof::<HashT>::expand_message(&[self.msg], &[dst], L::to_usize())?; let mut uniform_bytes = GenericArray::<u8, L>::default(); expander.fill_bytes(&mut uniform_bytes); @@ -127,8 +126,8 @@ mod test { const DST_PRIME: &[u8] = &hex!("515555582d5630312d435330322d776974682d657870616e6465722d5348414b4531323824"); - let dst_prime = Domain::<U32>::xof::<Shake128>(DST)?; - dst_prime.assert(DST_PRIME); + let dst_prime = Domain::<U32>::xof::<Shake128>(&[DST])?; + dst_prime.assert_dst(DST_PRIME); const TEST_VECTORS_32: &[TestVector] = &[ TestVector { @@ -203,8 +202,8 @@ mod test { const DST_PRIME: &[u8] = &hex!("acb9736c0867fdfbd6385519b90fc8c034b5af04a958973212950132d035792f20"); - let dst_prime = Domain::<U32>::xof::<Shake128>(DST)?; - dst_prime.assert(DST_PRIME); + let dst_prime = Domain::<U32>::xof::<Shake128>(&[DST])?; + dst_prime.assert_dst(DST_PRIME); const TEST_VECTORS_32: &[TestVector] = &[ TestVector { @@ -281,8 +280,8 @@ mod test { const DST_PRIME: &[u8] = &hex!("515555582d5630312d435330322d776974682d657870616e6465722d5348414b4532353624"); - let dst_prime = Domain::<U32>::xof::<Shake256>(DST)?; - dst_prime.assert(DST_PRIME); + let dst_prime = Domain::<U32>::xof::<Shake256>(&[DST])?; + dst_prime.assert_dst(DST_PRIME); const TEST_VECTORS_32: &[TestVector] = &[ TestVector { diff --git a/vendor/elliptic-curve/src/hash2curve/isogeny.rs b/vendor/elliptic-curve/src/hash2curve/isogeny.rs index fc197246a..7a28983dd 100644 --- a/vendor/elliptic-curve/src/hash2curve/isogeny.rs +++ b/vendor/elliptic-curve/src/hash2curve/isogeny.rs @@ -26,9 +26,10 @@ pub trait Isogeny: Field + AddAssign + Mul<Output = Self> { const COEFFICIENTS: IsogenyCoefficients<Self>; /// Map from the isogeny points to the main curve + #[allow(clippy::integer_arithmetic)] fn isogeny(x: Self, y: Self) -> (Self, Self) { let mut xs = GenericArray::<Self, Self::Degree>::default(); - xs[0] = Self::one(); + xs[0] = Self::ONE; xs[1] = x; xs[2] = x.square(); for i in 3..Self::Degree::to_usize() { @@ -48,7 +49,7 @@ pub trait Isogeny: Field + AddAssign + Mul<Output = Self> { /// Compute the ISO transform fn compute_iso(xxs: &[Self], k: &[Self]) -> Self { - let mut xx = Self::zero(); + let mut xx = Self::ZERO; for (xi, ki) in xxs.iter().zip(k.iter()) { xx += *xi * ki; } diff --git a/vendor/elliptic-curve/src/hash2curve/osswu.rs b/vendor/elliptic-curve/src/hash2curve/osswu.rs index f803863b1..3c3669ac3 100644 --- a/vendor/elliptic-curve/src/hash2curve/osswu.rs +++ b/vendor/elliptic-curve/src/hash2curve/osswu.rs @@ -1,9 +1,11 @@ //! Optimized simplified Shallue-van de Woestijne-Ulas methods. //! -//! <https://eprint.iacr.org/2009/340.pdf> +//! <https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html#straightline-sswu> use ff::Field; use subtle::Choice; +use subtle::ConditionallySelectable; +use subtle::ConstantTimeEq; /// The Optimized Simplified Shallue-van de Woestijne-Ulas parameters pub struct OsswuMapParams<F> @@ -11,7 +13,7 @@ where F: Field, { /// The first constant term - pub c1: [u64; 4], + pub c1: &'static [u64], /// The second constant term pub c2: F, /// The ISO A variable or Curve A variable @@ -38,50 +40,91 @@ pub trait OsswuMap: Field + Sgn0 { /// should be for isogeny where A≠0 and B≠0. const PARAMS: OsswuMapParams<Self>; + /// Optimized sqrt_ratio for q = 3 mod 4. + fn sqrt_ratio_3mod4(u: Self, v: Self) -> (Choice, Self) { + // 1. tv1 = v^2 + let tv1 = v.square(); + // 2. tv2 = u * v + let tv2 = u * v; + // 3. tv1 = tv1 * tv2 + let tv1 = tv1 * tv2; + // 4. y1 = tv1^c1 + let y1 = tv1.pow_vartime(Self::PARAMS.c1); + // 5. y1 = y1 * tv2 + let y1 = y1 * tv2; + // 6. y2 = y1 * c2 + let y2 = y1 * Self::PARAMS.c2; + // 7. tv3 = y1^2 + let tv3 = y1.square(); + // 8. tv3 = tv3 * v + let tv3 = tv3 * v; + // 9. isQR = tv3 == u + let is_qr = tv3.ct_eq(&u); + // 10. y = CMOV(y2, y1, isQR) + let y = ConditionallySelectable::conditional_select(&y2, &y1, is_qr); + // 11. return (isQR, y) + (is_qr, y) + } + /// Convert this field element into an affine point on the elliptic curve /// returning (X, Y). For Weierstrass curves having A==0 or B==0 /// the result is a point on an isogeny. fn osswu(&self) -> (Self, Self) { - let tv1 = self.square(); // u^2 - let tv3 = Self::PARAMS.z * tv1; // Z * u^2 - let mut tv2 = tv3.square(); // tv3^2 - let mut xd = tv2 + tv3; // tv3^2 + tv3 - let x1n = Self::PARAMS.map_b * (xd + Self::one()); // B * (xd + 1) - xd *= -Self::PARAMS.map_a; // -A * xd - - let tv = Self::PARAMS.z * Self::PARAMS.map_a; - xd.conditional_assign(&tv, xd.is_zero()); - - tv2 = xd.square(); //xd^2 - let gxd = tv2 * xd; // xd^3 - tv2 *= Self::PARAMS.map_a; // A * tv2 - - let mut gx1 = x1n * (tv2 + x1n.square()); //x1n *(tv2 + x1n^2) - tv2 = gxd * Self::PARAMS.map_b; // B * gxd - gx1 += tv2; // gx1 + tv2 - - let mut tv4 = gxd.square(); // gxd^2 - tv2 = gx1 * gxd; // gx1 * gxd - tv4 *= tv2; - - let y1 = tv4.pow_vartime(&Self::PARAMS.c1) * tv2; // tv4^C1 * tv2 - let x2n = tv3 * x1n; // tv3 * x1n - - let y2 = y1 * Self::PARAMS.c2 * tv1 * self; // y1 * c2 * tv1 * u - - tv2 = y1.square() * gxd; //y1^2 * gxd - - let e2 = tv2.ct_eq(&gx1); - - // if e2 , x = x1, else x = x2 - let mut x = Self::conditional_select(&x2n, &x1n, e2); - // xn / xd - x *= xd.invert().unwrap(); - - // if e2, y = y1, else y = y2 - let mut y = Self::conditional_select(&y2, &y1, e2); - - y.conditional_assign(&-y, self.sgn0() ^ y.sgn0()); + // 1. tv1 = u^2 + let tv1 = self.square(); + // 2. tv1 = Z * tv1 + let tv1 = Self::PARAMS.z * tv1; + // 3. tv2 = tv1^2 + let tv2 = tv1.square(); + // 4. tv2 = tv2 + tv1 + let tv2 = tv2 + tv1; + // 5. tv3 = tv2 + 1 + let tv3 = tv2 + Self::ONE; + // 6. tv3 = B * tv3 + let tv3 = Self::PARAMS.map_b * tv3; + // 7. tv4 = CMOV(Z, -tv2, tv2 != 0) + let tv4 = ConditionallySelectable::conditional_select( + &Self::PARAMS.z, + &-tv2, + !Field::is_zero(&tv2), + ); + // 8. tv4 = A * tv4 + let tv4 = Self::PARAMS.map_a * tv4; + // 9. tv2 = tv3^2 + let tv2 = tv3.square(); + // 10. tv6 = tv4^2 + let tv6 = tv4.square(); + // 11. tv5 = A * tv6 + let tv5 = Self::PARAMS.map_a * tv6; + // 12. tv2 = tv2 + tv5 + let tv2 = tv2 + tv5; + // 13. tv2 = tv2 * tv3 + let tv2 = tv2 * tv3; + // 14. tv6 = tv6 * tv4 + let tv6 = tv6 * tv4; + // 15. tv5 = B * tv6 + let tv5 = Self::PARAMS.map_b * tv6; + // 16. tv2 = tv2 + tv5 + let tv2 = tv2 + tv5; + // 17. x = tv1 * tv3 + let x = tv1 * tv3; + // 18. (is_gx1_square, y1) = sqrt_ratio(tv2, tv6) + let (is_gx1_square, y1) = Self::sqrt_ratio_3mod4(tv2, tv6); + // 19. y = tv1 * u + let y = tv1 * self; + // 20. y = y * y1 + let y = y * y1; + // 21. x = CMOV(x, tv3, is_gx1_square) + let x = ConditionallySelectable::conditional_select(&x, &tv3, is_gx1_square); + // 22. y = CMOV(y, y1, is_gx1_square) + let y = ConditionallySelectable::conditional_select(&y, &y1, is_gx1_square); + // 23. e1 = sgn0(u) == sgn0(y) + let e1 = self.sgn0().ct_eq(&y.sgn0()); + // 24. y = CMOV(-y, y, e1) + let y = ConditionallySelectable::conditional_select(&-y, &y, e1); + // 25. x = x / tv4 + let x = x * tv4.invert().unwrap(); + // 26. return (x, y) (x, y) } } |