1 // Copyright 2016 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::{
16 elem::{binary_op, binary_op_assign},
17 elem_sqr_mul, elem_sqr_mul_acc, Modulus, *,
18 };
19 use core::marker::PhantomData;
20
21 macro_rules! p384_limbs {
22 [$($limb:expr),+] => {
23 limbs![$($limb),+]
24 };
25 }
26
27 pub static COMMON_OPS: CommonOps = CommonOps {
28 num_limbs: 384 / LIMB_BITS,
29
30 q: Modulus {
31 p: p384_limbs![
32 0xffffffff, 0x00000000, 0x00000000, 0xffffffff, 0xfffffffe, 0xffffffff, 0xffffffff,
33 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff
34 ],
35 rr: p384_limbs![1, 0xfffffffe, 0, 2, 0, 0xfffffffe, 0, 2, 1, 0, 0, 0],
36 },
37 n: Elem {
38 limbs: p384_limbs![
39 0xccc52973, 0xecec196a, 0x48b0a77a, 0x581a0db2, 0xf4372ddf, 0xc7634d81, 0xffffffff,
40 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff
41 ],
42 m: PhantomData,
43 encoding: PhantomData, // Unencoded
44 },
45
46 a: Elem {
47 limbs: p384_limbs![
48 0xfffffffc, 0x00000003, 0x00000000, 0xfffffffc, 0xfffffffb, 0xffffffff, 0xffffffff,
49 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff
50 ],
51 m: PhantomData,
52 encoding: PhantomData, // Unreduced
53 },
54 b: Elem {
55 limbs: p384_limbs![
56 0x9d412dcc, 0x08118871, 0x7a4c32ec, 0xf729add8, 0x1920022e, 0x77f2209b, 0x94938ae2,
57 0xe3374bee, 0x1f022094, 0xb62b21f4, 0x604fbff9, 0xcd08114b
58 ],
59 m: PhantomData,
60 encoding: PhantomData, // Unreduced
61 },
62
63 elem_mul_mont: p384_elem_mul_mont,
64 elem_sqr_mont: p384_elem_sqr_mont,
65
66 point_add_jacobian_impl: nistz384_point_add,
67 };
68
69 pub static PRIVATE_KEY_OPS: PrivateKeyOps = PrivateKeyOps {
70 common: &COMMON_OPS,
71 elem_inv_squared: p384_elem_inv_squared,
72 point_mul_base_impl: p384_point_mul_base_impl,
73 point_mul_impl: nistz384_point_mul,
74 };
75
p384_elem_inv_squared(a: &Elem<R>) -> Elem<R>76 fn p384_elem_inv_squared(a: &Elem<R>) -> Elem<R> {
77 // Calculate a**-2 (mod q) == a**(q - 3) (mod q)
78 //
79 // The exponent (q - 3) is:
80 //
81 // 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe\
82 // ffffffff0000000000000000fffffffc
83
84 #[inline]
85 fn sqr_mul(a: &Elem<R>, squarings: usize, b: &Elem<R>) -> Elem<R> {
86 elem_sqr_mul(&COMMON_OPS, a, squarings, b)
87 }
88
89 #[inline]
90 fn sqr_mul_acc(a: &mut Elem<R>, squarings: usize, b: &Elem<R>) {
91 elem_sqr_mul_acc(&COMMON_OPS, a, squarings, b)
92 }
93
94 let b_1 = &a;
95 let b_11 = sqr_mul(b_1, 1, b_1);
96 let b_111 = sqr_mul(&b_11, 1, b_1);
97 let f_11 = sqr_mul(&b_111, 3, &b_111);
98 let fff = sqr_mul(&f_11, 6, &f_11);
99 let fff_111 = sqr_mul(&fff, 3, &b_111);
100 let fffffff_11 = sqr_mul(&fff_111, 15, &fff_111);
101
102 let fffffffffffffff = sqr_mul(&fffffff_11, 30, &fffffff_11);
103
104 let ffffffffffffffffffffffffffffff = sqr_mul(&fffffffffffffff, 60, &fffffffffffffff);
105
106 // ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
107 let mut acc = sqr_mul(
108 &ffffffffffffffffffffffffffffff,
109 120,
110 &ffffffffffffffffffffffffffffff,
111 );
112
113 // fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff_111
114 sqr_mul_acc(&mut acc, 15, &fff_111);
115
116 // fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff
117 sqr_mul_acc(&mut acc, 1 + 30, &fffffff_11);
118 sqr_mul_acc(&mut acc, 2, &b_11);
119
120 // fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff
121 // 0000000000000000fffffff_11
122 sqr_mul_acc(&mut acc, 64 + 30, &fffffff_11);
123
124 // fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff
125 // 0000000000000000fffffffc
126 COMMON_OPS.elem_square(&mut acc);
127 COMMON_OPS.elem_square(&mut acc);
128
129 acc
130 }
131
p384_point_mul_base_impl(a: &Scalar) -> Point132 fn p384_point_mul_base_impl(a: &Scalar) -> Point {
133 // XXX: Not efficient. TODO: Precompute multiples of the generator.
134 static GENERATOR: (Elem<R>, Elem<R>) = (
135 Elem {
136 limbs: p384_limbs![
137 0x49c0b528, 0x3dd07566, 0xa0d6ce38, 0x20e378e2, 0x541b4d6e, 0x879c3afc, 0x59a30eff,
138 0x64548684, 0x614ede2b, 0x812ff723, 0x299e1513, 0x4d3aadc2
139 ],
140 m: PhantomData,
141 encoding: PhantomData,
142 },
143 Elem {
144 limbs: p384_limbs![
145 0x4b03a4fe, 0x23043dad, 0x7bb4a9ac, 0xa1bfa8bf, 0x2e83b050, 0x8bade756, 0x68f4ffd9,
146 0xc6c35219, 0x3969a840, 0xdd800226, 0x5a15c5e9, 0x2b78abc2
147 ],
148 m: PhantomData,
149 encoding: PhantomData,
150 },
151 );
152
153 PRIVATE_KEY_OPS.point_mul(a, &GENERATOR)
154 }
155
156 pub static PUBLIC_KEY_OPS: PublicKeyOps = PublicKeyOps {
157 common: &COMMON_OPS,
158 };
159
160 pub static SCALAR_OPS: ScalarOps = ScalarOps {
161 common: &COMMON_OPS,
162 scalar_inv_to_mont_impl: p384_scalar_inv_to_mont,
163 scalar_mul_mont: p384_scalar_mul_mont,
164 };
165
166 pub static PUBLIC_SCALAR_OPS: PublicScalarOps = PublicScalarOps {
167 scalar_ops: &SCALAR_OPS,
168 public_key_ops: &PUBLIC_KEY_OPS,
169 private_key_ops: &PRIVATE_KEY_OPS,
170
171 q_minus_n: Elem {
172 limbs: p384_limbs![
173 0x333ad68c, 0x1313e696, 0xb74f5885, 0xa7e5f24c, 0x0bc8d21f, 0x389cb27e, 0, 0, 0, 0, 0,
174 0
175 ],
176
177 m: PhantomData,
178 encoding: PhantomData, // Unencoded
179 },
180 };
181
182 pub static PRIVATE_SCALAR_OPS: PrivateScalarOps = PrivateScalarOps {
183 scalar_ops: &SCALAR_OPS,
184
185 oneRR_mod_n: Scalar {
186 limbs: N_RR_LIMBS,
187 m: PhantomData,
188 encoding: PhantomData, // R
189 },
190 };
191
p384_scalar_inv_to_mont(a: &Scalar<Unencoded>) -> Scalar<R>192 fn p384_scalar_inv_to_mont(a: &Scalar<Unencoded>) -> Scalar<R> {
193 // Calculate the modular inverse of scalar |a| using Fermat's Little
194 // Theorem:
195 //
196 // a**-1 (mod n) == a**(n - 2) (mod n)
197 //
198 // The exponent (n - 2) is:
199 //
200 // 0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf\
201 // 581a0db248b0a77aecec196accc52971.
202
203 fn mul(a: &Scalar<R>, b: &Scalar<R>) -> Scalar<R> {
204 binary_op(p384_scalar_mul_mont, a, b)
205 }
206
207 fn sqr(a: &Scalar<R>) -> Scalar<R> {
208 binary_op(p384_scalar_mul_mont, a, a)
209 }
210
211 fn sqr_mut(a: &mut Scalar<R>) {
212 unary_op_from_binary_op_assign(p384_scalar_mul_mont, a);
213 }
214
215 // Returns (`a` squared `squarings` times) * `b`.
216 fn sqr_mul(a: &Scalar<R>, squarings: usize, b: &Scalar<R>) -> Scalar<R> {
217 debug_assert!(squarings >= 1);
218 let mut tmp = sqr(a);
219 for _ in 1..squarings {
220 sqr_mut(&mut tmp);
221 }
222 mul(&tmp, b)
223 }
224
225 // Sets `acc` = (`acc` squared `squarings` times) * `b`.
226 fn sqr_mul_acc(acc: &mut Scalar<R>, squarings: usize, b: &Scalar<R>) {
227 debug_assert!(squarings >= 1);
228 for _ in 0..squarings {
229 sqr_mut(acc);
230 }
231 binary_op_assign(p384_scalar_mul_mont, acc, b)
232 }
233
234 fn to_mont(a: &Scalar<Unencoded>) -> Scalar<R> {
235 static N_RR: Scalar<Unencoded> = Scalar {
236 limbs: N_RR_LIMBS,
237 m: PhantomData,
238 encoding: PhantomData,
239 };
240 binary_op(p384_scalar_mul_mont, a, &N_RR)
241 }
242
243 // Indexes into `d`.
244 const B_1: usize = 0;
245 const B_11: usize = 1;
246 const B_101: usize = 2;
247 const B_111: usize = 3;
248 const B_1001: usize = 4;
249 const B_1011: usize = 5;
250 const B_1101: usize = 6;
251 const B_1111: usize = 7;
252 const DIGIT_COUNT: usize = 8;
253
254 let mut d = [Scalar::zero(); DIGIT_COUNT];
255 d[B_1] = to_mont(a);
256 let b_10 = sqr(&d[B_1]);
257 for i in B_11..DIGIT_COUNT {
258 d[i] = mul(&d[i - 1], &b_10);
259 }
260
261 let ff = sqr_mul(&d[B_1111], 0 + 4, &d[B_1111]);
262 let ffff = sqr_mul(&ff, 0 + 8, &ff);
263 let ffffffff = sqr_mul(&ffff, 0 + 16, &ffff);
264
265 let ffffffffffffffff = sqr_mul(&ffffffff, 0 + 32, &ffffffff);
266
267 let ffffffffffffffffffffffff = sqr_mul(&ffffffffffffffff, 0 + 32, &ffffffff);
268
269 // ffffffffffffffffffffffffffffffffffffffffffffffff
270 let mut acc = sqr_mul(&ffffffffffffffffffffffff, 0 + 96, &ffffffffffffffffffffffff);
271
272 // The rest of the exponent, in binary, is:
273 //
274 // 1100011101100011010011011000000111110100001101110010110111011111
275 // 0101100000011010000011011011001001001000101100001010011101111010
276 // 1110110011101100000110010110101011001100110001010010100101110001
277
278 static REMAINING_WINDOWS: [(u8, u8); 39] = [
279 (2, B_11 as u8),
280 (3 + 3, B_111 as u8),
281 (1 + 2, B_11 as u8),
282 (3 + 2, B_11 as u8),
283 (1 + 4, B_1001 as u8),
284 (4, B_1011 as u8),
285 (6 + 4, B_1111 as u8),
286 (3, B_101 as u8),
287 (4 + 1, B_1 as u8),
288 (4, B_1011 as u8),
289 (4, B_1001 as u8),
290 (1 + 4, B_1101 as u8),
291 (4, B_1101 as u8),
292 (4, B_1111 as u8),
293 (1 + 4, B_1011 as u8),
294 (6 + 4, B_1101 as u8),
295 (5 + 4, B_1101 as u8),
296 (4, B_1011 as u8),
297 (2 + 4, B_1001 as u8),
298 (2 + 1, B_1 as u8),
299 (3 + 4, B_1011 as u8),
300 (4 + 3, B_101 as u8),
301 (2 + 3, B_111 as u8),
302 (1 + 4, B_1111 as u8),
303 (1 + 4, B_1011 as u8),
304 (4, B_1011 as u8),
305 (2 + 3, B_111 as u8),
306 (1 + 2, B_11 as u8),
307 (5 + 2, B_11 as u8),
308 (2 + 4, B_1011 as u8),
309 (1 + 3, B_101 as u8),
310 (1 + 2, B_11 as u8),
311 (2 + 2, B_11 as u8),
312 (2 + 2, B_11 as u8),
313 (3 + 3, B_101 as u8),
314 (2 + 3, B_101 as u8),
315 (2 + 3, B_101 as u8),
316 (2, B_11 as u8),
317 (3 + 1, B_1 as u8),
318 ];
319
320 for &(squarings, digit) in &REMAINING_WINDOWS[..] {
321 sqr_mul_acc(&mut acc, usize::from(squarings), &d[usize::from(digit)]);
322 }
323
324 acc
325 }
326
p384_elem_sqr_mont( r: *mut Limb, a: *const Limb, )327 unsafe extern "C" fn p384_elem_sqr_mont(
328 r: *mut Limb, // [COMMON_OPS.num_limbs]
329 a: *const Limb, // [COMMON_OPS.num_limbs]
330 ) {
331 // XXX: Inefficient. TODO: Make a dedicated squaring routine.
332 p384_elem_mul_mont(r, a, a);
333 }
334
335 const N_RR_LIMBS: [Limb; MAX_LIMBS] = p384_limbs![
336 0x19b409a9, 0x2d319b24, 0xdf1aa419, 0xff3d81e5, 0xfcb82947, 0xbc3e483a, 0x4aab1cc5, 0xd40d4917,
337 0x28266895, 0x3fb05b7a, 0x2b39bf21, 0x0c84ee01
338 ];
339
340 prefixed_extern! {
341 fn p384_elem_mul_mont(
342 r: *mut Limb, // [COMMON_OPS.num_limbs]
343 a: *const Limb, // [COMMON_OPS.num_limbs]
344 b: *const Limb, // [COMMON_OPS.num_limbs]
345 );
346
347 fn nistz384_point_add(
348 r: *mut Limb, // [3][COMMON_OPS.num_limbs]
349 a: *const Limb, // [3][COMMON_OPS.num_limbs]
350 b: *const Limb, // [3][COMMON_OPS.num_limbs]
351 );
352 fn nistz384_point_mul(
353 r: *mut Limb, // [3][COMMON_OPS.num_limbs]
354 p_scalar: *const Limb, // [COMMON_OPS.num_limbs]
355 p_x: *const Limb, // [COMMON_OPS.num_limbs]
356 p_y: *const Limb, // [COMMON_OPS.num_limbs]
357 );
358
359 fn p384_scalar_mul_mont(
360 r: *mut Limb, // [COMMON_OPS.num_limbs]
361 a: *const Limb, // [COMMON_OPS.num_limbs]
362 b: *const Limb, // [COMMON_OPS.num_limbs]
363 );
364 }
365