crypto_bigint/uint/boxed/
invert_mod.rs

1//! [`BoxedUint`] modular inverse (i.e. reciprocal) operations.
2
3use crate::{
4    BoxedUint, Choice, CtEq, CtLt, CtOption, CtSelect, InvertMod, Limb, NonZero, Odd, U64, bitlen,
5    modular::safegcd, uint::invert_mod::expand_invert_mod2k,
6};
7
8impl BoxedUint {
9    /// Computes the multiplicative inverse of `self` mod `modulus`, where `modulus` is odd.
10    #[deprecated(since = "0.7.0", note = "please use `invert_odd_mod` instead")]
11    #[must_use]
12    pub fn inv_odd_mod(&self, modulus: &Odd<Self>) -> CtOption<Self> {
13        self.invert_odd_mod(modulus)
14    }
15
16    /// Computes the multiplicative inverse of `self` mod `modulus`, where `modulus` is odd.
17    #[must_use]
18    pub fn invert_odd_mod(&self, modulus: &Odd<Self>) -> CtOption<Self> {
19        safegcd::boxed::invert_odd_mod::<false>(self, modulus)
20    }
21
22    /// Computes the multiplicative inverse of `self` mod `modulus`, where `modulus` is odd.
23    #[must_use]
24    pub fn invert_odd_mod_vartime(&self, modulus: &Odd<Self>) -> CtOption<Self> {
25        safegcd::boxed::invert_odd_mod::<true>(self, modulus)
26    }
27
28    /// Computes 1/`self` mod `2^k`.
29    /// This method is constant-time w.r.t. `self` but not `k`.
30    ///
31    /// If the inverse does not exist (`k > 0` and `self` is even, or `k > bits_precision()`),
32    /// returns `Choice::FALSE` as the second element of the tuple, otherwise returns `Choice::TRUE`.
33    #[deprecated(since = "0.7.0", note = "please use `invert_mod2k_vartime` instead")]
34    #[must_use]
35    pub fn inv_mod2k_vartime(&self, k: u32) -> (Self, Choice) {
36        self.invert_mod2k_vartime(k)
37    }
38
39    /// Computes 1/`self` mod `2^k`.
40    /// This method is constant-time w.r.t. `self` but not `k`.
41    ///
42    /// If the inverse does not exist (`k > 0` and `self` is even, or `k > bits_precision()`),
43    /// returns `Choice::FALSE` as the second element of the tuple, otherwise returns `Choice::TRUE`.
44    #[must_use]
45    pub fn invert_mod2k_vartime(&self, k: u32) -> (Self, Choice) {
46        let bits = self.bits_precision();
47
48        if k == 0 {
49            (Self::zero_with_precision(bits), Choice::TRUE)
50        } else if k > bits {
51            (Self::zero_with_precision(bits), Choice::FALSE)
52        } else {
53            let (odd, is_some) = self.to_odd_or_one();
54            let inv = odd.invert_mod2k_vartime(k);
55            (inv, is_some)
56        }
57    }
58
59    /// Computes 1/`self` mod `2^k`.
60    ///
61    /// If the inverse does not exist (`k > 0` and `self` is even, or `k > bits_precision()`),
62    /// returns `Choice::FALSE` as the second element of the tuple, otherwise returns `Choice::TRUE`.
63    #[deprecated(since = "0.7.0", note = "please use `invert_mod2k` instead")]
64    #[must_use]
65    pub fn inv_mod2k(&self, k: u32) -> (Self, Choice) {
66        self.invert_mod2k(k)
67    }
68
69    /// Computes 1/`self` mod `2^k`.
70    ///
71    /// If the inverse does not exist (`k > 0` and `self` is even, or `k > bits_precision()`),
72    /// returns `Choice::FALSE` as the second element of the tuple, otherwise returns `Choice::TRUE`.
73    #[must_use]
74    pub fn invert_mod2k(&self, k: u32) -> (Self, Choice) {
75        let bits = self.bits_precision();
76        let (odd, is_odd) = self.to_odd_or_one();
77        let is_some = k.ct_lt(&(bits + 1)) & (k.ct_eq(&0) | is_odd);
78        let mut inv = odd.invert_mod_precision();
79        inv.restrict_bits(k);
80        (inv, is_some)
81    }
82
83    /// Computes the multiplicative inverse of `self` mod `modulus`
84    ///
85    /// `self` and `modulus` must have the same number of limbs, or the function will panic
86    ///
87    /// TODO: maybe some better documentation is needed
88    #[deprecated(since = "0.7.0", note = "please use `invert_mod` instead")]
89    #[must_use]
90    pub fn inv_mod(&self, modulus: &Self) -> CtOption<Self> {
91        let is_nz = modulus.is_nonzero();
92        let m = NonZero::new_unchecked(Self::ct_select(
93            &Self::one_with_precision(self.bits_precision()),
94            modulus,
95            is_nz,
96        ));
97        let inv_mod_s = self.invert_mod(&m);
98        let is_some = inv_mod_s.is_some();
99        let result =
100            Option::from(inv_mod_s).unwrap_or(Self::zero_with_precision(self.bits_precision()));
101        CtOption::new(result, is_some & is_nz)
102    }
103
104    /// Computes the multiplicative inverse of `self` mod `modulus`
105    ///
106    /// `self` and `modulus` must have the same number of limbs, or the function will panic
107    ///
108    /// TODO: maybe some better documentation is needed
109    #[must_use]
110    pub fn invert_mod(&self, modulus: &NonZero<Self>) -> CtOption<Self> {
111        debug_assert_eq!(self.bits_precision(), modulus.bits_precision());
112        let k = modulus.trailing_zeros();
113        let s = Odd::new_unchecked(modulus.shr(k));
114
115        let inv_mod_s = self.invert_odd_mod(&s);
116        let invertible_mod_s = inv_mod_s.is_some();
117        let inv_mod_s = inv_mod_s.unwrap_or(Self::zero_with_precision(self.bits_precision()));
118
119        let (inverse_mod2k, invertible_mod_2k) = self.invert_mod2k(k);
120        let is_some = invertible_mod_s & invertible_mod_2k;
121
122        let s_inverse_mod2k = s.invert_mod_precision();
123        let mut t = inverse_mod2k
124            .wrapping_sub(&inv_mod_s)
125            .wrapping_mul(&s_inverse_mod2k);
126        t.restrict_bits(k);
127        let result = inv_mod_s.wrapping_add(s.wrapping_mul(&t));
128
129        CtOption::new(result, is_some)
130    }
131}
132
133impl Odd<BoxedUint> {
134    /// Compute a full-width quadratic inversion, `self^-1 mod 2^bits_precision()`.
135    #[inline]
136    pub(crate) fn invert_mod_precision(&self) -> BoxedUint {
137        self.invert_mod2k_vartime(self.bits_precision())
138    }
139
140    /// Compute a quadratic inversion, `self^-1 mod 2^k` where `k <= bits_precision()`.
141    ///
142    /// This method is variable-time in `k` only.
143    pub(crate) fn invert_mod2k_vartime(&self, k: u32) -> BoxedUint {
144        let bits = self.bits_precision();
145        assert!(k <= bits);
146
147        let k_limbs = bitlen::to_limbs(k);
148        let inv_64 = U64::from_u64(self.as_uint_ref().invert_mod_u64());
149        let mut inv = BoxedUint::from_words_with_precision(*inv_64.as_words(), bits);
150
151        if k_limbs <= U64::LIMBS {
152            // trim to k_limbs
153            inv.as_mut_uint_ref().trailing_mut(k_limbs).fill(Limb::ZERO);
154        } else {
155            // expand to k_limbss
156            let mut scratch = BoxedUint::zero_with_precision(2 * bitlen::from_limbs(k_limbs));
157
158            expand_invert_mod2k(
159                self.as_uint_ref(),
160                inv.as_mut_uint_ref().leading_mut(k_limbs),
161                U64::LIMBS,
162                scratch.as_mut_uint_ref().split_at_mut(k_limbs),
163            );
164        }
165
166        // clear bits in the high limb if necessary
167        let k_bits = k & (Limb::BITS - 1);
168
169        if k_bits > 0 {
170            inv.limbs[k_limbs - 1] = inv.limbs[k_limbs - 1].restrict_bits(k_bits);
171        }
172
173        inv
174    }
175}
176
177impl InvertMod for BoxedUint {
178    type Output = Self;
179
180    fn invert_mod(&self, modulus: &NonZero<Self>) -> CtOption<Self> {
181        self.invert_mod(modulus)
182    }
183}
184
185#[cfg(test)]
186mod tests {
187    use crate::{Limb, NonZero, Odd, Resize, U256};
188
189    use super::BoxedUint;
190    use hex_literal::hex;
191    use num_bigint::BigUint;
192    use num_integer::Integer;
193
194    #[test]
195    fn invert_odd_mod_wider_modulus() {
196        let a = BoxedUint::from(2u64);
197        let modulus = Odd::new(BoxedUint::from(u128::MAX >> 1)).unwrap();
198        // 2 * 2^126 = modulus + 1.
199        let expected = BoxedUint::from(1u128 << 126);
200
201        assert!(a.bits_precision() < modulus.bits_precision());
202        assert_eq!(a.invert_odd_mod(&modulus).unwrap(), expected);
203    }
204
205    #[test]
206    fn invert_odd_mod_vartime_wider_modulus() {
207        let a = BoxedUint::from(2u64);
208        let modulus = Odd::new(BoxedUint::from(u128::MAX >> 1)).unwrap();
209        // 2 * 2^126 = modulus + 1.
210        let expected = BoxedUint::from(1u128 << 126);
211
212        assert!(a.bits_precision() < modulus.bits_precision());
213        assert_eq!(a.invert_odd_mod_vartime(&modulus).unwrap(), expected);
214    }
215
216    /// `invert_mod` at a precision where the safegcd iteration count overflowed `u32`
217    /// (`45907 * bits + 30179 > u32::MAX` from 93558 bits), with an even modulus so that
218    /// both the odd-modulus and the `2^k` paths are exercised.
219    #[test]
220    fn invert_mod_large_precision_even_modulus() {
221        const BITS: u32 = 93_568;
222        let mut bytes: alloc::vec::Vec<u8> = (0..BITS >> 3)
223            .map(|i| {
224                let h = (i ^ 0xDA94_2042).wrapping_mul(0x85EB_CA6B);
225                let h = (h ^ (h >> 13)).wrapping_mul(0xC2B2_AE35);
226                (h ^ (h >> 16)).to_le_bytes()[0]
227            })
228            .collect();
229        bytes[0] |= 0x80;
230        *bytes.last_mut().unwrap() &= !1;
231        let m = BoxedUint::from_be_slice(&bytes, BITS).unwrap();
232        let a = BoxedUint::from(65537u32).resize(BITS);
233
234        let to_big = |x: &BoxedUint| BigUint::from_bytes_be(&x.to_be_bytes());
235        assert_eq!(to_big(&a).gcd(&to_big(&m)), BigUint::from(1u32));
236
237        let inv = a.invert_mod(&NonZero::new(m.clone()).unwrap()).unwrap();
238        assert_eq!(
239            (to_big(&a) * to_big(&inv)) % to_big(&m),
240            BigUint::from(1u32)
241        );
242    }
243
244    #[test]
245    fn invert_mod2k() {
246        let v = BoxedUint::from_be_slice(
247            &hex!("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"),
248            256,
249        )
250        .unwrap();
251        let e = BoxedUint::from_be_slice(
252            &hex!("3642e6faeaac7c6663b93d3d6a0d489e434ddc0123db5fa627c7f6e22ddacacf"),
253            256,
254        )
255        .unwrap();
256        let (a, is_some) = v.invert_mod2k(256);
257        assert_eq!(e, a);
258        assert!(bool::from(is_some));
259
260        let v = BoxedUint::from_be_slice(
261            &hex!("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141"),
262            256,
263        )
264        .unwrap();
265        let e = BoxedUint::from_be_slice(
266            &hex!("261776f29b6b106c7680cf3ed83054a1af5ae537cb4613dbb4f20099aa774ec1"),
267            256,
268        )
269        .unwrap();
270        let (a, is_some) = v.invert_mod2k(256);
271        assert_eq!(e, a);
272        assert!(bool::from(is_some));
273    }
274
275    #[test]
276    fn inv_odd() {
277        let a = BoxedUint::from_be_hex(
278            concat![
279                "000225E99153B467A5B451979A3F451DAEF3BF8D6C6521D2FA24BBB17F29544E",
280                "347A412B065B75A351EA9719E2430D2477B11CC9CF9C1AD6EDEE26CB15F463F8",
281                "BCC72EF87EA30288E95A48AA792226CEC959DCB0672D8F9D80A54CBBEA85CAD8",
282                "382EC224DEB2F5784E62D0CC2F81C2E6AD14EBABE646D6764B30C32B87688985"
283            ],
284            1024,
285        )
286        .unwrap();
287        let m = BoxedUint::from_be_hex(
288            concat![
289                "D509E7854ABDC81921F669F1DC6F61359523F3949803E58ED4EA8BC16483DC6F",
290                "37BFE27A9AC9EEA2969B357ABC5C0EE214BE16A7D4C58FC620D5B5A20AFF001A",
291                "D198D3155E5799DC4EA76652D64983A7E130B5EACEBAC768D28D589C36EC749C",
292                "558D0B64E37CD0775C0D0104AE7D98BA23C815185DD43CD8B16292FD94156767"
293            ],
294            1024,
295        )
296        .unwrap()
297        .to_odd()
298        .unwrap();
299        let expected = BoxedUint::from_be_hex(
300            concat![
301                "B03623284B0EBABCABD5C5881893320281460C0A8E7BF4BFDCFFCBCCBF436A55",
302                "D364235C8171E46C7D21AAD0680676E57274A8FDA6D12768EF961CACDD2DAE57",
303                "88D93DA5EB8EDC391EE3726CDCF4613C539F7D23E8702200CB31B5ED5B06E5CA",
304                "3E520968399B4017BF98A864FABA2B647EFC4998B56774D4F2CB026BC024A336"
305            ],
306            1024,
307        )
308        .unwrap();
309        assert_eq!(a.invert_odd_mod(&m).unwrap(), expected);
310
311        assert_eq!(a.invert_mod(m.as_nz_ref()).unwrap(), expected);
312    }
313
314    #[test]
315    fn test_invert_odd_no_inverse() {
316        // 2^128 - 159, a prime
317        let p1 = BoxedUint::from_be_hex(
318            "00000000000000000000000000000000ffffffffffffffffffffffffffffff61",
319            256,
320        )
321        .unwrap();
322        // 2^128 - 173, a prime
323        let p2 = BoxedUint::from_be_hex(
324            "00000000000000000000000000000000ffffffffffffffffffffffffffffff53",
325            256,
326        )
327        .unwrap();
328
329        let m = p1.wrapping_mul(&p2).to_odd().unwrap();
330
331        // `m` is a multiple of `p1`, so no inverse exists
332        let res = p1.invert_odd_mod(&m);
333        let is_none: bool = res.is_none().into();
334        assert!(is_none);
335    }
336
337    #[test]
338    fn test_invert_even() {
339        let a = BoxedUint::from_be_hex(
340            concat![
341                "000225E99153B467A5B451979A3F451DAEF3BF8D6C6521D2FA24BBB17F29544E",
342                "347A412B065B75A351EA9719E2430D2477B11CC9CF9C1AD6EDEE26CB15F463F8",
343                "BCC72EF87EA30288E95A48AA792226CEC959DCB0672D8F9D80A54CBBEA85CAD8",
344                "382EC224DEB2F5784E62D0CC2F81C2E6AD14EBABE646D6764B30C32B87688985"
345            ],
346            1024,
347        )
348        .unwrap();
349        let m = BoxedUint::from_be_hex(
350            concat![
351                "D509E7854ABDC81921F669F1DC6F61359523F3949803E58ED4EA8BC16483DC6F",
352                "37BFE27A9AC9EEA2969B357ABC5C0EE214BE16A7D4C58FC620D5B5A20AFF001A",
353                "D198D3155E5799DC4EA76652D64983A7E130B5EACEBAC768D28D589C36EC749C",
354                "558D0B64E37CD0775C0D0104AE7D98BA23C815185DD43CD8B16292FD94156000"
355            ],
356            1024,
357        )
358        .unwrap()
359        .to_nz()
360        .unwrap();
361        let expected = BoxedUint::from_be_hex(
362            concat![
363                "1EBF391306817E1BC610E213F4453AD70911CCBD59A901B2A468A4FC1D64F357",
364                "DBFC6381EC5635CAA664DF280028AF4651482C77A143DF38D6BFD4D64B6C0225",
365                "FC0E199B15A64966FB26D88A86AD144271F6BDCD3D63193AB2B3CC53B99F21A3",
366                "5B9BFAE5D43C6BC6E7A9856C71C7318C76530E9E5AE35882D5ABB02F1696874D",
367            ],
368            1024,
369        )
370        .unwrap();
371
372        let res = a.invert_mod(&m).unwrap();
373        assert_eq!(res, expected);
374    }
375
376    #[test]
377    fn test_invert_small() {
378        let a = BoxedUint::from(3u64);
379        let m = BoxedUint::from(13u64).to_odd().unwrap();
380
381        let res = a.invert_odd_mod(&m).unwrap();
382        assert_eq!(BoxedUint::from(9u64), res);
383    }
384
385    #[test]
386    fn test_no_inverse_small() {
387        let a = BoxedUint::from(14u64);
388        let m = BoxedUint::from(49u64).to_odd().unwrap();
389
390        let res = a.invert_odd_mod(&m);
391        let is_none: bool = res.is_none().into();
392        assert!(is_none);
393    }
394
395    #[test]
396    fn test_invert_edge() {
397        assert!(bool::from(
398            BoxedUint::zero()
399                .invert_odd_mod(&BoxedUint::one().to_odd().unwrap())
400                .is_none()
401        ));
402        assert_eq!(
403            BoxedUint::one()
404                .invert_odd_mod(&BoxedUint::one().to_odd().unwrap())
405                .unwrap(),
406            BoxedUint::zero()
407        );
408        assert_eq!(
409            BoxedUint::one()
410                .invert_odd_mod(&BoxedUint::from(U256::MAX).to_odd().unwrap())
411                .unwrap(),
412            BoxedUint::one()
413        );
414        assert!(bool::from(
415            BoxedUint::from(U256::MAX)
416                .invert_odd_mod(&BoxedUint::from(U256::MAX).to_odd().unwrap())
417                .is_none()
418        ));
419    }
420
421    #[test]
422    fn invert_mod_precision() {
423        const PRECISION: u32 = 8 * Limb::BITS;
424
425        for limbs in 1..10 {
426            let a = Odd::new_unchecked(BoxedUint::max(PRECISION).resize_unchecked(limbs));
427            let a_inv = a.invert_mod_precision();
428            assert_eq!(a.as_ref().wrapping_mul(&a_inv), BoxedUint::one());
429        }
430    }
431}
crypto_bigint/uint/boxed/invert_mod.rs

crypto_bigint/uint/boxed/
invert_mod.rs
