1// Copyright 2015-2021 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::{PublicExponent, PublicModulus, N, PUBLIC_KEY_PUBLIC_MODULUS_MAX_LEN};
16use crate::{
17 arithmetic::bigint,
18 bits, cpu, error,
19 io::{self, der, der_writer},
20 limb::LIMB_BYTES,
21};
22use alloc::boxed::Box;
23use core::num::NonZeroU64;
24
25/// An RSA Public Key.
26#[derive(Clone)]
27pub struct PublicKey {
28 inner: Inner,
29 serialized: Box<[u8]>,
30}
31
32derive_debug_self_as_ref_hex_bytes!(PublicKey);
33
34impl PublicKey {
35 pub(super) fn from_modulus_and_exponent(
36 n: untrusted::Input,
37 e: untrusted::Input,
38 n_min_bits: bits::BitLength,
39 n_max_bits: bits::BitLength,
40 e_min_value: PublicExponent,
41 cpu_features: cpu::Features,
42 ) -> Result<Self, error::KeyRejected> {
43 let inner = Inner::from_modulus_and_exponent(
44 n,
45 e,
46 n_min_bits,
47 n_max_bits,
48 e_min_value,
49 cpu_features,
50 )?;
51
52 let n_bytes = n;
53 let e_bytes = e;
54
55 // TODO: Remove this re-parsing, and stop allocating this here.
56 // Instead we should serialize on demand without allocation, from
57 // `Modulus::be_bytes()` and `Exponent::be_bytes()`. Once this is
58 // fixed, merge `Inner` back into `PublicKey`.
59 let n_bytes = io::Positive::from_be_bytes(n_bytes)
60 .map_err(|_: error::Unspecified| error::KeyRejected::unexpected_error())?;
61 let e_bytes = io::Positive::from_be_bytes(e_bytes)
62 .map_err(|_: error::Unspecified| error::KeyRejected::unexpected_error())?;
63 let serialized = der_writer::write_all(der::Tag::Sequence, &|output| {
64 der_writer::write_positive_integer(output, &n_bytes);
65 der_writer::write_positive_integer(output, &e_bytes);
66 });
67
68 Ok(Self { inner, serialized })
69 }
70
71 /// The length, in bytes, of the public modulus.
72 ///
73 /// The modulus length is rounded up to a whole number of bytes if its
74 /// bit length isn't a multiple of 8.
75 pub fn modulus_len(&self) -> usize {
76 self.inner.n().len_bits().as_usize_bytes_rounded_up()
77 }
78
79 pub(super) fn inner(&self) -> &Inner {
80 &self.inner
81 }
82}
83
84/// `PublicKey` but without any superfluous allocations, optimized for one-shot
85/// RSA signature verification.
86#[derive(Clone)]
87pub(crate) struct Inner {
88 n: PublicModulus,
89 e: PublicExponent,
90}
91
92impl Inner {
93 pub(super) fn from_modulus_and_exponent(
94 n: untrusted::Input,
95 e: untrusted::Input,
96 n_min_bits: bits::BitLength,
97 n_max_bits: bits::BitLength,
98 e_min_value: PublicExponent,
99 cpu_features: cpu::Features,
100 ) -> Result<Self, error::KeyRejected> {
101 // This is an incomplete implementation of NIST SP800-56Br1 Section
102 // 6.4.2.2, "Partial Public-Key Validation for RSA." That spec defers
103 // to NIST SP800-89 Section 5.3.3, "(Explicit) Partial Public Key
104 // Validation for RSA," "with the caveat that the length of the modulus
105 // shall be a length that is specified in this Recommendation." In
106 // SP800-89, two different sets of steps are given, one set numbered,
107 // and one set lettered. TODO: Document this in the end-user
108 // documentation for RSA keys.
109
110 let n = PublicModulus::from_be_bytes(n, n_min_bits..=n_max_bits, cpu_features)?;
111
112 let e = PublicExponent::from_be_bytes(e, e_min_value)?;
113
114 // If `n` is less than `e` then somebody has probably accidentally swapped
115 // them. The largest acceptable `e` is smaller than the smallest acceptable
116 // `n`, so no additional checks need to be done.
117
118 // XXX: Steps 4 & 5 / Steps d, e, & f are not implemented. This is also the
119 // case in most other commonly-used crypto libraries.
120
121 Ok(Self { n, e })
122 }
123
124 /// The public modulus.
125 #[inline]
126 pub(super) fn n(&self) -> &PublicModulus {
127 &self.n
128 }
129
130 /// The public exponent.
131 #[inline]
132 pub(super) fn e(&self) -> PublicExponent {
133 self.e
134 }
135
136 /// Calculates base**e (mod n), filling the first part of `out_buffer` with
137 /// the result.
138 ///
139 /// This is constant-time with respect to the value in `base` (only).
140 ///
141 /// The result will be a slice of the encoded bytes of the result within
142 /// `out_buffer`, if successful.
143 pub(super) fn exponentiate<'out>(
144 &self,
145 base: untrusted::Input,
146 out_buffer: &'out mut [u8; PUBLIC_KEY_PUBLIC_MODULUS_MAX_LEN],
147 cpu_features: cpu::Features,
148 ) -> Result<&'out [u8], error::Unspecified> {
149 let n = &self.n.value(cpu_features);
150
151 // The encoded value of the base must be the same length as the modulus,
152 // in bytes.
153 if base.len() != self.n.len_bits().as_usize_bytes_rounded_up() {
154 return Err(error::Unspecified);
155 }
156
157 // RFC 8017 Section 5.2.2: RSAVP1.
158
159 // Step 1.
160 let s = bigint::Elem::from_be_bytes_padded(base, n)?;
161 if s.is_zero() {
162 return Err(error::Unspecified);
163 }
164
165 // Step 2.
166 let m = self.exponentiate_elem(&s, cpu_features);
167
168 // Step 3.
169 Ok(fill_be_bytes_n(m, self.n.len_bits(), out_buffer))
170 }
171
172 /// Calculates base**e (mod n).
173 ///
174 /// This is constant-time with respect to `base` only.
175 pub(super) fn exponentiate_elem(
176 &self,
177 base: &bigint::Elem<N>,
178 cpu_features: cpu::Features,
179 ) -> bigint::Elem<N> {
180 // The exponent was already checked to be at least 3.
181 let exponent_without_low_bit = NonZeroU64::try_from(self.e.value().get() & !1).unwrap();
182 // The exponent was already checked to be odd.
183 debug_assert_ne!(exponent_without_low_bit, self.e.value());
184
185 let n = &self.n.value(cpu_features);
186
187 let base_r = bigint::elem_mul(self.n.oneRR(), base.clone(), n);
188
189 // During RSA public key operations the exponent is almost always either
190 // 65537 (0b10000000000000001) or 3 (0b11), both of which have a Hamming
191 // weight of 2. The maximum bit length and maximum Hamming weight of the
192 // exponent is bounded by the value of `PublicExponent::MAX`.
193 let acc = bigint::elem_exp_vartime(base_r, exponent_without_low_bit, n);
194
195 // Now do the multiplication for the low bit and convert out of the Montgomery domain.
196 bigint::elem_mul(base, acc, n)
197 }
198}
199
200// XXX: Refactor `signature::KeyPair` to get rid of this.
201impl AsRef<[u8]> for PublicKey {
202 fn as_ref(&self) -> &[u8] {
203 &self.serialized
204 }
205}
206
207/// Returns the big-endian representation of `elem` that is
208/// the same length as the minimal-length big-endian representation of
209/// the modulus `n`.
210///
211/// `n_bits` must be the bit length of the public modulus `n`.
212fn fill_be_bytes_n(
213 elem: bigint::Elem<N>,
214 n_bits: bits::BitLength,
215 out: &mut [u8; PUBLIC_KEY_PUBLIC_MODULUS_MAX_LEN],
216) -> &[u8] {
217 let n_bytes: usize = n_bits.as_usize_bytes_rounded_up();
218 let n_bytes_padded: usize = ((n_bytes + (LIMB_BYTES - 1)) / LIMB_BYTES) * LIMB_BYTES;
219 let out: &mut [u8] = &mut out[..n_bytes_padded];
220 elem.fill_be_bytes(out);
221 let (padding: &[u8], out: &[u8]) = out.split_at(mid:n_bytes_padded - n_bytes);
222 assert!(padding.iter().all(|&b| b == 0));
223 out
224}
225