New implementation of Curve25519 (using multiplications of words of 15 bits or so...
[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 * - `mulgen()`
73 *
74 * Multiply the curve generator with an integer. This may be faster
75 * than the generic `mul()`.
76 *
77 * - `muladd()`
78 *
79 * Multiply two curve points by two integers, and return the sum of
80 * the two products.
81 *
82 * All curve points are represented in uncompressed format. The `mul()`
83 * and `muladd()` methods take care to validate that the provided points
84 * are really part of the relevant curve subgroup.
85 *
86 * For all point multiplication functions, the following holds:
87 *
88 * - Functions validate that the provided points are valid members
89 * of the relevant curve subgroup. An error is reported if that is
90 * not the case.
91 *
92 * - Processing is constant-time, even if the point operands are not
93 * valid. This holds for both the source and resulting points, and
94 * the multipliers (integers). Only the byte length of the provided
95 * multiplier arrays (not their actual value length in bits) may
96 * leak through timing-based side channels.
97 *
98 * - The multipliers (integers) MUST be lower than the subgroup order.
99 * If this property is not met, then the result is indeterminate,
100 * but an error value is not ncessearily returned.
101 *
102 *
103 * ## ECDSA
104 *
105 * ECDSA signatures have two standard formats, called "raw" and "asn1".
106 * Internally, such a signature is a pair of modular integers `(r,s)`.
107 * The "raw" format is the concatenation of the unsigned big-endian
108 * encodings of these two integers, possibly left-padded with zeros so
109 * that they have the same encoded length. The "asn1" format is the
110 * DER encoding of an ASN.1 structure that contains the two integer
111 * values:
112 *
113 * ECDSASignature ::= SEQUENCE {
114 * r INTEGER,
115 * s INTEGER
116 * }
117 *
118 * In general, in all of X.509 and SSL/TLS, the "asn1" format is used.
119 * BearSSL offers ECDSA implementations for both formats; conversion
120 * functions between the two formats are also provided. Conversion of a
121 * "raw" format signature into "asn1" may enlarge a signature by no more
122 * than 9 bytes for all supported curves; conversely, conversion of an
123 * "asn1" signature to "raw" may expand the signature but the "raw"
124 * length will never be more than twice the length of the "asn1" length
125 * (and usually it will be shorter).
126 *
127 * Note that for a given signature, the "raw" format is not fully
128 * deterministic, in that it does not enforce a minimal common length.
129 */
130
131 /*
132 * Standard curve ID. These ID are equal to the assigned numerical
133 * identifiers assigned to these curves for TLS:
134 * http://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-8
135 */
136
137 /** \brief Identifier for named curve sect163k1. */
138 #define BR_EC_sect163k1 1
139
140 /** \brief Identifier for named curve sect163r1. */
141 #define BR_EC_sect163r1 2
142
143 /** \brief Identifier for named curve sect163r2. */
144 #define BR_EC_sect163r2 3
145
146 /** \brief Identifier for named curve sect193r1. */
147 #define BR_EC_sect193r1 4
148
149 /** \brief Identifier for named curve sect193r2. */
150 #define BR_EC_sect193r2 5
151
152 /** \brief Identifier for named curve sect233k1. */
153 #define BR_EC_sect233k1 6
154
155 /** \brief Identifier for named curve sect233r1. */
156 #define BR_EC_sect233r1 7
157
158 /** \brief Identifier for named curve sect239k1. */
159 #define BR_EC_sect239k1 8
160
161 /** \brief Identifier for named curve sect283k1. */
162 #define BR_EC_sect283k1 9
163
164 /** \brief Identifier for named curve sect283r1. */
165 #define BR_EC_sect283r1 10
166
167 /** \brief Identifier for named curve sect409k1. */
168 #define BR_EC_sect409k1 11
169
170 /** \brief Identifier for named curve sect409r1. */
171 #define BR_EC_sect409r1 12
172
173 /** \brief Identifier for named curve sect571k1. */
174 #define BR_EC_sect571k1 13
175
176 /** \brief Identifier for named curve sect571r1. */
177 #define BR_EC_sect571r1 14
178
179 /** \brief Identifier for named curve secp160k1. */
180 #define BR_EC_secp160k1 15
181
182 /** \brief Identifier for named curve secp160r1. */
183 #define BR_EC_secp160r1 16
184
185 /** \brief Identifier for named curve secp160r2. */
186 #define BR_EC_secp160r2 17
187
188 /** \brief Identifier for named curve secp192k1. */
189 #define BR_EC_secp192k1 18
190
191 /** \brief Identifier for named curve secp192r1. */
192 #define BR_EC_secp192r1 19
193
194 /** \brief Identifier for named curve secp224k1. */
195 #define BR_EC_secp224k1 20
196
197 /** \brief Identifier for named curve secp224r1. */
198 #define BR_EC_secp224r1 21
199
200 /** \brief Identifier for named curve secp256k1. */
201 #define BR_EC_secp256k1 22
202
203 /** \brief Identifier for named curve secp256r1. */
204 #define BR_EC_secp256r1 23
205
206 /** \brief Identifier for named curve secp384r1. */
207 #define BR_EC_secp384r1 24
208
209 /** \brief Identifier for named curve secp521r1. */
210 #define BR_EC_secp521r1 25
211
212 /** \brief Identifier for named curve brainpoolP256r1. */
213 #define BR_EC_brainpoolP256r1 26
214
215 /** \brief Identifier for named curve brainpoolP384r1. */
216 #define BR_EC_brainpoolP384r1 27
217
218 /** \brief Identifier for named curve brainpoolP512r1. */
219 #define BR_EC_brainpoolP512r1 28
220
221 /** \brief Identifier for named curve Curve25519. */
222 #define BR_EC_curve25519 29
223
224 /** \brief Identifier for named curve Curve448. */
225 #define BR_EC_curve448 30
226
227 /**
228 * \brief Structure for an EC public key.
229 */
230 typedef struct {
231 /** \brief Identifier for the curve used by this key. */
232 int curve;
233 /** \brief Public curve point (uncompressed format). */
234 unsigned char *q;
235 /** \brief Length of public curve point (in bytes). */
236 size_t qlen;
237 } br_ec_public_key;
238
239 /**
240 * \brief Structure for an EC private key.
241 *
242 * The private key is an integer modulo the curve subgroup order. The
243 * encoding below tolerates extra leading zeros. In general, it is
244 * recommended that the private key has the same length as the curve
245 * subgroup order.
246 */
247 typedef struct {
248 /** \brief Identifier for the curve used by this key. */
249 int curve;
250 /** \brief Private key (integer, unsigned big-endian encoding). */
251 unsigned char *x;
252 /** \brief Private key length (in bytes). */
253 size_t xlen;
254 } br_ec_private_key;
255
256 /**
257 * \brief Type for an EC implementation.
258 */
259 typedef struct {
260 /**
261 * \brief Supported curves.
262 *
263 * This word is a bitfield: bit `x` is set if the curve of ID `x`
264 * is supported. E.g. an implementation supporting both NIST P-256
265 * (secp256r1, ID 23) and NIST P-384 (secp384r1, ID 24) will have
266 * value `0x01800000` in this field.
267 */
268 uint32_t supported_curves;
269
270 /**
271 * \brief Get the conventional generator.
272 *
273 * This function returns the conventional generator (encoded
274 * curve point) for the specified curve. This function MUST NOT
275 * be called if the curve is not supported.
276 *
277 * \param curve curve identifier.
278 * \param len receiver for the encoded generator length (in bytes).
279 * \return the encoded generator.
280 */
281 const unsigned char *(*generator)(int curve, size_t *len);
282
283 /**
284 * \brief Get the subgroup order.
285 *
286 * This function returns the order of the subgroup generated by
287 * the conventional generator, for the specified curve. Unsigned
288 * big-endian encoding is used. This function MUST NOT be called
289 * if the curve is not supported.
290 *
291 * \param curve curve identifier.
292 * \param len receiver for the encoded order length (in bytes).
293 * \return the encoded order.
294 */
295 const unsigned char *(*order)(int curve, size_t *len);
296
297 /**
298 * \brief Multiply a curve point by an integer.
299 *
300 * The source point is provided in array `G` (of size `Glen` bytes);
301 * the multiplication result is written over it. The multiplier
302 * `x` (of size `xlen` bytes) uses unsigned big-endian encoding.
303 *
304 * Rules:
305 *
306 * - The specified curve MUST be supported.
307 *
308 * - The source point must be a valid point on the relevant curve
309 * subgroup (and not the "point at infinity" either). If this is
310 * not the case, then this function returns an error (0).
311 *
312 * - The multiplier integer MUST be non-zero and less than the
313 * curve subgroup order. If this property does not hold, then
314 * the result is indeterminate and an error code is not
315 * guaranteed.
316 *
317 * Returned value is 1 on success, 0 on error. On error, the
318 * contents of `G` are indeterminate.
319 *
320 * \param G point to multiply.
321 * \param Glen length of the encoded point (in bytes).
322 * \param x multiplier (unsigned big-endian).
323 * \param xlen multiplier length (in bytes).
324 * \param curve curve identifier.
325 * \return 1 on success, 0 on error.
326 */
327 uint32_t (*mul)(unsigned char *G, size_t Glen,
328 const unsigned char *x, size_t xlen, int curve);
329
330 /**
331 * \brief Multiply the generator by an integer.
332 *
333 * The multiplier MUST be non-zero and less than the curve
334 * subgroup order. Results are indeterminate if this property
335 * does not hold.
336 *
337 * \param R output buffer for the point.
338 * \param x multiplier (unsigned big-endian).
339 * \param xlen multiplier length (in bytes).
340 * \param curve curve identifier.
341 * \return encoded result point length (in bytes).
342 */
343 size_t (*mulgen)(unsigned char *R,
344 const unsigned char *x, size_t xlen, int curve);
345
346 /**
347 * \brief Multiply two points by two integers and add the
348 * results.
349 *
350 * The point `x*A + y*B` is computed and written back in the `A`
351 * array.
352 *
353 * Rules:
354 *
355 * - The specified curve MUST be supported.
356 *
357 * - The source points (`A` and `B`) must be valid points on
358 * the relevant curve subgroup (and not the "point at
359 * infinity" either). If this is not the case, then this
360 * function returns an error (0).
361 *
362 * - If the `B` pointer is `NULL`, then the conventional
363 * subgroup generator is used. With some implementations,
364 * this may be faster than providing a pointer to the
365 * generator.
366 *
367 * - The multiplier integers (`x` and `y`) MUST be non-zero
368 * and less than the curve subgroup order. If either integer
369 * is zero, then an error is reported, but if one of them is
370 * not lower than the subgroup order, then the result is
371 * indeterminate and an error code is not guaranteed.
372 *
373 * - If the final result is the point at infinity, then an
374 * error is returned.
375 *
376 * Returned value is 1 on success, 0 on error. On error, the
377 * contents of `A` are indeterminate.
378 *
379 * \param A first point to multiply.
380 * \param B second point to multiply (`NULL` for the generator).
381 * \param len common length of the encoded points (in bytes).
382 * \param x multiplier for `A` (unsigned big-endian).
383 * \param xlen length of multiplier for `A` (in bytes).
384 * \param y multiplier for `A` (unsigned big-endian).
385 * \param ylen length of multiplier for `A` (in bytes).
386 * \param curve curve identifier.
387 * \return 1 on success, 0 on error.
388 */
389 uint32_t (*muladd)(unsigned char *A, const unsigned char *B, size_t len,
390 const unsigned char *x, size_t xlen,
391 const unsigned char *y, size_t ylen, int curve);
392 } br_ec_impl;
393
394 /**
395 * \brief EC implementation "i31".
396 *
397 * This implementation internally uses generic code for modular integers,
398 * with a representation as sequences of 31-bit words. It supports secp256r1,
399 * secp384r1 and secp521r1 (aka NIST curves P-256, P-384 and P-521).
400 */
401 extern const br_ec_impl br_ec_prime_i31;
402
403 /**
404 * \brief EC implementation "i15".
405 *
406 * This implementation internally uses generic code for modular integers,
407 * with a representation as sequences of 15-bit words. It supports secp256r1,
408 * secp384r1 and secp521r1 (aka NIST curves P-256, P-384 and P-521).
409 */
410 extern const br_ec_impl br_ec_prime_i15;
411
412 /**
413 * \brief EC implementation "m15" for P-256.
414 *
415 * This implementation uses specialised code for curve secp256r1 (also
416 * known as NIST P-256), with optional Karatsuba decomposition, and fast
417 * modular reduction thanks to the field modulus special format. Only
418 * 32-bit multiplications are used (with 32-bit results, not 64-bit).
419 */
420 extern const br_ec_impl br_ec_p256_m15;
421
422 /**
423 * \brief EC implementation "i15" (generic code) for Curve25519.
424 *
425 * This implementation uses the generic code for modular integers (with
426 * 15-bit words) to support Curve25519. The `muladd()` method is not
427 * implemented.
428 */
429 extern const br_ec_impl br_ec_c25519_i15;
430
431 /**
432 * \brief EC implementation "m15" (specialised code) for Curve25519.
433 *
434 * This implementation uses custom code relying on multiplication of
435 * integers up to 15 bits. The `muladd()` method is not implemented.
436 */
437 extern const br_ec_impl br_ec_c25519_m15;
438
439 /**
440 * \brief Convert a signature from "raw" to "asn1".
441 *
442 * Conversion is done "in place" and the new length is returned.
443 * Conversion may enlarge the signature, but by no more than 9 bytes at
444 * most. On error, 0 is returned (error conditions include an odd raw
445 * signature length, or an oversized integer).
446 *
447 * \param sig signature to convert.
448 * \param sig_len signature length (in bytes).
449 * \return the new signature length, or 0 on error.
450 */
451 size_t br_ecdsa_raw_to_asn1(void *sig, size_t sig_len);
452
453 /**
454 * \brief Convert a signature from "asn1" to "raw".
455 *
456 * Conversion is done "in place" and the new length is returned.
457 * Conversion may enlarge the signature, but the new signature length
458 * will be less than twice the source length at most. On error, 0 is
459 * returned (error conditions include an invalid ASN.1 structure or an
460 * oversized integer).
461 *
462 * \param sig signature to convert.
463 * \param sig_len signature length (in bytes).
464 * \return the new signature length, or 0 on error.
465 */
466 size_t br_ecdsa_asn1_to_raw(void *sig, size_t sig_len);
467
468 /**
469 * \brief Type for an ECDSA signer function.
470 *
471 * A pointer to the EC implementation is provided. The hash value is
472 * assumed to have the length inferred from the designated hash function
473 * class.
474 *
475 * Signature is written in the buffer pointed to by `sig`, and the length
476 * (in bytes) is returned. On error, nothing is written in the buffer,
477 * and 0 is returned. This function returns 0 if the specified curve is
478 * not supported by the provided EC implementation.
479 *
480 * The signature format is either "raw" or "asn1", depending on the
481 * implementation; maximum length is predictable from the implemented
482 * curve:
483 *
484 * | curve | raw | asn1 |
485 * | :--------- | --: | ---: |
486 * | NIST P-256 | 64 | 72 |
487 * | NIST P-384 | 96 | 104 |
488 * | NIST P-521 | 132 | 139 |
489 *
490 * \param impl EC implementation to use.
491 * \param hf hash function used to process the data.
492 * \param hash_value signed data (hashed).
493 * \param sk EC private key.
494 * \param sig destination buffer.
495 * \return the signature length (in bytes), or 0 on error.
496 */
497 typedef size_t (*br_ecdsa_sign)(const br_ec_impl *impl,
498 const br_hash_class *hf, const void *hash_value,
499 const br_ec_private_key *sk, void *sig);
500
501 /**
502 * \brief Type for an ECDSA signature verification function.
503 *
504 * A pointer to the EC implementation is provided. The hashed value,
505 * computed over the purportedly signed data, is also provided with
506 * its length.
507 *
508 * The signature format is either "raw" or "asn1", depending on the
509 * implementation.
510 *
511 * Returned value is 1 on success (valid signature), 0 on error. This
512 * function returns 0 if the specified curve is not supported by the
513 * provided EC implementation.
514 *
515 * \param impl EC implementation to use.
516 * \param hash signed data (hashed).
517 * \param hash_len hash value length (in bytes).
518 * \param pk EC public key.
519 * \param sig signature.
520 * \param sig_len signature length (in bytes).
521 * \return 1 on success, 0 on error.
522 */
523 typedef uint32_t (*br_ecdsa_vrfy)(const br_ec_impl *impl,
524 const void *hash, size_t hash_len,
525 const br_ec_public_key *pk, const void *sig, size_t sig_len);
526
527 /**
528 * \brief ECDSA signature generator, "i31" implementation, "asn1" format.
529 *
530 * \see br_ecdsa_sign()
531 *
532 * \param impl EC implementation to use.
533 * \param hf hash function used to process the data.
534 * \param hash_value signed data (hashed).
535 * \param sk EC private key.
536 * \param sig destination buffer.
537 * \return the signature length (in bytes), or 0 on error.
538 */
539 size_t br_ecdsa_i31_sign_asn1(const br_ec_impl *impl,
540 const br_hash_class *hf, const void *hash_value,
541 const br_ec_private_key *sk, void *sig);
542
543 /**
544 * \brief ECDSA signature generator, "i31" implementation, "raw" format.
545 *
546 * \see br_ecdsa_sign()
547 *
548 * \param impl EC implementation to use.
549 * \param hf hash function used to process the data.
550 * \param hash_value signed data (hashed).
551 * \param sk EC private key.
552 * \param sig destination buffer.
553 * \return the signature length (in bytes), or 0 on error.
554 */
555 size_t br_ecdsa_i31_sign_raw(const br_ec_impl *impl,
556 const br_hash_class *hf, const void *hash_value,
557 const br_ec_private_key *sk, void *sig);
558
559 /**
560 * \brief ECDSA signature verifier, "i31" implementation, "asn1" format.
561 *
562 * \see br_ecdsa_vrfy()
563 *
564 * \param impl EC implementation to use.
565 * \param hash signed data (hashed).
566 * \param hash_len hash value length (in bytes).
567 * \param pk EC public key.
568 * \param sig signature.
569 * \param sig_len signature length (in bytes).
570 * \return 1 on success, 0 on error.
571 */
572 uint32_t br_ecdsa_i31_vrfy_asn1(const br_ec_impl *impl,
573 const void *hash, size_t hash_len,
574 const br_ec_public_key *pk, const void *sig, size_t sig_len);
575
576 /**
577 * \brief ECDSA signature verifier, "i31" implementation, "raw" format.
578 *
579 * \see br_ecdsa_vrfy()
580 *
581 * \param impl EC implementation to use.
582 * \param hash signed data (hashed).
583 * \param hash_len hash value length (in bytes).
584 * \param pk EC public key.
585 * \param sig signature.
586 * \param sig_len signature length (in bytes).
587 * \return 1 on success, 0 on error.
588 */
589 uint32_t br_ecdsa_i31_vrfy_raw(const br_ec_impl *impl,
590 const void *hash, size_t hash_len,
591 const br_ec_public_key *pk, const void *sig, size_t sig_len);
592
593 /**
594 * \brief ECDSA signature generator, "i15" implementation, "asn1" format.
595 *
596 * \see br_ecdsa_sign()
597 *
598 * \param impl EC implementation to use.
599 * \param hf hash function used to process the data.
600 * \param hash_value signed data (hashed).
601 * \param sk EC private key.
602 * \param sig destination buffer.
603 * \return the signature length (in bytes), or 0 on error.
604 */
605 size_t br_ecdsa_i15_sign_asn1(const br_ec_impl *impl,
606 const br_hash_class *hf, const void *hash_value,
607 const br_ec_private_key *sk, void *sig);
608
609 /**
610 * \brief ECDSA signature generator, "i15" implementation, "raw" format.
611 *
612 * \see br_ecdsa_sign()
613 *
614 * \param impl EC implementation to use.
615 * \param hf hash function used to process the data.
616 * \param hash_value signed data (hashed).
617 * \param sk EC private key.
618 * \param sig destination buffer.
619 * \return the signature length (in bytes), or 0 on error.
620 */
621 size_t br_ecdsa_i15_sign_raw(const br_ec_impl *impl,
622 const br_hash_class *hf, const void *hash_value,
623 const br_ec_private_key *sk, void *sig);
624
625 /**
626 * \brief ECDSA signature verifier, "i15" implementation, "asn1" format.
627 *
628 * \see br_ecdsa_vrfy()
629 *
630 * \param impl EC implementation to use.
631 * \param hash signed data (hashed).
632 * \param hash_len hash value length (in bytes).
633 * \param pk EC public key.
634 * \param sig signature.
635 * \param sig_len signature length (in bytes).
636 * \return 1 on success, 0 on error.
637 */
638 uint32_t br_ecdsa_i15_vrfy_asn1(const br_ec_impl *impl,
639 const void *hash, size_t hash_len,
640 const br_ec_public_key *pk, const void *sig, size_t sig_len);
641
642 /**
643 * \brief ECDSA signature verifier, "i15" implementation, "raw" format.
644 *
645 * \see br_ecdsa_vrfy()
646 *
647 * \param impl EC implementation to use.
648 * \param hash signed data (hashed).
649 * \param hash_len hash value length (in bytes).
650 * \param pk EC public key.
651 * \param sig signature.
652 * \param sig_len signature length (in bytes).
653 * \return 1 on success, 0 on error.
654 */
655 uint32_t br_ecdsa_i15_vrfy_raw(const br_ec_impl *impl,
656 const void *hash, size_t hash_len,
657 const br_ec_public_key *pk, const void *sig, size_t sig_len);
658
659 #endif