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! p256_limbs {
22 [ $($limb:expr),+ ] => {
23 limbs![$($limb),+, 0, 0, 0, 0]
24 };
25 }
26
27 pub static COMMON_OPS: CommonOps = CommonOps {
28 num_limbs: 256 / LIMB_BITS,
29
30 q: Modulus {
31 p: p256_limbs![
32 0xffffffff, 0xffffffff, 0xffffffff, 0x00000000, 0x00000000, 0x00000000, 0x00000001,
33 0xffffffff
34 ],
35 rr: p256_limbs![
36 0x00000003, 0x00000000, 0xffffffff, 0xfffffffb, 0xfffffffe, 0xffffffff, 0xfffffffd,
37 0x00000004
38 ],
39 },
40
41 n: Elem {
42 limbs: p256_limbs![
43 0xfc632551, 0xf3b9cac2, 0xa7179e84, 0xbce6faad, 0xffffffff, 0xffffffff, 0x00000000,
44 0xffffffff
45 ],
46 m: PhantomData,
47 encoding: PhantomData, // Unencoded
48 },
49
50 a: Elem {
51 limbs: p256_limbs![
52 0xfffffffc, 0xffffffff, 0xffffffff, 0x00000003, 0x00000000, 0x00000000, 0x00000004,
53 0xfffffffc
54 ],
55 m: PhantomData,
56 encoding: PhantomData, // R
57 },
58 b: Elem {
59 limbs: p256_limbs![
60 0x29c4bddf, 0xd89cdf62, 0x78843090, 0xacf005cd, 0xf7212ed6, 0xe5a220ab, 0x04874834,
61 0xdc30061d
62 ],
63 m: PhantomData,
64 encoding: PhantomData, // R
65 },
66
67 elem_add_impl: GFp_nistz256_add,
68 elem_mul_mont: GFp_nistz256_mul_mont,
69 elem_sqr_mont: GFp_nistz256_sqr_mont,
70
71 point_add_jacobian_impl: GFp_nistz256_point_add,
72 };
73
74 pub static PRIVATE_KEY_OPS: PrivateKeyOps = PrivateKeyOps {
75 common: &COMMON_OPS,
76 elem_inv_squared: p256_elem_inv_squared,
77 point_mul_base_impl: p256_point_mul_base_impl,
78 point_mul_impl: GFp_nistz256_point_mul,
79 };
80
p256_elem_inv_squared(a: &Elem<R>) -> Elem<R>81 fn p256_elem_inv_squared(a: &Elem<R>) -> Elem<R> {
82 // Calculate a**-2 (mod q) == a**(q - 3) (mod q)
83 //
84 // The exponent (q - 3) is:
85 //
86 // 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
87
88 #[inline]
89 fn sqr_mul(a: &Elem<R>, squarings: usize, b: &Elem<R>) -> Elem<R> {
90 elem_sqr_mul(&COMMON_OPS, a, squarings, b)
91 }
92
93 #[inline]
94 fn sqr_mul_acc(a: &mut Elem<R>, squarings: usize, b: &Elem<R>) {
95 elem_sqr_mul_acc(&COMMON_OPS, a, squarings, b)
96 }
97
98 let b_1 = &a;
99 let b_11 = sqr_mul(b_1, 1, b_1);
100 let b_111 = sqr_mul(&b_11, 1, b_1);
101 let f_11 = sqr_mul(&b_111, 3, &b_111);
102 let fff = sqr_mul(&f_11, 6, &f_11);
103 let fff_111 = sqr_mul(&fff, 3, &b_111);
104 let fffffff_11 = sqr_mul(&fff_111, 15, &fff_111);
105 let ffffffff = sqr_mul(&fffffff_11, 2, &b_11);
106
107 // ffffffff00000001
108 let mut acc = sqr_mul(&ffffffff, 31 + 1, b_1);
109
110 // ffffffff00000001000000000000000000000000ffffffff
111 sqr_mul_acc(&mut acc, 96 + 32, &ffffffff);
112
113 // ffffffff00000001000000000000000000000000ffffffffffffffff
114 sqr_mul_acc(&mut acc, 32, &ffffffff);
115
116 // ffffffff00000001000000000000000000000000fffffffffffffffffffffff_11
117 sqr_mul_acc(&mut acc, 30, &fffffff_11);
118
119 // ffffffff00000001000000000000000000000000fffffffffffffffffffffffc
120 COMMON_OPS.elem_square(&mut acc);
121 COMMON_OPS.elem_square(&mut acc);
122
123 acc
124 }
125
p256_point_mul_base_impl(g_scalar: &Scalar) -> Point126 fn p256_point_mul_base_impl(g_scalar: &Scalar) -> Point {
127 let mut r = Point::new_at_infinity();
128
129 // Keep this in sync with the logic for defining `GFp_USE_LARGE_TABLE` and
130 // with the logic for deciding whether to test `GFp_nistz256_point_add_affine`
131 // in suite_b/ops.rs.
132
133 #[cfg(any(target_arch = "aarch64", target_arch = "x86", target_arch = "x86_64"))]
134 {
135 extern "C" {
136 fn GFp_nistz256_point_mul_base(
137 r: *mut Limb, // [3][COMMON_OPS.num_limbs]
138 g_scalar: *const Limb, // [COMMON_OPS.num_limbs]
139 );
140 }
141 unsafe {
142 GFp_nistz256_point_mul_base(r.xyz.as_mut_ptr(), g_scalar.limbs.as_ptr());
143 }
144 }
145
146 #[cfg(not(any(target_arch = "aarch64", target_arch = "x86", target_arch = "x86_64")))]
147 {
148 static GENERATOR: (Elem<R>, Elem<R>) = (
149 Elem {
150 limbs: p256_limbs![
151 0x18a9143c, 0x79e730d4, 0x5fedb601, 0x75ba95fc, 0x77622510, 0x79fb732b,
152 0xa53755c6, 0x18905f76
153 ],
154 m: PhantomData,
155 encoding: PhantomData,
156 },
157 Elem {
158 limbs: p256_limbs![
159 0xce95560a, 0xddf25357, 0xba19e45c, 0x8b4ab8e4, 0xdd21f325, 0xd2e88688,
160 0x25885d85, 0x8571ff18
161 ],
162 m: PhantomData,
163 encoding: PhantomData,
164 },
165 );
166
167 unsafe {
168 GFp_nistz256_point_mul(
169 r.xyz.as_mut_ptr(),
170 g_scalar.limbs.as_ptr(),
171 GENERATOR.0.limbs.as_ptr(),
172 GENERATOR.1.limbs.as_ptr(),
173 );
174 }
175 }
176
177 r
178 }
179
180 pub static PUBLIC_KEY_OPS: PublicKeyOps = PublicKeyOps {
181 common: &COMMON_OPS,
182 };
183
184 pub static SCALAR_OPS: ScalarOps = ScalarOps {
185 common: &COMMON_OPS,
186 scalar_inv_to_mont_impl: p256_scalar_inv_to_mont,
187 scalar_mul_mont: GFp_p256_scalar_mul_mont,
188 };
189
190 pub static PUBLIC_SCALAR_OPS: PublicScalarOps = PublicScalarOps {
191 scalar_ops: &SCALAR_OPS,
192 public_key_ops: &PUBLIC_KEY_OPS,
193 private_key_ops: &PRIVATE_KEY_OPS,
194
195 q_minus_n: Elem {
196 limbs: p256_limbs![0x039cdaae, 0x0c46353d, 0x58e8617b, 0x43190553, 0, 0, 0, 0],
197 m: PhantomData,
198 encoding: PhantomData, // Unencoded
199 },
200 };
201
202 pub static PRIVATE_SCALAR_OPS: PrivateScalarOps = PrivateScalarOps {
203 scalar_ops: &SCALAR_OPS,
204
205 oneRR_mod_n: Scalar {
206 limbs: p256_limbs![
207 0xbe79eea2, 0x83244c95, 0x49bd6fa6, 0x4699799c, 0x2b6bec59, 0x2845b239, 0xf3d95620,
208 0x66e12d94
209 ],
210 m: PhantomData,
211 encoding: PhantomData, // R
212 },
213 };
214
p256_scalar_inv_to_mont(a: &Scalar<Unencoded>) -> Scalar<R>215 fn p256_scalar_inv_to_mont(a: &Scalar<Unencoded>) -> Scalar<R> {
216 // Calculate the modular inverse of scalar |a| using Fermat's Little
217 // Theorem:
218 //
219 // a**-1 (mod n) == a**(n - 2) (mod n)
220 //
221 // The exponent (n - 2) is:
222 //
223 // 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc63254f
224
225 #[inline]
226 fn mul(a: &Scalar<R>, b: &Scalar<R>) -> Scalar<R> {
227 binary_op(GFp_p256_scalar_mul_mont, a, b)
228 }
229
230 #[inline]
231 fn sqr(a: &Scalar<R>) -> Scalar<R> {
232 unary_op(GFp_p256_scalar_sqr_mont, a)
233 }
234
235 // Returns (`a` squared `squarings` times) * `b`.
236 fn sqr_mul(a: &Scalar<R>, squarings: Limb, b: &Scalar<R>) -> Scalar<R> {
237 debug_assert!(squarings >= 1);
238 let mut tmp = Scalar::zero();
239 unsafe { GFp_p256_scalar_sqr_rep_mont(tmp.limbs.as_mut_ptr(), a.limbs.as_ptr(), squarings) }
240 mul(&tmp, b)
241 }
242
243 // Sets `acc` = (`acc` squared `squarings` times) * `b`.
244 fn sqr_mul_acc(acc: &mut Scalar<R>, squarings: Limb, b: &Scalar<R>) {
245 debug_assert!(squarings >= 1);
246 unsafe {
247 GFp_p256_scalar_sqr_rep_mont(acc.limbs.as_mut_ptr(), acc.limbs.as_ptr(), squarings)
248 }
249 binary_op_assign(GFp_p256_scalar_mul_mont, acc, b);
250 }
251
252 fn to_mont(a: &Scalar) -> Scalar<R> {
253 static N_RR: Scalar<Unencoded> = Scalar {
254 limbs: p256_limbs![
255 0xbe79eea2, 0x83244c95, 0x49bd6fa6, 0x4699799c, 0x2b6bec59, 0x2845b239, 0xf3d95620,
256 0x66e12d94
257 ],
258 m: PhantomData,
259 encoding: PhantomData,
260 };
261 binary_op(GFp_p256_scalar_mul_mont, a, &N_RR)
262 }
263
264 // Indexes into `d`.
265 const B_1: usize = 0;
266 const B_10: usize = 1;
267 const B_11: usize = 2;
268 const B_101: usize = 3;
269 const B_111: usize = 4;
270 const B_1111: usize = 5;
271 const B_10101: usize = 6;
272 const B_101111: usize = 7;
273 const DIGIT_COUNT: usize = 8;
274
275 let mut d = [Scalar::zero(); DIGIT_COUNT];
276
277 d[B_1] = to_mont(a);
278 d[B_10] = sqr(&d[B_1]);
279 d[B_11] = mul(&d[B_10], &d[B_1]);
280 d[B_101] = mul(&d[B_10], &d[B_11]);
281 d[B_111] = mul(&d[B_101], &d[B_10]);
282 let b_1010 = sqr(&d[B_101]);
283 d[B_1111] = mul(&b_1010, &d[B_101]);
284 d[B_10101] = sqr_mul(&b_1010, 0 + 1, &d[B_1]);
285 let b_101010 = sqr(&d[B_10101]);
286 d[B_101111] = mul(&b_101010, &d[B_101]);
287 let b_111111 = mul(&b_101010, &d[B_10101]);
288
289 let ff = sqr_mul(&b_111111, 0 + 2, &d[B_11]);
290 let ffff = sqr_mul(&ff, 0 + 8, &ff);
291 let ffffffff = sqr_mul(&ffff, 0 + 16, &ffff);
292
293 // ffffffff00000000ffffffff
294 let mut acc = sqr_mul(&ffffffff, 32 + 32, &ffffffff);
295
296 // ffffffff00000000ffffffffffffffff
297 sqr_mul_acc(&mut acc, 0 + 32, &ffffffff);
298
299 // The rest of the exponent, in binary, is:
300 //
301 // 1011110011100110111110101010110110100111000101111001111010000100
302 // 1111001110111001110010101100001011111100011000110010010101001111
303
304 static REMAINING_WINDOWS: [(u8, u8); 26] = [
305 (6, B_101111 as u8),
306 (2 + 3, B_111 as u8),
307 (2 + 2, B_11 as u8),
308 (1 + 4, B_1111 as u8),
309 (5, B_10101 as u8),
310 (1 + 3, B_101 as u8),
311 (3, B_101 as u8),
312 (3, B_101 as u8),
313 (2 + 3, B_111 as u8),
314 (3 + 6, B_101111 as u8),
315 (2 + 4, B_1111 as u8),
316 (1 + 1, B_1 as u8),
317 (4 + 1, B_1 as u8),
318 (2 + 4, B_1111 as u8),
319 (2 + 3, B_111 as u8),
320 (1 + 3, B_111 as u8),
321 (2 + 3, B_111 as u8),
322 (2 + 3, B_101 as u8),
323 (1 + 2, B_11 as u8),
324 (4 + 6, B_101111 as u8),
325 (2, B_11 as u8),
326 (3 + 2, B_11 as u8),
327 (3 + 2, B_11 as u8),
328 (2 + 1, B_1 as u8),
329 (2 + 5, B_10101 as u8),
330 (2 + 4, B_1111 as u8),
331 ];
332
333 for &(squarings, digit) in &REMAINING_WINDOWS {
334 sqr_mul_acc(&mut acc, Limb::from(squarings), &d[usize::from(digit)]);
335 }
336
337 acc
338 }
339
340 extern "C" {
GFp_nistz256_add( r: *mut Limb, a: *const Limb, b: *const Limb, )341 fn GFp_nistz256_add(
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 );
GFp_nistz256_mul_mont( r: *mut Limb, a: *const Limb, b: *const Limb, )346 fn GFp_nistz256_mul_mont(
347 r: *mut Limb, // [COMMON_OPS.num_limbs]
348 a: *const Limb, // [COMMON_OPS.num_limbs]
349 b: *const Limb, // [COMMON_OPS.num_limbs]
350 );
GFp_nistz256_sqr_mont( r: *mut Limb, a: *const Limb, )351 fn GFp_nistz256_sqr_mont(
352 r: *mut Limb, // [COMMON_OPS.num_limbs]
353 a: *const Limb, // [COMMON_OPS.num_limbs]
354 );
355
GFp_nistz256_point_add( r: *mut Limb, a: *const Limb, b: *const Limb, )356 fn GFp_nistz256_point_add(
357 r: *mut Limb, // [3][COMMON_OPS.num_limbs]
358 a: *const Limb, // [3][COMMON_OPS.num_limbs]
359 b: *const Limb, // [3][COMMON_OPS.num_limbs]
360 );
GFp_nistz256_point_mul( r: *mut Limb, p_scalar: *const Limb, p_x: *const Limb, p_y: *const Limb, )361 fn GFp_nistz256_point_mul(
362 r: *mut Limb, // [3][COMMON_OPS.num_limbs]
363 p_scalar: *const Limb, // [COMMON_OPS.num_limbs]
364 p_x: *const Limb, // [COMMON_OPS.num_limbs]
365 p_y: *const Limb, // [COMMON_OPS.num_limbs]
366 );
367
GFp_p256_scalar_mul_mont( r: *mut Limb, a: *const Limb, b: *const Limb, )368 fn GFp_p256_scalar_mul_mont(
369 r: *mut Limb, // [COMMON_OPS.num_limbs]
370 a: *const Limb, // [COMMON_OPS.num_limbs]
371 b: *const Limb, // [COMMON_OPS.num_limbs]
372 );
GFp_p256_scalar_sqr_mont( r: *mut Limb, a: *const Limb, )373 fn GFp_p256_scalar_sqr_mont(
374 r: *mut Limb, // [COMMON_OPS.num_limbs]
375 a: *const Limb, // [COMMON_OPS.num_limbs]
376 );
GFp_p256_scalar_sqr_rep_mont( r: *mut Limb, a: *const Limb, rep: Limb, )377 fn GFp_p256_scalar_sqr_rep_mont(
378 r: *mut Limb, // [COMMON_OPS.num_limbs]
379 a: *const Limb, // [COMMON_OPS.num_limbs]
380 rep: Limb,
381 );
382 }
383