primefield/macros/
fiat.rs

1//! Macros for generating wrappers for `fiat-crypto` synthesized field implementations, currently
2//! specialized to support `word-by-word-montgomery` implementations.
3
4/// Add `fiat-crypto` synthesized arithmetic impls to the given field element.
5///
6/// This macro wraps a field implementation generated by the `word-by-word-montgomery` backend
7/// (other field implementations are not supported) and uses it in conjunction with this crate's
8/// `MontyField` type as the internal representation.
9#[macro_export]
10macro_rules! fiat_monty_field_arithmetic {
11    (
12        name: $fe:tt,
13        params: $params:ty,
14        uint: $uint:ty,
15        non_mont: $non_mont_type:expr,
16        mont: $mont_type:expr,
17        from_mont: $from_mont:ident,
18        to_mont: $to_mont:ident,
19        add: $add:ident,
20        sub: $sub:ident,
21        mul: $mul:ident,
22        neg: $neg:ident,
23        square: $square:ident,
24        divstep_precomp: $divstep_precomp:ident,
25        divstep: $divstep:ident,
26        msat: $msat:ident,
27        selectnz: $selectznz:ident
28    ) => {
29        impl $fe {
30            /// Decode [`
31            #[doc = stringify!($fe)]
32            /// `] from [`
33            #[doc = stringify!($uint)]
34            /// `] converting it into Montgomery form.
35            ///
36            /// Does *not* perform a check that the field element does not overflow the order.
37            ///
38            /// Used incorrectly this can lead to invalid results!
39            #[inline]
40            pub(crate) const fn from_uint_unchecked(w: $uint) -> Self {
41                let mut out = $mont_type([0; <$uint>::LIMBS]);
42                $to_mont(&mut out, &$non_mont_type(w.to_words()));
43                Self(
44                    $crate::MontyFieldElement::<$params, { <$uint>::LIMBS }>::from_montgomery_words(
45                        out.0,
46                    ),
47                )
48            }
49
50            /// Translate [`
51            #[doc = stringify!($fe)]
52            /// `] out of the Montgomery domain, returning a [`
53            #[doc = stringify!($uint)]
54            /// `] in canonical form.
55            #[inline]
56            pub const fn to_canonical(self) -> $uint {
57                let mut out = $non_mont_type([0; <$uint>::LIMBS]);
58                $from_mont(&mut out, &$mont_type(self.0.to_montgomery_words()));
59                <$uint>::from_words(out.0)
60            }
61
62            /// Add elements.
63            #[inline]
64            pub const fn add(&self, rhs: &Self) -> Self {
65                let mut out = $mont_type([0; <$uint>::LIMBS]);
66                $add(
67                    &mut out,
68                    &$mont_type(self.0.to_montgomery_words()),
69                    &$mont_type(rhs.0.to_montgomery_words()),
70                );
71                Self(
72                    $crate::MontyFieldElement::<$params, { <$uint>::LIMBS }>::from_montgomery_words(
73                        out.0,
74                    ),
75                )
76            }
77
78            /// Double element (add it to itself).
79            #[inline]
80            #[must_use]
81            pub const fn double(&self) -> Self {
82                self.add(self)
83            }
84
85            /// Subtract elements.
86            #[inline]
87            pub const fn sub(&self, rhs: &Self) -> Self {
88                let mut out = $mont_type([0; <$uint>::LIMBS]);
89                $sub(
90                    &mut out,
91                    &$mont_type(self.0.to_montgomery_words()),
92                    &$mont_type(rhs.0.to_montgomery_words()),
93                );
94                Self(
95                    $crate::MontyFieldElement::<$params, { <$uint>::LIMBS }>::from_montgomery_words(
96                        out.0,
97                    ),
98                )
99            }
100
101            /// Multiply elements.
102            #[inline]
103            pub const fn multiply(&self, rhs: &Self) -> Self {
104                let mut out = $mont_type([0; <$uint>::LIMBS]);
105                $mul(
106                    &mut out,
107                    &$mont_type(self.0.to_montgomery_words()),
108                    &$mont_type(rhs.0.to_montgomery_words()),
109                );
110                Self(
111                    $crate::MontyFieldElement::<$params, { <$uint>::LIMBS }>::from_montgomery_words(
112                        out.0,
113                    ),
114                )
115            }
116
117            /// Negate element.
118            #[inline]
119            pub const fn neg(&self) -> Self {
120                let mut out = $mont_type([0; <$uint>::LIMBS]);
121                $neg(&mut out, &$mont_type(self.0.to_montgomery_words()));
122                Self(
123                    $crate::MontyFieldElement::<$params, { <$uint>::LIMBS }>::from_montgomery_words(
124                        out.0,
125                    ),
126                )
127            }
128
129            /// Compute modular square.
130            #[inline]
131            #[must_use]
132            pub const fn square(&self) -> Self {
133                let mut out = $mont_type([0; <$uint>::LIMBS]);
134                $square(&mut out, &$mont_type(self.0.to_montgomery_words()));
135                Self(
136                    $crate::MontyFieldElement::<$params, { <$uint>::LIMBS }>::from_montgomery_words(
137                        out.0,
138                    ),
139                )
140            }
141
142            /// Compute
143            #[doc = stringify!($fe)]
144            /// inversion: `1 / self`.
145            #[inline]
146            pub fn invert(&self) -> $crate::subtle::CtOption<Self> {
147                $crate::subtle::CtOption::new(self.invert_unchecked(), !self.is_zero())
148            }
149
150            /// Compute field inversion as a `const fn`. Panics if `self` is zero.
151            ///
152            /// This is mainly intended for inverting constants at compile time.
153            pub const fn const_invert(&self) -> Self {
154                assert!(
155                    !self.0.as_montgomery().cmp_vartime(&<$uint>::ZERO).is_eq(),
156                    "input to invert should be non-zero"
157                );
158                self.invert_unchecked()
159            }
160
161            /// Returns the multiplicative inverse of self.
162            ///
163            /// Does not check that self is non-zero.
164            const fn invert_unchecked(&self) -> Self {
165                let words = $crate::fiat_bernstein_yang_invert!(
166                    a: &$mont_type(self.0.to_montgomery_words()),
167                    one: &$mont_type(Self::ONE.0.to_montgomery_words()),
168                    d: <$fe as $crate::ff::PrimeField>::NUM_BITS as usize,
169                    nlimbs: <$uint>::LIMBS,
170                    word: $crate::bigint::Word,
171                    non_mont: $non_mont_type,
172                    mont: $mont_type,
173                    from_mont: $from_mont,
174                    mul: $mul,
175                    neg: $neg,
176                    divstep_precomp: $divstep_precomp,
177                    divstep: $divstep,
178                    msat: $msat,
179                    selectnz: $selectznz
180                );
181
182                Self(
183                    $crate::MontyFieldElement::<$params, { <$uint>::LIMBS }>::from_montgomery_words(
184                        words,
185                    ),
186                )
187            }
188        }
189    };
190}
191
192/// Emit wrapper function for a `fiat-crypto` generated implementation of the Bernstein-Yang
193/// (a.k.a. safegcd) modular inversion algorithm.
194#[macro_export]
195macro_rules! fiat_bernstein_yang_invert {
196    (
197        a: $a:expr,
198        one: $one:expr,
199        d: $d:expr,
200        nlimbs: $nlimbs:expr,
201        word: $word:ty,
202        non_mont: $non_mont_type: expr,
203        mont: $mont_type: expr,
204        from_mont: $from_mont:ident,
205        mul: $mul:ident,
206        neg: $neg:ident,
207        divstep_precomp: $divstep_precomp:ident,
208        divstep: $divstep:ident,
209        msat: $msat:ident,
210        selectnz: $selectznz:ident
211    ) => {{
212        // See Bernstein-Yang 2019 p.366
213        const ITERATIONS: usize = (49 * $d + 57) / 17;
214
215        let mut a = $non_mont_type([0; $nlimbs]);
216        $from_mont(&mut a, $a);
217        let mut d = 1;
218        let mut f = [0; $nlimbs + 1];
219        $msat(&mut f);
220        let mut g = [0; $nlimbs + 1];
221        let mut v = [0; $nlimbs];
222        let mut r = $one.0;
223        let mut i = 0;
224        let mut j = 0;
225
226        while j < $nlimbs {
227            g[j] = a.0[j];
228            j += 1;
229        }
230
231        while i < ITERATIONS - ITERATIONS % 2 {
232            let mut out1 = 0;
233            let mut out2 = [0; $nlimbs + 1];
234            let mut out3 = [0; $nlimbs + 1];
235            let mut out4 = [0; $nlimbs];
236            let mut out5 = [0; $nlimbs];
237
238            $divstep(
239                &mut out1, &mut out2, &mut out3, &mut out4, &mut out5, d, &f, &g, &v, &r,
240            );
241            $divstep(
242                &mut d, &mut f, &mut g, &mut v, &mut r, out1, &out2, &out3, &out4, &out5,
243            );
244            i += 2;
245        }
246
247        if ITERATIONS % 2 != 0 {
248            let mut out1 = 0;
249            let mut out2 = [0; $nlimbs + 1];
250            let mut out3 = [0; $nlimbs + 1];
251            let mut out4 = [0; $nlimbs];
252            let mut out5 = [0; $nlimbs];
253            $divstep(
254                &mut out1, &mut out2, &mut out3, &mut out4, &mut out5, d, &f, &g, &v, &r,
255            );
256            f = out2;
257            v = out4;
258        }
259
260        let s = ((f[f.len() - 1] >> <$word>::BITS - 1) & 1) as u8;
261        let mut neg_v = $mont_type([0; $nlimbs]);
262        $neg(&mut neg_v, &$mont_type(v));
263
264        let mut v2 = $mont_type([0; $nlimbs]);
265        $selectznz(&mut v2.0, s, &v, &neg_v.0);
266
267        let mut precomp = $mont_type([0; $nlimbs]);
268        $divstep_precomp(&mut precomp.0);
269
270        let mut out = $mont_type([0; $nlimbs]);
271        $mul(&mut out, &v2, &precomp);
272        out.0
273    }};
274}
275
276/// Test that the wrapper generated for a `word-by-word-montgomery` fiat-crypto implementation
277/// matches the internal representation used by `MontyField*`, e.g. do they have the same saturated
278/// modulus representation and agree on the value of `R`.
279///
280/// If these tests do not pass, the `fiat-crypto` synthesized implementation is incompatible with
281/// `MontyField*`.
282///
283/// See also: mit-plv/fiat-crypto#2166
284#[macro_export]
285macro_rules! test_fiat_monty_field_arithmetic {
286    (
287        name: $fe:tt,
288        params: $params:ty,
289        uint: $uint:ty,
290        non_mont: $non_mont_type:expr,
291        mont: $mont_type:expr,
292        to_mont: $to_mont:ident,
293        msat: $msat:ident
294    ) => {
295        use $crate::bigint::modular::ConstMontyParams as _;
296
297        /// Compute `fiat-crypto`'s selection of `R` by converting `1` into Montgomery form using
298        /// `$to_mont`, and then compare it to `ConstMontyParams::PARAMS.one()` as computed by
299        /// `crypto_bigint::modular` to ensure they're equal.
300        #[test]
301        fn fiat_montgomery_r_constant() {
302            let mut one = $non_mont_type([0; <$uint>::LIMBS]);
303            one[0] = 1;
304
305            let mut R = $mont_type([0; <$uint>::LIMBS]);
306            $to_mont(&mut R, &one);
307
308            assert_eq!(<$params>::PARAMS.one().as_words(), &R.0)
309        }
310
311        /// Compute `fiat-crypto`'s saturated modulus representation using `$msat`, and then compare
312        /// it to `ConstMontyParams::PARAMS.modulus()` as computed by `crypto_bigint::modular`
313        /// to ensure they're equal.
314        #[test]
315        fn fiat_msat_constant() {
316            use $crate::bigint::Word;
317
318            let mut out = [0 as Word; <$uint>::LIMBS + 1];
319            $msat(&mut out);
320            assert_eq!(out[<$uint>::LIMBS], 0);
321            assert_eq!(
322                <$params>::PARAMS.modulus().as_words(),
323                &out[..<$uint>::LIMBS]
324            );
325        }
326    };
327}
primefield/macros/fiat.rs

primefield/macros/
fiat.rs
