Coverage Report

Created: 2025-12-31 06:17

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/rust/registry/src/index.crates.io-1949cf8c6b5b557f/p256-0.13.2/src/arithmetic/scalar.rs
Line
Count
Source
1
//! Scalar field arithmetic modulo n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
2
3
#[cfg_attr(target_pointer_width = "32", path = "scalar/scalar32.rs")]
4
#[cfg_attr(target_pointer_width = "64", path = "scalar/scalar64.rs")]
5
mod scalar_impl;
6
7
use self::scalar_impl::barrett_reduce;
8
use crate::{FieldBytes, NistP256, SecretKey, ORDER_HEX};
9
use core::{
10
    fmt::{self, Debug},
11
    iter::{Product, Sum},
12
    ops::{Add, AddAssign, Mul, MulAssign, Neg, Shr, ShrAssign, Sub, SubAssign},
13
};
14
use elliptic_curve::{
15
    bigint::{prelude::*, Limb, U256},
16
    group::ff::{self, Field, PrimeField},
17
    ops::{Invert, Reduce, ReduceNonZero},
18
    rand_core::RngCore,
19
    scalar::{FromUintUnchecked, IsHigh},
20
    subtle::{
21
        Choice, ConditionallySelectable, ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess,
22
        CtOption,
23
    },
24
    zeroize::DefaultIsZeroes,
25
    Curve, ScalarPrimitive,
26
};
27
28
#[cfg(feature = "bits")]
29
use {crate::ScalarBits, elliptic_curve::group::ff::PrimeFieldBits};
30
31
#[cfg(feature = "serde")]
32
use serdect::serde::{de, ser, Deserialize, Serialize};
33
34
/// Constant representing the modulus
35
/// n = FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551
36
pub(crate) const MODULUS: U256 = NistP256::ORDER;
37
38
/// `MODULUS / 2`
39
const FRAC_MODULUS_2: Scalar = Scalar(MODULUS.shr_vartime(1));
40
41
/// MU = floor(2^512 / n)
42
///    = 115792089264276142090721624801893421302707618245269942344307673200490803338238
43
///    = 0x100000000fffffffffffffffeffffffff43190552df1a6c21012ffd85eedf9bfe
44
pub const MU: [u64; 5] = [
45
    0x012f_fd85_eedf_9bfe,
46
    0x4319_0552_df1a_6c21,
47
    0xffff_fffe_ffff_ffff,
48
    0x0000_0000_ffff_ffff,
49
    0x0000_0000_0000_0001,
50
];
51
52
/// Scalars are elements in the finite field modulo n.
53
///
54
/// # Trait impls
55
///
56
/// Much of the important functionality of scalars is provided by traits from
57
/// the [`ff`](https://docs.rs/ff/) crate, which is re-exported as
58
/// `p256::elliptic_curve::ff`:
59
///
60
/// - [`Field`](https://docs.rs/ff/latest/ff/trait.Field.html) -
61
///   represents elements of finite fields and provides:
62
///   - [`Field::random`](https://docs.rs/ff/latest/ff/trait.Field.html#tymethod.random) -
63
///     generate a random scalar
64
///   - `double`, `square`, and `invert` operations
65
///   - Bounds for [`Add`], [`Sub`], [`Mul`], and [`Neg`] (as well as `*Assign` equivalents)
66
///   - Bounds for [`ConditionallySelectable`] from the `subtle` crate
67
/// - [`PrimeField`](https://docs.rs/ff/latest/ff/trait.PrimeField.html) -
68
///   represents elements of prime fields and provides:
69
///   - `from_repr`/`to_repr` for converting field elements from/to big integers.
70
///   - `multiplicative_generator` and `root_of_unity` constants.
71
/// - [`PrimeFieldBits`](https://docs.rs/ff/latest/ff/trait.PrimeFieldBits.html) -
72
///   operations over field elements represented as bits (requires `bits` feature)
73
///
74
/// Please see the documentation for the relevant traits for more information.
75
///
76
/// # `serde` support
77
///
78
/// When the `serde` feature of this crate is enabled, the `Serialize` and
79
/// `Deserialize` traits are impl'd for this type.
80
///
81
/// The serialization is a fixed-width big endian encoding. When used with
82
/// textual formats, the binary data is encoded as hexadecimal.
83
#[derive(Clone, Copy, Default)]
84
pub struct Scalar(pub(crate) U256);
85
86
impl Scalar {
87
    /// Zero scalar.
88
    pub const ZERO: Self = Self(U256::ZERO);
89
90
    /// Multiplicative identity.
91
    pub const ONE: Self = Self(U256::ONE);
92
93
    /// Returns the SEC1 encoding of this scalar.
94
15.5k
    pub fn to_bytes(&self) -> FieldBytes {
95
15.5k
        self.0.to_be_byte_array()
96
15.5k
    }
97
98
    /// Returns self + rhs mod n
99
3.05k
    pub const fn add(&self, rhs: &Self) -> Self {
100
3.05k
        Self(self.0.add_mod(&rhs.0, &NistP256::ORDER))
101
3.05k
    }
102
103
    /// Returns 2*self.
104
0
    pub const fn double(&self) -> Self {
105
0
        self.add(self)
106
0
    }
107
108
    /// Returns self - rhs mod n.
109
0
    pub const fn sub(&self, rhs: &Self) -> Self {
110
0
        Self(self.0.sub_mod(&rhs.0, &NistP256::ORDER))
111
0
    }
112
113
    /// Returns self * rhs mod n
114
1.30M
    pub const fn multiply(&self, rhs: &Self) -> Self {
115
1.30M
        let (lo, hi) = self.0.mul_wide(&rhs.0);
116
1.30M
        Self(barrett_reduce(lo, hi))
117
1.30M
    }
118
119
    /// Returns self * self mod p
120
781k
    pub const fn square(&self) -> Self {
121
        // Schoolbook multiplication.
122
781k
        self.multiply(self)
123
781k
    }
124
125
    /// Right shifts the scalar.
126
    ///
127
    /// Note: not constant-time with respect to the `shift` parameter.
128
0
    pub const fn shr_vartime(&self, shift: usize) -> Scalar {
129
0
        Self(self.0.shr_vartime(shift))
130
0
    }
131
132
    /// Returns the multiplicative inverse of self, if self is non-zero
133
3.05k
    pub fn invert(&self) -> CtOption<Self> {
134
3.05k
        CtOption::new(self.invert_unchecked(), !self.is_zero())
135
3.05k
    }
136
137
    /// Returns the multiplicative inverse of self.
138
    ///
139
    /// Does not check that self is non-zero.
140
3.05k
    const fn invert_unchecked(&self) -> Self {
141
        // We need to find b such that b * a ≡ 1 mod p. As we are in a prime
142
        // field, we can apply Fermat's Little Theorem:
143
        //
144
        //    a^p         ≡ a mod p
145
        //    a^(p-1)     ≡ 1 mod p
146
        //    a^(p-2) * a ≡ 1 mod p
147
        //
148
        // Thus inversion can be implemented with a single exponentiation.
149
        //
150
        // This is `n - 2`, so the top right two digits are `4f` instead of `51`.
151
3.05k
        self.pow_vartime(&[
152
3.05k
            0xf3b9_cac2_fc63_254f,
153
3.05k
            0xbce6_faad_a717_9e84,
154
3.05k
            0xffff_ffff_ffff_ffff,
155
3.05k
            0xffff_ffff_0000_0000,
156
3.05k
        ])
157
3.05k
    }
158
159
    /// Exponentiates `self` by `exp`, where `exp` is a little-endian order integer
160
    /// exponent.
161
3.05k
    pub const fn pow_vartime(&self, exp: &[u64]) -> Self {
162
3.05k
        let mut res = Self::ONE;
163
164
3.05k
        let mut i = exp.len();
165
15.2k
        while i > 0 {
166
12.2k
            i -= 1;
167
168
12.2k
            let mut j = 64;
169
793k
            while j > 0 {
170
781k
                j -= 1;
171
781k
                res = res.square();
172
173
781k
                if ((exp[i] >> j) & 1) == 1 {
174
515k
                    res = res.multiply(self);
175
515k
                }
176
            }
177
        }
178
179
3.05k
        res
180
3.05k
    }
181
182
    /// Is integer representing equivalence class odd?
183
0
    pub fn is_odd(&self) -> Choice {
184
0
        self.0.is_odd()
185
0
    }
186
187
    /// Is integer representing equivalence class even?
188
0
    pub fn is_even(&self) -> Choice {
189
0
        !self.is_odd()
190
0
    }
191
}
192
193
impl AsRef<Scalar> for Scalar {
194
6.10k
    fn as_ref(&self) -> &Scalar {
195
6.10k
        self
196
6.10k
    }
197
}
198
199
impl Field for Scalar {
200
    const ZERO: Self = Self::ZERO;
201
    const ONE: Self = Self::ONE;
202
203
38.8k
    fn random(mut rng: impl RngCore) -> Self {
204
38.8k
        let mut bytes = FieldBytes::default();
205
206
        // Generate a uniformly random scalar using rejection sampling,
207
        // which produces a uniformly random distribution of scalars.
208
        //
209
        // This method is not constant time, but should be secure so long as
210
        // rejected RNG outputs are unrelated to future ones (which is a
211
        // necessary property of a `CryptoRng`).
212
        //
213
        // With an unbiased RNG, the probability of failing to complete after 4
214
        // iterations is vanishingly small.
215
        loop {
216
38.8k
            rng.fill_bytes(&mut bytes);
217
38.8k
            if let Some(scalar) = Scalar::from_repr(bytes).into() {
218
38.8k
                return scalar;
219
22
            }
220
        }
221
38.8k
    }
<p256::arithmetic::scalar::Scalar as ff::Field>::random::<&mut &mut rand::rngs::std::StdRng>
Line
Count
Source
203
38.8k
    fn random(mut rng: impl RngCore) -> Self {
204
38.8k
        let mut bytes = FieldBytes::default();
205
206
        // Generate a uniformly random scalar using rejection sampling,
207
        // which produces a uniformly random distribution of scalars.
208
        //
209
        // This method is not constant time, but should be secure so long as
210
        // rejected RNG outputs are unrelated to future ones (which is a
211
        // necessary property of a `CryptoRng`).
212
        //
213
        // With an unbiased RNG, the probability of failing to complete after 4
214
        // iterations is vanishingly small.
215
        loop {
216
38.8k
            rng.fill_bytes(&mut bytes);
217
38.8k
            if let Some(scalar) = Scalar::from_repr(bytes).into() {
218
38.8k
                return scalar;
219
22
            }
220
        }
221
38.8k
    }
Unexecuted instantiation: <p256::arithmetic::scalar::Scalar as ff::Field>::random::<_>
222
223
    #[must_use]
224
0
    fn square(&self) -> Self {
225
0
        Scalar::square(self)
226
0
    }
227
228
    #[must_use]
229
0
    fn double(&self) -> Self {
230
0
        self.add(self)
231
0
    }
232
233
0
    fn invert(&self) -> CtOption<Self> {
234
0
        Scalar::invert(self)
235
0
    }
236
237
    /// Tonelli-Shank's algorithm for q mod 16 = 1
238
    /// <https://eprint.iacr.org/2012/685.pdf> (page 12, algorithm 5)
239
    #[allow(clippy::many_single_char_names)]
240
0
    fn sqrt(&self) -> CtOption<Self> {
241
        // Note: `pow_vartime` is constant-time with respect to `self`
242
0
        let w = self.pow_vartime(&[
243
0
            0x279dce5617e3192a,
244
0
            0xfde737d56d38bcf4,
245
0
            0x07ffffffffffffff,
246
0
            0x07fffffff8000000,
247
0
        ]);
248
249
0
        let mut v = Self::S;
250
0
        let mut x = *self * w;
251
0
        let mut b = x * w;
252
0
        let mut z = Self::ROOT_OF_UNITY;
253
254
0
        for max_v in (1..=Self::S).rev() {
255
0
            let mut k = 1;
256
0
            let mut tmp = b.square();
257
0
            let mut j_less_than_v = Choice::from(1);
258
259
0
            for j in 2..max_v {
260
0
                let tmp_is_one = tmp.ct_eq(&Self::ONE);
261
0
                let squared = Self::conditional_select(&tmp, &z, tmp_is_one).square();
262
0
                tmp = Self::conditional_select(&squared, &tmp, tmp_is_one);
263
0
                let new_z = Self::conditional_select(&z, &squared, tmp_is_one);
264
0
                j_less_than_v &= !j.ct_eq(&v);
265
0
                k = u32::conditional_select(&j, &k, tmp_is_one);
266
0
                z = Self::conditional_select(&z, &new_z, j_less_than_v);
267
0
            }
268
269
0
            let result = x * z;
270
0
            x = Self::conditional_select(&result, &x, b.ct_eq(&Self::ONE));
271
0
            z = z.square();
272
0
            b *= z;
273
0
            v = k;
274
        }
275
276
0
        CtOption::new(x, x.square().ct_eq(self))
277
0
    }
278
279
0
    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
280
0
        ff::helpers::sqrt_ratio_generic(num, div)
281
0
    }
