ring/ec/suite_b/ops/
p384.rs

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

ring/ec/suite_b/ops/
p384.rs
