testudo/src/scalar/ristretto255.rs
src/scalar/ristretto255.rsRaw
1//! This module provides an implementation of the Curve25519's scalar field $\mathbb{F}_q$
2//! where `q = 2^252 + 27742317777372353535851937790883648493 = 0x1000000000000000 0000000000000000 14def9dea2f79cd6 5812631a5cf5d3ed`
3//! This module is an adaptation of code from the bls12-381 crate.
4//! We modify various constants (MODULUS, R, R2, etc.) to appropriate values for Curve25519 and update tests
5//! We borrow the `invert` method from the curve25519-dalek crate.
6//! See NOTICE.md for more details
7#![allow(clippy::all)]
8use core::borrow::Borrow;
9use core::convert::TryFrom;
10use core::fmt;
11use core::iter::{Product, Sum};
12use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
13use rand_core::{CryptoRng, RngCore};
14use serde::{Deserialize, Serialize};
15use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
16use zeroize::Zeroize;
17
18// use crate::util::{adc, mac, sbb};
19/// Compute a + b + carry, returning the result and the new carry over.
20#[inline(always)]
21pub const fn adc(a: u64, b: u64, carry: u64) -> (u64, u64) {
22 let ret = (a as u128) + (b as u128) + (carry as u128);
23 (ret as u64, (ret >> 64) as u64)
24}
25
26/// Compute a - (b + borrow), returning the result and the new borrow.
27#[inline(always)]
28pub const fn sbb(a: u64, b: u64, borrow: u64) -> (u64, u64) {
29 let ret = (a as u128).wrapping_sub((b as u128) + ((borrow >> 63) as u128));
30 (ret as u64, (ret >> 64) as u64)
31}
32
33/// Compute a + (b * c) + carry, returning the result and the new carry over.
34#[inline(always)]
35pub const fn mac(a: u64, b: u64, c: u64, carry: u64) -> (u64, u64) {
36 let ret = (a as u128) + ((b as u128) * (c as u128)) + (carry as u128);
37 (ret as u64, (ret >> 64) as u64)
38}
39
40macro_rules! impl_add_binop_specify_output {
41 ($lhs:ident, $rhs:ident, $output:ident) => {
42 impl<'b> Add<&'b $rhs> for $lhs {
43 type Output = $output;
44
45 #[inline]
46 fn add(self, rhs: &'b $rhs) -> $output {
47 &self + rhs
48 }
49 }
50
51 impl<'a> Add<$rhs> for &'a $lhs {
52 type Output = $output;
53
54 #[inline]
55 fn add(self, rhs: $rhs) -> $output {
56 self + &rhs
57 }
58 }
59
60 impl Add<$rhs> for $lhs {
61 type Output = $output;
62
63 #[inline]
64 fn add(self, rhs: $rhs) -> $output {
65 &self + &rhs
66 }
67 }
68 };
69}
70
71macro_rules! impl_sub_binop_specify_output {
72 ($lhs:ident, $rhs:ident, $output:ident) => {
73 impl<'b> Sub<&'b $rhs> for $lhs {
74 type Output = $output;
75
76 #[inline]
77 fn sub(self, rhs: &'b $rhs) -> $output {
78 &self - rhs
79 }
80 }
81
82 impl<'a> Sub<$rhs> for &'a $lhs {
83 type Output = $output;
84
85 #[inline]
86 fn sub(self, rhs: $rhs) -> $output {
87 self - &rhs
88 }
89 }
90
91 impl Sub<$rhs> for $lhs {
92 type Output = $output;
93
94 #[inline]
95 fn sub(self, rhs: $rhs) -> $output {
96 &self - &rhs
97 }
98 }
99 };
100}
101
102macro_rules! impl_binops_additive_specify_output {
103 ($lhs:ident, $rhs:ident, $output:ident) => {
104 impl_add_binop_specify_output!($lhs, $rhs, $output);
105 impl_sub_binop_specify_output!($lhs, $rhs, $output);
106 };
107}
108
109macro_rules! impl_binops_multiplicative_mixed {
110 ($lhs:ident, $rhs:ident, $output:ident) => {
111 impl<'b> Mul<&'b $rhs> for $lhs {
112 type Output = $output;
113
114 #[inline]
115 fn mul(self, rhs: &'b $rhs) -> $output {
116 &self * rhs
117 }
118 }
119
120 impl<'a> Mul<$rhs> for &'a $lhs {
121 type Output = $output;
122
123 #[inline]
124 fn mul(self, rhs: $rhs) -> $output {
125 self * &rhs
126 }
127 }
128
129 impl Mul<$rhs> for $lhs {
130 type Output = $output;
131
132 #[inline]
133 fn mul(self, rhs: $rhs) -> $output {
134 &self * &rhs
135 }
136 }
137 };
138}
139
140macro_rules! impl_binops_additive {
141 ($lhs:ident, $rhs:ident) => {
142 impl_binops_additive_specify_output!($lhs, $rhs, $lhs);
143
144 impl SubAssign<$rhs> for $lhs {
145 #[inline]
146 fn sub_assign(&mut self, rhs: $rhs) {
147 *self = &*self - &rhs;
148 }
149 }
150
151 impl AddAssign<$rhs> for $lhs {
152 #[inline]
153 fn add_assign(&mut self, rhs: $rhs) {
154 *self = &*self + &rhs;
155 }
156 }
157
158 impl<'b> SubAssign<&'b $rhs> for $lhs {
159 #[inline]
160 fn sub_assign(&mut self, rhs: &'b $rhs) {
161 *self = &*self - rhs;
162 }
163 }
164
165 impl<'b> AddAssign<&'b $rhs> for $lhs {
166 #[inline]
167 fn add_assign(&mut self, rhs: &'b $rhs) {
168 *self = &*self + rhs;
169 }
170 }
171 };
172}
173
174macro_rules! impl_binops_multiplicative {
175 ($lhs:ident, $rhs:ident) => {
176 impl_binops_multiplicative_mixed!($lhs, $rhs, $lhs);
177
178 impl MulAssign<$rhs> for $lhs {
179 #[inline]
180 fn mul_assign(&mut self, rhs: $rhs) {
181 *self = &*self * &rhs;
182 }
183 }
184
185 impl<'b> MulAssign<&'b $rhs> for $lhs {
186 #[inline]
187 fn mul_assign(&mut self, rhs: &'b $rhs) {
188 *self = &*self * rhs;
189 }
190 }
191 };
192}
193
194/// Represents an element of the scalar field $\mathbb{F}_q$ of the Curve25519 elliptic
195/// curve construction.
196// The internal representation of this type is four 64-bit unsigned
197// integers in little-endian order. `Scalar` values are always in
198// Montgomery form; i.e., Scalar(a) = aR mod q, with R = 2^256.
199#[derive(Clone, Copy, Eq, Serialize, Deserialize)]
200pub struct Scalar(pub(crate) [u64; 4]);
201
202impl fmt::Debug for Scalar {
203 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
204 let tmp = self.to_bytes();
205 write!(f, "0x")?;
206 for &b in tmp.iter().rev() {
207 write!(f, "{:02x}", b)?;
208 }
209 Ok(())
210 }
211}
212
213impl From<u64> for Scalar {
214 fn from(val: u64) -> Scalar {
215 Scalar([val, 0, 0, 0]) * R2
216 }
217}
218
219impl ConstantTimeEq for Scalar {
220 fn ct_eq(&self, other: &Self) -> Choice {
221 self.0[0].ct_eq(&other.0[0])
222 & self.0[1].ct_eq(&other.0[1])
223 & self.0[2].ct_eq(&other.0[2])
224 & self.0[3].ct_eq(&other.0[3])
225 }
226}
227
228impl PartialEq for Scalar {
229 #[inline]
230 fn eq(&self, other: &Self) -> bool {
231 self.ct_eq(other).unwrap_u8() == 1
232 }
233}
234
235impl ConditionallySelectable for Scalar {
236 fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
237 Scalar([
238 u64::conditional_select(&a.0[0], &b.0[0], choice),
239 u64::conditional_select(&a.0[1], &b.0[1], choice),
240 u64::conditional_select(&a.0[2], &b.0[2], choice),
241 u64::conditional_select(&a.0[3], &b.0[3], choice),
242 ])
243 }
244}
245
246/// Constant representing the modulus
247/// q = 2^252 + 27742317777372353535851937790883648493
248/// 0x1000000000000000 0000000000000000 14def9dea2f79cd6 5812631a5cf5d3ed
249const MODULUS: Scalar = Scalar([
250 0x5812_631a_5cf5_d3ed,
251 0x14de_f9de_a2f7_9cd6,
252 0x0000_0000_0000_0000,
253 0x1000_0000_0000_0000,
254]);
255
256impl<'a> Neg for &'a Scalar {
257 type Output = Scalar;
258
259 #[inline]
260 fn neg(self) -> Scalar {
261 self.neg()
262 }
263}
264
265impl Neg for Scalar {
266 type Output = Scalar;
267
268 #[inline]
269 fn neg(self) -> Scalar {
270 -&self
271 }
272}
273
274impl<'a, 'b> Sub<&'b Scalar> for &'a Scalar {
275 type Output = Scalar;
276
277 #[inline]
278 fn sub(self, rhs: &'b Scalar) -> Scalar {
279 self.sub(rhs)
280 }
281}
282
283impl<'a, 'b> Add<&'b Scalar> for &'a Scalar {
284 type Output = Scalar;
285
286 #[inline]
287 fn add(self, rhs: &'b Scalar) -> Scalar {
288 self.add(rhs)
289 }
290}
291
292impl<'a, 'b> Mul<&'b Scalar> for &'a Scalar {
293 type Output = Scalar;
294
295 #[inline]
296 fn mul(self, rhs: &'b Scalar) -> Scalar {
297 self.mul(rhs)
298 }
299}
300
301impl_binops_additive!(Scalar, Scalar);
302impl_binops_multiplicative!(Scalar, Scalar);
303
304/// INV = -(q^{-1} mod 2^64) mod 2^64
305const INV: u64 = 0xd2b5_1da3_1254_7e1b;
306
307/// R = 2^256 mod q
308const R: Scalar = Scalar([
309 0xd6ec_3174_8d98_951d,
310 0xc6ef_5bf4_737d_cf70,
311 0xffff_ffff_ffff_fffe,
312 0x0fff_ffff_ffff_ffff,
313]);
314
315/// R^2 = 2^512 mod q
316const R2: Scalar = Scalar([
317 0xa406_11e3_449c_0f01,
318 0xd00e_1ba7_6885_9347,
319 0xceec_73d2_17f5_be65,
320 0x0399_411b_7c30_9a3d,
321]);
322
323/// R^3 = 2^768 mod q
324const R3: Scalar = Scalar([
325 0x2a9e_4968_7b83_a2db,
326 0x2783_24e6_aef7_f3ec,
327 0x8065_dc6c_04ec_5b65,
328 0x0e53_0b77_3599_cec7,
329]);
330
331impl Default for Scalar {
332 #[inline]
333 fn default() -> Self {
334 Self::zero()
335 }
336}
337
338impl<T> Product<T> for Scalar
339where
340 T: Borrow<Scalar>,
341{
342 fn product<I>(iter: I) -> Self
343 where
344 I: Iterator<Item = T>,
345 {
346 iter.fold(Scalar::one(), |acc, item| acc * item.borrow())
347 }
348}
349
350impl<T> Sum<T> for Scalar
351where
352 T: Borrow<Scalar>,
353{
354 fn sum<I>(iter: I) -> Self
355 where
356 I: Iterator<Item = T>,
357 {
358 iter.fold(Scalar::zero(), |acc, item| acc + item.borrow())
359 }
360}
361
362impl Zeroize for Scalar {
363 fn zeroize(&mut self) {
364 self.0 = [0u64; 4];
365 }
366}
367
368impl Scalar {
369 /// Returns zero, the additive identity.
370 #[inline]
371 pub const fn zero() -> Scalar {
372 Scalar([0, 0, 0, 0])
373 }
374
375 /// Returns one, the multiplicative identity.
376 #[inline]
377 pub const fn one() -> Scalar {
378 R
379 }
380
381 pub fn random<Rng: RngCore + CryptoRng>(rng: &mut Rng) -> Self {
382 let mut limbs = [0u64; 8];
383 for i in 0..8 {
384 limbs[i] = rng.next_u64();
385 }
386 Scalar::from_u512(limbs)
387 }
388
389 /// Doubles this field element.
390 #[inline]
391 pub const fn double(&self) -> Scalar {
392 // TODO: This can be achieved more efficiently with a bitshift.
393 self.add(self)
394 }
395
396 /// Attempts to convert a little-endian byte representation of
397 /// a scalar into a `Scalar`, failing if the input is not canonical.
398 pub fn from_bytes(bytes: &[u8; 32]) -> CtOption<Scalar> {
399 let mut tmp = Scalar([0, 0, 0, 0]);
400
401 tmp.0[0] = u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[0..8]).unwrap());
402 tmp.0[1] = u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[8..16]).unwrap());
403 tmp.0[2] = u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[16..24]).unwrap());
404 tmp.0[3] = u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[24..32]).unwrap());
405
406 // Try to subtract the modulus
407 let (_, borrow) = sbb(tmp.0[0], MODULUS.0[0], 0);
408 let (_, borrow) = sbb(tmp.0[1], MODULUS.0[1], borrow);
409 let (_, borrow) = sbb(tmp.0[2], MODULUS.0[2], borrow);
410 let (_, borrow) = sbb(tmp.0[3], MODULUS.0[3], borrow);
411
412 // If the element is smaller than MODULUS then the
413 // subtraction will underflow, producing a borrow value
414 // of 0xffff...ffff. Otherwise, it'll be zero.
415 let is_some = (borrow as u8) & 1;
416
417 // Convert to Montgomery form by computing
418 // (a.R^0 * R^2) / R = a.R
419 tmp *= &R2;
420
421 CtOption::new(tmp, Choice::from(is_some))
422 }
423
424 /// Converts an element of `Scalar` into a byte representation in
425 /// little-endian byte order.
426 pub fn to_bytes(&self) -> [u8; 32] {
427 // Turn into canonical form by computing
428 // (a.R) / R = a
429 let tmp = Scalar::montgomery_reduce(self.0[0], self.0[1], self.0[2], self.0[3], 0, 0, 0, 0);
430
431 let mut res = [0; 32];
432 res[0..8].copy_from_slice(&tmp.0[0].to_le_bytes());
433 res[8..16].copy_from_slice(&tmp.0[1].to_le_bytes());
434 res[16..24].copy_from_slice(&tmp.0[2].to_le_bytes());
435 res[24..32].copy_from_slice(&tmp.0[3].to_le_bytes());
436
437 res
438 }
439
440 /// Converts a 512-bit little endian integer into
441 /// a `Scalar` by reducing by the modulus.
442 pub fn from_bytes_wide(bytes: &[u8; 64]) -> Scalar {
443 Scalar::from_u512([
444 u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[0..8]).unwrap()),
445 u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[8..16]).unwrap()),
446 u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[16..24]).unwrap()),
447 u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[24..32]).unwrap()),
448 u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[32..40]).unwrap()),
449 u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[40..48]).unwrap()),
450 u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[48..56]).unwrap()),
451 u64::from_le_bytes(<[u8; 8]>::try_from(&bytes[56..64]).unwrap()),
452 ])
453 }
454
455 fn from_u512(limbs: [u64; 8]) -> Scalar {
456 // We reduce an arbitrary 512-bit number by decomposing it into two 256-bit digits
457 // with the higher bits multiplied by 2^256. Thus, we perform two reductions
458 //
459 // 1. the lower bits are multiplied by R^2, as normal
460 // 2. the upper bits are multiplied by R^2 * 2^256 = R^3
461 //
462 // and computing their sum in the field. It remains to see that arbitrary 256-bit
463 // numbers can be placed into Montgomery form safely using the reduction. The
464 // reduction works so long as the product is less than R=2^256 multipled by
465 // the modulus. This holds because for any `c` smaller than the modulus, we have
466 // that (2^256 - 1)*c is an acceptable product for the reduction. Therefore, the
467 // reduction always works so long as `c` is in the field; in this case it is either the
468 // constant `R2` or `R3`.
469 let d0 = Scalar([limbs[0], limbs[1], limbs[2], limbs[3]]);
470 let d1 = Scalar([limbs[4], limbs[5], limbs[6], limbs[7]]);
471 // Convert to Montgomery form
472 d0 * R2 + d1 * R3
473 }
474
475 /// Converts from an integer represented in little endian
476 /// into its (congruent) `Scalar` representation.
477 pub const fn from_raw(val: [u64; 4]) -> Self {
478 (&Scalar(val)).mul(&R2)
479 }
480
481 /// Squares this element.
482 #[inline]
483 pub const fn square(&self) -> Scalar {
484 let (r1, carry) = mac(0, self.0[0], self.0[1], 0);
485 let (r2, carry) = mac(0, self.0[0], self.0[2], carry);
486 let (r3, r4) = mac(0, self.0[0], self.0[3], carry);
487
488 let (r3, carry) = mac(r3, self.0[1], self.0[2], 0);
489 let (r4, r5) = mac(r4, self.0[1], self.0[3], carry);
490
491 let (r5, r6) = mac(r5, self.0[2], self.0[3], 0);
492
493 let r7 = r6 >> 63;
494 let r6 = (r6 << 1) | (r5 >> 63);
495 let r5 = (r5 << 1) | (r4 >> 63);
496 let r4 = (r4 << 1) | (r3 >> 63);
497 let r3 = (r3 << 1) | (r2 >> 63);
498 let r2 = (r2 << 1) | (r1 >> 63);
499 let r1 = r1 << 1;
500
501 let (r0, carry) = mac(0, self.0[0], self.0[0], 0);
502 let (r1, carry) = adc(0, r1, carry);
503 let (r2, carry) = mac(r2, self.0[1], self.0[1], carry);
504 let (r3, carry) = adc(0, r3, carry);
505 let (r4, carry) = mac(r4, self.0[2], self.0[2], carry);
506 let (r5, carry) = adc(0, r5, carry);
507 let (r6, carry) = mac(r6, self.0[3], self.0[3], carry);
508 let (r7, _) = adc(0, r7, carry);
509
510 Scalar::montgomery_reduce(r0, r1, r2, r3, r4, r5, r6, r7)
511 }
512
513 /// Exponentiates `self` by `by`, where `by` is a
514 /// little-endian order integer exponent.
515 pub fn pow(&self, by: &[u64; 4]) -> Self {
516 let mut res = Self::one();
517 for e in by.iter().rev() {
518 for i in (0..64).rev() {
519 res = res.square();
520 let mut tmp = res;
521 tmp *= self;
522 res.conditional_assign(&tmp, (((*e >> i) & 0x1) as u8).into());
523 }
524 }
525 res
526 }
527
528 /// Exponentiates `self` by `by`, where `by` is a
529 /// little-endian order integer exponent.
530 ///
531 /// **This operation is variable time with respect
532 /// to the exponent.** If the exponent is fixed,
533 /// this operation is effectively constant time.
534 pub fn pow_vartime(&self, by: &[u64; 4]) -> Self {
535 let mut res = Self::one();
536 for e in by.iter().rev() {
537 for i in (0..64).rev() {
538 res = res.square();
539
540 if ((*e >> i) & 1) == 1 {
541 res.mul_assign(self);
542 }
543 }
544 }
545 res
546 }
547
548 pub fn invert(&self) -> CtOption<Self> {
549 // Uses the addition chain from
550 // https://briansmith.org/ecc-inversion-addition-chains-01#curve25519_scalar_inversion
551 // implementation adapted from curve25519-dalek
552 let _1 = self;
553 let _10 = _1.square();
554 let _100 = _10.square();
555 let _11 = &_10 * _1;
556 let _101 = &_10 * &_11;
557 let _111 = &_10 * &_101;
558 let _1001 = &_10 * &_111;
559 let _1011 = &_10 * &_1001;
560 let _1111 = &_100 * &_1011;
561
562 // _10000
563 let mut y = &_1111 * _1;
564
565 #[inline]
566 fn square_multiply(y: &mut Scalar, squarings: usize, x: &Scalar) {
567 for _ in 0..squarings {
568 *y = y.square();
569 }
570 *y = y.mul(x);
571 }
572
573 square_multiply(&mut y, 123 + 3, &_101);
574 square_multiply(&mut y, 2 + 2, &_11);
575 square_multiply(&mut y, 1 + 4, &_1111);
576 square_multiply(&mut y, 1 + 4, &_1111);
577 square_multiply(&mut y, 4, &_1001);
578 square_multiply(&mut y, 2, &_11);
579 square_multiply(&mut y, 1 + 4, &_1111);
580 square_multiply(&mut y, 1 + 3, &_101);
581 square_multiply(&mut y, 3 + 3, &_101);
582 square_multiply(&mut y, 3, &_111);
583 square_multiply(&mut y, 1 + 4, &_1111);
584 square_multiply(&mut y, 2 + 3, &_111);
585 square_multiply(&mut y, 2 + 2, &_11);
586 square_multiply(&mut y, 1 + 4, &_1011);
587 square_multiply(&mut y, 2 + 4, &_1011);
588 square_multiply(&mut y, 6 + 4, &_1001);
589 square_multiply(&mut y, 2 + 2, &_11);
590 square_multiply(&mut y, 3 + 2, &_11);
591 square_multiply(&mut y, 3 + 2, &_11);
592 square_multiply(&mut y, 1 + 4, &_1001);
593 square_multiply(&mut y, 1 + 3, &_111);
594 square_multiply(&mut y, 2 + 4, &_1111);
595 square_multiply(&mut y, 1 + 4, &_1011);
596 square_multiply(&mut y, 3, &_101);
597 square_multiply(&mut y, 2 + 4, &_1111);
598 square_multiply(&mut y, 3, &_101);
599 square_multiply(&mut y, 1 + 2, &_11);
600
601 CtOption::new(y, !self.ct_eq(&Self::zero()))
602 }
603
604 pub fn batch_invert(inputs: &mut [Scalar]) -> Scalar {
605 // This code is essentially identical to the FieldElement
606 // implementation, and is documented there. Unfortunately,
607 // it's not easy to write it generically, since here we want
608 // to use `UnpackedScalar`s internally, and `Scalar`s
609 // externally, but there's no corresponding distinction for
610 // field elements.
611
612 use zeroize::Zeroizing;
613
614 let n = inputs.len();
615 let one = Scalar::one();
616
617 // Place scratch storage in a Zeroizing wrapper to wipe it when
618 // we pass out of scope.
619 let scratch_vec = vec![one; n];
620 let mut scratch = Zeroizing::new(scratch_vec);
621
622 // Keep an accumulator of all of the previous products
623 let mut acc = Scalar::one();
624
625 // Pass through the input vector, recording the previous
626 // products in the scratch space
627 for (input, scratch) in inputs.iter().zip(scratch.iter_mut()) {
628 *scratch = acc;
629
630 acc = acc * input;
631 }
632
633 // acc is nonzero iff all inputs are nonzero
634 debug_assert!(acc != Scalar::zero());
635
636 // Compute the inverse of all products
637 acc = acc.invert().unwrap();
638
639 // We need to return the product of all inverses later
640 let ret = acc;
641
642 // Pass through the vector backwards to compute the inverses
643 // in place
644 for (input, scratch) in inputs.iter_mut().rev().zip(scratch.iter().rev()) {
645 let tmp = &acc * input.clone();
646 *input = &acc * scratch;
647 acc = tmp;
648 }
649
650 ret
651 }
652
653 #[inline(always)]
654 const fn montgomery_reduce(
655 r0: u64,
656 r1: u64,
657 r2: u64,
658 r3: u64,
659 r4: u64,
660 r5: u64,
661 r6: u64,
662 r7: u64,
663 ) -> Self {
664 // The Montgomery reduction here is based on Algorithm 14.32 in
665 // Handbook of Applied Cryptography
666 // <http://cacr.uwaterloo.ca/hac/about/chap14.pdf>.
667
668 let k = r0.wrapping_mul(INV);
669 let (_, carry) = mac(r0, k, MODULUS.0[0], 0);
670 let (r1, carry) = mac(r1, k, MODULUS.0[1], carry);
671 let (r2, carry) = mac(r2, k, MODULUS.0[2], carry);
672 let (r3, carry) = mac(r3, k, MODULUS.0[3], carry);
673 let (r4, carry2) = adc(r4, 0, carry);
674
675 let k = r1.wrapping_mul(INV);
676 let (_, carry) = mac(r1, k, MODULUS.0[0], 0);
677 let (r2, carry) = mac(r2, k, MODULUS.0[1], carry);
678 let (r3, carry) = mac(r3, k, MODULUS.0[2], carry);
679 let (r4, carry) = mac(r4, k, MODULUS.0[3], carry);
680 let (r5, carry2) = adc(r5, carry2, carry);
681
682 let k = r2.wrapping_mul(INV);
683 let (_, carry) = mac(r2, k, MODULUS.0[0], 0);
684 let (r3, carry) = mac(r3, k, MODULUS.0[1], carry);
685 let (r4, carry) = mac(r4, k, MODULUS.0[2], carry);
686 let (r5, carry) = mac(r5, k, MODULUS.0[3], carry);
687 let (r6, carry2) = adc(r6, carry2, carry);
688
689 let k = r3.wrapping_mul(INV);
690 let (_, carry) = mac(r3, k, MODULUS.0[0], 0);
691 let (r4, carry) = mac(r4, k, MODULUS.0[1], carry);
692 let (r5, carry) = mac(r5, k, MODULUS.0[2], carry);
693 let (r6, carry) = mac(r6, k, MODULUS.0[3], carry);
694 let (r7, _) = adc(r7, carry2, carry);
695
696 // Result may be within MODULUS of the correct value
697 (&Scalar([r4, r5, r6, r7])).sub(&MODULUS)
698 }
699
700 /// Multiplies `rhs` by `self`, returning the result.
701 #[inline]
702 pub const fn mul(&self, rhs: &Self) -> Self {
703 // Schoolbook multiplication
704
705 let (r0, carry) = mac(0, self.0[0], rhs.0[0], 0);
706 let (r1, carry) = mac(0, self.0[0], rhs.0[1], carry);
707 let (r2, carry) = mac(0, self.0[0], rhs.0[2], carry);
708 let (r3, r4) = mac(0, self.0[0], rhs.0[3], carry);
709
710 let (r1, carry) = mac(r1, self.0[1], rhs.0[0], 0);
711 let (r2, carry) = mac(r2, self.0[1], rhs.0[1], carry);
712 let (r3, carry) = mac(r3, self.0[1], rhs.0[2], carry);
713 let (r4, r5) = mac(r4, self.0[1], rhs.0[3], carry);
714
715 let (r2, carry) = mac(r2, self.0[2], rhs.0[0], 0);
716 let (r3, carry) = mac(r3, self.0[2], rhs.0[1], carry);
717 let (r4, carry) = mac(r4, self.0[2], rhs.0[2], carry);
718 let (r5, r6) = mac(r5, self.0[2], rhs.0[3], carry);
719
720 let (r3, carry) = mac(r3, self.0[3], rhs.0[0], 0);
721 let (r4, carry) = mac(r4, self.0[3], rhs.0[1], carry);
722 let (r5, carry) = mac(r5, self.0[3], rhs.0[2], carry);
723 let (r6, r7) = mac(r6, self.0[3], rhs.0[3], carry);
724
725 Scalar::montgomery_reduce(r0, r1, r2, r3, r4, r5, r6, r7)
726 }
727
728 /// Subtracts `rhs` from `self`, returning the result.
729 #[inline]
730 pub const fn sub(&self, rhs: &Self) -> Self {
731 let (d0, borrow) = sbb(self.0[0], rhs.0[0], 0);
732 let (d1, borrow) = sbb(self.0[1], rhs.0[1], borrow);
733 let (d2, borrow) = sbb(self.0[2], rhs.0[2], borrow);
734 let (d3, borrow) = sbb(self.0[3], rhs.0[3], borrow);
735
736 // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
737 // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
738 let (d0, carry) = adc(d0, MODULUS.0[0] & borrow, 0);
739 let (d1, carry) = adc(d1, MODULUS.0[1] & borrow, carry);
740 let (d2, carry) = adc(d2, MODULUS.0[2] & borrow, carry);
741 let (d3, _) = adc(d3, MODULUS.0[3] & borrow, carry);
742
743 Scalar([d0, d1, d2, d3])
744 }
745
746 /// Adds `rhs` to `self`, returning the result.
747 #[inline]
748 pub const fn add(&self, rhs: &Self) -> Self {
749 let (d0, carry) = adc(self.0[0], rhs.0[0], 0);
750 let (d1, carry) = adc(self.0[1], rhs.0[1], carry);
751 let (d2, carry) = adc(self.0[2], rhs.0[2], carry);
752 let (d3, _) = adc(self.0[3], rhs.0[3], carry);
753
754 // Attempt to subtract the modulus, to ensure the value
755 // is smaller than the modulus.
756 (&Scalar([d0, d1, d2, d3])).sub(&MODULUS)
757 }
758
759 /// Negates `self`.
760 #[inline]
761 pub const fn neg(&self) -> Self {
762 // Subtract `self` from `MODULUS` to negate. Ignore the final
763 // borrow because it cannot underflow; self is guaranteed to
764 // be in the field.
765 let (d0, borrow) = sbb(MODULUS.0[0], self.0[0], 0);
766 let (d1, borrow) = sbb(MODULUS.0[1], self.0[1], borrow);
767 let (d2, borrow) = sbb(MODULUS.0[2], self.0[2], borrow);
768 let (d3, _) = sbb(MODULUS.0[3], self.0[3], borrow);
769
770 // `tmp` could be `MODULUS` if `self` was zero. Create a mask that is
771 // zero if `self` was zero, and `u64::max_value()` if self was nonzero.
772 let mask = (((self.0[0] | self.0[1] | self.0[2] | self.0[3]) == 0) as u64).wrapping_sub(1);
773
774 Scalar([d0 & mask, d1 & mask, d2 & mask, d3 & mask])
775 }
776}
777
778impl<'a> From<&'a Scalar> for [u8; 32] {
779 fn from(value: &'a Scalar) -> [u8; 32] {
780 value.to_bytes()
781 }
782}
783
784#[cfg(test)]
785mod tests {
786 use super::*;
787
788 #[test]
789 fn test_inv() {
790 // Compute -(q^{-1} mod 2^64) mod 2^64 by exponentiating
791 // by totient(2**64) - 1
792
793 let mut inv = 1u64;
794 for _ in 0..63 {
795 inv = inv.wrapping_mul(inv);
796 inv = inv.wrapping_mul(MODULUS.0[0]);
797 }
798 inv = inv.wrapping_neg();
799
800 assert_eq!(inv, INV);
801 }
802
803 #[cfg(feature = "std")]
804 #[test]
805 fn test_debug() {
806 assert_eq!(
807 format!("{:?}", Scalar::zero()),
808 "0x0000000000000000000000000000000000000000000000000000000000000000"
809 );
810 assert_eq!(
811 format!("{:?}", Scalar::one()),
812 "0x0000000000000000000000000000000000000000000000000000000000000001"
813 );
814 assert_eq!(
815 format!("{:?}", R2),
816 "0x1824b159acc5056f998c4fefecbc4ff55884b7fa0003480200000001fffffffe"
817 );
818 }
819
820 #[test]
821 fn test_equality() {
822 assert_eq!(Scalar::zero(), Scalar::zero());
823 assert_eq!(Scalar::one(), Scalar::one());
824 assert_eq!(R2, R2);
825
826 assert!(Scalar::zero() != Scalar::one());
827 assert!(Scalar::one() != R2);
828 }
829
830 #[test]
831 fn test_to_bytes() {
832 assert_eq!(
833 Scalar::zero().to_bytes(),
834 [
835 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
836 0, 0
837 ]
838 );
839
840 assert_eq!(
841 Scalar::one().to_bytes(),
842 [
843 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
844 0, 0
845 ]
846 );
847
848 assert_eq!(
849 R2.to_bytes(),
850 [
851 29, 149, 152, 141, 116, 49, 236, 214, 112, 207, 125, 115, 244, 91, 239, 198, 254, 255, 255,
852 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 15
853 ]
854 );
855
856 assert_eq!(
857 (-&Scalar::one()).to_bytes(),
858 [
859 236, 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 249, 222, 20, 0, 0, 0, 0, 0, 0,
860 0, 0, 0, 0, 0, 0, 0, 0, 0, 16
861 ]
862 );
863 }
864
865 #[test]
866 fn test_from_bytes() {
867 assert_eq!(
868 Scalar::from_bytes(&[
869 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
870 0, 0
871 ])
872 .unwrap(),
873 Scalar::zero()
874 );
875
876 assert_eq!(
877 Scalar::from_bytes(&[
878 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
879 0, 0
880 ])
881 .unwrap(),
882 Scalar::one()
883 );
884
885 assert_eq!(
886 Scalar::from_bytes(&[
887 29, 149, 152, 141, 116, 49, 236, 214, 112, 207, 125, 115, 244, 91, 239, 198, 254, 255, 255,
888 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 15
889 ])
890 .unwrap(),
891 R2
892 );
893
894 // -1 should work
895 assert!(
896 Scalar::from_bytes(&[
897 236, 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 249, 222, 20, 0, 0, 0, 0, 0, 0,
898 0, 0, 0, 0, 0, 0, 0, 0, 0, 16
899 ])
900 .is_some()
901 .unwrap_u8()
902 == 1
903 );
904
905 // modulus is invalid
906 assert!(
907 Scalar::from_bytes(&[
908 1, 0, 0, 0, 255, 255, 255, 255, 254, 91, 254, 255, 2, 164, 189, 83, 5, 216, 161, 9, 8, 216,
909 57, 51, 72, 125, 157, 41, 83, 167, 237, 115
910 ])
911 .is_none()
912 .unwrap_u8()
913 == 1
914 );
915
916 // Anything larger than the modulus is invalid
917 assert!(
918 Scalar::from_bytes(&[
919 2, 0, 0, 0, 255, 255, 255, 255, 254, 91, 254, 255, 2, 164, 189, 83, 5, 216, 161, 9, 8, 216,
920 57, 51, 72, 125, 157, 41, 83, 167, 237, 115
921 ])
922 .is_none()
923 .unwrap_u8()
924 == 1
925 );
926 assert!(
927 Scalar::from_bytes(&[
928 1, 0, 0, 0, 255, 255, 255, 255, 254, 91, 254, 255, 2, 164, 189, 83, 5, 216, 161, 9, 8, 216,
929 58, 51, 72, 125, 157, 41, 83, 167, 237, 115
930 ])
931 .is_none()
932 .unwrap_u8()
933 == 1
934 );
935 assert!(
936 Scalar::from_bytes(&[
937 1, 0, 0, 0, 255, 255, 255, 255, 254, 91, 254, 255, 2, 164, 189, 83, 5, 216, 161, 9, 8, 216,
938 57, 51, 72, 125, 157, 41, 83, 167, 237, 116
939 ])
940 .is_none()
941 .unwrap_u8()
942 == 1
943 );
944 }
945
946 #[test]
947 fn test_from_u512_zero() {
948 assert_eq!(
949 Scalar::zero(),
950 Scalar::from_u512([
951 MODULUS.0[0],
952 MODULUS.0[1],
953 MODULUS.0[2],
954 MODULUS.0[3],
955 0,
956 0,
957 0,
958 0
959 ])
960 );
961 }
962
963 #[test]
964 fn test_from_u512_r() {
965 assert_eq!(R, Scalar::from_u512([1, 0, 0, 0, 0, 0, 0, 0]));
966 }
967
968 #[test]
969 fn test_from_u512_r2() {
970 assert_eq!(R2, Scalar::from_u512([0, 0, 0, 0, 1, 0, 0, 0]));
971 }
972
973 #[test]
974 fn test_from_u512_max() {
975 let max_u64 = 0xffffffffffffffff;
976 assert_eq!(
977 R3 - R,
978 Scalar::from_u512([max_u64, max_u64, max_u64, max_u64, max_u64, max_u64, max_u64, max_u64])
979 );
980 }
981
982 #[test]
983 fn test_from_bytes_wide_r2() {
984 assert_eq!(
985 R2,
986 Scalar::from_bytes_wide(&[
987 29, 149, 152, 141, 116, 49, 236, 214, 112, 207, 125, 115, 244, 91, 239, 198, 254, 255, 255,
988 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0,
989 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
990 ])
991 );
992 }
993
994 #[test]
995 fn test_from_bytes_wide_negative_one() {
996 assert_eq!(
997 -&Scalar::one(),
998 Scalar::from_bytes_wide(&[
999 236, 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 249, 222, 20, 0, 0, 0, 0, 0, 0,
1000 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1001 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1002 ])
1003 );
1004 }
1005
1006 #[test]
1007 fn test_from_bytes_wide_maximum() {
1008 assert_eq!(
1009 Scalar::from_raw([
1010 0xa40611e3449c0f00,
1011 0xd00e1ba768859347,
1012 0xceec73d217f5be65,
1013 0x0399411b7c309a3d
1014 ]),
1015 Scalar::from_bytes_wide(&[0xff; 64])
1016 );
1017 }
1018
1019 #[test]
1020 fn test_zero() {
1021 assert_eq!(Scalar::zero(), -&Scalar::zero());
1022 assert_eq!(Scalar::zero(), Scalar::zero() + Scalar::zero());
1023 assert_eq!(Scalar::zero(), Scalar::zero() - Scalar::zero());
1024 assert_eq!(Scalar::zero(), Scalar::zero() * Scalar::zero());
1025 }
1026
1027 const LARGEST: Scalar = Scalar([
1028 0x5812631a5cf5d3ec,
1029 0x14def9dea2f79cd6,
1030 0x0000000000000000,
1031 0x1000000000000000,
1032 ]);
1033
1034 #[test]
1035 fn test_addition() {
1036 let mut tmp = LARGEST;
1037 tmp += &LARGEST;
1038
1039 assert_eq!(
1040 tmp,
1041 Scalar([
1042 0x5812631a5cf5d3eb,
1043 0x14def9dea2f79cd6,
1044 0x0000000000000000,
1045 0x1000000000000000,
1046 ])
1047 );
1048
1049 let mut tmp = LARGEST;
1050 tmp += &Scalar([1, 0, 0, 0]);
1051
1052 assert_eq!(tmp, Scalar::zero());
1053 }
1054
1055 #[test]
1056 fn test_negation() {
1057 let tmp = -&LARGEST;
1058
1059 assert_eq!(tmp, Scalar([1, 0, 0, 0]));
1060
1061 let tmp = -&Scalar::zero();
1062 assert_eq!(tmp, Scalar::zero());
1063 let tmp = -&Scalar([1, 0, 0, 0]);
1064 assert_eq!(tmp, LARGEST);
1065 }
1066
1067 #[test]
1068 fn test_subtraction() {
1069 let mut tmp = LARGEST;
1070 tmp -= &LARGEST;
1071
1072 assert_eq!(tmp, Scalar::zero());
1073
1074 let mut tmp = Scalar::zero();
1075 tmp -= &LARGEST;
1076
1077 let mut tmp2 = MODULUS;
1078 tmp2 -= &LARGEST;
1079
1080 assert_eq!(tmp, tmp2);
1081 }
1082
1083 #[test]
1084 fn test_multiplication() {
1085 let mut cur = LARGEST;
1086
1087 for _ in 0..100 {
1088 let mut tmp = cur;
1089 tmp *= &cur;
1090
1091 let mut tmp2 = Scalar::zero();
1092 for b in cur
1093 .to_bytes()
1094 .iter()
1095 .rev()
1096 .flat_map(|byte| (0..8).rev().map(move |i| ((byte >> i) & 1u8) == 1u8))
1097 {
1098 let tmp3 = tmp2;
1099 tmp2.add_assign(&tmp3);
1100
1101 if b {
1102 tmp2.add_assign(&cur);
1103 }
1104 }
1105
1106 assert_eq!(tmp, tmp2);
1107
1108 cur.add_assign(&LARGEST);
1109 }
1110 }
1111
1112 #[test]
1113 fn test_squaring() {
1114 let mut cur = LARGEST;
1115
1116 for _ in 0..100 {
1117 let mut tmp = cur;
1118 tmp = tmp.square();
1119
1120 let mut tmp2 = Scalar::zero();
1121 for b in cur
1122 .to_bytes()
1123 .iter()
1124 .rev()
1125 .flat_map(|byte| (0..8).rev().map(move |i| ((byte >> i) & 1u8) == 1u8))
1126 {
1127 let tmp3 = tmp2;
1128 tmp2.add_assign(&tmp3);
1129
1130 if b {
1131 tmp2.add_assign(&cur);
1132 }
1133 }
1134
1135 assert_eq!(tmp, tmp2);
1136
1137 cur.add_assign(&LARGEST);
1138 }
1139 }
1140
1141 #[test]
1142 fn test_inversion() {
1143 assert_eq!(Scalar::zero().invert().is_none().unwrap_u8(), 1);
1144 assert_eq!(Scalar::one().invert().unwrap(), Scalar::one());
1145 assert_eq!((-&Scalar::one()).invert().unwrap(), -&Scalar::one());
1146
1147 let mut tmp = R2;
1148
1149 for _ in 0..100 {
1150 let mut tmp2 = tmp.invert().unwrap();
1151 tmp2.mul_assign(&tmp);
1152
1153 assert_eq!(tmp2, Scalar::one());
1154
1155 tmp.add_assign(&R2);
1156 }
1157 }
1158
1159 #[test]
1160 fn test_invert_is_pow() {
1161 let q_minus_2 = [
1162 0x5812631a5cf5d3eb,
1163 0x14def9dea2f79cd6,
1164 0x0000000000000000,
1165 0x1000000000000000,
1166 ];
1167
1168 let mut r1 = R;
1169 let mut r2 = R;
1170 let mut r3 = R;
1171
1172 for _ in 0..100 {
1173 r1 = r1.invert().unwrap();
1174 r2 = r2.pow_vartime(&q_minus_2);
1175 r3 = r3.pow(&q_minus_2);
1176
1177 assert_eq!(r1, r2);
1178 assert_eq!(r2, r3);
1179 // Add R so we check something different next time around
1180 r1.add_assign(&R);
1181 r2 = r1;
1182 r3 = r1;
1183 }
1184 }
1185
1186 #[test]
1187 fn test_from_raw() {
1188 assert_eq!(
1189 Scalar::from_raw([
1190 0xd6ec31748d98951c,
1191 0xc6ef5bf4737dcf70,
1192 0xfffffffffffffffe,
1193 0x0fffffffffffffff
1194 ]),
1195 Scalar::from_raw([0xffffffffffffffff; 4])
1196 );
1197
1198 assert_eq!(Scalar::from_raw(MODULUS.0), Scalar::zero());
1199
1200 assert_eq!(Scalar::from_raw([1, 0, 0, 0]), R);
1201 }
1202
1203 #[test]
1204 fn test_double() {
1205 let a = Scalar::from_raw([
1206 0x1fff3231233ffffd,
1207 0x4884b7fa00034802,
1208 0x998c4fefecbc4ff3,
1209 0x1824b159acc50562,
1210 ]);
1211
1212 assert_eq!(a.double(), a + a);
1213 }
1214}