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 *
55 * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf
56 *
57 * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
58 * for elliptic curve cryptosystems. In : Cryptographic Hardware and
59 * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
60 * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
61 *
62 * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
63 * render ECC resistant against Side Channel Attacks. IACR Cryptology
64 * ePrint Archive, 2004, vol. 2004, p. 342.
65 * <http://eprint.iacr.org/2004/342.pdf>
66 */
67
68 #if !defined(MBEDTLS_CONFIG_FILE)
69 #include "mbedtls/config.h"
70 #else
71 #include MBEDTLS_CONFIG_FILE
72 #endif
73
74 #if defined(MBEDTLS_ECP_C)
75
76 #include "mbedtls/ecp.h"
77 #include "mbedtls/threading.h"
78
79 #include <string.h>
80
81 #if !defined(MBEDTLS_ECP_ALT)
82
83 #if defined(MBEDTLS_PLATFORM_C)
84 #include "mbedtls/platform.h"
85 #else
86 #include <stdlib.h>
87 #include <stdio.h>
88 #define mbedtls_printf printf
89 #define mbedtls_calloc calloc
90 #define mbedtls_free free
91 #endif
92
93 #include "mbedtls/ecp_internal.h"
94
95 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
96 #if defined(MBEDTLS_HMAC_DRBG_C)
97 #include "mbedtls/hmac_drbg.h"
98 #elif defined(MBEDTLS_CTR_DRBG_C)
99 #include "mbedtls/ctr_drbg.h"
100 #elif defined(MBEDTLS_SHA512_C)
101 #include "mbedtls/sha512.h"
102 #elif defined(MBEDTLS_SHA256_C)
103 #include "mbedtls/sha256.h"
104 #else
105 #error "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid."
106 #endif
107 #endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */
108
109 #if ( defined(__ARMCC_VERSION) || defined(_MSC_VER) ) && \
110 !defined(inline) && !defined(__cplusplus)
111 #define inline __inline
112 #endif
113
114 /* Implementation that should never be optimized out by the compiler */
mbedtls_zeroize(void * v,size_t n)115 static void mbedtls_zeroize( void *v, size_t n ) {
116 volatile unsigned char *p = v; while( n-- ) *p++ = 0;
117 }
118
119 #if defined(MBEDTLS_SELF_TEST)
120 /*
121 * Counts of point addition and doubling, and field multiplications.
122 * Used to test resistance of point multiplication to simple timing attacks.
123 */
124 static unsigned long add_count, dbl_count, mul_count;
125 #endif
126
127 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
128 /*
129 * Currently ecp_mul() takes a RNG function as an argument, used for
130 * side-channel protection, but it can be NULL. The initial reasoning was
131 * that people will pass non-NULL RNG when they care about side-channels, but
132 * unfortunately we have some APIs that call ecp_mul() with a NULL RNG, with
133 * no opportunity for the user to do anything about it.
134 *
135 * The obvious strategies for addressing that include:
136 * - change those APIs so that they take RNG arguments;
137 * - require a global RNG to be available to all crypto modules.
138 *
139 * Unfortunately those would break compatibility. So what we do instead is
140 * have our own internal DRBG instance, seeded from the secret scalar.
141 *
142 * The following is a light-weight abstraction layer for doing that with
143 * HMAC_DRBG (first choice) or CTR_DRBG.
144 */
145
146 #if defined(MBEDTLS_HMAC_DRBG_C)
147
148 /* DRBG context type */
149 typedef mbedtls_hmac_drbg_context ecp_drbg_context;
150
151 /* DRBG context init */
ecp_drbg_init(ecp_drbg_context * ctx)152 static inline void ecp_drbg_init( ecp_drbg_context *ctx )
153 {
154 mbedtls_hmac_drbg_init( ctx );
155 }
156
157 /* DRBG context free */
ecp_drbg_free(ecp_drbg_context * ctx)158 static inline void ecp_drbg_free( ecp_drbg_context *ctx )
159 {
160 mbedtls_hmac_drbg_free( ctx );
161 }
162
163 /* DRBG function */
ecp_drbg_random(void * p_rng,unsigned char * output,size_t output_len)164 static inline int ecp_drbg_random( void *p_rng,
165 unsigned char *output, size_t output_len )
166 {
167 return( mbedtls_hmac_drbg_random( p_rng, output, output_len ) );
168 }
169
170 /* DRBG context seeding */
ecp_drbg_seed(ecp_drbg_context * ctx,const mbedtls_mpi * secret,size_t secret_len)171 static int ecp_drbg_seed( ecp_drbg_context *ctx,
172 const mbedtls_mpi *secret, size_t secret_len )
173 {
174 int ret;
175 unsigned char secret_bytes[MBEDTLS_ECP_MAX_BYTES];
176 /* The list starts with strong hashes */
177 const mbedtls_md_type_t md_type = mbedtls_md_list()[0];
178 const mbedtls_md_info_t *md_info = mbedtls_md_info_from_type( md_type );
179
180 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( secret,
181 secret_bytes, secret_len ) );
182
183 ret = mbedtls_hmac_drbg_seed_buf( ctx, md_info, secret_bytes, secret_len );
184
185 cleanup:
186 mbedtls_zeroize( secret_bytes, secret_len );
187
188 return( ret );
189 }
190
191 #elif defined(MBEDTLS_CTR_DRBG_C)
192
193 /* DRBG context type */
194 typedef mbedtls_ctr_drbg_context ecp_drbg_context;
195
196 /* DRBG context init */
ecp_drbg_init(ecp_drbg_context * ctx)197 static inline void ecp_drbg_init( ecp_drbg_context *ctx )
198 {
199 mbedtls_ctr_drbg_init( ctx );
200 }
201
202 /* DRBG context free */
ecp_drbg_free(ecp_drbg_context * ctx)203 static inline void ecp_drbg_free( ecp_drbg_context *ctx )
204 {
205 mbedtls_ctr_drbg_free( ctx );
206 }
207
208 /* DRBG function */
ecp_drbg_random(void * p_rng,unsigned char * output,size_t output_len)209 static inline int ecp_drbg_random( void *p_rng,
210 unsigned char *output, size_t output_len )
211 {
212 return( mbedtls_ctr_drbg_random( p_rng, output, output_len ) );
213 }
214
215 /*
216 * Since CTR_DRBG doesn't have a seed_buf() function the way HMAC_DRBG does,
217 * we need to pass an entropy function when seeding. So we use a dummy
218 * function for that, and pass the actual entropy as customisation string.
219 * (During seeding of CTR_DRBG the entropy input and customisation string are
220 * concatenated before being used to update the secret state.)
221 */
ecp_ctr_drbg_null_entropy(void * ctx,unsigned char * out,size_t len)222 static int ecp_ctr_drbg_null_entropy(void *ctx, unsigned char *out, size_t len)
223 {
224 (void) ctx;
225 memset( out, 0, len );
226 return( 0 );
227 }
228
229 /* DRBG context seeding */
ecp_drbg_seed(ecp_drbg_context * ctx,const mbedtls_mpi * secret,size_t secret_len)230 static int ecp_drbg_seed( ecp_drbg_context *ctx,
231 const mbedtls_mpi *secret, size_t secret_len )
232 {
233 int ret;
234 unsigned char secret_bytes[MBEDTLS_ECP_MAX_BYTES];
235
236 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( secret,
237 secret_bytes, secret_len ) );
238
239 ret = mbedtls_ctr_drbg_seed( ctx, ecp_ctr_drbg_null_entropy, NULL,
240 secret_bytes, secret_len );
241
242 cleanup:
243 mbedtls_zeroize( secret_bytes, secret_len );
244
245 return( ret );
246 }
247
248 #elif defined(MBEDTLS_SHA512_C) || defined(MBEDTLS_SHA256_C)
249
250 /* This will be used in the self-test function */
251 #define ECP_ONE_STEP_KDF
252
253 /*
254 * We need to expand secret data (the scalar) into a longer stream of bytes.
255 *
256 * We'll use the One-Step KDF from NIST SP 800-56C, with option 1 (H is a hash
257 * function) and empty FixedInfo. (Though we'll make it fit the DRBG API for
258 * convenience, this is not a full-fledged DRBG, but we don't need one here.)
259 *
260 * We need a basic hash abstraction layer to use whatever SHA-2 is available.
261 */
262 #if defined(MBEDTLS_SHA512_C)
263
264 #define HASH_FUNC( in, ilen, out ) mbedtls_sha512_ret( in, ilen, out, 0 );
265 #define HASH_BLOCK_BYTES ( 512 / 8 )
266
267 #elif defined(MBEDTLS_SHA256_C)
268
269 #define HASH_FUNC( in, ilen, out ) mbedtls_sha256_ret( in, ilen, out, 0 );
270 #define HASH_BLOCK_BYTES ( 256 / 8 )
271
272 #endif /* SHA512/SHA256 abstraction */
273
274 /*
275 * State consists of a 32-bit counter plus the secret value.
276 *
277 * We stored them concatenated in a single buffer as that's what will get
278 * passed to the hash function.
279 */
280 typedef struct {
281 size_t total_len;
282 uint8_t buf[4 + MBEDTLS_ECP_MAX_BYTES];
283 } ecp_drbg_context;
284
ecp_drbg_init(ecp_drbg_context * ctx)285 static void ecp_drbg_init( ecp_drbg_context *ctx )
286 {
287 memset( ctx, 0, sizeof( ecp_drbg_context ) );
288 }
289
ecp_drbg_free(ecp_drbg_context * ctx)290 static void ecp_drbg_free( ecp_drbg_context *ctx )
291 {
292 mbedtls_zeroize( ctx, sizeof( ecp_drbg_context ) );
293 }
294
ecp_drbg_seed(ecp_drbg_context * ctx,const mbedtls_mpi * secret,size_t secret_len)295 static int ecp_drbg_seed( ecp_drbg_context *ctx,
296 const mbedtls_mpi *secret, size_t secret_len )
297 {
298 ctx->total_len = 4 + secret_len;
299 memset( ctx->buf, 0, 4);
300 return( mbedtls_mpi_write_binary( secret, ctx->buf + 4, secret_len ) );
301 }
302
ecp_drbg_random(void * p_rng,unsigned char * output,size_t output_len)303 static int ecp_drbg_random( void *p_rng, unsigned char *output, size_t output_len )
304 {
305 ecp_drbg_context *ctx = p_rng;
306 int ret;
307 size_t len_done = 0;
308 uint8_t tmp[HASH_BLOCK_BYTES];
309
310 while( len_done < output_len )
311 {
312 uint8_t use_len;
313
314 /* This function is only called for coordinate randomisation, which
315 * happens only twice in a scalar multiplication. Each time needs a
316 * random value in the range [2, p-1], and gets it by drawing len(p)
317 * bytes from this function, and retrying up to 10 times if unlucky.
318 *
319 * So for the largest curve, each scalar multiplication draws at most
320 * 20 * 66 bytes. The minimum block size is 32 (SHA-256), so with
321 * rounding that means a most 20 * 3 blocks.
322 *
323 * Since we don't need to draw more that 255 blocks, don't bother
324 * with carry propagation and just return an error instead. We can
325 * change that it we even need to draw more blinding values.
326 */
327 ctx->buf[3] += 1;
328 if( ctx->buf[3] == 0 )
329 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
330
331 ret = HASH_FUNC( ctx->buf, ctx->total_len, tmp );
332 if( ret != 0 )
333 return( ret );
334
335 if( output_len - len_done > HASH_BLOCK_BYTES )
336 use_len = HASH_BLOCK_BYTES;
337 else
338 use_len = output_len - len_done;
339
340 memcpy( output + len_done, tmp, use_len );
341 len_done += use_len;
342 }
343
344 mbedtls_zeroize( tmp, sizeof( tmp ) );
345
346 return( 0 );
347 }
348
349 #else /* DRBG/SHA modules */
350 #error "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid."
351 #endif /* DRBG/SHA modules */
352 #endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */
353
354 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) || \
355 defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) || \
356 defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) || \
357 defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) || \
358 defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) || \
359 defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) || \
360 defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) || \
361 defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) || \
362 defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) || \
363 defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) || \
364 defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
365 #define ECP_SHORTWEIERSTRASS
366 #endif
367
368 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
369 #define ECP_MONTGOMERY
370 #endif
371
372 /*
373 * Curve types: internal for now, might be exposed later
374 */
375 typedef enum
376 {
377 ECP_TYPE_NONE = 0,
378 ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */
379 ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */
380 } ecp_curve_type;
381
382 /*
383 * List of supported curves:
384 * - internal ID
385 * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
386 * - size in bits
387 * - readable name
388 *
389 * Curves are listed in order: largest curves first, and for a given size,
390 * fastest curves first. This provides the default order for the SSL module.
391 *
392 * Reminder: update profiles in x509_crt.c when adding a new curves!
393 */
394 static const mbedtls_ecp_curve_info ecp_supported_curves[] =
395 {
396 #if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
397 { MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" },
398 #endif
399 #if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
400 { MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" },
401 #endif
402 #if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
403 { MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" },
404 #endif
405 #if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
406 { MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" },
407 #endif
408 #if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
409 { MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" },
410 #endif
411 #if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
412 { MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" },
413 #endif
414 #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
415 { MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" },
416 #endif
417 #if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
418 { MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" },
419 #endif
420 #if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
421 { MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" },
422 #endif
423 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
424 { MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" },
425 #endif
426 #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
427 { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" },
428 #endif
429 { MBEDTLS_ECP_DP_NONE, 0, 0, NULL },
430 };
431
432 #define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \
433 sizeof( ecp_supported_curves[0] )
434
435 static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
436
437 /*
438 * List of supported curves and associated info
439 */
mbedtls_ecp_curve_list(void)440 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void )
441 {
442 return( ecp_supported_curves );
443 }
444
445 /*
446 * List of supported curves, group ID only
447 */
mbedtls_ecp_grp_id_list(void)448 const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void )
449 {
450 static int init_done = 0;
451
452 if( ! init_done )
453 {
454 size_t i = 0;
455 const mbedtls_ecp_curve_info *curve_info;
456
457 for( curve_info = mbedtls_ecp_curve_list();
458 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
459 curve_info++ )
460 {
461 ecp_supported_grp_id[i++] = curve_info->grp_id;
462 }
463 ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
464
465 init_done = 1;
466 }
467
468 return( ecp_supported_grp_id );
469 }
470
471 /*
472 * Get the curve info for the internal identifier
473 */
mbedtls_ecp_curve_info_from_grp_id(mbedtls_ecp_group_id grp_id)474 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id )
475 {
476 const mbedtls_ecp_curve_info *curve_info;
477
478 for( curve_info = mbedtls_ecp_curve_list();
479 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
480 curve_info++ )
481 {
482 if( curve_info->grp_id == grp_id )
483 return( curve_info );
484 }
485
486 return( NULL );
487 }
488
489 /*
490 * Get the curve info from the TLS identifier
491 */
mbedtls_ecp_curve_info_from_tls_id(uint16_t tls_id)492 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id )
493 {
494 const mbedtls_ecp_curve_info *curve_info;
495
496 for( curve_info = mbedtls_ecp_curve_list();
497 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
498 curve_info++ )
499 {
500 if( curve_info->tls_id == tls_id )
501 return( curve_info );
502 }
503
504 return( NULL );
505 }
506
507 /*
508 * Get the curve info from the name
509 */
mbedtls_ecp_curve_info_from_name(const char * name)510 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name )
511 {
512 const mbedtls_ecp_curve_info *curve_info;
513
514 for( curve_info = mbedtls_ecp_curve_list();
515 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
516 curve_info++ )
517 {
518 if( strcmp( curve_info->name, name ) == 0 )
519 return( curve_info );
520 }
521
522 return( NULL );
523 }
524
525 /*
526 * Get the type of a curve
527 */
ecp_get_type(const mbedtls_ecp_group * grp)528 static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp )
529 {
530 if( grp->G.X.p == NULL )
531 return( ECP_TYPE_NONE );
532
533 if( grp->G.Y.p == NULL )
534 return( ECP_TYPE_MONTGOMERY );
535 else
536 return( ECP_TYPE_SHORT_WEIERSTRASS );
537 }
538
539 /*
540 * Initialize (the components of) a point
541 */
mbedtls_ecp_point_init(mbedtls_ecp_point * pt)542 void mbedtls_ecp_point_init( mbedtls_ecp_point *pt )
543 {
544 if( pt == NULL )
545 return;
546
547 mbedtls_mpi_init( &pt->X );
548 mbedtls_mpi_init( &pt->Y );
549 mbedtls_mpi_init( &pt->Z );
550 }
551
552 /*
553 * Initialize (the components of) a group
554 */
mbedtls_ecp_group_init(mbedtls_ecp_group * grp)555 void mbedtls_ecp_group_init( mbedtls_ecp_group *grp )
556 {
557 if( grp == NULL )
558 return;
559
560 memset( grp, 0, sizeof( mbedtls_ecp_group ) );
561 }
562
563 /*
564 * Initialize (the components of) a key pair
565 */
mbedtls_ecp_keypair_init(mbedtls_ecp_keypair * key)566 void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key )
567 {
568 if( key == NULL )
569 return;
570
571 mbedtls_ecp_group_init( &key->grp );
572 mbedtls_mpi_init( &key->d );
573 mbedtls_ecp_point_init( &key->Q );
574 }
575
576 /*
577 * Unallocate (the components of) a point
578 */
mbedtls_ecp_point_free(mbedtls_ecp_point * pt)579 void mbedtls_ecp_point_free( mbedtls_ecp_point *pt )
580 {
581 if( pt == NULL )
582 return;
583
584 mbedtls_mpi_free( &( pt->X ) );
585 mbedtls_mpi_free( &( pt->Y ) );
586 mbedtls_mpi_free( &( pt->Z ) );
587 }
588
589 /*
590 * Unallocate (the components of) a group
591 */
mbedtls_ecp_group_free(mbedtls_ecp_group * grp)592 void mbedtls_ecp_group_free( mbedtls_ecp_group *grp )
593 {
594 size_t i;
595
596 if( grp == NULL )
597 return;
598
599 if( grp->h != 1 )
600 {
601 mbedtls_mpi_free( &grp->P );
602 mbedtls_mpi_free( &grp->A );
603 mbedtls_mpi_free( &grp->B );
604 mbedtls_ecp_point_free( &grp->G );
605 mbedtls_mpi_free( &grp->N );
606 }
607
608 if( grp->T != NULL )
609 {
610 for( i = 0; i < grp->T_size; i++ )
611 mbedtls_ecp_point_free( &grp->T[i] );
612 mbedtls_free( grp->T );
613 }
614
615 mbedtls_zeroize( grp, sizeof( mbedtls_ecp_group ) );
616 }
617
618 /*
619 * Unallocate (the components of) a key pair
620 */
mbedtls_ecp_keypair_free(mbedtls_ecp_keypair * key)621 void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key )
622 {
623 if( key == NULL )
624 return;
625
626 mbedtls_ecp_group_free( &key->grp );
627 mbedtls_mpi_free( &key->d );
628 mbedtls_ecp_point_free( &key->Q );
629 }
630
631 /*
632 * Copy the contents of a point
633 */
mbedtls_ecp_copy(mbedtls_ecp_point * P,const mbedtls_ecp_point * Q)634 int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
635 {
636 int ret;
637
638 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X, &Q->X ) );
639 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y, &Q->Y ) );
640 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z, &Q->Z ) );
641
642 cleanup:
643 return( ret );
644 }
645
646 /*
647 * Copy the contents of a group object
648 */
mbedtls_ecp_group_copy(mbedtls_ecp_group * dst,const mbedtls_ecp_group * src)649 int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src )
650 {
651 return mbedtls_ecp_group_load( dst, src->id );
652 }
653
654 /*
655 * Set point to zero
656 */
mbedtls_ecp_set_zero(mbedtls_ecp_point * pt)657 int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt )
658 {
659 int ret;
660
661 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) );
662 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y , 1 ) );
663 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 0 ) );
664
665 cleanup:
666 return( ret );
667 }
668
669 /*
670 * Tell if a point is zero
671 */
mbedtls_ecp_is_zero(mbedtls_ecp_point * pt)672 int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt )
673 {
674 return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 );
675 }
676
677 /*
678 * Compare two points lazily
679 */
mbedtls_ecp_point_cmp(const mbedtls_ecp_point * P,const mbedtls_ecp_point * Q)680 int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P,
681 const mbedtls_ecp_point *Q )
682 {
683 if( mbedtls_mpi_cmp_mpi( &P->X, &Q->X ) == 0 &&
684 mbedtls_mpi_cmp_mpi( &P->Y, &Q->Y ) == 0 &&
685 mbedtls_mpi_cmp_mpi( &P->Z, &Q->Z ) == 0 )
686 {
687 return( 0 );
688 }
689
690 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
691 }
692
693 /*
694 * Import a non-zero point from ASCII strings
695 */
mbedtls_ecp_point_read_string(mbedtls_ecp_point * P,int radix,const char * x,const char * y)696 int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix,
697 const char *x, const char *y )
698 {
699 int ret;
700
701 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X, radix, x ) );
702 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y, radix, y ) );
703 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
704
705 cleanup:
706 return( ret );
707 }
708
709 /*
710 * Export a point into unsigned binary data (SEC1 2.3.3)
711 */
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)712 int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *P,
713 int format, size_t *olen,
714 unsigned char *buf, size_t buflen )
715 {
716 int ret = 0;
717 size_t plen;
718
719 if( format != MBEDTLS_ECP_PF_UNCOMPRESSED &&
720 format != MBEDTLS_ECP_PF_COMPRESSED )
721 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
722
723 /*
724 * Common case: P == 0
725 */
726 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
727 {
728 if( buflen < 1 )
729 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
730
731 buf[0] = 0x00;
732 *olen = 1;
733
734 return( 0 );
735 }
736
737 plen = mbedtls_mpi_size( &grp->P );
738
739 if( format == MBEDTLS_ECP_PF_UNCOMPRESSED )
740 {
741 *olen = 2 * plen + 1;
742
743 if( buflen < *olen )
744 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
745
746 buf[0] = 0x04;
747 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
748 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) );
749 }
750 else if( format == MBEDTLS_ECP_PF_COMPRESSED )
751 {
752 *olen = plen + 1;
753
754 if( buflen < *olen )
755 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
756
757 buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 );
758 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
759 }
760
761 cleanup:
762 return( ret );
763 }
764
765 /*
766 * Import a point from unsigned binary data (SEC1 2.3.4)
767 */
mbedtls_ecp_point_read_binary(const mbedtls_ecp_group * grp,mbedtls_ecp_point * pt,const unsigned char * buf,size_t ilen)768 int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
769 const unsigned char *buf, size_t ilen )
770 {
771 int ret;
772 size_t plen;
773
774 if( ilen < 1 )
775 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
776
777 if( buf[0] == 0x00 )
778 {
779 if( ilen == 1 )
780 return( mbedtls_ecp_set_zero( pt ) );
781 else
782 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
783 }
784
785 plen = mbedtls_mpi_size( &grp->P );
786
787 if( buf[0] != 0x04 )
788 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
789
790 if( ilen != 2 * plen + 1 )
791 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
792
793 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) );
794 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) );
795 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
796
797 cleanup:
798 return( ret );
799 }
800
801 /*
802 * Import a point from a TLS ECPoint record (RFC 4492)
803 * struct {
804 * opaque point <1..2^8-1>;
805 * } ECPoint;
806 */
mbedtls_ecp_tls_read_point(const mbedtls_ecp_group * grp,mbedtls_ecp_point * pt,const unsigned char ** buf,size_t buf_len)807 int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
808 const unsigned char **buf, size_t buf_len )
809 {
810 unsigned char data_len;
811 const unsigned char *buf_start;
812
813 /*
814 * We must have at least two bytes (1 for length, at least one for data)
815 */
816 if( buf_len < 2 )
817 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
818
819 data_len = *(*buf)++;
820 if( data_len < 1 || data_len > buf_len - 1 )
821 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
822
823 /*
824 * Save buffer start for read_binary and update buf
825 */
826 buf_start = *buf;
827 *buf += data_len;
828
829 return mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len );
830 }
831
832 /*
833 * Export a point as a TLS ECPoint record (RFC 4492)
834 * struct {
835 * opaque point <1..2^8-1>;
836 * } ECPoint;
837 */
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)838 int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt,
839 int format, size_t *olen,
840 unsigned char *buf, size_t blen )
841 {
842 int ret;
843
844 /*
845 * buffer length must be at least one, for our length byte
846 */
847 if( blen < 1 )
848 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
849
850 if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format,
851 olen, buf + 1, blen - 1) ) != 0 )
852 return( ret );
853
854 /*
855 * write length to the first byte and update total length
856 */
857 buf[0] = (unsigned char) *olen;
858 ++*olen;
859
860 return( 0 );
861 }
862
863 /*
864 * Set a group from an ECParameters record (RFC 4492)
865 */
mbedtls_ecp_tls_read_group(mbedtls_ecp_group * grp,const unsigned char ** buf,size_t len)866 int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp, const unsigned char **buf, size_t len )
867 {
868 uint16_t tls_id;
869 const mbedtls_ecp_curve_info *curve_info;
870
871 /*
872 * We expect at least three bytes (see below)
873 */
874 if( len < 3 )
875 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
876
877 /*
878 * First byte is curve_type; only named_curve is handled
879 */
880 if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE )
881 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
882
883 /*
884 * Next two bytes are the namedcurve value
885 */
886 tls_id = *(*buf)++;
887 tls_id <<= 8;
888 tls_id |= *(*buf)++;
889
890 if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
891 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
892
893 return mbedtls_ecp_group_load( grp, curve_info->grp_id );
894 }
895
896 /*
897 * Write the ECParameters record corresponding to a group (RFC 4492)
898 */
mbedtls_ecp_tls_write_group(const mbedtls_ecp_group * grp,size_t * olen,unsigned char * buf,size_t blen)899 int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen,
900 unsigned char *buf, size_t blen )
901 {
902 const mbedtls_ecp_curve_info *curve_info;
903
904 if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL )
905 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
906
907 /*
908 * We are going to write 3 bytes (see below)
909 */
910 *olen = 3;
911 if( blen < *olen )
912 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
913
914 /*
915 * First byte is curve_type, always named_curve
916 */
917 *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
918
919 /*
920 * Next two bytes are the namedcurve value
921 */
922 buf[0] = curve_info->tls_id >> 8;
923 buf[1] = curve_info->tls_id & 0xFF;
924
925 return( 0 );
926 }
927
928 /*
929 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
930 * See the documentation of struct mbedtls_ecp_group.
931 *
932 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
933 */
ecp_modp(mbedtls_mpi * N,const mbedtls_ecp_group * grp)934 static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp )
935 {
936 int ret;
937
938 if( grp->modp == NULL )
939 return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) );
940
941 /* N->s < 0 is a much faster test, which fails only if N is 0 */
942 if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) ||
943 mbedtls_mpi_bitlen( N ) > 2 * grp->pbits )
944 {
945 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
946 }
947
948 MBEDTLS_MPI_CHK( grp->modp( N ) );
949
950 /* N->s < 0 is a much faster test, which fails only if N is 0 */
951 while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 )
952 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) );
953
954 while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 )
955 /* we known P, N and the result are positive */
956 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) );
957
958 cleanup:
959 return( ret );
960 }
961
962 /*
963 * Fast mod-p functions expect their argument to be in the 0..p^2 range.
964 *
965 * In order to guarantee that, we need to ensure that operands of
966 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
967 * bring the result back to this range.
968 *
969 * The following macros are shortcuts for doing that.
970 */
971
972 /*
973 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
974 */
975 #if defined(MBEDTLS_SELF_TEST)
976 #define INC_MUL_COUNT mul_count++;
977 #else
978 #define INC_MUL_COUNT
979 #endif
980
981 #define MOD_MUL( N ) do { MBEDTLS_MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
982 while( 0 )
983
984 /*
985 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
986 * N->s < 0 is a very fast test, which fails only if N is 0
987 */
988 #define MOD_SUB( N ) \
989 while( N.s < 0 && mbedtls_mpi_cmp_int( &N, 0 ) != 0 ) \
990 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &N, &N, &grp->P ) )
991
992 /*
993 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
994 * We known P, N and the result are positive, so sub_abs is correct, and
995 * a bit faster.
996 */
997 #define MOD_ADD( N ) \
998 while( mbedtls_mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
999 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &N, &N, &grp->P ) )
1000
1001 #if defined(ECP_SHORTWEIERSTRASS)
1002 /*
1003 * For curves in short Weierstrass form, we do all the internal operations in
1004 * Jacobian coordinates.
1005 *
1006 * For multiplication, we'll use a comb method with coutermeasueres against
1007 * SPA, hence timing attacks.
1008 */
1009
1010 /*
1011 * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1)
1012 * Cost: 1N := 1I + 3M + 1S
1013 */
ecp_normalize_jac(const mbedtls_ecp_group * grp,mbedtls_ecp_point * pt)1014 static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt )
1015 {
1016 int ret;
1017 mbedtls_mpi Zi, ZZi;
1018
1019 if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 )
1020 return( 0 );
1021
1022 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
1023 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1024 {
1025 return mbedtls_internal_ecp_normalize_jac( grp, pt );
1026 }
1027 #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */
1028 mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
1029
1030 /*
1031 * X = X / Z^2 mod p
1032 */
1033 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z, &grp->P ) );
1034 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
1035 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X );
1036
1037 /*
1038 * Y = Y / Z^3 mod p
1039 */
1040 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y );
1041 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y );
1042
1043 /*
1044 * Z = 1
1045 */
1046 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
1047
1048 cleanup:
1049
1050 mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
1051
1052 return( ret );
1053 }
1054
1055 /*
1056 * Normalize jacobian coordinates of an array of (pointers to) points,
1057 * using Montgomery's trick to perform only one inversion mod P.
1058 * (See for example Cohen's "A Course in Computational Algebraic Number
1059 * Theory", Algorithm 10.3.4.)
1060 *
1061 * Warning: fails (returning an error) if one of the points is zero!
1062 * This should never happen, see choice of w in ecp_mul_comb().
1063 *
1064 * Cost: 1N(t) := 1I + (6t - 3)M + 1S
1065 */
ecp_normalize_jac_many(const mbedtls_ecp_group * grp,mbedtls_ecp_point * T[],size_t t_len)1066 static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
1067 mbedtls_ecp_point *T[], size_t t_len )
1068 {
1069 int ret;
1070 size_t i;
1071 mbedtls_mpi *c, u, Zi, ZZi;
1072
1073 if( t_len < 2 )
1074 return( ecp_normalize_jac( grp, *T ) );
1075
1076 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
1077 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1078 {
1079 return mbedtls_internal_ecp_normalize_jac_many(grp, T, t_len);
1080 }
1081 #endif
1082
1083 if( ( c = mbedtls_calloc( t_len, sizeof( mbedtls_mpi ) ) ) == NULL )
1084 return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
1085
1086 mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
1087
1088 /*
1089 * c[i] = Z_0 * ... * Z_i
1090 */
1091 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) );
1092 for( i = 1; i < t_len; i++ )
1093 {
1094 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );
1095 MOD_MUL( c[i] );
1096 }
1097
1098 /*
1099 * u = 1 / (Z_0 * ... * Z_n) mod P
1100 */
1101 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[t_len-1], &grp->P ) );
1102
1103 for( i = t_len - 1; ; i-- )
1104 {
1105 /*
1106 * Zi = 1 / Z_i mod p
1107 * u = 1 / (Z_0 * ... * Z_i) mod P
1108 */
1109 if( i == 0 ) {
1110 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) );
1111 }
1112 else
1113 {
1114 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi );
1115 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u );
1116 }
1117
1118 /*
1119 * proceed as in normalize()
1120 */
1121 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
1122 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X );
1123 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y );
1124 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y );
1125
1126 /*
1127 * Post-precessing: reclaim some memory by shrinking coordinates
1128 * - not storing Z (always 1)
1129 * - shrinking other coordinates, but still keeping the same number of
1130 * limbs as P, as otherwise it will too likely be regrown too fast.
1131 */
1132 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) );
1133 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) );
1134 mbedtls_mpi_free( &T[i]->Z );
1135
1136 if( i == 0 )
1137 break;
1138 }
1139
1140 cleanup:
1141
1142 mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
1143 for( i = 0; i < t_len; i++ )
1144 mbedtls_mpi_free( &c[i] );
1145 mbedtls_free( c );
1146
1147 return( ret );
1148 }
1149
1150 /*
1151 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
1152 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
1153 */
ecp_safe_invert_jac(const mbedtls_ecp_group * grp,mbedtls_ecp_point * Q,unsigned char inv)1154 static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp,
1155 mbedtls_ecp_point *Q,
1156 unsigned char inv )
1157 {
1158 int ret;
1159 unsigned char nonzero;
1160 mbedtls_mpi mQY;
1161
1162 mbedtls_mpi_init( &mQY );
1163
1164 /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
1165 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) );
1166 nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0;
1167 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) );
1168
1169 cleanup:
1170 mbedtls_mpi_free( &mQY );
1171
1172 return( ret );
1173 }
1174
1175 /*
1176 * Point doubling R = 2 P, Jacobian coordinates
1177 *
1178 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
1179 *
1180 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR
1181 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.
1182 *
1183 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
1184 *
1185 * Cost: 1D := 3M + 4S (A == 0)
1186 * 4M + 4S (A == -3)
1187 * 3M + 6S + 1a otherwise
1188 */
ecp_double_jac(const mbedtls_ecp_group * grp,mbedtls_ecp_point * R,const mbedtls_ecp_point * P)1189 static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1190 const mbedtls_ecp_point *P )
1191 {
1192 int ret;
1193 mbedtls_mpi M, S, T, U;
1194
1195 #if defined(MBEDTLS_SELF_TEST)
1196 dbl_count++;
1197 #endif
1198
1199 #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
1200 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1201 {
1202 return mbedtls_internal_ecp_double_jac( grp, R, P );
1203 }
1204 #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */
1205
1206 mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U );
1207
1208 /* Special case for A = -3 */
1209 if( grp->A.p == NULL )
1210 {
1211 /* M = 3(X + Z^2)(X - Z^2) */
1212 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S );
1213 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T, &P->X, &S ) ); MOD_ADD( T );
1214 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U, &P->X, &S ) ); MOD_SUB( U );
1215 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &U ) ); MOD_MUL( S );
1216 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
1217 }
1218 else
1219 {
1220 /* M = 3.X^2 */
1221 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &P->X ) ); MOD_MUL( S );
1222 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
1223
1224 /* Optimize away for "koblitz" curves with A = 0 */
1225 if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 )
1226 {
1227 /* M += A.Z^4 */
1228 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S );
1229 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &S, &S ) ); MOD_MUL( T );
1230 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &grp->A ) ); MOD_MUL( S );
1231 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M, &M, &S ) ); MOD_ADD( M );
1232 }
1233 }
1234
1235 /* S = 4.X.Y^2 */
1236 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &P->Y, &P->Y ) ); MOD_MUL( T );
1237 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T, 1 ) ); MOD_ADD( T );
1238 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &T ) ); MOD_MUL( S );
1239 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S, 1 ) ); MOD_ADD( S );
1240
1241 /* U = 8.Y^4 */
1242 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &T, &T ) ); MOD_MUL( U );
1243 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U );
1244
1245 /* T = M^2 - 2.S */
1246 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &M, &M ) ); MOD_MUL( T );
1247 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T );
1248 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T );
1249
1250 /* S = M(S - T) - U */
1251 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &T ) ); MOD_SUB( S );
1252 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &S, &M ) ); MOD_MUL( S );
1253 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &U ) ); MOD_SUB( S );
1254
1255 /* U = 2.Y.Z */
1256 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &P->Y, &P->Z ) ); MOD_MUL( U );
1257 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U );
1258
1259 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) );
1260 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) );
1261 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) );
1262
1263 cleanup:
1264 mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U );
1265
1266 return( ret );
1267 }
1268
1269 /*
1270 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
1271 *
1272 * The coordinates of Q must be normalized (= affine),
1273 * but those of P don't need to. R is not normalized.
1274 *
1275 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
1276 * None of these cases can happen as intermediate step in ecp_mul_comb():
1277 * - at each step, P, Q and R are multiples of the base point, the factor
1278 * being less than its order, so none of them is zero;
1279 * - Q is an odd multiple of the base point, P an even multiple,
1280 * due to the choice of precomputed points in the modified comb method.
1281 * So branches for these cases do not leak secret information.
1282 *
1283 * We accept Q->Z being unset (saving memory in tables) as meaning 1.
1284 *
1285 * Cost: 1A := 8M + 3S
1286 */
ecp_add_mixed(const mbedtls_ecp_group * grp,mbedtls_ecp_point * R,const mbedtls_ecp_point * P,const mbedtls_ecp_point * Q)1287 static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1288 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
1289 {
1290 int ret;
1291 mbedtls_mpi T1, T2, T3, T4, X, Y, Z;
1292
1293 #if defined(MBEDTLS_SELF_TEST)
1294 add_count++;
1295 #endif
1296
1297 #if defined(MBEDTLS_ECP_ADD_MIXED_ALT)
1298 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1299 {
1300 return mbedtls_internal_ecp_add_mixed( grp, R, P, Q );
1301 }
1302 #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */
1303
1304 /*
1305 * Trivial cases: P == 0 or Q == 0 (case 1)
1306 */
1307 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
1308 return( mbedtls_ecp_copy( R, Q ) );
1309
1310 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 )
1311 return( mbedtls_ecp_copy( R, P ) );
1312
1313 /*
1314 * Make sure Q coordinates are normalized
1315 */
1316 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 )
1317 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1318
1319 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 );
1320 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1321
1322 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 );
1323 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 );
1324 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 );
1325 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 );
1326 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 );
1327 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 );
1328
1329 /* Special cases (2) and (3) */
1330 if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 )
1331 {
1332 if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 )
1333 {
1334 ret = ecp_double_jac( grp, R, P );
1335 goto cleanup;
1336 }
1337 else
1338 {
1339 ret = mbedtls_ecp_set_zero( R );
1340 goto cleanup;
1341 }
1342 }
1343
1344 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z );
1345 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 );
1346 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 );
1347 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 );
1348 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 );
1349 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X );
1350 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X );
1351 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X );
1352 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 );
1353 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 );
1354 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 );
1355 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y );
1356
1357 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) );
1358 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) );
1359 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) );
1360
1361 cleanup:
1362
1363 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 );
1364 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1365
1366 return( ret );
1367 }
1368
1369 /*
1370 * Randomize jacobian coordinates:
1371 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
1372 * This is sort of the reverse operation of ecp_normalize_jac().
1373 *
1374 * This countermeasure was first suggested in [2].
1375 */
ecp_randomize_jac(const mbedtls_ecp_group * grp,mbedtls_ecp_point * pt,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)1376 static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
1377 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1378 {
1379 int ret;
1380 mbedtls_mpi l, ll;
1381 size_t p_size;
1382 int count = 0;
1383
1384 #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
1385 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1386 {
1387 return mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng );
1388 }
1389 #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */
1390
1391 p_size = ( grp->pbits + 7 ) / 8;
1392 mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll );
1393
1394 /* Generate l such that 1 < l < p */
1395 do
1396 {
1397 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
1398
1399 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
1400 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
1401
1402 if( count++ > 10 )
1403 {
1404 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
1405 goto cleanup;
1406 }
1407 }
1408 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
1409
1410 /* Z = l * Z */
1411 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z );
1412
1413 /* X = l^2 * X */
1414 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll );
1415 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X );
1416
1417 /* Y = l^3 * Y */
1418 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll );
1419 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y );
1420
1421 cleanup:
1422 mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll );
1423
1424 return( ret );
1425 }
1426
1427 /*
1428 * Check and define parameters used by the comb method (see below for details)
1429 */
1430 #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7
1431 #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"
1432 #endif
1433
1434 /* d = ceil( n / w ) */
1435 #define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2
1436
1437 /* number of precomputed points */
1438 #define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) )
1439
1440 /*
1441 * Compute the representation of m that will be used with our comb method.
1442 *
1443 * The basic comb method is described in GECC 3.44 for example. We use a
1444 * modified version that provides resistance to SPA by avoiding zero
1445 * digits in the representation as in [3]. We modify the method further by
1446 * requiring that all K_i be odd, which has the small cost that our
1447 * representation uses one more K_i, due to carries.
1448 *
1449 * Also, for the sake of compactness, only the seven low-order bits of x[i]
1450 * are used to represent K_i, and the msb of x[i] encodes the the sign (s_i in
1451 * the paper): it is set if and only if if s_i == -1;
1452 *
1453 * Calling conventions:
1454 * - x is an array of size d + 1
1455 * - w is the size, ie number of teeth, of the comb, and must be between
1456 * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE)
1457 * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d
1458 * (the result will be incorrect if these assumptions are not satisfied)
1459 */
ecp_comb_fixed(unsigned char x[],size_t d,unsigned char w,const mbedtls_mpi * m)1460 static void ecp_comb_fixed( unsigned char x[], size_t d,
1461 unsigned char w, const mbedtls_mpi *m )
1462 {
1463 size_t i, j;
1464 unsigned char c, cc, adjust;
1465
1466 memset( x, 0, d+1 );
1467
1468 /* First get the classical comb values (except for x_d = 0) */
1469 for( i = 0; i < d; i++ )
1470 for( j = 0; j < w; j++ )
1471 x[i] |= mbedtls_mpi_get_bit( m, i + d * j ) << j;
1472
1473 /* Now make sure x_1 .. x_d are odd */
1474 c = 0;
1475 for( i = 1; i <= d; i++ )
1476 {
1477 /* Add carry and update it */
1478 cc = x[i] & c;
1479 x[i] = x[i] ^ c;
1480 c = cc;
1481
1482 /* Adjust if needed, avoiding branches */
1483 adjust = 1 - ( x[i] & 0x01 );
1484 c |= x[i] & ( x[i-1] * adjust );
1485 x[i] = x[i] ^ ( x[i-1] * adjust );
1486 x[i-1] |= adjust << 7;
1487 }
1488 }
1489
1490 /*
1491 * Precompute points for the comb method
1492 *
1493 * If i = i_{w-1} ... i_1 is the binary representation of i, then
1494 * T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P
1495 *
1496 * T must be able to hold 2^{w - 1} elements
1497 *
1498 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
1499 */
ecp_precompute_comb(const mbedtls_ecp_group * grp,mbedtls_ecp_point T[],const mbedtls_ecp_point * P,unsigned char w,size_t d)1500 static int ecp_precompute_comb( const mbedtls_ecp_group *grp,
1501 mbedtls_ecp_point T[], const mbedtls_ecp_point *P,
1502 unsigned char w, size_t d )
1503 {
1504 int ret;
1505 unsigned char i, k;
1506 size_t j;
1507 mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1];
1508
1509 /*
1510 * Set T[0] = P and
1511 * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
1512 */
1513 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) );
1514
1515 k = 0;
1516 for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 )
1517 {
1518 cur = T + i;
1519 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) );
1520 for( j = 0; j < d; j++ )
1521 MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) );
1522
1523 TT[k++] = cur;
1524 }
1525
1526 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1527
1528 /*
1529 * Compute the remaining ones using the minimal number of additions
1530 * Be careful to update T[2^l] only after using it!
1531 */
1532 k = 0;
1533 for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 )
1534 {
1535 j = i;
1536 while( j-- )
1537 {
1538 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
1539 TT[k++] = &T[i + j];
1540 }
1541 }
1542
1543 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1544
1545 cleanup:
1546
1547 return( ret );
1548 }
1549
1550 /*
1551 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
1552 */
ecp_select_comb(const mbedtls_ecp_group * grp,mbedtls_ecp_point * R,const mbedtls_ecp_point T[],unsigned char t_len,unsigned char i)1553 static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1554 const mbedtls_ecp_point T[], unsigned char t_len,
1555 unsigned char i )
1556 {
1557 int ret;
1558 unsigned char ii, j;
1559
1560 /* Ignore the "sign" bit and scale down */
1561 ii = ( i & 0x7Fu ) >> 1;
1562
1563 /* Read the whole table to thwart cache-based timing attacks */
1564 for( j = 0; j < t_len; j++ )
1565 {
1566 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) );
1567 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) );
1568 }
1569
1570 /* Safely invert result if i is "negative" */
1571 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
1572
1573 cleanup:
1574 return( ret );
1575 }
1576
1577 /*
1578 * Core multiplication algorithm for the (modified) comb method.
1579 * This part is actually common with the basic comb method (GECC 3.44)
1580 *
1581 * Cost: d A + d D + 1 R
1582 */
ecp_mul_comb_core(const mbedtls_ecp_group * grp,mbedtls_ecp_point * R,const mbedtls_ecp_point T[],unsigned char t_len,const unsigned char x[],size_t d,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)1583 static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1584 const mbedtls_ecp_point T[], unsigned char t_len,
1585 const unsigned char x[], size_t d,
1586 int (*f_rng)(void *, unsigned char *, size_t),
1587 void *p_rng )
1588 {
1589 int ret;
1590 mbedtls_ecp_point Txi;
1591 size_t i;
1592
1593 mbedtls_ecp_point_init( &Txi );
1594
1595 /* Start with a non-zero point and randomize its coordinates */
1596 i = d;
1597 MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) );
1598 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 1 ) );
1599 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
1600 if( f_rng != 0 )
1601 #endif
1602 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
1603
1604 while( i-- != 0 )
1605 {
1606 MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) );
1607 MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) );
1608 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
1609 }
1610
1611 cleanup:
1612
1613 mbedtls_ecp_point_free( &Txi );
1614
1615 return( ret );
1616 }
1617
1618 /*
1619 * Multiplication using the comb method,
1620 * for curves in short Weierstrass form
1621 */
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)1622 static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1623 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
1624 int (*f_rng)(void *, unsigned char *, size_t),
1625 void *p_rng )
1626 {
1627 int ret;
1628 unsigned char w, m_is_odd, p_eq_g, pre_len, i;
1629 size_t d;
1630 unsigned char k[COMB_MAX_D + 1];
1631 mbedtls_ecp_point *T;
1632 mbedtls_mpi M, mm;
1633
1634 mbedtls_mpi_init( &M );
1635 mbedtls_mpi_init( &mm );
1636
1637 /* we need N to be odd to trnaform m in an odd number, check now */
1638 if( mbedtls_mpi_get_bit( &grp->N, 0 ) != 1 )
1639 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1640
1641 /*
1642 * Minimize the number of multiplications, that is minimize
1643 * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
1644 * (see costs of the various parts, with 1S = 1M)
1645 */
1646 w = grp->nbits >= 384 ? 5 : 4;
1647
1648 /*
1649 * If P == G, pre-compute a bit more, since this may be re-used later.
1650 * Just adding one avoids upping the cost of the first mul too much,
1651 * and the memory cost too.
1652 */
1653 #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
1654 p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&
1655 mbedtls_mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 );
1656 if( p_eq_g )
1657 w++;
1658 #else
1659 p_eq_g = 0;
1660 #endif
1661
1662 /*
1663 * Make sure w is within bounds.
1664 * (The last test is useful only for very small curves in the test suite.)
1665 */
1666 if( w > MBEDTLS_ECP_WINDOW_SIZE )
1667 w = MBEDTLS_ECP_WINDOW_SIZE;
1668 if( w >= grp->nbits )
1669 w = 2;
1670
1671 /* Other sizes that depend on w */
1672 pre_len = 1U << ( w - 1 );
1673 d = ( grp->nbits + w - 1 ) / w;
1674
1675 /*
1676 * Prepare precomputed points: if P == G we want to
1677 * use grp->T if already initialized, or initialize it.
1678 */
1679 T = p_eq_g ? grp->T : NULL;
1680
1681 if( T == NULL )
1682 {
1683 T = mbedtls_calloc( pre_len, sizeof( mbedtls_ecp_point ) );
1684 if( T == NULL )
1685 {
1686 ret = MBEDTLS_ERR_ECP_ALLOC_FAILED;
1687 goto cleanup;
1688 }
1689
1690 MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) );
1691
1692 if( p_eq_g )
1693 {
1694 grp->T = T;
1695 grp->T_size = pre_len;
1696 }
1697 }
1698
1699 /*
1700 * Make sure M is odd (M = m or M = N - m, since N is odd)
1701 * using the fact that m * P = - (N - m) * P
1702 */
1703 m_is_odd = ( mbedtls_mpi_get_bit( m, 0 ) == 1 );
1704 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) );
1705 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N, m ) );
1706 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, ! m_is_odd ) );
1707
1708 /*
1709 * Go for comb multiplication, R = M * P
1710 */
1711 ecp_comb_fixed( k, d, w, &M );
1712 MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) );
1713
1714 /*
1715 * Now get m * P from M * P and normalize it
1716 */
1717 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) );
1718
1719 /*
1720 * Knowledge of the jacobian coordinates may leak the last few bits of the
1721 * scalar [1], and since our MPI implementation isn't constant-flow,
1722 * inversion (used for coordinate normalization) may leak the full value
1723 * of its input via side-channels [2].
1724 *
1725 * [1] https://eprint.iacr.org/2003/191
1726 * [2] https://eprint.iacr.org/2020/055
1727 *
1728 * Avoid the leak by randomizing coordinates before we normalize them.
1729 */
1730 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
1731 if( f_rng != 0 )
1732 #endif
1733 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
1734 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) );
1735
1736 cleanup:
1737
1738 /* There are two cases where T is not stored in grp:
1739 * - P != G
1740 * - An intermediate operation failed before setting grp->T
1741 * In either case, T must be freed.
1742 */
1743 if( T != NULL && T != grp->T )
1744 {
1745 for( i = 0; i < pre_len; i++ )
1746 mbedtls_ecp_point_free( &T[i] );
1747 mbedtls_free( T );
1748 }
1749
1750 mbedtls_mpi_free( &M );
1751 mbedtls_mpi_free( &mm );
1752
1753 if( ret != 0 )
1754 mbedtls_ecp_point_free( R );
1755
1756 return( ret );
1757 }
1758
1759 #endif /* ECP_SHORTWEIERSTRASS */
1760
1761 #if defined(ECP_MONTGOMERY)
1762 /*
1763 * For Montgomery curves, we do all the internal arithmetic in projective
1764 * coordinates. Import/export of points uses only the x coordinates, which is
1765 * internaly represented as X / Z.
1766 *
1767 * For scalar multiplication, we'll use a Montgomery ladder.
1768 */
1769
1770 /*
1771 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
1772 * Cost: 1M + 1I
1773 */
ecp_normalize_mxz(const mbedtls_ecp_group * grp,mbedtls_ecp_point * P)1774 static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P )
1775 {
1776 int ret;
1777
1778 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
1779 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1780 {
1781 return mbedtls_internal_ecp_normalize_mxz( grp, P );
1782 }
1783 #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */
1784
1785 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) );
1786 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X );
1787 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
1788
1789 cleanup:
1790 return( ret );
1791 }
1792
1793 /*
1794 * Randomize projective x/z coordinates:
1795 * (X, Z) -> (l X, l Z) for random l
1796 * This is sort of the reverse operation of ecp_normalize_mxz().
1797 *
1798 * This countermeasure was first suggested in [2].
1799 * Cost: 2M
1800 */
ecp_randomize_mxz(const mbedtls_ecp_group * grp,mbedtls_ecp_point * P,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)1801 static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P,
1802 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1803 {
1804 int ret;
1805 mbedtls_mpi l;
1806 size_t p_size;
1807 int count = 0;
1808
1809 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
1810 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1811 {
1812 return mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng );
1813 }
1814 #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */
1815
1816 p_size = ( grp->pbits + 7 ) / 8;
1817 mbedtls_mpi_init( &l );
1818
1819 /* Generate l such that 1 < l < p */
1820 do
1821 {
1822 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
1823
1824 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
1825 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
1826
1827 if( count++ > 10 )
1828 {
1829 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
1830 goto cleanup;
1831 }
1832 }
1833 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
1834
1835 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X );
1836 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z );
1837
1838 cleanup:
1839 mbedtls_mpi_free( &l );
1840
1841 return( ret );
1842 }
1843
1844 /*
1845 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
1846 * for Montgomery curves in x/z coordinates.
1847 *
1848 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
1849 * with
1850 * d = X1
1851 * P = (X2, Z2)
1852 * Q = (X3, Z3)
1853 * R = (X4, Z4)
1854 * S = (X5, Z5)
1855 * and eliminating temporary variables tO, ..., t4.
1856 *
1857 * Cost: 5M + 4S
1858 */
ecp_double_add_mxz(const mbedtls_ecp_group * grp,mbedtls_ecp_point * R,mbedtls_ecp_point * S,const mbedtls_ecp_point * P,const mbedtls_ecp_point * Q,const mbedtls_mpi * d)1859 static int ecp_double_add_mxz( const mbedtls_ecp_group *grp,
1860 mbedtls_ecp_point *R, mbedtls_ecp_point *S,
1861 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q,
1862 const mbedtls_mpi *d )
1863 {
1864 int ret;
1865 mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB;
1866
1867 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
1868 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1869 {
1870 return mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d );
1871 }
1872 #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */
1873
1874 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B );
1875 mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C );
1876 mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB );
1877
1878 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A );
1879 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA );
1880 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B );
1881 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB );
1882 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E );
1883 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C );
1884 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D );
1885 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA );
1886 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB );
1887 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X );
1888 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X );
1889 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z );
1890 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z );
1891 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z );
1892 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X );
1893 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z );
1894 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z );
1895 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z );
1896
1897 cleanup:
1898 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B );
1899 mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C );
1900 mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB );
1901
1902 return( ret );
1903 }
1904
1905 /*
1906 * Multiplication with Montgomery ladder in x/z coordinates,
1907 * for curves in Montgomery form
1908 */
ecp_mul_mxz(mbedtls_ecp_group * grp,mbedtls_ecp_point * R,const mbedtls_mpi * m,const mbedtls_ecp_point * P,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)1909 static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1910 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
1911 int (*f_rng)(void *, unsigned char *, size_t),
1912 void *p_rng )
1913 {
1914 int ret;
1915 size_t i;
1916 unsigned char b;
1917 mbedtls_ecp_point RP;
1918 mbedtls_mpi PX;
1919
1920 mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX );
1921
1922 /* Save PX and read from P before writing to R, in case P == R */
1923 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) );
1924 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) );
1925
1926 /* Set R to zero in modified x/z coordinates */
1927 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X, 1 ) );
1928 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) );
1929 mbedtls_mpi_free( &R->Y );
1930
1931 /* RP.X might be sligtly larger than P, so reduce it */
1932 MOD_ADD( RP.X );
1933
1934 /* Randomize coordinates of the starting point */
1935 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
1936 if( f_rng != NULL )
1937 #endif
1938 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
1939
1940 /* Loop invariant: R = result so far, RP = R + P */
1941 i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */
1942 while( i-- > 0 )
1943 {
1944 b = mbedtls_mpi_get_bit( m, i );
1945 /*
1946 * if (b) R = 2R + P else R = 2R,
1947 * which is:
1948 * if (b) double_add( RP, R, RP, R )
1949 * else double_add( R, RP, R, RP )
1950 * but using safe conditional swaps to avoid leaks
1951 */
1952 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );
1953 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
1954 MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
1955 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );
1956 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
1957 }
1958
1959 /*
1960 * Knowledge of the projective coordinates may leak the last few bits of the
1961 * scalar [1], and since our MPI implementation isn't constant-flow,
1962 * inversion (used for coordinate normalization) may leak the full value
1963 * of its input via side-channels [2].
1964 *
1965 * [1] https://eprint.iacr.org/2003/191
1966 * [2] https://eprint.iacr.org/2020/055
1967 *
1968 * Avoid the leak by randomizing coordinates before we normalize them.
1969 */
1970 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
1971 if( f_rng != NULL )
1972 #endif
1973 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, R, f_rng, p_rng ) );
1974
1975 MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) );
1976
1977 cleanup:
1978 mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX );
1979
1980 return( ret );
1981 }
1982
1983 #endif /* ECP_MONTGOMERY */
1984
1985 /*
1986 * Multiplication R = m * P
1987 */
mbedtls_ecp_mul(mbedtls_ecp_group * grp,mbedtls_ecp_point * R,const mbedtls_mpi * m,const mbedtls_ecp_point * P,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)1988 int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1989 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
1990 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1991 {
1992 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1993 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
1994 char is_grp_capable = 0;
1995 #endif
1996 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
1997 ecp_drbg_context drbg_ctx;
1998
1999 ecp_drbg_init( &drbg_ctx );
2000 #endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */
2001
2002 /* Common sanity checks */
2003 if( mbedtls_mpi_cmp_int( &P->Z, 1 ) != 0 )
2004 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
2005
2006 if( ( ret = mbedtls_ecp_check_privkey( grp, m ) ) != 0 ||
2007 ( ret = mbedtls_ecp_check_pubkey( grp, P ) ) != 0 )
2008 return( ret );
2009
2010 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2011 if( f_rng == NULL )
2012 {
2013 const size_t m_len = ( grp->nbits + 7 ) / 8;
2014 MBEDTLS_MPI_CHK( ecp_drbg_seed( &drbg_ctx, m, m_len ) );
2015 f_rng = &ecp_drbg_random;
2016 p_rng = &drbg_ctx;
2017 }
2018 #endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */
2019
2020 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2021 if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) )
2022 {
2023 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );
2024 }
2025 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
2026
2027 #if defined(ECP_MONTGOMERY)
2028 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
2029 ret = ecp_mul_mxz( grp, R, m, P, f_rng, p_rng );
2030 #endif
2031 #if defined(ECP_SHORTWEIERSTRASS)
2032 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
2033 ret = ecp_mul_comb( grp, R, m, P, f_rng, p_rng );
2034 #endif
2035
2036 #if defined(MBEDTLS_ECP_INTERNAL_ALT) || !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2037 cleanup:
2038 #endif
2039 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2040 if ( is_grp_capable )
2041 {
2042 mbedtls_internal_ecp_free( grp );
2043 }
2044 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
2045
2046 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2047 ecp_drbg_free( &drbg_ctx );
2048 #endif
2049
2050 return( ret );
2051 }
2052
2053 #if defined(ECP_SHORTWEIERSTRASS)
2054 /*
2055 * Check that an affine point is valid as a public key,
2056 * short weierstrass curves (SEC1 3.2.3.1)
2057 */
ecp_check_pubkey_sw(const mbedtls_ecp_group * grp,const mbedtls_ecp_point * pt)2058 static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
2059 {
2060 int ret;
2061 mbedtls_mpi YY, RHS;
2062
2063 /* pt coordinates must be normalized for our checks */
2064 if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 ||
2065 mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 ||
2066 mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 ||
2067 mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 )
2068 return( MBEDTLS_ERR_ECP_INVALID_KEY );
2069
2070 mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS );
2071
2072 /*
2073 * YY = Y^2
2074 * RHS = X (X^2 + A) + B = X^3 + A X + B
2075 */
2076 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY );
2077 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS );
2078
2079 /* Special case for A = -3 */
2080 if( grp->A.p == NULL )
2081 {
2082 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS );
2083 }
2084 else
2085 {
2086 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS );
2087 }
2088
2089 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS );
2090 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS );
2091
2092 if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 )
2093 ret = MBEDTLS_ERR_ECP_INVALID_KEY;
2094
2095 cleanup:
2096
2097 mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS );
2098
2099 return( ret );
2100 }
2101 #endif /* ECP_SHORTWEIERSTRASS */
2102
2103 /*
2104 * R = m * P with shortcuts for m == 1 and m == -1
2105 * NOT constant-time - ONLY for short Weierstrass!
2106 */
mbedtls_ecp_mul_shortcuts(mbedtls_ecp_group * grp,mbedtls_ecp_point * R,const mbedtls_mpi * m,const mbedtls_ecp_point * P)2107 static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp,
2108 mbedtls_ecp_point *R,
2109 const mbedtls_mpi *m,
2110 const mbedtls_ecp_point *P )
2111 {
2112 int ret;
2113
2114 if( mbedtls_mpi_cmp_int( m, 1 ) == 0 )
2115 {
2116 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
2117 }
2118 else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 )
2119 {
2120 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
2121 if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 )
2122 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) );
2123 }
2124 else
2125 {
2126 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, R, m, P, NULL, NULL ) );
2127 }
2128
2129 cleanup:
2130 return( ret );
2131 }
2132
2133 /*
2134 * Linear combination
2135 * NOT constant-time
2136 */
mbedtls_ecp_muladd(mbedtls_ecp_group * grp,mbedtls_ecp_point * R,const mbedtls_mpi * m,const mbedtls_ecp_point * P,const mbedtls_mpi * n,const mbedtls_ecp_point * Q)2137 int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2138 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2139 const mbedtls_mpi *n, const mbedtls_ecp_point *Q )
2140 {
2141 int ret;
2142 mbedtls_ecp_point mP;
2143 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2144 char is_grp_capable = 0;
2145 #endif
2146
2147 if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS )
2148 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
2149
2150 mbedtls_ecp_point_init( &mP );
2151
2152 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, &mP, m, P ) );
2153 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, R, n, Q ) );
2154
2155 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2156 if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) )
2157 {
2158 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );
2159 }
2160
2161 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
2162 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, &mP, R ) );
2163 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) );
2164
2165 cleanup:
2166
2167 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2168 if ( is_grp_capable )
2169 {
2170 mbedtls_internal_ecp_free( grp );
2171 }
2172
2173 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
2174 mbedtls_ecp_point_free( &mP );
2175
2176 return( ret );
2177 }
2178
2179
2180 #if defined(ECP_MONTGOMERY)
2181 /*
2182 * Check validity of a public key for Montgomery curves with x-only schemes
2183 */
ecp_check_pubkey_mx(const mbedtls_ecp_group * grp,const mbedtls_ecp_point * pt)2184 static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
2185 {
2186 /* [Curve25519 p. 5] Just check X is the correct number of bytes */
2187 if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 )
2188 return( MBEDTLS_ERR_ECP_INVALID_KEY );
2189
2190 return( 0 );
2191 }
2192 #endif /* ECP_MONTGOMERY */
2193
2194 /*
2195 * Check that a point is valid as a public key
2196 */
mbedtls_ecp_check_pubkey(const mbedtls_ecp_group * grp,const mbedtls_ecp_point * pt)2197 int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
2198 {
2199 /* Must use affine coordinates */
2200 if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 )
2201 return( MBEDTLS_ERR_ECP_INVALID_KEY );
2202
2203 #if defined(ECP_MONTGOMERY)
2204 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
2205 return( ecp_check_pubkey_mx( grp, pt ) );
2206 #endif
2207 #if defined(ECP_SHORTWEIERSTRASS)
2208 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
2209 return( ecp_check_pubkey_sw( grp, pt ) );
2210 #endif
2211 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
2212 }
2213
2214 /*
2215 * Check that an mbedtls_mpi is valid as a private key
2216 */
mbedtls_ecp_check_privkey(const mbedtls_ecp_group * grp,const mbedtls_mpi * d)2217 int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, const mbedtls_mpi *d )
2218 {
2219 #if defined(ECP_MONTGOMERY)
2220 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
2221 {
2222 /* see [Curve25519] page 5 */
2223 if( mbedtls_mpi_get_bit( d, 0 ) != 0 ||
2224 mbedtls_mpi_get_bit( d, 1 ) != 0 ||
2225 mbedtls_mpi_get_bit( d, 2 ) != 0 ||
2226 mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */
2227 return( MBEDTLS_ERR_ECP_INVALID_KEY );
2228 else
2229 return( 0 );
2230 }
2231 #endif /* ECP_MONTGOMERY */
2232 #if defined(ECP_SHORTWEIERSTRASS)
2233 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
2234 {
2235 /* see SEC1 3.2 */
2236 if( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
2237 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 )
2238 return( MBEDTLS_ERR_ECP_INVALID_KEY );
2239 else
2240 return( 0 );
2241 }
2242 #endif /* ECP_SHORTWEIERSTRASS */
2243
2244 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
2245 }
2246
2247 /*
2248 * Generate a private key
2249 */
mbedtls_ecp_gen_privkey(const mbedtls_ecp_group * grp,mbedtls_mpi * d,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2250 int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp,
2251 mbedtls_mpi *d,
2252 int (*f_rng)(void *, unsigned char *, size_t),
2253 void *p_rng )
2254 {
2255 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
2256 size_t n_size = ( grp->nbits + 7 ) / 8;
2257
2258 #if defined(ECP_MONTGOMERY)
2259 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
2260 {
2261 /* [M225] page 5 */
2262 size_t b;
2263
2264 do {
2265 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
2266 } while( mbedtls_mpi_bitlen( d ) == 0);
2267
2268 /* Make sure the most significant bit is nbits */
2269 b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */
2270 if( b > grp->nbits )
2271 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) );
2272 else
2273 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits, 1 ) );
2274
2275 /* Make sure the last three bits are unset */
2276 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) );
2277 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) );
2278 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) );
2279 }
2280 #endif /* ECP_MONTGOMERY */
2281
2282 #if defined(ECP_SHORTWEIERSTRASS)
2283 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
2284 {
2285 /* SEC1 3.2.1: Generate d such that 1 <= n < N */
2286 int count = 0;
2287 unsigned cmp = 0;
2288
2289 /*
2290 * Match the procedure given in RFC 6979 (deterministic ECDSA):
2291 * - use the same byte ordering;
2292 * - keep the leftmost nbits bits of the generated octet string;
2293 * - try until result is in the desired range.
2294 * This also avoids any biais, which is especially important for ECDSA.
2295 */
2296 do
2297 {
2298 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
2299 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) );
2300
2301 /*
2302 * Each try has at worst a probability 1/2 of failing (the msb has
2303 * a probability 1/2 of being 0, and then the result will be < N),
2304 * so after 30 tries failure probability is a most 2**(-30).
2305 *
2306 * For most curves, 1 try is enough with overwhelming probability,
2307 * since N starts with a lot of 1s in binary, but some curves
2308 * such as secp224k1 are actually very close to the worst case.
2309 */
2310 if( ++count > 30 )
2311 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
2312
2313 ret = mbedtls_mpi_lt_mpi_ct( d, &grp->N, &cmp );
2314 if( ret != 0 )
2315 {
2316 goto cleanup;
2317 }
2318 }
2319 while( mbedtls_mpi_cmp_int( d, 1 ) < 0 || cmp != 1 );
2320 }
2321 #endif /* ECP_SHORTWEIERSTRASS */
2322
2323 cleanup:
2324 return( ret );
2325 }
2326
2327 /*
2328 * Generate a keypair with configurable base point
2329 */
mbedtls_ecp_gen_keypair_base(mbedtls_ecp_group * grp,const mbedtls_ecp_point * G,mbedtls_mpi * d,mbedtls_ecp_point * Q,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2330 int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp,
2331 const mbedtls_ecp_point *G,
2332 mbedtls_mpi *d, mbedtls_ecp_point *Q,
2333 int (*f_rng)(void *, unsigned char *, size_t),
2334 void *p_rng )
2335 {
2336 int ret;
2337
2338 MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, d, f_rng, p_rng ) );
2339 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) );
2340
2341 cleanup:
2342 return( ret );
2343 }
2344
2345 /*
2346 * Generate key pair, wrapper for conventional base point
2347 */
mbedtls_ecp_gen_keypair(mbedtls_ecp_group * grp,mbedtls_mpi * d,mbedtls_ecp_point * Q,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2348 int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp,
2349 mbedtls_mpi *d, mbedtls_ecp_point *Q,
2350 int (*f_rng)(void *, unsigned char *, size_t),
2351 void *p_rng )
2352 {
2353 return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) );
2354 }
2355
2356 /*
2357 * Generate a keypair, prettier wrapper
2358 */
mbedtls_ecp_gen_key(mbedtls_ecp_group_id grp_id,mbedtls_ecp_keypair * key,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2359 int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
2360 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
2361 {
2362 int ret;
2363
2364 if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 )
2365 return( ret );
2366
2367 return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) );
2368 }
2369
2370 /*
2371 * Check a public-private key pair
2372 */
mbedtls_ecp_check_pub_priv(const mbedtls_ecp_keypair * pub,const mbedtls_ecp_keypair * prv)2373 int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv )
2374 {
2375 int ret;
2376 mbedtls_ecp_point Q;
2377 mbedtls_ecp_group grp;
2378
2379 if( pub->grp.id == MBEDTLS_ECP_DP_NONE ||
2380 pub->grp.id != prv->grp.id ||
2381 mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) ||
2382 mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) ||
2383 mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) )
2384 {
2385 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
2386 }
2387
2388 mbedtls_ecp_point_init( &Q );
2389 mbedtls_ecp_group_init( &grp );
2390
2391 /* mbedtls_ecp_mul() needs a non-const group... */
2392 mbedtls_ecp_group_copy( &grp, &prv->grp );
2393
2394 /* Also checks d is valid */
2395 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) );
2396
2397 if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) ||
2398 mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) ||
2399 mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) )
2400 {
2401 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
2402 goto cleanup;
2403 }
2404
2405 cleanup:
2406 mbedtls_ecp_point_free( &Q );
2407 mbedtls_ecp_group_free( &grp );
2408
2409 return( ret );
2410 }
2411
2412 #if defined(MBEDTLS_SELF_TEST)
2413
2414 #if defined(ECP_ONE_STEP_KDF)
2415 /*
2416 * There are no test vectors from NIST for the One-Step KDF in SP 800-56C,
2417 * but unofficial ones can be found at:
2418 * https://github.com/patrickfav/singlestep-kdf/wiki/NIST-SP-800-56C-Rev1:-Non-Official-Test-Vectors
2419 *
2420 * We only use the ones with empty fixedInfo, and for brevity's sake, only
2421 * 40-bytes output (with SHA-256 that's more than one block, and with SHA-512
2422 * less than one block).
2423 */
2424 #if defined(MBEDTLS_SHA512_C)
2425
2426 static const uint8_t test_kdf_z[16] = {
2427 0x3b, 0xa9, 0x79, 0xe9, 0xbc, 0x5e, 0x3e, 0xc7,
2428 0x61, 0x30, 0x36, 0xb6, 0xf5, 0x1c, 0xd5, 0xaa,
2429 };
2430 static const uint8_t test_kdf_out[40] = {
2431 0x3e, 0xf6, 0xda, 0xf9, 0x51, 0x60, 0x70, 0x5f,
2432 0xdf, 0x21, 0xcd, 0xab, 0xac, 0x25, 0x7b, 0x05,
2433 0xfe, 0xc1, 0xab, 0x7c, 0xc9, 0x68, 0x43, 0x25,
2434 0x8a, 0xfc, 0x40, 0x6e, 0x5b, 0xf7, 0x98, 0x27,
2435 0x10, 0xfa, 0x7b, 0x93, 0x52, 0xd4, 0x16, 0xaa,
2436 };
2437
2438 #elif defined(MBEDTLS_SHA256_C)
2439
2440 static const uint8_t test_kdf_z[16] = {
2441 0xc8, 0x3e, 0x35, 0x8e, 0x99, 0xa6, 0x89, 0xc6,
2442 0x7d, 0xb4, 0xfe, 0x39, 0xcf, 0x8f, 0x26, 0xe1,
2443 };
2444 static const uint8_t test_kdf_out[40] = {
2445 0x7d, 0xf6, 0x41, 0xf8, 0x3c, 0x47, 0xdc, 0x28,
2446 0x5f, 0x7f, 0xaa, 0xde, 0x05, 0x64, 0xd6, 0x25,
2447 0x00, 0x6a, 0x47, 0xd9, 0x1e, 0xa4, 0xa0, 0x8c,
2448 0xd7, 0xf7, 0x0c, 0x99, 0xaa, 0xa0, 0x72, 0x66,
2449 0x69, 0x0e, 0x25, 0xaa, 0xa1, 0x63, 0x14, 0x79,
2450 };
2451
2452 #endif
2453
ecp_kdf_self_test(void)2454 static int ecp_kdf_self_test( void )
2455 {
2456 int ret;
2457 ecp_drbg_context kdf_ctx;
2458 mbedtls_mpi scalar;
2459 uint8_t out[sizeof( test_kdf_out )];
2460
2461 ecp_drbg_init( &kdf_ctx );
2462 mbedtls_mpi_init( &scalar );
2463 memset( out, 0, sizeof( out ) );
2464
2465 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &scalar,
2466 test_kdf_z, sizeof( test_kdf_z ) ) );
2467
2468 MBEDTLS_MPI_CHK( ecp_drbg_seed( &kdf_ctx,
2469 &scalar, sizeof( test_kdf_z ) ) );
2470
2471 MBEDTLS_MPI_CHK( ecp_drbg_random( &kdf_ctx, out, sizeof( out ) ) );
2472
2473 if( memcmp( out, test_kdf_out, sizeof( out ) ) != 0 )
2474 ret = -1;
2475
2476 cleanup:
2477 ecp_drbg_free( &kdf_ctx );
2478 mbedtls_mpi_free( &scalar );
2479
2480 return( ret );
2481 }
2482 #endif /* ECP_ONE_STEP_KDF */
2483
2484 /*
2485 * Checkup routine
2486 */
mbedtls_ecp_self_test(int verbose)2487 int mbedtls_ecp_self_test( int verbose )
2488 {
2489 int ret;
2490 size_t i;
2491 mbedtls_ecp_group grp;
2492 mbedtls_ecp_point R, P;
2493 mbedtls_mpi m;
2494 unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
2495 /* exponents especially adapted for secp192r1 */
2496 const char *exponents[] =
2497 {
2498 "000000000000000000000000000000000000000000000001", /* one */
2499 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */
2500 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
2501 "400000000000000000000000000000000000000000000000", /* one and zeros */
2502 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
2503 "555555555555555555555555555555555555555555555555", /* 101010... */
2504 };
2505
2506 mbedtls_ecp_group_init( &grp );
2507 mbedtls_ecp_point_init( &R );
2508 mbedtls_ecp_point_init( &P );
2509 mbedtls_mpi_init( &m );
2510
2511 /* Use secp192r1 if available, or any available curve */
2512 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
2513 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) );
2514 #else
2515 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) );
2516 #endif
2517
2518 if( verbose != 0 )
2519 mbedtls_printf( " ECP test #1 (constant op_count, base point G): " );
2520
2521 /* Do a dummy multiplication first to trigger precomputation */
2522 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) );
2523 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) );
2524
2525 add_count = 0;
2526 dbl_count = 0;
2527 mul_count = 0;
2528 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
2529 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
2530
2531 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
2532 {
2533 add_c_prev = add_count;
2534 dbl_c_prev = dbl_count;
2535 mul_c_prev = mul_count;
2536 add_count = 0;
2537 dbl_count = 0;
2538 mul_count = 0;
2539
2540 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
2541 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
2542
2543 if( add_count != add_c_prev ||
2544 dbl_count != dbl_c_prev ||
2545 mul_count != mul_c_prev )
2546 {
2547 if( verbose != 0 )
2548 mbedtls_printf( "failed (%u)\n", (unsigned int) i );
2549
2550 ret = 1;
2551 goto cleanup;
2552 }
2553 }
2554
2555 if( verbose != 0 )
2556 mbedtls_printf( "passed\n" );
2557
2558 if( verbose != 0 )
2559 mbedtls_printf( " ECP test #2 (constant op_count, other point): " );
2560 /* We computed P = 2G last time, use it */
2561
2562 add_count = 0;
2563 dbl_count = 0;
2564 mul_count = 0;
2565 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
2566 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
2567
2568 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
2569 {
2570 add_c_prev = add_count;
2571 dbl_c_prev = dbl_count;
2572 mul_c_prev = mul_count;
2573 add_count = 0;
2574 dbl_count = 0;
2575 mul_count = 0;
2576
2577 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
2578 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
2579
2580 if( add_count != add_c_prev ||
2581 dbl_count != dbl_c_prev ||
2582 mul_count != mul_c_prev )
2583 {
2584 if( verbose != 0 )
2585 mbedtls_printf( "failed (%u)\n", (unsigned int) i );
2586
2587 ret = 1;
2588 goto cleanup;
2589 }
2590 }
2591
2592 if( verbose != 0 )
2593 mbedtls_printf( "passed\n" );
2594
2595 #if defined(ECP_ONE_STEP_KDF)
2596 if( verbose != 0 )
2597 mbedtls_printf( " ECP test #3 (internal KDF): " );
2598
2599 ret = ecp_kdf_self_test();
2600 if( ret != 0 )
2601 {
2602 if( verbose != 0 )
2603 mbedtls_printf( "failed\n" );
2604
2605 ret = 1;
2606 goto cleanup;
2607 }
2608
2609 if( verbose != 0 )
2610 mbedtls_printf( "passed\n" );
2611 #endif /* ECP_ONE_STEP_KDF */
2612
2613 cleanup:
2614
2615 if( ret < 0 && verbose != 0 )
2616 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
2617
2618 mbedtls_ecp_group_free( &grp );
2619 mbedtls_ecp_point_free( &R );
2620 mbedtls_ecp_point_free( &P );
2621 mbedtls_mpi_free( &m );
2622
2623 if( verbose != 0 )
2624 mbedtls_printf( "\n" );
2625
2626 return( ret );
2627 }
2628
2629 #endif /* MBEDTLS_SELF_TEST */
2630
2631 #endif /* !MBEDTLS_ECP_ALT */
2632
2633 #endif /* MBEDTLS_ECP_C */
2634