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