ring/arithmetic/
montgomery.rs

Help
1// Copyright 2017-2023 Brian Smith.
2//
3// Permission to use, copy, modify, and/or distribute this software for any
4// purpose with or without fee is hereby granted, provided that the above
5// copyright notice and this permission notice appear in all copies.
6//
7// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES
8// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
10// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
14
15pub use super::n0::N0;
16use crate::cpu;
17
18// Indicates that the element is not encoded; there is no *R* factor
19// that needs to be canceled out.
20#[derive(Copy, Clone)]
21pub enum Unencoded {}
22
23// Indicates that the element is encoded; the value has one *R*
24// factor that needs to be canceled out.
25#[derive(Copy, Clone)]
26pub enum R {}
27
28// Indicates the element is encoded three times; the value has three
29// *R* factors that need to be canceled out.
30#[allow(clippy::upper_case_acronyms)]
31#[derive(Copy, Clone)]
32pub enum RRR {}
33
34// Indicates the element is encoded twice; the value has two *R*
35// factors that need to be canceled out.
36#[derive(Copy, Clone)]
37pub enum RR {}
38
39// Indicates the element is inversely encoded; the value has one
40// 1/*R* factor that needs to be canceled out.
41#[derive(Copy, Clone)]
42pub enum RInverse {}
43
44pub trait Encoding {}
45
46impl Encoding for RRR {}
47impl Encoding for RR {}
48impl Encoding for R {}
49impl Encoding for Unencoded {}
50impl Encoding for RInverse {}
51
52/// The encoding of the result of a reduction.
53pub trait ReductionEncoding {
54    type Output: Encoding;
55}
56
57impl ReductionEncoding for RRR {
58    type Output = RR;
59}
60
61impl ReductionEncoding for RR {
62    type Output = R;
63}
64impl ReductionEncoding for R {
65    type Output = Unencoded;
66}
67impl ReductionEncoding for Unencoded {
68    type Output = RInverse;
69}
70
71/// The encoding of the result of a multiplication.
72pub trait ProductEncoding {
73    type Output: Encoding;
74}
75
76impl<E: ReductionEncoding> ProductEncoding for (Unencoded, E) {
77    type Output = E::Output;
78}
79
80impl<E: Encoding> ProductEncoding for (R, E) {
81    type Output = E;
82}
83
84impl ProductEncoding for (RR, RR) {
85    type Output = RRR;
86}
87
88impl<E: ReductionEncoding> ProductEncoding for (RInverse, E)
89where
90    E::Output: ReductionEncoding,
91{
92    type Output = <<E as ReductionEncoding>::Output as ReductionEncoding>::Output;
93}
94
95// XXX: Rust doesn't allow overlapping impls,
96// TODO (if/when Rust allows it):
97// impl<E1, E2: ReductionEncoding> ProductEncoding for
98//         (E1, E2) {
99//     type Output = <(E2, E1) as ProductEncoding>::Output;
100// }
101impl ProductEncoding for (RR, Unencoded) {
102    type Output = <(Unencoded, RR) as ProductEncoding>::Output;
103}
104impl ProductEncoding for (RR, RInverse) {
105    type Output = <(RInverse, RR) as ProductEncoding>::Output;
106}
107
108impl ProductEncoding for (RRR, RInverse) {
109    type Output = <(RInverse, RRR) as ProductEncoding>::Output;
110}
111
112#[allow(unused_imports)]
113use crate::{bssl, c, limb::Limb};
114
115#[inline(always)]
116unsafe fn mul_mont(
117    r: *mut Limb,
118    a: *const Limb,
119    b: *const Limb,
120    n: *const Limb,
121    n0: &N0,
122    num_limbs: c::size_t,
123    _: cpu::Features,
124) {
125    bn_mul_mont(r, a, b, n, n0, num_limbs)
126}
127
128#[cfg(not(any(
129    target_arch = "aarch64",
130    target_arch = "arm",
131    target_arch = "x86",
132    target_arch = "x86_64"
133)))]
134// TODO: Stop calling this from C and un-export it.
135#[allow(deprecated)]
136prefixed_export! {
137    unsafe fn bn_mul_mont(
138        r: *mut Limb,
139        a: *const Limb,
140        b: *const Limb,
141        n: *const Limb,
142        n0: &N0,
143        num_limbs: c::size_t,
144    ) {
145        // The mutable pointer `r` may alias `a` and/or `b`, so the lifetimes of
146        // any slices for `a` or `b` must not overlap with the lifetime of any
147        // mutable for `r`.
148
149        // Nothing aliases `n`
150        let n = unsafe { core::slice::from_raw_parts(n, num_limbs) };
151
152        let mut tmp = [0; 2 * super::BIGINT_MODULUS_MAX_LIMBS];
153        let tmp = &mut tmp[..(2 * num_limbs)];
154        {
155            let a: &[Limb] = unsafe { core::slice::from_raw_parts(a, num_limbs) };
156            let b: &[Limb] = unsafe { core::slice::from_raw_parts(b, num_limbs) };
157            limbs_mul(tmp, a, b);
158        }
159        let r: &mut [Limb] = unsafe { core::slice::from_raw_parts_mut(r, num_limbs) };
160        limbs_from_mont_in_place(r, tmp, n, n0);
161    }
162}
163
164// `bigint` needs then when the `alloc` feature is enabled. `bn_mul_mont` above needs this when
165// we are using the platforms for which we don't have `bn_mul_mont` in assembly.
166#[cfg(any(
167    feature = "alloc",
168    not(any(
169        target_arch = "aarch64",
170        target_arch = "arm",
171        target_arch = "x86",
172        target_arch = "x86_64"
173    ))
174))]
175pub(super) fn limbs_from_mont_in_place(r: &mut [Limb], tmp: &mut [Limb], m: &[Limb], n0: &N0) {
176    prefixed_extern! {
177        fn bn_from_montgomery_in_place(
178            r: *mut Limb,
179            num_r: c::size_t,
180            a: *mut Limb,
181            num_a: c::size_t,
182            n: *const Limb,
183            num_n: c::size_t,
184            n0: &N0,
185        ) -> bssl::Result;
186    }
187    Result::from(unsafe {
188        bn_from_montgomery_in_place(
189            r.as_mut_ptr(),
190            r.len(),
191            tmp.as_mut_ptr(),
192            tmp.len(),
193            m.as_ptr(),
194            m.len(),
195            n0,
196        )
197    })
198    .unwrap()
199}
200
201#[cfg(not(any(
202    target_arch = "aarch64",
203    target_arch = "arm",
204    target_arch = "x86",
205    target_arch = "x86_64"
206)))]
207fn limbs_mul(r: &mut [Limb], a: &[Limb], b: &[Limb]) {
208    debug_assert_eq!(r.len(), 2 * a.len());
209    debug_assert_eq!(a.len(), b.len());
210    let ab_len = a.len();
211
212    r[..ab_len].fill(0);
213    for (i, &b_limb) in b.iter().enumerate() {
214        r[ab_len + i] = unsafe {
215            limbs_mul_add_limb(r[i..][..ab_len].as_mut_ptr(), a.as_ptr(), b_limb, ab_len)
216        };
217    }
218}
219
220#[cfg(any(
221    test,
222    not(any(
223        target_arch = "aarch64",
224        target_arch = "arm",
225        target_arch = "x86_64",
226        target_arch = "x86"
227    ))
228))]
229prefixed_extern! {
230    // `r` must not alias `a`
231    #[must_use]
232    fn limbs_mul_add_limb(r: *mut Limb, a: *const Limb, b: Limb, num_limbs: c::size_t) -> Limb;
233}
234
235#[cfg(any(
236    target_arch = "aarch64",
237    target_arch = "arm",
238    target_arch = "x86_64",
239    target_arch = "x86"
240))]
241prefixed_extern! {
242    // `r` and/or 'a' and/or 'b' may alias.
243    fn bn_mul_mont(
244        r: *mut Limb,
245        a: *const Limb,
246        b: *const Limb,
247        n: *const Limb,
248        n0: &N0,
249        num_limbs: c::size_t,
250    );
251}
252
253/// r *= a
254pub(super) fn limbs_mont_mul(
255    r: &mut [Limb],
256    a: &[Limb],
257    m: &[Limb],
258    n0: &N0,
259    cpu_features: cpu::Features,
260) {
261    debug_assert_eq!(r.len(), m.len());
262    debug_assert_eq!(a.len(), m.len());
263    unsafe {
264        mul_mont(
265            r.as_mut_ptr(),
266            r.as_ptr(),
267            a.as_ptr(),
268            m.as_ptr(),
269            n0,
270            r.len(),
271            cpu_features,
272        )
273    }
274}
275
276/// r = a * b
277#[cfg(not(target_arch = "x86_64"))]
278pub(super) fn limbs_mont_product(
279    r: &mut [Limb],
280    a: &[Limb],
281    b: &[Limb],
282    m: &[Limb],
283    n0: &N0,
284    cpu_features: cpu::Features,
285) {
286    debug_assert_eq!(r.len(), m.len());
287    debug_assert_eq!(a.len(), m.len());
288    debug_assert_eq!(b.len(), m.len());
289
290    unsafe {
291        mul_mont(
292            r.as_mut_ptr(),
293            a.as_ptr(),
294            b.as_ptr(),
295            m.as_ptr(),
296            n0,
297            r.len(),
298            cpu_features,
299        )
300    }
301}
302
303/// r = r**2
304pub(super) fn limbs_mont_square(r: &mut [Limb], m: &[Limb], n0: &N0, cpu_features: cpu::Features) {
305    debug_assert_eq!(r.len(), m.len());
306    unsafe {
307        mul_mont(
308            r.as_mut_ptr(),
309            r.as_ptr(),
310            r.as_ptr(),
311            m.as_ptr(),
312            n0,
313            r.len(),
314            cpu_features,
315        )
316    }
317}
318#[cfg(test)]
319mod tests {
320    use super::*;
321    use crate::limb::Limb;
322
323    #[test]
324    // TODO: wasm
325    fn test_mul_add_words() {
326        const ZERO: Limb = 0;
327        const MAX: Limb = ZERO.wrapping_sub(1);
328        static TEST_CASES: &[(&[Limb], &[Limb], Limb, Limb, &[Limb])] = &[
329            (&[0], &[0], 0, 0, &[0]),
330            (&[MAX], &[0], MAX, 0, &[MAX]),
331            (&[0], &[MAX], MAX, MAX - 1, &[1]),
332            (&[MAX], &[MAX], MAX, MAX, &[0]),
333            (&[0, 0], &[MAX, MAX], MAX, MAX - 1, &[1, MAX]),
334            (&[1, 0], &[MAX, MAX], MAX, MAX - 1, &[2, MAX]),
335            (&[MAX, 0], &[MAX, MAX], MAX, MAX, &[0, 0]),
336            (&[0, 1], &[MAX, MAX], MAX, MAX, &[1, 0]),
337            (&[MAX, MAX], &[MAX, MAX], MAX, MAX, &[0, MAX]),
338        ];
339
340        for (i, (r_input, a, w, expected_retval, expected_r)) in TEST_CASES.iter().enumerate() {
341            let mut r = [0; super::super::BIGINT_MODULUS_MAX_LIMBS];
342            let r = {
343                let r = &mut r[..r_input.len()];
344                r.copy_from_slice(r_input);
345                r
346            };
347            assert_eq!(r.len(), a.len()); // Sanity check
348            let actual_retval =
349                unsafe { limbs_mul_add_limb(r.as_mut_ptr(), a.as_ptr(), *w, a.len()) };
350            assert_eq!(&r, expected_r, "{}: {:x?} != {:x?}", i, r, expected_r);
351            assert_eq!(
352                actual_retval, *expected_retval,
353                "{}: {:x?} != {:x?}",
354                i, actual_retval, *expected_retval
355            );
356        }
357    }
358}
ring/arithmetic/montgomery.rs

ring/arithmetic/
montgomery.rs