282
}
283
284
impl PrimeField for Scalar {
285
    type Repr = FieldBytes;
286
287
    const MODULUS: &'static str = ORDER_HEX;
288
    const NUM_BITS: u32 = 256;
289
    const CAPACITY: u32 = 255;
290
    const TWO_INV: Self = Self(U256::from_u8(2)).invert_unchecked();
291
    const MULTIPLICATIVE_GENERATOR: Self = Self(U256::from_u8(7));
292
    const S: u32 = 4;
293
    const ROOT_OF_UNITY: Self = Self(U256::from_be_hex(
294
        "ffc97f062a770992ba807ace842a3dfc1546cad004378daf0592d7fbb41e6602",
295
    ));
296
    const ROOT_OF_UNITY_INV: Self = Self::ROOT_OF_UNITY.invert_unchecked();
297
    const DELTA: Self = Self(U256::from_u64(33232930569601));
298
299
    /// Attempts to parse the given byte array as an SEC1-encoded scalar.
300
    ///
301
    /// Returns None if the byte array does not contain a big-endian integer in the range
302
    /// [0, p).
303
41.9k
    fn from_repr(bytes: FieldBytes) -> CtOption<Self> {
304
41.9k
        let inner = U256::from_be_byte_array(bytes);
305
41.9k
        CtOption::new(Self(inner), inner.ct_lt(&NistP256::ORDER))
306
41.9k
    }
307
308
9.41k
    fn to_repr(&self) -> FieldBytes {
309
9.41k
        self.to_bytes()
310
9.41k
    }
311
312
0
    fn is_odd(&self) -> Choice {
313
0
        self.0.is_odd()
314
0
    }
315
}
316
317
#[cfg(feature = "bits")]
318
impl PrimeFieldBits for Scalar {
319
    #[cfg(target_pointer_width = "32")]
320
    type ReprBits = [u32; 8];
321
322
    #[cfg(target_pointer_width = "64")]
323
    type ReprBits = [u64; 4];
324
325
    fn to_le_bits(&self) -> ScalarBits {
326
        self.into()
327
    }
328
329
    fn char_le_bits() -> ScalarBits {
330
        NistP256::ORDER.to_words().into()
331
    }
332
}
333
334
impl DefaultIsZeroes for Scalar {}
335
336
impl Eq for Scalar {}
337
338
impl FromUintUnchecked for Scalar {
339
    type Uint = U256;
340
341
79
    fn from_uint_unchecked(uint: Self::Uint) -> Self {
342
79
        Self(uint)
343
79
    }
344
}
345
346
impl Invert for Scalar {
347
    type Output = CtOption<Self>;
348
349
3.05k
    fn invert(&self) -> CtOption<Self> {
350
3.05k
        self.invert()
351
3.05k
    }
352
353
    /// Fast variable-time inversion using Stein's algorithm.
354
    ///
355
    /// Returns none if the scalar is zero.
356
    ///
357
    /// <https://link.springer.com/article/10.1007/s13389-016-0135-4>
358
    ///
359
    /// ⚠️ WARNING!
360
    ///
361
    /// This method should not be used with (unblinded) secret scalars, as its
362
    /// variable-time operation can potentially leak secrets through
363
    /// sidechannels.
364
    #[allow(non_snake_case)]
365
0
    fn invert_vartime(&self) -> CtOption<Self> {
366
0
        let mut u = *self;
367
0
        let mut v = Self(MODULUS);
368
0
        let mut A = Self::ONE;
369
0
        let mut C = Self::ZERO;
370
371
0
        while !bool::from(u.is_zero()) {
372
            // u-loop
373
0
            while bool::from(u.is_even()) {
374
0
                u >>= 1;
375
376
0
                let was_odd: bool = A.is_odd().into();
377
0
                A >>= 1;
378
379
0
                if was_odd {
380
0
                    A += FRAC_MODULUS_2;
381
0
                    A += Self::ONE;
382
0
                }
383
            }
384
385
            // v-loop
386
0
            while bool::from(v.is_even()) {
387
0
                v >>= 1;
388
389
0
                let was_odd: bool = C.is_odd().into();
390
0
                C >>= 1;
391
392
0
                if was_odd {
393
0
                    C += FRAC_MODULUS_2;
394
0
                    C += Self::ONE;
395
0
                }
396
            }
397
398
            // sub-step
399
0
            if u >= v {
400
0
                u -= &v;
401
0
                A -= &C;
402
0
            } else {
403
0
                v -= &u;
404
0
                C -= &A;
405
0
            }
406
        }
407
408
0
        CtOption::new(C, !self.is_zero())
409
0
    }
410
}
411
412
impl IsHigh for Scalar {
413
0
    fn is_high(&self) -> Choice {
414
0
        self.0.ct_gt(&FRAC_MODULUS_2.0)
415
0
    }
416
}
417
418
impl Shr<usize> for Scalar {
419
    type Output = Self;
420
421
0
    fn shr(self, rhs: usize) -> Self::Output {
422
0
        self.shr_vartime(rhs)
423
0
    }
424
}
425
426
impl Shr<usize> for &Scalar {
427
    type Output = Scalar;
428
429
0
    fn shr(self, rhs: usize) -> Self::Output {
430
0
        self.shr_vartime(rhs)
431
0
    }
432
}
433
434
impl ShrAssign<usize> for Scalar {
435
0
    fn shr_assign(&mut self, rhs: usize) {
436
0
        *self = *self >> rhs;
437
0
    }
438
}
439
440
impl PartialEq for Scalar {
441
0
    fn eq(&self, other: &Self) -> bool {
442
0
        self.ct_eq(other).into()
443
0
    }
444
}
445
446
impl PartialOrd for Scalar {
447
0
    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
448
0
        Some(self.cmp(other))
449
0
    }
