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