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