tecdsa_core/arith/
monty.rs

1//! Modular arithmetic over an odd modulus with Montgomery parameters computed once.
2use crypto_bigint::{
3    BoxedUint, NonZero, Odd,
4    ctutils::CtSelect,
5    modular::{BoxedMontyForm, BoxedMontyParams},
6};
7
8use crypto_bigint::Resize;
9
10use super::sbig::{SBig, resized};
11use crate::error::{Error, Result};
12
13/// Residue ring `Z_M` for an odd `M`; parameters are shared (`Arc`) across clones.
14#[derive(Clone, Debug)]
15pub struct Modulus {
16    params: BoxedMontyParams,
17    nz: NonZero<BoxedUint>,
18}
19
20pub type Residue = BoxedMontyForm;
21
22impl Modulus {
23    pub fn new(m: BoxedUint) -> Result<Self> {
24        let odd = Option::<Odd<BoxedUint>>::from(m.to_odd()).ok_or(Error::InvalidModulus)?;
25        let nz = Option::<NonZero<BoxedUint>>::from(m.to_nz()).ok_or(Error::InvalidModulus)?;
26        Ok(Self {
27            params: BoxedMontyParams::new_vartime(odd),
28            nz,
29        })
30    }
31
32    pub fn from_be_bytes(bytes: &[u8]) -> Result<Self> {
33        let bits = (bytes.len() as u32 * 8).max(64);
34        let m = BoxedUint::from_be_slice(bytes, bits).map_err(|_| Error::InvalidEncoding)?;
35        Self::new(m)
36    }
37
38    pub fn modulus(&self) -> &NonZero<BoxedUint> {
39        &self.nz
40    }
41
42    pub fn bits_precision(&self) -> u32 {
43        self.params.bits_precision()
44    }
45
46    /// Residue of `x mod M` (any width).
47    pub fn residue(&self, x: &BoxedUint) -> Residue {
48        let prec = self.bits_precision();
49        let x = if x.bits_precision() > prec {
50            let wide = Option::<NonZero<BoxedUint>>::from(
51                resized(self.nz.as_ref(), x.bits_precision()).to_nz(),
52            )
53            .unwrap_or_else(|| self.nz.clone());
54            x.rem(&wide).resize(prec)
55        } else {
56            resized(x, prec)
57        };
58        BoxedMontyForm::new(x, &self.params)
59    }
60
61    pub fn residue_signed(&self, x: &SBig) -> Residue {
62        let r = self.residue(x.mag());
63        let n = r.neg();
64        Residue::from_montgomery(
65            r.as_montgomery().ct_select(n.as_montgomery(), x.is_neg()),
66            &self.params,
67        )
68    }
69
70    pub fn one(&self) -> Residue {
71        BoxedMontyForm::one(&self.params)
72    }
73
74    pub fn invert(&self, a: &Residue) -> Result<Residue> {
75        Option::from(a.invert()).ok_or(Error::NotInvertible)
76    }
77
78    /// `base^exp` with a secret exponent whose magnitude fits in `exp_bits` bits (leaked).
79    /// Negative exponents invert the base; invertibility of the base is public.
80    pub fn pow_ct(&self, base: &Residue, exp: &SBig, exp_bits: u32) -> Result<Residue> {
81        let inv = self.invert(base)?;
82        let b = Residue::from_montgomery(
83            base.as_montgomery()
84                .ct_select(inv.as_montgomery(), exp.is_neg()),
85            &self.params,
86        );
87        Ok(b.pow_bounded_exp(exp.mag(), exp_bits.min(exp.mag().bits_precision())))
88    }
89
90    /// `base^exp` for public exponents.
91    pub fn pow_vartime(&self, base: &Residue, exp: &SBig) -> Result<Residue> {
92        let bits = exp.mag().bits_vartime();
93        let b = if bool::from(exp.is_neg()) {
94            self.invert(base)?
95        } else {
96            base.clone()
97        };
98        if bits == 0 {
99            return Ok(self.one());
100        }
101        Ok(b.pow_bounded_exp(exp.mag(), bits))
102    }
103
104    /// Jacobi symbol `(a/M)` for public `a` (binary algorithm, variable time): −1, 0 or 1.
105    pub fn jacobi_vartime(&self, a: &BoxedUint) -> i8 {
106        jacobi_vartime(a, self.nz.as_ref())
107    }
108}
109
110/// Jacobi symbol `(a/n)` for odd `n`, variable time.
111pub fn jacobi_vartime(a: &BoxedUint, n: &BoxedUint) -> i8 {
112    let bits = a.bits_precision().max(n.bits_precision());
113    let mut n = resized(n, bits);
114    let mut a = match NonZero::new(n.clone()).into_option() {
115        Some(nz) => resized(a, bits).rem_vartime(&nz),
116        None => return 0,
117    };
118    let mut t: i8 = 1;
119    while !bool::from(a.is_zero()) {
120        let tz = a.trailing_zeros_vartime();
121        a = a
122            .shr_vartime(tz)
123            .unwrap_or_else(|| BoxedUint::zero_with_precision(bits));
124        let n_mod8 = n.as_words()[0] & 7;
125        if tz % 2 == 1 && (n_mod8 == 3 || n_mod8 == 5) {
126            t = -t;
127        }
128        core::mem::swap(&mut a, &mut n);
129        if a.as_words()[0] & 3 == 3 && n.as_words()[0] & 3 == 3 {
130            t = -t;
131        }
132        if let Some(nz) = NonZero::new(n.clone()).into_option() {
133            a = a.rem_vartime(&nz);
134        }
135    }
136    if n.is_one().into() { t } else { 0 }
137}
tecdsa_core/arith/monty.rs

tecdsa_core/arith/
monty.rs
