2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to deal in the Software without restriction, including
7 * without limitation the rights to use, copy, modify, merge, publish,
8 * distribute, sublicense, and/or sell copies of the Software, and to
9 * permit persons to whom the Software is furnished to do so, subject to
10 * the following conditions:
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 #ifndef BR_BEARSSL_RSA_H__
26 #define BR_BEARSSL_RSA_H__
31 /** \file bearssl_rsa.h
35 * This file documents the RSA implementations provided with BearSSL.
36 * Note that the SSL engine accesses these implementations through a
37 * configurable API, so it is possible to, for instance, run a SSL
38 * server which uses a RSA engine which is not based on this code.
42 * RSA public and private keys consist in lists of big integers. All
43 * such integers are represented with big-endian unsigned notation:
44 * first byte is the most significant, and the value is positive (so
45 * there is no dedicated "sign bit"). Public and private key structures
46 * thus contain, for each such integer, a pointer to the first value byte
47 * (`unsigned char *`), and a length (`size_t`) which is the number of
48 * relevant bytes. As a general rule, minimal-length encoding is not
49 * enforced: values may have extra leading bytes of value 0.
51 * RSA public keys consist in two integers:
53 * - the modulus (`n`);
54 * - the public exponent (`e`).
56 * RSA private keys, as defined in
57 * [PKCS#1](https://tools.ietf.org/html/rfc3447), contain eight integers:
59 * - the modulus (`n`);
60 * - the public exponent (`e`);
61 * - the private exponent (`d`);
62 * - the first prime factor (`p`);
63 * - the second prime factor (`q`);
64 * - the first reduced exponent (`dp`, which is `d` modulo `p-1`);
65 * - the second reduced exponent (`dq`, which is `d` modulo `q-1`);
66 * - the CRT coefficient (`iq`, the inverse of `q` modulo `p`).
68 * However, the implementations defined in BearSSL use only five of
69 * these integers: `p`, `q`, `dp`, `dq` and `iq`.
71 * ## Security Features and Limitations
73 * The implementations contained in BearSSL have the following limitations
76 * - They are constant-time. This means that the execution time and
77 * memory access pattern may depend on the _lengths_ of the private
78 * key components, but not on their value, nor on the value of
79 * the operand. Note that this property is not achieved through
80 * random masking, but "true" constant-time code.
82 * - They support only private keys with two prime factors. RSA private
83 * key with three or more prime factors are nominally supported, but
84 * rarely used; they may offer faster operations, at the expense of
85 * more code and potentially a reduction in security if there are
86 * "too many" prime factors.
88 * - The public exponent may have arbitrary length. Of course, it is
89 * a good idea to keep public exponents small, so that public key
90 * operations are fast; but, contrary to some widely deployed
91 * implementations, BearSSL has no problem with public exponent
92 * longer than 32 bits.
94 * - The two prime factors of the modulus need not have the same length
95 * (but severely imbalanced factor lengths might reduce security).
96 * Similarly, there is no requirement that the first factor (`p`)
97 * be greater than the second factor (`q`).
99 * - Prime factors and modulus must be smaller than a compile-time limit.
100 * This is made necessary by the use of fixed-size stack buffers, and
101 * the limit has been adjusted to keep stack usage under 2 kB for the
102 * RSA operations. Currently, the maximum modulus size is 4096 bits,
103 * and the maximum prime factor size is 2080 bits.
105 * - The RSA functions themselves do not enforce lower size limits,
106 * except that which is absolutely necessary for the operation to
107 * mathematically make sense (e.g. a PKCS#1 v1.5 signature with
108 * SHA-1 requires a modulus of at least 361 bits). It is up to users
109 * of this code to enforce size limitations when appropriate (e.g.
110 * the X.509 validation engine, by default, rejects RSA keys of
111 * less than 1017 bits).
113 * - Within the size constraints expressed above, arbitrary bit lengths
114 * are supported. There is no requirement that prime factors or
115 * modulus have a size multiple of 8 or 16.
117 * - When verifying PKCS#1 v1.5 signatures, both variants of the hash
118 * function identifying header (with and without the ASN.1 NULL) are
119 * supported. When producing such signatures, the variant with the
120 * ASN.1 NULL is used.
124 * Three RSA implementations are included:
126 * - The **i32** implementation internally represents big integers
127 * as arrays of 32-bit integers. It is perfunctory and portable,
128 * but not very efficient.
130 * - The **i31** implementation uses 32-bit integers, each containing
131 * 31 bits worth of integer data. The i31 implementation is somewhat
132 * faster than the i32 implementation (the reduced integer size makes
133 * carry propagation easier) for a similar code footprint, but uses
134 * very slightly larger stack buffers (about 4% bigger).
136 * - The **i15** implementation uses 16-bit integers, each containing
137 * 15 bits worth of integer data. Multiplication results fit on
138 * 32 bits, so this won't use the "widening" multiplication routine
139 * on ARM Cortex M0/M0+, for much better performance and constant-time
144 * \brief RSA public key.
146 * The structure references the modulus and the public exponent. Both
147 * integers use unsigned big-endian representation; extra leading bytes
148 * of value 0 are allowed.
151 /** \brief Modulus. */
153 /** \brief Modulus length (in bytes). */
155 /** \brief Public exponent. */
157 /** \brief Public exponent length (in bytes). */
162 * \brief RSA private key.
164 * The structure references the primvate factors, reduced private
165 * exponents, and CRT coefficient. It also contains the bit length of
166 * the modulus. The big integers use unsigned big-endian representation;
167 * extra leading bytes of value 0 are allowed. However, the modulus bit
168 * length (`n_bitlen`) MUST be exact.
171 /** \brief Modulus bit length (in bits, exact value). */
173 /** \brief First prime factor. */
175 /** \brief First prime factor length (in bytes). */
177 /** \brief Second prime factor. */
179 /** \brief Second prime factor length (in bytes). */
181 /** \brief First reduced private exponent. */
183 /** \brief First reduced private exponent length (in bytes). */
185 /** \brief Second reduced private exponent. */
187 /** \brief Second reduced private exponent length (in bytes). */
189 /** \brief CRT coefficient. */
191 /** \brief CRT coefficient length (in bytes). */
193 } br_rsa_private_key
;
196 * \brief Type for a RSA public key engine.
198 * The public key engine performs the modular exponentiation of the
199 * provided value with the public exponent. The value is modified in
202 * The value length (`xlen`) is verified to have _exactly_ the same
203 * length as the modulus (actual modulus length, without extra leading
204 * zeros in the modulus representation in memory). If the length does
205 * not match, then this function returns 0 and `x[]` is unmodified.
207 * It `xlen` is correct, then `x[]` is modified. Returned value is 1
208 * on success, 0 on error. Error conditions include an oversized `x[]`
209 * (the array has the same length as the modulus, but the numerical value
210 * is not lower than the modulus) and an invalid modulus (e.g. an even
211 * integer). If an error is reported, then the new contents of `x[]` are
214 * \param x operand to exponentiate.
215 * \param xlen length of the operand (in bytes).
216 * \param pk RSA public key.
217 * \return 1 on success, 0 on error.
219 typedef uint32_t (*br_rsa_public
)(unsigned char *x
, size_t xlen
,
220 const br_rsa_public_key
*pk
);
223 * \brief Type for a RSA signature verification engine (PKCS#1 v1.5).
227 * - The signature itself. The provided array is NOT modified.
229 * - The encoded OID for the hash function. The provided array must begin
230 * with a single byte that contains the length of the OID value (in
231 * bytes), followed by exactly that many bytes. This parameter may
232 * also be `NULL`, in which case the raw hash value should be used
233 * with the PKCS#1 v1.5 "type 1" padding (as used in SSL/TLS up
234 * to TLS-1.1, with a 36-byte hash value).
236 * - The hash output length, in bytes.
240 * - An output buffer for the hash value. The caller must still compare
241 * it with the hash of the data over which the signature is computed.
245 * - Hash length MUST be no more than 64 bytes.
247 * - OID value length MUST be no more than 32 bytes (i.e. `hash_oid[0]`
248 * must have a value in the 0..32 range, inclusive).
250 * This function verifies that the signature length (`xlen`) matches the
251 * modulus length (this function returns 0 on mismatch). If the modulus
252 * size exceeds the maximum supported RSA size, then the function also
255 * Returned value is 1 on success, 0 on error.
257 * Implementations of this type need not be constant-time.
259 * \param x signature buffer.
260 * \param xlen signature length (in bytes).
261 * \param hash_oid encoded hash algorithm OID (or `NULL`).
262 * \param hash_len expected hash value length (in bytes).
263 * \param pk RSA public key.
264 * \param hash_out output buffer for the hash value.
265 * \return 1 on success, 0 on error.
267 typedef uint32_t (*br_rsa_pkcs1_vrfy
)(const unsigned char *x
, size_t xlen
,
268 const unsigned char *hash_oid
, size_t hash_len
,
269 const br_rsa_public_key
*pk
, unsigned char *hash_out
);
272 * \brief Type for a RSA private key engine.
274 * The `x[]` buffer is modified in place, and its length is inferred from
275 * the modulus length (`x[]` is assumed to have a length of
276 * `(sk->n_bitlen+7)/8` bytes).
278 * Returned value is 1 on success, 0 on error.
280 * \param x operand to exponentiate.
281 * \param sk RSA private key.
282 * \return 1 on success, 0 on error.
284 typedef uint32_t (*br_rsa_private
)(unsigned char *x
,
285 const br_rsa_private_key
*sk
);
288 * \brief Type for a RSA signature generation engine (PKCS#1 v1.5).
292 * - The encoded OID for the hash function. The provided array must begin
293 * with a single byte that contains the length of the OID value (in
294 * bytes), followed by exactly that many bytes. This parameter may
295 * also be `NULL`, in which case the raw hash value should be used
296 * with the PKCS#1 v1.5 "type 1" padding (as used in SSL/TLS up
297 * to TLS-1.1, with a 36-byte hash value).
299 * - The hash value computes over the data to sign (its length is
300 * expressed in bytes).
302 * - The RSA private key.
304 * - The output buffer, that receives the signature.
306 * Returned value is 1 on success, 0 on error. Error conditions include
307 * a too small modulus for the provided hash OID and value, or some
308 * invalid key parameters. The signature length is exactly
309 * `(sk->n_bitlen+7)/8` bytes.
311 * This function is expected to be constant-time with regards to the
312 * private key bytes (lengths of the modulus and the individual factors
313 * may leak, though) and to the hashed data.
315 * \param hash_oid encoded hash algorithm OID (or `NULL`).
316 * \param hash hash value.
317 * \param hash_len hash value length (in bytes).
318 * \param sk RSA private key.
319 * \param x output buffer for the signature value.
320 * \return 1 on success, 0 on error.
322 typedef uint32_t (*br_rsa_pkcs1_sign
)(const unsigned char *hash_oid
,
323 const unsigned char *hash
, size_t hash_len
,
324 const br_rsa_private_key
*sk
, unsigned char *x
);
327 * RSA "i32" engine. Integers are internally represented as arrays of
328 * 32-bit integers, and the core multiplication primitive is the
329 * 32x32->64 multiplication.
333 * \brief RSA public key engine "i32".
337 * \param x operand to exponentiate.
338 * \param xlen length of the operand (in bytes).
339 * \param pk RSA public key.
340 * \return 1 on success, 0 on error.
342 uint32_t br_rsa_i32_public(unsigned char *x
, size_t xlen
,
343 const br_rsa_public_key
*pk
);
346 * \brief RSA signature verification engine "i32".
348 * \see br_rsa_pkcs1_vrfy
350 * \param x signature buffer.
351 * \param xlen signature length (in bytes).
352 * \param hash_oid encoded hash algorithm OID (or `NULL`).
353 * \param hash_len expected hash value length (in bytes).
354 * \param pk RSA public key.
355 * \param hash_out output buffer for the hash value.
356 * \return 1 on success, 0 on error.
358 uint32_t br_rsa_i32_pkcs1_vrfy(const unsigned char *x
, size_t xlen
,
359 const unsigned char *hash_oid
, size_t hash_len
,
360 const br_rsa_public_key
*pk
, unsigned char *hash_out
);
363 * \brief RSA private key engine "i32".
365 * \see br_rsa_private
367 * \param x operand to exponentiate.
368 * \param sk RSA private key.
369 * \return 1 on success, 0 on error.
371 uint32_t br_rsa_i32_private(unsigned char *x
,
372 const br_rsa_private_key
*sk
);
375 * \brief RSA signature generation engine "i32".
377 * \see br_rsa_pkcs1_sign
379 * \param hash_oid encoded hash algorithm OID (or `NULL`).
380 * \param hash hash value.
381 * \param hash_len hash value length (in bytes).
382 * \param sk RSA private key.
383 * \param x output buffer for the hash value.
384 * \return 1 on success, 0 on error.
386 uint32_t br_rsa_i32_pkcs1_sign(const unsigned char *hash_oid
,
387 const unsigned char *hash
, size_t hash_len
,
388 const br_rsa_private_key
*sk
, unsigned char *x
);
391 * RSA "i31" engine. Similar to i32, but only 31 bits are used per 32-bit
392 * word. This uses slightly more stack space (about 4% more) and code
393 * space, but it quite faster.
397 * \brief RSA public key engine "i31".
401 * \param x operand to exponentiate.
402 * \param xlen length of the operand (in bytes).
403 * \param pk RSA public key.
404 * \return 1 on success, 0 on error.
406 uint32_t br_rsa_i31_public(unsigned char *x
, size_t xlen
,
407 const br_rsa_public_key
*pk
);
410 * \brief RSA signature verification engine "i31".
412 * \see br_rsa_pkcs1_vrfy
414 * \param x signature buffer.
415 * \param xlen signature length (in bytes).
416 * \param hash_oid encoded hash algorithm OID (or `NULL`).
417 * \param hash_len expected hash value length (in bytes).
418 * \param pk RSA public key.
419 * \param hash_out output buffer for the hash value.
420 * \return 1 on success, 0 on error.
422 uint32_t br_rsa_i31_pkcs1_vrfy(const unsigned char *x
, size_t xlen
,
423 const unsigned char *hash_oid
, size_t hash_len
,
424 const br_rsa_public_key
*pk
, unsigned char *hash_out
);
427 * \brief RSA private key engine "i31".
429 * \see br_rsa_private
431 * \param x operand to exponentiate.
432 * \param sk RSA private key.
433 * \return 1 on success, 0 on error.
435 uint32_t br_rsa_i31_private(unsigned char *x
,
436 const br_rsa_private_key
*sk
);
439 * \brief RSA signature generation engine "i31".
441 * \see br_rsa_pkcs1_sign
443 * \param hash_oid encoded hash algorithm OID (or `NULL`).
444 * \param hash hash value.
445 * \param hash_len hash value length (in bytes).
446 * \param sk RSA private key.
447 * \param x output buffer for the hash value.
448 * \return 1 on success, 0 on error.
450 uint32_t br_rsa_i31_pkcs1_sign(const unsigned char *hash_oid
,
451 const unsigned char *hash
, size_t hash_len
,
452 const br_rsa_private_key
*sk
, unsigned char *x
);
455 * RSA "i15" engine. Integers are represented as 15-bit integers, so
456 * the code uses only 32-bit multiplication (no 64-bit result), which
457 * is vastly faster (and constant-time) on the ARM Cortex M0/M0+.
461 * \brief RSA public key engine "i15".
465 * \param x operand to exponentiate.
466 * \param xlen length of the operand (in bytes).
467 * \param pk RSA public key.
468 * \return 1 on success, 0 on error.
470 uint32_t br_rsa_i15_public(unsigned char *x
, size_t xlen
,
471 const br_rsa_public_key
*pk
);
474 * \brief RSA signature verification engine "i15".
476 * \see br_rsa_pkcs1_vrfy
478 * \param x signature buffer.
479 * \param xlen signature length (in bytes).
480 * \param hash_oid encoded hash algorithm OID (or `NULL`).
481 * \param hash_len expected hash value length (in bytes).
482 * \param pk RSA public key.
483 * \param hash_out output buffer for the hash value.
484 * \return 1 on success, 0 on error.
486 uint32_t br_rsa_i15_pkcs1_vrfy(const unsigned char *x
, size_t xlen
,
487 const unsigned char *hash_oid
, size_t hash_len
,
488 const br_rsa_public_key
*pk
, unsigned char *hash_out
);
491 * \brief RSA private key engine "i15".
493 * \see br_rsa_private
495 * \param x operand to exponentiate.
496 * \param sk RSA private key.
497 * \return 1 on success, 0 on error.
499 uint32_t br_rsa_i15_private(unsigned char *x
,
500 const br_rsa_private_key
*sk
);
503 * \brief RSA signature generation engine "i15".
505 * \see br_rsa_pkcs1_sign
507 * \param hash_oid encoded hash algorithm OID (or `NULL`).
508 * \param hash hash value.
509 * \param hash_len hash value length (in bytes).
510 * \param sk RSA private key.
511 * \param x output buffer for the hash value.
512 * \return 1 on success, 0 on error.
514 uint32_t br_rsa_i15_pkcs1_sign(const unsigned char *hash_oid
,
515 const unsigned char *hash
, size_t hash_len
,
516 const br_rsa_private_key
*sk
, unsigned char *x
);
519 * \brief RSA decryption helper, for SSL/TLS.
521 * This function performs the RSA decryption for a RSA-based key exchange
522 * in a SSL/TLS server. The provided RSA engine is used. The `data`
523 * parameter points to the value to decrypt, of length `len` bytes. On
524 * success, the 48-byte pre-master secret is copied into `data`, starting
525 * at the first byte of that buffer; on error, the contents of `data`
526 * become indeterminate.
528 * This function first checks that the provided value length (`len`) is
529 * not lower than 59 bytes, and matches the RSA modulus length; if neither
530 * of this property is met, then this function returns 0 and the buffer
533 * Otherwise, decryption and then padding verification are performed, both
534 * in constant-time. A decryption error, or a bad padding, or an
535 * incorrect decrypted value length are reported with a returned value of
536 * 0; on success, 1 is returned. The caller (SSL server engine) is supposed
537 * to proceed with a random pre-master secret in case of error.
539 * \param core RSA private key engine.
540 * \param sk RSA private key.
541 * \param data input/output buffer.
542 * \param len length (in bytes) of the data to decrypt.
543 * \return 1 on success, 0 on error.
545 uint32_t br_rsa_ssl_decrypt(br_rsa_private core
, const br_rsa_private_key
*sk
,
546 unsigned char *data
, size_t len
);