crypto_bigint/modular/
prime_params.rs

1//! Parameter calculation for prime moduli.
2
3use core::num::NonZeroU32;
4use ctutils::{CtAssignSlice, CtEqSlice, CtSelectUsingCtAssign};
5
6use super::{FixedMontyForm, FixedMontyParams};
7use crate::{Choice, CtAssign, CtEq, OddUint, Uint};
8
9#[cfg(feature = "subtle")]
10use crate::CtSelect;
11
12/// Parameters for supporting efficient computations on integers in Montgomery form
13/// with a prime modulus.
14#[derive(Debug, Copy, Clone)]
15pub struct PrimeParams<const LIMBS: usize> {
16    /// The largest power of two that divides `(modulus - 1)`.
17    pub(super) s: NonZeroU32,
18    /// The result of dividing `modulus - 1` by `2^s`.
19    pub(super) t: OddUint<LIMBS>,
20    /// The smallest primitive root of the modulus.
21    pub(super) generator: NonZeroU32,
22    /// The exponent to use in computing a modular square root.
23    pub(super) sqrt_exp: Uint<LIMBS>,
24    /// An s'th root of unity for the modulus, in Montgomery form.
25    pub(super) monty_root_unity: Uint<LIMBS>,
26    /// Equal to `monty_root_unity^2 mod p`.
27    pub(super) monty_root_unity_p2: Uint<LIMBS>,
28}
29
30impl<const LIMBS: usize> PrimeParams<LIMBS> {
31    /// Instantiates a new set of [`PrimeParams`] given [`FixedMontyParams`] for a prime modulus.
32    ///
33    /// The value `generator` must be a multiplicative generator (ie. primitive element) of the
34    /// finite field, having order `modulus-1`. Its powers generate all nonzero elements of the
35    /// field: `generator^0, generator^1, ..., generator^(modulus-2)` enumerate `[1, modulus-1]`.
36    #[must_use]
37    #[allow(clippy::unwrap_in_result, clippy::missing_panics_doc)]
38    pub const fn new_vartime(params: &FixedMontyParams<LIMBS>, generator: u32) -> Self {
39        let p = params.modulus();
40        let p_minus_one = p.as_ref().set_bit_vartime(0, false);
41        let generator = NonZeroU32::new(generator).expect("invalid generator");
42        let s = NonZeroU32::new(p_minus_one.trailing_zeros_vartime()).expect("ensured non-zero");
43        let t = p
44            .as_ref()
45            .shr(s.get())
46            .to_odd()
47            .expect_copied("ensured odd");
48
49        // if s=1 and p is a power of a prime then -1 is always a root of unity
50        let (exp, root) = if s.get() == 1 {
51            // (p+1)/4
52            let exp = p.as_ref().shr_vartime(2).wrapping_add(&Uint::ONE);
53            let root = FixedMontyForm::new(&p_minus_one, params);
54            (exp, root)
55        } else {
56            // t = (p-1)/2^s
57            let t = p.as_ref().shr_vartime(s.get());
58            // exp = (t-1)/2
59            let exp = t.shr_vartime(1);
60            // the s'th root of unity is calculated as `generator^t`
61            let root =
62                FixedMontyForm::new(&Uint::from_u32(generator.get()), params).pow_vartime(&t);
63            // root^(2^(s-1)) must be equal to -1
64            let check = root.square_repeat_vartime(s.get() - 1);
65            assert!(
66                Uint::eq(&check.retrieve(), &p_minus_one).to_bool_vartime(),
67                "error calculating root of unity: invalid generator"
68            );
69            (exp, root)
70        };
71
72        Self {
73            s,
74            t,
75            generator,
76            sqrt_exp: exp,
77            monty_root_unity: root.to_montgomery(),
78            monty_root_unity_p2: root.square().to_montgomery(),
79        }
80    }
81
82    /// Get the constant 'generator' used in modular square root calculation.
83    #[must_use]
84    pub const fn generator(&self) -> NonZeroU32 {
85        self.generator
86    }
87
88    /// Get the constant 's' used in modular square root calculation.
89    #[must_use]
90    pub const fn s(&self) -> NonZeroU32 {
91        self.s
92    }
93
94    /// Get the constant 't' used in modular square root calculation.
95    #[must_use]
96    pub const fn t(&self) -> OddUint<LIMBS> {
97        self.t
98    }
99}
100
101impl<const LIMBS: usize> CtAssign for PrimeParams<LIMBS> {
102    fn ct_assign(&mut self, other: &Self, choice: Choice) {
103        self.s.ct_assign(&other.s, choice);
104        self.generator.ct_assign(&other.generator, choice);
105        self.sqrt_exp.ct_assign(&other.sqrt_exp, choice);
106        self.monty_root_unity
107            .ct_assign(&other.monty_root_unity, choice);
108        self.monty_root_unity_p2
109            .ct_assign(&other.monty_root_unity_p2, choice);
110    }
111}
112impl<const LIMBS: usize> CtAssignSlice for PrimeParams<LIMBS> {}
113impl<const LIMBS: usize> CtSelectUsingCtAssign for PrimeParams<LIMBS> {}
114
115impl<const LIMBS: usize> CtEq for PrimeParams<LIMBS> {
116    fn ct_eq(&self, other: &Self) -> Choice {
117        self.s.ct_eq(&other.s)
118            & self.generator.ct_eq(&other.generator)
119            & self.sqrt_exp.ct_eq(&other.sqrt_exp)
120            & self.monty_root_unity.ct_eq(&other.monty_root_unity)
121            & self.monty_root_unity_p2.ct_eq(&other.monty_root_unity_p2)
122    }
123}
124impl<const LIMBS: usize> CtEqSlice for PrimeParams<LIMBS> {}
125
126#[cfg(feature = "subtle")]
127impl<const LIMBS: usize> subtle::ConstantTimeEq for PrimeParams<LIMBS> {
128    fn ct_eq(&self, other: &Self) -> subtle::Choice {
129        CtEq::ct_eq(self, other).into()
130    }
131}
132
133#[cfg(feature = "subtle")]
134impl<const LIMBS: usize> subtle::ConditionallySelectable for PrimeParams<LIMBS> {
135    fn conditional_assign(&mut self, src: &Self, choice: subtle::Choice) {
136        self.ct_assign(src, choice.into());
137    }
138
139    fn conditional_select(a: &Self, b: &Self, choice: subtle::Choice) -> Self {
140        a.ct_select(b, choice.into())
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::PrimeParams;
147    use crate::{Choice, CtEq, CtSelect, Odd, U128, modular::MontyParams};
148
149    #[test]
150    fn check_expected() {
151        let monty_params =
152            MontyParams::new_vartime(Odd::<U128>::from_be_hex("e38af050d74b8567f73c8713cbc7bc47"));
153        let prime_params = PrimeParams::new_vartime(&monty_params, 5);
154        assert_eq!(prime_params.s.get(), 1);
155        assert_eq!(prime_params.generator.get(), 5);
156    }
157
158    #[should_panic]
159    #[test]
160    fn check_invalid_generator() {
161        let monty_params =
162            MontyParams::new_vartime(Odd::<U128>::from_be_hex("e38af050d74b8567f73c8713cbc7bc47"));
163        let _ = PrimeParams::new_vartime(&monty_params, 0);
164    }
165
166    #[should_panic]
167    #[test]
168    fn check_non_prime() {
169        let monty_params =
170            MontyParams::new_vartime(Odd::<U128>::from_be_hex("e38af050d74b8567f73c8713cbc7bc01"));
171        let _ = PrimeParams::new_vartime(&monty_params, 5);
172    }
173
174    #[test]
175    fn check_equality() {
176        let monty_params_1 =
177            MontyParams::new_vartime(Odd::<U128>::from_be_hex("e38af050d74b8567f73c8713cbc7bc47"));
178        let prime_params_1 = PrimeParams::new_vartime(&monty_params_1, 5);
179
180        let monty_params_2 =
181            MontyParams::new_vartime(Odd::<U128>::from_be_hex("f2799d643ab7ff983437c3a86cdb1beb"));
182        let prime_params_2 = PrimeParams::new_vartime(&monty_params_2, 5);
183
184        assert!(CtEq::ct_eq(&prime_params_1, &prime_params_1).to_bool_vartime());
185        #[cfg(feature = "subtle")]
186        assert!(bool::from(subtle::ConstantTimeEq::ct_eq(
187            &prime_params_1,
188            &prime_params_1
189        )));
190
191        assert!(CtEq::ct_ne(&prime_params_1, &prime_params_2).to_bool_vartime());
192        #[cfg(feature = "subtle")]
193        assert!(bool::from(subtle::ConstantTimeEq::ct_ne(
194            &prime_params_1,
195            &prime_params_2
196        )));
197
198        assert!(
199            CtEq::ct_eq(
200                &CtSelect::ct_select(&prime_params_1, &prime_params_2, Choice::FALSE),
201                &prime_params_1,
202            )
203            .to_bool_vartime()
204        );
205        #[cfg(feature = "subtle")]
206        assert!(
207            CtEq::ct_eq(
208                &subtle::ConditionallySelectable::conditional_select(
209                    &prime_params_1,
210                    &prime_params_2,
211                    subtle::Choice::from(0u8)
212                ),
213                &prime_params_1,
214            )
215            .to_bool_vartime()
216        );
217
218        assert!(
219            CtEq::ct_eq(
220                &CtSelect::ct_select(&prime_params_1, &prime_params_2, Choice::TRUE),
221                &prime_params_2,
222            )
223            .to_bool_vartime()
224        );
225        #[cfg(feature = "subtle")]
226        assert!(
227            CtEq::ct_eq(
228                &subtle::ConditionallySelectable::conditional_select(
229                    &prime_params_1,
230                    &prime_params_2,
231                    subtle::Choice::from(1u8)
232                ),
233                &prime_params_2,
234            )
235            .to_bool_vartime()
236        );
237    }
238}
crypto_bigint/modular/prime_params.rs

crypto_bigint/modular/
prime_params.rs
