1/*
2 * Elliptic curves over GF(p): generic functions
3 *
4 * Copyright The Mbed TLS Contributors
5 * SPDX-License-Identifier: Apache-2.0
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License"); you may
8 * not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20/*
21 * References:
22 *
23 * SEC1 https://www.secg.org/sec1-v2.pdf
24 * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
25 * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
26 * RFC 4492 for the related TLS structures and constants
27 * - https://www.rfc-editor.org/rfc/rfc4492
28 * RFC 7748 for the Curve448 and Curve25519 curve definitions
29 * - https://www.rfc-editor.org/rfc/rfc7748
30 *
31 * [Curve25519] https://cr.yp.to/ecdh/curve25519-20060209.pdf
32 *
33 * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
34 * for elliptic curve cryptosystems. In : Cryptographic Hardware and
35 * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
36 * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
37 *
38 * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
39 * render ECC resistant against Side Channel Attacks. IACR Cryptology
40 * ePrint Archive, 2004, vol. 2004, p. 342.
41 * <http://eprint.iacr.org/2004/342.pdf>
42 */
43
44#include "common.h"
45
46/**
47 * \brief Function level alternative implementation.
48 *
49 * The MBEDTLS_ECP_INTERNAL_ALT macro enables alternative implementations to
50 * replace certain functions in this module. The alternative implementations are
51 * typically hardware accelerators and need to activate the hardware before the
52 * computation starts and deactivate it after it finishes. The
53 * mbedtls_internal_ecp_init() and mbedtls_internal_ecp_free() functions serve
54 * this purpose.
55 *
56 * To preserve the correct functionality the following conditions must hold:
57 *
58 * - The alternative implementation must be activated by
59 * mbedtls_internal_ecp_init() before any of the replaceable functions is
60 * called.
61 * - mbedtls_internal_ecp_free() must \b only be called when the alternative
62 * implementation is activated.
63 * - mbedtls_internal_ecp_init() must \b not be called when the alternative
64 * implementation is activated.
65 * - Public functions must not return while the alternative implementation is
66 * activated.
67 * - Replaceable functions are guarded by \c MBEDTLS_ECP_XXX_ALT macros and
68 * before calling them an \code if( mbedtls_internal_ecp_grp_capable( grp ) )
69 * \endcode ensures that the alternative implementation supports the current
70 * group.
71 */
72#if defined(MBEDTLS_ECP_INTERNAL_ALT)
73#endif
74
75#if defined(MBEDTLS_ECP_C)
76
77#include "mbedtls/ecp.h"
78#include "mbedtls/threading.h"
79#include "mbedtls/platform_util.h"
80#include "mbedtls/error.h"
81#include "mbedtls/bn_mul.h"
82
83#include "ecp_invasive.h"
84
85#include <string.h>
86
87#if !defined(MBEDTLS_ECP_ALT)
88
89/* Parameter validation macros based on platform_util.h */
90#define ECP_VALIDATE_RET(cond) \
91 MBEDTLS_INTERNAL_VALIDATE_RET(cond, MBEDTLS_ERR_ECP_BAD_INPUT_DATA)
92#define ECP_VALIDATE(cond) \
93 MBEDTLS_INTERNAL_VALIDATE(cond)
94
95#include "mbedtls/platform.h"
96
97#include "mbedtls/ecp_internal.h"
98
99#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
100#if defined(MBEDTLS_HMAC_DRBG_C)
101#include "mbedtls/hmac_drbg.h"
102#elif defined(MBEDTLS_CTR_DRBG_C)
103#include "mbedtls/ctr_drbg.h"
104#else
105#error \
106 "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid."
107#endif
108#endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */
109
110#if defined(MBEDTLS_SELF_TEST)
111/*
112 * Counts of point addition and doubling, and field multiplications.
113 * Used to test resistance of point multiplication to simple timing attacks.
114 */
115static unsigned long add_count, dbl_count, mul_count;
116#endif
117
118#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
119/*
120 * Currently ecp_mul() takes a RNG function as an argument, used for
121 * side-channel protection, but it can be NULL. The initial reasoning was
122 * that people will pass non-NULL RNG when they care about side-channels, but
123 * unfortunately we have some APIs that call ecp_mul() with a NULL RNG, with
124 * no opportunity for the user to do anything about it.
125 *
126 * The obvious strategies for addressing that include:
127 * - change those APIs so that they take RNG arguments;
128 * - require a global RNG to be available to all crypto modules.
129 *
130 * Unfortunately those would break compatibility. So what we do instead is
131 * have our own internal DRBG instance, seeded from the secret scalar.
132 *
133 * The following is a light-weight abstraction layer for doing that with
134 * HMAC_DRBG (first choice) or CTR_DRBG.
135 */
136
137#if defined(MBEDTLS_HMAC_DRBG_C)
138
139/* DRBG context type */
140typedef mbedtls_hmac_drbg_context ecp_drbg_context;
141
142/* DRBG context init */
143static inline void ecp_drbg_init(ecp_drbg_context *ctx)
144{
145 mbedtls_hmac_drbg_init(ctx);
146}
147
148/* DRBG context free */
149static inline void ecp_drbg_free(ecp_drbg_context *ctx)
150{
151 mbedtls_hmac_drbg_free(ctx);
152}
153
154/* DRBG function */
155static inline int ecp_drbg_random(void *p_rng,
156 unsigned char *output, size_t output_len)
157{
158 return mbedtls_hmac_drbg_random(p_rng, output, output_len);
159}
160
161/* DRBG context seeding */
162static int ecp_drbg_seed(ecp_drbg_context *ctx,
163 const mbedtls_mpi *secret, size_t secret_len)
164{
165 int ret;
166 unsigned char secret_bytes[MBEDTLS_ECP_MAX_BYTES];
167 /* The list starts with strong hashes */
168 const mbedtls_md_type_t md_type =
169 (const mbedtls_md_type_t) (mbedtls_md_list()[0]);
170 const mbedtls_md_info_t *md_info = mbedtls_md_info_from_type(md_type);
171
172 if (secret_len > MBEDTLS_ECP_MAX_BYTES) {
173 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
174 goto cleanup;
175 }
176
177 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(secret,
178 secret_bytes, secret_len));
179
180 ret = mbedtls_hmac_drbg_seed_buf(ctx, md_info, secret_bytes, secret_len);
181
182cleanup:
183 mbedtls_platform_zeroize(secret_bytes, secret_len);
184
185 return ret;
186}
187
188#elif defined(MBEDTLS_CTR_DRBG_C)
189
190/* DRBG context type */
191typedef mbedtls_ctr_drbg_context ecp_drbg_context;
192
193/* DRBG context init */
194static inline void ecp_drbg_init(ecp_drbg_context *ctx)
195{
196 mbedtls_ctr_drbg_init(ctx);
197}
198
199/* DRBG context free */
200static inline void ecp_drbg_free(ecp_drbg_context *ctx)
201{
202 mbedtls_ctr_drbg_free(ctx);
203}
204
205/* DRBG function */
206static inline int ecp_drbg_random(void *p_rng,
207 unsigned char *output, size_t output_len)
208{
209 return mbedtls_ctr_drbg_random(p_rng, output, output_len);
210}
211
212/*
213 * Since CTR_DRBG doesn't have a seed_buf() function the way HMAC_DRBG does,
214 * we need to pass an entropy function when seeding. So we use a dummy
215 * function for that, and pass the actual entropy as customisation string.
216 * (During seeding of CTR_DRBG the entropy input and customisation string are
217 * concatenated before being used to update the secret state.)
218 */
219static int ecp_ctr_drbg_null_entropy(void *ctx, unsigned char *out, size_t len)
220{
221 (void) ctx;
222 memset(out, 0, len);
223 return 0;
224}
225
226/* DRBG context seeding */
227static int ecp_drbg_seed(ecp_drbg_context *ctx,
228 const mbedtls_mpi *secret, size_t secret_len)
229{
230 int ret;
231 unsigned char secret_bytes[MBEDTLS_ECP_MAX_BYTES];
232
233 if (secret_len > MBEDTLS_ECP_MAX_BYTES) {
234 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
235 goto cleanup;
236 }
237
238 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(secret,
239 secret_bytes, secret_len));
240
241 ret = mbedtls_ctr_drbg_seed(ctx, ecp_ctr_drbg_null_entropy, NULL,
242 secret_bytes, secret_len);
243
244cleanup:
245 mbedtls_platform_zeroize(secret_bytes, secret_len);
246
247 return ret;
248}
249
250#else
251#error \
252 "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid."
253#endif /* DRBG modules */
254#endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */
255
256#if defined(MBEDTLS_ECP_RESTARTABLE)
257/*
258 * Maximum number of "basic operations" to be done in a row.
259 *
260 * Default value 0 means that ECC operations will not yield.
261 * Note that regardless of the value of ecp_max_ops, always at
262 * least one step is performed before yielding.
263 *
264 * Setting ecp_max_ops=1 can be suitable for testing purposes
265 * as it will interrupt computation at all possible points.
266 */
267static unsigned ecp_max_ops = 0;
268
269/*
270 * Set ecp_max_ops
271 */
272void mbedtls_ecp_set_max_ops(unsigned max_ops)
273{
274 ecp_max_ops = max_ops;
275}
276
277/*
278 * Check if restart is enabled
279 */
280int mbedtls_ecp_restart_is_enabled(void)
281{
282 return ecp_max_ops != 0;
283}
284
285/*
286 * Restart sub-context for ecp_mul_comb()
287 */
288struct mbedtls_ecp_restart_mul {
289 mbedtls_ecp_point R; /* current intermediate result */
290 size_t i; /* current index in various loops, 0 outside */
291 mbedtls_ecp_point *T; /* table for precomputed points */
292 unsigned char T_size; /* number of points in table T */
293 enum { /* what were we doing last time we returned? */
294 ecp_rsm_init = 0, /* nothing so far, dummy initial state */
295 ecp_rsm_pre_dbl, /* precompute 2^n multiples */
296 ecp_rsm_pre_norm_dbl, /* normalize precomputed 2^n multiples */
297 ecp_rsm_pre_add, /* precompute remaining points by adding */
298 ecp_rsm_pre_norm_add, /* normalize all precomputed points */
299 ecp_rsm_comb_core, /* ecp_mul_comb_core() */
300 ecp_rsm_final_norm, /* do the final normalization */
301 } state;
302#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
303 ecp_drbg_context drbg_ctx;
304 unsigned char drbg_seeded;
305#endif
306};
307
308/*
309 * Init restart_mul sub-context
310 */
311static void ecp_restart_rsm_init(mbedtls_ecp_restart_mul_ctx *ctx)
312{
313 mbedtls_ecp_point_init(&ctx->R);
314 ctx->i = 0;
315 ctx->T = NULL;
316 ctx->T_size = 0;
317 ctx->state = ecp_rsm_init;
318#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
319 ecp_drbg_init(&ctx->drbg_ctx);
320 ctx->drbg_seeded = 0;
321#endif
322}
323
324/*
325 * Free the components of a restart_mul sub-context
326 */
327static void ecp_restart_rsm_free(mbedtls_ecp_restart_mul_ctx *ctx)
328{
329 unsigned char i;
330
331 if (ctx == NULL) {
332 return;
333 }
334
335 mbedtls_ecp_point_free(&ctx->R);
336
337 if (ctx->T != NULL) {
338 for (i = 0; i < ctx->T_size; i++) {
339 mbedtls_ecp_point_free(ctx->T + i);
340 }
341 mbedtls_free(ctx->T);
342 }
343
344#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
345 ecp_drbg_free(&ctx->drbg_ctx);
346#endif
347
348 ecp_restart_rsm_init(ctx);
349}
350
351/*
352 * Restart context for ecp_muladd()
353 */
354struct mbedtls_ecp_restart_muladd {
355 mbedtls_ecp_point mP; /* mP value */
356 mbedtls_ecp_point R; /* R intermediate result */
357 enum { /* what should we do next? */
358 ecp_rsma_mul1 = 0, /* first multiplication */
359 ecp_rsma_mul2, /* second multiplication */
360 ecp_rsma_add, /* addition */
361 ecp_rsma_norm, /* normalization */
362 } state;
363};
364
365/*
366 * Init restart_muladd sub-context
367 */
368static void ecp_restart_ma_init(mbedtls_ecp_restart_muladd_ctx *ctx)
369{
370 mbedtls_ecp_point_init(&ctx->mP);
371 mbedtls_ecp_point_init(&ctx->R);
372 ctx->state = ecp_rsma_mul1;
373}
374
375/*
376 * Free the components of a restart_muladd sub-context
377 */
378static void ecp_restart_ma_free(mbedtls_ecp_restart_muladd_ctx *ctx)
379{
380 if (ctx == NULL) {
381 return;
382 }
383
384 mbedtls_ecp_point_free(&ctx->mP);
385 mbedtls_ecp_point_free(&ctx->R);
386
387 ecp_restart_ma_init(ctx);
388}
389
390/*
391 * Initialize a restart context
392 */
393void mbedtls_ecp_restart_init(mbedtls_ecp_restart_ctx *ctx)
394{
395 ECP_VALIDATE(ctx != NULL);
396 ctx->ops_done = 0;
397 ctx->depth = 0;
398 ctx->rsm = NULL;
399 ctx->ma = NULL;
400}
401
402/*
403 * Free the components of a restart context
404 */
405void mbedtls_ecp_restart_free(mbedtls_ecp_restart_ctx *ctx)
406{
407 if (ctx == NULL) {
408 return;
409 }
410
411 ecp_restart_rsm_free(ctx->rsm);
412 mbedtls_free(ctx->rsm);
413
414 ecp_restart_ma_free(ctx->ma);
415 mbedtls_free(ctx->ma);
416
417 mbedtls_ecp_restart_init(ctx);
418}
419
420/*
421 * Check if we can do the next step
422 */
423int mbedtls_ecp_check_budget(const mbedtls_ecp_group *grp,
424 mbedtls_ecp_restart_ctx *rs_ctx,
425 unsigned ops)
426{
427 ECP_VALIDATE_RET(grp != NULL);
428
429 if (rs_ctx != NULL && ecp_max_ops != 0) {
430 /* scale depending on curve size: the chosen reference is 256-bit,
431 * and multiplication is quadratic. Round to the closest integer. */
432 if (grp->pbits >= 512) {
433 ops *= 4;
434 } else if (grp->pbits >= 384) {
435 ops *= 2;
436 }
437
438 /* Avoid infinite loops: always allow first step.
439 * Because of that, however, it's not generally true
440 * that ops_done <= ecp_max_ops, so the check
441 * ops_done > ecp_max_ops below is mandatory. */
442 if ((rs_ctx->ops_done != 0) &&
443 (rs_ctx->ops_done > ecp_max_ops ||
444 ops > ecp_max_ops - rs_ctx->ops_done)) {
445 return MBEDTLS_ERR_ECP_IN_PROGRESS;
446 }
447
448 /* update running count */
449 rs_ctx->ops_done += ops;
450 }
451
452 return 0;
453}
454
455/* Call this when entering a function that needs its own sub-context */
456#define ECP_RS_ENTER(SUB) do { \
457 /* reset ops count for this call if top-level */ \
458 if (rs_ctx != NULL && rs_ctx->depth++ == 0) \
459 rs_ctx->ops_done = 0; \
460 \
461 /* set up our own sub-context if needed */ \
462 if (mbedtls_ecp_restart_is_enabled() && \
463 rs_ctx != NULL && rs_ctx->SUB == NULL) \
464 { \
465 rs_ctx->SUB = mbedtls_calloc(1, sizeof(*rs_ctx->SUB)); \
466 if (rs_ctx->SUB == NULL) \
467 return MBEDTLS_ERR_ECP_ALLOC_FAILED; \
468 \
469 ecp_restart_## SUB ##_init(rs_ctx->SUB); \
470 } \
471} while (0)
472
473/* Call this when leaving a function that needs its own sub-context */
474#define ECP_RS_LEAVE(SUB) do { \
475 /* clear our sub-context when not in progress (done or error) */ \
476 if (rs_ctx != NULL && rs_ctx->SUB != NULL && \
477 ret != MBEDTLS_ERR_ECP_IN_PROGRESS) \
478 { \
479 ecp_restart_## SUB ##_free(rs_ctx->SUB); \
480 mbedtls_free(rs_ctx->SUB); \
481 rs_ctx->SUB = NULL; \
482 } \
483 \
484 if (rs_ctx != NULL) \
485 rs_ctx->depth--; \
486} while (0)
487
488#else /* MBEDTLS_ECP_RESTARTABLE */
489
490#define ECP_RS_ENTER(sub) (void) rs_ctx;
491#define ECP_RS_LEAVE(sub) (void) rs_ctx;
492
493#endif /* MBEDTLS_ECP_RESTARTABLE */
494
495/*
496 * List of supported curves:
497 * - internal ID
498 * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2, RFC 8446 sec. 4.2.7)
499 * - size in bits
500 * - readable name
501 *
502 * Curves are listed in order: largest curves first, and for a given size,
503 * fastest curves first. This provides the default order for the SSL module.
504 *
505 * Reminder: update profiles in x509_crt.c when adding a new curves!
506 */
507static const mbedtls_ecp_curve_info ecp_supported_curves[] =
508{
509#if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
510 { MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" },
511#endif
512#if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
513 { MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" },
514#endif
515#if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
516 { MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" },
517#endif
518#if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
519 { MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" },
520#endif
521#if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
522 { MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" },
523#endif
524#if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
525 { MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" },
526#endif
527#if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
528 { MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" },
529#endif
530#if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
531 { MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" },
532#endif
533#if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
534 { MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" },
535#endif
536#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
537 { MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" },
538#endif
539#if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
540 { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" },
541#endif
542#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
543 { MBEDTLS_ECP_DP_CURVE25519, 29, 256, "x25519" },
544#endif
545#if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
546 { MBEDTLS_ECP_DP_CURVE448, 30, 448, "x448" },
547#endif
548 { MBEDTLS_ECP_DP_NONE, 0, 0, NULL },
549};
550
551#define ECP_NB_CURVES sizeof(ecp_supported_curves) / \
552 sizeof(ecp_supported_curves[0])
553
554static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
555
556/*
557 * List of supported curves and associated info
558 */
559const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list(void)
560{
561 return ecp_supported_curves;
562}
563
564/*
565 * List of supported curves, group ID only
566 */
567const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list(void)
568{
569 static int init_done = 0;
570
571 if (!init_done) {
572 size_t i = 0;
573 const mbedtls_ecp_curve_info *curve_info;
574
575 for (curve_info = mbedtls_ecp_curve_list();
576 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
577 curve_info++) {
578 ecp_supported_grp_id[i++] = curve_info->grp_id;
579 }
580 ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
581
582 init_done = 1;
583 }
584
585 return ecp_supported_grp_id;
586}
587
588/*
589 * Get the curve info for the internal identifier
590 */
591const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id(mbedtls_ecp_group_id grp_id)
592{
593 const mbedtls_ecp_curve_info *curve_info;
594
595 for (curve_info = mbedtls_ecp_curve_list();
596 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
597 curve_info++) {
598 if (curve_info->grp_id == grp_id) {
599 return curve_info;
600 }
601 }
602
603 return NULL;
604}
605
606/*
607 * Get the curve info from the TLS identifier
608 */
609const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id(uint16_t tls_id)
610{
611 const mbedtls_ecp_curve_info *curve_info;
612
613 for (curve_info = mbedtls_ecp_curve_list();
614 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
615 curve_info++) {
616 if (curve_info->tls_id == tls_id) {
617 return curve_info;
618 }
619 }
620
621 return NULL;
622}
623
624/*
625 * Get the curve info from the name
626 */
627const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name(const char *name)
628{
629 const mbedtls_ecp_curve_info *curve_info;
630
631 if (name == NULL) {
632 return NULL;
633 }
634
635 for (curve_info = mbedtls_ecp_curve_list();
636 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
637 curve_info++) {
638 if (strcmp(curve_info->name, name) == 0) {
639 return curve_info;
640 }
641 }
642
643 return NULL;
644}
645
646/*
647 * Get the type of a curve
648 */
649mbedtls_ecp_curve_type mbedtls_ecp_get_type(const mbedtls_ecp_group *grp)
650{
651 if (grp->G.X.p == NULL) {
652 return MBEDTLS_ECP_TYPE_NONE;
653 }
654
655 if (grp->G.Y.p == NULL) {
656 return MBEDTLS_ECP_TYPE_MONTGOMERY;
657 } else {
658 return MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS;
659 }
660}
661
662/*
663 * Initialize (the components of) a point
664 */
665void mbedtls_ecp_point_init(mbedtls_ecp_point *pt)
666{
667 ECP_VALIDATE(pt != NULL);
668
669 mbedtls_mpi_init(&pt->X);
670 mbedtls_mpi_init(&pt->Y);
671 mbedtls_mpi_init(&pt->Z);
672}
673
674/*
675 * Initialize (the components of) a group
676 */
677void mbedtls_ecp_group_init(mbedtls_ecp_group *grp)
678{
679 ECP_VALIDATE(grp != NULL);
680
681 grp->id = MBEDTLS_ECP_DP_NONE;
682 mbedtls_mpi_init(&grp->P);
683 mbedtls_mpi_init(&grp->A);
684 mbedtls_mpi_init(&grp->B);
685 mbedtls_ecp_point_init(&grp->G);
686 mbedtls_mpi_init(&grp->N);
687 grp->pbits = 0;
688 grp->nbits = 0;
689 grp->h = 0;
690 grp->modp = NULL;
691 grp->t_pre = NULL;
692 grp->t_post = NULL;
693 grp->t_data = NULL;
694 grp->T = NULL;
695 grp->T_size = 0;
696}
697
698/*
699 * Initialize (the components of) a key pair
700 */
701void mbedtls_ecp_keypair_init(mbedtls_ecp_keypair *key)
702{
703 ECP_VALIDATE(key != NULL);
704
705 mbedtls_ecp_group_init(&key->grp);
706 mbedtls_mpi_init(&key->d);
707 mbedtls_ecp_point_init(&key->Q);
708}
709
710/*
711 * Unallocate (the components of) a point
712 */
713void mbedtls_ecp_point_free(mbedtls_ecp_point *pt)
714{
715 if (pt == NULL) {
716 return;
717 }
718
719 mbedtls_mpi_free(&(pt->X));
720 mbedtls_mpi_free(&(pt->Y));
721 mbedtls_mpi_free(&(pt->Z));
722}
723
724/*
725 * Unallocate (the components of) a group
726 */
727void mbedtls_ecp_group_free(mbedtls_ecp_group *grp)
728{
729 size_t i;
730
731 if (grp == NULL) {
732 return;
733 }
734
735 if (grp->h != 1) {
736 mbedtls_mpi_free(&grp->P);
737 mbedtls_mpi_free(&grp->A);
738 mbedtls_mpi_free(&grp->B);
739 mbedtls_ecp_point_free(&grp->G);
740 mbedtls_mpi_free(&grp->N);
741 }
742
743 if (grp->T != NULL) {
744 for (i = 0; i < grp->T_size; i++) {
745 mbedtls_ecp_point_free(&grp->T[i]);
746 }
747 mbedtls_free(grp->T);
748 }
749
750 mbedtls_platform_zeroize(grp, sizeof(mbedtls_ecp_group));
751}
752
753/*
754 * Unallocate (the components of) a key pair
755 */
756void mbedtls_ecp_keypair_free(mbedtls_ecp_keypair *key)
757{
758 if (key == NULL) {
759 return;
760 }
761
762 mbedtls_ecp_group_free(&key->grp);
763 mbedtls_mpi_free(&key->d);
764 mbedtls_ecp_point_free(&key->Q);
765}
766
767/*
768 * Copy the contents of a point
769 */
770int mbedtls_ecp_copy(mbedtls_ecp_point *P, const mbedtls_ecp_point *Q)
771{
772 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
773 ECP_VALIDATE_RET(P != NULL);
774 ECP_VALIDATE_RET(Q != NULL);
775
776 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->X, &Q->X));
777 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->Y, &Q->Y));
778 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->Z, &Q->Z));
779
780cleanup:
781 return ret;
782}
783
784/*
785 * Copy the contents of a group object
786 */
787int mbedtls_ecp_group_copy(mbedtls_ecp_group *dst, const mbedtls_ecp_group *src)
788{
789 ECP_VALIDATE_RET(dst != NULL);
790 ECP_VALIDATE_RET(src != NULL);
791
792 return mbedtls_ecp_group_load(dst, src->id);
793}
794
795/*
796 * Set point to zero
797 */
798int mbedtls_ecp_set_zero(mbedtls_ecp_point *pt)
799{
800 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
801 ECP_VALIDATE_RET(pt != NULL);
802
803 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->X, 1));
804 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Y, 1));
805 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 0));
806
807cleanup:
808 return ret;
809}
810
811/*
812 * Tell if a point is zero
813 */
814int mbedtls_ecp_is_zero(mbedtls_ecp_point *pt)
815{
816 ECP_VALIDATE_RET(pt != NULL);
817
818 return mbedtls_mpi_cmp_int(&pt->Z, 0) == 0;
819}
820
821/*
822 * Compare two points lazily
823 */
824int mbedtls_ecp_point_cmp(const mbedtls_ecp_point *P,
825 const mbedtls_ecp_point *Q)
826{
827 ECP_VALIDATE_RET(P != NULL);
828 ECP_VALIDATE_RET(Q != NULL);
829
830 if (mbedtls_mpi_cmp_mpi(&P->X, &Q->X) == 0 &&
831 mbedtls_mpi_cmp_mpi(&P->Y, &Q->Y) == 0 &&
832 mbedtls_mpi_cmp_mpi(&P->Z, &Q->Z) == 0) {
833 return 0;
834 }
835
836 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
837}
838
839/*
840 * Import a non-zero point from ASCII strings
841 */
842int mbedtls_ecp_point_read_string(mbedtls_ecp_point *P, int radix,
843 const char *x, const char *y)
844{
845 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
846 ECP_VALIDATE_RET(P != NULL);
847 ECP_VALIDATE_RET(x != NULL);
848 ECP_VALIDATE_RET(y != NULL);
849
850 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&P->X, radix, x));
851 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&P->Y, radix, y));
852 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&P->Z, 1));
853
854cleanup:
855 return ret;
856}
857
858/*
859 * Export a point into unsigned binary data (SEC1 2.3.3 and RFC7748)
860 */
861int mbedtls_ecp_point_write_binary(const mbedtls_ecp_group *grp,
862 const mbedtls_ecp_point *P,
863 int format, size_t *olen,
864 unsigned char *buf, size_t buflen)
865{
866 int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
867 size_t plen;
868 ECP_VALIDATE_RET(grp != NULL);
869 ECP_VALIDATE_RET(P != NULL);
870 ECP_VALIDATE_RET(olen != NULL);
871 ECP_VALIDATE_RET(buf != NULL);
872 ECP_VALIDATE_RET(format == MBEDTLS_ECP_PF_UNCOMPRESSED ||
873 format == MBEDTLS_ECP_PF_COMPRESSED);
874
875 plen = mbedtls_mpi_size(&grp->P);
876
877#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
878 (void) format; /* Montgomery curves always use the same point format */
879 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
880 *olen = plen;
881 if (buflen < *olen) {
882 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
883 }
884
885 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary_le(&P->X, buf, plen));
886 }
887#endif
888#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
889 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
890 /*
891 * Common case: P == 0
892 */
893 if (mbedtls_mpi_cmp_int(&P->Z, 0) == 0) {
894 if (buflen < 1) {
895 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
896 }
897
898 buf[0] = 0x00;
899 *olen = 1;
900
901 return 0;
902 }
903
904 if (format == MBEDTLS_ECP_PF_UNCOMPRESSED) {
905 *olen = 2 * plen + 1;
906
907 if (buflen < *olen) {
908 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
909 }
910
911 buf[0] = 0x04;
912 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->X, buf + 1, plen));
913 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->Y, buf + 1 + plen, plen));
914 } else if (format == MBEDTLS_ECP_PF_COMPRESSED) {
915 *olen = plen + 1;
916
917 if (buflen < *olen) {
918 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
919 }
920
921 buf[0] = 0x02 + mbedtls_mpi_get_bit(&P->Y, 0);
922 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->X, buf + 1, plen));
923 }
924 }
925#endif
926
927cleanup:
928 return ret;
929}
930
931/*
932 * Import a point from unsigned binary data (SEC1 2.3.4 and RFC7748)
933 */
934int mbedtls_ecp_point_read_binary(const mbedtls_ecp_group *grp,
935 mbedtls_ecp_point *pt,
936 const unsigned char *buf, size_t ilen)
937{
938 int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
939 size_t plen;
940 ECP_VALIDATE_RET(grp != NULL);
941 ECP_VALIDATE_RET(pt != NULL);
942 ECP_VALIDATE_RET(buf != NULL);
943
944 if (ilen < 1) {
945 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
946 }
947
948 plen = mbedtls_mpi_size(&grp->P);
949
950#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
951 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
952 if (plen != ilen) {
953 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
954 }
955
956 MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary_le(&pt->X, buf, plen));
957 mbedtls_mpi_free(&pt->Y);
958
959 if (grp->id == MBEDTLS_ECP_DP_CURVE25519) {
960 /* Set most significant bit to 0 as prescribed in RFC7748 §5 */
961 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&pt->X, plen * 8 - 1, 0));
962 }
963
964 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 1));
965 }
966#endif
967#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
968 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
969 if (buf[0] == 0x00) {
970 if (ilen == 1) {
971 return mbedtls_ecp_set_zero(pt);
972 } else {
973 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
974 }
975 }
976
977 if (buf[0] != 0x04) {
978 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
979 }
980
981 if (ilen != 2 * plen + 1) {
982 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
983 }
984
985 MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(&pt->X, buf + 1, plen));
986 MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(&pt->Y,
987 buf + 1 + plen, plen));
988 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 1));
989 }
990#endif
991
992cleanup:
993 return ret;
994}
995
996/*
997 * Import a point from a TLS ECPoint record (RFC 4492)
998 * struct {
999 * opaque point <1..2^8-1>;
1000 * } ECPoint;
1001 */
1002int mbedtls_ecp_tls_read_point(const mbedtls_ecp_group *grp,
1003 mbedtls_ecp_point *pt,
1004 const unsigned char **buf, size_t buf_len)
1005{
1006 unsigned char data_len;
1007 const unsigned char *buf_start;
1008 ECP_VALIDATE_RET(grp != NULL);
1009 ECP_VALIDATE_RET(pt != NULL);
1010 ECP_VALIDATE_RET(buf != NULL);
1011 ECP_VALIDATE_RET(*buf != NULL);
1012
1013 /*
1014 * We must have at least two bytes (1 for length, at least one for data)
1015 */
1016 if (buf_len < 2) {
1017 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1018 }
1019
1020 data_len = *(*buf)++;
1021 if (data_len < 1 || data_len > buf_len - 1) {
1022 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1023 }
1024
1025 /*
1026 * Save buffer start for read_binary and update buf
1027 */
1028 buf_start = *buf;
1029 *buf += data_len;
1030
1031 return mbedtls_ecp_point_read_binary(grp, pt, buf_start, data_len);
1032}
1033
1034/*
1035 * Export a point as a TLS ECPoint record (RFC 4492)
1036 * struct {
1037 * opaque point <1..2^8-1>;
1038 * } ECPoint;
1039 */
1040int mbedtls_ecp_tls_write_point(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt,
1041 int format, size_t *olen,
1042 unsigned char *buf, size_t blen)
1043{
1044 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1045 ECP_VALIDATE_RET(grp != NULL);
1046 ECP_VALIDATE_RET(pt != NULL);
1047 ECP_VALIDATE_RET(olen != NULL);
1048 ECP_VALIDATE_RET(buf != NULL);
1049 ECP_VALIDATE_RET(format == MBEDTLS_ECP_PF_UNCOMPRESSED ||
1050 format == MBEDTLS_ECP_PF_COMPRESSED);
1051
1052 /*
1053 * buffer length must be at least one, for our length byte
1054 */
1055 if (blen < 1) {
1056 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1057 }
1058
1059 if ((ret = mbedtls_ecp_point_write_binary(grp, pt, format,
1060 olen, buf + 1, blen - 1)) != 0) {
1061 return ret;
1062 }
1063
1064 /*
1065 * write length to the first byte and update total length
1066 */
1067 buf[0] = (unsigned char) *olen;
1068 ++*olen;
1069
1070 return 0;
1071}
1072
1073/*
1074 * Set a group from an ECParameters record (RFC 4492)
1075 */
1076int mbedtls_ecp_tls_read_group(mbedtls_ecp_group *grp,
1077 const unsigned char **buf, size_t len)
1078{
1079 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1080 mbedtls_ecp_group_id grp_id;
1081 ECP_VALIDATE_RET(grp != NULL);
1082 ECP_VALIDATE_RET(buf != NULL);
1083 ECP_VALIDATE_RET(*buf != NULL);
1084
1085 if ((ret = mbedtls_ecp_tls_read_group_id(&grp_id, buf, len)) != 0) {
1086 return ret;
1087 }
1088
1089 return mbedtls_ecp_group_load(grp, grp_id);
1090}
1091
1092/*
1093 * Read a group id from an ECParameters record (RFC 4492) and convert it to
1094 * mbedtls_ecp_group_id.
1095 */
1096int mbedtls_ecp_tls_read_group_id(mbedtls_ecp_group_id *grp,
1097 const unsigned char **buf, size_t len)
1098{
1099 uint16_t tls_id;
1100 const mbedtls_ecp_curve_info *curve_info;
1101 ECP_VALIDATE_RET(grp != NULL);
1102 ECP_VALIDATE_RET(buf != NULL);
1103 ECP_VALIDATE_RET(*buf != NULL);
1104
1105 /*
1106 * We expect at least three bytes (see below)
1107 */
1108 if (len < 3) {
1109 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1110 }
1111
1112 /*
1113 * First byte is curve_type; only named_curve is handled
1114 */
1115 if (*(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE) {
1116 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1117 }
1118
1119 /*
1120 * Next two bytes are the namedcurve value
1121 */
1122 tls_id = *(*buf)++;
1123 tls_id <<= 8;
1124 tls_id |= *(*buf)++;
1125
1126 if ((curve_info = mbedtls_ecp_curve_info_from_tls_id(tls_id)) == NULL) {
1127 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1128 }
1129
1130 *grp = curve_info->grp_id;
1131
1132 return 0;
1133}
1134
1135/*
1136 * Write the ECParameters record corresponding to a group (RFC 4492)
1137 */
1138int mbedtls_ecp_tls_write_group(const mbedtls_ecp_group *grp, size_t *olen,
1139 unsigned char *buf, size_t blen)
1140{
1141 const mbedtls_ecp_curve_info *curve_info;
1142 ECP_VALIDATE_RET(grp != NULL);
1143 ECP_VALIDATE_RET(buf != NULL);
1144 ECP_VALIDATE_RET(olen != NULL);
1145
1146 if ((curve_info = mbedtls_ecp_curve_info_from_grp_id(grp->id)) == NULL) {
1147 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1148 }
1149
1150 /*
1151 * We are going to write 3 bytes (see below)
1152 */
1153 *olen = 3;
1154 if (blen < *olen) {
1155 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
1156 }
1157
1158 /*
1159 * First byte is curve_type, always named_curve
1160 */
1161 *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
1162
1163 /*
1164 * Next two bytes are the namedcurve value
1165 */
1166 MBEDTLS_PUT_UINT16_BE(curve_info->tls_id, buf, 0);
1167
1168 return 0;
1169}
1170
1171/*
1172 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
1173 * See the documentation of struct mbedtls_ecp_group.
1174 *
1175 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
1176 */
1177static int ecp_modp(mbedtls_mpi *N, const mbedtls_ecp_group *grp)
1178{
1179 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1180
1181 if (grp->modp == NULL) {
1182 return mbedtls_mpi_mod_mpi(N, N, &grp->P);
1183 }
1184
1185 /* N->s < 0 is a much faster test, which fails only if N is 0 */
1186 if ((N->s < 0 && mbedtls_mpi_cmp_int(N, 0) != 0) ||
1187 mbedtls_mpi_bitlen(N) > 2 * grp->pbits) {
1188 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1189 }
1190
1191 MBEDTLS_MPI_CHK(grp->modp(N));
1192
1193 /* N->s < 0 is a much faster test, which fails only if N is 0 */
1194 while (N->s < 0 && mbedtls_mpi_cmp_int(N, 0) != 0) {
1195 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(N, N, &grp->P));
1196 }
1197
1198 while (mbedtls_mpi_cmp_mpi(N, &grp->P) >= 0) {
1199 /* we known P, N and the result are positive */
1200 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(N, N, &grp->P));
1201 }
1202
1203cleanup:
1204 return ret;
1205}
1206
1207/*
1208 * Fast mod-p functions expect their argument to be in the 0..p^2 range.
1209 *
1210 * In order to guarantee that, we need to ensure that operands of
1211 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
1212 * bring the result back to this range.
1213 *
1214 * The following macros are shortcuts for doing that.
1215 */
1216
1217/*
1218 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
1219 */
1220#if defined(MBEDTLS_SELF_TEST)
1221#define INC_MUL_COUNT mul_count++;
1222#else
1223#define INC_MUL_COUNT
1224#endif
1225
1226#define MOD_MUL(N) \
1227 do \
1228 { \
1229 MBEDTLS_MPI_CHK(ecp_modp(&(N), grp)); \
1230 INC_MUL_COUNT \
1231 } while (0)
1232
1233static inline int mbedtls_mpi_mul_mod(const mbedtls_ecp_group *grp,
1234 mbedtls_mpi *X,
1235 const mbedtls_mpi *A,
1236 const mbedtls_mpi *B)
1237{
1238 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1239 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(X, A, B));
1240 MOD_MUL(*X);
1241cleanup:
1242 return ret;
1243}
1244
1245/*
1246 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
1247 * N->s < 0 is a very fast test, which fails only if N is 0
1248 */
1249#define MOD_SUB(N) \
1250 while ((N).s < 0 && mbedtls_mpi_cmp_int(&(N), 0) != 0) \
1251 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&(N), &(N), &grp->P))
1252
1253#if (defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) && \
1254 !(defined(MBEDTLS_ECP_NO_FALLBACK) && \
1255 defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) && \
1256 defined(MBEDTLS_ECP_ADD_MIXED_ALT))) || \
1257 (defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) && \
1258 !(defined(MBEDTLS_ECP_NO_FALLBACK) && \
1259 defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)))
1260static inline int mbedtls_mpi_sub_mod(const mbedtls_ecp_group *grp,
1261 mbedtls_mpi *X,
1262 const mbedtls_mpi *A,
1263 const mbedtls_mpi *B)
1264{
1265 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1266 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(X, A, B));
1267 MOD_SUB(*X);
1268cleanup:
1269 return ret;
1270}
1271#endif /* All functions referencing mbedtls_mpi_sub_mod() are alt-implemented without fallback */
1272
1273/*
1274 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
1275 * We known P, N and the result are positive, so sub_abs is correct, and
1276 * a bit faster.
1277 */
1278#define MOD_ADD(N) \
1279 while (mbedtls_mpi_cmp_mpi(&(N), &grp->P) >= 0) \
1280 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&(N), &(N), &grp->P))
1281
1282static inline int mbedtls_mpi_add_mod(const mbedtls_ecp_group *grp,
1283 mbedtls_mpi *X,
1284 const mbedtls_mpi *A,
1285 const mbedtls_mpi *B)
1286{
1287 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1288 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, A, B));
1289 MOD_ADD(*X);
1290cleanup:
1291 return ret;
1292}
1293
1294#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) && \
1295 !(defined(MBEDTLS_ECP_NO_FALLBACK) && \
1296 defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) && \
1297 defined(MBEDTLS_ECP_ADD_MIXED_ALT))
1298static inline int mbedtls_mpi_shift_l_mod(const mbedtls_ecp_group *grp,
1299 mbedtls_mpi *X,
1300 size_t count)
1301{
1302 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1303 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(X, count));
1304 MOD_ADD(*X);
1305cleanup:
1306 return ret;
1307}
1308#endif \
1309 /* All functions referencing mbedtls_mpi_shift_l_mod() are alt-implemented without fallback */
1310
1311#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
1312/*
1313 * For curves in short Weierstrass form, we do all the internal operations in
1314 * Jacobian coordinates.
1315 *
1316 * For multiplication, we'll use a comb method with countermeasures against
1317 * SPA, hence timing attacks.
1318 */
1319
1320/*
1321 * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1)
1322 * Cost: 1N := 1I + 3M + 1S
1323 */
1324static int ecp_normalize_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt)
1325{
1326 if (mbedtls_mpi_cmp_int(&pt->Z, 0) == 0) {
1327 return 0;
1328 }
1329
1330#if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
1331 if (mbedtls_internal_ecp_grp_capable(grp)) {
1332 return mbedtls_internal_ecp_normalize_jac(grp, pt);
1333 }
1334#endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */
1335
1336#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
1337 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1338#else
1339 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1340 mbedtls_mpi Zi, ZZi;
1341 mbedtls_mpi_init(&Zi); mbedtls_mpi_init(&ZZi);
1342
1343 /*
1344 * X = X / Z^2 mod p
1345 */
1346 MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&Zi, &pt->Z, &grp->P));
1347 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &ZZi, &Zi, &Zi));
1348 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->X, &pt->X, &ZZi));
1349
1350 /*
1351 * Y = Y / Z^3 mod p
1352 */
1353 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->Y, &pt->Y, &ZZi));
1354 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->Y, &pt->Y, &Zi));
1355
1356 /*
1357 * Z = 1
1358 */
1359 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 1));
1360
1361cleanup:
1362
1363 mbedtls_mpi_free(&Zi); mbedtls_mpi_free(&ZZi);
1364
1365 return ret;
1366#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) */
1367}
1368
1369/*
1370 * Normalize jacobian coordinates of an array of (pointers to) points,
1371 * using Montgomery's trick to perform only one inversion mod P.
1372 * (See for example Cohen's "A Course in Computational Algebraic Number
1373 * Theory", Algorithm 10.3.4.)
1374 *
1375 * Warning: fails (returning an error) if one of the points is zero!
1376 * This should never happen, see choice of w in ecp_mul_comb().
1377 *
1378 * Cost: 1N(t) := 1I + (6t - 3)M + 1S
1379 */
1380static int ecp_normalize_jac_many(const mbedtls_ecp_group *grp,
1381 mbedtls_ecp_point *T[], size_t T_size)
1382{
1383 if (T_size < 2) {
1384 return ecp_normalize_jac(grp, *T);
1385 }
1386
1387#if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
1388 if (mbedtls_internal_ecp_grp_capable(grp)) {
1389 return mbedtls_internal_ecp_normalize_jac_many(grp, T, T_size);
1390 }
1391#endif
1392
1393#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
1394 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1395#else
1396 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1397 size_t i;
1398 mbedtls_mpi *c, u, Zi, ZZi;
1399
1400 if ((c = mbedtls_calloc(T_size, sizeof(mbedtls_mpi))) == NULL) {
1401 return MBEDTLS_ERR_ECP_ALLOC_FAILED;
1402 }
1403
1404 for (i = 0; i < T_size; i++) {
1405 mbedtls_mpi_init(&c[i]);
1406 }
1407
1408 mbedtls_mpi_init(&u); mbedtls_mpi_init(&Zi); mbedtls_mpi_init(&ZZi);
1409
1410 /*
1411 * c[i] = Z_0 * ... * Z_i
1412 */
1413 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&c[0], &T[0]->Z));
1414 for (i = 1; i < T_size; i++) {
1415 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &c[i], &c[i-1], &T[i]->Z));
1416 }
1417
1418 /*
1419 * u = 1 / (Z_0 * ... * Z_n) mod P
1420 */
1421 MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&u, &c[T_size-1], &grp->P));
1422
1423 for (i = T_size - 1;; i--) {
1424 /*
1425 * Zi = 1 / Z_i mod p
1426 * u = 1 / (Z_0 * ... * Z_i) mod P
1427 */
1428 if (i == 0) {
1429 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Zi, &u));
1430 } else {
1431 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &Zi, &u, &c[i-1]));
1432 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &u, &u, &T[i]->Z));
1433 }
1434
1435 /*
1436 * proceed as in normalize()
1437 */
1438 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &ZZi, &Zi, &Zi));
1439 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T[i]->X, &T[i]->X, &ZZi));
1440 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T[i]->Y, &T[i]->Y, &ZZi));
1441 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T[i]->Y, &T[i]->Y, &Zi));
1442
1443 /*
1444 * Post-precessing: reclaim some memory by shrinking coordinates
1445 * - not storing Z (always 1)
1446 * - shrinking other coordinates, but still keeping the same number of
1447 * limbs as P, as otherwise it will too likely be regrown too fast.
1448 */
1449 MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(&T[i]->X, grp->P.n));
1450 MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(&T[i]->Y, grp->P.n));
1451 mbedtls_mpi_free(&T[i]->Z);
1452
1453 if (i == 0) {
1454 break;
1455 }
1456 }
1457
1458cleanup:
1459
1460 mbedtls_mpi_free(&u); mbedtls_mpi_free(&Zi); mbedtls_mpi_free(&ZZi);
1461 for (i = 0; i < T_size; i++) {
1462 mbedtls_mpi_free(&c[i]);
1463 }
1464 mbedtls_free(c);
1465
1466 return ret;
1467#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) */
1468}
1469
1470/*
1471 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
1472 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
1473 */
1474static int ecp_safe_invert_jac(const mbedtls_ecp_group *grp,
1475 mbedtls_ecp_point *Q,
1476 unsigned char inv)
1477{
1478 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1479 unsigned char nonzero;
1480 mbedtls_mpi mQY;
1481
1482 mbedtls_mpi_init(&mQY);
1483
1484 /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
1485 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&mQY, &grp->P, &Q->Y));
1486 nonzero = mbedtls_mpi_cmp_int(&Q->Y, 0) != 0;
1487 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(&Q->Y, &mQY, inv & nonzero));
1488
1489cleanup:
1490 mbedtls_mpi_free(&mQY);
1491
1492 return ret;
1493}
1494
1495/*
1496 * Point doubling R = 2 P, Jacobian coordinates
1497 *
1498 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
1499 *
1500 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR
1501 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.
1502 *
1503 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
1504 *
1505 * Cost: 1D := 3M + 4S (A == 0)
1506 * 4M + 4S (A == -3)
1507 * 3M + 6S + 1a otherwise
1508 */
1509static int ecp_double_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1510 const mbedtls_ecp_point *P)
1511{
1512#if defined(MBEDTLS_SELF_TEST)
1513 dbl_count++;
1514#endif
1515
1516#if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
1517 if (mbedtls_internal_ecp_grp_capable(grp)) {
1518 return mbedtls_internal_ecp_double_jac(grp, R, P);
1519 }
1520#endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */
1521
1522#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
1523 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1524#else
1525 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1526 mbedtls_mpi M, S, T, U;
1527
1528 mbedtls_mpi_init(&M); mbedtls_mpi_init(&S); mbedtls_mpi_init(&T); mbedtls_mpi_init(&U);
1529
1530 /* Special case for A = -3 */
1531 if (grp->A.p == NULL) {
1532 /* M = 3(X + Z^2)(X - Z^2) */
1533 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &P->Z, &P->Z));
1534 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &T, &P->X, &S));
1535 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &U, &P->X, &S));
1536 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &T, &U));
1537 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&M, &S, 3)); MOD_ADD(M);
1538 } else {
1539 /* M = 3.X^2 */
1540 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &P->X, &P->X));
1541 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&M, &S, 3)); MOD_ADD(M);
1542
1543 /* Optimize away for "koblitz" curves with A = 0 */
1544 if (mbedtls_mpi_cmp_int(&grp->A, 0) != 0) {
1545 /* M += A.Z^4 */
1546 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &P->Z, &P->Z));
1547 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T, &S, &S));
1548 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &T, &grp->A));
1549 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &M, &M, &S));
1550 }
1551 }
1552
1553 /* S = 4.X.Y^2 */
1554 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T, &P->Y, &P->Y));
1555 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, &T, 1));
1556 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &P->X, &T));
1557 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, &S, 1));
1558
1559 /* U = 8.Y^4 */
1560 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &U, &T, &T));
1561 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, &U, 1));
1562
1563 /* T = M^2 - 2.S */
1564 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T, &M, &M));
1565 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &T, &T, &S));
1566 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &T, &T, &S));
1567
1568 /* S = M(S - T) - U */
1569 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &S, &S, &T));
1570 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &S, &M));
1571 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &S, &S, &U));
1572
1573 /* U = 2.Y.Z */
1574 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &U, &P->Y, &P->Z));
1575 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, &U, 1));
1576
1577 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->X, &T));
1578 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->Y, &S));
1579 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->Z, &U));
1580
1581cleanup:
1582 mbedtls_mpi_free(&M); mbedtls_mpi_free(&S); mbedtls_mpi_free(&T); mbedtls_mpi_free(&U);
1583
1584 return ret;
1585#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) */
1586}
1587
1588/*
1589 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
1590 *
1591 * The coordinates of Q must be normalized (= affine),
1592 * but those of P don't need to. R is not normalized.
1593 *
1594 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
1595 * None of these cases can happen as intermediate step in ecp_mul_comb():
1596 * - at each step, P, Q and R are multiples of the base point, the factor
1597 * being less than its order, so none of them is zero;
1598 * - Q is an odd multiple of the base point, P an even multiple,
1599 * due to the choice of precomputed points in the modified comb method.
1600 * So branches for these cases do not leak secret information.
1601 *
1602 * We accept Q->Z being unset (saving memory in tables) as meaning 1.
1603 *
1604 * Cost: 1A := 8M + 3S
1605 */
1606static int ecp_add_mixed(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1607 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q)
1608{
1609#if defined(MBEDTLS_SELF_TEST)
1610 add_count++;
1611#endif
1612
1613#if defined(MBEDTLS_ECP_ADD_MIXED_ALT)
1614 if (mbedtls_internal_ecp_grp_capable(grp)) {
1615 return mbedtls_internal_ecp_add_mixed(grp, R, P, Q);
1616 }
1617#endif /* MBEDTLS_ECP_ADD_MIXED_ALT */
1618
1619#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_ADD_MIXED_ALT)
1620 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1621#else
1622 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1623 mbedtls_mpi T1, T2, T3, T4, X, Y, Z;
1624
1625 /*
1626 * Trivial cases: P == 0 or Q == 0 (case 1)
1627 */
1628 if (mbedtls_mpi_cmp_int(&P->Z, 0) == 0) {
1629 return mbedtls_ecp_copy(R, Q);
1630 }
1631
1632 if (Q->Z.p != NULL && mbedtls_mpi_cmp_int(&Q->Z, 0) == 0) {
1633 return mbedtls_ecp_copy(R, P);
1634 }
1635
1636 /*
1637 * Make sure Q coordinates are normalized
1638 */
1639 if (Q->Z.p != NULL && mbedtls_mpi_cmp_int(&Q->Z, 1) != 0) {
1640 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1641 }
1642
1643 mbedtls_mpi_init(&T1); mbedtls_mpi_init(&T2); mbedtls_mpi_init(&T3); mbedtls_mpi_init(&T4);
1644 mbedtls_mpi_init(&X); mbedtls_mpi_init(&Y); mbedtls_mpi_init(&Z);
1645
1646 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T1, &P->Z, &P->Z));
1647 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T2, &T1, &P->Z));
1648 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T1, &T1, &Q->X));
1649 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T2, &T2, &Q->Y));
1650 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &T1, &T1, &P->X));
1651 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &T2, &T2, &P->Y));
1652
1653 /* Special cases (2) and (3) */
1654 if (mbedtls_mpi_cmp_int(&T1, 0) == 0) {
1655 if (mbedtls_mpi_cmp_int(&T2, 0) == 0) {
1656 ret = ecp_double_jac(grp, R, P);
1657 goto cleanup;
1658 } else {
1659 ret = mbedtls_ecp_set_zero(R);
1660 goto cleanup;
1661 }
1662 }
1663
1664 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &Z, &P->Z, &T1));
1665 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T3, &T1, &T1));
1666 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T4, &T3, &T1));
1667 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T3, &T3, &P->X));
1668 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T1, &T3));
1669 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, &T1, 1));
1670 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &X, &T2, &T2));
1671 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &X, &X, &T1));
1672 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &X, &X, &T4));
1673 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &T3, &T3, &X));
1674 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T3, &T3, &T2));
1675 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T4, &T4, &P->Y));
1676 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &Y, &T3, &T4));
1677
1678 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->X, &X));
1679 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->Y, &Y));
1680 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->Z, &Z));
1681
1682cleanup:
1683
1684 mbedtls_mpi_free(&T1); mbedtls_mpi_free(&T2); mbedtls_mpi_free(&T3); mbedtls_mpi_free(&T4);
1685 mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z);
1686
1687 return ret;
1688#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_ADD_MIXED_ALT) */
1689}
1690
1691/*
1692 * Randomize jacobian coordinates:
1693 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
1694 * This is sort of the reverse operation of ecp_normalize_jac().
1695 *
1696 * This countermeasure was first suggested in [2].
1697 */
1698static int ecp_randomize_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
1699 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
1700{
1701#if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
1702 if (mbedtls_internal_ecp_grp_capable(grp)) {
1703 return mbedtls_internal_ecp_randomize_jac(grp, pt, f_rng, p_rng);
1704 }
1705#endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */
1706
1707#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
1708 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1709#else
1710 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1711 mbedtls_mpi l, ll;
1712
1713 mbedtls_mpi_init(&l); mbedtls_mpi_init(&ll);
1714
1715 /* Generate l such that 1 < l < p */
1716 MBEDTLS_MPI_CHK(mbedtls_mpi_random(&l, 2, &grp->P, f_rng, p_rng));
1717
1718 /* Z = l * Z */
1719 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->Z, &pt->Z, &l));
1720
1721 /* X = l^2 * X */
1722 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &ll, &l, &l));
1723 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->X, &pt->X, &ll));
1724
1725 /* Y = l^3 * Y */
1726 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &ll, &ll, &l));
1727 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->Y, &pt->Y, &ll));
1728
1729cleanup:
1730 mbedtls_mpi_free(&l); mbedtls_mpi_free(&ll);
1731
1732 if (ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
1733 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
1734 }
1735 return ret;
1736#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) */
1737}
1738
1739/*
1740 * Check and define parameters used by the comb method (see below for details)
1741 */
1742#if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7
1743#error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"
1744#endif
1745
1746/* d = ceil( n / w ) */
1747#define COMB_MAX_D (MBEDTLS_ECP_MAX_BITS + 1) / 2
1748
1749/* number of precomputed points */
1750#define COMB_MAX_PRE (1 << (MBEDTLS_ECP_WINDOW_SIZE - 1))
1751
1752/*
1753 * Compute the representation of m that will be used with our comb method.
1754 *
1755 * The basic comb method is described in GECC 3.44 for example. We use a
1756 * modified version that provides resistance to SPA by avoiding zero
1757 * digits in the representation as in [3]. We modify the method further by
1758 * requiring that all K_i be odd, which has the small cost that our
1759 * representation uses one more K_i, due to carries, but saves on the size of
1760 * the precomputed table.
1761 *
1762 * Summary of the comb method and its modifications:
1763 *
1764 * - The goal is to compute m*P for some w*d-bit integer m.
1765 *
1766 * - The basic comb method splits m into the w-bit integers
1767 * x[0] .. x[d-1] where x[i] consists of the bits in m whose
1768 * index has residue i modulo d, and computes m * P as
1769 * S[x[0]] + 2 * S[x[1]] + .. + 2^(d-1) S[x[d-1]], where
1770 * S[i_{w-1} .. i_0] := i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + i_0 P.
1771 *
1772 * - If it happens that, say, x[i+1]=0 (=> S[x[i+1]]=0), one can replace the sum by
1773 * .. + 2^{i-1} S[x[i-1]] - 2^i S[x[i]] + 2^{i+1} S[x[i]] + 2^{i+2} S[x[i+2]] ..,
1774 * thereby successively converting it into a form where all summands
1775 * are nonzero, at the cost of negative summands. This is the basic idea of [3].
1776 *
1777 * - More generally, even if x[i+1] != 0, we can first transform the sum as
1778 * .. - 2^i S[x[i]] + 2^{i+1} ( S[x[i]] + S[x[i+1]] ) + 2^{i+2} S[x[i+2]] ..,
1779 * and then replace S[x[i]] + S[x[i+1]] = S[x[i] ^ x[i+1]] + 2 S[x[i] & x[i+1]].
1780 * Performing and iterating this procedure for those x[i] that are even
1781 * (keeping track of carry), we can transform the original sum into one of the form
1782 * S[x'[0]] +- 2 S[x'[1]] +- .. +- 2^{d-1} S[x'[d-1]] + 2^d S[x'[d]]
1783 * with all x'[i] odd. It is therefore only necessary to know S at odd indices,
1784 * which is why we are only computing half of it in the first place in
1785 * ecp_precompute_comb and accessing it with index abs(i) / 2 in ecp_select_comb.
1786 *
1787 * - For the sake of compactness, only the seven low-order bits of x[i]
1788 * are used to represent its absolute value (K_i in the paper), and the msb
1789 * of x[i] encodes the sign (s_i in the paper): it is set if and only if
1790 * if s_i == -1;
1791 *
1792 * Calling conventions:
1793 * - x is an array of size d + 1
1794 * - w is the size, ie number of teeth, of the comb, and must be between
1795 * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE)
1796 * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d
1797 * (the result will be incorrect if these assumptions are not satisfied)
1798 */
1799static void ecp_comb_recode_core(unsigned char x[], size_t d,
1800 unsigned char w, const mbedtls_mpi *m)
1801{
1802 size_t i, j;
1803 unsigned char c, cc, adjust;
1804
1805 memset(x, 0, d+1);
1806
1807 /* First get the classical comb values (except for x_d = 0) */
1808 for (i = 0; i < d; i++) {
1809 for (j = 0; j < w; j++) {
1810 x[i] |= mbedtls_mpi_get_bit(m, i + d * j) << j;
1811 }
1812 }
1813
1814 /* Now make sure x_1 .. x_d are odd */
1815 c = 0;
1816 for (i = 1; i <= d; i++) {
1817 /* Add carry and update it */
1818 cc = x[i] & c;
1819 x[i] = x[i] ^ c;
1820 c = cc;
1821
1822 /* Adjust if needed, avoiding branches */
1823 adjust = 1 - (x[i] & 0x01);
1824 c |= x[i] & (x[i-1] * adjust);
1825 x[i] = x[i] ^ (x[i-1] * adjust);
1826 x[i-1] |= adjust << 7;
1827 }
1828}
1829
1830/*
1831 * Precompute points for the adapted comb method
1832 *
1833 * Assumption: T must be able to hold 2^{w - 1} elements.
1834 *
1835 * Operation: If i = i_{w-1} ... i_1 is the binary representation of i,
1836 * sets T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P.
1837 *
1838 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
1839 *
1840 * Note: Even comb values (those where P would be omitted from the
1841 * sum defining T[i] above) are not needed in our adaption
1842 * the comb method. See ecp_comb_recode_core().
1843 *
1844 * This function currently works in four steps:
1845 * (1) [dbl] Computation of intermediate T[i] for 2-power values of i
1846 * (2) [norm_dbl] Normalization of coordinates of these T[i]
1847 * (3) [add] Computation of all T[i]
1848 * (4) [norm_add] Normalization of all T[i]
1849 *
1850 * Step 1 can be interrupted but not the others; together with the final
1851 * coordinate normalization they are the largest steps done at once, depending
1852 * on the window size. Here are operation counts for P-256:
1853 *
1854 * step (2) (3) (4)
1855 * w = 5 142 165 208
1856 * w = 4 136 77 160
1857 * w = 3 130 33 136
1858 * w = 2 124 11 124
1859 *
1860 * So if ECC operations are blocking for too long even with a low max_ops
1861 * value, it's useful to set MBEDTLS_ECP_WINDOW_SIZE to a lower value in order
1862 * to minimize maximum blocking time.
1863 */
1864static int ecp_precompute_comb(const mbedtls_ecp_group *grp,
1865 mbedtls_ecp_point T[], const mbedtls_ecp_point *P,
1866 unsigned char w, size_t d,
1867 mbedtls_ecp_restart_ctx *rs_ctx)
1868{
1869 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1870 unsigned char i;
1871 size_t j = 0;
1872 const unsigned char T_size = 1U << (w - 1);
1873 mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1];
1874
1875#if defined(MBEDTLS_ECP_RESTARTABLE)
1876 if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
1877 if (rs_ctx->rsm->state == ecp_rsm_pre_dbl) {
1878 goto dbl;
1879 }
1880 if (rs_ctx->rsm->state == ecp_rsm_pre_norm_dbl) {
1881 goto norm_dbl;
1882 }
1883 if (rs_ctx->rsm->state == ecp_rsm_pre_add) {
1884 goto add;
1885 }
1886 if (rs_ctx->rsm->state == ecp_rsm_pre_norm_add) {
1887 goto norm_add;
1888 }
1889 }
1890#else
1891 (void) rs_ctx;
1892#endif
1893
1894#if defined(MBEDTLS_ECP_RESTARTABLE)
1895 if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
1896 rs_ctx->rsm->state = ecp_rsm_pre_dbl;
1897
1898 /* initial state for the loop */
1899 rs_ctx->rsm->i = 0;
1900 }
1901
1902dbl:
1903#endif
1904 /*
1905 * Set T[0] = P and
1906 * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
1907 */
1908 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(&T[0], P));
1909
1910#if defined(MBEDTLS_ECP_RESTARTABLE)
1911 if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0) {
1912 j = rs_ctx->rsm->i;
1913 } else
1914#endif
1915 j = 0;
1916
1917 for (; j < d * (w - 1); j++) {
1918 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_DBL);
1919
1920 i = 1U << (j / d);
1921 cur = T + i;
1922
1923 if (j % d == 0) {
1924 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(cur, T + (i >> 1)));
1925 }
1926
1927 MBEDTLS_MPI_CHK(ecp_double_jac(grp, cur, cur));
1928 }
1929
1930#if defined(MBEDTLS_ECP_RESTARTABLE)
1931 if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
1932 rs_ctx->rsm->state = ecp_rsm_pre_norm_dbl;
1933 }
1934
1935norm_dbl:
1936#endif
1937 /*
1938 * Normalize current elements in T. As T has holes,
1939 * use an auxiliary array of pointers to elements in T.
1940 */
1941 j = 0;
1942 for (i = 1; i < T_size; i <<= 1) {
1943 TT[j++] = T + i;
1944 }
1945
1946 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV + 6 * j - 2);
1947
1948 MBEDTLS_MPI_CHK(ecp_normalize_jac_many(grp, TT, j));
1949
1950#if defined(MBEDTLS_ECP_RESTARTABLE)
1951 if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
1952 rs_ctx->rsm->state = ecp_rsm_pre_add;
1953 }
1954
1955add:
1956#endif
1957 /*
1958 * Compute the remaining ones using the minimal number of additions
1959 * Be careful to update T[2^l] only after using it!
1960 */
1961 MBEDTLS_ECP_BUDGET((T_size - 1) * MBEDTLS_ECP_OPS_ADD);
1962
1963 for (i = 1; i < T_size; i <<= 1) {
1964 j = i;
1965 while (j--) {
1966 MBEDTLS_MPI_CHK(ecp_add_mixed(grp, &T[i + j], &T[j], &T[i]));
1967 }
1968 }
1969
1970#if defined(MBEDTLS_ECP_RESTARTABLE)
1971 if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
1972 rs_ctx->rsm->state = ecp_rsm_pre_norm_add;
1973 }
1974
1975norm_add:
1976#endif
1977 /*
1978 * Normalize final elements in T. Even though there are no holes now, we
1979 * still need the auxiliary array for homogeneity with the previous
1980 * call. Also, skip T[0] which is already normalised, being a copy of P.
1981 */
1982 for (j = 0; j + 1 < T_size; j++) {
1983 TT[j] = T + j + 1;
1984 }
1985
1986 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV + 6 * j - 2);
1987
1988 MBEDTLS_MPI_CHK(ecp_normalize_jac_many(grp, TT, j));
1989
1990cleanup:
1991#if defined(MBEDTLS_ECP_RESTARTABLE)
1992 if (rs_ctx != NULL && rs_ctx->rsm != NULL &&
1993 ret == MBEDTLS_ERR_ECP_IN_PROGRESS) {
1994 if (rs_ctx->rsm->state == ecp_rsm_pre_dbl) {
1995 rs_ctx->rsm->i = j;
1996 }
1997 }
1998#endif
1999
2000 return ret;
2001}
2002
2003/*
2004 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
2005 *
2006 * See ecp_comb_recode_core() for background
2007 */
2008static int ecp_select_comb(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2009 const mbedtls_ecp_point T[], unsigned char T_size,
2010 unsigned char i)
2011{
2012 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2013 unsigned char ii, j;
2014
2015 /* Ignore the "sign" bit and scale down */
2016 ii = (i & 0x7Fu) >> 1;
2017
2018 /* Read the whole table to thwart cache-based timing attacks */
2019 for (j = 0; j < T_size; j++) {
2020 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(&R->X, &T[j].X, j == ii));
2021 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(&R->Y, &T[j].Y, j == ii));
2022 }
2023
2024 /* Safely invert result if i is "negative" */
2025 MBEDTLS_MPI_CHK(ecp_safe_invert_jac(grp, R, i >> 7));
2026
2027cleanup:
2028 return ret;
2029}
2030
2031/*
2032 * Core multiplication algorithm for the (modified) comb method.
2033 * This part is actually common with the basic comb method (GECC 3.44)
2034 *
2035 * Cost: d A + d D + 1 R
2036 */
2037static int ecp_mul_comb_core(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2038 const mbedtls_ecp_point T[], unsigned char T_size,
2039 const unsigned char x[], size_t d,
2040 int (*f_rng)(void *, unsigned char *, size_t),
2041 void *p_rng,
2042 mbedtls_ecp_restart_ctx *rs_ctx)
2043{
2044 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2045 mbedtls_ecp_point Txi;
2046 size_t i;
2047
2048 mbedtls_ecp_point_init(&Txi);
2049
2050#if !defined(MBEDTLS_ECP_RESTARTABLE)
2051 (void) rs_ctx;
2052#endif
2053
2054#if defined(MBEDTLS_ECP_RESTARTABLE)
2055 if (rs_ctx != NULL && rs_ctx->rsm != NULL &&
2056 rs_ctx->rsm->state != ecp_rsm_comb_core) {
2057 rs_ctx->rsm->i = 0;
2058 rs_ctx->rsm->state = ecp_rsm_comb_core;
2059 }
2060
2061 /* new 'if' instead of nested for the sake of the 'else' branch */
2062 if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0) {
2063 /* restore current index (R already pointing to rs_ctx->rsm->R) */
2064 i = rs_ctx->rsm->i;
2065 } else
2066#endif
2067 {
2068 int have_rng = 1;
2069
2070 /* Start with a non-zero point and randomize its coordinates */
2071 i = d;
2072 MBEDTLS_MPI_CHK(ecp_select_comb(grp, R, T, T_size, x[i]));
2073 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&R->Z, 1));
2074
2075#if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2076 if (f_rng == NULL) {
2077 have_rng = 0;
2078 }
2079#endif
2080 if (have_rng) {
2081 MBEDTLS_MPI_CHK(ecp_randomize_jac(grp, R, f_rng, p_rng));
2082 }
2083 }
2084
2085 while (i != 0) {
2086 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD);
2087 --i;
2088
2089 MBEDTLS_MPI_CHK(ecp_double_jac(grp, R, R));
2090 MBEDTLS_MPI_CHK(ecp_select_comb(grp, &Txi, T, T_size, x[i]));
2091 MBEDTLS_MPI_CHK(ecp_add_mixed(grp, R, R, &Txi));
2092 }
2093
2094cleanup:
2095
2096 mbedtls_ecp_point_free(&Txi);
2097
2098#if defined(MBEDTLS_ECP_RESTARTABLE)
2099 if (rs_ctx != NULL && rs_ctx->rsm != NULL &&
2100 ret == MBEDTLS_ERR_ECP_IN_PROGRESS) {
2101 rs_ctx->rsm->i = i;
2102 /* no need to save R, already pointing to rs_ctx->rsm->R */
2103 }
2104#endif
2105
2106 return ret;
2107}
2108
2109/*
2110 * Recode the scalar to get constant-time comb multiplication
2111 *
2112 * As the actual scalar recoding needs an odd scalar as a starting point,
2113 * this wrapper ensures that by replacing m by N - m if necessary, and
2114 * informs the caller that the result of multiplication will be negated.
2115 *
2116 * This works because we only support large prime order for Short Weierstrass
2117 * curves, so N is always odd hence either m or N - m is.
2118 *
2119 * See ecp_comb_recode_core() for background.
2120 */
2121static int ecp_comb_recode_scalar(const mbedtls_ecp_group *grp,
2122 const mbedtls_mpi *m,
2123 unsigned char k[COMB_MAX_D + 1],
2124 size_t d,
2125 unsigned char w,
2126 unsigned char *parity_trick)
2127{
2128 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2129 mbedtls_mpi M, mm;
2130
2131 mbedtls_mpi_init(&M);
2132 mbedtls_mpi_init(&mm);
2133
2134 /* N is always odd (see above), just make extra sure */
2135 if (mbedtls_mpi_get_bit(&grp->N, 0) != 1) {
2136 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
2137 }
2138
2139 /* do we need the parity trick? */
2140 *parity_trick = (mbedtls_mpi_get_bit(m, 0) == 0);
2141
2142 /* execute parity fix in constant time */
2143 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&M, m));
2144 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&mm, &grp->N, m));
2145 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(&M, &mm, *parity_trick));
2146
2147 /* actual scalar recoding */
2148 ecp_comb_recode_core(k, d, w, &M);
2149
2150cleanup:
2151 mbedtls_mpi_free(&mm);
2152 mbedtls_mpi_free(&M);
2153
2154 return ret;
2155}
2156
2157/*
2158 * Perform comb multiplication (for short Weierstrass curves)
2159 * once the auxiliary table has been pre-computed.
2160 *
2161 * Scalar recoding may use a parity trick that makes us compute -m * P,
2162 * if that is the case we'll need to recover m * P at the end.
2163 */
2164static int ecp_mul_comb_after_precomp(const mbedtls_ecp_group *grp,
2165 mbedtls_ecp_point *R,
2166 const mbedtls_mpi *m,
2167 const mbedtls_ecp_point *T,
2168 unsigned char T_size,
2169 unsigned char w,
2170 size_t d,
2171 int (*f_rng)(void *, unsigned char *, size_t),
2172 void *p_rng,
2173 mbedtls_ecp_restart_ctx *rs_ctx)
2174{
2175 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2176 unsigned char parity_trick;
2177 unsigned char k[COMB_MAX_D + 1];
2178 mbedtls_ecp_point *RR = R;
2179 int have_rng = 1;
2180
2181#if defined(MBEDTLS_ECP_RESTARTABLE)
2182 if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
2183 RR = &rs_ctx->rsm->R;
2184
2185 if (rs_ctx->rsm->state == ecp_rsm_final_norm) {
2186 goto final_norm;
2187 }
2188 }
2189#endif
2190
2191 MBEDTLS_MPI_CHK(ecp_comb_recode_scalar(grp, m, k, d, w,
2192 &parity_trick));
2193 MBEDTLS_MPI_CHK(ecp_mul_comb_core(grp, RR, T, T_size, k, d,
2194 f_rng, p_rng, rs_ctx));
2195 MBEDTLS_MPI_CHK(ecp_safe_invert_jac(grp, RR, parity_trick));
2196
2197#if defined(MBEDTLS_ECP_RESTARTABLE)
2198 if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
2199 rs_ctx->rsm->state = ecp_rsm_final_norm;
2200 }
2201
2202final_norm:
2203 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV);
2204#endif
2205 /*
2206 * Knowledge of the jacobian coordinates may leak the last few bits of the
2207 * scalar [1], and since our MPI implementation isn't constant-flow,
2208 * inversion (used for coordinate normalization) may leak the full value
2209 * of its input via side-channels [2].
2210 *
2211 * [1] https://eprint.iacr.org/2003/191
2212 * [2] https://eprint.iacr.org/2020/055
2213 *
2214 * Avoid the leak by randomizing coordinates before we normalize them.
2215 */
2216#if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2217 if (f_rng == NULL) {
2218 have_rng = 0;
2219 }
2220#endif
2221 if (have_rng) {
2222 MBEDTLS_MPI_CHK(ecp_randomize_jac(grp, RR, f_rng, p_rng));
2223 }
2224
2225 MBEDTLS_MPI_CHK(ecp_normalize_jac(grp, RR));
2226
2227#if defined(MBEDTLS_ECP_RESTARTABLE)
2228 if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
2229 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, RR));
2230 }
2231#endif
2232
2233cleanup:
2234 return ret;
2235}
2236
2237/*
2238 * Pick window size based on curve size and whether we optimize for base point
2239 */
2240static unsigned char ecp_pick_window_size(const mbedtls_ecp_group *grp,
2241 unsigned char p_eq_g)
2242{
2243 unsigned char w;
2244
2245 /*
2246 * Minimize the number of multiplications, that is minimize
2247 * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
2248 * (see costs of the various parts, with 1S = 1M)
2249 */
2250 w = grp->nbits >= 384 ? 5 : 4;
2251
2252 /*
2253 * If P == G, pre-compute a bit more, since this may be re-used later.
2254 * Just adding one avoids upping the cost of the first mul too much,
2255 * and the memory cost too.
2256 */
2257 if (p_eq_g) {
2258 w++;
2259 }
2260
2261 /*
2262 * Make sure w is within bounds.
2263 * (The last test is useful only for very small curves in the test suite.)
2264 */
2265#if (MBEDTLS_ECP_WINDOW_SIZE < 6)
2266 if (w > MBEDTLS_ECP_WINDOW_SIZE) {
2267 w = MBEDTLS_ECP_WINDOW_SIZE;
2268 }
2269#endif
2270 if (w >= grp->nbits) {
2271 w = 2;
2272 }
2273
2274 return w;
2275}
2276
2277/*
2278 * Multiplication using the comb method - for curves in short Weierstrass form
2279 *
2280 * This function is mainly responsible for administrative work:
2281 * - managing the restart context if enabled
2282 * - managing the table of precomputed points (passed between the below two
2283 * functions): allocation, computation, ownership transfer, freeing.
2284 *
2285 * It delegates the actual arithmetic work to:
2286 * ecp_precompute_comb() and ecp_mul_comb_with_precomp()
2287 *
2288 * See comments on ecp_comb_recode_core() regarding the computation strategy.
2289 */
2290static int ecp_mul_comb(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2291 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2292 int (*f_rng)(void *, unsigned char *, size_t),
2293 void *p_rng,
2294 mbedtls_ecp_restart_ctx *rs_ctx)
2295{
2296 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2297 unsigned char w, p_eq_g, i;
2298 size_t d;
2299 unsigned char T_size = 0, T_ok = 0;
2300 mbedtls_ecp_point *T = NULL;
2301#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2302 ecp_drbg_context drbg_ctx;
2303
2304 ecp_drbg_init(&drbg_ctx);
2305#endif
2306
2307 ECP_RS_ENTER(rsm);
2308
2309#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2310 if (f_rng == NULL) {
2311 /* Adjust pointers */
2312 f_rng = &ecp_drbg_random;
2313#if defined(MBEDTLS_ECP_RESTARTABLE)
2314 if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
2315 p_rng = &rs_ctx->rsm->drbg_ctx;
2316 } else
2317#endif
2318 p_rng = &drbg_ctx;
2319
2320 /* Initialize internal DRBG if necessary */
2321#if defined(MBEDTLS_ECP_RESTARTABLE)
2322 if (rs_ctx == NULL || rs_ctx->rsm == NULL ||
2323 rs_ctx->rsm->drbg_seeded == 0)
2324#endif
2325 {
2326 const size_t m_len = (grp->nbits + 7) / 8;
2327 MBEDTLS_MPI_CHK(ecp_drbg_seed(p_rng, m, m_len));
2328 }
2329#if defined(MBEDTLS_ECP_RESTARTABLE)
2330 if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
2331 rs_ctx->rsm->drbg_seeded = 1;
2332 }
2333#endif
2334 }
2335#endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */
2336
2337 /* Is P the base point ? */
2338#if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
2339 p_eq_g = (mbedtls_mpi_cmp_mpi(&P->Y, &grp->G.Y) == 0 &&
2340 mbedtls_mpi_cmp_mpi(&P->X, &grp->G.X) == 0);
2341#else
2342 p_eq_g = 0;
2343#endif
2344
2345 /* Pick window size and deduce related sizes */
2346 w = ecp_pick_window_size(grp, p_eq_g);
2347 T_size = 1U << (w - 1);
2348 d = (grp->nbits + w - 1) / w;
2349
2350 /* Pre-computed table: do we have it already for the base point? */
2351 if (p_eq_g && grp->T != NULL) {
2352 /* second pointer to the same table, will be deleted on exit */
2353 T = grp->T;
2354 T_ok = 1;
2355 } else
2356#if defined(MBEDTLS_ECP_RESTARTABLE)
2357 /* Pre-computed table: do we have one in progress? complete? */
2358 if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->T != NULL) {
2359 /* transfer ownership of T from rsm to local function */
2360 T = rs_ctx->rsm->T;
2361 rs_ctx->rsm->T = NULL;
2362 rs_ctx->rsm->T_size = 0;
2363
2364 /* This effectively jumps to the call to mul_comb_after_precomp() */
2365 T_ok = rs_ctx->rsm->state >= ecp_rsm_comb_core;
2366 } else
2367#endif
2368 /* Allocate table if we didn't have any */
2369 {
2370 T = mbedtls_calloc(T_size, sizeof(mbedtls_ecp_point));
2371 if (T == NULL) {
2372 ret = MBEDTLS_ERR_ECP_ALLOC_FAILED;
2373 goto cleanup;
2374 }
2375
2376 for (i = 0; i < T_size; i++) {
2377 mbedtls_ecp_point_init(&T[i]);
2378 }
2379
2380 T_ok = 0;
2381 }
2382
2383 /* Compute table (or finish computing it) if not done already */
2384 if (!T_ok) {
2385 MBEDTLS_MPI_CHK(ecp_precompute_comb(grp, T, P, w, d, rs_ctx));
2386
2387 if (p_eq_g) {
2388 /* almost transfer ownership of T to the group, but keep a copy of
2389 * the pointer to use for calling the next function more easily */
2390 grp->T = T;
2391 grp->T_size = T_size;
2392 }
2393 }
2394
2395 /* Actual comb multiplication using precomputed points */
2396 MBEDTLS_MPI_CHK(ecp_mul_comb_after_precomp(grp, R, m,
2397 T, T_size, w, d,
2398 f_rng, p_rng, rs_ctx));
2399
2400cleanup:
2401
2402#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2403 ecp_drbg_free(&drbg_ctx);
2404#endif
2405
2406 /* does T belong to the group? */
2407 if (T == grp->T) {
2408 T = NULL;
2409 }
2410
2411 /* does T belong to the restart context? */
2412#if defined(MBEDTLS_ECP_RESTARTABLE)
2413 if (rs_ctx != NULL && rs_ctx->rsm != NULL && ret == MBEDTLS_ERR_ECP_IN_PROGRESS && T != NULL) {
2414 /* transfer ownership of T from local function to rsm */
2415 rs_ctx->rsm->T_size = T_size;
2416 rs_ctx->rsm->T = T;
2417 T = NULL;
2418 }
2419#endif
2420
2421 /* did T belong to us? then let's destroy it! */
2422 if (T != NULL) {
2423 for (i = 0; i < T_size; i++) {
2424 mbedtls_ecp_point_free(&T[i]);
2425 }
2426 mbedtls_free(T);
2427 }
2428
2429 /* prevent caller from using invalid value */
2430 int should_free_R = (ret != 0);
2431#if defined(MBEDTLS_ECP_RESTARTABLE)
2432 /* don't free R while in progress in case R == P */
2433 if (ret == MBEDTLS_ERR_ECP_IN_PROGRESS) {
2434 should_free_R = 0;
2435 }
2436#endif
2437 if (should_free_R) {
2438 mbedtls_ecp_point_free(R);
2439 }
2440
2441 ECP_RS_LEAVE(rsm);
2442
2443 return ret;
2444}
2445
2446#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
2447
2448#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
2449/*
2450 * For Montgomery curves, we do all the internal arithmetic in projective
2451 * coordinates. Import/export of points uses only the x coordinates, which is
2452 * internally represented as X / Z.
2453 *
2454 * For scalar multiplication, we'll use a Montgomery ladder.
2455 */
2456
2457/*
2458 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
2459 * Cost: 1M + 1I
2460 */
2461static int ecp_normalize_mxz(const mbedtls_ecp_group *grp, mbedtls_ecp_point *P)
2462{
2463#if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
2464 if (mbedtls_internal_ecp_grp_capable(grp)) {
2465 return mbedtls_internal_ecp_normalize_mxz(grp, P);
2466 }
2467#endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */
2468
2469#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
2470 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
2471#else
2472 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2473 MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&P->Z, &P->Z, &grp->P));
2474 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &P->X, &P->X, &P->Z));
2475 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&P->Z, 1));
2476
2477cleanup:
2478 return ret;
2479#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) */
2480}
2481
2482/*
2483 * Randomize projective x/z coordinates:
2484 * (X, Z) -> (l X, l Z) for random l
2485 * This is sort of the reverse operation of ecp_normalize_mxz().
2486 *
2487 * This countermeasure was first suggested in [2].
2488 * Cost: 2M
2489 */
2490static int ecp_randomize_mxz(const mbedtls_ecp_group *grp, mbedtls_ecp_point *P,
2491 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
2492{
2493#if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
2494 if (mbedtls_internal_ecp_grp_capable(grp)) {
2495 return mbedtls_internal_ecp_randomize_mxz(grp, P, f_rng, p_rng);
2496 }
2497#endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */
2498
2499#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
2500 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
2501#else
2502 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2503 mbedtls_mpi l;
2504 mbedtls_mpi_init(&l);
2505
2506 /* Generate l such that 1 < l < p */
2507 MBEDTLS_MPI_CHK(mbedtls_mpi_random(&l, 2, &grp->P, f_rng, p_rng));
2508
2509 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &P->X, &P->X, &l));
2510 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &P->Z, &P->Z, &l));
2511
2512cleanup:
2513 mbedtls_mpi_free(&l);
2514
2515 if (ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
2516 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
2517 }
2518 return ret;
2519#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) */
2520}
2521
2522/*
2523 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
2524 * for Montgomery curves in x/z coordinates.
2525 *
2526 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
2527 * with
2528 * d = X1
2529 * P = (X2, Z2)
2530 * Q = (X3, Z3)
2531 * R = (X4, Z4)
2532 * S = (X5, Z5)
2533 * and eliminating temporary variables tO, ..., t4.
2534 *
2535 * Cost: 5M + 4S
2536 */
2537static int ecp_double_add_mxz(const mbedtls_ecp_group *grp,
2538 mbedtls_ecp_point *R, mbedtls_ecp_point *S,
2539 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q,
2540 const mbedtls_mpi *d)
2541{
2542#if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
2543 if (mbedtls_internal_ecp_grp_capable(grp)) {
2544 return mbedtls_internal_ecp_double_add_mxz(grp, R, S, P, Q, d);
2545 }
2546#endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */
2547
2548#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
2549 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
2550#else
2551 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2552 mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB;
2553
2554 mbedtls_mpi_init(&A); mbedtls_mpi_init(&AA); mbedtls_mpi_init(&B);
2555 mbedtls_mpi_init(&BB); mbedtls_mpi_init(&E); mbedtls_mpi_init(&C);
2556 mbedtls_mpi_init(&D); mbedtls_mpi_init(&DA); mbedtls_mpi_init(&CB);
2557
2558 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &A, &P->X, &P->Z));
2559 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &AA, &A, &A));
2560 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &B, &P->X, &P->Z));
2561 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &BB, &B, &B));
2562 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &E, &AA, &BB));
2563 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &C, &Q->X, &Q->Z));
2564 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &D, &Q->X, &Q->Z));
2565 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &DA, &D, &A));
2566 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &CB, &C, &B));
2567 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &S->X, &DA, &CB));
2568 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S->X, &S->X, &S->X));
2569 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &S->Z, &DA, &CB));
2570 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S->Z, &S->Z, &S->Z));
2571 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S->Z, d, &S->Z));
2572 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &R->X, &AA, &BB));
2573 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &R->Z, &grp->A, &E));
2574 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &R->Z, &BB, &R->Z));
2575 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &R->Z, &E, &R->Z));
2576
2577cleanup:
2578 mbedtls_mpi_free(&A); mbedtls_mpi_free(&AA); mbedtls_mpi_free(&B);
2579 mbedtls_mpi_free(&BB); mbedtls_mpi_free(&E); mbedtls_mpi_free(&C);
2580 mbedtls_mpi_free(&D); mbedtls_mpi_free(&DA); mbedtls_mpi_free(&CB);
2581
2582 return ret;
2583#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) */
2584}
2585
2586/*
2587 * Multiplication with Montgomery ladder in x/z coordinates,
2588 * for curves in Montgomery form
2589 */
2590static int ecp_mul_mxz(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2591 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2592 int (*f_rng)(void *, unsigned char *, size_t),
2593 void *p_rng)
2594{
2595 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2596 int have_rng = 1;
2597 size_t i;
2598 unsigned char b;
2599 mbedtls_ecp_point RP;
2600 mbedtls_mpi PX;
2601#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2602 ecp_drbg_context drbg_ctx;
2603
2604 ecp_drbg_init(&drbg_ctx);
2605#endif
2606 mbedtls_ecp_point_init(&RP); mbedtls_mpi_init(&PX);
2607
2608#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2609 if (f_rng == NULL) {
2610 const size_t m_len = (grp->nbits + 7) / 8;
2611 MBEDTLS_MPI_CHK(ecp_drbg_seed(&drbg_ctx, m, m_len));
2612 f_rng = &ecp_drbg_random;
2613 p_rng = &drbg_ctx;
2614 }
2615#endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */
2616
2617 /* Save PX and read from P before writing to R, in case P == R */
2618 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&PX, &P->X));
2619 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(&RP, P));
2620
2621 /* Set R to zero in modified x/z coordinates */
2622 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&R->X, 1));
2623 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&R->Z, 0));
2624 mbedtls_mpi_free(&R->Y);
2625
2626 /* RP.X might be slightly larger than P, so reduce it */
2627 MOD_ADD(RP.X);
2628
2629#if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2630 /* Derandomize coordinates of the starting point */
2631 if (f_rng == NULL) {
2632 have_rng = 0;
2633 }
2634#endif
2635 if (have_rng) {
2636 MBEDTLS_MPI_CHK(ecp_randomize_mxz(grp, &RP, f_rng, p_rng));
2637 }
2638
2639 /* Loop invariant: R = result so far, RP = R + P */
2640 i = grp->nbits + 1; /* one past the (zero-based) required msb for private keys */
2641 while (i-- > 0) {
2642 b = mbedtls_mpi_get_bit(m, i);
2643 /*
2644 * if (b) R = 2R + P else R = 2R,
2645 * which is:
2646 * if (b) double_add( RP, R, RP, R )
2647 * else double_add( R, RP, R, RP )
2648 * but using safe conditional swaps to avoid leaks
2649 */
2650 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_swap(&R->X, &RP.X, b));
2651 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_swap(&R->Z, &RP.Z, b));
2652 MBEDTLS_MPI_CHK(ecp_double_add_mxz(grp, R, &RP, R, &RP, &PX));
2653 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_swap(&R->X, &RP.X, b));
2654 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_swap(&R->Z, &RP.Z, b));
2655 }
2656
2657 /*
2658 * Knowledge of the projective coordinates may leak the last few bits of the
2659 * scalar [1], and since our MPI implementation isn't constant-flow,
2660 * inversion (used for coordinate normalization) may leak the full value
2661 * of its input via side-channels [2].
2662 *
2663 * [1] https://eprint.iacr.org/2003/191
2664 * [2] https://eprint.iacr.org/2020/055
2665 *
2666 * Avoid the leak by randomizing coordinates before we normalize them.
2667 */
2668 have_rng = 1;
2669#if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2670 if (f_rng == NULL) {
2671 have_rng = 0;
2672 }
2673#endif
2674 if (have_rng) {
2675 MBEDTLS_MPI_CHK(ecp_randomize_mxz(grp, R, f_rng, p_rng));
2676 }
2677
2678 MBEDTLS_MPI_CHK(ecp_normalize_mxz(grp, R));
2679
2680cleanup:
2681#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2682 ecp_drbg_free(&drbg_ctx);
2683#endif
2684
2685 mbedtls_ecp_point_free(&RP); mbedtls_mpi_free(&PX);
2686
2687 return ret;
2688}
2689
2690#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
2691
2692/*
2693 * Restartable multiplication R = m * P
2694 */
2695int mbedtls_ecp_mul_restartable(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2696 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2697 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,
2698 mbedtls_ecp_restart_ctx *rs_ctx)
2699{
2700 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
2701#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2702 char is_grp_capable = 0;
2703#endif
2704 ECP_VALIDATE_RET(grp != NULL);
2705 ECP_VALIDATE_RET(R != NULL);
2706 ECP_VALIDATE_RET(m != NULL);
2707 ECP_VALIDATE_RET(P != NULL);
2708
2709#if defined(MBEDTLS_ECP_RESTARTABLE)
2710 /* reset ops count for this call if top-level */
2711 if (rs_ctx != NULL && rs_ctx->depth++ == 0) {
2712 rs_ctx->ops_done = 0;
2713 }
2714#else
2715 (void) rs_ctx;
2716#endif
2717
2718#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2719 if ((is_grp_capable = mbedtls_internal_ecp_grp_capable(grp))) {
2720 MBEDTLS_MPI_CHK(mbedtls_internal_ecp_init(grp));
2721 }
2722#endif /* MBEDTLS_ECP_INTERNAL_ALT */
2723
2724 int restarting = 0;
2725#if defined(MBEDTLS_ECP_RESTARTABLE)
2726 restarting = (rs_ctx != NULL && rs_ctx->rsm != NULL);
2727#endif
2728 /* skip argument check when restarting */
2729 if (!restarting) {
2730 /* check_privkey is free */
2731 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_CHK);
2732
2733 /* Common sanity checks */
2734 MBEDTLS_MPI_CHK(mbedtls_ecp_check_privkey(grp, m));
2735 MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
2736 }
2737
2738 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
2739#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
2740 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
2741 MBEDTLS_MPI_CHK(ecp_mul_mxz(grp, R, m, P, f_rng, p_rng));
2742 }
2743#endif
2744#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
2745 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
2746 MBEDTLS_MPI_CHK(ecp_mul_comb(grp, R, m, P, f_rng, p_rng, rs_ctx));
2747 }
2748#endif
2749
2750cleanup:
2751
2752#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2753 if (is_grp_capable) {
2754 mbedtls_internal_ecp_free(grp);
2755 }
2756#endif /* MBEDTLS_ECP_INTERNAL_ALT */
2757
2758#if defined(MBEDTLS_ECP_RESTARTABLE)
2759 if (rs_ctx != NULL) {
2760 rs_ctx->depth--;
2761 }
2762#endif
2763
2764 return ret;
2765}
2766
2767/*
2768 * Multiplication R = m * P
2769 */
2770int mbedtls_ecp_mul(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2771 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2772 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
2773{
2774 ECP_VALIDATE_RET(grp != NULL);
2775 ECP_VALIDATE_RET(R != NULL);
2776 ECP_VALIDATE_RET(m != NULL);
2777 ECP_VALIDATE_RET(P != NULL);
2778 return mbedtls_ecp_mul_restartable(grp, R, m, P, f_rng, p_rng, NULL);
2779}
2780
2781#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
2782/*
2783 * Check that an affine point is valid as a public key,
2784 * short weierstrass curves (SEC1 3.2.3.1)
2785 */
2786static int ecp_check_pubkey_sw(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt)
2787{
2788 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2789 mbedtls_mpi YY, RHS;
2790
2791 /* pt coordinates must be normalized for our checks */
2792 if (mbedtls_mpi_cmp_int(&pt->X, 0) < 0 ||
2793 mbedtls_mpi_cmp_int(&pt->Y, 0) < 0 ||
2794 mbedtls_mpi_cmp_mpi(&pt->X, &grp->P) >= 0 ||
2795 mbedtls_mpi_cmp_mpi(&pt->Y, &grp->P) >= 0) {
2796 return MBEDTLS_ERR_ECP_INVALID_KEY;
2797 }
2798
2799 mbedtls_mpi_init(&YY); mbedtls_mpi_init(&RHS);
2800
2801 /*
2802 * YY = Y^2
2803 * RHS = X (X^2 + A) + B = X^3 + A X + B
2804 */
2805 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &YY, &pt->Y, &pt->Y));
2806 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &RHS, &pt->X, &pt->X));
2807
2808 /* Special case for A = -3 */
2809 if (grp->A.p == NULL) {
2810 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&RHS, &RHS, 3)); MOD_SUB(RHS);
2811 } else {
2812 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &RHS, &RHS, &grp->A));
2813 }
2814
2815 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &RHS, &RHS, &pt->X));
2816 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &RHS, &RHS, &grp->B));
2817
2818 if (mbedtls_mpi_cmp_mpi(&YY, &RHS) != 0) {
2819 ret = MBEDTLS_ERR_ECP_INVALID_KEY;
2820 }
2821
2822cleanup:
2823
2824 mbedtls_mpi_free(&YY); mbedtls_mpi_free(&RHS);
2825
2826 return ret;
2827}
2828#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
2829
2830#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
2831/*
2832 * R = m * P with shortcuts for m == 0, m == 1 and m == -1
2833 * NOT constant-time - ONLY for short Weierstrass!
2834 */
2835static int mbedtls_ecp_mul_shortcuts(mbedtls_ecp_group *grp,
2836 mbedtls_ecp_point *R,
2837 const mbedtls_mpi *m,
2838 const mbedtls_ecp_point *P,
2839 mbedtls_ecp_restart_ctx *rs_ctx)
2840{
2841 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2842
2843 if (mbedtls_mpi_cmp_int(m, 0) == 0) {
2844 MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
2845 MBEDTLS_MPI_CHK(mbedtls_ecp_set_zero(R));
2846 } else if (mbedtls_mpi_cmp_int(m, 1) == 0) {
2847 MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
2848 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, P));
2849 } else if (mbedtls_mpi_cmp_int(m, -1) == 0) {
2850 MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
2851 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, P));
2852 if (mbedtls_mpi_cmp_int(&R->Y, 0) != 0) {
2853 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&R->Y, &grp->P, &R->Y));
2854 }
2855 } else {
2856 MBEDTLS_MPI_CHK(mbedtls_ecp_mul_restartable(grp, R, m, P,
2857 NULL, NULL, rs_ctx));
2858 }
2859
2860cleanup:
2861 return ret;
2862}
2863
2864/*
2865 * Restartable linear combination
2866 * NOT constant-time
2867 */
2868int mbedtls_ecp_muladd_restartable(
2869 mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2870 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2871 const mbedtls_mpi *n, const mbedtls_ecp_point *Q,
2872 mbedtls_ecp_restart_ctx *rs_ctx)
2873{
2874 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2875 mbedtls_ecp_point mP;
2876 mbedtls_ecp_point *pmP = &mP;
2877 mbedtls_ecp_point *pR = R;
2878#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2879 char is_grp_capable = 0;
2880#endif
2881 ECP_VALIDATE_RET(grp != NULL);
2882 ECP_VALIDATE_RET(R != NULL);
2883 ECP_VALIDATE_RET(m != NULL);
2884 ECP_VALIDATE_RET(P != NULL);
2885 ECP_VALIDATE_RET(n != NULL);
2886 ECP_VALIDATE_RET(Q != NULL);
2887
2888 if (mbedtls_ecp_get_type(grp) != MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
2889 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
2890 }
2891
2892 mbedtls_ecp_point_init(&mP);
2893
2894 ECP_RS_ENTER(ma);
2895
2896#if defined(MBEDTLS_ECP_RESTARTABLE)
2897 if (rs_ctx != NULL && rs_ctx->ma != NULL) {
2898 /* redirect intermediate results to restart context */
2899 pmP = &rs_ctx->ma->mP;
2900 pR = &rs_ctx->ma->R;
2901
2902 /* jump to next operation */
2903 if (rs_ctx->ma->state == ecp_rsma_mul2) {
2904 goto mul2;
2905 }
2906 if (rs_ctx->ma->state == ecp_rsma_add) {
2907 goto add;
2908 }
2909 if (rs_ctx->ma->state == ecp_rsma_norm) {
2910 goto norm;
2911 }
2912 }
2913#endif /* MBEDTLS_ECP_RESTARTABLE */
2914
2915 MBEDTLS_MPI_CHK(mbedtls_ecp_mul_shortcuts(grp, pmP, m, P, rs_ctx));
2916#if defined(MBEDTLS_ECP_RESTARTABLE)
2917 if (rs_ctx != NULL && rs_ctx->ma != NULL) {
2918 rs_ctx->ma->state = ecp_rsma_mul2;
2919 }
2920
2921mul2:
2922#endif
2923 MBEDTLS_MPI_CHK(mbedtls_ecp_mul_shortcuts(grp, pR, n, Q, rs_ctx));
2924
2925#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2926 if ((is_grp_capable = mbedtls_internal_ecp_grp_capable(grp))) {
2927 MBEDTLS_MPI_CHK(mbedtls_internal_ecp_init(grp));
2928 }
2929#endif /* MBEDTLS_ECP_INTERNAL_ALT */
2930
2931#if defined(MBEDTLS_ECP_RESTARTABLE)
2932 if (rs_ctx != NULL && rs_ctx->ma != NULL) {
2933 rs_ctx->ma->state = ecp_rsma_add;
2934 }
2935
2936add:
2937#endif
2938 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_ADD);
2939 MBEDTLS_MPI_CHK(ecp_add_mixed(grp, pR, pmP, pR));
2940#if defined(MBEDTLS_ECP_RESTARTABLE)
2941 if (rs_ctx != NULL && rs_ctx->ma != NULL) {
2942 rs_ctx->ma->state = ecp_rsma_norm;
2943 }
2944
2945norm:
2946#endif
2947 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV);
2948 MBEDTLS_MPI_CHK(ecp_normalize_jac(grp, pR));
2949
2950#if defined(MBEDTLS_ECP_RESTARTABLE)
2951 if (rs_ctx != NULL && rs_ctx->ma != NULL) {
2952 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, pR));
2953 }
2954#endif
2955
2956cleanup:
2957#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2958 if (is_grp_capable) {
2959 mbedtls_internal_ecp_free(grp);
2960 }
2961#endif /* MBEDTLS_ECP_INTERNAL_ALT */
2962
2963 mbedtls_ecp_point_free(&mP);
2964
2965 ECP_RS_LEAVE(ma);
2966
2967 return ret;
2968}
2969
2970/*
2971 * Linear combination
2972 * NOT constant-time
2973 */
2974int mbedtls_ecp_muladd(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2975 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2976 const mbedtls_mpi *n, const mbedtls_ecp_point *Q)
2977{
2978 ECP_VALIDATE_RET(grp != NULL);
2979 ECP_VALIDATE_RET(R != NULL);
2980 ECP_VALIDATE_RET(m != NULL);
2981 ECP_VALIDATE_RET(P != NULL);
2982 ECP_VALIDATE_RET(n != NULL);
2983 ECP_VALIDATE_RET(Q != NULL);
2984 return mbedtls_ecp_muladd_restartable(grp, R, m, P, n, Q, NULL);
2985}
2986#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
2987
2988#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
2989#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
2990#define ECP_MPI_INIT(s, n, p) { s, (n), (mbedtls_mpi_uint *) (p) }
2991#define ECP_MPI_INIT_ARRAY(x) \
2992 ECP_MPI_INIT(1, sizeof(x) / sizeof(mbedtls_mpi_uint), x)
2993/*
2994 * Constants for the two points other than 0, 1, -1 (mod p) in
2995 * https://cr.yp.to/ecdh.html#validate
2996 * See ecp_check_pubkey_x25519().
2997 */
2998static const mbedtls_mpi_uint x25519_bad_point_1[] = {
2999 MBEDTLS_BYTES_TO_T_UINT_8(0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae),
3000 MBEDTLS_BYTES_TO_T_UINT_8(0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a),
3001 MBEDTLS_BYTES_TO_T_UINT_8(0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd),
3002 MBEDTLS_BYTES_TO_T_UINT_8(0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00),
3003};
3004static const mbedtls_mpi_uint x25519_bad_point_2[] = {
3005 MBEDTLS_BYTES_TO_T_UINT_8(0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24),
3006 MBEDTLS_BYTES_TO_T_UINT_8(0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b),
3007 MBEDTLS_BYTES_TO_T_UINT_8(0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86),
3008 MBEDTLS_BYTES_TO_T_UINT_8(0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57),
3009};
3010static const mbedtls_mpi ecp_x25519_bad_point_1 = ECP_MPI_INIT_ARRAY(
3011 x25519_bad_point_1);
3012static const mbedtls_mpi ecp_x25519_bad_point_2 = ECP_MPI_INIT_ARRAY(
3013 x25519_bad_point_2);
3014#endif /* MBEDTLS_ECP_DP_CURVE25519_ENABLED */
3015
3016/*
3017 * Check that the input point is not one of the low-order points.
3018 * This is recommended by the "May the Fourth" paper:
3019 * https://eprint.iacr.org/2017/806.pdf
3020 * Those points are never sent by an honest peer.
3021 */
3022static int ecp_check_bad_points_mx(const mbedtls_mpi *X, const mbedtls_mpi *P,
3023 const mbedtls_ecp_group_id grp_id)
3024{
3025 int ret;
3026 mbedtls_mpi XmP;
3027
3028 mbedtls_mpi_init(&XmP);
3029
3030 /* Reduce X mod P so that we only need to check values less than P.
3031 * We know X < 2^256 so we can proceed by subtraction. */
3032 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&XmP, X));
3033 while (mbedtls_mpi_cmp_mpi(&XmP, P) >= 0) {
3034 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&XmP, &XmP, P));
3035 }
3036
3037 /* Check against the known bad values that are less than P. For Curve448
3038 * these are 0, 1 and -1. For Curve25519 we check the values less than P
3039 * from the following list: https://cr.yp.to/ecdh.html#validate */
3040 if (mbedtls_mpi_cmp_int(&XmP, 1) <= 0) { /* takes care of 0 and 1 */
3041 ret = MBEDTLS_ERR_ECP_INVALID_KEY;
3042 goto cleanup;
3043 }
3044
3045#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
3046 if (grp_id == MBEDTLS_ECP_DP_CURVE25519) {
3047 if (mbedtls_mpi_cmp_mpi(&XmP, &ecp_x25519_bad_point_1) == 0) {
3048 ret = MBEDTLS_ERR_ECP_INVALID_KEY;
3049 goto cleanup;
3050 }
3051
3052 if (mbedtls_mpi_cmp_mpi(&XmP, &ecp_x25519_bad_point_2) == 0) {
3053 ret = MBEDTLS_ERR_ECP_INVALID_KEY;
3054 goto cleanup;
3055 }
3056 }
3057#else
3058 (void) grp_id;
3059#endif
3060
3061 /* Final check: check if XmP + 1 is P (final because it changes XmP!) */
3062 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&XmP, &XmP, 1));
3063 if (mbedtls_mpi_cmp_mpi(&XmP, P) == 0) {
3064 ret = MBEDTLS_ERR_ECP_INVALID_KEY;
3065 goto cleanup;
3066 }
3067
3068 ret = 0;
3069
3070cleanup:
3071 mbedtls_mpi_free(&XmP);
3072
3073 return ret;
3074}
3075
3076/*
3077 * Check validity of a public key for Montgomery curves with x-only schemes
3078 */
3079static int ecp_check_pubkey_mx(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt)
3080{
3081 /* [Curve25519 p. 5] Just check X is the correct number of bytes */
3082 /* Allow any public value, if it's too big then we'll just reduce it mod p
3083 * (RFC 7748 sec. 5 para. 3). */
3084 if (mbedtls_mpi_size(&pt->X) > (grp->nbits + 7) / 8) {
3085 return MBEDTLS_ERR_ECP_INVALID_KEY;
3086 }
3087
3088 /* Implicit in all standards (as they don't consider negative numbers):
3089 * X must be non-negative. This is normally ensured by the way it's
3090 * encoded for transmission, but let's be extra sure. */
3091 if (mbedtls_mpi_cmp_int(&pt->X, 0) < 0) {
3092 return MBEDTLS_ERR_ECP_INVALID_KEY;
3093 }
3094
3095 return ecp_check_bad_points_mx(&pt->X, &grp->P, grp->id);
3096}
3097#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3098
3099/*
3100 * Check that a point is valid as a public key
3101 */
3102int mbedtls_ecp_check_pubkey(const mbedtls_ecp_group *grp,
3103 const mbedtls_ecp_point *pt)
3104{
3105 ECP_VALIDATE_RET(grp != NULL);
3106 ECP_VALIDATE_RET(pt != NULL);
3107
3108 /* Must use affine coordinates */
3109 if (mbedtls_mpi_cmp_int(&pt->Z, 1) != 0) {
3110 return MBEDTLS_ERR_ECP_INVALID_KEY;
3111 }
3112
3113#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3114 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
3115 return ecp_check_pubkey_mx(grp, pt);
3116 }
3117#endif
3118#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3119 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
3120 return ecp_check_pubkey_sw(grp, pt);
3121 }
3122#endif
3123 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3124}
3125
3126/*
3127 * Check that an mbedtls_mpi is valid as a private key
3128 */
3129int mbedtls_ecp_check_privkey(const mbedtls_ecp_group *grp,
3130 const mbedtls_mpi *d)
3131{
3132 ECP_VALIDATE_RET(grp != NULL);
3133 ECP_VALIDATE_RET(d != NULL);
3134
3135#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3136 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
3137 /* see RFC 7748 sec. 5 para. 5 */
3138 if (mbedtls_mpi_get_bit(d, 0) != 0 ||
3139 mbedtls_mpi_get_bit(d, 1) != 0 ||
3140 mbedtls_mpi_bitlen(d) - 1 != grp->nbits) { /* mbedtls_mpi_bitlen is one-based! */
3141 return MBEDTLS_ERR_ECP_INVALID_KEY;
3142 }
3143
3144 /* see [Curve25519] page 5 */
3145 if (grp->nbits == 254 && mbedtls_mpi_get_bit(d, 2) != 0) {
3146 return MBEDTLS_ERR_ECP_INVALID_KEY;
3147 }
3148
3149 return 0;
3150 }
3151#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3152#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3153 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
3154 /* see SEC1 3.2 */
3155 if (mbedtls_mpi_cmp_int(d, 1) < 0 ||
3156 mbedtls_mpi_cmp_mpi(d, &grp->N) >= 0) {
3157 return MBEDTLS_ERR_ECP_INVALID_KEY;
3158 } else {
3159 return 0;
3160 }
3161 }
3162#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
3163
3164 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3165}
3166
3167#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3168MBEDTLS_STATIC_TESTABLE
3169int mbedtls_ecp_gen_privkey_mx(size_t high_bit,
3170 mbedtls_mpi *d,
3171 int (*f_rng)(void *, unsigned char *, size_t),
3172 void *p_rng)
3173{
3174 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3175 size_t n_random_bytes = high_bit / 8 + 1;
3176
3177 /* [Curve25519] page 5 */
3178 /* Generate a (high_bit+1)-bit random number by generating just enough
3179 * random bytes, then shifting out extra bits from the top (necessary
3180 * when (high_bit+1) is not a multiple of 8). */
3181 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(d, n_random_bytes,
3182 f_rng, p_rng));
3183 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(d, 8 * n_random_bytes - high_bit - 1));
3184
3185 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, high_bit, 1));
3186
3187 /* Make sure the last two bits are unset for Curve448, three bits for
3188 Curve25519 */
3189 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 0, 0));
3190 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 1, 0));
3191 if (high_bit == 254) {
3192 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 2, 0));
3193 }
3194
3195cleanup:
3196 return ret;
3197}
3198#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3199
3200#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3201static int mbedtls_ecp_gen_privkey_sw(
3202 const mbedtls_mpi *N, mbedtls_mpi *d,
3203 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
3204{
3205 int ret = mbedtls_mpi_random(d, 1, N, f_rng, p_rng);
3206 switch (ret) {
3207 case MBEDTLS_ERR_MPI_NOT_ACCEPTABLE:
3208 return MBEDTLS_ERR_ECP_RANDOM_FAILED;
3209 default:
3210 return ret;
3211 }
3212}
3213#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
3214
3215/*
3216 * Generate a private key
3217 */
3218int mbedtls_ecp_gen_privkey(const mbedtls_ecp_group *grp,
3219 mbedtls_mpi *d,
3220 int (*f_rng)(void *, unsigned char *, size_t),
3221 void *p_rng)
3222{
3223 ECP_VALIDATE_RET(grp != NULL);
3224 ECP_VALIDATE_RET(d != NULL);
3225 ECP_VALIDATE_RET(f_rng != NULL);
3226
3227#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3228 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
3229 return mbedtls_ecp_gen_privkey_mx(grp->nbits, d, f_rng, p_rng);
3230 }
3231#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3232
3233#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3234 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
3235 return mbedtls_ecp_gen_privkey_sw(&grp->N, d, f_rng, p_rng);
3236 }
3237#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
3238
3239 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3240}
3241
3242/*
3243 * Generate a keypair with configurable base point
3244 */
3245int mbedtls_ecp_gen_keypair_base(mbedtls_ecp_group *grp,
3246 const mbedtls_ecp_point *G,
3247 mbedtls_mpi *d, mbedtls_ecp_point *Q,
3248 int (*f_rng)(void *, unsigned char *, size_t),
3249 void *p_rng)
3250{
3251 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3252 ECP_VALIDATE_RET(grp != NULL);
3253 ECP_VALIDATE_RET(d != NULL);
3254 ECP_VALIDATE_RET(G != NULL);
3255 ECP_VALIDATE_RET(Q != NULL);
3256 ECP_VALIDATE_RET(f_rng != NULL);
3257
3258 MBEDTLS_MPI_CHK(mbedtls_ecp_gen_privkey(grp, d, f_rng, p_rng));
3259 MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, Q, d, G, f_rng, p_rng));
3260
3261cleanup:
3262 return ret;
3263}
3264
3265/*
3266 * Generate key pair, wrapper for conventional base point
3267 */
3268int mbedtls_ecp_gen_keypair(mbedtls_ecp_group *grp,
3269 mbedtls_mpi *d, mbedtls_ecp_point *Q,
3270 int (*f_rng)(void *, unsigned char *, size_t),
3271 void *p_rng)
3272{
3273 ECP_VALIDATE_RET(grp != NULL);
3274 ECP_VALIDATE_RET(d != NULL);
3275 ECP_VALIDATE_RET(Q != NULL);
3276 ECP_VALIDATE_RET(f_rng != NULL);
3277
3278 return mbedtls_ecp_gen_keypair_base(grp, &grp->G, d, Q, f_rng, p_rng);
3279}
3280
3281/*
3282 * Generate a keypair, prettier wrapper
3283 */
3284int mbedtls_ecp_gen_key(mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
3285 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
3286{
3287 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3288 ECP_VALIDATE_RET(key != NULL);
3289 ECP_VALIDATE_RET(f_rng != NULL);
3290
3291 if ((ret = mbedtls_ecp_group_load(&key->grp, grp_id)) != 0) {
3292 return ret;
3293 }
3294
3295 return mbedtls_ecp_gen_keypair(&key->grp, &key->d, &key->Q, f_rng, p_rng);
3296}
3297
3298#define ECP_CURVE25519_KEY_SIZE 32
3299/*
3300 * Read a private key.
3301 */
3302int mbedtls_ecp_read_key(mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
3303 const unsigned char *buf, size_t buflen)
3304{
3305 int ret = 0;
3306
3307 ECP_VALIDATE_RET(key != NULL);
3308 ECP_VALIDATE_RET(buf != NULL);
3309
3310 if ((ret = mbedtls_ecp_group_load(&key->grp, grp_id)) != 0) {
3311 return ret;
3312 }
3313
3314 ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
3315
3316#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3317 if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
3318 /*
3319 * If it is Curve25519 curve then mask the key as mandated by RFC7748
3320 */
3321 if (grp_id == MBEDTLS_ECP_DP_CURVE25519) {
3322 if (buflen != ECP_CURVE25519_KEY_SIZE) {
3323 return MBEDTLS_ERR_ECP_INVALID_KEY;
3324 }
3325
3326 MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary_le(&key->d, buf, buflen));
3327
3328 /* Set the three least significant bits to 0 */
3329 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 0, 0));
3330 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 1, 0));
3331 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 2, 0));
3332
3333 /* Set the most significant bit to 0 */
3334 MBEDTLS_MPI_CHK(
3335 mbedtls_mpi_set_bit(&key->d,
3336 ECP_CURVE25519_KEY_SIZE * 8 - 1, 0)
3337 );
3338
3339 /* Set the second most significant bit to 1 */
3340 MBEDTLS_MPI_CHK(
3341 mbedtls_mpi_set_bit(&key->d,
3342 ECP_CURVE25519_KEY_SIZE * 8 - 2, 1)
3343 );
3344 } else {
3345 ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
3346 }
3347 }
3348
3349#endif
3350#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3351 if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
3352 MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(&key->d, buf, buflen));
3353
3354 MBEDTLS_MPI_CHK(mbedtls_ecp_check_privkey(&key->grp, &key->d));
3355 }
3356
3357#endif
3358cleanup:
3359
3360 if (ret != 0) {
3361 mbedtls_mpi_free(&key->d);
3362 }
3363
3364 return ret;
3365}
3366
3367/*
3368 * Write a private key.
3369 */
3370int mbedtls_ecp_write_key(mbedtls_ecp_keypair *key,
3371 unsigned char *buf, size_t buflen)
3372{
3373 int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
3374
3375 ECP_VALIDATE_RET(key != NULL);
3376 ECP_VALIDATE_RET(buf != NULL);
3377
3378#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3379 if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
3380 if (key->grp.id == MBEDTLS_ECP_DP_CURVE25519) {
3381 if (buflen < ECP_CURVE25519_KEY_SIZE) {
3382 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
3383 }
3384
3385 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary_le(&key->d, buf, buflen));
3386 } else {
3387 ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
3388 }
3389 }
3390
3391#endif
3392#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3393 if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
3394 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&key->d, buf, buflen));
3395 }
3396
3397#endif
3398cleanup:
3399
3400 return ret;
3401}
3402
3403
3404/*
3405 * Check a public-private key pair
3406 */
3407int mbedtls_ecp_check_pub_priv(const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv)
3408{
3409 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3410 mbedtls_ecp_point Q;
3411 mbedtls_ecp_group grp;
3412 ECP_VALIDATE_RET(pub != NULL);
3413 ECP_VALIDATE_RET(prv != NULL);
3414
3415 if (pub->grp.id == MBEDTLS_ECP_DP_NONE ||
3416 pub->grp.id != prv->grp.id ||
3417 mbedtls_mpi_cmp_mpi(&pub->Q.X, &prv->Q.X) ||
3418 mbedtls_mpi_cmp_mpi(&pub->Q.Y, &prv->Q.Y) ||
3419 mbedtls_mpi_cmp_mpi(&pub->Q.Z, &prv->Q.Z)) {
3420 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3421 }
3422
3423 mbedtls_ecp_point_init(&Q);
3424 mbedtls_ecp_group_init(&grp);
3425
3426 /* mbedtls_ecp_mul() needs a non-const group... */
3427 mbedtls_ecp_group_copy(&grp, &prv->grp);
3428
3429 /* Also checks d is valid */
3430 MBEDTLS_MPI_CHK(mbedtls_ecp_mul(&grp, &Q, &prv->d, &prv->grp.G, NULL, NULL));
3431
3432 if (mbedtls_mpi_cmp_mpi(&Q.X, &prv->Q.X) ||
3433 mbedtls_mpi_cmp_mpi(&Q.Y, &prv->Q.Y) ||
3434 mbedtls_mpi_cmp_mpi(&Q.Z, &prv->Q.Z)) {
3435 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3436 goto cleanup;
3437 }
3438
3439cleanup:
3440 mbedtls_ecp_point_free(&Q);
3441 mbedtls_ecp_group_free(&grp);
3442
3443 return ret;
3444}
3445
3446#if defined(MBEDTLS_SELF_TEST)
3447
3448/* Adjust the exponent to be a valid private point for the specified curve.
3449 * This is sometimes necessary because we use a single set of exponents
3450 * for all curves but the validity of values depends on the curve. */
3451static int self_test_adjust_exponent(const mbedtls_ecp_group *grp,
3452 mbedtls_mpi *m)
3453{
3454 int ret = 0;
3455 switch (grp->id) {
3456 /* If Curve25519 is available, then that's what we use for the
3457 * Montgomery test, so we don't need the adjustment code. */
3458#if !defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
3459#if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
3460 case MBEDTLS_ECP_DP_CURVE448:
3461 /* Move highest bit from 254 to N-1. Setting bit N-1 is
3462 * necessary to enforce the highest-bit-set constraint. */
3463 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(m, 254, 0));
3464 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(m, grp->nbits, 1));
3465 /* Copy second-highest bit from 253 to N-2. This is not
3466 * necessary but improves the test variety a bit. */
3467 MBEDTLS_MPI_CHK(
3468 mbedtls_mpi_set_bit(m, grp->nbits - 1,
3469 mbedtls_mpi_get_bit(m, 253)));
3470 break;
3471#endif
3472#endif /* ! defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) */
3473 default:
3474 /* Non-Montgomery curves and Curve25519 need no adjustment. */
3475 (void) grp;
3476 (void) m;
3477 goto cleanup;
3478 }
3479cleanup:
3480 return ret;
3481}
3482
3483/* Calculate R = m.P for each m in exponents. Check that the number of
3484 * basic operations doesn't depend on the value of m. */
3485static int self_test_point(int verbose,
3486 mbedtls_ecp_group *grp,
3487 mbedtls_ecp_point *R,
3488 mbedtls_mpi *m,
3489 const mbedtls_ecp_point *P,
3490 const char *const *exponents,
3491 size_t n_exponents)
3492{
3493 int ret = 0;
3494 size_t i = 0;
3495 unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
3496 add_count = 0;
3497 dbl_count = 0;
3498 mul_count = 0;
3499
3500 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(m, 16, exponents[0]));
3501 MBEDTLS_MPI_CHK(self_test_adjust_exponent(grp, m));
3502 MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, R, m, P, NULL, NULL));
3503
3504 for (i = 1; i < n_exponents; i++) {
3505 add_c_prev = add_count;
3506 dbl_c_prev = dbl_count;
3507 mul_c_prev = mul_count;
3508 add_count = 0;
3509 dbl_count = 0;
3510 mul_count = 0;
3511
3512 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(m, 16, exponents[i]));
3513 MBEDTLS_MPI_CHK(self_test_adjust_exponent(grp, m));
3514 MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, R, m, P, NULL, NULL));
3515
3516 if (add_count != add_c_prev ||
3517 dbl_count != dbl_c_prev ||
3518 mul_count != mul_c_prev) {
3519 ret = 1;
3520 break;
3521 }
3522 }
3523
3524cleanup:
3525 if (verbose != 0) {
3526 if (ret != 0) {
3527 mbedtls_printf("failed (%u)\n", (unsigned int) i);
3528 } else {
3529 mbedtls_printf("passed\n");
3530 }
3531 }
3532 return ret;
3533}
3534
3535/*
3536 * Checkup routine
3537 */
3538int mbedtls_ecp_self_test(int verbose)
3539{
3540 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3541 mbedtls_ecp_group grp;
3542 mbedtls_ecp_point R, P;
3543 mbedtls_mpi m;
3544
3545#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3546 /* Exponents especially adapted for secp192k1, which has the lowest
3547 * order n of all supported curves (secp192r1 is in a slightly larger
3548 * field but the order of its base point is slightly smaller). */
3549 const char *sw_exponents[] =
3550 {
3551 "000000000000000000000000000000000000000000000001", /* one */
3552 "FFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8C", /* n - 1 */
3553 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
3554 "400000000000000000000000000000000000000000000000", /* one and zeros */
3555 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
3556 "555555555555555555555555555555555555555555555555", /* 101010... */
3557 };
3558#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
3559#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3560 const char *m_exponents[] =
3561 {
3562 /* Valid private values for Curve25519. In a build with Curve448
3563 * but not Curve25519, they will be adjusted in
3564 * self_test_adjust_exponent(). */
3565 "4000000000000000000000000000000000000000000000000000000000000000",
3566 "5C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C30",
3567 "5715ECCE24583F7A7023C24164390586842E816D7280A49EF6DF4EAE6B280BF8",
3568 "41A2B017516F6D254E1F002BCCBADD54BE30F8CEC737A0E912B4963B6BA74460",
3569 "5555555555555555555555555555555555555555555555555555555555555550",
3570 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8",
3571 };
3572#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3573
3574 mbedtls_ecp_group_init(&grp);
3575 mbedtls_ecp_point_init(&R);
3576 mbedtls_ecp_point_init(&P);
3577 mbedtls_mpi_init(&m);
3578
3579#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3580 /* Use secp192r1 if available, or any available curve */
3581#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
3582 MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_SECP192R1));
3583#else
3584 MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, mbedtls_ecp_curve_list()->grp_id));
3585#endif
3586
3587 if (verbose != 0) {
3588 mbedtls_printf(" ECP SW test #1 (constant op_count, base point G): ");
3589 }
3590 /* Do a dummy multiplication first to trigger precomputation */
3591 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&m, 2));
3592 MBEDTLS_MPI_CHK(mbedtls_ecp_mul(&grp, &P, &m, &grp.G, NULL, NULL));
3593 ret = self_test_point(verbose,
3594 &grp, &R, &m, &grp.G,
3595 sw_exponents,
3596 sizeof(sw_exponents) / sizeof(sw_exponents[0]));
3597 if (ret != 0) {
3598 goto cleanup;
3599 }
3600
3601 if (verbose != 0) {
3602 mbedtls_printf(" ECP SW test #2 (constant op_count, other point): ");
3603 }
3604 /* We computed P = 2G last time, use it */
3605 ret = self_test_point(verbose,
3606 &grp, &R, &m, &P,
3607 sw_exponents,
3608 sizeof(sw_exponents) / sizeof(sw_exponents[0]));
3609 if (ret != 0) {
3610 goto cleanup;
3611 }
3612
3613 mbedtls_ecp_group_free(&grp);
3614 mbedtls_ecp_point_free(&R);
3615#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
3616
3617#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3618 if (verbose != 0) {
3619 mbedtls_printf(" ECP Montgomery test (constant op_count): ");
3620 }
3621#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
3622 MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_CURVE25519));
3623#elif defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
3624 MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_CURVE448));
3625#else
3626#error "MBEDTLS_ECP_MONTGOMERY_ENABLED is defined, but no curve is supported for self-test"
3627#endif
3628 ret = self_test_point(verbose,
3629 &grp, &R, &m, &grp.G,
3630 m_exponents,
3631 sizeof(m_exponents) / sizeof(m_exponents[0]));
3632 if (ret != 0) {
3633 goto cleanup;
3634 }
3635#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3636
3637cleanup:
3638
3639 if (ret < 0 && verbose != 0) {
3640 mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret);
3641 }
3642
3643 mbedtls_ecp_group_free(&grp);
3644 mbedtls_ecp_point_free(&R);
3645 mbedtls_ecp_point_free(&P);
3646 mbedtls_mpi_free(&m);
3647
3648 if (verbose != 0) {
3649 mbedtls_printf("\n");
3650 }
3651
3652 return ret;
3653}
3654
3655#endif /* MBEDTLS_SELF_TEST */
3656
3657#endif /* !MBEDTLS_ECP_ALT */
3658
3659#endif /* MBEDTLS_ECP_C */
3660