k256/arithmetic/
scalar.rs

1//! Scalar field arithmetic.
2
3use crate::{FieldBytes, NonZeroScalar, ORDER, ORDER_HEX, Secp256k1, WideBytes};
4use core::iter::{Product, Sum};
5use elliptic_curve::{
6    Curve, Error, Generate, ScalarValue,
7    bigint::{ArrayEncoding, Limb, U256, U512, Word, cpubits, modular::Retrieve},
8    ctutils,
9    ff::{self, Field, FromUniformBytes, PrimeField},
10    ops::{
11        Add, AddAssign, Invert, Mul, MulAssign, Neg, Reduce, ReduceNonZero, Shr, ShrAssign, Sub,
12        SubAssign,
13    },
14    rand_core::{CryptoRng, TryCryptoRng, TryRng},
15    scalar::{FromUintUnchecked, IsHigh},
16    subtle::{
17        Choice, ConditionallySelectable, ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess,
18        CtOption,
19    },
20    zeroize::DefaultIsZeroes,
21};
22use primeorder::{FieldExt, PrimeFieldExt};
23
24cpubits! {
25    32 => {
26        #[path = "scalar/wide32.rs"]
27        mod wide;
28    }
29    64 => {
30         #[path = "scalar/wide64.rs"]
31        mod wide;
32    }
33}
34pub(crate) use self::wide::WideScalar;
35
36#[cfg(feature = "serde")]
37use serdect::serde::{Deserialize, Serialize, de, ser};
38
39#[cfg(test)]
40use num_bigint::{BigUint, ToBigUint};
41
42/// Constant representing the modulus
43/// n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
44const MODULUS: [Word; U256::LIMBS] = ORDER.as_ref().to_words();
45
46/// Constant representing the modulus / 2
47const FRAC_MODULUS_2: U256 = ORDER.as_ref().shr_vartime(1);
48
49/// Scalars are elements in the finite field modulo n.
50///
51/// # Trait impls
52///
53/// Much of the important functionality of scalars is provided by traits from
54/// the [`ff`](https://docs.rs/ff/) crate, which is re-exported as
55/// `k256::elliptic_curve::ff`:
56///
57/// - [`Field`](https://docs.rs/ff/latest/ff/trait.Field.html) -
58///   represents elements of finite fields and provides:
59///   - [`Field::random`](https://docs.rs/ff/latest/ff/trait.Field.html#tymethod.random) -
60///     generate a random scalar
61///   - `double`, `square`, and `invert` operations
62///   - Bounds for [`Add`], [`Sub`], [`Mul`], and [`Neg`] (as well as `*Assign` equivalents)
63///   - Bounds for [`ConditionallySelectable`] from the `subtle` crate
64/// - [`PrimeField`](https://docs.rs/ff/latest/ff/trait.PrimeField.html) -
65///   represents elements of prime fields and provides:
66///   - `from_repr`/`to_repr` for converting field elements from/to big integers.
67///   - `multiplicative_generator` and `root_of_unity` constants.
68///
69/// Please see the documentation for the relevant traits for more information.
70///
71/// # `serde` support
72///
73/// When the `serde` feature of this crate is enabled, the `Serialize` and
74/// `Deserialize` traits are impl'd for this type.
75///
76/// The serialization is a fixed-width big endian encoding. When used with
77/// textual formats, the binary data is encoded as hexadecimal.
78#[derive(Clone, Copy, Debug, Default, PartialOrd, Ord)]
79pub struct Scalar(pub(crate) U256);
80
81impl Scalar {
82    /// Zero scalar.
83    pub const ZERO: Self = Self(U256::ZERO);
84
85    /// Multiplicative identity.
86    pub const ONE: Self = Self(U256::ONE);
87
88    /// Checks if the scalar is zero.
89    #[must_use]
90    pub fn is_zero(&self) -> Choice {
91        self.0.is_zero().into()
92    }
93
94    /// Returns the SEC1 encoding of this scalar.
95    #[must_use]
96    pub fn to_bytes(&self) -> FieldBytes {
97        self.0.to_be_byte_array()
98    }
99
100    /// Negates the scalar.
101    #[must_use]
102    pub const fn negate(&self) -> Self {
103        Self(self.0.neg_mod(ORDER.as_nz_ref()))
104    }
105
106    /// Returns self + rhs mod n.
107    #[must_use]
108    pub const fn add(&self, rhs: &Self) -> Self {
109        Self(self.0.add_mod(&rhs.0, ORDER.as_nz_ref()))
110    }
111
112    /// Returns self - rhs mod n.
113    #[must_use]
114    pub const fn sub(&self, rhs: &Self) -> Self {
115        Self(self.0.sub_mod(&rhs.0, ORDER.as_nz_ref()))
116    }
117
118    /// Modulo multiplies two scalars.
119    #[must_use]
120    pub fn mul(&self, rhs: &Scalar) -> Scalar {
121        WideScalar::mul_wide(self, rhs).reduce()
122    }
123
124    /// Modulo squares the scalar.
125    #[must_use]
126    pub fn square(&self) -> Self {
127        self.mul(self)
128    }
129
130    /// Right shifts the scalar.
131    ///
132    /// Note: not constant-time with respect to the `shift` parameter.
133    #[must_use]
134    pub fn shr_vartime(&self, shift: u32) -> Scalar {
135        Self(self.0.unbounded_shr_vartime(shift))
136    }
137
138    /// Returns the multiplicative inverse of self, if self is non-zero.
139    pub fn invert(&self) -> CtOption<Self> {
140        let inv = self.retrieve().invert_odd_mod(&ORDER);
141
142        CtOption::from(inv).map(Self::from_uint_unchecked)
143    }
144
145    /// Returns the multiplicative inverse of self in variable-time, if self is non-zero.
146    pub fn invert_vartime(&self) -> CtOption<Self> {
147        let inv = self.retrieve().invert_odd_mod_vartime(&ORDER);
148
149        CtOption::from(inv).map(Self::from_uint_unchecked)
150    }
151
152    /// Returns the scalar modulus as a `BigUint` object.
153    #[cfg(test)]
154    #[must_use]
155    #[allow(clippy::missing_panics_doc, reason = "test")]
156    pub fn modulus_as_biguint() -> BigUint {
157        Self::ONE.negate().to_biguint().unwrap() + 1.to_biguint().unwrap()
158    }
159
160    /// Returns a (nearly) uniformly-random scalar, generated in constant time.
161    pub fn generate_biased_from_rng<R: CryptoRng + ?Sized>(rng: &mut R) -> Self {
162        let Ok(scalar) = Self::try_generate_biased_from_rng(rng);
163        scalar
164    }
165
166    /// Returns a (nearly) uniformly-random scalar, generated in constant time.
167    ///
168    /// # Errors
169    /// Propagates `R::Error` on RNG failure.
170    pub fn try_generate_biased_from_rng<R: TryCryptoRng + ?Sized>(
171        rng: &mut R,
172    ) -> Result<Self, R::Error> {
173        // We reduce a random 512-bit value into a 256-bit field, which results in a
174        // negligible bias from the uniform distribution, but the process is constant-time.
175        let mut buf = [0u8; 64];
176        rng.try_fill_bytes(&mut buf)?;
177        Ok(WideScalar::from_bytes(&buf).reduce())
178    }
179
180    /// Attempts to parse the given byte array as a scalar.
181    /// Does not check the result for being in the correct range.
182    pub(crate) const fn from_bytes_unchecked(bytes: &[u8; 32]) -> Self {
183        Self(U256::from_be_slice(bytes))
184    }
185}
186
187impl AsRef<Scalar> for Scalar {
188    fn as_ref(&self) -> &Scalar {
189        self
190    }
191}
192
193impl DefaultIsZeroes for Scalar {}
194
195impl Field for Scalar {
196    const ZERO: Self = Self::ZERO;
197    const ONE: Self = Self::ONE;
198
199    fn try_random<R: TryRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
200        // Uses rejection sampling as the default random generation method,
201        // which produces a uniformly random distribution of scalars.
202        //
203        // This method is not constant time, but should be secure so long as
204        // rejected RNG outputs are unrelated to future ones (which is a
205        // necessary property of a `CryptoRng`).
206        //
207        // With an unbiased RNG, the probability of failing to complete after 4
208        // iterations is vanishingly small.
209        let mut bytes = FieldBytes::default();
210
211        // TODO: pre-generate several scalars to bring the probability of non-constant-timeness down?
212        loop {
213            rng.try_fill_bytes(&mut bytes)?;
214            if let Some(scalar) = Scalar::from_repr(bytes).into() {
215                return Ok(scalar);
216            }
217        }
218    }
219
220    fn square(&self) -> Self {
221        Scalar::square(self)
222    }
223
224    fn double(&self) -> Self {
225        self.add(self)
226    }
227
228    fn invert(&self) -> CtOption<Self> {
229        Scalar::invert(self)
230    }
231
232    /// Tonelli-Shank's algorithm for q mod 16 = 1
233    /// <https://eprint.iacr.org/2012/685.pdf> (page 12, algorithm 5)
234    #[allow(clippy::many_single_char_names)]
235    fn sqrt(&self) -> CtOption<Self> {
236        // Note: `pow_vartime` is constant-time with respect to `self`
237        let w = self.pow_vartime([
238            0x777fa4bd19a06c82,
239            0xfd755db9cd5e9140,
240            0xffffffffffffffff,
241            0x1ffffffffffffff,
242        ]);
243
244        let mut v = Self::S;
245        let mut x = *self * w;
246        let mut b = x * w;
247        let mut z = Self::ROOT_OF_UNITY;
248
249        for max_v in (1..=Self::S).rev() {
250            let mut k = 1;
251            let mut tmp = b.square();
252            let mut j_less_than_v = Choice::from(1);
253
254            for j in 2..max_v {
255                let tmp_is_one = tmp.ct_eq(&Self::ONE);
256                let squared = Self::conditional_select(&tmp, &z, tmp_is_one).square();
257                tmp = Self::conditional_select(&squared, &tmp, tmp_is_one);
258                let new_z = Self::conditional_select(&z, &squared, tmp_is_one);
259                j_less_than_v &= !ConstantTimeEq::ct_eq(&j, &v);
260                k = u32::conditional_select(&j, &k, tmp_is_one);
261                z = Self::conditional_select(&z, &new_z, j_less_than_v);
262            }
263
264            let result = x * z;
265            x = Self::conditional_select(&result, &x, b.ct_eq(&Self::ONE));
266            z = z.square();
267            b *= z;
268            v = k;
269        }
270
271        CtOption::new(x, x.square().ct_eq(self))
272    }
273
274    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
275        ff::helpers::sqrt_ratio_generic(num, div)
276    }
277}
278
279impl Generate for Scalar {
280    fn try_generate_from_rng<R: TryCryptoRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
281        Self::try_random(rng)
282    }
283}
284
285impl PrimeField for Scalar {
286    type Repr = FieldBytes;
287
288    const MODULUS: &'static str = ORDER_HEX;
289    const NUM_BITS: u32 = 256;
290    const CAPACITY: u32 = 255;
291    const TWO_INV: Self = Self(U256::from_be_hex(
292        "7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1",
293    ));
294    const MULTIPLICATIVE_GENERATOR: Self = Self(U256::from_u8(7));
295    const S: u32 = 6;
296    const ROOT_OF_UNITY: Self = Self(U256::from_be_hex(
297        "0c1dc060e7a91986df9879a3fbc483a898bdeab680756045992f4b5402b052f2",
298    ));
299    const ROOT_OF_UNITY_INV: Self = Self(U256::from_be_hex(
300        "fd3ae181f12d7096efc7b0c75b8cbb7277a275910aa413c3b6fb30a0884f0d1c",
301    ));
302    const DELTA: Self = Self(U256::from_be_hex(
303        "0000000000000000000cbc21fe4561c8d63b78e780e1341e199417c8c0bb7601",
304    ));
305
306    /// Attempts to parse the given byte array as an SEC1-encoded scalar.
307    ///
308    /// Returns None if the byte array does not contain a big-endian integer in the range
309    /// [0, p).
310    fn from_repr(bytes: FieldBytes) -> CtOption<Self> {
311        let inner = U256::from_be_byte_array(bytes);
312        CtOption::new(
313            Self(inner),
314            ConstantTimeLess::ct_lt(&inner, &Secp256k1::ORDER),
315        )
316    }
317
318    fn to_repr(&self) -> FieldBytes {
319        self.to_bytes()
320    }
321
322    fn is_odd(&self) -> Choice {
323        self.0.is_odd().into()
324    }
325}
326
327impl FieldExt for Scalar {}
328impl PrimeFieldExt for Scalar {}
329
330impl From<u32> for Scalar {
331    fn from(k: u32) -> Self {
332        Self(k.into())
333    }
334}
335
336impl From<u64> for Scalar {
337    fn from(k: u64) -> Self {
338        Self(k.into())
339    }
340}
341
342impl From<u128> for Scalar {
343    fn from(k: u128) -> Self {
344        Self(k.into())
345    }
346}
347
348impl FromUniformBytes<64> for Scalar {
349    fn from_uniform_bytes(bytes: &[u8; 64]) -> Self {
350        WideScalar::from_bytes(bytes).reduce()
351    }
352}
353
354impl From<NonZeroScalar> for Scalar {
355    fn from(scalar: NonZeroScalar) -> Self {
356        *scalar.as_ref()
357    }
358}
359
360impl From<&NonZeroScalar> for Scalar {
361    fn from(scalar: &NonZeroScalar) -> Self {
362        *scalar.as_ref()
363    }
364}
365
366impl From<ScalarValue<Secp256k1>> for Scalar {
367    fn from(scalar: ScalarValue<Secp256k1>) -> Scalar {
368        Scalar(*scalar.as_uint())
369    }
370}
371
372impl From<&ScalarValue<Secp256k1>> for Scalar {
373    fn from(scalar: &ScalarValue<Secp256k1>) -> Scalar {
374        Scalar(*scalar.as_uint())
375    }
376}
377
378impl From<Scalar> for ScalarValue<Secp256k1> {
379    fn from(scalar: Scalar) -> ScalarValue<Secp256k1> {
380        ScalarValue::from(&scalar)
381    }
382}
383
384impl From<&Scalar> for ScalarValue<Secp256k1> {
385    fn from(scalar: &Scalar) -> ScalarValue<Secp256k1> {
386        ScalarValue::new(scalar.0).unwrap()
387    }
388}
389
390/// The constant-time alternative is available at [`NonZeroScalar::new()`].
391impl TryFrom<Scalar> for NonZeroScalar {
392    type Error = Error;
393
394    fn try_from(scalar: Scalar) -> Result<Self, Error> {
395        NonZeroScalar::new(scalar).into_option().ok_or(Error)
396    }
397}
398
399impl FromUintUnchecked for Scalar {
400    type Uint = U256;
401
402    fn from_uint_unchecked(uint: Self::Uint) -> Self {
403        Self(uint)
404    }
405}
406
407impl Invert for Scalar {
408    type Output = CtOption<Self>;
409
410    fn invert(&self) -> CtOption<Self> {
411        Scalar::invert(self)
412    }
413
414    fn invert_vartime(&self) -> CtOption<Self> {
415        Scalar::invert_vartime(self)
416    }
417}
418
419impl IsHigh for Scalar {
420    fn is_high(&self) -> Choice {
421        ConstantTimeGreater::ct_gt(&self.0, &FRAC_MODULUS_2)
422    }
423}
424
425impl Shr<usize> for Scalar {
426    type Output = Self;
427
428    fn shr(self, rhs: usize) -> Self::Output {
429        #[allow(clippy::cast_possible_truncation)]
430        self.shr_vartime(rhs as u32)
431    }
432}
433
434impl Shr<usize> for &Scalar {
435    type Output = Scalar;
436
437    fn shr(self, rhs: usize) -> Self::Output {
438        #[allow(clippy::cast_possible_truncation)]
439        self.shr_vartime(rhs as u32)
440    }
441}
442
443impl ShrAssign<usize> for Scalar {
444    fn shr_assign(&mut self, rhs: usize) {
445        *self = *self >> rhs;
446    }
447}
448
449impl ConditionallySelectable for Scalar {
450    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
451        Self(U256::conditional_select(&a.0, &b.0, choice))
452    }
453}
454
455impl ConstantTimeEq for Scalar {
456    fn ct_eq(&self, other: &Self) -> Choice {
457        ConstantTimeEq::ct_eq(&self.0, &other.0)
458    }
459}
460
461impl ctutils::CtEq for Scalar {
462    fn ct_eq(&self, other: &Self) -> ctutils::Choice {
463        ConstantTimeEq::ct_eq(self, other).into()
464    }
465}
466
467impl ctutils::CtSelect for Scalar {
468    fn ct_select(&self, other: &Self, choice: ctutils::Choice) -> Self {
469        ConditionallySelectable::conditional_select(self, other, choice.into())
470    }
471}
472
473impl PartialEq for Scalar {
474    fn eq(&self, other: &Self) -> bool {
475        ConstantTimeEq::ct_eq(self, other).into()
476    }
477}
478
479impl Eq for Scalar {}
480
481impl Neg for Scalar {
482    type Output = Scalar;
483
484    fn neg(self) -> Scalar {
485        self.negate()
486    }
487}
488
489impl Neg for &Scalar {
490    type Output = Scalar;
491
492    fn neg(self) -> Scalar {
493        self.negate()
494    }
495}
496
497impl Add<Scalar> for Scalar {
498    type Output = Scalar;
499
500    fn add(self, other: Scalar) -> Scalar {
501        Scalar::add(&self, &other)
502    }
503}
504
505impl Add<&Scalar> for &Scalar {
506    type Output = Scalar;
507
508    fn add(self, other: &Scalar) -> Scalar {
509        Scalar::add(self, other)
510    }
511}
512
513impl Add<Scalar> for &Scalar {
514    type Output = Scalar;
515
516    fn add(self, other: Scalar) -> Scalar {
517        Scalar::add(self, &other)
518    }
519}
520
521impl Add<&Scalar> for Scalar {
522    type Output = Scalar;
523
524    fn add(self, other: &Scalar) -> Scalar {
525        Scalar::add(&self, other)
526    }
527}
528
529impl AddAssign<Scalar> for Scalar {
530    #[inline]
531    fn add_assign(&mut self, rhs: Scalar) {
532        *self = Scalar::add(self, &rhs);
533    }
534}
535
536impl AddAssign<&Scalar> for Scalar {
537    fn add_assign(&mut self, rhs: &Scalar) {
538        *self = Scalar::add(self, rhs);
539    }
540}
541
542impl Sub<Scalar> for Scalar {
543    type Output = Scalar;
544
545    fn sub(self, other: Scalar) -> Scalar {
546        Scalar::sub(&self, &other)
547    }
548}
549
550impl Sub<&Scalar> for &Scalar {
551    type Output = Scalar;
552
553    fn sub(self, other: &Scalar) -> Scalar {
554        Scalar::sub(self, other)
555    }
556}
557
558impl Sub<&Scalar> for Scalar {
559    type Output = Scalar;
560
561    fn sub(self, other: &Scalar) -> Scalar {
562        Scalar::sub(&self, other)
563    }
564}
565
566impl SubAssign<Scalar> for Scalar {
567    fn sub_assign(&mut self, rhs: Scalar) {
568        *self = Scalar::sub(self, &rhs);
569    }
570}
571
572impl SubAssign<&Scalar> for Scalar {
573    fn sub_assign(&mut self, rhs: &Scalar) {
574        *self = Scalar::sub(self, rhs);
575    }
576}
577
578impl Mul<Scalar> for Scalar {
579    type Output = Scalar;
580
581    fn mul(self, other: Scalar) -> Scalar {
582        Scalar::mul(&self, &other)
583    }
584}
585
586impl Mul<&Scalar> for &Scalar {
587    type Output = Scalar;
588
589    fn mul(self, other: &Scalar) -> Scalar {
590        Scalar::mul(self, other)
591    }
592}
593
594impl Mul<&Scalar> for Scalar {
595    type Output = Scalar;
596
597    fn mul(self, other: &Scalar) -> Scalar {
598        Scalar::mul(&self, other)
599    }
600}
601
602elliptic_curve::scalar_mul_impls!(Secp256k1, Scalar);
603
604wnaf::impl_wnaf_size_for_scalar!(Scalar);
605
606impl MulAssign<Scalar> for Scalar {
607    fn mul_assign(&mut self, rhs: Scalar) {
608        *self = Scalar::mul(self, &rhs);
609    }
610}
611
612impl MulAssign<&Scalar> for Scalar {
613    fn mul_assign(&mut self, rhs: &Scalar) {
614        *self = Scalar::mul(self, rhs);
615    }
616}
617
618impl Reduce<U256> for Scalar {
619    fn reduce(w: &U256) -> Self {
620        let (r, underflow) = w.borrowing_sub(&ORDER, Limb::ZERO);
621        let underflow = Choice::from((underflow.0 >> (Limb::BITS - 1)) as u8);
622        Self(U256::conditional_select(w, &r, !underflow))
623    }
624}
625
626impl Reduce<FieldBytes> for Scalar {
627    #[inline]
628    fn reduce(bytes: &FieldBytes) -> Self {
629        Self::reduce(&U256::from_be_byte_array(*bytes))
630    }
631}
632
633impl Reduce<U512> for Scalar {
634    fn reduce(w: &U512) -> Self {
635        WideScalar(*w).reduce()
636    }
637}
638
639impl Reduce<WideBytes> for Scalar {
640    fn reduce(bytes: &WideBytes) -> Self {
641        Self::reduce(&U512::from_be_byte_array(*bytes))
642    }
643}
644
645impl ReduceNonZero<U256> for Scalar {
646    fn reduce_nonzero(w: &U256) -> Self {
647        const ORDER_MINUS_ONE: U256 = ORDER.as_ref().wrapping_sub(&U256::ONE);
648        let (r, underflow) = w.borrowing_sub(&ORDER_MINUS_ONE, Limb::ZERO);
649        let underflow = Choice::from((underflow.0 >> (Limb::BITS - 1)) as u8);
650        Self(U256::conditional_select(w, &r, !underflow).wrapping_add(&U256::ONE))
651    }
652}
653
654impl ReduceNonZero<FieldBytes> for Scalar {
655    #[inline]
656    fn reduce_nonzero(bytes: &FieldBytes) -> Self {
657        Self::reduce_nonzero(&U256::from_be_byte_array(*bytes))
658    }
659}
660
661impl ReduceNonZero<U512> for Scalar {
662    fn reduce_nonzero(w: &U512) -> Self {
663        WideScalar(*w).reduce_nonzero()
664    }
665}
666
667impl ReduceNonZero<WideBytes> for Scalar {
668    #[inline]
669    fn reduce_nonzero(bytes: &WideBytes) -> Self {
670        Self::reduce_nonzero(&U512::from_be_byte_array(*bytes))
671    }
672}
673
674impl Retrieve for Scalar {
675    type Output = U256;
676
677    fn retrieve(&self) -> U256 {
678        self.0
679    }
680}
681
682impl Sum for Scalar {
683    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
684        iter.reduce(Add::add).unwrap_or(Self::ZERO)
685    }
686}
687
688impl<'a> Sum<&'a Scalar> for Scalar {
689    fn sum<I: Iterator<Item = &'a Scalar>>(iter: I) -> Self {
690        iter.copied().sum()
691    }
692}
693
694impl Product for Scalar {
695    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
696        iter.reduce(Mul::mul).unwrap_or(Self::ONE)
697    }
698}
699
700impl<'a> Product<&'a Scalar> for Scalar {
701    fn product<I: Iterator<Item = &'a Scalar>>(iter: I) -> Self {
702        iter.copied().product()
703    }
704}
705
706impl From<Scalar> for FieldBytes {
707    fn from(scalar: Scalar) -> Self {
708        scalar.to_bytes()
709    }
710}
711
712impl From<&Scalar> for FieldBytes {
713    fn from(scalar: &Scalar) -> Self {
714        scalar.to_bytes()
715    }
716}
717
718impl From<Scalar> for U256 {
719    fn from(scalar: Scalar) -> Self {
720        scalar.0
721    }
722}
723
724impl From<&Scalar> for U256 {
725    fn from(scalar: &Scalar) -> Self {
726        scalar.0
727    }
728}
729
730#[cfg(feature = "serde")]
731impl Serialize for Scalar {
732    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
733    where
734        S: ser::Serializer,
735    {
736        ScalarValue::from(self).serialize(serializer)
737    }
738}
739
740#[cfg(feature = "serde")]
741impl<'de> Deserialize<'de> for Scalar {
742    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
743    where
744        D: de::Deserializer<'de>,
745    {
746        Ok(ScalarValue::deserialize(deserializer)?.into())
747    }
748}
749
750#[cfg(test)]
751mod tests {
752    use super::Scalar;
753    use crate::{
754        FieldBytes, NonZeroScalar, ORDER, WideBytes,
755        arithmetic::dev::{biguint_to_bytes, bytes_to_biguint},
756    };
757    use elliptic_curve::{
758        array::Array,
759        bigint::{ArrayEncoding, U256, U512},
760        ff::{Field, PrimeField},
761        ops::Reduce,
762        scalar::IsHigh,
763    };
764    use num_bigint::{BigUint, ToBigUint};
765    use num_traits::Zero;
766    use proptest::prelude::*;
767
768    #[cfg(feature = "getrandom")]
769    use elliptic_curve::{Generate, common::getrandom::SysRng};
770
771    impl From<&BigUint> for Scalar {
772        fn from(x: &BigUint) -> Self {
773            debug_assert!(x < &Scalar::modulus_as_biguint());
774            let bytes = biguint_to_bytes(x);
775            Self::from_repr(bytes.into()).unwrap()
776        }
777    }
778
779    impl From<BigUint> for Scalar {
780        fn from(x: BigUint) -> Self {
781            Self::from(&x)
782        }
783    }
784
785    impl ToBigUint for Scalar {
786        fn to_biguint(&self) -> Option<BigUint> {
787            Some(bytes_to_biguint(self.to_bytes().as_ref()))
788        }
789    }
790
791    /// t = (modulus - 1) >> S
792    const T: [u64; 4] = [
793        0xeeff497a3340d905,
794        0xfaeabb739abd2280,
795        0xffffffffffffffff,
796        0x03ffffffffffffff,
797    ];
798
799    #[test]
800    fn two_inv_constant() {
801        assert_eq!(Scalar::from(2u32) * Scalar::TWO_INV, Scalar::ONE);
802    }
803
804    #[test]
805    fn root_of_unity_constant() {
806        // ROOT_OF_UNITY^{2^s} mod m == 1
807        assert_eq!(
808            Scalar::ROOT_OF_UNITY.pow_vartime([1u64 << Scalar::S, 0, 0, 0]),
809            Scalar::ONE
810        );
811
812        // MULTIPLICATIVE_GENERATOR^{t} mod m == ROOT_OF_UNITY
813        assert_eq!(
814            Scalar::MULTIPLICATIVE_GENERATOR.pow_vartime(T),
815            Scalar::ROOT_OF_UNITY
816        );
817    }
818
819    #[test]
820    fn root_of_unity_inv_constant() {
821        assert_eq!(
822            Scalar::ROOT_OF_UNITY * Scalar::ROOT_OF_UNITY_INV,
823            Scalar::ONE
824        );
825    }
826
827    #[test]
828    fn delta_constant() {
829        // DELTA^{t} mod m == 1
830        assert_eq!(Scalar::DELTA.pow_vartime(T), Scalar::ONE);
831    }
832
833    #[test]
834    fn is_high() {
835        // 0 is not high
836        let high: bool = Scalar::ZERO.is_high().into();
837        assert!(!high);
838
839        // 1 is not high
840        let one = 1.to_biguint().unwrap();
841        let high: bool = Scalar::from(&one).is_high().into();
842        assert!(!high);
843
844        let m = Scalar::modulus_as_biguint();
845        let m_by_2 = &m >> 1;
846
847        // M / 2 is not high
848        let high: bool = Scalar::from(&m_by_2).is_high().into();
849        assert!(!high);
850
851        // M / 2 + 1 is high
852        let high: bool = Scalar::from(&m_by_2 + &one).is_high().into();
853        assert!(high);
854
855        // MODULUS - 1 is high
856        let high: bool = Scalar::from(&m - &one).is_high().into();
857        assert!(high);
858    }
859
860    /// Basic tests that sqrt works.
861    #[test]
862    fn sqrt() {
863        for &n in &[1u64, 4, 9, 16, 25, 36, 49, 64] {
864            let scalar = Scalar::from(n);
865            let sqrt = scalar.sqrt().unwrap();
866            assert_eq!(sqrt.square(), scalar);
867        }
868    }
869
870    /// Basic tests that `invert` works.
871    #[test]
872    fn invert() {
873        assert_eq!(Scalar::ONE, Scalar::ONE.invert().unwrap());
874
875        let three = Scalar::from(3u64);
876        let inv_three = three.invert().unwrap();
877        assert_eq!(three * inv_three, Scalar::ONE);
878
879        let minus_three = -three;
880        let inv_minus_three = minus_three.invert().unwrap();
881        assert_eq!(inv_minus_three, -inv_three);
882        assert_eq!(three * inv_minus_three, -Scalar::ONE);
883
884        assert!(bool::from(Scalar::ZERO.invert().is_none()));
885        assert_eq!(Scalar::from(2u64).invert().unwrap(), Scalar::TWO_INV);
886        assert_eq!(
887            Scalar::ROOT_OF_UNITY.invert_vartime().unwrap(),
888            Scalar::ROOT_OF_UNITY_INV
889        );
890    }
891
892    /// Basic tests that `invert_vartime` works.
893    #[test]
894    fn invert_vartime() {
895        assert_eq!(Scalar::ONE, Scalar::ONE.invert_vartime().unwrap());
896
897        let three = Scalar::from(3u64);
898        let inv_three = three.invert_vartime().unwrap();
899        assert_eq!(three * inv_three, Scalar::ONE);
900
901        let minus_three = -three;
902        let inv_minus_three = minus_three.invert_vartime().unwrap();
903        assert_eq!(inv_minus_three, -inv_three);
904        assert_eq!(three * inv_minus_three, -Scalar::ONE);
905
906        assert!(bool::from(Scalar::ZERO.invert_vartime().is_none()));
907        assert_eq!(
908            Scalar::from(2u64).invert_vartime().unwrap(),
909            Scalar::TWO_INV
910        );
911        assert_eq!(
912            Scalar::ROOT_OF_UNITY.invert_vartime().unwrap(),
913            Scalar::ROOT_OF_UNITY_INV
914        );
915    }
916
917    #[test]
918    fn negate() {
919        let zero_neg = -Scalar::ZERO;
920        assert_eq!(zero_neg, Scalar::ZERO);
921
922        let m = Scalar::modulus_as_biguint();
923        let one = 1.to_biguint().unwrap();
924        let m_minus_one = &m - &one;
925        let m_by_2 = &m >> 1;
926
927        let one_neg = -Scalar::ONE;
928        assert_eq!(one_neg, Scalar::from(&m_minus_one));
929
930        let frac_modulus_2_neg = -Scalar::from(&m_by_2);
931        let frac_modulus_2_plus_one = Scalar::from(&m_by_2 + &one);
932        assert_eq!(frac_modulus_2_neg, frac_modulus_2_plus_one);
933
934        let modulus_minus_one_neg = -Scalar::from(&m - &one);
935        assert_eq!(modulus_minus_one_neg, Scalar::ONE);
936    }
937
938    #[test]
939    fn add_result_within_256_bits() {
940        // A regression for a bug where reduction was not applied
941        // when the unreduced result of addition was in the range `[modulus, 2^256)`.
942        let t = 1.to_biguint().unwrap() << 255;
943        let one = 1.to_biguint().unwrap();
944
945        let a = Scalar::from(&t - &one);
946        let b = Scalar::from(&t);
947        let res = a + b;
948
949        let m = Scalar::modulus_as_biguint();
950        let res_ref = Scalar::from((&t + &t - &one) % &m);
951
952        assert_eq!(res, res_ref);
953    }
954
955    #[cfg(feature = "getrandom")]
956    #[allow(clippy::op_ref)]
957    #[test]
958    fn try_generate_biased_from_rng() {
959        let a = Scalar::try_generate_biased_from_rng(&mut SysRng).unwrap();
960        // just to make sure `a` is not optimized out by the compiler
961        assert_eq!((a - &a).is_zero().unwrap_u8(), 1);
962    }
963
964    #[cfg(feature = "getrandom")]
965    #[test]
966    fn try_generate_from_rng() {
967        let a = Scalar::try_generate_from_rng(&mut SysRng).unwrap();
968        // just to make sure `a` is not optimized out by the compiler
969        assert_eq!((a - a).is_zero().unwrap_u8(), 1);
970    }
971
972    #[test]
973    fn from_bytes_reduced() {
974        let m = Scalar::modulus_as_biguint();
975
976        fn reduce<T: Reduce<FieldBytes>>(arr: &[u8]) -> T {
977            T::reduce(&Array::try_from(arr).unwrap())
978        }
979
980        // Regular reduction
981
982        let s = reduce::<Scalar>(&[0xffu8; 32]).to_biguint().unwrap();
983        assert!(s < m);
984
985        let s = reduce::<Scalar>(&[0u8; 32]).to_biguint().unwrap();
986        assert!(s.is_zero());
987
988        let s = reduce::<Scalar>(&ORDER.to_be_byte_array())
989            .to_biguint()
990            .unwrap();
991        assert!(s.is_zero());
992
993        // Reduction to a non-zero scalar
994
995        let s = reduce::<NonZeroScalar>(&[0xffu8; 32]).to_biguint().unwrap();
996        assert!(s < m);
997
998        let s = reduce::<NonZeroScalar>(&[0u8; 32]).to_biguint().unwrap();
999        assert!(s < m);
1000        assert!(!s.is_zero());
1001
1002        let s = reduce::<NonZeroScalar>(&ORDER.to_be_byte_array())
1003            .to_biguint()
1004            .unwrap();
1005        assert!(s < m);
1006        assert!(!s.is_zero());
1007
1008        let s = reduce::<NonZeroScalar>(&(ORDER.wrapping_sub(&U256::ONE)).to_be_byte_array())
1009            .to_biguint()
1010            .unwrap();
1011        assert!(s < m);
1012        assert!(!s.is_zero());
1013    }
1014
1015    #[test]
1016    fn from_wide_bytes_reduced() {
1017        let m = Scalar::modulus_as_biguint();
1018
1019        fn reduce<T: Reduce<WideBytes>>(slice: &[u8]) -> T {
1020            let mut bytes = WideBytes::default();
1021            bytes[(64 - slice.len())..].copy_from_slice(slice);
1022            T::reduce(&bytes)
1023        }
1024
1025        // Regular reduction
1026
1027        let s = reduce::<Scalar>(&[0xffu8; 64]).to_biguint().unwrap();
1028        assert!(s < m);
1029
1030        let s = reduce::<Scalar>(&[0u8; 64]).to_biguint().unwrap();
1031        assert!(s.is_zero());
1032
1033        let s = reduce::<Scalar>(&ORDER.to_be_byte_array())
1034            .to_biguint()
1035            .unwrap();
1036        assert!(s.is_zero());
1037
1038        // Reduction to a non-zero scalar
1039
1040        let s = reduce::<NonZeroScalar>(&[0xffu8; 64]).to_biguint().unwrap();
1041        assert!(s < m);
1042
1043        let s = reduce::<NonZeroScalar>(&[0u8; 64]).to_biguint().unwrap();
1044        assert!(s < m);
1045        assert!(!s.is_zero());
1046
1047        let s = reduce::<NonZeroScalar>(&ORDER.to_be_byte_array())
1048            .to_biguint()
1049            .unwrap();
1050        assert!(s < m);
1051        assert!(!s.is_zero());
1052
1053        let s = reduce::<NonZeroScalar>(&(ORDER.wrapping_sub(&U256::ONE)).to_be_byte_array())
1054            .to_biguint()
1055            .unwrap();
1056        assert!(s < m);
1057        assert!(!s.is_zero());
1058    }
1059
1060    prop_compose! {
1061        fn scalar()(bytes in any::<[u8; 32]>()) -> Scalar {
1062            <Scalar as Reduce<FieldBytes>>::reduce(&bytes.into())
1063        }
1064    }
1065
1066    proptest! {
1067        #[test]
1068        fn fuzzy_roundtrip_to_bytes(a in scalar()) {
1069            let a_back = Scalar::from_repr(a.to_bytes()).unwrap();
1070            assert_eq!(a, a_back);
1071        }
1072
1073        #[test]
1074        fn fuzzy_roundtrip_to_bytes_unchecked(a in scalar()) {
1075            let bytes = a.to_bytes();
1076            let a_back = Scalar::from_bytes_unchecked(bytes.as_ref());
1077            assert_eq!(a, a_back);
1078        }
1079
1080        #[test]
1081        fn fuzzy_add(a in scalar(), b in scalar()) {
1082            let a_bi = a.to_biguint().unwrap();
1083            let b_bi = b.to_biguint().unwrap();
1084
1085            let res_bi = (&a_bi + &b_bi) % &Scalar::modulus_as_biguint();
1086            let res_ref = Scalar::from(&res_bi);
1087            let res_test = a.add(&b);
1088
1089            assert_eq!(res_ref, res_test);
1090        }
1091
1092        #[test]
1093        fn fuzzy_sub(a in scalar(), b in scalar()) {
1094            let a_bi = a.to_biguint().unwrap();
1095            let b_bi = b.to_biguint().unwrap();
1096
1097            let m = Scalar::modulus_as_biguint();
1098            let res_bi = (&m + &a_bi - &b_bi) % &m;
1099            let res_ref = Scalar::from(&res_bi);
1100            let res_test = a.sub(&b);
1101
1102            assert_eq!(res_ref, res_test);
1103        }
1104
1105        #[test]
1106        fn fuzzy_neg(a in scalar()) {
1107            let a_bi = a.to_biguint().unwrap();
1108
1109            let m = Scalar::modulus_as_biguint();
1110            let res_bi = (&m - &a_bi) % &m;
1111            let res_ref = Scalar::from(&res_bi);
1112            let res_test = -a;
1113
1114            assert_eq!(res_ref, res_test);
1115        }
1116
1117        #[test]
1118        fn fuzzy_mul(a in scalar(), b in scalar()) {
1119            let a_bi = a.to_biguint().unwrap();
1120            let b_bi = b.to_biguint().unwrap();
1121
1122            let res_bi = (&a_bi * &b_bi) % &Scalar::modulus_as_biguint();
1123            let res_ref = Scalar::from(&res_bi);
1124            let res_test = a.mul(&b);
1125
1126            assert_eq!(res_ref, res_test);
1127        }
1128
1129        #[test]
1130        fn fuzzy_rshift(a in scalar(), b in 0usize..512) {
1131            let a_bi = a.to_biguint().unwrap();
1132
1133            let res_bi = &a_bi >> b;
1134            let res_ref = Scalar::from(&res_bi);
1135            let res_test = a >> b;
1136
1137            assert_eq!(res_ref, res_test);
1138        }
1139
1140        #[test]
1141        fn fuzzy_invert(
1142            a in scalar()
1143        ) {
1144            let a = if bool::from(a.is_zero()) { Scalar::ONE } else { a };
1145            let a_bi = a.to_biguint().unwrap();
1146            let inv = a.invert().unwrap();
1147            let inv_bi = inv.to_biguint().unwrap();
1148            let m = Scalar::modulus_as_biguint();
1149            assert_eq!((&inv_bi * &a_bi) % &m, 1.to_biguint().unwrap());
1150        }
1151
1152        #[test]
1153        fn fuzzy_invert_vartime(w in scalar()) {
1154            let inv: Option<Scalar> = w.invert().into();
1155            let inv_vartime: Option<Scalar> = w.invert_vartime().into();
1156            assert_eq!(inv, inv_vartime);
1157        }
1158
1159        #[test]
1160        fn fuzzy_from_wide_bytes_reduced(bytes_hi in any::<[u8; 32]>(), bytes_lo in any::<[u8; 32]>()) {
1161            let m = Scalar::modulus_as_biguint();
1162            let mut bytes = [0u8; 64];
1163            bytes[0..32].clone_from_slice(&bytes_hi);
1164            bytes[32..64].clone_from_slice(&bytes_lo);
1165            let s = <Scalar as Reduce<U512>>::reduce(&U512::from_be_slice(&bytes));
1166            let s_bu = s.to_biguint().unwrap();
1167            assert!(s_bu < m);
1168        }
1169    }
1170}
k256/arithmetic/scalar.rs

k256/arithmetic/
scalar.rs
