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, Odd, Resize, U256};
188
189    use super::BoxedUint;
190    use hex_literal::hex;
191
192    #[test]
193    fn invert_mod2k() {
194        let v = BoxedUint::from_be_slice(
195            &hex!("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"),
196            256,
197        )
198        .unwrap();
199        let e = BoxedUint::from_be_slice(
200            &hex!("3642e6faeaac7c6663b93d3d6a0d489e434ddc0123db5fa627c7f6e22ddacacf"),
201            256,
202        )
203        .unwrap();
204        let (a, is_some) = v.invert_mod2k(256);
205        assert_eq!(e, a);
206        assert!(bool::from(is_some));
207
208        let v = BoxedUint::from_be_slice(
209            &hex!("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141"),
210            256,
211        )
212        .unwrap();
213        let e = BoxedUint::from_be_slice(
214            &hex!("261776f29b6b106c7680cf3ed83054a1af5ae537cb4613dbb4f20099aa774ec1"),
215            256,
216        )
217        .unwrap();
218        let (a, is_some) = v.invert_mod2k(256);
219        assert_eq!(e, a);
220        assert!(bool::from(is_some));
221    }
222
223    #[test]
224    fn inv_odd() {
225        let a = BoxedUint::from_be_hex(
226            concat![
227                "000225E99153B467A5B451979A3F451DAEF3BF8D6C6521D2FA24BBB17F29544E",
228                "347A412B065B75A351EA9719E2430D2477B11CC9CF9C1AD6EDEE26CB15F463F8",
229                "BCC72EF87EA30288E95A48AA792226CEC959DCB0672D8F9D80A54CBBEA85CAD8",
230                "382EC224DEB2F5784E62D0CC2F81C2E6AD14EBABE646D6764B30C32B87688985"
231            ],
232            1024,
233        )
234        .unwrap();
235        let m = BoxedUint::from_be_hex(
236            concat![
237                "D509E7854ABDC81921F669F1DC6F61359523F3949803E58ED4EA8BC16483DC6F",
238                "37BFE27A9AC9EEA2969B357ABC5C0EE214BE16A7D4C58FC620D5B5A20AFF001A",
239                "D198D3155E5799DC4EA76652D64983A7E130B5EACEBAC768D28D589C36EC749C",
240                "558D0B64E37CD0775C0D0104AE7D98BA23C815185DD43CD8B16292FD94156767"
241            ],
242            1024,
243        )
244        .unwrap()
245        .to_odd()
246        .unwrap();
247        let expected = BoxedUint::from_be_hex(
248            concat![
249                "B03623284B0EBABCABD5C5881893320281460C0A8E7BF4BFDCFFCBCCBF436A55",
250                "D364235C8171E46C7D21AAD0680676E57274A8FDA6D12768EF961CACDD2DAE57",
251                "88D93DA5EB8EDC391EE3726CDCF4613C539F7D23E8702200CB31B5ED5B06E5CA",
252                "3E520968399B4017BF98A864FABA2B647EFC4998B56774D4F2CB026BC024A336"
253            ],
254            1024,
255        )
256        .unwrap();
257        assert_eq!(a.invert_odd_mod(&m).unwrap(), expected);
258
259        assert_eq!(a.invert_mod(m.as_nz_ref()).unwrap(), expected);
260    }
261
262    #[test]
263    fn test_invert_odd_no_inverse() {
264        // 2^128 - 159, a prime
265        let p1 = BoxedUint::from_be_hex(
266            "00000000000000000000000000000000ffffffffffffffffffffffffffffff61",
267            256,
268        )
269        .unwrap();
270        // 2^128 - 173, a prime
271        let p2 = BoxedUint::from_be_hex(
272            "00000000000000000000000000000000ffffffffffffffffffffffffffffff53",
273            256,
274        )
275        .unwrap();
276
277        let m = p1.wrapping_mul(&p2).to_odd().unwrap();
278
279        // `m` is a multiple of `p1`, so no inverse exists
280        let res = p1.invert_odd_mod(&m);
281        let is_none: bool = res.is_none().into();
282        assert!(is_none);
283    }
284
285    #[test]
286    fn test_invert_even() {
287        let a = BoxedUint::from_be_hex(
288            concat![
289                "000225E99153B467A5B451979A3F451DAEF3BF8D6C6521D2FA24BBB17F29544E",
290                "347A412B065B75A351EA9719E2430D2477B11CC9CF9C1AD6EDEE26CB15F463F8",
291                "BCC72EF87EA30288E95A48AA792226CEC959DCB0672D8F9D80A54CBBEA85CAD8",
292                "382EC224DEB2F5784E62D0CC2F81C2E6AD14EBABE646D6764B30C32B87688985"
293            ],
294            1024,
295        )
296        .unwrap();
297        let m = BoxedUint::from_be_hex(
298            concat![
299                "D509E7854ABDC81921F669F1DC6F61359523F3949803E58ED4EA8BC16483DC6F",
300                "37BFE27A9AC9EEA2969B357ABC5C0EE214BE16A7D4C58FC620D5B5A20AFF001A",
301                "D198D3155E5799DC4EA76652D64983A7E130B5EACEBAC768D28D589C36EC749C",
302                "558D0B64E37CD0775C0D0104AE7D98BA23C815185DD43CD8B16292FD94156000"
303            ],
304            1024,
305        )
306        .unwrap()
307        .to_nz()
308        .unwrap();
309        let expected = BoxedUint::from_be_hex(
310            concat![
311                "1EBF391306817E1BC610E213F4453AD70911CCBD59A901B2A468A4FC1D64F357",
312                "DBFC6381EC5635CAA664DF280028AF4651482C77A143DF38D6BFD4D64B6C0225",
313                "FC0E199B15A64966FB26D88A86AD144271F6BDCD3D63193AB2B3CC53B99F21A3",
314                "5B9BFAE5D43C6BC6E7A9856C71C7318C76530E9E5AE35882D5ABB02F1696874D",
315            ],
316            1024,
317        )
318        .unwrap();
319
320        let res = a.invert_mod(&m).unwrap();
321        assert_eq!(res, expected);
322    }
323
324    #[test]
325    fn test_invert_small() {
326        let a = BoxedUint::from(3u64);
327        let m = BoxedUint::from(13u64).to_odd().unwrap();
328
329        let res = a.invert_odd_mod(&m).unwrap();
330        assert_eq!(BoxedUint::from(9u64), res);
331    }
332
333    #[test]
334    fn test_no_inverse_small() {
335        let a = BoxedUint::from(14u64);
336        let m = BoxedUint::from(49u64).to_odd().unwrap();
337
338        let res = a.invert_odd_mod(&m);
339        let is_none: bool = res.is_none().into();
340        assert!(is_none);
341    }
342
343    #[test]
344    fn test_invert_edge() {
345        assert!(bool::from(
346            BoxedUint::zero()
347                .invert_odd_mod(&BoxedUint::one().to_odd().unwrap())
348                .is_none()
349        ));
350        assert_eq!(
351            BoxedUint::one()
352                .invert_odd_mod(&BoxedUint::one().to_odd().unwrap())
353                .unwrap(),
354            BoxedUint::zero()
355        );
356        assert_eq!(
357            BoxedUint::one()
358                .invert_odd_mod(&BoxedUint::from(U256::MAX).to_odd().unwrap())
359                .unwrap(),
360            BoxedUint::one()
361        );
362        assert!(bool::from(
363            BoxedUint::from(U256::MAX)
364                .invert_odd_mod(&BoxedUint::from(U256::MAX).to_odd().unwrap())
365                .is_none()
366        ));
367    }
368
369    #[test]
370    fn invert_mod_precision() {
371        const PRECISION: u32 = 8 * Limb::BITS;
372
373        for limbs in 1..10 {
374            let a = Odd::new_unchecked(BoxedUint::max(PRECISION).resize_unchecked(limbs));
375            let a_inv = a.invert_mod_precision();
376            assert_eq!(a.as_ref().wrapping_mul(&a_inv), BoxedUint::one());
377        }
378    }
379}
crypto_bigint/uint/boxed/invert_mod.rs

crypto_bigint/uint/boxed/
invert_mod.rs
