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