1 | // Copyright 2015-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 | |
15 | use super::{BoxedLimbs, Elem, PublicModulus, Unencoded, N0}; |
16 | use crate::{ |
17 | bits::BitLength, |
18 | cpu, error, |
19 | limb::{self, Limb, LimbMask, LIMB_BITS}, |
20 | polyfill::LeadingZerosStripped, |
21 | }; |
22 | use core::marker::PhantomData; |
23 | |
24 | /// The x86 implementation of `bn_mul_mont`, at least, requires at least 4 |
25 | /// limbs. For a long time we have required 4 limbs for all targets, though |
26 | /// this may be unnecessary. TODO: Replace this with |
27 | /// `n.len() < 256 / LIMB_BITS` so that 32-bit and 64-bit platforms behave the |
28 | /// same. |
29 | pub const MODULUS_MIN_LIMBS: usize = 4; |
30 | |
31 | pub const MODULUS_MAX_LIMBS: usize = super::super::BIGINT_MODULUS_MAX_LIMBS; |
32 | |
33 | /// The modulus *m* for a ring ℤ/mℤ, along with the precomputed values needed |
34 | /// for efficient Montgomery multiplication modulo *m*. The value must be odd |
35 | /// and larger than 2. The larger-than-1 requirement is imposed, at least, by |
36 | /// the modular inversion code. |
37 | pub struct OwnedModulus<M> { |
38 | limbs: BoxedLimbs<M>, // Also `value >= 3`. |
39 | |
40 | // n0 * N == -1 (mod r). |
41 | // |
42 | // r == 2**(N0::LIMBS_USED * LIMB_BITS) and LG_LITTLE_R == lg(r). This |
43 | // ensures that we can do integer division by |r| by simply ignoring |
44 | // `N0::LIMBS_USED` limbs. Similarly, we can calculate values modulo `r` by |
45 | // just looking at the lowest `N0::LIMBS_USED` limbs. This is what makes |
46 | // Montgomery multiplication efficient. |
47 | // |
48 | // As shown in Algorithm 1 of "Fast Prime Field Elliptic Curve Cryptography |
49 | // with 256 Bit Primes" by Shay Gueron and Vlad Krasnov, in the loop of a |
50 | // multi-limb Montgomery multiplication of a * b (mod n), given the |
51 | // unreduced product t == a * b, we repeatedly calculate: |
52 | // |
53 | // t1 := t % r |t1| is |t|'s lowest limb (see previous paragraph). |
54 | // t2 := t1*n0*n |
55 | // t3 := t + t2 |
56 | // t := t3 / r copy all limbs of |t3| except the lowest to |t|. |
57 | // |
58 | // In the last step, it would only make sense to ignore the lowest limb of |
59 | // |t3| if it were zero. The middle steps ensure that this is the case: |
60 | // |
61 | // t3 == 0 (mod r) |
62 | // t + t2 == 0 (mod r) |
63 | // t + t1*n0*n == 0 (mod r) |
64 | // t1*n0*n == -t (mod r) |
65 | // t*n0*n == -t (mod r) |
66 | // n0*n == -1 (mod r) |
67 | // n0 == -1/n (mod r) |
68 | // |
69 | // Thus, in each iteration of the loop, we multiply by the constant factor |
70 | // n0, the negative inverse of n (mod r). |
71 | // |
72 | // TODO(perf): Not all 32-bit platforms actually make use of n0[1]. For the |
73 | // ones that don't, we could use a shorter `R` value and use faster `Limb` |
74 | // calculations instead of double-precision `u64` calculations. |
75 | n0: N0, |
76 | |
77 | len_bits: BitLength, |
78 | } |
79 | |
80 | impl<M: PublicModulus> Clone for OwnedModulus<M> { |
81 | fn clone(&self) -> Self { |
82 | Self { |
83 | limbs: self.limbs.clone(), |
84 | n0: self.n0, |
85 | len_bits: self.len_bits, |
86 | } |
87 | } |
88 | } |
89 | |
90 | impl<M> OwnedModulus<M> { |
91 | pub(crate) fn from_be_bytes(input: untrusted::Input) -> Result<Self, error::KeyRejected> { |
92 | let n = BoxedLimbs::positive_minimal_width_from_be_bytes(input)?; |
93 | if n.len() > MODULUS_MAX_LIMBS { |
94 | return Err(error::KeyRejected::too_large()); |
95 | } |
96 | if n.len() < MODULUS_MIN_LIMBS { |
97 | return Err(error::KeyRejected::unexpected_error()); |
98 | } |
99 | if limb::limbs_are_even_constant_time(&n) != LimbMask::False { |
100 | return Err(error::KeyRejected::invalid_component()); |
101 | } |
102 | if limb::limbs_less_than_limb_constant_time(&n, 3) != LimbMask::False { |
103 | return Err(error::KeyRejected::unexpected_error()); |
104 | } |
105 | |
106 | // n_mod_r = n % r. As explained in the documentation for `n0`, this is |
107 | // done by taking the lowest `N0::LIMBS_USED` limbs of `n`. |
108 | #[allow (clippy::useless_conversion)] |
109 | let n0 = { |
110 | prefixed_extern! { |
111 | fn bn_neg_inv_mod_r_u64(n: u64) -> u64; |
112 | } |
113 | |
114 | // XXX: u64::from isn't guaranteed to be constant time. |
115 | let mut n_mod_r: u64 = u64::from(n[0]); |
116 | |
117 | if N0::LIMBS_USED == 2 { |
118 | // XXX: If we use `<< LIMB_BITS` here then 64-bit builds |
119 | // fail to compile because of `deny(exceeding_bitshifts)`. |
120 | debug_assert_eq!(LIMB_BITS, 32); |
121 | n_mod_r |= u64::from(n[1]) << 32; |
122 | } |
123 | N0::precalculated(unsafe { bn_neg_inv_mod_r_u64(n_mod_r) }) |
124 | }; |
125 | |
126 | let len_bits = limb::limbs_minimal_bits(&n); |
127 | |
128 | Ok(Self { |
129 | limbs: n, |
130 | n0, |
131 | len_bits, |
132 | }) |
133 | } |
134 | |
135 | pub fn verify_less_than<L>(&self, l: &Modulus<L>) -> Result<(), error::Unspecified> { |
136 | if self.len_bits() > l.len_bits() |
137 | || (self.limbs.len() == l.limbs().len() |
138 | && limb::limbs_less_than_limbs_consttime(&self.limbs, l.limbs()) != LimbMask::True) |
139 | { |
140 | return Err(error::Unspecified); |
141 | } |
142 | Ok(()) |
143 | } |
144 | |
145 | pub fn to_elem<L>(&self, l: &Modulus<L>) -> Result<Elem<L, Unencoded>, error::Unspecified> { |
146 | self.verify_less_than(l)?; |
147 | let mut limbs = BoxedLimbs::zero(l.limbs.len()); |
148 | limbs[..self.limbs.len()].copy_from_slice(&self.limbs); |
149 | Ok(Elem { |
150 | limbs, |
151 | encoding: PhantomData, |
152 | }) |
153 | } |
154 | pub(crate) fn modulus(&self, cpu_features: cpu::Features) -> Modulus<M> { |
155 | Modulus { |
156 | limbs: &self.limbs, |
157 | n0: self.n0, |
158 | len_bits: self.len_bits, |
159 | m: PhantomData, |
160 | cpu_features, |
161 | } |
162 | } |
163 | |
164 | pub fn len_bits(&self) -> BitLength { |
165 | self.len_bits |
166 | } |
167 | } |
168 | |
169 | impl<M: PublicModulus> OwnedModulus<M> { |
170 | pub fn be_bytes(&self) -> LeadingZerosStripped<impl ExactSizeIterator<Item = u8> + Clone + '_> { |
171 | LeadingZerosStripped::new(inner:limb::unstripped_be_bytes(&self.limbs)) |
172 | } |
173 | } |
174 | |
175 | pub struct Modulus<'a, M> { |
176 | limbs: &'a [Limb], |
177 | n0: N0, |
178 | len_bits: BitLength, |
179 | m: PhantomData<M>, |
180 | cpu_features: cpu::Features, |
181 | } |
182 | |
183 | impl<M> Modulus<'_, M> { |
184 | pub(super) fn oneR(&self, out: &mut [Limb]) { |
185 | assert_eq!(self.limbs.len(), out.len()); |
186 | |
187 | let r = self.limbs.len() * LIMB_BITS; |
188 | |
189 | // out = 2**r - m where m = self. |
190 | limb::limbs_negative_odd(out, self.limbs); |
191 | |
192 | let lg_m = self.len_bits().as_bits(); |
193 | let leading_zero_bits_in_m = r - lg_m; |
194 | |
195 | // When m's length is a multiple of LIMB_BITS, which is the case we |
196 | // most want to optimize for, then we already have |
197 | // out == 2**r - m == 2**r (mod m). |
198 | if leading_zero_bits_in_m != 0 { |
199 | debug_assert!(leading_zero_bits_in_m < LIMB_BITS); |
200 | // Correct out to 2**(lg m) (mod m). `limbs_negative_odd` flipped |
201 | // all the leading zero bits to ones. Flip them back. |
202 | *out.last_mut().unwrap() &= (!0) >> leading_zero_bits_in_m; |
203 | |
204 | // Now we have out == 2**(lg m) (mod m). Keep doubling until we get |
205 | // to 2**r (mod m). |
206 | for _ in 0..leading_zero_bits_in_m { |
207 | limb::limbs_double_mod(out, self.limbs) |
208 | } |
209 | } |
210 | |
211 | // Now out == 2**r (mod m) == 1*R. |
212 | } |
213 | |
214 | // TODO: XXX Avoid duplication with `Modulus`. |
215 | pub(super) fn zero<E>(&self) -> Elem<M, E> { |
216 | Elem { |
217 | limbs: BoxedLimbs::zero(self.limbs.len()), |
218 | encoding: PhantomData, |
219 | } |
220 | } |
221 | |
222 | #[inline ] |
223 | pub(super) fn limbs(&self) -> &[Limb] { |
224 | self.limbs |
225 | } |
226 | |
227 | #[inline ] |
228 | pub(super) fn n0(&self) -> &N0 { |
229 | &self.n0 |
230 | } |
231 | |
232 | pub fn len_bits(&self) -> BitLength { |
233 | self.len_bits |
234 | } |
235 | |
236 | #[inline ] |
237 | pub(crate) fn cpu_features(&self) -> cpu::Features { |
238 | self.cpu_features |
239 | } |
240 | } |
241 | |