More API documentation (Doxygen format) for EC code.
[BearSSL] / inc / bearssl_ec.h
1 /*
2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
3 *
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:
11 *
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
14 *
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
22 * SOFTWARE.
23 */
24
25 #ifndef BR_BEARSSL_EC_H__
26 #define BR_BEARSSL_EC_H__
27
28 #include <stddef.h>
29 #include <stdint.h>
30
31 /** \file bearssl_ec.h
32 *
33 * # Elliptic Curves
34 *
35 * This file documents the EC implementations provided with BearSSL, and
36 * ECDSA.
37 *
38 * ## Elliptic Curve API
39 *
40 * Only "named curves" are supported. Each EC implementation supports
41 * one or several named curves, identified by symbolic identifiers.
42 * These identifiers are small integers, that correspond to the values
43 * registered by the
44 * [IANA](http://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-8).
45 *
46 * Since all currently defined elliptic curve identifiers are in the 0..31
47 * range, it is convenient to encode support of some curves in a 32-bit
48 * word, such that bit x corresponds to curve of identifier x.
49 *
50 * An EC implementation is incarnated by a `br_ec_impl` instance, that
51 * offers the following fields:
52 *
53 * - `supported_curves`
54 *
55 * A 32-bit word that documents the identifiers of the curves supported
56 * by this implementation.
57 *
58 * - `generator()`
59 *
60 * Callback method that returns a pointer to the conventional generator
61 * point for that curve.
62 *
63 * - `order()`
64 *
65 * Callback method that returns a pointer to the subgroup order for
66 * that curve. That value uses unsigned big-endian encoding.
67 *
68 * - `mul()`
69 *
70 * Multiply a curve point with an integer.
71 *
72 * - `muladd()`
73 *
74 * Multiply two curve points by two integers, and return the sum of
75 * the two products.
76 *
77 * All curve points are represented in uncompressed format. The `mul()`
78 * and `muladd()` methods take care to validate that the provided points
79 * are really part of the relevant curve subgroup.
80 *
81 * For all point multiplication functions, the following holds:
82 *
83 * - Functions validate that the provided points are valid members
84 * of the relevant curve subgroup. An error is reported if that is
85 * not the case.
86 *
87 * - Processing is constant-time, even if the point operands are not
88 * valid. This holds for both the source and resulting points, and
89 * the multipliers (integers). Only the byte length of the provided
90 * multiplier arrays (not their actual value length in bits) may
91 * leak through timing-based side channels.
92 *
93 * - The multipliers (integers) MUST be lower than the subgroup order.
94 * If this property is not met, then the result is indeterminate,
95 * but an error value is not ncessearily returned.
96 *
97 *
98 * ## ECDSA
99 *
100 * ECDSA signatures have two standard formats, called "raw" and "asn1".
101 * Internally, such a signature is a pair of modular integers `(r,s)`.
102 * The "raw" format is the concatenation of the unsigned big-endian
103 * encodings of these two integers, possibly left-padded with zeros so
104 * that they have the same encoded length. The "asn1" format is the
105 * DER encoding of an ASN.1 structure that contains the two integer
106 * values:
107 *
108 * ECDSASignature ::= SEQUENCE {
109 * r INTEGER,
110 * s INTEGER
111 * }
112 *
113 * In general, in all of X.509 and SSL/TLS, the "asn1" format is used.
114 * BearSSL offers ECDSA implementations for both formats; conversion
115 * functions between the two formats are also provided. Conversion of a
116 * "raw" format signature into "asn1" may enlarge a signature by no more
117 * than 9 bytes for all supported curves; conversely, conversion of an
118 * "asn1" signature to "raw" may expand the signature but the "raw"
119 * length will never be more than twice the length of the "asn1" length
120 * (and usually it will be shorter).
121 *
122 * Note that for a given signature, the "raw" format is not fully
123 * deterministic, in that it does not enforce a minimal common length.
124 */
125
126 /*
127 * Standard curve ID. These ID are equal to the assigned numerical
128 * identifiers assigned to these curves for TLS:
129 * http://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-8
130 */
131
132 /** \brief Identifier for named curve sect163k1. */
133 #define BR_EC_sect163k1 1
134
135 /** \brief Identifier for named curve sect163r1. */
136 #define BR_EC_sect163r1 2
137
138 /** \brief Identifier for named curve sect163r2. */
139 #define BR_EC_sect163r2 3
140
141 /** \brief Identifier for named curve sect193r1. */
142 #define BR_EC_sect193r1 4
143
144 /** \brief Identifier for named curve sect193r2. */
145 #define BR_EC_sect193r2 5
146
147 /** \brief Identifier for named curve sect233k1. */
148 #define BR_EC_sect233k1 6
149
150 /** \brief Identifier for named curve sect233r1. */
151 #define BR_EC_sect233r1 7
152
153 /** \brief Identifier for named curve sect239k1. */
154 #define BR_EC_sect239k1 8
155
156 /** \brief Identifier for named curve sect283k1. */
157 #define BR_EC_sect283k1 9
158
159 /** \brief Identifier for named curve sect283r1. */
160 #define BR_EC_sect283r1 10
161
162 /** \brief Identifier for named curve sect409k1. */
163 #define BR_EC_sect409k1 11
164
165 /** \brief Identifier for named curve sect409r1. */
166 #define BR_EC_sect409r1 12
167
168 /** \brief Identifier for named curve sect571k1. */
169 #define BR_EC_sect571k1 13
170
171 /** \brief Identifier for named curve sect571r1. */
172 #define BR_EC_sect571r1 14
173
174 /** \brief Identifier for named curve secp160k1. */
175 #define BR_EC_secp160k1 15
176
177 /** \brief Identifier for named curve secp160r1. */
178 #define BR_EC_secp160r1 16
179
180 /** \brief Identifier for named curve secp160r2. */
181 #define BR_EC_secp160r2 17
182
183 /** \brief Identifier for named curve secp192k1. */
184 #define BR_EC_secp192k1 18
185
186 /** \brief Identifier for named curve secp192r1. */
187 #define BR_EC_secp192r1 19
188
189 /** \brief Identifier for named curve secp224k1. */
190 #define BR_EC_secp224k1 20
191
192 /** \brief Identifier for named curve secp224r1. */
193 #define BR_EC_secp224r1 21
194
195 /** \brief Identifier for named curve secp256k1. */
196 #define BR_EC_secp256k1 22
197
198 /** \brief Identifier for named curve secp256r1. */
199 #define BR_EC_secp256r1 23
200
201 /** \brief Identifier for named curve secp384r1. */
202 #define BR_EC_secp384r1 24
203
204 /** \brief Identifier for named curve secp521r1. */
205 #define BR_EC_secp521r1 25
206
207 /** \brief Identifier for named curve brainpoolP256r1. */
208 #define BR_EC_brainpoolP256r1 26
209
210 /** \brief Identifier for named curve brainpoolP384r1. */
211 #define BR_EC_brainpoolP384r1 27
212
213 /** \brief Identifier for named curve brainpoolP512r1. */
214 #define BR_EC_brainpoolP512r1 28
215
216 /**
217 * \brief Structure for an EC public key.
218 */
219 typedef struct {
220 /** \brief Identifier for the curve used by this key. */
221 int curve;
222 /** \brief Public curve point (uncompressed format). */
223 unsigned char *q;
224 /** \brief Length of public curve point (in bytes). */
225 size_t qlen;
226 } br_ec_public_key;
227
228 /**
229 * \brief Structure for an EC private key.
230 *
231 * The private key is an integer modulo the curve subgroup order. The
232 * encoding below tolerates extra leading zeros. In general, it is
233 * recommended that the private key has the same length as the curve
234 * subgroup order.
235 */
236 typedef struct {
237 /** \brief Identifier for the curve used by this key. */
238 int curve;
239 /** \brief Private key (integer, unsigned big-endian encoding). */
240 unsigned char *x;
241 /** \brief Private key length (in bytes). */
242 size_t xlen;
243 } br_ec_private_key;
244
245 /**
246 * \brief Type for an EC implementation.
247 */
248 typedef struct {
249 /**
250 * \brief Supported curves.
251 *
252 * This word is a bitfield: bit `x` is set if the curve of ID `x`
253 * is supported. E.g. an implementation supporting both NIST P-256
254 * (secp256r1, ID 23) and NIST P-384 (secp384r1, ID 24) will have
255 * value `0x01800000` in this field.
256 */
257 uint32_t supported_curves;
258
259 /**
260 * \brief Get the conventional generator.
261 *
262 * This function returns the conventional generator (encoded
263 * curve point) for the specified curve. This function MUST NOT
264 * be called if the curve is not supported.
265 *
266 * \param curve curve identifier.
267 * \param len receiver for the encoded generator length (in bytes).
268 * \return the encoded generator.
269 */
270 const unsigned char *(*generator)(int curve, size_t *len);
271
272 /**
273 * \brief Get the subgroup order.
274 *
275 * This function returns the order of the subgroup generated by
276 * the conventional generator, for the specified curve. Unsigned
277 * big-endian encoding is used. This function MUST NOT be called
278 * if the curve is not supported.
279 *
280 * \param curve curve identifier.
281 * \param len receiver for the encoded order length (in bytes).
282 * \return the encoded order.
283 */
284 const unsigned char *(*order)(int curve, size_t *len);
285
286 /**
287 * \brief Multiply a curve point by an integer.
288 *
289 * The source point is provided in array `G` (of size `Glen` bytes);
290 * the multiplication result is written over it. The multiplier
291 * `x` (of size `xlen` bytes) uses unsigned big-endian encoding.
292 *
293 * Rules:
294 *
295 * - The specified curve MUST be supported.
296 *
297 * - The source point must be a valid point on the relevant curve
298 * subgroup (and not the "point at infinity" either). If this is
299 * not the case, then this function returns an error (0).
300 *
301 * - The multiplier integer MUST be non-zero and less than the
302 * curve subgroup order. If the integer is zero, then an
303 * error is reported, but if the integer is not lower than
304 * the subgroup order, then the result is indeterminate and an
305 * error code is not guaranteed.
306 *
307 * Returned value is 1 on success, 0 on error. On error, the
308 * contents of `G` are indeterminate.
309 *
310 * \param G point to multiply.
311 * \param Glen length of the encoded point (in bytes).
312 * \param x multiplier (unsigned big-endian).
313 * \param xlen multiplier length (in bytes).
314 * \param curve curve identifier.
315 * \return 1 on success, 0 on error.
316 */
317 uint32_t (*mul)(unsigned char *G, size_t Glen,
318 const unsigned char *x, size_t xlen, int curve);
319
320 /**
321 * \brief Multiply two points by two integers and add the
322 * results.
323 *
324 * The point `x*A + y*B` is computed and written back in the `A`
325 * array.
326 *
327 * Rules:
328 *
329 * - The specified curve MUST be supported.
330 *
331 * - The source points (`A` and `B`) must be valid points on
332 * the relevant curve subgroup (and not the "point at
333 * infinity" either). If this is not the case, then this
334 * function returns an error (0).
335 *
336 * - The multiplier integers (`x` and `y`) MUST be non-zero
337 * and less than the curve subgroup order. If either integer
338 * is zero, then an error is reported, but if one of them is
339 * not lower than the subgroup order, then the result is
340 * indeterminate and an error code is not guaranteed.
341 *
342 * - If the final result is the point at infinity, then an
343 * error is returned.
344 *
345 * Returned value is 1 on success, 0 on error. On error, the
346 * contents of `A` are indeterminate.
347 *
348 * \param A first point to multiply.
349 * \param B second point to multiply.
350 * \param len common length of the encoded points (in bytes).
351 * \param x multiplier for `A` (unsigned big-endian).
352 * \param xlen length of multiplier for `A` (in bytes).
353 * \param y multiplier for `A` (unsigned big-endian).
354 * \param ylen length of multiplier for `A` (in bytes).
355 * \param curve curve identifier.
356 * \return 1 on success, 0 on error.
357 */
358 uint32_t (*muladd)(unsigned char *A, const unsigned char *B, size_t len,
359 const unsigned char *x, size_t xlen,
360 const unsigned char *y, size_t ylen, int curve);
361 } br_ec_impl;
362
363 /**
364 * \brief EC implementation "i31".
365 *
366 * This implementation internally uses generic code for modular integers,
367 * with a representation as sequences of 31-bit words. It supports secp256r1,
368 * secp384r1 and secp521r1 (aka NIST curves P-256, P-384 and P-521).
369 */
370 extern const br_ec_impl br_ec_prime_i31;
371
372 /**
373 * \brief Convert a signature from "raw" to "asn1".
374 *
375 * Conversion is done "in place" and the new length is returned.
376 * Conversion may enlarge the signature, but by no more than 9 bytes at
377 * most. On error, 0 is returned (error conditions include an odd raw
378 * signature length, or an oversized integer).
379 *
380 * \param sig signature to convert.
381 * \param sig_len signature length (in bytes).
382 * \return the new signature length, or 0 on error.
383 */
384 size_t br_ecdsa_raw_to_asn1(void *sig, size_t sig_len);
385
386 /**
387 * \brief Convert a signature from "asn1" to "raw".
388 *
389 * Conversion is done "in place" and the new length is returned.
390 * Conversion may enlarge the signature, but the new signature length
391 * will be less than twice the source length at most. On error, 0 is
392 * returned (error conditions include an invalid ASN.1 structure or an
393 * oversized integer).
394 *
395 * \param sig signature to convert.
396 * \param sig_len signature length (in bytes).
397 * \return the new signature length, or 0 on error.
398 */
399 size_t br_ecdsa_asn1_to_raw(void *sig, size_t sig_len);
400
401 /**
402 * \brief Type for an ECDSA signer function.
403 *
404 * A pointer to the EC implementation is provided. The hash value is
405 * assumed to have the length inferred from the designated hash function
406 * class.
407 *
408 * Signature is written in the buffer pointed to by `sig`, and the length
409 * (in bytes) is returned. On error, nothing is written in the buffer,
410 * and 0 is returned. This function returns 0 if the specified curve is
411 * not supported by the provided EC implementation.
412 *
413 * The signature format is either "raw" or "asn1", depending on the
414 * implementation; maximum length is predictable from the implemented
415 * curve:
416 *
417 * | curve | raw | asn1 |
418 * | :--------- | --: | ---: |
419 * | NIST P-256 | 64 | 72 |
420 * | NIST P-384 | 96 | 104 |
421 * | NIST P-521 | 132 | 139 |
422 *
423 * \param impl EC implementation to use.
424 * \param hf hash function used to process the data.
425 * \param hash_value signed data (hashed).
426 * \param sk EC private key.
427 * \param sig destination buffer.
428 * \return the signature length (in bytes), or 0 on error.
429 */
430 typedef size_t (*br_ecdsa_sign)(const br_ec_impl *impl,
431 const br_hash_class *hf, const void *hash_value,
432 const br_ec_private_key *sk, void *sig);
433
434 /**
435 * \brief Type for an ECDSA signature verification function.
436 *
437 * A pointer to the EC implementation is provided. The hashed value,
438 * computed over the purportedly signed data, is also provided with
439 * its length.
440 *
441 * The signature format is either "raw" or "asn1", depending on the
442 * implementation.
443 *
444 * Returned value is 1 on success (valid signature), 0 on error. This
445 * function returns 0 if the specified curve is not supported by the
446 * provided EC implementation.
447 *
448 * \param impl EC implementation to use.
449 * \param hash signed data (hashed).
450 * \param hash_len hash value length (in bytes).
451 * \param pk EC public key.
452 * \param sig signature.
453 * \param sig_len signature length (in bytes).
454 * \return 1 on success, 0 on error.
455 */
456 typedef uint32_t (*br_ecdsa_vrfy)(const br_ec_impl *impl,
457 const void *hash, size_t hash_len,
458 const br_ec_public_key *pk, const void *sig, size_t sig_len);
459
460 /**
461 * \brief ECDSA signature generator, "i31" implementation, "asn1" format.
462 *
463 * \see br_ecdsa_sign()
464 *
465 * \param impl EC implementation to use.
466 * \param hf hash function used to process the data.
467 * \param hash_value signed data (hashed).
468 * \param sk EC private key.
469 * \param sig destination buffer.
470 * \return the signature length (in bytes), or 0 on error.
471 */
472 size_t br_ecdsa_i31_sign_asn1(const br_ec_impl *impl,
473 const br_hash_class *hf, const void *hash_value,
474 const br_ec_private_key *sk, void *sig);
475
476 /**
477 * \brief ECDSA signature generator, "i31" implementation, "raw" format.
478 *
479 * \see br_ecdsa_sign()
480 *
481 * \param impl EC implementation to use.
482 * \param hf hash function used to process the data.
483 * \param hash_value signed data (hashed).
484 * \param sk EC private key.
485 * \param sig destination buffer.
486 * \return the signature length (in bytes), or 0 on error.
487 */
488 size_t br_ecdsa_i31_sign_raw(const br_ec_impl *impl,
489 const br_hash_class *hf, const void *hash_value,
490 const br_ec_private_key *sk, void *sig);
491
492 /**
493 * \brief ECDSA signature verifier, "i31" implementation, "asn1" format.
494 *
495 * \see br_ecdsa_vrfy()
496 *
497 * \param impl EC implementation to use.
498 * \param hash signed data (hashed).
499 * \param hash_len hash value length (in bytes).
500 * \param pk EC public key.
501 * \param sig signature.
502 * \param sig_len signature length (in bytes).
503 * \return 1 on success, 0 on error.
504 */
505 uint32_t br_ecdsa_i31_vrfy_asn1(const br_ec_impl *impl,
506 const void *hash, size_t hash_len,
507 const br_ec_public_key *pk, const void *sig, size_t sig_len);
508
509 /**
510 * \brief ECDSA signature verifier, "i31" implementation, "raw" format.
511 *
512 * \see br_ecdsa_vrfy()
513 *
514 * \param impl EC implementation to use.
515 * \param hash signed data (hashed).
516 * \param hash_len hash value length (in bytes).
517 * \param pk EC public key.
518 * \param sig signature.
519 * \param sig_len signature length (in bytes).
520 * \return 1 on success, 0 on error.
521 */
522 uint32_t br_ecdsa_i31_vrfy_raw(const br_ec_impl *impl,
523 const void *hash, size_t hash_len,
524 const br_ec_public_key *pk, const void *sig, size_t sig_len);
525
526 #endif