450
}
451
452
impl Ord for Scalar {
453
0
    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
454
0
        self.0.cmp(&other.0)
455
0
    }
456
}
457
458
impl From<u32> for Scalar {
459
0
    fn from(k: u32) -> Self {
460
0
        Scalar(k.into())
461
0
    }
462
}
463
464
impl From<u64> for Scalar {
465
0
    fn from(k: u64) -> Self {
466
0
        Scalar(k.into())
467
0
    }
468
}
469
470
impl From<u128> for Scalar {
471
0
    fn from(k: u128) -> Self {
472
0
        Scalar(k.into())
473
0
    }
474
}
475
476
impl From<Scalar> for FieldBytes {
477
6.10k
    fn from(scalar: Scalar) -> Self {
478
6.10k
        scalar.to_bytes()
479
6.10k
    }
480
}
481
482
impl From<&Scalar> for FieldBytes {
483
0
    fn from(scalar: &Scalar) -> Self {
484
0
        scalar.to_bytes()
485
0
    }
486
}
487
488
impl From<ScalarPrimitive<NistP256>> for Scalar {
489
0
    fn from(scalar: ScalarPrimitive<NistP256>) -> Scalar {
490
0
        Scalar(*scalar.as_uint())
491
0
    }
492
}
493
494
impl From<&ScalarPrimitive<NistP256>> for Scalar {
495
0
    fn from(scalar: &ScalarPrimitive<NistP256>) -> Scalar {
496
0
        Scalar(*scalar.as_uint())
497
0
    }
498
}
499
500
impl From<Scalar> for ScalarPrimitive<NistP256> {
501
0
    fn from(scalar: Scalar) -> ScalarPrimitive<NistP256> {
502
0
        ScalarPrimitive::from(&scalar)
503
0
    }
504
}
505
506
impl From<&Scalar> for ScalarPrimitive<NistP256> {
507
0
    fn from(scalar: &Scalar) -> ScalarPrimitive<NistP256> {
508
0
        ScalarPrimitive::new(scalar.0).unwrap()
509
0
    }
510
}
511
512
impl From<&SecretKey> for Scalar {
513
0
    fn from(secret_key: &SecretKey) -> Scalar {
514
0
        *secret_key.to_nonzero_scalar()
515
0
    }
516
}
517
518
impl From<Scalar> for U256 {
519
8.09k
    fn from(scalar: Scalar) -> U256 {
520
8.09k
        scalar.0
521
8.09k
    }
522
}
523
524
impl From<&Scalar> for U256 {
525
0
    fn from(scalar: &Scalar) -> U256 {
526
0
        scalar.0
527
0
    }
528
}
529
530
#[cfg(feature = "bits")]
531
impl From<&Scalar> for ScalarBits {
532
    fn from(scalar: &Scalar) -> ScalarBits {
533
        scalar.0.to_words().into()
534
    }
535
}
536
537
impl Add<Scalar> for Scalar {
538
    type Output = Scalar;
539
540
3.05k
    fn add(self, other: Scalar) -> Scalar {
541
3.05k
        Scalar::add(&self, &other)
542
3.05k
    }
543
}
544
545
impl Add<&Scalar> for &Scalar {
546
    type Output = Scalar;
547
548
0
    fn add(self, other: &Scalar) -> Scalar {
549
0
        Scalar::add(self, other)
550
0
    }
551
}
552
553
impl Add<&Scalar> for Scalar {
554
    type Output = Scalar;
555
556
0
    fn add(self, other: &Scalar) -> Scalar {
557
0
        Scalar::add(&self, other)
558
0
    }
559
}
560
561
impl AddAssign<Scalar> for Scalar {
562
0
    fn add_assign(&mut self, rhs: Scalar) {
563
0
        *self = Scalar::add(self, &rhs);
564
0
    }
565
}
566
567
impl AddAssign<&Scalar> for Scalar {
568
0
    fn add_assign(&mut self, rhs: &Scalar) {
569
0
        *self = Scalar::add(self, rhs);
570
0
    }
571
}
572
573
impl Sub<Scalar> for Scalar {
574
    type Output = Scalar;
575
576
0
    fn sub(self, other: Scalar) -> Scalar {
577
0
        Scalar::sub(&self, &other)
578
0
    }
579
}
580
581
impl Sub<&Scalar> for &Scalar {
582
    type Output = Scalar;
583
584
0
    fn sub(self, other: &Scalar) -> Scalar {
585
0
        Scalar::sub(self, other)
586
0
    }
587
}
588
589
impl Sub<&Scalar> for Scalar {
590
    type Output = Scalar;
591
592
0
    fn sub(self, other: &Scalar) -> Scalar {
593
0
        Scalar::sub(&self, other)
594
0
    }
595
}
596
597
impl SubAssign<Scalar> for Scalar {
598
0
    fn sub_assign(&mut self, rhs: Scalar) {
599
0
        *self = Scalar::sub(self, &rhs);
600
0
    }
601
}
602
603
impl SubAssign<&Scalar> for Scalar {
604
0
    fn sub_assign(&mut self, rhs: &Scalar) {
605
0
        *self = Scalar::sub(self, rhs);
606
0
    }
607
}
608
609
impl Mul<Scalar> for Scalar {
610
    type Output = Scalar;
611
612
3.05k
    fn mul(self, other: Scalar) -> Scalar {
613
3.05k
        Scalar::multiply(&self, &other)
614
3.05k
    }
615
}
616
617
impl Mul<&Scalar> for &Scalar {
618
    type Output = Scalar;
619
620
0
    fn mul(self, other: &Scalar) -> Scalar {
621
0
        Scalar::multiply(self, other)
622
0
    }
623
}
624
625
impl Mul<&Scalar> for Scalar {
626
    type Output = Scalar;
627
628
3.05k
    fn mul(self, other: &Scalar) -> Scalar {
629
3.05k
        Scalar::multiply(&self, other)
630
3.05k
    }
631
}
632
633
impl MulAssign<Scalar> for Scalar {
634
0
    fn mul_assign(&mut self, rhs: Scalar) {
635
0
        *self = Scalar::multiply(self, &rhs);
636
0
    }
637
}
638
639
impl MulAssign<&Scalar> for Scalar {
640
0
    fn mul_assign(&mut self, rhs: &Scalar) {
641
0
        *self = Scalar::multiply(self, rhs);
642
0
    }
643
}
644
645
impl Neg for Scalar {
646
    type Output = Scalar;
647
648
0
    fn neg(self) -> Scalar {
649
0
        Scalar::ZERO - self
650
0
    }
651
}
652
653
impl<'a> Neg for &'a Scalar {
654
    type Output = Scalar;
655
656
0
    fn neg(self) -> Scalar {
657
0
        Scalar::ZERO - self
658
0
    }
659
}
660
661
impl Reduce<U256> for Scalar {
662
    type Bytes = FieldBytes;
663
664
6.10k
    fn reduce(w: U256) -> Self {
665
6.10k
        let (r, underflow) = w.sbb(&NistP256::ORDER, Limb::ZERO);
666
6.10k
        let underflow = Choice::from((underflow.0 >> (Limb::BITS - 1)) as u8);
667
6.10k
        Self(U256::conditional_select(&w, &r, !underflow))
668
6.10k
    }
669
670
6.10k
    fn reduce_bytes(bytes: &FieldBytes) -> Self {
671
6.10k
        Self::reduce(U256::from_be_byte_array(*bytes))
672
6.10k
    }
673
}
674
675
impl ReduceNonZero<U256> for Scalar {
676
0
    fn reduce_nonzero(w: U256) -> Self {
677
        const ORDER_MINUS_ONE: U256 = NistP256::ORDER.wrapping_sub(&U256::ONE);
678
0
        let (r, underflow) = w.sbb(&ORDER_MINUS_ONE, Limb::ZERO);
679
0
        let underflow = Choice::from((underflow.0 >> (Limb::BITS - 1)) as u8);
680
0
        Self(U256::conditional_select(&w, &r, !underflow).wrapping_add(&U256::ONE))
681
0
    }
682
683
0
    fn reduce_nonzero_bytes(bytes: &FieldBytes) -> Self {
684
0
        Self::reduce_nonzero(U256::from_be_byte_array(*bytes))
685
0
    }
686
}
687
688
impl Sum for Scalar {
689
0
    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
690
0
        iter.reduce(core::ops::Add::add).unwrap_or(Self::ZERO)
691
0
    }
