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//! Functionality shared by operations on private keys (ECC keygen and
16//! ECDSA signing).
17
18use super::{ops::*, verify_affine_point_is_on_the_curve};
19use crate::{arithmetic::montgomery::R, cpu, ec, error, limb, rand};
20
21/// Generates a random scalar in the range [1, n).
22pub(super) fn random_scalar(
23 ops: &PrivateKeyOps,
24 n: &Modulus<N>,
25 rng: &dyn rand::SecureRandom,
26) -> Result<Scalar, error::Unspecified> {
27 let mut bytes: [u8; 48] = [0; ec::SCALAR_MAX_BYTES];
28 let bytes: &mut [u8] = &mut bytes[..ops.common.len()];
29 generate_private_scalar_bytes(ops, rng, out:bytes, n.cpu())?;
30 scalar_from_big_endian_bytes(n, bytes)
31}
32
33pub(super) fn generate_private_scalar_bytes(
34 ops: &PrivateKeyOps,
35 rng: &dyn rand::SecureRandom,
36 out: &mut [u8],
37 cpu: cpu::Features,
38) -> Result<(), error::Unspecified> {
39 // [NSA Suite B Implementer's Guide to ECDSA] Appendix A.1.2, and
40 // [NSA Suite B Implementer's Guide to NIST SP 800-56A] Appendix B.2,
41 // "Key Pair Generation by Testing Candidates".
42 //
43 // [NSA Suite B Implementer's Guide to ECDSA]: doc/ecdsa.pdf
44 // [NSA Suite B Implementer's Guide to NIST SP 800-56A]: doc/ecdh.pdf
45
46 // TODO: The NSA guide also suggests, in appendix B.1, another mechanism
47 // that would avoid the need to use `rng.fill()` more than once. It works
48 // by generating an extra 64 bits of random bytes and then reducing the
49 // output (mod n). Supposedly, this removes enough of the bias towards
50 // small values from the modular reduction, but it isn't obvious that it is
51 // sufficient. TODO: Figure out what we can do to mitigate the bias issue
52 // and switch to the other mechanism.
53
54 let candidate = out;
55
56 // XXX: The value 100 was chosen to match OpenSSL due to uncertainty of
57 // what specific value would be better, but it seems bad to try 100 times.
58 for _ in 0..100 {
59 // NSA Guide Steps 1, 2, and 3.
60 //
61 // Since we calculate the length ourselves, it is pointless to check
62 // it, since we can only check it by doing the same calculation.
63
64 // NSA Guide Step 4.
65 //
66 // The requirement that the random number generator has the
67 // requested security strength is delegated to `rng`.
68 rng.fill(candidate)?;
69
70 // NSA Guide Steps 5, 6, and 7.
71 if check_scalar_big_endian_bytes(ops, candidate, cpu).is_err() {
72 continue;
73 }
74
75 // NSA Guide Step 8 is done in `public_from_private()`.
76
77 // NSA Guide Step 9.
78 return Ok(());
79 }
80
81 Err(error::Unspecified)
82}
83
84// The underlying X25519 and Ed25519 code uses an [u8; 32] to store the private
85// key. To make the ECDH and ECDSA code similar to that, we also store the
86// private key that way, which means we have to convert it to a Scalar whenever
87// we need to use it.
88#[inline]
89pub(super) fn private_key_as_scalar(n: &Modulus<N>, private_key: &ec::Seed) -> Scalar {
90 // This cannot fail because we know the private key is valid.
91 scalar_from_big_endian_bytes(n, bytes:private_key.bytes_less_safe()).unwrap()
92}
93
94pub(super) fn check_scalar_big_endian_bytes(
95 ops: &PrivateKeyOps,
96 bytes: &[u8],
97 cpu: cpu::Features,
98) -> Result<(), error::Unspecified> {
99 debug_assert_eq!(bytes.len(), ops.common.len());
100 let n: &Modulus = &ops.common.scalar_modulus(cpu);
101 scalar_from_big_endian_bytes(n, bytes).map(|_| ())
102}
103
104// Parses a fixed-length (zero-padded) big-endian-encoded scalar in the range
105// [1, n). This is constant-time with respect to the actual value *only if* the
106// value is actually in range. In other words, this won't leak anything about a
107// valid value, but it might leak small amounts of information about an invalid
108// value (which constraint it failed).
109pub(super) fn scalar_from_big_endian_bytes(
110 n: &Modulus<N>,
111 bytes: &[u8],
112) -> Result<Scalar, error::Unspecified> {
113 // [NSA Suite B Implementer's Guide to ECDSA] Appendix A.1.2, and
114 // [NSA Suite B Implementer's Guide to NIST SP 800-56A] Appendix B.2,
115 // "Key Pair Generation by Testing Candidates".
116 //
117 // [NSA Suite B Implementer's Guide to ECDSA]: doc/ecdsa.pdf
118 // [NSA Suite B Implementer's Guide to NIST SP 800-56A]: doc/ecdh.pdf
119 //
120 // Steps 5, 6, and 7.
121 //
122 // XXX: The NSA guide says that we should verify that the random scalar is
123 // in the range [0, n - 1) and then add one to it so that it is in the range
124 // [1, n). Instead, we verify that the scalar is in the range [1, n). This
125 // way, we avoid needing to compute or store the value (n - 1), we avoid the
126 // need to implement a function to add one to a scalar, and we avoid needing
127 // to convert the scalar back into an array of bytes.
128 scalar_parse_big_endian_fixed_consttime(n, bytes:untrusted::Input::from(bytes))
129}
130
131pub(super) fn public_from_private(
132 ops: &PrivateKeyOps,
133 public_out: &mut [u8],
134 my_private_key: &ec::Seed,
135 cpu: cpu::Features,
136) -> Result<(), error::Unspecified> {
137 let q: &Modulus = &ops.common.elem_modulus(cpu);
138 let elem_and_scalar_bytes: usize = ops.common.len();
139 debug_assert_eq!(public_out.len(), 1 + (2 * elem_and_scalar_bytes));
140 let n: &Modulus = &ops.common.scalar_modulus(cpu);
141 let my_private_key: Elem = private_key_as_scalar(n, my_private_key);
142 let my_public_key: Point = ops.point_mul_base(&my_private_key, cpu);
143 public_out[0] = 4; // Uncompressed encoding.
144 let (x_out: &mut [u8], y_out: &mut [u8]) = public_out[1..].split_at_mut(mid:elem_and_scalar_bytes);
145
146 // `big_endian_affine_from_jacobian` verifies that the point is not at
147 // infinity and is on the curve.
148 big_endian_affine_from_jacobian(ops, q, x_out, y_out:Some(y_out), &my_public_key)
149}
150
151pub(super) fn affine_from_jacobian(
152 ops: &PrivateKeyOps,
153 q: &Modulus<Q>,
154 p: &Point,
155) -> Result<(Elem<R>, Elem<R>), error::Unspecified> {
156 let z = q.point_z(p);
157
158 // Since we restrict our private key to the range [1, n), the curve has
159 // prime order, and we verify that the peer's point is on the curve,
160 // there's no way that the result can be at infinity. But, use `assert!`
161 // instead of `debug_assert!` anyway
162 assert!(q.elem_verify_is_not_zero(&z).is_ok());
163
164 let x = q.point_x(p);
165 let y = q.point_y(p);
166
167 let zz_inv = ops.elem_inverse_squared(q, &z);
168
169 let x_aff = q.elem_product(&x, &zz_inv);
170
171 // `y_aff` is needed to validate the point is on the curve. It is also
172 // needed in the non-ECDH case where we need to output it.
173 let y_aff = {
174 let zzzz_inv = q.elem_squared(&zz_inv);
175 let zzz_inv = q.elem_product(&z, &zzzz_inv);
176 q.elem_product(&y, &zzz_inv)
177 };
178
179 // If we validated our inputs correctly and then computed (x, y, z), then
180 // (x, y, z) will be on the curve. See
181 // `verify_affine_point_is_on_the_curve_scaled` for the motivation.
182 verify_affine_point_is_on_the_curve(q, (&x_aff, &y_aff))?;
183
184 Ok((x_aff, y_aff))
185}
186
187pub(super) fn big_endian_affine_from_jacobian(
188 ops: &PrivateKeyOps,
189 q: &Modulus<Q>,
190 x_out: &mut [u8],
191 y_out: Option<&mut [u8]>,
192 p: &Point,
193) -> Result<(), error::Unspecified> {
194 let (x_aff: Elem, y_aff: Elem) = affine_from_jacobian(ops, q, p)?;
195 let x: Elem = q.elem_unencoded(&x_aff);
196 limb::big_endian_from_limbs(ops.leak_limbs(&x), x_out);
197 if let Some(y_out: &mut [u8]) = y_out {
198 let y: Elem = q.elem_unencoded(&y_aff);
199 limb::big_endian_from_limbs(ops.leak_limbs(&y), y_out);
200 }
201
202 Ok(())
203}
204