1// Copyright 2016-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
15use super::{
16 elem::{binary_op, binary_op_assign},
17 elem_sqr_mul, elem_sqr_mul_acc, PublicModulus, *,
18};
19
20pub(super) const NUM_LIMBS: usize = 384 / LIMB_BITS;
21
22pub static COMMON_OPS: CommonOps = CommonOps {
23 num_limbs: elem::NumLimbs::P384,
24
25 q: PublicModulus {
26 p: limbs_from_hex("fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff"),
27 rr: PublicElem::from_hex("10000000200000000fffffffe000000000000000200000000fffffffe00000001"),
28 },
29 n: PublicElem::from_hex("ffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973"),
30
31 a: PublicElem::from_hex("fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffffffc0000000000000003fffffffc"),
32 b: PublicElem::from_hex("cd08114b604fbff9b62b21f41f022094e3374bee94938ae277f2209b1920022ef729add87a4c32ec081188719d412dcc"),
33
34 elem_mul_mont: p384_elem_mul_mont,
35 elem_sqr_mont: p384_elem_sqr_mont,
36};
37
38pub(super) static GENERATOR: (PublicElem<R>, PublicElem<R>) = (
39 PublicElem::from_hex("4d3aadc2299e1513812ff723614ede2b6454868459a30eff879c3afc541b4d6e20e378e2a0d6ce383dd0756649c0b528"),
40 PublicElem::from_hex("2b78abc25a15c5e9dd8002263969a840c6c3521968f4ffd98bade7562e83b050a1bfa8bf7bb4a9ac23043dad4b03a4fe"),
41);
42
43pub static PRIVATE_KEY_OPS: PrivateKeyOps = PrivateKeyOps {
44 common: &COMMON_OPS,
45 elem_inv_squared: p384_elem_inv_squared,
46 point_mul_base_impl: p384_point_mul_base_impl,
47 point_mul_impl: p384_point_mul,
48 point_add_jacobian_impl: p384_point_add,
49};
50
51fn p384_elem_inv_squared(q: &Modulus<Q>, a: &Elem<R>) -> Elem<R> {
52 // Calculate a**-2 (mod q) == a**(q - 3) (mod q)
53 //
54 // The exponent (q - 3) is:
55 //
56 // 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe\
57 // ffffffff0000000000000000fffffffc
58
59 #[inline]
60 fn sqr_mul(q: &Modulus<Q>, a: &Elem<R>, squarings: LeakyWord, b: &Elem<R>) -> Elem<R> {
61 elem_sqr_mul(&COMMON_OPS, a, squarings, b, q.cpu())
62 }
63
64 #[inline]
65 fn sqr_mul_acc(q: &Modulus<Q>, a: &mut Elem<R>, squarings: LeakyWord, b: &Elem<R>) {
66 elem_sqr_mul_acc(&COMMON_OPS, a, squarings, b, q.cpu())
67 }
68
69 let b_1 = &a;
70 let b_11 = sqr_mul(q, b_1, 1, b_1);
71 let b_111 = sqr_mul(q, &b_11, 1, b_1);
72 let f_11 = sqr_mul(q, &b_111, 3, &b_111);
73 let fff = sqr_mul(q, &f_11, 6, &f_11);
74 let fff_111 = sqr_mul(q, &fff, 3, &b_111);
75 let fffffff_11 = sqr_mul(q, &fff_111, 15, &fff_111);
76
77 let fffffffffffffff = sqr_mul(q, &fffffff_11, 30, &fffffff_11);
78
79 let ffffffffffffffffffffffffffffff = sqr_mul(q, &fffffffffffffff, 60, &fffffffffffffff);
80
81 // ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
82 let mut acc = sqr_mul(
83 q,
84 &ffffffffffffffffffffffffffffff,
85 120,
86 &ffffffffffffffffffffffffffffff,
87 );
88
89 // fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff_111
90 sqr_mul_acc(q, &mut acc, 15, &fff_111);
91
92 // fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff
93 sqr_mul_acc(q, &mut acc, 1 + 30, &fffffff_11);
94 sqr_mul_acc(q, &mut acc, 2, &b_11);
95
96 // fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff
97 // 0000000000000000fffffff_11
98 sqr_mul_acc(q, &mut acc, 64 + 30, &fffffff_11);
99
100 // fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff
101 // 0000000000000000fffffffc
102 q.elem_square(&mut acc);
103 q.elem_square(&mut acc);
104
105 acc
106}
107
108fn p384_point_mul_base_impl(a: &Scalar, cpu: cpu::Features) -> Point {
109 // XXX: Not efficient. TODO: Precompute multiples of the generator.
110 let generator: (Elem, Elem) = (Elem::from(&GENERATOR.0), Elem::from(&GENERATOR.1));
111 PRIVATE_KEY_OPS.point_mul(p_scalar:a, &generator, cpu)
112}
113
114pub static PUBLIC_KEY_OPS: PublicKeyOps = PublicKeyOps {
115 common: &COMMON_OPS,
116};
117
118pub static SCALAR_OPS: ScalarOps = ScalarOps {
119 common: &COMMON_OPS,
120 scalar_mul_mont: p384_scalar_mul_mont,
121};
122
123pub static PUBLIC_SCALAR_OPS: PublicScalarOps = PublicScalarOps {
124 scalar_ops: &SCALAR_OPS,
125 public_key_ops: &PUBLIC_KEY_OPS,
126 twin_mul: |g_scalar: &Elem, p_scalar: &Elem, p_xy: &(Elem, Elem), cpu: Features| {
127 twin_mul_inefficient(&PRIVATE_KEY_OPS, g_scalar, p_scalar, p_xy, cpu)
128 },
129
130 q_minus_n: PublicElem::from_hex("389cb27e0bc8d21fa7e5f24cb74f58851313e696333ad68c"),
131
132 // TODO: Use an optimized variable-time implementation.
133 scalar_inv_to_mont_vartime: |s: &Elem, cpu: Features| PRIVATE_SCALAR_OPS.scalar_inv_to_mont(a:s, cpu),
134};
135
136pub static PRIVATE_SCALAR_OPS: PrivateScalarOps = PrivateScalarOps {
137 scalar_ops: &SCALAR_OPS,
138
139 oneRR_mod_n: PublicScalar::from_hex("c84ee012b39bf213fb05b7a28266895d40d49174aab1cc5bc3e483afcb82947ff3d81e5df1aa4192d319b2419b409a9"),
140 scalar_inv_to_mont: p384_scalar_inv_to_mont,
141};
142
143fn p384_scalar_inv_to_mont(a: Scalar<R>, _cpu: cpu::Features) -> Scalar<R> {
144 // Calculate the modular inverse of scalar |a| using Fermat's Little
145 // Theorem:
146 //
147 // a**-1 (mod n) == a**(n - 2) (mod n)
148 //
149 // The exponent (n - 2) is:
150 //
151 // 0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf\
152 // 581a0db248b0a77aecec196accc52971
153
154 fn mul(a: &Scalar<R>, b: &Scalar<R>) -> Scalar<R> {
155 binary_op(p384_scalar_mul_mont, a, b)
156 }
157
158 fn sqr(a: &Scalar<R>) -> Scalar<R> {
159 binary_op(p384_scalar_mul_mont, a, a)
160 }
161
162 fn sqr_mut(a: &mut Scalar<R>) {
163 unary_op_from_binary_op_assign(p384_scalar_mul_mont, a);
164 }
165
166 // Returns (`a` squared `squarings` times) * `b`.
167 fn sqr_mul(a: &Scalar<R>, squarings: LeakyWord, b: &Scalar<R>) -> Scalar<R> {
168 debug_assert!(squarings >= 1);
169 let mut tmp = sqr(a);
170 for _ in 1..squarings {
171 sqr_mut(&mut tmp);
172 }
173 mul(&tmp, b)
174 }
175
176 // Sets `acc` = (`acc` squared `squarings` times) * `b`.
177 fn sqr_mul_acc(acc: &mut Scalar<R>, squarings: LeakyWord, b: &Scalar<R>) {
178 debug_assert!(squarings >= 1);
179 for _ in 0..squarings {
180 sqr_mut(acc);
181 }
182 binary_op_assign(p384_scalar_mul_mont, acc, b)
183 }
184
185 // Indexes into `d`.
186 const B_1: usize = 0;
187 const B_11: usize = 1;
188 const B_101: usize = 2;
189 const B_111: usize = 3;
190 const B_1001: usize = 4;
191 const B_1011: usize = 5;
192 const B_1101: usize = 6;
193 const B_1111: usize = 7;
194 const DIGIT_COUNT: usize = 8;
195
196 let mut d = [Scalar::zero(); DIGIT_COUNT];
197 d[B_1] = a;
198 let b_10 = sqr(&d[B_1]);
199 for i in B_11..DIGIT_COUNT {
200 d[i] = mul(&d[i - 1], &b_10);
201 }
202
203 let ff = sqr_mul(&d[B_1111], 0 + 4, &d[B_1111]);
204 let ffff = sqr_mul(&ff, 0 + 8, &ff);
205 let ffffffff = sqr_mul(&ffff, 0 + 16, &ffff);
206
207 let ffffffffffffffff = sqr_mul(&ffffffff, 0 + 32, &ffffffff);
208
209 let ffffffffffffffffffffffff = sqr_mul(&ffffffffffffffff, 0 + 32, &ffffffff);
210
211 // ffffffffffffffffffffffffffffffffffffffffffffffff
212 let mut acc = sqr_mul(&ffffffffffffffffffffffff, 0 + 96, &ffffffffffffffffffffffff);
213
214 // The rest of the exponent, in binary, is:
215 //
216 // 1100011101100011010011011000000111110100001101110010110111011111
217 // 0101100000011010000011011011001001001000101100001010011101111010
218 // 1110110011101100000110010110101011001100110001010010100101110001
219
220 #[allow(clippy::cast_possible_truncation)]
221 static REMAINING_WINDOWS: [(u8, u8); 39] = [
222 (2, B_11 as u8),
223 (3 + 3, B_111 as u8),
224 (1 + 2, B_11 as u8),
225 (3 + 2, B_11 as u8),
226 (1 + 4, B_1001 as u8),
227 (4, B_1011 as u8),
228 (6 + 4, B_1111 as u8),
229 (3, B_101 as u8),
230 (4 + 1, B_1 as u8),
231 (4, B_1011 as u8),
232 (4, B_1001 as u8),
233 (1 + 4, B_1101 as u8),
234 (4, B_1101 as u8),
235 (4, B_1111 as u8),
236 (1 + 4, B_1011 as u8),
237 (6 + 4, B_1101 as u8),
238 (5 + 4, B_1101 as u8),
239 (4, B_1011 as u8),
240 (2 + 4, B_1001 as u8),
241 (2 + 1, B_1 as u8),
242 (3 + 4, B_1011 as u8),
243 (4 + 3, B_101 as u8),
244 (2 + 3, B_111 as u8),
245 (1 + 4, B_1111 as u8),
246 (1 + 4, B_1011 as u8),
247 (4, B_1011 as u8),
248 (2 + 3, B_111 as u8),
249 (1 + 2, B_11 as u8),
250 (5 + 2, B_11 as u8),
251 (2 + 4, B_1011 as u8),
252 (1 + 3, B_101 as u8),
253 (1 + 2, B_11 as u8),
254 (2 + 2, B_11 as u8),
255 (2 + 2, B_11 as u8),
256 (3 + 3, B_101 as u8),
257 (2 + 3, B_101 as u8),
258 (2 + 3, B_101 as u8),
259 (2, B_11 as u8),
260 (3 + 1, B_1 as u8),
261 ];
262
263 for &(squarings, digit) in &REMAINING_WINDOWS[..] {
264 sqr_mul_acc(&mut acc, LeakyWord::from(squarings), &d[usize::from(digit)]);
265 }
266
267 acc
268}
269
270unsafe extern "C" fn p384_elem_sqr_mont(
271 r: *mut Limb, // [COMMON_OPS.num_limbs]
272 a: *const Limb, // [COMMON_OPS.num_limbs]
273) {
274 // XXX: Inefficient. TODO: Make a dedicated squaring routine.
275 unsafe {
276 p384_elem_mul_mont(r, a, b:a);
277 }
278}
279
280prefixed_extern! {
281 fn p384_elem_mul_mont(
282 r: *mut Limb, // [COMMON_OPS.num_limbs]
283 a: *const Limb, // [COMMON_OPS.num_limbs]
284 b: *const Limb, // [COMMON_OPS.num_limbs]
285 );
286
287 fn p384_point_add(
288 r: *mut Limb, // [3][COMMON_OPS.num_limbs]
289 a: *const Limb, // [3][COMMON_OPS.num_limbs]
290 b: *const Limb, // [3][COMMON_OPS.num_limbs]
291 );
292 fn p384_point_mul(
293 r: *mut Limb, // [3][COMMON_OPS.num_limbs]
294 p_scalar: *const Limb, // [COMMON_OPS.num_limbs]
295 p_x: *const Limb, // [COMMON_OPS.num_limbs]
296 p_y: *const Limb, // [COMMON_OPS.num_limbs]
297 );
298
299 fn p384_scalar_mul_mont(
300 r: *mut Limb, // [COMMON_OPS.num_limbs]
301 a: *const Limb, // [COMMON_OPS.num_limbs]
302 b: *const Limb, // [COMMON_OPS.num_limbs]
303 );
304}
305