692
}
693
694
impl<'a> Sum<&'a Scalar> for Scalar {
695
0
    fn sum<I: Iterator<Item = &'a Scalar>>(iter: I) -> Self {
696
0
        iter.copied().sum()
697
0
    }
698
}
699
700
impl Product for Scalar {
701
0
    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
702
0
        iter.reduce(core::ops::Mul::mul).unwrap_or(Self::ONE)
703
0
    }
704
}
705
706
impl<'a> Product<&'a Scalar> for Scalar {
707
0
    fn product<I: Iterator<Item = &'a Scalar>>(iter: I) -> Self {
708
0
        iter.copied().product()
709
0
    }
710
}
711
712
impl ConditionallySelectable for Scalar {
713
0
    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
714
0
        Self(U256::conditional_select(&a.0, &b.0, choice))
715
0
    }
716
}
717
718
impl ConstantTimeEq for Scalar {
719
44.9k
    fn ct_eq(&self, other: &Self) -> Choice {
720
44.9k
        self.0.ct_eq(&other.0)
721
44.9k
    }
722
}
723
724
impl Debug for Scalar {
725
0
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
726
0
        write!(f, "Scalar(0x{:X})", &self.0)
727
0
    }
728
}
729
730
#[cfg(feature = "serde")]
731
impl Serialize for Scalar {
732
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
733
    where
734
        S: ser::Serializer,
735
    {
736
        ScalarPrimitive::from(self).serialize(serializer)
737
    }
738
}
739
740
#[cfg(feature = "serde")]
741
impl<'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(ScalarPrimitive::deserialize(deserializer)?.into())
747
    }
