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