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        // t = (p-1)/2^s
44        let t = p
45            .as_ref()
46            .shr_vartime(s.get())
47            .to_odd()
48            .expect_copied("ensured odd");
49
50        // if s=1 and p is a power of a prime then -1 is always a root of unity
51        let (exp, root) = if s.get() == 1 {
52            // (p+1)/4
53            let exp = p.as_ref().shr_vartime(2).wrapping_add(&Uint::ONE);
54            let root = FixedMontyForm::new(&p_minus_one, params);
55            (exp, root)
56        } else {
57            // exp = (t-1)/2
58            let exp = t.as_ref().shr_vartime(1);
59            // the s'th root of unity is calculated as `generator^t`
60            let root = FixedMontyForm::new(&Uint::from_u32(generator.get()), params)
61                .pow_vartime(t.as_ref());
62            // root^(2^(s-1)) must be equal to -1
63            let check = root.square_repeat_vartime(s.get() - 1);
64            assert!(
65                Uint::eq(&check.retrieve(), &p_minus_one).to_bool(),
66                "error calculating root of unity: invalid generator"
67            );
68            (exp, root)
69        };
70
71        Self {
72            s,
73            t,
74            generator,
75            sqrt_exp: exp,
76            monty_root_unity: root.to_montgomery(),
77            monty_root_unity_p2: root.square().to_montgomery(),
78        }
79    }
80
81    /// Get the constant 'generator' used in modular square root calculation.
82    #[must_use]
83    pub const fn generator(&self) -> NonZeroU32 {
84        self.generator
85    }
86
87    /// Get the constant 's' used in modular square root calculation.
88    #[must_use]
89    pub const fn s(&self) -> NonZeroU32 {
90        self.s
91    }
92
93    /// Get the constant 't' used in modular square root calculation.
94    #[must_use]
95    pub const fn t(&self) -> OddUint<LIMBS> {
96        self.t
97    }
98}
99
100impl<const LIMBS: usize> CtAssign for PrimeParams<LIMBS> {
101    fn ct_assign(&mut self, other: &Self, choice: Choice) {
102        self.s.ct_assign(&other.s, choice);
103        self.generator.ct_assign(&other.generator, choice);
104        self.sqrt_exp.ct_assign(&other.sqrt_exp, choice);
105        self.monty_root_unity
106            .ct_assign(&other.monty_root_unity, choice);
107        self.monty_root_unity_p2
108            .ct_assign(&other.monty_root_unity_p2, choice);
109    }
110}
111impl<const LIMBS: usize> CtAssignSlice for PrimeParams<LIMBS> {}
112impl<const LIMBS: usize> CtSelectUsingCtAssign for PrimeParams<LIMBS> {}
113
114impl<const LIMBS: usize> CtEq for PrimeParams<LIMBS> {
115    fn ct_eq(&self, other: &Self) -> Choice {
116        self.s.ct_eq(&other.s)
117            & self.generator.ct_eq(&other.generator)
118            & self.sqrt_exp.ct_eq(&other.sqrt_exp)
119            & self.monty_root_unity.ct_eq(&other.monty_root_unity)
120            & self.monty_root_unity_p2.ct_eq(&other.monty_root_unity_p2)
121    }
122}
123impl<const LIMBS: usize> CtEqSlice for PrimeParams<LIMBS> {}
124
125#[cfg(feature = "subtle")]
126impl<const LIMBS: usize> subtle::ConstantTimeEq for PrimeParams<LIMBS> {
127    fn ct_eq(&self, other: &Self) -> subtle::Choice {
128        CtEq::ct_eq(self, other).into()
129    }
130}
131
132#[cfg(feature = "subtle")]
133impl<const LIMBS: usize> subtle::ConditionallySelectable for PrimeParams<LIMBS> {
134    fn conditional_assign(&mut self, src: &Self, choice: subtle::Choice) {
135        self.ct_assign(src, choice.into());
136    }
137
138    fn conditional_select(a: &Self, b: &Self, choice: subtle::Choice) -> Self {
139        a.ct_select(b, choice.into())
140    }
141}
142
143#[cfg(test)]
144mod tests {
145    use super::PrimeParams;
146    use crate::{Choice, CtEq, CtSelect, Odd, U128, modular::MontyParams};
147
148    #[test]
149    fn check_expected() {
150        let monty_params =
151            MontyParams::new_vartime(Odd::<U128>::from_be_hex("e38af050d74b8567f73c8713cbc7bc47"));
152        let prime_params = PrimeParams::new_vartime(&monty_params, 5);
153        assert_eq!(prime_params.s.get(), 1);
154        assert_eq!(prime_params.generator.get(), 5);
155    }
156
157    #[should_panic]
158    #[test]
159    fn check_invalid_generator() {
160        let monty_params =
161            MontyParams::new_vartime(Odd::<U128>::from_be_hex("e38af050d74b8567f73c8713cbc7bc47"));
162        let _ = PrimeParams::new_vartime(&monty_params, 0);
163    }
164
165    #[should_panic]
166    #[test]
167    fn check_non_prime() {
168        let monty_params =
169            MontyParams::new_vartime(Odd::<U128>::from_be_hex("e38af050d74b8567f73c8713cbc7bc01"));
170        let _ = PrimeParams::new_vartime(&monty_params, 5);
171    }
172
173    #[test]
174    fn check_equality() {
175        let monty_params_1 =
176            MontyParams::new_vartime(Odd::<U128>::from_be_hex("e38af050d74b8567f73c8713cbc7bc47"));
177        let prime_params_1 = PrimeParams::new_vartime(&monty_params_1, 5);
178
179        let monty_params_2 =
180            MontyParams::new_vartime(Odd::<U128>::from_be_hex("f2799d643ab7ff983437c3a86cdb1beb"));
181        let prime_params_2 = PrimeParams::new_vartime(&monty_params_2, 5);
182
183        assert!(CtEq::ct_eq(&prime_params_1, &prime_params_1).to_bool());
184        #[cfg(feature = "subtle")]
185        assert!(bool::from(subtle::ConstantTimeEq::ct_eq(
186            &prime_params_1,
187            &prime_params_1
188        )));
189
190        assert!(CtEq::ct_ne(&prime_params_1, &prime_params_2).to_bool());
191        #[cfg(feature = "subtle")]
192        assert!(bool::from(subtle::ConstantTimeEq::ct_ne(
193            &prime_params_1,
194            &prime_params_2
195        )));
196
197        assert!(
198            CtEq::ct_eq(
199                &CtSelect::ct_select(&prime_params_1, &prime_params_2, Choice::FALSE),
200                &prime_params_1,
201            )
202            .to_bool()
203        );
204        #[cfg(feature = "subtle")]
205        assert!(
206            CtEq::ct_eq(
207                &subtle::ConditionallySelectable::conditional_select(
208                    &prime_params_1,
209                    &prime_params_2,
210                    subtle::Choice::from(0u8)
211                ),
212                &prime_params_1,
213            )
214            .to_bool()
215        );
216
217        assert!(
218            CtEq::ct_eq(
219                &CtSelect::ct_select(&prime_params_1, &prime_params_2, Choice::TRUE),
220                &prime_params_2,
221            )
222            .to_bool()
223        );
224        #[cfg(feature = "subtle")]
225        assert!(
226            CtEq::ct_eq(
227                &subtle::ConditionallySelectable::conditional_select(
228                    &prime_params_1,
229                    &prime_params_2,
230                    subtle::Choice::from(1u8)
231                ),
232                &prime_params_2,
233            )
234            .to_bool()
235        );
236    }
237}
crypto_bigint/modular/prime_params.rs

crypto_bigint/modular/
prime_params.rs