748
}
749
750
#[cfg(test)]
751
mod tests {
752
    use super::Scalar;
753
    use crate::{FieldBytes, SecretKey};
754
    use elliptic_curve::group::ff::{Field, PrimeField};
755
    use primeorder::{
756
        impl_field_identity_tests, impl_field_invert_tests, impl_field_sqrt_tests,
757
        impl_primefield_tests,
758
    };
759
760
    /// t = (modulus - 1) >> S
761
    const T: [u64; 4] = [
762
        0x4f3b9cac2fc63255,
763
        0xfbce6faada7179e8,
764
        0x0fffffffffffffff,
765
        0x0ffffffff0000000,
766
    ];
767
768
    impl_field_identity_tests!(Scalar);
769
    impl_field_invert_tests!(Scalar);
770
    impl_field_sqrt_tests!(Scalar);
771
    impl_primefield_tests!(Scalar, T);
772
773
    #[test]
774
    fn from_to_bytes_roundtrip() {
775
        let k: u64 = 42;
776
        let mut bytes = FieldBytes::default();
777
        bytes[24..].copy_from_slice(k.to_be_bytes().as_ref());
778
779
        let scalar = Scalar::from_repr(bytes).unwrap();
780
        assert_eq!(bytes, scalar.to_bytes());
781
    }
782
783
    /// Basic tests that multiplication works.
784
    #[test]
785
    fn multiply() {
786
        let one = Scalar::ONE;
787
        let two = one + &one;
788
        let three = two + &one;
789
        let six = three + &three;
790
        assert_eq!(six, two * &three);
791
792
        let minus_two = -two;
793
        let minus_three = -three;
794
        assert_eq!(two, -minus_two);
795
796
        assert_eq!(minus_three * &minus_two, minus_two * &minus_three);
797
        assert_eq!(six, minus_two * &minus_three);
798
    }
799
800
    /// Tests that a Scalar can be safely converted to a SecretKey and back
801
    #[test]
802
    fn from_ec_secret() {
803
        let scalar = Scalar::ONE;
804
        let secret = SecretKey::from_bytes(&scalar.to_bytes()).unwrap();
805
        let rederived_scalar = Scalar::from(&secret);
806
        assert_eq!(scalar.0, rederived_scalar.0);
807
    }
808
809
    #[test]
810
    #[cfg(all(feature = "bits", target_pointer_width = "32"))]
811
    fn scalar_into_scalarbits() {
812
        use crate::ScalarBits;
813
814
        let minus_one = ScalarBits::from([
815
            0xfc63_2550,
816
            0xf3b9_cac2,
817
            0xa717_9e84,
818
            0xbce6_faad,
819
            0xffff_ffff,
820
            0xffff_ffff,
821
            0x0000_0000,
822
            0xffff_ffff,
823
        ]);
824
825
        let scalar_bits = ScalarBits::from(&-Scalar::from(1u32));
826
        assert_eq!(minus_one, scalar_bits);
827
    }
828
}