crypto_bigint/uint/boxed/
inv_mod.rs

1//! [`BoxedUint`] modular inverse (i.e. reciprocal) operations.
2
3use crate::{
4    modular::BoxedSafeGcdInverter, BoxedUint, ConstantTimeSelect, Integer, InvMod, Inverter, Odd,
5    PrecomputeInverter, PrecomputeInverterWithAdjuster,
6};
7use subtle::{Choice, ConstantTimeEq, ConstantTimeLess, CtOption};
8
9impl BoxedUint {
10    /// Computes the multiplicative inverse of `self` mod `modulus`, where `modulus` is odd.
11    pub fn inv_odd_mod(&self, modulus: &Odd<Self>) -> CtOption<Self> {
12        modulus.precompute_inverter().invert(self)
13    }
14
15    /// Computes 1/`self` mod `2^k`.
16    ///
17    /// If the inverse does not exist (`k > 0` and `self` is even),
18    /// returns `Choice::FALSE` as the second element of the tuple,
19    /// otherwise returns `Choice::TRUE`.
20    pub(crate) fn inv_mod2k(&self, k: u32) -> (Self, Choice) {
21        let mut x = Self::zero_with_precision(self.bits_precision()); // keeps `x` during iterations
22        let mut b = Self::one_with_precision(self.bits_precision()); // keeps `b_i` during iterations
23
24        // The inverse exists either if `k` is 0 or if `self` is odd.
25        let is_some = k.ct_eq(&0) | self.is_odd();
26
27        for i in 0..self.bits_precision() {
28            // Only iterations for i = 0..k need to change `x`,
29            // the rest are dummy ones performed for the sake of constant-timeness.
30            let within_range = i.ct_lt(&k);
31
32            // X_i = b_i mod 2
33            let x_i = b.limbs[0].0 & 1;
34            let x_i_choice = Choice::from(x_i as u8);
35            // b_{i+1} = (b_i - a * X_i) / 2
36            b = Self::ct_select(&b, &b.wrapping_sub(self), x_i_choice).shr1();
37
38            // Store the X_i bit in the result (x = x | (1 << X_i))
39            // Don't change the result in dummy iterations.
40            let x_i_choice = x_i_choice & within_range;
41            x.set_bit(i, x_i_choice);
42        }
43
44        (x, is_some)
45    }
46
47    /// Computes the multiplicaitve inverse of `self` mod `modulus`
48    ///
49    /// `self` and `modulus` must have the same number of limbs, or the function will panic
50    ///
51    /// TODO: maybe some better documentation is needed
52    pub fn inv_mod(&self, modulus: &Self) -> CtOption<Self> {
53        debug_assert_eq!(self.bits_precision(), modulus.bits_precision());
54        let k = modulus.trailing_zeros();
55        let (s, _overflowed) = modulus.overflowing_shr(k);
56
57        let s_is_odd = s.is_odd();
58        let inv_mod_s = self.inv_odd_mod(&Odd(s.clone()));
59        let invertible_mod_s = inv_mod_s.is_some() & s_is_odd;
60        // NOTE: this is some strange acrobatics to get around BoxedUint not supporting
61        // ConditionallySelectable
62        let inv_mod_s =
63            Option::from(inv_mod_s).unwrap_or(Self::zero_with_precision(self.bits_precision()));
64
65        let (inv_mod_2k, invertible_mod_2k) = self.inv_mod2k(k);
66        let is_some = invertible_mod_s & invertible_mod_2k;
67
68        let (s_inv_mod_2k, _) = s.inv_mod2k(k);
69        let (shifted, _overflowed) =
70            BoxedUint::one_with_precision(self.bits_precision()).overflowing_shl(k);
71        let mask = shifted.wrapping_sub(&BoxedUint::one_with_precision(self.bits_precision()));
72        let t = inv_mod_2k
73            .wrapping_sub(&inv_mod_s)
74            .wrapping_mul(&s_inv_mod_2k)
75            .bitand(&mask);
76        let result = inv_mod_s.wrapping_add(&s.wrapping_mul(&t));
77
78        CtOption::new(result, is_some)
79    }
80}
81
82impl InvMod for BoxedUint {
83    type Output = Self;
84
85    fn inv_mod(&self, modulus: &Self) -> CtOption<Self> {
86        self.inv_mod(modulus)
87    }
88}
89
90/// Precompute a Bernstein-Yang inverter using `self` as the modulus.
91impl PrecomputeInverter for Odd<BoxedUint> {
92    type Inverter = BoxedSafeGcdInverter;
93    type Output = BoxedUint;
94
95    fn precompute_inverter(&self) -> BoxedSafeGcdInverter {
96        Self::precompute_inverter_with_adjuster(self, &BoxedUint::one())
97    }
98}
99
100/// Precompute a Bernstein-Yang inverter using `self` as the modulus.
101impl PrecomputeInverterWithAdjuster<BoxedUint> for Odd<BoxedUint> {
102    fn precompute_inverter_with_adjuster(&self, adjuster: &BoxedUint) -> BoxedSafeGcdInverter {
103        BoxedSafeGcdInverter::new(self, adjuster)
104    }
105}
106
107#[cfg(test)]
108mod tests {
109    use super::BoxedUint;
110    use hex_literal::hex;
111
112    #[test]
113    fn inv_mod2k() {
114        let v = BoxedUint::from_be_slice(
115            &hex!("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"),
116            256,
117        )
118        .unwrap();
119        let e = BoxedUint::from_be_slice(
120            &hex!("3642e6faeaac7c6663b93d3d6a0d489e434ddc0123db5fa627c7f6e22ddacacf"),
121            256,
122        )
123        .unwrap();
124        let (a, is_some) = v.inv_mod2k(256);
125        assert_eq!(e, a);
126        assert!(bool::from(is_some));
127
128        let v = BoxedUint::from_be_slice(
129            &hex!("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141"),
130            256,
131        )
132        .unwrap();
133        let e = BoxedUint::from_be_slice(
134            &hex!("261776f29b6b106c7680cf3ed83054a1af5ae537cb4613dbb4f20099aa774ec1"),
135            256,
136        )
137        .unwrap();
138        let (a, is_some) = v.inv_mod2k(256);
139        assert_eq!(e, a);
140        assert!(bool::from(is_some));
141    }
142
143    #[test]
144    fn inv_odd() {
145        let a = BoxedUint::from_be_hex(
146            concat![
147                "000225E99153B467A5B451979A3F451DAEF3BF8D6C6521D2FA24BBB17F29544E",
148                "347A412B065B75A351EA9719E2430D2477B11CC9CF9C1AD6EDEE26CB15F463F8",
149                "BCC72EF87EA30288E95A48AA792226CEC959DCB0672D8F9D80A54CBBEA85CAD8",
150                "382EC224DEB2F5784E62D0CC2F81C2E6AD14EBABE646D6764B30C32B87688985"
151            ],
152            1024,
153        )
154        .unwrap();
155        let m = BoxedUint::from_be_hex(
156            concat![
157                "D509E7854ABDC81921F669F1DC6F61359523F3949803E58ED4EA8BC16483DC6F",
158                "37BFE27A9AC9EEA2969B357ABC5C0EE214BE16A7D4C58FC620D5B5A20AFF001A",
159                "D198D3155E5799DC4EA76652D64983A7E130B5EACEBAC768D28D589C36EC749C",
160                "558D0B64E37CD0775C0D0104AE7D98BA23C815185DD43CD8B16292FD94156767"
161            ],
162            1024,
163        )
164        .unwrap()
165        .to_odd()
166        .unwrap();
167        let expected = BoxedUint::from_be_hex(
168            concat![
169                "B03623284B0EBABCABD5C5881893320281460C0A8E7BF4BFDCFFCBCCBF436A55",
170                "D364235C8171E46C7D21AAD0680676E57274A8FDA6D12768EF961CACDD2DAE57",
171                "88D93DA5EB8EDC391EE3726CDCF4613C539F7D23E8702200CB31B5ED5B06E5CA",
172                "3E520968399B4017BF98A864FABA2B647EFC4998B56774D4F2CB026BC024A336"
173            ],
174            1024,
175        )
176        .unwrap();
177        assert_eq!(a.inv_odd_mod(&m).unwrap(), expected);
178
179        assert_eq!(a.inv_mod(&m).unwrap(), expected);
180    }
181
182    #[test]
183    fn test_invert_odd_no_inverse() {
184        // 2^128 - 159, a prime
185        let p1 = BoxedUint::from_be_hex(
186            "00000000000000000000000000000000ffffffffffffffffffffffffffffff61",
187            256,
188        )
189        .unwrap();
190        // 2^128 - 173, a prime
191        let p2 = BoxedUint::from_be_hex(
192            "00000000000000000000000000000000ffffffffffffffffffffffffffffff53",
193            256,
194        )
195        .unwrap();
196
197        let m = p1.wrapping_mul(&p2).to_odd().unwrap();
198
199        // `m` is a multiple of `p1`, so no inverse exists
200        let res = p1.inv_odd_mod(&m);
201        let is_none: bool = res.is_none().into();
202        assert!(is_none);
203    }
204
205    #[test]
206    fn test_invert_even() {
207        let a = BoxedUint::from_be_hex(
208            concat![
209                "000225E99153B467A5B451979A3F451DAEF3BF8D6C6521D2FA24BBB17F29544E",
210                "347A412B065B75A351EA9719E2430D2477B11CC9CF9C1AD6EDEE26CB15F463F8",
211                "BCC72EF87EA30288E95A48AA792226CEC959DCB0672D8F9D80A54CBBEA85CAD8",
212                "382EC224DEB2F5784E62D0CC2F81C2E6AD14EBABE646D6764B30C32B87688985"
213            ],
214            1024,
215        )
216        .unwrap();
217        let m = BoxedUint::from_be_hex(
218            concat![
219                "D509E7854ABDC81921F669F1DC6F61359523F3949803E58ED4EA8BC16483DC6F",
220                "37BFE27A9AC9EEA2969B357ABC5C0EE214BE16A7D4C58FC620D5B5A20AFF001A",
221                "D198D3155E5799DC4EA76652D64983A7E130B5EACEBAC768D28D589C36EC749C",
222                "558D0B64E37CD0775C0D0104AE7D98BA23C815185DD43CD8B16292FD94156000"
223            ],
224            1024,
225        )
226        .unwrap();
227        let expected = BoxedUint::from_be_hex(
228            concat![
229                "1EBF391306817E1BC610E213F4453AD70911CCBD59A901B2A468A4FC1D64F357",
230                "DBFC6381EC5635CAA664DF280028AF4651482C77A143DF38D6BFD4D64B6C0225",
231                "FC0E199B15A64966FB26D88A86AD144271F6BDCD3D63193AB2B3CC53B99F21A3",
232                "5B9BFAE5D43C6BC6E7A9856C71C7318C76530E9E5AE35882D5ABB02F1696874D",
233            ],
234            1024,
235        )
236        .unwrap();
237
238        let res = a.inv_mod(&m).unwrap();
239        assert_eq!(res, expected);
240    }
241
242    #[test]
243    fn test_invert_small() {
244        let a = BoxedUint::from(3u64);
245        let m = BoxedUint::from(13u64).to_odd().unwrap();
246
247        let res = a.inv_odd_mod(&m).unwrap();
248        assert_eq!(BoxedUint::from(9u64), res);
249    }
250
251    #[test]
252    fn test_no_inverse_small() {
253        let a = BoxedUint::from(14u64);
254        let m = BoxedUint::from(49u64).to_odd().unwrap();
255
256        let res = a.inv_odd_mod(&m);
257        let is_none: bool = res.is_none().into();
258        assert!(is_none);
259    }
260}
crypto_bigint/uint/boxed/inv_mod.rs

crypto_bigint/uint/boxed/
inv_mod.rs
