Branch data Line data Source code
1 : : /*
2 : : * Elliptic curves over GF(p): generic functions
3 : : *
4 : : * Copyright The Mbed TLS Contributors
5 : : * SPDX-License-Identifier: Apache-2.0
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 : : */
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 : : */
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 : : */
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 : : */
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 : : */
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 : : */
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 : : */
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 : : */
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 : : */
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 : : */
409 : 0 : const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void )
410 : : {
411 : 0 : return( ecp_supported_curves );
412 : : }
413 : :
414 : : /*
415 : : * List of supported curves, group ID only
416 : : */
417 : 0 : const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void )
418 : : {
419 : 0 : static int init_done = 0;
420 : :
421 [ # # ]: 0 : if( ! init_done )
422 : : {
423 : 0 : size_t i = 0;
424 : 0 : const mbedtls_ecp_curve_info *curve_info;
425 : :
426 : 0 : for( curve_info = mbedtls_ecp_curve_list();
427 [ # # ]: 0 : curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
428 : 0 : curve_info++ )
429 : : {
430 : 0 : ecp_supported_grp_id[i++] = curve_info->grp_id;
431 : : }
432 : 0 : ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
433 : :
434 : 0 : init_done = 1;
435 : : }
436 : :
437 : 0 : return( ecp_supported_grp_id );
438 : : }
439 : :
440 : : /*
441 : : * Get the curve info for the internal identifier
442 : : */
443 : 0 : const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id )
444 : : {
445 : 0 : const mbedtls_ecp_curve_info *curve_info;
446 : :
447 : 0 : for( curve_info = mbedtls_ecp_curve_list();
448 [ # # ]: 0 : curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
449 : 0 : curve_info++ )
450 : : {
451 [ # # ]: 0 : if( curve_info->grp_id == grp_id )
452 : 0 : return( curve_info );
453 : : }
454 : :
455 : : return( NULL );
456 : : }
457 : :
458 : : /*
459 : : * Get the curve info from the TLS identifier
460 : : */
461 : 0 : const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id )
462 : : {
463 : 0 : const mbedtls_ecp_curve_info *curve_info;
464 : :
465 : 0 : for( curve_info = mbedtls_ecp_curve_list();
466 [ # # ]: 0 : curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
467 : 0 : curve_info++ )
468 : : {
469 [ # # ]: 0 : if( curve_info->tls_id == tls_id )
470 : 0 : return( curve_info );
471 : : }
472 : :
473 : : return( NULL );
474 : : }
475 : :
476 : : /*
477 : : * Get the curve info from the name
478 : : */
479 : 0 : const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name )
480 : : {
481 : 0 : const mbedtls_ecp_curve_info *curve_info;
482 : :
483 [ # # ]: 0 : if( name == NULL )
484 : : return( NULL );
485 : :
486 : 0 : for( curve_info = mbedtls_ecp_curve_list();
487 [ # # ]: 0 : curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
488 : 0 : curve_info++ )
489 : : {
490 [ # # ]: 0 : if( strcmp( curve_info->name, name ) == 0 )
491 : 0 : return( curve_info );
492 : : }
493 : :
494 : : return( NULL );
495 : : }
496 : :
497 : : /*
498 : : * Get the type of a curve
499 : : */
500 : 164 : mbedtls_ecp_curve_type mbedtls_ecp_get_type( const mbedtls_ecp_group *grp )
501 : : {
502 [ + - ]: 164 : if( grp->G.X.p == NULL )
503 : : return( MBEDTLS_ECP_TYPE_NONE );
504 : :
505 [ + - ]: 164 : if( grp->G.Y.p == NULL )
506 : : return( MBEDTLS_ECP_TYPE_MONTGOMERY );
507 : : else
508 : 164 : return( MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS );
509 : : }
510 : :
511 : : /*
512 : : * Initialize (the components of) a point
513 : : */
514 : 212 : void mbedtls_ecp_point_init( mbedtls_ecp_point *pt )
515 : : {
516 : 212 : ECP_VALIDATE( pt != NULL );
517 : :
518 : 212 : mbedtls_mpi_init( &pt->X );
519 : 212 : mbedtls_mpi_init( &pt->Y );
520 : 212 : mbedtls_mpi_init( &pt->Z );
521 : 212 : }
522 : :
523 : : /*
524 : : * Initialize (the components of) a group
525 : : */
526 : 44 : void mbedtls_ecp_group_init( mbedtls_ecp_group *grp )
527 : : {
528 : 44 : ECP_VALIDATE( grp != NULL );
529 : :
530 : 44 : grp->id = MBEDTLS_ECP_DP_NONE;
531 : 44 : mbedtls_mpi_init( &grp->P );
532 : 44 : mbedtls_mpi_init( &grp->A );
533 : 44 : mbedtls_mpi_init( &grp->B );
534 : 44 : mbedtls_ecp_point_init( &grp->G );
535 : 44 : mbedtls_mpi_init( &grp->N );
536 : 44 : grp->pbits = 0;
537 : 44 : grp->nbits = 0;
538 : 44 : grp->h = 0;
539 : 44 : grp->modp = NULL;
540 : 44 : grp->t_pre = NULL;
541 : 44 : grp->t_post = NULL;
542 : 44 : grp->t_data = NULL;
543 : 44 : grp->T = NULL;
544 : 44 : grp->T_size = 0;
545 : 44 : }
546 : :
547 : : /*
548 : : * Initialize (the components of) a key pair
549 : : */
550 : 40 : void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key )
551 : : {
552 : 40 : ECP_VALIDATE( key != NULL );
553 : :
554 : 40 : mbedtls_ecp_group_init( &key->grp );
555 : 40 : mbedtls_mpi_init( &key->d );
556 : 40 : mbedtls_ecp_point_init( &key->Q );
557 : 40 : }
558 : :
559 : : /*
560 : : * Unallocate (the components of) a point
561 : : */
562 : 212 : void mbedtls_ecp_point_free( mbedtls_ecp_point *pt )
563 : : {
564 [ + - ]: 212 : if( pt == NULL )
565 : : return;
566 : :
567 : 212 : mbedtls_mpi_free( &( pt->X ) );
568 : 212 : mbedtls_mpi_free( &( pt->Y ) );
569 : 212 : mbedtls_mpi_free( &( pt->Z ) );
570 : : }
571 : :
572 : : /*
573 : : * Check that the comb table (grp->T) is static initialized.
574 : : */
575 : 114 : static int ecp_group_is_static_comb_table( const mbedtls_ecp_group *grp ) {
576 : : #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
577 [ + + - + ]: 114 : 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 : : */
587 : 104 : void mbedtls_ecp_group_free( mbedtls_ecp_group *grp )
588 : : {
589 : 104 : size_t i;
590 : :
591 [ + - ]: 104 : if( grp == NULL )
592 : : return;
593 : :
594 [ + + ]: 104 : if( grp->h != 1 )
595 : : {
596 : 44 : mbedtls_mpi_free( &grp->P );
597 : 44 : mbedtls_mpi_free( &grp->A );
598 : 44 : mbedtls_mpi_free( &grp->B );
599 : 44 : mbedtls_ecp_point_free( &grp->G );
600 : 44 : mbedtls_mpi_free( &grp->N );
601 : : }
602 : :
603 [ + + - + ]: 104 : if( !ecp_group_is_static_comb_table(grp) && grp->T != NULL )
604 : : {
605 [ # # ]: 0 : for( i = 0; i < grp->T_size; i++ )
606 : 0 : mbedtls_ecp_point_free( &grp->T[i] );
607 : 0 : mbedtls_free( grp->T );
608 : : }
609 : :
610 : 104 : mbedtls_platform_zeroize( grp, sizeof( mbedtls_ecp_group ) );
611 : : }
612 : :
613 : : /*
614 : : * Unallocate (the components of) a key pair
615 : : */
616 : 40 : void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key )
617 : : {
618 [ + - ]: 40 : if( key == NULL )
619 : : return;
620 : :
621 : 40 : mbedtls_ecp_group_free( &key->grp );
622 : 40 : mbedtls_mpi_free( &key->d );
623 : 40 : mbedtls_ecp_point_free( &key->Q );
624 : : }
625 : :
626 : : /*
627 : : * Copy the contents of a point
628 : : */
629 : 48 : int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
630 : : {
631 : 48 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
632 : 48 : ECP_VALIDATE_RET( P != NULL );
633 : 48 : ECP_VALIDATE_RET( Q != NULL );
634 : :
635 [ - + ]: 48 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X, &Q->X ) );
636 [ - + ]: 48 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y, &Q->Y ) );
637 [ + - ]: 48 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z, &Q->Z ) );
638 : :
639 : 48 : cleanup:
640 : 48 : return( ret );
641 : : }
642 : :
643 : : /*
644 : : * Copy the contents of a group object
645 : : */
646 : 0 : int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src )
647 : : {
648 : 0 : ECP_VALIDATE_RET( dst != NULL );
649 : 0 : ECP_VALIDATE_RET( src != NULL );
650 : :
651 : 0 : return( mbedtls_ecp_group_load( dst, src->id ) );
652 : : }
653 : :
654 : : /*
655 : : * Set point to zero
656 : : */
657 : 0 : int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt )
658 : : {
659 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
660 : 0 : ECP_VALIDATE_RET( pt != NULL );
661 : :
662 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) );
663 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y , 1 ) );
664 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 0 ) );
665 : :
666 : 0 : cleanup:
667 : 0 : return( ret );
668 : : }
669 : :
670 : : /*
671 : : * Tell if a point is zero
672 : : */
673 : 22 : int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt )
674 : : {
675 : 22 : ECP_VALIDATE_RET( pt != NULL );
676 : :
677 : 22 : return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 );
678 : : }
679 : :
680 : : /*
681 : : * Compare two points lazily
682 : : */
683 : 0 : int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P,
684 : : const mbedtls_ecp_point *Q )
685 : : {
686 : 0 : ECP_VALIDATE_RET( P != NULL );
687 : 0 : ECP_VALIDATE_RET( Q != NULL );
688 : :
689 [ # # # # ]: 0 : if( mbedtls_mpi_cmp_mpi( &P->X, &Q->X ) == 0 &&
690 [ # # ]: 0 : mbedtls_mpi_cmp_mpi( &P->Y, &Q->Y ) == 0 &&
691 : 0 : mbedtls_mpi_cmp_mpi( &P->Z, &Q->Z ) == 0 )
692 : : {
693 : 0 : 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 : : */
702 : 0 : int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix,
703 : : const char *x, const char *y )
704 : : {
705 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
706 : 0 : ECP_VALIDATE_RET( P != NULL );
707 : 0 : ECP_VALIDATE_RET( x != NULL );
708 : 0 : ECP_VALIDATE_RET( y != NULL );
709 : :
710 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X, radix, x ) );
711 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y, radix, y ) );
712 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
713 : :
714 : 0 : cleanup:
715 : 0 : return( ret );
716 : : }
717 : :
718 : : /*
719 : : * Export a point into unsigned binary data (SEC1 2.3.3 and RFC7748)
720 : : */
721 : 6 : 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 : 6 : int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
727 : 6 : size_t plen;
728 : 6 : ECP_VALIDATE_RET( grp != NULL );
729 : 6 : ECP_VALIDATE_RET( P != NULL );
730 : 6 : ECP_VALIDATE_RET( olen != NULL );
731 : 6 : ECP_VALIDATE_RET( buf != NULL );
732 : 6 : ECP_VALIDATE_RET( format == MBEDTLS_ECP_PF_UNCOMPRESSED ||
733 : : format == MBEDTLS_ECP_PF_COMPRESSED );
734 : :
735 : 6 : 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 [ - + ]: 6 : if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
750 : : {
751 : : /*
752 : : * Common case: P == 0
753 : : */
754 [ - + ]: 6 : if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
755 : : {
756 [ # # ]: 0 : if( buflen < 1 )
757 : : return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
758 : :
759 : 0 : buf[0] = 0x00;
760 : 0 : *olen = 1;
761 : :
762 : 0 : return( 0 );
763 : : }
764 : :
765 [ + - ]: 6 : if( format == MBEDTLS_ECP_PF_UNCOMPRESSED )
766 : : {
767 : 6 : *olen = 2 * plen + 1;
768 : :
769 [ + - ]: 6 : if( buflen < *olen )
770 : : return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
771 : :
772 : 6 : buf[0] = 0x04;
773 [ - + ]: 6 : MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
774 [ - + ]: 6 : MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) );
775 : : }
776 [ # # ]: 0 : else if( format == MBEDTLS_ECP_PF_COMPRESSED )
777 : : {
778 : 0 : *olen = plen + 1;
779 : :
780 [ # # ]: 0 : if( buflen < *olen )
781 : : return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
782 : :
783 : 0 : buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 );
784 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
785 : : }
786 : : }
787 : : #endif
788 : :
789 : 0 : cleanup:
790 : : return( ret );
791 : : }
792 : :
793 : : /*
794 : : * Import a point from unsigned binary data (SEC1 2.3.4 and RFC7748)
795 : : */
796 : 20 : 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 : 20 : int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
801 : 20 : size_t plen;
802 : 20 : ECP_VALIDATE_RET( grp != NULL );
803 : 20 : ECP_VALIDATE_RET( pt != NULL );
804 : 20 : ECP_VALIDATE_RET( buf != NULL );
805 : :
806 [ + - ]: 20 : if( ilen < 1 )
807 : : return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
808 : :
809 : 20 : 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 [ - + ]: 20 : if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
829 : : {
830 [ - + ]: 20 : if( buf[0] == 0x00 )
831 : : {
832 [ # # ]: 0 : if( ilen == 1 )
833 : 0 : return( mbedtls_ecp_set_zero( pt ) );
834 : : else
835 : : return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
836 : : }
837 : :
838 [ + - ]: 20 : if( buf[0] != 0x04 )
839 : : return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
840 : :
841 [ + - ]: 20 : if( ilen != 2 * plen + 1 )
842 : : return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
843 : :
844 [ - + ]: 20 : MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) );
845 [ - + ]: 20 : MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y,
846 : : buf + 1 + plen, plen ) );
847 [ + - ]: 20 : MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
848 : : }
849 : : #endif
850 : :
851 : 20 : 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 : : */
861 : 0 : 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 : 0 : unsigned char data_len;
866 : 0 : const unsigned char *buf_start;
867 : 0 : ECP_VALIDATE_RET( grp != NULL );
868 : 0 : ECP_VALIDATE_RET( pt != NULL );
869 : 0 : ECP_VALIDATE_RET( buf != NULL );
870 : 0 : 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 [ # # ]: 0 : if( buf_len < 2 )
876 : : return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
877 : :
878 : 0 : data_len = *(*buf)++;
879 [ # # # # ]: 0 : 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 : 0 : buf_start = *buf;
886 : 0 : *buf += data_len;
887 : :
888 : 0 : 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 : : */
897 : 0 : 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 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
902 : 0 : ECP_VALIDATE_RET( grp != NULL );
903 : 0 : ECP_VALIDATE_RET( pt != NULL );
904 : 0 : ECP_VALIDATE_RET( olen != NULL );
905 : 0 : ECP_VALIDATE_RET( buf != NULL );
906 : 0 : 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 [ # # ]: 0 : if( blen < 1 )
913 : : return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
914 : :
915 [ # # ]: 0 : 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 : 0 : buf[0] = (unsigned char) *olen;
923 : 0 : ++*olen;
924 : :
925 : 0 : return( 0 );
926 : : }
927 : :
928 : : /*
929 : : * Set a group from an ECParameters record (RFC 4492)
930 : : */
931 : 0 : int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp,
932 : : const unsigned char **buf, size_t len )
933 : : {
934 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
935 : 0 : mbedtls_ecp_group_id grp_id;
936 : 0 : ECP_VALIDATE_RET( grp != NULL );
937 : 0 : ECP_VALIDATE_RET( buf != NULL );
938 : 0 : ECP_VALIDATE_RET( *buf != NULL );
939 : :
940 [ # # ]: 0 : if( ( ret = mbedtls_ecp_tls_read_group_id( &grp_id, buf, len ) ) != 0 )
941 : : return( ret );
942 : :
943 : 0 : 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 : : */
950 : 0 : int mbedtls_ecp_tls_read_group_id( mbedtls_ecp_group_id *grp,
951 : : const unsigned char **buf, size_t len )
952 : : {
953 : 0 : uint16_t tls_id;
954 : 0 : const mbedtls_ecp_curve_info *curve_info;
955 : 0 : ECP_VALIDATE_RET( grp != NULL );
956 : 0 : ECP_VALIDATE_RET( buf != NULL );
957 : 0 : ECP_VALIDATE_RET( *buf != NULL );
958 : :
959 : : /*
960 : : * We expect at least three bytes (see below)
961 : : */
962 [ # # ]: 0 : 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 [ # # ]: 0 : 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 : 0 : tls_id = *(*buf)++;
975 : 0 : tls_id <<= 8;
976 : 0 : tls_id |= *(*buf)++;
977 : :
978 [ # # ]: 0 : if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
979 : : return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
980 : :
981 : 0 : *grp = curve_info->grp_id;
982 : :
983 : 0 : return( 0 );
984 : : }
985 : :
986 : : /*
987 : : * Write the ECParameters record corresponding to a group (RFC 4492)
988 : : */
989 : 0 : int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen,
990 : : unsigned char *buf, size_t blen )
991 : : {
992 : 0 : const mbedtls_ecp_curve_info *curve_info;
993 : 0 : ECP_VALIDATE_RET( grp != NULL );
994 : 0 : ECP_VALIDATE_RET( buf != NULL );
995 : 0 : ECP_VALIDATE_RET( olen != NULL );
996 : :
997 [ # # ]: 0 : 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 : 0 : *olen = 3;
1004 [ # # ]: 0 : if( blen < *olen )
1005 : : return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
1006 : :
1007 : : /*
1008 : : * First byte is curve_type, always named_curve
1009 : : */
1010 : 0 : *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
1011 : :
1012 : : /*
1013 : : * Next two bytes are the namedcurve value
1014 : : */
1015 : 0 : MBEDTLS_PUT_UINT16_BE( curve_info->tls_id, buf, 0 );
1016 : :
1017 : 0 : 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 : : */
1026 : 39180 : static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp )
1027 : : {
1028 : 39180 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1029 : :
1030 [ + - ]: 39180 : if( grp->modp == NULL )
1031 : 39180 : 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 [ # # # # ]: 0 : if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) ||
1035 [ # # ]: 0 : mbedtls_mpi_bitlen( N ) > 2 * grp->pbits )
1036 : : {
1037 : 0 : return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1038 : : }
1039 : :
1040 [ # # ]: 0 : MBEDTLS_MPI_CHK( grp->modp( N ) );
1041 : :
1042 : : /* N->s < 0 is a much faster test, which fails only if N is 0 */
1043 [ # # ]: 0 : while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 )
1044 [ # # # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) );
1045 : :
1046 [ # # ]: 0 : while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 )
1047 : : /* we known P, N and the result are positive */
1048 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) );
1049 : :
1050 : 0 : 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 : :
1080 : 39180 : 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 : 39180 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1086 [ - + ]: 39180 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( X, A, B ) );
1087 [ + - ]: 39180 : MOD_MUL( *X );
1088 : 39180 : cleanup:
1089 : 39180 : 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) ) )
1107 : 22816 : 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 : 22816 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1113 [ - + ]: 22816 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( X, A, B ) );
1114 [ + - + + : 34199 : MOD_SUB( *X );
+ - ]
1115 : 22816 : cleanup:
1116 : 22816 : 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 : :
1129 : 3120 : 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 : 3120 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1135 [ - + ]: 3120 : MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, A, B ) );
1136 [ + - + + ]: 4671 : MOD_ADD( *X );
1137 : 3120 : cleanup:
1138 : 3120 : 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) )
1145 : 13556 : static inline int mbedtls_mpi_shift_l_mod( const mbedtls_ecp_group *grp,
1146 : : mbedtls_mpi *X,
1147 : : size_t count )
1148 : : {
1149 : 13556 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1150 [ - + ]: 13556 : MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( X, count ) );
1151 [ + - + + ]: 20375 : MOD_ADD( *X );
1152 : 13556 : cleanup:
1153 : 13556 : 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 : : */
1170 : 26 : static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt )
1171 : : {
1172 [ + - ]: 26 : 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 : 26 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1184 : 26 : mbedtls_mpi Zi, ZZi;
1185 : 26 : mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
1186 : :
1187 : : /*
1188 : : * X = X / Z^2 mod p
1189 : : */
1190 [ - + ]: 26 : MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z, &grp->P ) );
1191 [ - + ]: 26 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ZZi, &Zi, &Zi ) );
1192 [ - + ]: 26 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->X, &pt->X, &ZZi ) );
1193 : :
1194 : : /*
1195 : : * Y = Y / Z^3 mod p
1196 : : */
1197 [ - + ]: 26 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y, &pt->Y, &ZZi ) );
1198 [ - + ]: 26 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y, &pt->Y, &Zi ) );
1199 : :
1200 : : /*
1201 : : * Z = 1
1202 : : */
1203 [ + - ]: 26 : MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
1204 : :
1205 : 26 : cleanup:
1206 : :
1207 : 26 : mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
1208 : :
1209 : 26 : 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 : : */
1224 : 20 : static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
1225 : : mbedtls_ecp_point *T[], size_t T_size )
1226 : : {
1227 [ - + ]: 20 : if( T_size < 2 )
1228 : 0 : 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 : 20 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1239 : 20 : size_t i;
1240 : 20 : mbedtls_mpi *c, u, Zi, ZZi;
1241 : :
1242 [ + - ]: 20 : if( ( c = mbedtls_calloc( T_size, sizeof( mbedtls_mpi ) ) ) == NULL )
1243 : : return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
1244 : :
1245 [ + + ]: 120 : for( i = 0; i < T_size; i++ )
1246 : 100 : mbedtls_mpi_init( &c[i] );
1247 : :
1248 : 20 : mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
1249 : :
1250 : : /*
1251 : : * c[i] = Z_0 * ... * Z_i
1252 : : */
1253 [ - + ]: 20 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) );
1254 [ + + ]: 100 : for( i = 1; i < T_size; i++ )
1255 : : {
1256 [ - + ]: 80 : 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 [ - + ]: 20 : MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[T_size-1], &grp->P ) );
1263 : :
1264 : 100 : 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 [ + + ]: 100 : if( i == 0 ) {
1271 [ - + ]: 20 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) );
1272 : : }
1273 : : else
1274 : : {
1275 [ - + ]: 80 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &Zi, &u, &c[i-1] ) );
1276 [ - + ]: 80 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &u, &u, &T[i]->Z ) );
1277 : : }
1278 : :
1279 : : /*
1280 : : * proceed as in normalize()
1281 : : */
1282 [ - + ]: 100 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ZZi, &Zi, &Zi ) );
1283 [ - + ]: 100 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T[i]->X, &T[i]->X, &ZZi ) );
1284 [ - + ]: 100 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T[i]->Y, &T[i]->Y, &ZZi ) );
1285 [ - + ]: 100 : 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 [ - + ]: 100 : MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) );
1294 [ - + ]: 100 : MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) );
1295 : 100 : mbedtls_mpi_free( &T[i]->Z );
1296 : :
1297 [ + + ]: 100 : if( i == 0 )
1298 : : break;
1299 : : }
1300 : :
1301 : 20 : cleanup:
1302 : :
1303 : 20 : mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
1304 [ + + ]: 140 : for( i = 0; i < T_size; i++ )
1305 : 100 : mbedtls_mpi_free( &c[i] );
1306 : 20 : mbedtls_free( c );
1307 : :
1308 : 20 : 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 : : */
1316 : 1200 : static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp,
1317 : : mbedtls_ecp_point *Q,
1318 : : unsigned char inv )
1319 : : {
1320 : 1200 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1321 : 1200 : unsigned char nonzero;
1322 : 1200 : mbedtls_mpi mQY;
1323 : :
1324 : 1200 : mbedtls_mpi_init( &mQY );
1325 : :
1326 : : /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
1327 [ - + ]: 1200 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) );
1328 : 1200 : nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0;
1329 [ + - ]: 1200 : MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) );
1330 : :
1331 : 1200 : cleanup:
1332 : 1200 : mbedtls_mpi_free( &mQY );
1333 : :
1334 : 1200 : 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 : : */
1351 : 3080 : 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 : 3080 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1367 : 3080 : mbedtls_mpi M, S, T, U;
1368 : :
1369 : 3080 : mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U );
1370 : :
1371 : : /* Special case for A = -3 */
1372 [ + - ]: 3080 : if( grp->A.p == NULL )
1373 : : {
1374 : : /* M = 3(X + Z^2)(X - Z^2) */
1375 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->Z, &P->Z ) );
1376 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &T, &P->X, &S ) );
1377 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &U, &P->X, &S ) );
1378 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &T, &U ) );
1379 [ - + + - : 9215 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
+ + ]
1380 : : }
1381 : : else
1382 : : {
1383 : : /* M = 3.X^2 */
1384 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->X, &P->X ) );
1385 [ # # # # : 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
# # ]
1386 : :
1387 : : /* Optimize away for "koblitz" curves with A = 0 */
1388 [ # # ]: 0 : if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 )
1389 : : {
1390 : : /* M += A.Z^4 */
1391 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->Z, &P->Z ) );
1392 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T, &S, &S ) );
1393 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &T, &grp->A ) );
1394 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &M, &M, &S ) );
1395 : : }
1396 : : }
1397 : :
1398 : : /* S = 4.X.Y^2 */
1399 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T, &P->Y, &P->Y ) );
1400 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &T, 1 ) );
1401 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->X, &T ) );
1402 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &S, 1 ) );
1403 : :
1404 : : /* U = 8.Y^4 */
1405 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &U, &T, &T ) );
1406 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &U, 1 ) );
1407 : :
1408 : : /* T = M^2 - 2.S */
1409 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T, &M, &M ) );
1410 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T, &T, &S ) );
1411 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T, &T, &S ) );
1412 : :
1413 : : /* S = M(S - T) - U */
1414 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &S, &S, &T ) );
1415 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &S, &M ) );
1416 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &S, &S, &U ) );
1417 : :
1418 : : /* U = 2.Y.Z */
1419 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &U, &P->Y, &P->Z ) );
1420 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &U, 1 ) );
1421 : :
1422 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) );
1423 [ - + ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) );
1424 [ + - ]: 3080 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) );
1425 : :
1426 : 3080 : cleanup:
1427 : 3080 : mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U );
1428 : :
1429 : 3080 : 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 : : */
1451 : 1236 : 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 : 1236 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1467 : 1236 : mbedtls_mpi T1, T2, T3, T4, X, Y, Z;
1468 : :
1469 : : /*
1470 : : * Trivial cases: P == 0 or Q == 0 (case 1)
1471 : : */
1472 [ - + ]: 1236 : if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
1473 : 0 : return( mbedtls_ecp_copy( R, Q ) );
1474 : :
1475 [ + + - + ]: 1236 : if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 )
1476 : 0 : return( mbedtls_ecp_copy( R, P ) );
1477 : :
1478 : : /*
1479 : : * Make sure Q coordinates are normalized
1480 : : */
1481 [ + + + - ]: 1236 : if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 )
1482 : : return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1483 : :
1484 : 1236 : mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 );
1485 : 1236 : mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1486 : :
1487 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T1, &P->Z, &P->Z ) );
1488 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T2, &T1, &P->Z ) );
1489 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T1, &T1, &Q->X ) );
1490 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T2, &T2, &Q->Y ) );
1491 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T1, &T1, &P->X ) );
1492 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T2, &T2, &P->Y ) );
1493 : :
1494 : : /* Special cases (2) and (3) */
1495 [ - + ]: 1236 : if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 )
1496 : : {
1497 [ # # ]: 0 : if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 )
1498 : : {
1499 : 0 : ret = ecp_double_jac( grp, R, P );
1500 : 0 : goto cleanup;
1501 : : }
1502 : : else
1503 : : {
1504 : 0 : ret = mbedtls_ecp_set_zero( R );
1505 : 0 : goto cleanup;
1506 : : }
1507 : : }
1508 : :
1509 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &Z, &P->Z, &T1 ) );
1510 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3, &T1, &T1 ) );
1511 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T4, &T3, &T1 ) );
1512 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3, &T3, &P->X ) );
1513 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &T3 ) );
1514 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &T1, 1 ) );
1515 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &X, &T2, &T2 ) );
1516 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &X, &X, &T1 ) );
1517 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &X, &X, &T4 ) );
1518 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T3, &T3, &X ) );
1519 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3, &T3, &T2 ) );
1520 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T4, &T4, &P->Y ) );
1521 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &Y, &T3, &T4 ) );
1522 : :
1523 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) );
1524 [ - + ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) );
1525 [ + - ]: 1236 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) );
1526 : :
1527 : 1236 : cleanup:
1528 : :
1529 : 1236 : mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 );
1530 : 1236 : mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1531 : :
1532 : 1236 : 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 : : */
1543 : 16 : 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 : 16 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1555 : 16 : mbedtls_mpi l, ll;
1556 : :
1557 : 16 : mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll );
1558 : :
1559 : : /* Generate l such that 1 < l < p */
1560 [ - + ]: 16 : MBEDTLS_MPI_CHK( mbedtls_mpi_random( &l, 2, &grp->P, f_rng, p_rng ) );
1561 : :
1562 : : /* Z = l * Z */
1563 [ - + ]: 16 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Z, &pt->Z, &l ) );
1564 : :
1565 : : /* X = l^2 * X */
1566 [ - + ]: 16 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ll, &l, &l ) );
1567 [ - + ]: 16 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->X, &pt->X, &ll ) );
1568 : :
1569 : : /* Y = l^3 * Y */
1570 [ - + ]: 16 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ll, &ll, &l ) );
1571 [ + - ]: 16 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y, &pt->Y, &ll ) );
1572 : :
1573 : 16 : cleanup:
1574 : 16 : mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll );
1575 : :
1576 [ - + ]: 16 : if( ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
1577 : 0 : ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
1578 : 16 : 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 : : */
1642 : 20 : static void ecp_comb_recode_core( unsigned char x[], size_t d,
1643 : : unsigned char w, const mbedtls_mpi *m )
1644 : : {
1645 : 20 : size_t i, j;
1646 : 20 : unsigned char c, cc, adjust;
1647 : :
1648 : 20 : memset( x, 0, d+1 );
1649 : :
1650 : : /* First get the classical comb values (except for x_d = 0) */
1651 [ + + ]: 1180 : for( i = 0; i < d; i++ )
1652 [ + + ]: 6320 : for( j = 0; j < w; j++ )
1653 : 5160 : 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 [ + + ]: 1180 : for( i = 1; i <= d; i++ )
1658 : : {
1659 : : /* Add carry and update it */
1660 : 1160 : cc = x[i] & c;
1661 : 1160 : x[i] = x[i] ^ c;
1662 : 1160 : c = cc;
1663 : :
1664 : : /* Adjust if needed, avoiding branches */
1665 : 1160 : adjust = 1 - ( x[i] & 0x01 );
1666 : 1160 : c |= x[i] & ( x[i-1] * adjust );
1667 : 1160 : x[i] = x[i] ^ ( x[i-1] * adjust );
1668 : 1160 : x[i-1] |= adjust << 7;
1669 : : }
1670 : 20 : }
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 : : */
1706 : 10 : 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 : 10 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1712 : 10 : unsigned char i;
1713 : 10 : size_t j = 0;
1714 : 10 : const unsigned char T_size = 1U << ( w - 1 );
1715 : 10 : 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 : 10 : (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 [ + - ]: 10 : 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 [ + + ]: 1930 : for( ; j < d * ( w - 1 ); j++ )
1758 : : {
1759 : 1920 : MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL );
1760 : :
1761 : 1920 : i = 1U << ( j / d );
1762 : 1920 : cur = T + i;
1763 : :
1764 [ + + ]: 1920 : if( j % d == 0 )
1765 [ - + ]: 30 : MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) );
1766 : :
1767 [ - + ]: 1920 : 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 [ + + ]: 40 : for( i = 1; i < T_size; i <<= 1 )
1782 : 30 : TT[j++] = T + i;
1783 : :
1784 : 10 : MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 );
1785 : :
1786 [ + - ]: 10 : 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 [ + + ]: 40 : for( i = 1; i < T_size; i <<= 1 )
1801 : : {
1802 : 30 : j = i;
1803 : 30 : while( j-- )
1804 [ - + + + ]: 100 : 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 [ + + ]: 80 : for( j = 0; j + 1 < T_size; j++ )
1819 : 70 : TT[j] = T + j + 1;
1820 : :
1821 : 10 : MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 );
1822 : :
1823 [ + - ]: 10 : MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) );
1824 : :
1825 : 10 : 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 : 10 : 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 : : */
1843 : 1180 : 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 : 1180 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1848 : 1180 : unsigned char ii, j;
1849 : :
1850 : : /* Ignore the "sign" bit and scale down */
1851 : 1180 : ii = ( i & 0x7Fu ) >> 1;
1852 : :
1853 : : /* Read the whole table to thwart cache-based timing attacks */
1854 [ + + ]: 14860 : for( j = 0; j < T_size; j++ )
1855 : : {
1856 [ - + ]: 13680 : MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) );
1857 [ - + ]: 13680 : 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 [ + - ]: 1180 : MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
1862 : :
1863 : 1180 : cleanup:
1864 : 1180 : 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 : : */
1873 : 20 : 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 : 20 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1881 : 20 : mbedtls_ecp_point Txi;
1882 : 20 : size_t i;
1883 : :
1884 : 20 : mbedtls_ecp_point_init( &Txi );
1885 : :
1886 : : #if !defined(MBEDTLS_ECP_RESTARTABLE)
1887 : 20 : (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 : 20 : i = d;
1909 [ - + ]: 20 : MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, T_size, x[i] ) );
1910 [ - + ]: 20 : MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 1 ) );
1911 [ + + ]: 20 : if( f_rng != 0 )
1912 [ - + ]: 8 : MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
1913 : : }
1914 : :
1915 : 1180 : while( i != 0 )
1916 : : {
1917 : 1160 : MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD );
1918 : 1160 : --i;
1919 : :
1920 [ - + ]: 1160 : MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) );
1921 [ - + ]: 1160 : MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, T_size, x[i] ) );
1922 [ + - + + ]: 2340 : MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
1923 : : }
1924 : :
1925 : 20 : cleanup:
1926 : :
1927 : 20 : 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 : 20 : 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 : : */
1953 : 20 : 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 : 20 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1961 : 20 : mbedtls_mpi M, mm;
1962 : :
1963 : 20 : mbedtls_mpi_init( &M );
1964 : 20 : mbedtls_mpi_init( &mm );
1965 : :
1966 : : /* N is always odd (see above), just make extra sure */
1967 [ + - ]: 20 : 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 : 20 : *parity_trick = ( mbedtls_mpi_get_bit( m, 0 ) == 0 );
1972 : :
1973 : : /* execute parity fix in constant time */
1974 [ - + ]: 20 : MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) );
1975 [ - + ]: 20 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N, m ) );
1976 [ - + ]: 20 : MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, *parity_trick ) );
1977 : :
1978 : : /* actual scalar recoding */
1979 : 20 : ecp_comb_recode_core( k, d, w, &M );
1980 : :
1981 : 20 : cleanup:
1982 : 20 : mbedtls_mpi_free( &mm );
1983 : 20 : mbedtls_mpi_free( &M );
1984 : :
1985 : 20 : 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 : : */
1995 : 20 : 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 : 20 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2007 : 20 : unsigned char parity_trick;
2008 : 20 : unsigned char k[COMB_MAX_D + 1];
2009 : 20 : 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 [ - + ]: 20 : MBEDTLS_MPI_CHK( ecp_comb_recode_scalar( grp, m, k, d, w,
2022 : : &parity_trick ) );
2023 [ - + ]: 20 : MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, RR, T, T_size, k, d,
2024 : : f_rng, p_rng, rs_ctx ) );
2025 [ - + ]: 20 : 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 [ + + ]: 20 : if( f_rng != 0 )
2046 [ - + ]: 8 : MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, RR, f_rng, p_rng ) );
2047 : :
2048 [ + - ]: 20 : 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 : 20 : cleanup:
2056 : 20 : return( ret );
2057 : : }
2058 : :
2059 : : /*
2060 : : * Pick window size based on curve size and whether we optimize for base point
2061 : : */
2062 : 20 : static unsigned char ecp_pick_window_size( const mbedtls_ecp_group *grp,
2063 : : unsigned char p_eq_g )
2064 : : {
2065 : 20 : 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 [ + - ]: 20 : 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 [ + + ]: 20 : if( p_eq_g )
2080 : 10 : 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 [ + + - + ]: 20 : 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 [ - + ]: 20 : if( w >= grp->nbits )
2096 : 0 : w = 2;
2097 : :
2098 : 20 : 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 : : */
2114 : 20 : 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 : 20 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2121 : 20 : unsigned char w, p_eq_g, i;
2122 : 20 : size_t d;
2123 : 20 : unsigned char T_size = 0, T_ok = 0;
2124 : 20 : mbedtls_ecp_point *T = NULL;
2125 : :
2126 : 20 : ECP_RS_ENTER( rsm );
2127 : :
2128 : : /* Is P the base point ? */
2129 : : #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
2130 [ + + - + ]: 30 : p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&
2131 : 10 : 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 : 20 : w = ecp_pick_window_size( grp, p_eq_g );
2138 : 20 : T_size = 1U << ( w - 1 );
2139 : 20 : d = ( grp->nbits + w - 1 ) / w;
2140 : :
2141 : : /* Pre-computed table: do we have it already for the base point? */
2142 [ + + - + ]: 20 : 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 : 10 : T = mbedtls_calloc( T_size, sizeof( mbedtls_ecp_point ) );
2166 [ - + ]: 10 : if( T == NULL )
2167 : : {
2168 : 0 : ret = MBEDTLS_ERR_ECP_ALLOC_FAILED;
2169 : 0 : goto cleanup;
2170 : : }
2171 : :
2172 [ + + ]: 90 : for( i = 0; i < T_size; i++ )
2173 : 80 : 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 : 10 : if( !T_ok )
2180 : : {
2181 [ - + ]: 10 : MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d, rs_ctx ) );
2182 : :
2183 [ - + ]: 10 : 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 : 0 : grp->T = T;
2188 : 0 : grp->T_size = T_size;
2189 : : }
2190 : : }
2191 : :
2192 : : /* Actual comb multiplication using precomputed points */
2193 [ + - ]: 20 : 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 : 20 : cleanup:
2198 : :
2199 : : /* does T belong to the group? */
2200 [ + + ]: 20 : 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 [ + - ]: 10 : if( T != NULL )
2216 : : {
2217 [ + + ]: 90 : for( i = 0; i < T_size; i++ )
2218 : 80 : mbedtls_ecp_point_free( &T[i] );
2219 : 10 : 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 [ - + ]: 20 : if( ret != 0 )
2228 : 0 : mbedtls_ecp_point_free( R );
2229 : :
2230 : 20 : ECP_RS_LEAVE( rsm );
2231 : :
2232 : 20 : 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 : : */
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 : : */
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 : : */
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 : : */
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 : : */
2452 : 20 : 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 : 20 : 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 : 20 : (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 : 20 : MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_CHK );
2482 : :
2483 : : /* Common sanity checks */
2484 [ - + ]: 20 : MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( grp, m ) );
2485 [ - + ]: 20 : MBEDTLS_MPI_CHK( mbedtls_ecp_check_pubkey( grp, P ) );
2486 : : }
2487 : :
2488 : 20 : 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 [ - + ]: 20 : if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
2495 [ + - ]: 20 : MBEDTLS_MPI_CHK( ecp_mul_comb( grp, R, m, P, f_rng, p_rng, rs_ctx ) );
2496 : : #endif
2497 : :
2498 : 20 : 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 : 20 : return( ret );
2511 : : }
2512 : :
2513 : : /*
2514 : : * Restartable multiplication R = m * P
2515 : : */
2516 : 8 : 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 : 8 : ECP_VALIDATE_RET( grp != NULL );
2522 : 8 : ECP_VALIDATE_RET( R != NULL );
2523 : 8 : ECP_VALIDATE_RET( m != NULL );
2524 : 8 : ECP_VALIDATE_RET( P != NULL );
2525 : :
2526 [ + - ]: 8 : if( f_rng == NULL )
2527 : : return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
2528 : :
2529 : 8 : return( ecp_mul_restartable_internal( grp, R, m, P, f_rng, p_rng, rs_ctx ) );
2530 : : }
2531 : :
2532 : : /*
2533 : : * Multiplication R = m * P
2534 : : */
2535 : 0 : 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 : 0 : ECP_VALIDATE_RET( grp != NULL );
2540 : 0 : ECP_VALIDATE_RET( R != NULL );
2541 : 0 : ECP_VALIDATE_RET( m != NULL );
2542 : 0 : ECP_VALIDATE_RET( P != NULL );
2543 : 0 : 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 : : */
2551 : 40 : static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
2552 : : {
2553 : 40 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2554 : 40 : mbedtls_mpi YY, RHS;
2555 : :
2556 : : /* pt coordinates must be normalized for our checks */
2557 [ + - + - ]: 80 : if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 ||
2558 [ + - ]: 80 : mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 ||
2559 [ - + ]: 80 : mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 ||
2560 : 40 : mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 )
2561 : 0 : return( MBEDTLS_ERR_ECP_INVALID_KEY );
2562 : :
2563 : 40 : 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 [ - + ]: 40 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &YY, &pt->Y, &pt->Y ) );
2570 [ - + ]: 40 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &RHS, &pt->X, &pt->X ) );
2571 : :
2572 : : /* Special case for A = -3 */
2573 [ + - ]: 40 : if( grp->A.p == NULL )
2574 : : {
2575 [ - + - - : 40 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS );
- + - - ]
2576 : : }
2577 : : else
2578 : : {
2579 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &RHS, &RHS, &grp->A ) );
2580 : : }
2581 : :
2582 [ - + ]: 40 : MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &RHS, &RHS, &pt->X ) );
2583 [ - + ]: 40 : MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &RHS, &RHS, &grp->B ) );
2584 : :
2585 [ + - ]: 40 : if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 )
2586 : 0 : ret = MBEDTLS_ERR_ECP_INVALID_KEY;
2587 : :
2588 : 40 : cleanup:
2589 : :
2590 : 40 : mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS );
2591 : :
2592 : 40 : 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 : : */
2601 : 12 : 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 : 12 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2608 : :
2609 [ - + ]: 12 : if( mbedtls_mpi_cmp_int( m, 0 ) == 0 )
2610 : : {
2611 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_ecp_set_zero( R ) );
2612 : : }
2613 [ - + ]: 12 : else if( mbedtls_mpi_cmp_int( m, 1 ) == 0 )
2614 : : {
2615 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
2616 : : }
2617 [ - + ]: 12 : else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 )
2618 : : {
2619 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
2620 [ # # ]: 0 : if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 )
2621 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) );
2622 : : }
2623 : : else
2624 : : {
2625 [ + - ]: 12 : MBEDTLS_MPI_CHK( ecp_mul_restartable_internal( grp, R, m, P,
2626 : : NULL, NULL, rs_ctx ) );
2627 : : }
2628 : :
2629 : 12 : cleanup:
2630 : 12 : return( ret );
2631 : : }
2632 : :
2633 : : /*
2634 : : * Restartable linear combination
2635 : : * NOT constant-time
2636 : : */
2637 : 6 : 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 : 6 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2644 : 6 : mbedtls_ecp_point mP;
2645 : 6 : mbedtls_ecp_point *pmP = &mP;
2646 : 6 : mbedtls_ecp_point *pR = R;
2647 : : #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2648 : : char is_grp_capable = 0;
2649 : : #endif
2650 : 6 : ECP_VALIDATE_RET( grp != NULL );
2651 : 6 : ECP_VALIDATE_RET( R != NULL );
2652 : 6 : ECP_VALIDATE_RET( m != NULL );
2653 : 6 : ECP_VALIDATE_RET( P != NULL );
2654 : 6 : ECP_VALIDATE_RET( n != NULL );
2655 : 6 : ECP_VALIDATE_RET( Q != NULL );
2656 : :
2657 [ + - ]: 6 : if( mbedtls_ecp_get_type( grp ) != MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
2658 : : return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
2659 : :
2660 : 6 : mbedtls_ecp_point_init( &mP );
2661 : :
2662 : 6 : 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 [ - + ]: 6 : 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 [ - + ]: 6 : 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 : 6 : MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_ADD );
2702 [ - + ]: 6 : 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 : 6 : MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV );
2710 [ + - ]: 6 : 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 : 6 : 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 : 6 : mbedtls_ecp_point_free( &mP );
2724 : :
2725 : 6 : ECP_RS_LEAVE( ma );
2726 : :
2727 : 6 : return( ret );
2728 : : }
2729 : :
2730 : : /*
2731 : : * Linear combination
2732 : : * NOT constant-time
2733 : : */
2734 : 0 : 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 : 0 : ECP_VALIDATE_RET( grp != NULL );
2739 : 0 : ECP_VALIDATE_RET( R != NULL );
2740 : 0 : ECP_VALIDATE_RET( m != NULL );
2741 : 0 : ECP_VALIDATE_RET( P != NULL );
2742 : 0 : ECP_VALIDATE_RET( n != NULL );
2743 : 0 : ECP_VALIDATE_RET( Q != NULL );
2744 : 0 : 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 : : */
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 : : */
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 : : */
2864 : 40 : int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp,
2865 : : const mbedtls_ecp_point *pt )
2866 : : {
2867 : 40 : ECP_VALIDATE_RET( grp != NULL );
2868 : 40 : ECP_VALIDATE_RET( pt != NULL );
2869 : :
2870 : : /* Must use affine coordinates */
2871 [ + - ]: 40 : 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 [ + - ]: 40 : if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
2880 : 40 : 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 : : */
2888 : 36 : int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp,
2889 : : const mbedtls_mpi *d )
2890 : : {
2891 : 36 : ECP_VALIDATE_RET( grp != NULL );
2892 : 36 : 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 [ + - ]: 36 : if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
2912 : : {
2913 : : /* see SEC1 3.2 */
2914 [ + - - + ]: 72 : if( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
2915 : 36 : mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 )
2916 : 0 : 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
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)
2960 : 8 : 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 : 8 : int ret = mbedtls_mpi_random( d, 1, N, f_rng, p_rng );
2965 [ + - ]: 8 : switch( ret )
2966 : : {
2967 : : case MBEDTLS_ERR_MPI_NOT_ACCEPTABLE:
2968 : : return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
2969 : 8 : default:
2970 : 8 : return( ret );
2971 : : }
2972 : : }
2973 : : #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
2974 : :
2975 : : /*
2976 : : * Generate a private key
2977 : : */
2978 : 8 : 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 : 8 : ECP_VALIDATE_RET( grp != NULL );
2984 : 8 : ECP_VALIDATE_RET( d != NULL );
2985 : 8 : 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 [ + - ]: 8 : if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
2994 : 8 : 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 : : */
3003 : 0 : 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 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3010 : 0 : ECP_VALIDATE_RET( grp != NULL );
3011 : 0 : ECP_VALIDATE_RET( d != NULL );
3012 : 0 : ECP_VALIDATE_RET( G != NULL );
3013 : 0 : ECP_VALIDATE_RET( Q != NULL );
3014 : 0 : ECP_VALIDATE_RET( f_rng != NULL );
3015 : :
3016 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, d, f_rng, p_rng ) );
3017 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) );
3018 : :
3019 : 0 : cleanup:
3020 : 0 : return( ret );
3021 : : }
3022 : :
3023 : : /*
3024 : : * Generate key pair, wrapper for conventional base point
3025 : : */
3026 : 0 : 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 : 0 : ECP_VALIDATE_RET( grp != NULL );
3032 : 0 : ECP_VALIDATE_RET( d != NULL );
3033 : 0 : ECP_VALIDATE_RET( Q != NULL );
3034 : 0 : ECP_VALIDATE_RET( f_rng != NULL );
3035 : :
3036 : 0 : 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 : : */
3042 : 0 : 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 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3046 : 0 : ECP_VALIDATE_RET( key != NULL );
3047 : 0 : ECP_VALIDATE_RET( f_rng != NULL );
3048 : :
3049 [ # # ]: 0 : if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 )
3050 : : return( ret );
3051 : :
3052 : 0 : 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 : : */
3060 : 16 : 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 : 16 : int ret = 0;
3064 : :
3065 : 16 : ECP_VALIDATE_RET( key != NULL );
3066 : 16 : ECP_VALIDATE_RET( buf != NULL );
3067 : :
3068 [ + - ]: 16 : if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 )
3069 : : return( ret );
3070 : :
3071 : 16 : 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 [ - + ]: 16 : if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
3125 : : {
3126 [ - + ]: 16 : MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &key->d, buf, buflen ) );
3127 : :
3128 [ + - ]: 16 : MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( &key->grp, &key->d ) );
3129 : : }
3130 : :
3131 : : #endif
3132 : 16 : cleanup:
3133 : :
3134 [ - + ]: 16 : if( ret != 0 )
3135 : 0 : mbedtls_mpi_free( &key->d );
3136 : :
3137 : : return( ret );
3138 : : }
3139 : :
3140 : : /*
3141 : : * Write a private key.
3142 : : */
3143 : 8 : int mbedtls_ecp_write_key( mbedtls_ecp_keypair *key,
3144 : : unsigned char *buf, size_t buflen )
3145 : : {
3146 : 8 : int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
3147 : :
3148 : 8 : ECP_VALIDATE_RET( key != NULL );
3149 : 8 : 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 [ - + ]: 8 : if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
3170 : : {
3171 [ + - ]: 8 : MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &key->d, buf, buflen ) );
3172 : : }
3173 : :
3174 : : #endif
3175 : 8 : cleanup:
3176 : :
3177 : 8 : return( ret );
3178 : : }
3179 : :
3180 : :
3181 : : /*
3182 : : * Check a public-private key pair
3183 : : */
3184 : 0 : 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 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3189 : 0 : mbedtls_ecp_point Q;
3190 : 0 : mbedtls_ecp_group grp;
3191 : 0 : ECP_VALIDATE_RET( pub != NULL );
3192 : 0 : ECP_VALIDATE_RET( prv != NULL );
3193 : :
3194 [ # # ]: 0 : if( pub->grp.id == MBEDTLS_ECP_DP_NONE ||
3195 [ # # # # ]: 0 : pub->grp.id != prv->grp.id ||
3196 [ # # ]: 0 : mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) ||
3197 [ # # ]: 0 : mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) ||
3198 : 0 : mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) )
3199 : : {
3200 : 0 : return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
3201 : : }
3202 : :
3203 : 0 : mbedtls_ecp_point_init( &Q );
3204 : 0 : mbedtls_ecp_group_init( &grp );
3205 : :
3206 : : /* mbedtls_ecp_mul() needs a non-const group... */
3207 : 0 : mbedtls_ecp_group_copy( &grp, &prv->grp );
3208 : :
3209 : : /* Also checks d is valid */
3210 [ # # ]: 0 : MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, f_rng, p_rng ) );
3211 : :
3212 [ # # # # ]: 0 : if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) ||
3213 [ # # ]: 0 : mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) ||
3214 : 0 : mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) )
3215 : : {
3216 : 0 : ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3217 : 0 : goto cleanup;
3218 : : }
3219 : :
3220 : 0 : cleanup:
3221 : 0 : mbedtls_ecp_point_free( &Q );
3222 : 0 : mbedtls_ecp_group_free( &grp );
3223 : :
3224 : 0 : 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 : : */
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. */
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. */
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 : : */
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 */
|
