ed448_goldilocks/field/
scalar.rs

1use crate::*;
2
3use core::{
4    cmp::Ordering,
5    fmt::{Debug, Display, Formatter, Result as FmtResult},
6    iter::{Product, Sum},
7    marker::PhantomData,
8    ops::{Index, IndexMut},
9};
10use elliptic_curve::{
11    CurveArithmetic, Generate, PrimeField,
12    array::{
13        Array, ArraySize,
14        typenum::{Prod, Unsigned},
15    },
16    bigint::{Limb, U448, U896, Word, modular::Retrieve},
17    consts::U2,
18    ctutils::{self, CtSelect},
19    ff::{Field, helpers},
20    ops::{
21        Add, AddAssign, Invert, Mul, MulAssign, Neg, Reduce, ReduceNonZero, Shr, ShrAssign, Sub,
22        SubAssign,
23    },
24    scalar::{FromUintUnchecked, IsHigh},
25};
26use rand_core::{CryptoRng, Rng, TryCryptoRng, TryRng};
27use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, ConstantTimeGreater, CtOption};
28
29/// Shared scalar for [`Ed448`] and [`Decaf448`].
30/// Use [`EdwardsScalar`] and [`DecafScalar`] directly.
31///
32/// This is the scalar field
33/// size = 4q = 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
34/// We can therefore use 14 saturated 32-bit limbs
35pub struct Scalar<C: CurveWithScalar> {
36    pub(crate) scalar: U448,
37    curve: PhantomData<C>,
38}
39
40/// The number of bytes needed to represent the scalar field
41pub type ScalarBytes<C> = Array<u8, <C as CurveWithScalar>::ReprSize>;
42/// The number of bytes needed to represent the safely create a scalar from a random bytes
43pub type WideScalarBytes<C> = Array<u8, Prod<<C as CurveWithScalar>::ReprSize, U2>>;
44
45pub trait CurveWithScalar: 'static + CurveArithmetic + Send + Sync {
46    type ReprSize: ArraySize<ArrayType<u8>: Copy> + Mul<U2, Output: ArraySize<ArrayType<u8>: Copy>>;
47
48    fn from_bytes_mod_order_wide(input: &WideScalarBytes<Self>) -> Scalar<Self>;
49
50    fn from_canonical_bytes(bytes: &ScalarBytes<Self>) -> CtOption<Scalar<Self>>;
51
52    fn to_repr(scalar: &Scalar<Self>) -> ScalarBytes<Self>;
53}
54
55/// The order of the scalar field
56pub const ORDER: Odd<U448> = Odd::<U448>::from_be_hex(
57    "3fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f3",
58);
59/// The order of the scalar field
60const ORDER_MINUS_ONE: U448 = ORDER.as_ref().wrapping_sub(&U448::ONE);
61const HALF_ORDER: U448 = ORDER.as_ref().shr_vartime(1);
62/// The wide order of the scalar field
63pub const WIDE_ORDER: U896 = U896::from_be_hex(
64    "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f3",
65);
66const WIDE_ORDER_MINUS_ONE: U896 = WIDE_ORDER.wrapping_sub(&U896::ONE);
67
68/// The modulus of the scalar field as a sequence of 14 32-bit limbs
69pub const MODULUS_LIMBS: [u32; 14] = [
70    0xab5844f3, 0x2378c292, 0x8dc58f55, 0x216cc272, 0xaed63690, 0xc44edb49, 0x7cca23e9, 0xffffffff,
71    0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0x3fffffff,
72];
73
74impl<C: CurveWithScalar> Clone for Scalar<C> {
75    fn clone(&self) -> Self {
76        *self
77    }
78}
79
80impl<C: CurveWithScalar> Copy for Scalar<C> {}
81
82impl<C: CurveWithScalar> Debug for Scalar<C> {
83    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
84        f.debug_tuple("Scalar").field(&self.scalar).finish()
85    }
86}
87
88impl<C: CurveWithScalar> Default for Scalar<C> {
89    fn default() -> Self {
90        Self::new(U448::default())
91    }
92}
93
94impl<C: CurveWithScalar> Display for Scalar<C> {
95    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
96        let bytes = self.to_repr();
97        for b in &bytes {
98            write!(f, "{b:02x}")?;
99        }
100        Ok(())
101    }
102}
103
104impl<C: CurveWithScalar> ConstantTimeEq for Scalar<C> {
105    fn ct_eq(&self, other: &Self) -> Choice {
106        self.to_bytes().ct_eq(&other.to_bytes())
107    }
108}
109
110impl<C: CurveWithScalar> ConditionallySelectable for Scalar<C> {
111    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
112        Self::new(U448::conditional_select(&a.scalar, &b.scalar, choice))
113    }
114}
115
116impl<C: CurveWithScalar> ctutils::CtEq for Scalar<C> {
117    fn ct_eq(&self, other: &Self) -> ctutils::Choice {
118        ConstantTimeEq::ct_eq(self, other).into()
119    }
120}
121
122impl<C: CurveWithScalar> ctutils::CtSelect for Scalar<C> {
123    fn ct_select(&self, other: &Self, choice: ctutils::Choice) -> Self {
124        ConditionallySelectable::conditional_select(self, other, choice.into())
125    }
126}
127
128impl<C: CurveWithScalar> PartialEq for Scalar<C> {
129    fn eq(&self, other: &Scalar<C>) -> bool {
130        self.ct_eq(other).into()
131    }
132}
133
134impl<C: CurveWithScalar> Eq for Scalar<C> {}
135
136impl<C: CurveWithScalar> PartialOrd for Scalar<C> {
137    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
138        Some(self.cmp(other))
139    }
140}
141
142impl<C: CurveWithScalar> Ord for Scalar<C> {
143    fn cmp(&self, other: &Self) -> Ordering {
144        self.scalar.cmp(&other.scalar)
145    }
146}
147
148impl<C: CurveWithScalar> From<u8> for Scalar<C> {
149    fn from(a: u8) -> Self {
150        Scalar::new(U448::from_u8(a))
151    }
152}
153
154impl<C: CurveWithScalar> From<u16> for Scalar<C> {
155    fn from(a: u16) -> Self {
156        Scalar::new(U448::from_u16(a))
157    }
158}
159
160impl<C: CurveWithScalar> From<u32> for Scalar<C> {
161    fn from(a: u32) -> Scalar<C> {
162        Scalar::new(U448::from_u32(a))
163    }
164}
165
166impl<C: CurveWithScalar> From<u64> for Scalar<C> {
167    fn from(a: u64) -> Self {
168        Scalar::new(U448::from_u64(a))
169    }
170}
171
172impl<C: CurveWithScalar> From<u128> for Scalar<C> {
173    fn from(a: u128) -> Self {
174        Scalar::new(U448::from_u128(a))
175    }
176}
177
178impl<C: CurveWithScalar> Index<usize> for Scalar<C> {
179    type Output = Word;
180
181    fn index(&self, index: usize) -> &Self::Output {
182        &self.scalar.as_words()[index]
183    }
184}
185
186impl<C: CurveWithScalar> IndexMut<usize> for Scalar<C> {
187    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
188        &mut self.scalar.as_mut_words()[index]
189    }
190}
191
192// Trait implementations
193impl<C: CurveWithScalar> Add<&Scalar<C>> for &Scalar<C> {
194    type Output = Scalar<C>;
195
196    fn add(self, rhs: &Scalar<C>) -> Self::Output {
197        self.addition(rhs)
198    }
199}
200
201define_add_variants!(GENERIC = C: CurveWithScalar, LHS = Scalar<C>, RHS = Scalar<C>, Output = Scalar<C>);
202
203impl<C: CurveWithScalar> AddAssign for Scalar<C> {
204    fn add_assign(&mut self, rhs: Self) {
205        *self = *self + rhs
206    }
207}
208
209impl<C: CurveWithScalar> AddAssign<&Scalar<C>> for Scalar<C> {
210    fn add_assign(&mut self, rhs: &Scalar<C>) {
211        *self = *self + rhs
212    }
213}
214
215impl<C: CurveWithScalar> Mul<&Scalar<C>> for &Scalar<C> {
216    type Output = Scalar<C>;
217
218    fn mul(self, rhs: &Scalar<C>) -> Self::Output {
219        self.multiply(rhs)
220    }
221}
222
223define_mul_variants!(GENERIC = C: CurveWithScalar, LHS = Scalar<C>, RHS = Scalar<C>, Output = Scalar<C>);
224
225impl<C: CurveWithScalar> MulAssign for Scalar<C> {
226    fn mul_assign(&mut self, rhs: Self) {
227        *self = *self * rhs
228    }
229}
230
231impl<C: CurveWithScalar> MulAssign<&Scalar<C>> for Scalar<C> {
232    fn mul_assign(&mut self, rhs: &Scalar<C>) {
233        *self = *self * rhs
234    }
235}
236
237impl<C: CurveWithScalar> Sub<&Scalar<C>> for &Scalar<C> {
238    type Output = Scalar<C>;
239
240    fn sub(self, rhs: &Scalar<C>) -> Self::Output {
241        self.subtract(rhs)
242    }
243}
244
245define_sub_variants!(GENERIC = C: CurveWithScalar, LHS = Scalar<C>, RHS = Scalar<C>, Output = Scalar<C>);
246
247impl<C: CurveWithScalar> SubAssign for Scalar<C> {
248    fn sub_assign(&mut self, rhs: Self) {
249        *self = *self - rhs
250    }
251}
252
253impl<C: CurveWithScalar> SubAssign<&Scalar<C>> for Scalar<C> {
254    fn sub_assign(&mut self, rhs: &Scalar<C>) {
255        *self = *self - rhs
256    }
257}
258
259impl<C: CurveWithScalar> Neg for Scalar<C> {
260    type Output = Scalar<C>;
261
262    fn neg(self) -> Self::Output {
263        -&self
264    }
265}
266
267impl<C: CurveWithScalar> Neg for &Scalar<C> {
268    type Output = Scalar<C>;
269
270    fn neg(self) -> Self::Output {
271        Scalar::ZERO - self
272    }
273}
274
275impl<C: CurveWithScalar> Sum for Scalar<C> {
276    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
277        let mut acc = Scalar::ZERO;
278        for s in iter {
279            acc += s;
280        }
281        acc
282    }
283}
284
285impl<'a, C: CurveWithScalar> Sum<&'a Scalar<C>> for Scalar<C> {
286    fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
287        let mut acc = Scalar::ZERO;
288        for s in iter {
289            acc += s;
290        }
291        acc
292    }
293}
294
295impl<C: CurveWithScalar> Product for Scalar<C> {
296    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
297        let mut acc = Scalar::ONE;
298        for s in iter {
299            acc *= s;
300        }
301        acc
302    }
303}
304
305impl<'a, C: CurveWithScalar> Product<&'a Scalar<C>> for Scalar<C> {
306    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
307        let mut acc = Scalar::ONE;
308        for s in iter {
309            acc *= s;
310        }
311        acc
312    }
313}
314
315impl<C: CurveWithScalar> Field for Scalar<C> {
316    const ZERO: Self = Self::ZERO;
317    const ONE: Self = Self::ONE;
318
319    fn try_random<R: TryRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
320        let mut seed = WideScalarBytes::<C>::default();
321        rng.try_fill_bytes(&mut seed)?;
322        Ok(C::from_bytes_mod_order_wide(&seed))
323    }
324
325    fn square(&self) -> Self {
326        self.square()
327    }
328
329    fn double(&self) -> Self {
330        self.double()
331    }
332
333    fn invert(&self) -> CtOption<Self> {
334        CtOption::new(self.invert(), !self.ct_eq(&Self::ZERO))
335    }
336
337    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
338        helpers::sqrt_ratio_generic(num, div)
339    }
340}
341
342impl<C: CurveWithScalar> PrimeField for Scalar<C> {
343    type Repr = ScalarBytes<C>;
344
345    fn from_repr(repr: Self::Repr) -> CtOption<Self> {
346        Self::from_canonical_bytes(&repr)
347    }
348    fn to_repr(&self) -> Self::Repr {
349        C::to_repr(self)
350    }
351    fn is_odd(&self) -> Choice {
352        Choice::from((self.scalar.to_words()[0] & 1) as u8)
353    }
354    const MODULUS: &'static str = "3fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f3";
355    const NUM_BITS: u32 = 446;
356    const CAPACITY: u32 = Self::NUM_BITS - 1;
357    const TWO_INV: Self = Self::new(U448::from_be_hex(
358        "1fffffffffffffffffffffffffffffffffffffffffffffffffffffffbe6511f4e2276da4d76b1b4810b6613946e2c7aa91bc614955ac227a",
359    ));
360    const MULTIPLICATIVE_GENERATOR: Self = Self::new(U448::from_u8(7));
361    const S: u32 = 1;
362
363    const ROOT_OF_UNITY: Self = Self::new(U448::from_be_hex(
364        "3fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f2",
365    ));
366
367    const ROOT_OF_UNITY_INV: Self = Self::new(U448::from_be_hex(
368        "3fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f2",
369    ));
370
371    const DELTA: Self = Self::new(U448::from_u8(49));
372}
373
374impl<C: CurveWithScalar> Generate for Scalar<C> {
375    fn try_generate_from_rng<R: TryCryptoRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
376        Self::try_random(rng)
377    }
378}
379
380#[cfg(feature = "alloc")]
381impl<C: CurveWithScalar> From<Scalar<C>> for Vec<u8> {
382    fn from(scalar: Scalar<C>) -> Vec<u8> {
383        Self::from(&scalar)
384    }
385}
386
387#[cfg(feature = "alloc")]
388impl<C: CurveWithScalar> From<&Scalar<C>> for Vec<u8> {
389    fn from(scalar: &Scalar<C>) -> Vec<u8> {
390        C::to_repr(scalar).to_vec()
391    }
392}
393
394impl<C: CurveWithScalar> From<Scalar<C>> for ScalarBytes<C> {
395    fn from(scalar: Scalar<C>) -> ScalarBytes<C> {
396        Self::from(&scalar)
397    }
398}
399
400impl<C: CurveWithScalar> From<&Scalar<C>> for ScalarBytes<C> {
401    fn from(scalar: &Scalar<C>) -> ScalarBytes<C> {
402        C::to_repr(scalar)
403    }
404}
405
406#[cfg(feature = "alloc")]
407impl<C: CurveWithScalar> TryFrom<Vec<u8>> for Scalar<C> {
408    type Error = &'static str;
409
410    fn try_from(bytes: Vec<u8>) -> Result<Self, Self::Error> {
411        Self::try_from(&bytes[..])
412    }
413}
414
415#[cfg(feature = "alloc")]
416impl<C: CurveWithScalar> TryFrom<&Vec<u8>> for Scalar<C> {
417    type Error = &'static str;
418
419    fn try_from(bytes: &Vec<u8>) -> Result<Self, Self::Error> {
420        Self::try_from(&bytes[..])
421    }
422}
423
424impl<C: CurveWithScalar> TryFrom<&[u8]> for Scalar<C> {
425    type Error = &'static str;
426
427    fn try_from(bytes: &[u8]) -> Result<Self, Self::Error> {
428        if bytes.len() != C::ReprSize::USIZE {
429            return Err("invalid byte length");
430        }
431        let scalar_bytes = ScalarBytes::<C>::try_from(bytes).expect("invalid scalar bytes");
432        Option::<Scalar<C>>::from(Scalar::from_canonical_bytes(&scalar_bytes))
433            .ok_or("scalar was not canonically encoded")
434    }
435}
436
437#[cfg(feature = "alloc")]
438impl<C: CurveWithScalar> TryFrom<Box<[u8]>> for Scalar<C> {
439    type Error = &'static str;
440
441    fn try_from(bytes: Box<[u8]>) -> Result<Self, Self::Error> {
442        Self::try_from(bytes.as_ref())
443    }
444}
445
446#[cfg(feature = "serde")]
447impl<C: CurveWithScalar> serdect::serde::Serialize for Scalar<C> {
448    fn serialize<S>(&self, s: S) -> Result<S::Ok, S::Error>
449    where
450        S: serdect::serde::Serializer,
451    {
452        serdect::slice::serialize_hex_lower_or_bin(&self.to_bytes(), s)
453    }
454}
455
456#[cfg(feature = "serde")]
457impl<'de, C: CurveWithScalar> serdect::serde::Deserialize<'de> for Scalar<C> {
458    fn deserialize<D>(d: D) -> Result<Self, D::Error>
459    where
460        D: serdect::serde::Deserializer<'de>,
461    {
462        let mut buffer = ScalarBytes::<C>::default();
463        serdect::array::deserialize_hex_or_bin(&mut buffer[..56], d)?;
464        Option::from(Self::from_canonical_bytes(&buffer)).ok_or(serdect::serde::de::Error::custom(
465            "scalar was not canonically encoded",
466        ))
467    }
468}
469
470impl<C: CurveWithScalar> elliptic_curve::zeroize::DefaultIsZeroes for Scalar<C> {}
471
472impl<C: CurveWithScalar> core::fmt::LowerHex for Scalar<C> {
473    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
474        let tmp = C::to_repr(self);
475        for &b in tmp.iter() {
476            write!(f, "{b:02x}")?;
477        }
478        Ok(())
479    }
480}
481
482impl<C: CurveWithScalar> core::fmt::UpperHex for Scalar<C> {
483    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
484        let tmp = C::to_repr(self);
485        for &b in tmp.iter() {
486            write!(f, "{b:02X}")?;
487        }
488        Ok(())
489    }
490}
491
492impl<C: CurveWithScalar> Reduce<U448> for Scalar<C> {
493    fn reduce(bytes: &U448) -> Self {
494        let (r, underflow) = bytes.borrowing_sub(&ORDER, Limb::ZERO);
495        let underflow = Choice::from((underflow.0 >> (Limb::BITS - 1)) as u8);
496        Self::new(U448::conditional_select(bytes, &r, !underflow))
497    }
498}
499
500impl<C: CurveWithScalar> Reduce<ScalarBytes<C>> for Scalar<C> {
501    fn reduce(bytes: &ScalarBytes<C>) -> Self {
502        Self::reduce(&U448::from_le_slice(bytes))
503    }
504}
505
506impl<C: CurveWithScalar> Reduce<U896> for Scalar<C> {
507    fn reduce(bytes: &U896) -> Self {
508        let (r, underflow) = bytes.borrowing_sub(&WIDE_ORDER, Limb::ZERO);
509        let underflow = Choice::from((underflow.0 >> (Limb::BITS - 1)) as u8);
510        Self::new(U896::conditional_select(bytes, &r, !underflow).split().1)
511    }
512}
513
514impl<C: CurveWithScalar> ReduceNonZero<U448> for Scalar<C> {
515    fn reduce_nonzero(bytes: &U448) -> Self {
516        let (r, underflow) = bytes.borrowing_sub(&ORDER_MINUS_ONE, Limb::ZERO);
517        let underflow = Choice::from((underflow.0 >> (Limb::BITS - 1)) as u8);
518        Self::new(U448::conditional_select(bytes, &r, !underflow).wrapping_add(&U448::ONE))
519    }
520}
521
522impl<C: CurveWithScalar> ReduceNonZero<ScalarBytes<C>> for Scalar<C> {
523    fn reduce_nonzero(bytes: &ScalarBytes<C>) -> Self {
524        Self::reduce_nonzero(&U448::from_le_slice(bytes))
525    }
526}
527
528impl<C: CurveWithScalar> ReduceNonZero<U896> for Scalar<C> {
529    fn reduce_nonzero(bytes: &U896) -> Self {
530        let (r, underflow) = bytes.borrowing_sub(&WIDE_ORDER_MINUS_ONE, Limb::ZERO);
531        let underflow = Choice::from((underflow.0 >> (Limb::BITS - 1)) as u8);
532
533        Self::new(
534            U896::conditional_select(bytes, &r, !underflow)
535                .split()
536                .1
537                .wrapping_add(&U448::ONE),
538        )
539    }
540}
541
542impl<C: CurveWithScalar> Retrieve for Scalar<C> {
543    type Output = U448;
544
545    fn retrieve(&self) -> U448 {
546        U448::from_le_byte_array(self.to_bytes().into())
547    }
548}
549
550impl<C: CurveWithScalar> From<U448> for Scalar<C> {
551    fn from(uint: U448) -> Self {
552        <Self as Reduce<U448>>::reduce(&uint)
553    }
554}
555
556impl<C: CurveWithScalar> From<&U448> for Scalar<C> {
557    fn from(uint: &U448) -> Self {
558        Self::from(*uint)
559    }
560}
561
562impl<C: CurveWithScalar> From<Scalar<C>> for U448 {
563    fn from(scalar: Scalar<C>) -> Self {
564        scalar.scalar
565    }
566}
567
568impl<C: CurveWithScalar> From<&Scalar<C>> for U448 {
569    fn from(scalar: &Scalar<C>) -> Self {
570        Self::from(*scalar)
571    }
572}
573
574impl<C: CurveWithScalar> FromUintUnchecked for Scalar<C> {
575    type Uint = U448;
576
577    fn from_uint_unchecked(uint: U448) -> Self {
578        Self::new(uint)
579    }
580}
581
582impl<C: CurveWithScalar> Invert for Scalar<C> {
583    type Output = CtOption<Self>;
584
585    fn invert(&self) -> CtOption<Self> {
586        CtOption::new(self.invert(), !self.ct_eq(&Self::ZERO))
587    }
588}
589
590impl<C: CurveWithScalar> IsHigh for Scalar<C> {
591    fn is_high(&self) -> Choice {
592        self.scalar.ct_gt(&HALF_ORDER)
593    }
594}
595
596impl<C: CurveWithScalar> AsRef<Scalar<C>> for Scalar<C> {
597    fn as_ref(&self) -> &Scalar<C> {
598        self
599    }
600}
601
602impl<C: CurveWithScalar> Shr<usize> for Scalar<C> {
603    type Output = Self;
604
605    fn shr(self, rhs: usize) -> Self::Output {
606        let mut cp = self;
607        cp.shr_assign(rhs);
608        cp
609    }
610}
611
612impl<C: CurveWithScalar> Shr<usize> for &Scalar<C> {
613    type Output = Scalar<C>;
614
615    fn shr(self, rhs: usize) -> Self::Output {
616        let mut cp = *self;
617        cp.shr_assign(rhs);
618        cp
619    }
620}
621
622impl<C: CurveWithScalar> ShrAssign<usize> for Scalar<C> {
623    fn shr_assign(&mut self, shift: usize) {
624        self.scalar >>= shift;
625    }
626}
627
628impl<C: CurveWithScalar> Scalar<C> {
629    /// The multiplicative identity element
630    pub const ONE: Scalar<C> = Scalar::new(U448::ONE);
631    /// Twice the multiplicative identity element
632    pub const TWO: Scalar<C> = Scalar::new(U448::from_u8(2));
633    /// The additive identity element
634    pub const ZERO: Scalar<C> = Scalar::new(U448::ZERO);
635
636    pub(crate) const fn new(scalar: U448) -> Self {
637        Self {
638            scalar,
639            curve: PhantomData,
640        }
641    }
642
643    /// Compute `self` + `rhs` mod ℓ
644    pub const fn addition(&self, rhs: &Self) -> Self {
645        Self::new(self.scalar.add_mod(&rhs.scalar, ORDER.as_nz_ref()))
646    }
647
648    /// Compute `self` + `self` mod ℓ
649    pub const fn double(&self) -> Self {
650        Self::new(self.scalar.double_mod(ORDER.as_nz_ref()))
651    }
652
653    /// Compute `self` - `rhs` mod ℓ
654    pub const fn subtract(&self, rhs: &Self) -> Self {
655        Self::new(self.scalar.sub_mod(&rhs.scalar, ORDER.as_nz_ref()))
656    }
657
658    /// Compute `self` * `rhs` mod ℓ
659    pub const fn multiply(&self, rhs: &Self) -> Self {
660        let wide_value = self.scalar.widening_mul(&rhs.scalar);
661        Self::new(U448::rem_wide_vartime(wide_value, ORDER.as_nz_ref()))
662    }
663
664    /// Square this scalar
665    pub const fn square(&self) -> Self {
666        let value = self.scalar.widening_square();
667        Self::new(U448::rem_wide_vartime(value, ORDER.as_nz_ref()))
668    }
669
670    /// Is this scalar equal to zero?
671    pub fn is_zero(&self) -> Choice {
672        self.scalar.is_zero().into()
673    }
674
675    // This method was modified from Curve25519-Dalek codebase. [scalar.rs]
676    // We start with 14 u32s and convert them to 56 u8s.
677    // We then use the code copied from Dalek to convert the 56 u8s to radix-16 and re-center the coefficients to be between [-16,16)
678    // XXX: We can recode the scalar without converting it to bytes, will refactor this method to use this and check which is faster.
679    pub(crate) fn to_radix_16(self) -> [i8; 113] {
680        let bytes = self.to_bytes();
681        let mut output = [0i8; 113];
682
683        // Step 1: change radix.
684        // Convert from radix 256 (bytes) to radix 16 (nibbles)
685        #[inline(always)]
686        fn bot_half(x: u8) -> u8 {
687            x & 15
688        }
689        #[inline(always)]
690        fn top_half(x: u8) -> u8 {
691            (x >> 4) & 15
692        }
693
694        // radix-16
695        for i in 0..56 {
696            output[2 * i] = bot_half(bytes[i]) as i8;
697            output[2 * i + 1] = top_half(bytes[i]) as i8;
698        }
699        // re-center co-efficients to be between [-8, 8)
700        for i in 0..112 {
701            let carry = (output[i] + 8) >> 4;
702            output[i] -= carry << 4;
703            output[i + 1] += carry;
704        }
705
706        output
707    }
708
709    // XXX: Better if this method returns an array of 448 items
710    /// Returns the bits of the scalar in little-endian order.
711    pub fn bits(&self) -> [bool; 448] {
712        let mut bits = [false; 448];
713        let mut i = 0;
714        // We have 56 limbs, each 8 bits
715        // First we iterate each limb
716        for limb in self.to_bytes().iter() {
717            // Then we iterate each bit in the limb
718            for j in 0..8 {
719                bits[i] = limb & (1 << j) != 0;
720                i += 1;
721            }
722        }
723
724        // XXX :We are doing LSB first
725        bits
726    }
727
728    /// Convert this `Scalar` to a little-endian byte array.
729    pub fn to_bytes(&self) -> [u8; 56] {
730        self.scalar.to_le_byte_array().0
731    }
732
733    /// Invert this scalar
734    pub fn invert(&self) -> Self {
735        Self::conditional_select(
736            &self.exp_vartime(&[
737                0x2378c292ab5844f1,
738                0x216cc2728dc58f55,
739                0xc44edb49aed63690,
740                0xffffffff7cca23e9,
741                0xffffffffffffffff,
742                0xffffffffffffffff,
743                0x3fffffffffffffff,
744            ]),
745            &Self::ZERO,
746            self.is_zero(),
747        )
748    }
749
750    /// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
751    /// exponent.
752    pub const fn exp_vartime(&self, exp: &[u64]) -> Self {
753        let mut res = Self::ONE;
754
755        let mut i = exp.len();
756        while i > 0 {
757            i -= 1;
758
759            let mut j = 64;
760            while j > 0 {
761                j -= 1;
762                res = res.square();
763
764                if ((exp[i] >> j) & 1) == 1 {
765                    res = res.multiply(self);
766                }
767            }
768        }
769
770        res
771    }
772
773    /// Return the square root of this scalar, if it is a quadratic residue.
774    pub fn sqrt(&self) -> CtOption<Self> {
775        let ss = self.pow([
776            0x48de30a4aad6113d,
777            0x085b309ca37163d5,
778            0x7113b6d26bb58da4,
779            0xffffffffdf3288fa,
780            0xffffffffffffffff,
781            0xffffffffffffffff,
782            0x0fffffffffffffff,
783        ]);
784        CtOption::new(ss, ss.square().ct_eq(self))
785    }
786
787    /// Halves a Scalar modulo the prime
788    pub fn div_by_2(&self) -> Self {
789        let is_odd = self.scalar.is_odd();
790        let if_odd = self.scalar + *ORDER;
791        let scalar = U448::ct_select(&self.scalar, &if_odd, is_odd);
792
793        Self::new(scalar >> 1)
794    }
795
796    /// Attempt to construct a `Scalar` from a canonical byte representation.
797    ///
798    /// # Return
799    ///
800    /// - `Some(s)`, where `s` is the `Scalar` corresponding to `bytes`,
801    ///   if `bytes` is a canonical byte representation;
802    /// - `None` if `bytes` is not a canonical byte representation.
803    pub fn from_canonical_bytes(bytes: &ScalarBytes<C>) -> CtOption<Self> {
804        C::from_canonical_bytes(bytes)
805    }
806
807    /// Construct a Scalar by reducing a 448-bit little-endian integer modulo the group order ℓ
808    pub fn from_bytes_mod_order(input: &ScalarBytes<C>) -> Scalar<C> {
809        let value = U448::from_le_slice(&input[..56]);
810        Self::new(value.rem_vartime(ORDER.as_nz_ref()))
811    }
812
813    /// Return a `Scalar` chosen uniformly at random using a user-provided RNG.
814    ///
815    /// # Inputs
816    ///
817    /// * `rng`: any RNG which implements the `Rng + CryptoRng` interface.
818    ///
819    /// # Returns
820    ///
821    /// A random scalar within ℤ/lℤ.
822    pub fn random<R: Rng + CryptoRng>(rng: &mut R) -> Self {
823        let mut scalar_bytes = WideScalarBytes::<C>::default();
824        rng.fill_bytes(&mut scalar_bytes);
825        C::from_bytes_mod_order_wide(&scalar_bytes)
826    }
827}
ed448_goldilocks/field/scalar.rs

ed448_goldilocks/field/
scalar.rs
