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