/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 | | } |