nautilus_lighter/signing/curve/
scalar.rs

1// -------------------------------------------------------------------------------------------------
2//  Copyright (C) 2015-2026 Nautech Systems Pty Ltd. All rights reserved.
3//  https://nautechsystems.io
4//
5//  Licensed under the GNU Lesser General Public License Version 3.0 (the "License");
6//  You may not use this file except in compliance with the License.
7//  You may obtain a copy of the License at https://www.gnu.org/licenses/lgpl-3.0.en.html
8//
9//  Unless required by applicable law or agreed to in writing, software
10//  distributed under the License is distributed on an "AS IS" BASIS,
11//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//  See the License for the specific language governing permissions and
13//  limitations under the License.
14// -------------------------------------------------------------------------------------------------
15
16//! Scalar field of the ECgFp5 curve.
17//!
18//! Operates modulo the prime group order `n`, a 319-bit prime stored as five
19//! 64-bit little-endian limbs in non-Montgomery form. Encoding/decoding and
20//! addition/subtraction work directly on the limbs; multiplication uses
21//! Montgomery form internally with the precomputed constants `R^2 mod n` and
22//! `-1/n[0] mod 2^64`.
23//!
24//! All arithmetic primitives execute as branch-free limb-wise sequences so
25//! timing reveals nothing about secret operands. The variable-time helpers are
26//! confined to encode/decode-style boundaries (`from_le_bytes_reduce`) and the
27//! signed-window recoding used by the variable-time scalar multiplication.
28
29use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
30
31use crate::signing::field::Fp5;
32
33/// Number of 64-bit limbs in a scalar.
34pub const LIMBS: usize = 5;
35
36/// Canonical 40-byte little-endian encoding length for a scalar.
37pub const SCALAR_BYTES: usize = LIMBS * 8;
38
39/// Group order `n` of the ECgFp5 curve, a 319-bit prime.
40///
41/// `n = 1067993516717146951041484916571792702745057740581727230159139685185762082554198619328292418486241`
42pub const ORDER: Scalar = Scalar([
43    0xE80F_D996_948B_FFE1,
44    0xE888_5C39_D724_A09C,
45    0x7FFF_FFE6_CFB8_0639,
46    0x7FFF_FFF1_0000_0016,
47    0x7FFF_FFFD_8000_0007,
48]);
49
50/// `-1 / n[0] mod 2^64`, the precomputed Montgomery reduction multiplier.
51const N0I: u64 = 0xD78B_EF72_057B_7BDF;
52
53/// `R^2 mod n` with `R = 2^320`. Multiplying by this lifts a value into
54/// Montgomery form via [`Scalar::monty_mul`].
55const R2: Scalar = Scalar([
56    0xA010_01DC_E33D_C739,
57    0x6C32_28D3_3F62_ACCF,
58    0xD1D7_96CC_91CF_8525,
59    0xAADF_FF5D_1574_C1D8,
60    0x4ACA_13B2_8CA2_51F5,
61]);
62
63/// A scalar in the ECgFp5 curve's scalar field, stored in non-Montgomery form
64/// as five 64-bit little-endian limbs.
65///
66/// Canonical instances (`< n`) round-trip through every public operation. The
67/// arithmetic primitives `add` / `sub` / `mul` require canonical inputs;
68/// `from_le_bytes_reduce` handles the wider input range produced by hashing.
69#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
70pub struct Scalar(pub [u64; LIMBS]);
71
72impl Scalar {
73    /// Additive identity.
74    pub const ZERO: Self = Self([0; LIMBS]);
75
76    /// Multiplicative identity.
77    pub const ONE: Self = Self([1, 0, 0, 0, 0]);
78
79    /// Build a scalar from five raw 64-bit limbs without any reduction.
80    ///
81    /// The caller is responsible for ensuring the value is canonical when it
82    /// will subsequently feed the modular `Add`, `Sub`, `Neg` or `Mul`
83    /// operators.
84    #[inline]
85    #[must_use]
86    pub const fn from_limbs(limbs: [u64; LIMBS]) -> Self {
87        Self(limbs)
88    }
89
90    /// Return the underlying limbs in little-endian order.
91    #[inline]
92    #[must_use]
93    pub const fn to_limbs(self) -> [u64; LIMBS] {
94        self.0
95    }
96
97    /// Test whether this scalar is canonical (`self < n`).
98    #[must_use]
99    pub fn is_canonical(self) -> bool {
100        for i in (0..LIMBS).rev() {
101            if self.0[i] < ORDER.0[i] {
102                return true;
103            }
104
105            if self.0[i] > ORDER.0[i] {
106                return false;
107            }
108        }
109        false
110    }
111
112    /// Test whether the scalar is zero.
113    #[inline]
114    #[must_use]
115    pub const fn is_zero(self) -> bool {
116        let mut acc: u64 = 0;
117        let mut i = 0;
118
119        while i < LIMBS {
120            acc |= self.0[i];
121            i += 1;
122        }
123        acc == 0
124    }
125
126    /// Canonical 40-byte little-endian encoding (5 x 8-byte limbs).
127    #[must_use]
128    pub fn to_le_bytes(self) -> [u8; SCALAR_BYTES] {
129        let mut out = [0u8; SCALAR_BYTES];
130
131        for (i, limb) in self.0.iter().enumerate() {
132            out[i * 8..(i + 1) * 8].copy_from_slice(&limb.to_le_bytes());
133        }
134        out
135    }
136
137    /// Decode 40 little-endian bytes, reducing modulo `n` if the encoded value
138    /// exceeds the canonical range. Mirrors the upstream Lighter helper.
139    #[must_use]
140    pub fn from_le_bytes_reduce(bytes: [u8; SCALAR_BYTES]) -> Self {
141        let mut limbs = [0u64; LIMBS];
142
143        for (i, slot) in limbs.iter_mut().enumerate() {
144            let mut chunk = [0u8; 8];
145            chunk.copy_from_slice(&bytes[i * 8..(i + 1) * 8]);
146            *slot = u64::from_le_bytes(chunk);
147        }
148
149        let s = Self(limbs);
150        if s.is_canonical() {
151            s
152        } else {
153            // The encoded integer is at most `2^320 - 1 < 4 * n`, so at most
154            // two conditional subtractions land us in canonical range.
155            let (s1, b1) = s.sub_inner(ORDER);
156            let s_after1 = if b1 != 0 { s } else { s1 };
157            let (s2, b2) = s_after1.sub_inner(ORDER);
158            if b2 != 0 { s_after1 } else { s2 }
159        }
160    }
161
162    /// Branch-free constant-time select: returns `a0` when `c == 0` and `a1`
163    /// when `c == u64::MAX`.
164    #[inline]
165    #[must_use]
166    pub const fn select(c: u64, a0: Self, a1: Self) -> Self {
167        Self([
168            a0.0[0] ^ (c & (a0.0[0] ^ a1.0[0])),
169            a0.0[1] ^ (c & (a0.0[1] ^ a1.0[1])),
170            a0.0[2] ^ (c & (a0.0[2] ^ a1.0[2])),
171            a0.0[3] ^ (c & (a0.0[3] ^ a1.0[3])),
172            a0.0[4] ^ (c & (a0.0[4] ^ a1.0[4])),
173        ])
174    }
175
176    /// Raw 320-bit addition with no modular reduction.
177    #[inline]
178    #[must_use]
179    pub fn add_inner(self, rhs: Self) -> Self {
180        let mut r = [0u64; LIMBS];
181        let mut carry: u8 = 0;
182
183        for (i, slot) in r.iter_mut().enumerate() {
184            let (t1, c1) = self.0[i].overflowing_add(rhs.0[i]);
185            let (t2, c2) = t1.overflowing_add(u64::from(carry));
186            *slot = t2;
187            carry = u8::from(c1) | u8::from(c2);
188        }
189        Self(r)
190    }
191
192    /// Raw 320-bit subtraction with no modular reduction. Returns the
193    /// difference and an `0` / `u64::MAX` mask indicating whether the operation
194    /// borrowed beyond the top limb.
195    #[inline]
196    #[must_use]
197    pub fn sub_inner(self, rhs: Self) -> (Self, u64) {
198        let mut r = [0u64; LIMBS];
199        let mut borrow: u8 = 0;
200
201        for (i, slot) in r.iter_mut().enumerate() {
202            let (t1, b1) = self.0[i].overflowing_sub(rhs.0[i]);
203            let (t2, b2) = t1.overflowing_sub(u64::from(borrow));
204            *slot = t2;
205            borrow = u8::from(b1) | u8::from(b2);
206        }
207        let mask = if borrow != 0 { u64::MAX } else { 0 };
208        (Self(r), mask)
209    }
210
211    /// Montgomery multiplication `(self * rhs) / 2^320 mod n`.
212    ///
213    /// `self` MUST be canonical. `rhs` may exceed `n` provided it fits in 320
214    /// bits, mirroring the upstream behaviour used to lift values into
215    /// Montgomery form via the `R2` constant.
216    #[must_use]
217    pub fn monty_mul(self, rhs: Self) -> Self {
218        debug_assert!(self.is_canonical(), "Scalar::monty_mul: lhs not canonical",);
219
220        let mut r = [0u64; LIMBS];
221
222        for i in 0..LIMBS {
223            let m = rhs.0[i];
224            let f = (self.0[0].wrapping_mul(m).wrapping_add(r[0])).wrapping_mul(N0I);
225
226            let mut cc1: u64 = 0;
227            let mut cc2: u64 = 0;
228
229            for j in 0..LIMBS {
230                let prod = u128::from(self.0[j]) * u128::from(m);
231                let s1 = prod + u128::from(r[j]) + u128::from(cc1);
232                cc1 = (s1 >> 64) as u64;
233                let s1_lo = s1 as u64;
234
235                let prod_n = u128::from(f) * u128::from(ORDER.0[j]);
236                let s2 = prod_n + u128::from(s1_lo) + u128::from(cc2);
237                cc2 = (s2 >> 64) as u64;
238                let s2_lo = s2 as u64;
239
240                if j > 0 {
241                    r[j - 1] = s2_lo;
242                }
243            }
244            r[LIMBS - 1] = cc1.wrapping_add(cc2);
245        }
246
247        let r0 = Self(r);
248        let (r1, c) = r0.sub_inner(ORDER);
249        Self::select(c, r1, r0)
250    }
251
252    /// Build a scalar from an `Fp5` element via reduction modulo `n`.
253    ///
254    /// Concatenates the five canonical 64-bit limbs of `e` into a 320-bit
255    /// little-endian integer and reduces, matching the upstream behaviour of
256    /// `FromGfp5`. Used by the Schnorr binding to derive a scalar from a
257    /// Poseidon2 digest.
258    #[must_use]
259    pub fn from_fp5(e: Fp5) -> Self {
260        let mut bytes = [0u8; SCALAR_BYTES];
261        let encoded = e.to_le_bytes();
262        bytes.copy_from_slice(&encoded);
263        Self::from_le_bytes_reduce(bytes)
264    }
265
266    /// Split the canonical scalar value into 80 little-endian 4-bit nibbles.
267    ///
268    /// Iteration order is least-significant nibble first.
269    #[must_use]
270    pub fn split_to_4_bit_limbs(self) -> [u8; 80] {
271        let mut out = [0u8; 80];
272
273        for i in 0..LIMBS {
274            for j in 0..16 {
275                out[i * 16 + j] = ((self.0[i] >> (j * 4)) & 0xF) as u8;
276            }
277        }
278        out
279    }
280
281    /// Recode the scalar into signed digits for a width-`w` window.
282    ///
283    /// `ss` is filled with `(2^w + 1)`-range signed values (lying in
284    /// `-(2^(w-1)) ..= 2^(w-1)` after carry propagation) so that
285    /// `sum(ss[i] * 2^(w*i)) == self mod 2^(w * len)`. When `w * len >= 320`,
286    /// the recoding spans the entire scalar and the top digit is non-negative.
287    ///
288    /// `w` MUST satisfy `2 <= w <= 10`. This helper is variable-time and is
289    /// only suitable for non-secret window selection.
290    pub fn recode_signed(self, ss: &mut [i32], w: u32) {
291        recode_signed_from_limbs(&self.0, ss, w);
292    }
293}
294
295/// Recode an arbitrary little-endian limb sequence into signed window digits.
296/// Standalone helper exposed mainly for testing parity with the upstream code.
297pub fn recode_signed_from_limbs(limbs: &[u64], ss: &mut [i32], w: u32) {
298    debug_assert!((2..=10).contains(&w), "window width must be in 2..=10");
299
300    let mw = (1u32 << w) - 1;
301    let hw = 1u32 << (w - 1);
302
303    let mut acc: u64 = 0;
304    let mut acc_len: i32 = 0;
305    let mut j: usize = 0;
306    let mut cc: u32 = 0;
307    let w_i32 = w as i32;
308
309    for slot in ss.iter_mut() {
310        let bb: u32 = if acc_len < w_i32 {
311            if j < limbs.len() {
312                let nl = limbs[j];
313                j += 1;
314                let bits = ((acc | (nl << acc_len)) as u32) & mw;
315                acc = nl >> (w_i32 - acc_len);
316                acc_len += 64 - w_i32;
317                bits
318            } else {
319                let bits = (acc as u32) & mw;
320                acc = 0;
321                acc_len += 64 - w_i32;
322                bits
323            }
324        } else {
325            let bits = (acc as u32) & mw;
326            acc_len -= w_i32;
327            acc >>= w;
328            bits
329        };
330
331        let sum = bb.wrapping_add(cc);
332        cc = (hw.wrapping_sub(sum)) >> 31;
333        *slot = (sum as i32) - ((cc << w) as i32);
334    }
335}
336
337impl Default for Scalar {
338    #[inline]
339    fn default() -> Self {
340        Self::ZERO
341    }
342}
343
344impl Add for Scalar {
345    type Output = Self;
346
347    fn add(self, rhs: Self) -> Self {
348        debug_assert!(self.is_canonical(), "Scalar add: lhs not canonical");
349        debug_assert!(rhs.is_canonical(), "Scalar add: rhs not canonical");
350
351        let r0 = self.add_inner(rhs);
352        let (r1, c) = r0.sub_inner(ORDER);
353        Self::select(c, r1, r0)
354    }
355}
356
357impl AddAssign for Scalar {
358    fn add_assign(&mut self, rhs: Self) {
359        *self = *self + rhs;
360    }
361}
362
363impl Sub for Scalar {
364    type Output = Self;
365
366    fn sub(self, rhs: Self) -> Self {
367        debug_assert!(self.is_canonical(), "Scalar sub: lhs not canonical");
368        debug_assert!(rhs.is_canonical(), "Scalar sub: rhs not canonical");
369
370        let (r0, c) = self.sub_inner(rhs);
371        let r1 = r0.add_inner(ORDER);
372        Self::select(c, r0, r1)
373    }
374}
375
376impl SubAssign for Scalar {
377    fn sub_assign(&mut self, rhs: Self) {
378        *self = *self - rhs;
379    }
380}
381
382impl Neg for Scalar {
383    type Output = Self;
384
385    fn neg(self) -> Self {
386        debug_assert!(self.is_canonical(), "Scalar neg: input not canonical");
387        Self::ZERO - self
388    }
389}
390
391impl Mul for Scalar {
392    type Output = Self;
393
394    fn mul(self, rhs: Self) -> Self {
395        debug_assert!(self.is_canonical(), "Scalar mul: lhs not canonical");
396        debug_assert!(rhs.is_canonical(), "Scalar mul: rhs not canonical");
397
398        self.monty_mul(R2).monty_mul(rhs)
399    }
400}
401
402impl MulAssign for Scalar {
403    fn mul_assign(&mut self, rhs: Self) {
404        *self = *self * rhs;
405    }
406}
407
408#[cfg(test)]
409mod tests {
410    use proptest::prelude::*;
411    use rstest::rstest;
412
413    use super::*;
414    use crate::signing::fixtures::{arb_scalar, arb_scalar_nonzero};
415
416    #[rstest]
417    fn order_round_trips_through_le_bytes() {
418        let bytes = ORDER.to_le_bytes();
419        // ORDER itself is not canonical (`< n` is false at equality), but the
420        // round-trip-with-reduce should normalize it to zero.
421        let s = Scalar::from_le_bytes_reduce(bytes);
422        assert_eq!(s, Scalar::ZERO);
423    }
424
425    #[rstest]
426    fn add_inner_carries_through_top_limb() {
427        let scalar1 = Scalar([
428            0xFFFF_FFFF_FFFF_FFFF,
429            0xFFFF_FFFF_FFFF_FFFF,
430            0xFFFF_FFFF_FFFF_FFFF,
431            0xFFFF_FFFF_FFFF_FFFF,
432            0xFFFF_FFFF_FFFF_FFFF,
433        ]);
434        let scalar2 = Scalar([
435            0x00FF_FFFF_FFFE_EFFF,
436            12_312_321_312,
437            0xFFFF_FFFF_FFFF_FFFF,
438            0x00FF_FFFF_FACD_FFFF,
439            0xBCAF_FFFF_FFFF_FFFF,
440        ]);
441        let expected = Scalar([
442            0x00FF_FFFF_FFFE_EFFE,
443            0x0000_0002_DDDF_1D20,
444            0xFFFF_FFFF_FFFF_FFFF,
445            0x00FF_FFFF_FACD_FFFF,
446            0xBCAF_FFFF_FFFF_FFFF,
447        ]);
448        assert_eq!(scalar1.add_inner(scalar2), expected);
449    }
450
451    #[rstest]
452    fn sub_inner_signals_borrow() {
453        let scalar1 = Scalar::ZERO;
454        let scalar2 = Scalar([u64::MAX; 5]);
455        let (result, borrow) = scalar1.sub_inner(scalar2);
456        assert_eq!(result, Scalar([1, 0, 0, 0, 0]));
457        assert_eq!(borrow, u64::MAX);
458    }
459
460    #[rstest]
461    fn modular_sub_wraps_through_order() {
462        let scalar1 = Scalar([1, 2, 0, 0, 0]);
463        let scalar2 = Scalar([
464            0xFFFF_FFFF_FFFF_FFFF,
465            0xFFFF_FFFF_FFFF_FFFF,
466            0xFFFF_FFFF_FFFF_FFFF,
467            0xFFFF_FFFF_FFFF_FFFF,
468            0x0FFF_FFFF_FFFF_FFFF,
469        ]);
470        assert!(scalar2.is_canonical());
471
472        let result = scalar1 - scalar2;
473        let expected = Scalar([
474            0xE80F_D996_948B_FFE3,
475            0xE888_5C39_D724_A09E,
476            0x7FFF_FFE6_CFB8_0639,
477            0x7FFF_FFF1_0000_0016,
478            8_070_450_521_510_510_599,
479        ]);
480        assert_eq!(result, expected);
481    }
482
483    #[rstest]
484    fn select_picks_branch_by_mask() {
485        let a0 = Scalar([1, 2, 3, 4, 5]);
486        let a1 = Scalar([
487            0xFFFF_FFFF_FFFF_FFFF,
488            0xFFFF_FFFF_FFFF_FFFE,
489            0xFFFF_FFFF_FFFF_FFFD,
490            0xFFFF_FFFF_FFFF_FFFC,
491            0xFFFF_FFFF_FFFF_FFFB,
492        ]);
493        assert_eq!(Scalar::select(0, a0, a1), a0);
494        assert_eq!(Scalar::select(u64::MAX, a0, a1), a1);
495    }
496
497    #[rstest]
498    fn one_is_multiplicative_identity() {
499        let s = Scalar([
500            0x1234_5678_90AB_CDEF,
501            0xFEDC_BA98_7654_3210,
502            0x0123_4567_89AB_CDEF,
503            0xFEDC_BA98_7654_3210,
504            0x1234_5678_90AB_CDEF,
505        ]);
506        assert!(s.is_canonical());
507        assert_eq!(s * Scalar::ONE, s);
508        assert_eq!(Scalar::ONE * s, s);
509    }
510
511    #[rstest]
512    fn neg_is_additive_inverse() {
513        let s = Scalar([7, 11, 13, 17, 19]);
514        let zero = s + (-s);
515        assert_eq!(zero, Scalar::ZERO);
516    }
517
518    #[rstest]
519    fn split_to_4_bit_limbs_matches_reference_vector() {
520        let scalar = Scalar([
521            6_950_590_877_883_398_434,
522            17_178_336_263_794_770_543,
523            11_012_823_478_139_181_320,
524            16_445_091_359_523_510_936,
525            5_882_925_226_143_600_273,
526        ]);
527
528        let limbs = scalar.split_to_4_bit_limbs();
529        // Spot-check a handful of nibbles against the upstream Go vector.
530        assert_eq!(limbs[0], 2);
531        assert_eq!(limbs[1], 2);
532        assert_eq!(limbs[2], 9);
533        assert_eq!(limbs[16], 15);
534        assert_eq!(limbs[39], 13);
535        assert_eq!(limbs[79], 5);
536
537        // Stronger: the nibble sequence reconstructs the original limbs.
538        assert_eq!(reconstruct_from_4_bit_nibbles(limbs), scalar.0);
539    }
540
541    /// Reconstruct a 5-limb scalar by repacking 80 little-endian 4-bit nibbles
542    /// back into 5 u64s.
543    fn reconstruct_from_4_bit_nibbles(nibbles: [u8; 80]) -> [u64; LIMBS] {
544        let mut out = [0u64; LIMBS];
545        for (i, slot) in out.iter_mut().enumerate() {
546            let mut v: u64 = 0;
547            for j in 0..16 {
548                v |= u64::from(nibbles[i * 16 + j]) << (j * 4);
549            }
550            *slot = v;
551        }
552        out
553    }
554
555    /// Reconstruct the 5-limb scalar value from its signed-window digits via
556    /// `sum(ss[i] * 2^(w*i)) mod 2^320`. Used in tests to pin the recoding
557    /// spec.
558    fn reconstruct_from_signed_digits(ss: &[i32], w: u32) -> [u64; LIMBS] {
559        // 5 + 2 buffer limbs to absorb intermediate overflow before
560        // propagating carries.
561        let mut limbs = [0i128; LIMBS + 2];
562
563        for (i, &d) in ss.iter().enumerate() {
564            let shift = (i as u64) * u64::from(w);
565            if shift >= ((LIMBS + 2) as u64) * 64 {
566                continue;
567            }
568            let limb_idx = (shift / 64) as usize;
569            let bit_off = (shift % 64) as u32;
570            // Each digit lies in roughly `-(2^(w-1)+1) ..= 2^(w-1)+1` and
571            // `bit_off <= 63`, so the shifted value fits in i128.
572            let shifted = (d as i128) << bit_off;
573            let lo_mask: i128 = (1i128 << 64) - 1;
574            limbs[limb_idx] += shifted & lo_mask;
575            if limb_idx + 1 < limbs.len() {
576                limbs[limb_idx + 1] += shifted >> 64;
577            }
578        }
579        let mut out = [0u64; LIMBS];
580        let mut carry: i128 = 0;
581        for (i, slot) in out.iter_mut().enumerate() {
582            let v = limbs[i] + carry;
583            *slot = v as u64;
584            carry = v >> 64;
585        }
586        out
587    }
588
589    #[rstest]
590    fn recode_signed_top_digit_is_nonnegative() {
591        // Using the example from the upstream test, the top digit at index 32
592        // (5-bit window over 5 limbs) is `-1` after carry propagation. The
593        // 66-slot buffer covers the full 320-bit scalar (`64 * 5 = 320`) with
594        // two slack slots so the reconstruction round-trip below has room for
595        // any trailing carry.
596        use crate::signing::field::MODULUS;
597
598        let mut ss = [0i32; 66];
599        let scalar = Scalar([
600            MODULUS - 1,
601            MODULUS - 2,
602            MODULUS - 3,
603            0xFFFF_FFFF_FFFF_FFFF,
604            MODULUS - 5,
605        ]);
606        scalar.recode_signed(&mut ss, 5);
607
608        assert_eq!(ss[6], -4);
609        assert_eq!(ss[19], -2);
610        assert_eq!(ss[25], -8);
611        assert_eq!(ss[32], -1);
612
613        // Stronger: the recoded digits reconstruct the original limbs via
614        // `sum(ss[i] * 2^(w*i)) mod 2^320`.
615        assert_eq!(reconstruct_from_signed_digits(&ss, 5), scalar.0);
616    }
617
618    proptest! {
619        /// Modular addition is commutative.
620        #[rstest]
621        fn prop_add_commutative(a in arb_scalar(), b in arb_scalar()) {
622            prop_assert_eq!(a + b, b + a);
623        }
624
625        /// Modular addition is associative.
626        #[rstest]
627        fn prop_add_associative(a in arb_scalar(), b in arb_scalar(), c in arb_scalar()) {
628            prop_assert_eq!((a + b) + c, a + (b + c));
629        }
630
631        /// `a + (-a) == 0`.
632        #[rstest]
633        fn prop_neg_inverse(a in arb_scalar()) {
634            prop_assert_eq!(a + (-a), Scalar::ZERO);
635        }
636
637        /// `(a + b) - b == a`.
638        #[rstest]
639        fn prop_sub_round_trip(a in arb_scalar(), b in arb_scalar()) {
640            prop_assert_eq!((a + b) - b, a);
641        }
642
643        /// `a - b == a + (-b)`.
644        #[rstest]
645        fn prop_sub_via_add_neg(a in arb_scalar(), b in arb_scalar()) {
646            prop_assert_eq!(a - b, a + (-b));
647        }
648
649        /// Modular multiplication is commutative.
650        #[rstest]
651        fn prop_mul_commutative(a in arb_scalar(), b in arb_scalar()) {
652            prop_assert_eq!(a * b, b * a);
653        }
654
655        /// Modular multiplication is associative.
656        #[rstest]
657        fn prop_mul_associative(a in arb_scalar(), b in arb_scalar(), c in arb_scalar()) {
658            prop_assert_eq!((a * b) * c, a * (b * c));
659        }
660
661        /// Multiplication distributes over addition.
662        #[rstest]
663        fn prop_distributive(a in arb_scalar(), b in arb_scalar(), c in arb_scalar()) {
664            prop_assert_eq!(a * (b + c), a * b + a * c);
665        }
666
667        /// `Scalar::ONE` is the multiplicative identity.
668        #[rstest]
669        fn prop_one_is_identity(a in arb_scalar()) {
670            prop_assert_eq!(a * Scalar::ONE, a);
671            prop_assert_eq!(Scalar::ONE * a, a);
672        }
673
674        /// `Scalar::ZERO` annihilates multiplication.
675        #[rstest]
676        fn prop_zero_annihilates(a in arb_scalar()) {
677            prop_assert_eq!(a * Scalar::ZERO, Scalar::ZERO);
678            prop_assert_eq!(Scalar::ZERO * a, Scalar::ZERO);
679        }
680
681        /// `from_le_bytes_reduce(s.to_le_bytes()) == s` for any canonical
682        /// scalar (idempotency under round-trip).
683        #[rstest]
684        fn prop_from_le_bytes_reduce_idempotent(s in arb_scalar()) {
685            prop_assert_eq!(Scalar::from_le_bytes_reduce(s.to_le_bytes()), s);
686        }
687
688        /// Decoding any 40-byte sequence produces a canonical scalar.
689        #[rstest]
690        fn prop_from_le_bytes_reduce_yields_canonical(bytes in any::<[u8; SCALAR_BYTES]>()) {
691            prop_assert!(Scalar::from_le_bytes_reduce(bytes).is_canonical());
692        }
693
694        /// `is_canonical` matches the hand-rolled limb compare against ORDER.
695        #[rstest]
696        fn prop_is_canonical_matches_lex_compare(s in arb_scalar()) {
697            // Canonical iff `s < ORDER` lex-wise on the limb sequence.
698            let mut expected = false;
699
700            for i in (0..LIMBS).rev() {
701                if s.0[i] < ORDER.0[i] {
702                    expected = true;
703                    break;
704                }
705
706                if s.0[i] > ORDER.0[i] {
707                    expected = false;
708                    break;
709                }
710            }
711            prop_assert_eq!(s.is_canonical(), expected);
712        }
713
714        /// Scalar `select` picks branch by mask.
715        #[rstest]
716        fn prop_select_picks_branch(a in arb_scalar(), b in arb_scalar()) {
717            prop_assert_eq!(Scalar::select(0, a, b), a);
718            prop_assert_eq!(Scalar::select(u64::MAX, a, b), b);
719        }
720
721        /// `recode_signed` reconstructs the canonical 5-limb value via
722        /// `sum(ss[i] * 2^(w*i)) mod 2^320` for every supported window width.
723        #[rstest]
724        fn prop_recode_signed_reconstructs(s in arb_scalar(), w in 2u32..=10) {
725            // 320 bits divided by `w`, rounded up, plus 2 slack slots so the
726            // final carry has somewhere to land regardless of window width.
727            let len = (320usize.div_ceil(w as usize)) + 2;
728            let mut ss = vec![0i32; len];
729            s.recode_signed(&mut ss, w);
730            prop_assert_eq!(reconstruct_from_signed_digits(&ss, w), s.0);
731
732            // Each digit must lie in the signed window range.
733            let bound: i32 = 1 << (w - 1);
734
735            for (i, &d) in ss.iter().enumerate() {
736                prop_assert!(
737                    d >= -bound && d <= bound,
738                    "digit {d} at index {i} outside [-{bound}, {bound}]",
739                );
740            }
741        }
742
743        /// `split_to_4_bit_limbs` and the test's reconstruction helper are
744        /// inverses for any canonical scalar.
745        #[rstest]
746        fn prop_split_to_4_bit_limbs_round_trip(s in arb_scalar()) {
747            prop_assert_eq!(reconstruct_from_4_bit_nibbles(s.split_to_4_bit_limbs()), s.0);
748        }
749
750        /// Every 4-bit nibble lies in `0..=15` for any scalar input.
751        #[rstest]
752        fn prop_split_to_4_bit_limbs_in_range(s in arb_scalar()) {
753            for &nibble in &s.split_to_4_bit_limbs() {
754                prop_assert!(nibble <= 15);
755            }
756        }
757    }
758
759    // `arb_scalar_nonzero` corollary: doubling a non-zero scalar lands on
760    // `2 * s mod n`. Kept in its own block so consumers that import only
761    // `arb_scalar` upstream don't pull the `nonzero` filter unnecessarily.
762    proptest! {
763        #[rstest]
764        fn prop_double_via_add(s in arb_scalar_nonzero()) {
765            prop_assert_eq!(s + s, s * Scalar::from_limbs([2, 0, 0, 0, 0]));
766        }
767    }
768}
nautilus_lighter/signing/curve/scalar.rs

nautilus_lighter/signing/curve/
scalar.rs
