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