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 MBEDTLS_PUT_UINT16_BE( curve_info->tls_id, buf, 0 ); 1168 1169 return( 0 ); 1170 } 1171 1172 /* 1173 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi. 1174 * See the documentation of struct mbedtls_ecp_group. 1175 * 1176 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf. 1177 */ 1178 static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp ) 1179 { 1180 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1181 1182 if( grp->modp == NULL ) 1183 return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) ); 1184 1185 /* N->s < 0 is a much faster test, which fails only if N is 0 */ 1186 if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) || 1187 mbedtls_mpi_bitlen( N ) > 2 * grp->pbits ) 1188 { 1189 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 1190 } 1191 1192 MBEDTLS_MPI_CHK( grp->modp( N ) ); 1193 1194 /* N->s < 0 is a much faster test, which fails only if N is 0 */ 1195 while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) 1196 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) ); 1197 1198 while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 ) 1199 /* we known P, N and the result are positive */ 1200 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) ); 1201 1202 cleanup: 1203 return( ret ); 1204 } 1205 1206 /* 1207 * Fast mod-p functions expect their argument to be in the 0..p^2 range. 1208 * 1209 * In order to guarantee that, we need to ensure that operands of 1210 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will 1211 * bring the result back to this range. 1212 * 1213 * The following macros are shortcuts for doing that. 1214 */ 1215 1216 /* 1217 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi 1218 */ 1219 #if defined(MBEDTLS_SELF_TEST) 1220 #define INC_MUL_COUNT mul_count++; 1221 #else 1222 #define INC_MUL_COUNT 1223 #endif 1224 1225 #define MOD_MUL( N ) \ 1226 do \ 1227 { \ 1228 MBEDTLS_MPI_CHK( ecp_modp( &(N), grp ) ); \ 1229 INC_MUL_COUNT \ 1230 } while( 0 ) 1231 1232 static inline int mbedtls_mpi_mul_mod( const mbedtls_ecp_group *grp, 1233 mbedtls_mpi *X, 1234 const mbedtls_mpi *A, 1235 const mbedtls_mpi *B ) 1236 { 1237 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1238 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( X, A, B ) ); 1239 MOD_MUL( *X ); 1240 cleanup: 1241 return( ret ); 1242 } 1243 1244 /* 1245 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi 1246 * N->s < 0 is a very fast test, which fails only if N is 0 1247 */ 1248 #define MOD_SUB( N ) \ 1249 while( (N).s < 0 && mbedtls_mpi_cmp_int( &(N), 0 ) != 0 ) \ 1250 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &(N), &(N), &grp->P ) ) 1251 1252 #if ( defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) && \ 1253 !( defined(MBEDTLS_ECP_NO_FALLBACK) && \ 1254 defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) && \ 1255 defined(MBEDTLS_ECP_ADD_MIXED_ALT) ) ) || \ 1256 ( defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) && \ 1257 !( defined(MBEDTLS_ECP_NO_FALLBACK) && \ 1258 defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) ) ) 1259 static inline int mbedtls_mpi_sub_mod( const mbedtls_ecp_group *grp, 1260 mbedtls_mpi *X, 1261 const mbedtls_mpi *A, 1262 const mbedtls_mpi *B ) 1263 { 1264 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1265 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( X, A, B ) ); 1266 MOD_SUB( *X ); 1267 cleanup: 1268 return( ret ); 1269 } 1270 #endif /* All functions referencing mbedtls_mpi_sub_mod() are alt-implemented without fallback */ 1271 1272 /* 1273 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int. 1274 * We known P, N and the result are positive, so sub_abs is correct, and 1275 * a bit faster. 1276 */ 1277 #define MOD_ADD( N ) \ 1278 while( mbedtls_mpi_cmp_mpi( &(N), &grp->P ) >= 0 ) \ 1279 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &(N), &(N), &grp->P ) ) 1280 1281 static inline int mbedtls_mpi_add_mod( const mbedtls_ecp_group *grp, 1282 mbedtls_mpi *X, 1283 const mbedtls_mpi *A, 1284 const mbedtls_mpi *B ) 1285 { 1286 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1287 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, A, B ) ); 1288 MOD_ADD( *X ); 1289 cleanup: 1290 return( ret ); 1291 } 1292 1293 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) && \ 1294 !( defined(MBEDTLS_ECP_NO_FALLBACK) && \ 1295 defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) && \ 1296 defined(MBEDTLS_ECP_ADD_MIXED_ALT) ) 1297 static inline int mbedtls_mpi_shift_l_mod( const mbedtls_ecp_group *grp, 1298 mbedtls_mpi *X, 1299 size_t count ) 1300 { 1301 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1302 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( X, count ) ); 1303 MOD_ADD( *X ); 1304 cleanup: 1305 return( ret ); 1306 } 1307 #endif /* All functions referencing mbedtls_mpi_shift_l_mod() are alt-implemented without fallback */ 1308 1309 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 1310 /* 1311 * For curves in short Weierstrass form, we do all the internal operations in 1312 * Jacobian coordinates. 1313 * 1314 * For multiplication, we'll use a comb method with countermeasures against 1315 * SPA, hence timing attacks. 1316 */ 1317 1318 /* 1319 * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1) 1320 * Cost: 1N := 1I + 3M + 1S 1321 */ 1322 static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt ) 1323 { 1324 if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 ) 1325 return( 0 ); 1326 1327 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) 1328 if( mbedtls_internal_ecp_grp_capable( grp ) ) 1329 return( mbedtls_internal_ecp_normalize_jac( grp, pt ) ); 1330 #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */ 1331 1332 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) 1333 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 1334 #else 1335 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1336 mbedtls_mpi Zi, ZZi; 1337 mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi ); 1338 1339 /* 1340 * X = X / Z^2 mod p 1341 */ 1342 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z, &grp->P ) ); 1343 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ZZi, &Zi, &Zi ) ); 1344 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->X, &pt->X, &ZZi ) ); 1345 1346 /* 1347 * Y = Y / Z^3 mod p 1348 */ 1349 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y, &pt->Y, &ZZi ) ); 1350 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y, &pt->Y, &Zi ) ); 1351 1352 /* 1353 * Z = 1 1354 */ 1355 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) ); 1356 1357 cleanup: 1358 1359 mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi ); 1360 1361 return( ret ); 1362 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) */ 1363 } 1364 1365 /* 1366 * Normalize jacobian coordinates of an array of (pointers to) points, 1367 * using Montgomery's trick to perform only one inversion mod P. 1368 * (See for example Cohen's "A Course in Computational Algebraic Number 1369 * Theory", Algorithm 10.3.4.) 1370 * 1371 * Warning: fails (returning an error) if one of the points is zero! 1372 * This should never happen, see choice of w in ecp_mul_comb(). 1373 * 1374 * Cost: 1N(t) := 1I + (6t - 3)M + 1S 1375 */ 1376 static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp, 1377 mbedtls_ecp_point *T[], size_t T_size ) 1378 { 1379 if( T_size < 2 ) 1380 return( ecp_normalize_jac( grp, *T ) ); 1381 1382 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) 1383 if( mbedtls_internal_ecp_grp_capable( grp ) ) 1384 return( mbedtls_internal_ecp_normalize_jac_many( grp, T, T_size ) ); 1385 #endif 1386 1387 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) 1388 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 1389 #else 1390 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1391 size_t i; 1392 mbedtls_mpi *c, u, Zi, ZZi; 1393 1394 if( ( c = mbedtls_calloc( T_size, sizeof( mbedtls_mpi ) ) ) == NULL ) 1395 return( MBEDTLS_ERR_ECP_ALLOC_FAILED ); 1396 1397 for( i = 0; i < T_size; i++ ) 1398 mbedtls_mpi_init( &c[i] ); 1399 1400 mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi ); 1401 1402 /* 1403 * c[i] = Z_0 * ... * Z_i 1404 */ 1405 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) ); 1406 for( i = 1; i < T_size; i++ ) 1407 { 1408 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &c[i], &c[i-1], &T[i]->Z ) ); 1409 } 1410 1411 /* 1412 * u = 1 / (Z_0 * ... * Z_n) mod P 1413 */ 1414 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[T_size-1], &grp->P ) ); 1415 1416 for( i = T_size - 1; ; i-- ) 1417 { 1418 /* 1419 * Zi = 1 / Z_i mod p 1420 * u = 1 / (Z_0 * ... * Z_i) mod P 1421 */ 1422 if( i == 0 ) { 1423 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) ); 1424 } 1425 else 1426 { 1427 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &Zi, &u, &c[i-1] ) ); 1428 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &u, &u, &T[i]->Z ) ); 1429 } 1430 1431 /* 1432 * proceed as in normalize() 1433 */ 1434 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ZZi, &Zi, &Zi ) ); 1435 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T[i]->X, &T[i]->X, &ZZi ) ); 1436 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T[i]->Y, &T[i]->Y, &ZZi ) ); 1437 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T[i]->Y, &T[i]->Y, &Zi ) ); 1438 1439 /* 1440 * Post-precessing: reclaim some memory by shrinking coordinates 1441 * - not storing Z (always 1) 1442 * - shrinking other coordinates, but still keeping the same number of 1443 * limbs as P, as otherwise it will too likely be regrown too fast. 1444 */ 1445 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) ); 1446 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) ); 1447 mbedtls_mpi_free( &T[i]->Z ); 1448 1449 if( i == 0 ) 1450 break; 1451 } 1452 1453 cleanup: 1454 1455 mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi ); 1456 for( i = 0; i < T_size; i++ ) 1457 mbedtls_mpi_free( &c[i] ); 1458 mbedtls_free( c ); 1459 1460 return( ret ); 1461 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) */ 1462 } 1463 1464 /* 1465 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak. 1466 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid 1467 */ 1468 static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp, 1469 mbedtls_ecp_point *Q, 1470 unsigned char inv ) 1471 { 1472 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1473 unsigned char nonzero; 1474 mbedtls_mpi mQY; 1475 1476 mbedtls_mpi_init( &mQY ); 1477 1478 /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */ 1479 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) ); 1480 nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0; 1481 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) ); 1482 1483 cleanup: 1484 mbedtls_mpi_free( &mQY ); 1485 1486 return( ret ); 1487 } 1488 1489 /* 1490 * Point doubling R = 2 P, Jacobian coordinates 1491 * 1492 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 . 1493 * 1494 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR 1495 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring. 1496 * 1497 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }. 1498 * 1499 * Cost: 1D := 3M + 4S (A == 0) 1500 * 4M + 4S (A == -3) 1501 * 3M + 6S + 1a otherwise 1502 */ 1503 static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1504 const mbedtls_ecp_point *P ) 1505 { 1506 #if defined(MBEDTLS_SELF_TEST) 1507 dbl_count++; 1508 #endif 1509 1510 #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) 1511 if( mbedtls_internal_ecp_grp_capable( grp ) ) 1512 return( mbedtls_internal_ecp_double_jac( grp, R, P ) ); 1513 #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */ 1514 1515 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) 1516 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 1517 #else 1518 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1519 mbedtls_mpi M, S, T, U; 1520 1521 mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U ); 1522 1523 /* Special case for A = -3 */ 1524 if( grp->A.p == NULL ) 1525 { 1526 /* M = 3(X + Z^2)(X - Z^2) */ 1527 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->Z, &P->Z ) ); 1528 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &T, &P->X, &S ) ); 1529 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &U, &P->X, &S ) ); 1530 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &T, &U ) ); 1531 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); 1532 } 1533 else 1534 { 1535 /* M = 3.X^2 */ 1536 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->X, &P->X ) ); 1537 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); 1538 1539 /* Optimize away for "koblitz" curves with A = 0 */ 1540 if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 ) 1541 { 1542 /* M += A.Z^4 */ 1543 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->Z, &P->Z ) ); 1544 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T, &S, &S ) ); 1545 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &T, &grp->A ) ); 1546 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &M, &M, &S ) ); 1547 } 1548 } 1549 1550 /* S = 4.X.Y^2 */ 1551 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T, &P->Y, &P->Y ) ); 1552 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &T, 1 ) ); 1553 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &P->X, &T ) ); 1554 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &S, 1 ) ); 1555 1556 /* U = 8.Y^4 */ 1557 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &U, &T, &T ) ); 1558 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &U, 1 ) ); 1559 1560 /* T = M^2 - 2.S */ 1561 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T, &M, &M ) ); 1562 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T, &T, &S ) ); 1563 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T, &T, &S ) ); 1564 1565 /* S = M(S - T) - U */ 1566 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &S, &S, &T ) ); 1567 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S, &S, &M ) ); 1568 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &S, &S, &U ) ); 1569 1570 /* U = 2.Y.Z */ 1571 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &U, &P->Y, &P->Z ) ); 1572 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &U, 1 ) ); 1573 1574 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) ); 1575 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) ); 1576 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) ); 1577 1578 cleanup: 1579 mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U ); 1580 1581 return( ret ); 1582 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) */ 1583 } 1584 1585 /* 1586 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22) 1587 * 1588 * The coordinates of Q must be normalized (= affine), 1589 * but those of P don't need to. R is not normalized. 1590 * 1591 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q. 1592 * None of these cases can happen as intermediate step in ecp_mul_comb(): 1593 * - at each step, P, Q and R are multiples of the base point, the factor 1594 * being less than its order, so none of them is zero; 1595 * - Q is an odd multiple of the base point, P an even multiple, 1596 * due to the choice of precomputed points in the modified comb method. 1597 * So branches for these cases do not leak secret information. 1598 * 1599 * We accept Q->Z being unset (saving memory in tables) as meaning 1. 1600 * 1601 * Cost: 1A := 8M + 3S 1602 */ 1603 static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1604 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q ) 1605 { 1606 #if defined(MBEDTLS_SELF_TEST) 1607 add_count++; 1608 #endif 1609 1610 #if defined(MBEDTLS_ECP_ADD_MIXED_ALT) 1611 if( mbedtls_internal_ecp_grp_capable( grp ) ) 1612 return( mbedtls_internal_ecp_add_mixed( grp, R, P, Q ) ); 1613 #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */ 1614 1615 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_ADD_MIXED_ALT) 1616 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 1617 #else 1618 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1619 mbedtls_mpi T1, T2, T3, T4, X, Y, Z; 1620 1621 /* 1622 * Trivial cases: P == 0 or Q == 0 (case 1) 1623 */ 1624 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 ) 1625 return( mbedtls_ecp_copy( R, Q ) ); 1626 1627 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 ) 1628 return( mbedtls_ecp_copy( R, P ) ); 1629 1630 /* 1631 * Make sure Q coordinates are normalized 1632 */ 1633 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 ) 1634 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 1635 1636 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 ); 1637 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z ); 1638 1639 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T1, &P->Z, &P->Z ) ); 1640 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T2, &T1, &P->Z ) ); 1641 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T1, &T1, &Q->X ) ); 1642 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T2, &T2, &Q->Y ) ); 1643 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T1, &T1, &P->X ) ); 1644 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T2, &T2, &P->Y ) ); 1645 1646 /* Special cases (2) and (3) */ 1647 if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 ) 1648 { 1649 if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 ) 1650 { 1651 ret = ecp_double_jac( grp, R, P ); 1652 goto cleanup; 1653 } 1654 else 1655 { 1656 ret = mbedtls_ecp_set_zero( R ); 1657 goto cleanup; 1658 } 1659 } 1660 1661 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &Z, &P->Z, &T1 ) ); 1662 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3, &T1, &T1 ) ); 1663 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T4, &T3, &T1 ) ); 1664 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3, &T3, &P->X ) ); 1665 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &T3 ) ); 1666 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &T1, 1 ) ); 1667 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &X, &T2, &T2 ) ); 1668 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &X, &X, &T1 ) ); 1669 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &X, &X, &T4 ) ); 1670 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T3, &T3, &X ) ); 1671 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3, &T3, &T2 ) ); 1672 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T4, &T4, &P->Y ) ); 1673 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &Y, &T3, &T4 ) ); 1674 1675 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) ); 1676 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) ); 1677 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) ); 1678 1679 cleanup: 1680 1681 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 ); 1682 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z ); 1683 1684 return( ret ); 1685 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_ADD_MIXED_ALT) */ 1686 } 1687 1688 /* 1689 * Randomize jacobian coordinates: 1690 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l 1691 * This is sort of the reverse operation of ecp_normalize_jac(). 1692 * 1693 * This countermeasure was first suggested in [2]. 1694 */ 1695 static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, 1696 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 1697 { 1698 #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) 1699 if( mbedtls_internal_ecp_grp_capable( grp ) ) 1700 return( mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng ) ); 1701 #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */ 1702 1703 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) 1704 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 1705 #else 1706 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1707 mbedtls_mpi l, ll; 1708 1709 mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll ); 1710 1711 /* Generate l such that 1 < l < p */ 1712 MBEDTLS_MPI_CHK( mbedtls_mpi_random( &l, 2, &grp->P, f_rng, p_rng ) ); 1713 1714 /* Z = l * Z */ 1715 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Z, &pt->Z, &l ) ); 1716 1717 /* X = l^2 * X */ 1718 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ll, &l, &l ) ); 1719 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->X, &pt->X, &ll ) ); 1720 1721 /* Y = l^3 * Y */ 1722 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ll, &ll, &l ) ); 1723 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y, &pt->Y, &ll ) ); 1724 1725 cleanup: 1726 mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll ); 1727 1728 if( ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ) 1729 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED; 1730 return( ret ); 1731 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) */ 1732 } 1733 1734 /* 1735 * Check and define parameters used by the comb method (see below for details) 1736 */ 1737 #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7 1738 #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds" 1739 #endif 1740 1741 /* d = ceil( n / w ) */ 1742 #define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2 1743 1744 /* number of precomputed points */ 1745 #define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) ) 1746 1747 /* 1748 * Compute the representation of m that will be used with our comb method. 1749 * 1750 * The basic comb method is described in GECC 3.44 for example. We use a 1751 * modified version that provides resistance to SPA by avoiding zero 1752 * digits in the representation as in [3]. We modify the method further by 1753 * requiring that all K_i be odd, which has the small cost that our 1754 * representation uses one more K_i, due to carries, but saves on the size of 1755 * the precomputed table. 1756 * 1757 * Summary of the comb method and its modifications: 1758 * 1759 * - The goal is to compute m*P for some w*d-bit integer m. 1760 * 1761 * - The basic comb method splits m into the w-bit integers 1762 * x[0] .. x[d-1] where x[i] consists of the bits in m whose 1763 * index has residue i modulo d, and computes m * P as 1764 * S[x[0]] + 2 * S[x[1]] + .. + 2^(d-1) S[x[d-1]], where 1765 * S[i_{w-1} .. i_0] := i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + i_0 P. 1766 * 1767 * - If it happens that, say, x[i+1]=0 (=> S[x[i+1]]=0), one can replace the sum by 1768 * .. + 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]] .., 1769 * thereby successively converting it into a form where all summands 1770 * are nonzero, at the cost of negative summands. This is the basic idea of [3]. 1771 * 1772 * - More generally, even if x[i+1] != 0, we can first transform the sum as 1773 * .. - 2^i S[x[i]] + 2^{i+1} ( S[x[i]] + S[x[i+1]] ) + 2^{i+2} S[x[i+2]] .., 1774 * and then replace S[x[i]] + S[x[i+1]] = S[x[i] ^ x[i+1]] + 2 S[x[i] & x[i+1]]. 1775 * Performing and iterating this procedure for those x[i] that are even 1776 * (keeping track of carry), we can transform the original sum into one of the form 1777 * S[x'[0]] +- 2 S[x'[1]] +- .. +- 2^{d-1} S[x'[d-1]] + 2^d S[x'[d]] 1778 * with all x'[i] odd. It is therefore only necessary to know S at odd indices, 1779 * which is why we are only computing half of it in the first place in 1780 * ecp_precompute_comb and accessing it with index abs(i) / 2 in ecp_select_comb. 1781 * 1782 * - For the sake of compactness, only the seven low-order bits of x[i] 1783 * are used to represent its absolute value (K_i in the paper), and the msb 1784 * of x[i] encodes the sign (s_i in the paper): it is set if and only if 1785 * if s_i == -1; 1786 * 1787 * Calling conventions: 1788 * - x is an array of size d + 1 1789 * - w is the size, ie number of teeth, of the comb, and must be between 1790 * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE) 1791 * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d 1792 * (the result will be incorrect if these assumptions are not satisfied) 1793 */ 1794 static void ecp_comb_recode_core( unsigned char x[], size_t d, 1795 unsigned char w, const mbedtls_mpi *m ) 1796 { 1797 size_t i, j; 1798 unsigned char c, cc, adjust; 1799 1800 memset( x, 0, d+1 ); 1801 1802 /* First get the classical comb values (except for x_d = 0) */ 1803 for( i = 0; i < d; i++ ) 1804 for( j = 0; j < w; j++ ) 1805 x[i] |= mbedtls_mpi_get_bit( m, i + d * j ) << j; 1806 1807 /* Now make sure x_1 .. x_d are odd */ 1808 c = 0; 1809 for( i = 1; i <= d; i++ ) 1810 { 1811 /* Add carry and update it */ 1812 cc = x[i] & c; 1813 x[i] = x[i] ^ c; 1814 c = cc; 1815 1816 /* Adjust if needed, avoiding branches */ 1817 adjust = 1 - ( x[i] & 0x01 ); 1818 c |= x[i] & ( x[i-1] * adjust ); 1819 x[i] = x[i] ^ ( x[i-1] * adjust ); 1820 x[i-1] |= adjust << 7; 1821 } 1822 } 1823 1824 /* 1825 * Precompute points for the adapted comb method 1826 * 1827 * Assumption: T must be able to hold 2^{w - 1} elements. 1828 * 1829 * Operation: If i = i_{w-1} ... i_1 is the binary representation of i, 1830 * sets T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P. 1831 * 1832 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1) 1833 * 1834 * Note: Even comb values (those where P would be omitted from the 1835 * sum defining T[i] above) are not needed in our adaption 1836 * the comb method. See ecp_comb_recode_core(). 1837 * 1838 * This function currently works in four steps: 1839 * (1) [dbl] Computation of intermediate T[i] for 2-power values of i 1840 * (2) [norm_dbl] Normalization of coordinates of these T[i] 1841 * (3) [add] Computation of all T[i] 1842 * (4) [norm_add] Normalization of all T[i] 1843 * 1844 * Step 1 can be interrupted but not the others; together with the final 1845 * coordinate normalization they are the largest steps done at once, depending 1846 * on the window size. Here are operation counts for P-256: 1847 * 1848 * step (2) (3) (4) 1849 * w = 5 142 165 208 1850 * w = 4 136 77 160 1851 * w = 3 130 33 136 1852 * w = 2 124 11 124 1853 * 1854 * So if ECC operations are blocking for too long even with a low max_ops 1855 * value, it's useful to set MBEDTLS_ECP_WINDOW_SIZE to a lower value in order 1856 * to minimize maximum blocking time. 1857 */ 1858 static int ecp_precompute_comb( const mbedtls_ecp_group *grp, 1859 mbedtls_ecp_point T[], const mbedtls_ecp_point *P, 1860 unsigned char w, size_t d, 1861 mbedtls_ecp_restart_ctx *rs_ctx ) 1862 { 1863 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1864 unsigned char i; 1865 size_t j = 0; 1866 const unsigned char T_size = 1U << ( w - 1 ); 1867 mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1]; 1868 1869 #if defined(MBEDTLS_ECP_RESTARTABLE) 1870 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1871 { 1872 if( rs_ctx->rsm->state == ecp_rsm_pre_dbl ) 1873 goto dbl; 1874 if( rs_ctx->rsm->state == ecp_rsm_pre_norm_dbl ) 1875 goto norm_dbl; 1876 if( rs_ctx->rsm->state == ecp_rsm_pre_add ) 1877 goto add; 1878 if( rs_ctx->rsm->state == ecp_rsm_pre_norm_add ) 1879 goto norm_add; 1880 } 1881 #else 1882 (void) rs_ctx; 1883 #endif 1884 1885 #if defined(MBEDTLS_ECP_RESTARTABLE) 1886 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1887 { 1888 rs_ctx->rsm->state = ecp_rsm_pre_dbl; 1889 1890 /* initial state for the loop */ 1891 rs_ctx->rsm->i = 0; 1892 } 1893 1894 dbl: 1895 #endif 1896 /* 1897 * Set T[0] = P and 1898 * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value) 1899 */ 1900 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) ); 1901 1902 #if defined(MBEDTLS_ECP_RESTARTABLE) 1903 if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0 ) 1904 j = rs_ctx->rsm->i; 1905 else 1906 #endif 1907 j = 0; 1908 1909 for( ; j < d * ( w - 1 ); j++ ) 1910 { 1911 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL ); 1912 1913 i = 1U << ( j / d ); 1914 cur = T + i; 1915 1916 if( j % d == 0 ) 1917 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) ); 1918 1919 MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) ); 1920 } 1921 1922 #if defined(MBEDTLS_ECP_RESTARTABLE) 1923 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1924 rs_ctx->rsm->state = ecp_rsm_pre_norm_dbl; 1925 1926 norm_dbl: 1927 #endif 1928 /* 1929 * Normalize current elements in T. As T has holes, 1930 * use an auxiliary array of pointers to elements in T. 1931 */ 1932 j = 0; 1933 for( i = 1; i < T_size; i <<= 1 ) 1934 TT[j++] = T + i; 1935 1936 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 ); 1937 1938 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) ); 1939 1940 #if defined(MBEDTLS_ECP_RESTARTABLE) 1941 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1942 rs_ctx->rsm->state = ecp_rsm_pre_add; 1943 1944 add: 1945 #endif 1946 /* 1947 * Compute the remaining ones using the minimal number of additions 1948 * Be careful to update T[2^l] only after using it! 1949 */ 1950 MBEDTLS_ECP_BUDGET( ( T_size - 1 ) * MBEDTLS_ECP_OPS_ADD ); 1951 1952 for( i = 1; i < T_size; i <<= 1 ) 1953 { 1954 j = i; 1955 while( j-- ) 1956 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) ); 1957 } 1958 1959 #if defined(MBEDTLS_ECP_RESTARTABLE) 1960 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1961 rs_ctx->rsm->state = ecp_rsm_pre_norm_add; 1962 1963 norm_add: 1964 #endif 1965 /* 1966 * Normalize final elements in T. Even though there are no holes now, we 1967 * still need the auxiliary array for homogeneity with the previous 1968 * call. Also, skip T[0] which is already normalised, being a copy of P. 1969 */ 1970 for( j = 0; j + 1 < T_size; j++ ) 1971 TT[j] = T + j + 1; 1972 1973 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 ); 1974 1975 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) ); 1976 1977 cleanup: 1978 #if defined(MBEDTLS_ECP_RESTARTABLE) 1979 if( rs_ctx != NULL && rs_ctx->rsm != NULL && 1980 ret == MBEDTLS_ERR_ECP_IN_PROGRESS ) 1981 { 1982 if( rs_ctx->rsm->state == ecp_rsm_pre_dbl ) 1983 rs_ctx->rsm->i = j; 1984 } 1985 #endif 1986 1987 return( ret ); 1988 } 1989 1990 /* 1991 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ] 1992 * 1993 * See ecp_comb_recode_core() for background 1994 */ 1995 static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1996 const mbedtls_ecp_point T[], unsigned char T_size, 1997 unsigned char i ) 1998 { 1999 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2000 unsigned char ii, j; 2001 2002 /* Ignore the "sign" bit and scale down */ 2003 ii = ( i & 0x7Fu ) >> 1; 2004 2005 /* Read the whole table to thwart cache-based timing attacks */ 2006 for( j = 0; j < T_size; j++ ) 2007 { 2008 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) ); 2009 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) ); 2010 } 2011 2012 /* Safely invert result if i is "negative" */ 2013 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) ); 2014 2015 cleanup: 2016 return( ret ); 2017 } 2018 2019 /* 2020 * Core multiplication algorithm for the (modified) comb method. 2021 * This part is actually common with the basic comb method (GECC 3.44) 2022 * 2023 * Cost: d A + d D + 1 R 2024 */ 2025 static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2026 const mbedtls_ecp_point T[], unsigned char T_size, 2027 const unsigned char x[], size_t d, 2028 int (*f_rng)(void *, unsigned char *, size_t), 2029 void *p_rng, 2030 mbedtls_ecp_restart_ctx *rs_ctx ) 2031 { 2032 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2033 mbedtls_ecp_point Txi; 2034 size_t i; 2035 2036 mbedtls_ecp_point_init( &Txi ); 2037 2038 #if !defined(MBEDTLS_ECP_RESTARTABLE) 2039 (void) rs_ctx; 2040 #endif 2041 2042 #if defined(MBEDTLS_ECP_RESTARTABLE) 2043 if( rs_ctx != NULL && rs_ctx->rsm != NULL && 2044 rs_ctx->rsm->state != ecp_rsm_comb_core ) 2045 { 2046 rs_ctx->rsm->i = 0; 2047 rs_ctx->rsm->state = ecp_rsm_comb_core; 2048 } 2049 2050 /* new 'if' instead of nested for the sake of the 'else' branch */ 2051 if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0 ) 2052 { 2053 /* restore current index (R already pointing to rs_ctx->rsm->R) */ 2054 i = rs_ctx->rsm->i; 2055 } 2056 else 2057 #endif 2058 { 2059 /* Start with a non-zero point and randomize its coordinates */ 2060 i = d; 2061 MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, T_size, x[i] ) ); 2062 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 1 ) ); 2063 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2064 if( f_rng != 0 ) 2065 #endif 2066 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) ); 2067 } 2068 2069 while( i != 0 ) 2070 { 2071 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD ); 2072 --i; 2073 2074 MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) ); 2075 MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, T_size, x[i] ) ); 2076 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) ); 2077 } 2078 2079 cleanup: 2080 2081 mbedtls_ecp_point_free( &Txi ); 2082 2083 #if defined(MBEDTLS_ECP_RESTARTABLE) 2084 if( rs_ctx != NULL && rs_ctx->rsm != NULL && 2085 ret == MBEDTLS_ERR_ECP_IN_PROGRESS ) 2086 { 2087 rs_ctx->rsm->i = i; 2088 /* no need to save R, already pointing to rs_ctx->rsm->R */ 2089 } 2090 #endif 2091 2092 return( ret ); 2093 } 2094 2095 /* 2096 * Recode the scalar to get constant-time comb multiplication 2097 * 2098 * As the actual scalar recoding needs an odd scalar as a starting point, 2099 * this wrapper ensures that by replacing m by N - m if necessary, and 2100 * informs the caller that the result of multiplication will be negated. 2101 * 2102 * This works because we only support large prime order for Short Weierstrass 2103 * curves, so N is always odd hence either m or N - m is. 2104 * 2105 * See ecp_comb_recode_core() for background. 2106 */ 2107 static int ecp_comb_recode_scalar( const mbedtls_ecp_group *grp, 2108 const mbedtls_mpi *m, 2109 unsigned char k[COMB_MAX_D + 1], 2110 size_t d, 2111 unsigned char w, 2112 unsigned char *parity_trick ) 2113 { 2114 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2115 mbedtls_mpi M, mm; 2116 2117 mbedtls_mpi_init( &M ); 2118 mbedtls_mpi_init( &mm ); 2119 2120 /* N is always odd (see above), just make extra sure */ 2121 if( mbedtls_mpi_get_bit( &grp->N, 0 ) != 1 ) 2122 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 2123 2124 /* do we need the parity trick? */ 2125 *parity_trick = ( mbedtls_mpi_get_bit( m, 0 ) == 0 ); 2126 2127 /* execute parity fix in constant time */ 2128 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) ); 2129 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N, m ) ); 2130 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, *parity_trick ) ); 2131 2132 /* actual scalar recoding */ 2133 ecp_comb_recode_core( k, d, w, &M ); 2134 2135 cleanup: 2136 mbedtls_mpi_free( &mm ); 2137 mbedtls_mpi_free( &M ); 2138 2139 return( ret ); 2140 } 2141 2142 /* 2143 * Perform comb multiplication (for short Weierstrass curves) 2144 * once the auxiliary table has been pre-computed. 2145 * 2146 * Scalar recoding may use a parity trick that makes us compute -m * P, 2147 * if that is the case we'll need to recover m * P at the end. 2148 */ 2149 static int ecp_mul_comb_after_precomp( const mbedtls_ecp_group *grp, 2150 mbedtls_ecp_point *R, 2151 const mbedtls_mpi *m, 2152 const mbedtls_ecp_point *T, 2153 unsigned char T_size, 2154 unsigned char w, 2155 size_t d, 2156 int (*f_rng)(void *, unsigned char *, size_t), 2157 void *p_rng, 2158 mbedtls_ecp_restart_ctx *rs_ctx ) 2159 { 2160 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2161 unsigned char parity_trick; 2162 unsigned char k[COMB_MAX_D + 1]; 2163 mbedtls_ecp_point *RR = R; 2164 2165 #if defined(MBEDTLS_ECP_RESTARTABLE) 2166 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 2167 { 2168 RR = &rs_ctx->rsm->R; 2169 2170 if( rs_ctx->rsm->state == ecp_rsm_final_norm ) 2171 goto final_norm; 2172 } 2173 #endif 2174 2175 MBEDTLS_MPI_CHK( ecp_comb_recode_scalar( grp, m, k, d, w, 2176 &parity_trick ) ); 2177 MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, RR, T, T_size, k, d, 2178 f_rng, p_rng, rs_ctx ) ); 2179 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, RR, parity_trick ) ); 2180 2181 #if defined(MBEDTLS_ECP_RESTARTABLE) 2182 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 2183 rs_ctx->rsm->state = ecp_rsm_final_norm; 2184 2185 final_norm: 2186 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV ); 2187 #endif 2188 /* 2189 * Knowledge of the jacobian coordinates may leak the last few bits of the 2190 * scalar [1], and since our MPI implementation isn't constant-flow, 2191 * inversion (used for coordinate normalization) may leak the full value 2192 * of its input via side-channels [2]. 2193 * 2194 * [1] https://eprint.iacr.org/2003/191 2195 * [2] https://eprint.iacr.org/2020/055 2196 * 2197 * Avoid the leak by randomizing coordinates before we normalize them. 2198 */ 2199 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2200 if( f_rng != 0 ) 2201 #endif 2202 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, RR, f_rng, p_rng ) ); 2203 2204 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, RR ) ); 2205 2206 #if defined(MBEDTLS_ECP_RESTARTABLE) 2207 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 2208 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, RR ) ); 2209 #endif 2210 2211 cleanup: 2212 return( ret ); 2213 } 2214 2215 /* 2216 * Pick window size based on curve size and whether we optimize for base point 2217 */ 2218 static unsigned char ecp_pick_window_size( const mbedtls_ecp_group *grp, 2219 unsigned char p_eq_g ) 2220 { 2221 unsigned char w; 2222 2223 /* 2224 * Minimize the number of multiplications, that is minimize 2225 * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w ) 2226 * (see costs of the various parts, with 1S = 1M) 2227 */ 2228 w = grp->nbits >= 384 ? 5 : 4; 2229 2230 /* 2231 * If P == G, pre-compute a bit more, since this may be re-used later. 2232 * Just adding one avoids upping the cost of the first mul too much, 2233 * and the memory cost too. 2234 */ 2235 if( p_eq_g ) 2236 w++; 2237 2238 /* 2239 * Make sure w is within bounds. 2240 * (The last test is useful only for very small curves in the test suite.) 2241 */ 2242 #if( MBEDTLS_ECP_WINDOW_SIZE < 6 ) 2243 if( w > MBEDTLS_ECP_WINDOW_SIZE ) 2244 w = MBEDTLS_ECP_WINDOW_SIZE; 2245 #endif 2246 if( w >= grp->nbits ) 2247 w = 2; 2248 2249 return( w ); 2250 } 2251 2252 /* 2253 * Multiplication using the comb method - for curves in short Weierstrass form 2254 * 2255 * This function is mainly responsible for administrative work: 2256 * - managing the restart context if enabled 2257 * - managing the table of precomputed points (passed between the below two 2258 * functions): allocation, computation, ownership transfer, freeing. 2259 * 2260 * It delegates the actual arithmetic work to: 2261 * ecp_precompute_comb() and ecp_mul_comb_with_precomp() 2262 * 2263 * See comments on ecp_comb_recode_core() regarding the computation strategy. 2264 */ 2265 static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2266 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2267 int (*f_rng)(void *, unsigned char *, size_t), 2268 void *p_rng, 2269 mbedtls_ecp_restart_ctx *rs_ctx ) 2270 { 2271 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2272 unsigned char w, p_eq_g, i; 2273 size_t d; 2274 unsigned char T_size = 0, T_ok = 0; 2275 mbedtls_ecp_point *T = NULL; 2276 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2277 ecp_drbg_context drbg_ctx; 2278 2279 ecp_drbg_init( &drbg_ctx ); 2280 #endif 2281 2282 ECP_RS_ENTER( rsm ); 2283 2284 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2285 if( f_rng == NULL ) 2286 { 2287 /* Adjust pointers */ 2288 f_rng = &ecp_drbg_random; 2289 #if defined(MBEDTLS_ECP_RESTARTABLE) 2290 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 2291 p_rng = &rs_ctx->rsm->drbg_ctx; 2292 else 2293 #endif 2294 p_rng = &drbg_ctx; 2295 2296 /* Initialize internal DRBG if necessary */ 2297 #if defined(MBEDTLS_ECP_RESTARTABLE) 2298 if( rs_ctx == NULL || rs_ctx->rsm == NULL || 2299 rs_ctx->rsm->drbg_seeded == 0 ) 2300 #endif 2301 { 2302 const size_t m_len = ( grp->nbits + 7 ) / 8; 2303 MBEDTLS_MPI_CHK( ecp_drbg_seed( p_rng, m, m_len ) ); 2304 } 2305 #if defined(MBEDTLS_ECP_RESTARTABLE) 2306 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 2307 rs_ctx->rsm->drbg_seeded = 1; 2308 #endif 2309 } 2310 #endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */ 2311 2312 /* Is P the base point ? */ 2313 #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1 2314 p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 && 2315 mbedtls_mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 ); 2316 #else 2317 p_eq_g = 0; 2318 #endif 2319 2320 /* Pick window size and deduce related sizes */ 2321 w = ecp_pick_window_size( grp, p_eq_g ); 2322 T_size = 1U << ( w - 1 ); 2323 d = ( grp->nbits + w - 1 ) / w; 2324 2325 /* Pre-computed table: do we have it already for the base point? */ 2326 if( p_eq_g && grp->T != NULL ) 2327 { 2328 /* second pointer to the same table, will be deleted on exit */ 2329 T = grp->T; 2330 T_ok = 1; 2331 } 2332 else 2333 #if defined(MBEDTLS_ECP_RESTARTABLE) 2334 /* Pre-computed table: do we have one in progress? complete? */ 2335 if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->T != NULL ) 2336 { 2337 /* transfer ownership of T from rsm to local function */ 2338 T = rs_ctx->rsm->T; 2339 rs_ctx->rsm->T = NULL; 2340 rs_ctx->rsm->T_size = 0; 2341 2342 /* This effectively jumps to the call to mul_comb_after_precomp() */ 2343 T_ok = rs_ctx->rsm->state >= ecp_rsm_comb_core; 2344 } 2345 else 2346 #endif 2347 /* Allocate table if we didn't have any */ 2348 { 2349 T = mbedtls_calloc( T_size, sizeof( mbedtls_ecp_point ) ); 2350 if( T == NULL ) 2351 { 2352 ret = MBEDTLS_ERR_ECP_ALLOC_FAILED; 2353 goto cleanup; 2354 } 2355 2356 for( i = 0; i < T_size; i++ ) 2357 mbedtls_ecp_point_init( &T[i] ); 2358 2359 T_ok = 0; 2360 } 2361 2362 /* Compute table (or finish computing it) if not done already */ 2363 if( !T_ok ) 2364 { 2365 MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d, rs_ctx ) ); 2366 2367 if( p_eq_g ) 2368 { 2369 /* almost transfer ownership of T to the group, but keep a copy of 2370 * the pointer to use for calling the next function more easily */ 2371 grp->T = T; 2372 grp->T_size = T_size; 2373 } 2374 } 2375 2376 /* Actual comb multiplication using precomputed points */ 2377 MBEDTLS_MPI_CHK( ecp_mul_comb_after_precomp( grp, R, m, 2378 T, T_size, w, d, 2379 f_rng, p_rng, rs_ctx ) ); 2380 2381 cleanup: 2382 2383 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2384 ecp_drbg_free( &drbg_ctx ); 2385 #endif 2386 2387 /* does T belong to the group? */ 2388 if( T == grp->T ) 2389 T = NULL; 2390 2391 /* does T belong to the restart context? */ 2392 #if defined(MBEDTLS_ECP_RESTARTABLE) 2393 if( rs_ctx != NULL && rs_ctx->rsm != NULL && ret == MBEDTLS_ERR_ECP_IN_PROGRESS && T != NULL ) 2394 { 2395 /* transfer ownership of T from local function to rsm */ 2396 rs_ctx->rsm->T_size = T_size; 2397 rs_ctx->rsm->T = T; 2398 T = NULL; 2399 } 2400 #endif 2401 2402 /* did T belong to us? then let's destroy it! */ 2403 if( T != NULL ) 2404 { 2405 for( i = 0; i < T_size; i++ ) 2406 mbedtls_ecp_point_free( &T[i] ); 2407 mbedtls_free( T ); 2408 } 2409 2410 /* don't free R while in progress in case R == P */ 2411 #if defined(MBEDTLS_ECP_RESTARTABLE) 2412 if( ret != MBEDTLS_ERR_ECP_IN_PROGRESS ) 2413 #endif 2414 /* prevent caller from using invalid value */ 2415 if( ret != 0 ) 2416 mbedtls_ecp_point_free( R ); 2417 2418 ECP_RS_LEAVE( rsm ); 2419 2420 return( ret ); 2421 } 2422 2423 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 2424 2425 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 2426 /* 2427 * For Montgomery curves, we do all the internal arithmetic in projective 2428 * coordinates. Import/export of points uses only the x coordinates, which is 2429 * internally represented as X / Z. 2430 * 2431 * For scalar multiplication, we'll use a Montgomery ladder. 2432 */ 2433 2434 /* 2435 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1 2436 * Cost: 1M + 1I 2437 */ 2438 static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P ) 2439 { 2440 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) 2441 if( mbedtls_internal_ecp_grp_capable( grp ) ) 2442 return( mbedtls_internal_ecp_normalize_mxz( grp, P ) ); 2443 #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */ 2444 2445 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) 2446 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 2447 #else 2448 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2449 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) ); 2450 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &P->X, &P->X, &P->Z ) ); 2451 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) ); 2452 2453 cleanup: 2454 return( ret ); 2455 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) */ 2456 } 2457 2458 /* 2459 * Randomize projective x/z coordinates: 2460 * (X, Z) -> (l X, l Z) for random l 2461 * This is sort of the reverse operation of ecp_normalize_mxz(). 2462 * 2463 * This countermeasure was first suggested in [2]. 2464 * Cost: 2M 2465 */ 2466 static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P, 2467 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 2468 { 2469 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) 2470 if( mbedtls_internal_ecp_grp_capable( grp ) ) 2471 return( mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng ) ); 2472 #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */ 2473 2474 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) 2475 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 2476 #else 2477 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2478 mbedtls_mpi l; 2479 mbedtls_mpi_init( &l ); 2480 2481 /* Generate l such that 1 < l < p */ 2482 MBEDTLS_MPI_CHK( mbedtls_mpi_random( &l, 2, &grp->P, f_rng, p_rng ) ); 2483 2484 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &P->X, &P->X, &l ) ); 2485 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &P->Z, &P->Z, &l ) ); 2486 2487 cleanup: 2488 mbedtls_mpi_free( &l ); 2489 2490 if( ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ) 2491 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED; 2492 return( ret ); 2493 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) */ 2494 } 2495 2496 /* 2497 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q), 2498 * for Montgomery curves in x/z coordinates. 2499 * 2500 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3 2501 * with 2502 * d = X1 2503 * P = (X2, Z2) 2504 * Q = (X3, Z3) 2505 * R = (X4, Z4) 2506 * S = (X5, Z5) 2507 * and eliminating temporary variables tO, ..., t4. 2508 * 2509 * Cost: 5M + 4S 2510 */ 2511 static int ecp_double_add_mxz( const mbedtls_ecp_group *grp, 2512 mbedtls_ecp_point *R, mbedtls_ecp_point *S, 2513 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q, 2514 const mbedtls_mpi *d ) 2515 { 2516 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) 2517 if( mbedtls_internal_ecp_grp_capable( grp ) ) 2518 return( mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d ) ); 2519 #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */ 2520 2521 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) 2522 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 2523 #else 2524 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2525 mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB; 2526 2527 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B ); 2528 mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C ); 2529 mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB ); 2530 2531 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &A, &P->X, &P->Z ) ); 2532 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &AA, &A, &A ) ); 2533 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &B, &P->X, &P->Z ) ); 2534 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &BB, &B, &B ) ); 2535 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &E, &AA, &BB ) ); 2536 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &C, &Q->X, &Q->Z ) ); 2537 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &D, &Q->X, &Q->Z ) ); 2538 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &DA, &D, &A ) ); 2539 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &CB, &C, &B ) ); 2540 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &S->X, &DA, &CB ) ); 2541 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S->X, &S->X, &S->X ) ); 2542 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &S->Z, &DA, &CB ) ); 2543 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S->Z, &S->Z, &S->Z ) ); 2544 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S->Z, d, &S->Z ) ); 2545 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &R->X, &AA, &BB ) ); 2546 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &R->Z, &grp->A, &E ) ); 2547 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &R->Z, &BB, &R->Z ) ); 2548 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &R->Z, &E, &R->Z ) ); 2549 2550 cleanup: 2551 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B ); 2552 mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C ); 2553 mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB ); 2554 2555 return( ret ); 2556 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) */ 2557 } 2558 2559 /* 2560 * Multiplication with Montgomery ladder in x/z coordinates, 2561 * for curves in Montgomery form 2562 */ 2563 static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2564 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2565 int (*f_rng)(void *, unsigned char *, size_t), 2566 void *p_rng ) 2567 { 2568 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2569 size_t i; 2570 unsigned char b; 2571 mbedtls_ecp_point RP; 2572 mbedtls_mpi PX; 2573 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2574 ecp_drbg_context drbg_ctx; 2575 2576 ecp_drbg_init( &drbg_ctx ); 2577 #endif 2578 mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX ); 2579 2580 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2581 if( f_rng == NULL ) 2582 { 2583 const size_t m_len = ( grp->nbits + 7 ) / 8; 2584 MBEDTLS_MPI_CHK( ecp_drbg_seed( &drbg_ctx, m, m_len ) ); 2585 f_rng = &ecp_drbg_random; 2586 p_rng = &drbg_ctx; 2587 } 2588 #endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */ 2589 2590 /* Save PX and read from P before writing to R, in case P == R */ 2591 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) ); 2592 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) ); 2593 2594 /* Set R to zero in modified x/z coordinates */ 2595 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X, 1 ) ); 2596 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) ); 2597 mbedtls_mpi_free( &R->Y ); 2598 2599 /* RP.X might be slightly larger than P, so reduce it */ 2600 MOD_ADD( RP.X ); 2601 2602 /* Randomize coordinates of the starting point */ 2603 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2604 if( f_rng != NULL ) 2605 #endif 2606 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) ); 2607 2608 /* Loop invariant: R = result so far, RP = R + P */ 2609 i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */ 2610 while( i-- > 0 ) 2611 { 2612 b = mbedtls_mpi_get_bit( m, i ); 2613 /* 2614 * if (b) R = 2R + P else R = 2R, 2615 * which is: 2616 * if (b) double_add( RP, R, RP, R ) 2617 * else double_add( R, RP, R, RP ) 2618 * but using safe conditional swaps to avoid leaks 2619 */ 2620 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) ); 2621 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); 2622 MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) ); 2623 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) ); 2624 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); 2625 } 2626 2627 /* 2628 * Knowledge of the projective coordinates may leak the last few bits of the 2629 * scalar [1], and since our MPI implementation isn't constant-flow, 2630 * inversion (used for coordinate normalization) may leak the full value 2631 * of its input via side-channels [2]. 2632 * 2633 * [1] https://eprint.iacr.org/2003/191 2634 * [2] https://eprint.iacr.org/2020/055 2635 * 2636 * Avoid the leak by randomizing coordinates before we normalize them. 2637 */ 2638 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2639 if( f_rng != NULL ) 2640 #endif 2641 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, R, f_rng, p_rng ) ); 2642 2643 MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) ); 2644 2645 cleanup: 2646 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2647 ecp_drbg_free( &drbg_ctx ); 2648 #endif 2649 2650 mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX ); 2651 2652 return( ret ); 2653 } 2654 2655 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 2656 2657 /* 2658 * Restartable multiplication R = m * P 2659 */ 2660 int mbedtls_ecp_mul_restartable( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2661 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2662 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng, 2663 mbedtls_ecp_restart_ctx *rs_ctx ) 2664 { 2665 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2666 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2667 char is_grp_capable = 0; 2668 #endif 2669 ECP_VALIDATE_RET( grp != NULL ); 2670 ECP_VALIDATE_RET( R != NULL ); 2671 ECP_VALIDATE_RET( m != NULL ); 2672 ECP_VALIDATE_RET( P != NULL ); 2673 2674 #if defined(MBEDTLS_ECP_RESTARTABLE) 2675 /* reset ops count for this call if top-level */ 2676 if( rs_ctx != NULL && rs_ctx->depth++ == 0 ) 2677 rs_ctx->ops_done = 0; 2678 #else 2679 (void) rs_ctx; 2680 #endif 2681 2682 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2683 if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) ) 2684 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); 2685 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2686 2687 #if defined(MBEDTLS_ECP_RESTARTABLE) 2688 /* skip argument check when restarting */ 2689 if( rs_ctx == NULL || rs_ctx->rsm == NULL ) 2690 #endif 2691 { 2692 /* check_privkey is free */ 2693 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_CHK ); 2694 2695 /* Common sanity checks */ 2696 MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( grp, m ) ); 2697 MBEDTLS_MPI_CHK( mbedtls_ecp_check_pubkey( grp, P ) ); 2698 } 2699 2700 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2701 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 2702 if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) 2703 MBEDTLS_MPI_CHK( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) ); 2704 #endif 2705 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 2706 if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) 2707 MBEDTLS_MPI_CHK( ecp_mul_comb( grp, R, m, P, f_rng, p_rng, rs_ctx ) ); 2708 #endif 2709 2710 cleanup: 2711 2712 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2713 if( is_grp_capable ) 2714 mbedtls_internal_ecp_free( grp ); 2715 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2716 2717 #if defined(MBEDTLS_ECP_RESTARTABLE) 2718 if( rs_ctx != NULL ) 2719 rs_ctx->depth--; 2720 #endif 2721 2722 return( ret ); 2723 } 2724 2725 /* 2726 * Multiplication R = m * P 2727 */ 2728 int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2729 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2730 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 2731 { 2732 ECP_VALIDATE_RET( grp != NULL ); 2733 ECP_VALIDATE_RET( R != NULL ); 2734 ECP_VALIDATE_RET( m != NULL ); 2735 ECP_VALIDATE_RET( P != NULL ); 2736 return( mbedtls_ecp_mul_restartable( grp, R, m, P, f_rng, p_rng, NULL ) ); 2737 } 2738 2739 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 2740 /* 2741 * Check that an affine point is valid as a public key, 2742 * short weierstrass curves (SEC1 3.2.3.1) 2743 */ 2744 static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 2745 { 2746 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2747 mbedtls_mpi YY, RHS; 2748 2749 /* pt coordinates must be normalized for our checks */ 2750 if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 || 2751 mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 || 2752 mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 || 2753 mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 ) 2754 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2755 2756 mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS ); 2757 2758 /* 2759 * YY = Y^2 2760 * RHS = X (X^2 + A) + B = X^3 + A X + B 2761 */ 2762 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &YY, &pt->Y, &pt->Y ) ); 2763 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &RHS, &pt->X, &pt->X ) ); 2764 2765 /* Special case for A = -3 */ 2766 if( grp->A.p == NULL ) 2767 { 2768 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS ); 2769 } 2770 else 2771 { 2772 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &RHS, &RHS, &grp->A ) ); 2773 } 2774 2775 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &RHS, &RHS, &pt->X ) ); 2776 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &RHS, &RHS, &grp->B ) ); 2777 2778 if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 ) 2779 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 2780 2781 cleanup: 2782 2783 mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS ); 2784 2785 return( ret ); 2786 } 2787 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 2788 2789 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 2790 /* 2791 * R = m * P with shortcuts for m == 0, m == 1 and m == -1 2792 * NOT constant-time - ONLY for short Weierstrass! 2793 */ 2794 static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp, 2795 mbedtls_ecp_point *R, 2796 const mbedtls_mpi *m, 2797 const mbedtls_ecp_point *P, 2798 mbedtls_ecp_restart_ctx *rs_ctx ) 2799 { 2800 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2801 2802 if( mbedtls_mpi_cmp_int( m, 0 ) == 0 ) 2803 { 2804 MBEDTLS_MPI_CHK( mbedtls_ecp_set_zero( R ) ); 2805 } 2806 else if( mbedtls_mpi_cmp_int( m, 1 ) == 0 ) 2807 { 2808 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); 2809 } 2810 else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 ) 2811 { 2812 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); 2813 if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 ) 2814 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) ); 2815 } 2816 else 2817 { 2818 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_restartable( grp, R, m, P, 2819 NULL, NULL, rs_ctx ) ); 2820 } 2821 2822 cleanup: 2823 return( ret ); 2824 } 2825 2826 /* 2827 * Restartable linear combination 2828 * NOT constant-time 2829 */ 2830 int mbedtls_ecp_muladd_restartable( 2831 mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2832 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2833 const mbedtls_mpi *n, const mbedtls_ecp_point *Q, 2834 mbedtls_ecp_restart_ctx *rs_ctx ) 2835 { 2836 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2837 mbedtls_ecp_point mP; 2838 mbedtls_ecp_point *pmP = &mP; 2839 mbedtls_ecp_point *pR = R; 2840 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2841 char is_grp_capable = 0; 2842 #endif 2843 ECP_VALIDATE_RET( grp != NULL ); 2844 ECP_VALIDATE_RET( R != NULL ); 2845 ECP_VALIDATE_RET( m != NULL ); 2846 ECP_VALIDATE_RET( P != NULL ); 2847 ECP_VALIDATE_RET( n != NULL ); 2848 ECP_VALIDATE_RET( Q != NULL ); 2849 2850 if( mbedtls_ecp_get_type( grp ) != MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) 2851 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 2852 2853 mbedtls_ecp_point_init( &mP ); 2854 2855 ECP_RS_ENTER( ma ); 2856 2857 #if defined(MBEDTLS_ECP_RESTARTABLE) 2858 if( rs_ctx != NULL && rs_ctx->ma != NULL ) 2859 { 2860 /* redirect intermediate results to restart context */ 2861 pmP = &rs_ctx->ma->mP; 2862 pR = &rs_ctx->ma->R; 2863 2864 /* jump to next operation */ 2865 if( rs_ctx->ma->state == ecp_rsma_mul2 ) 2866 goto mul2; 2867 if( rs_ctx->ma->state == ecp_rsma_add ) 2868 goto add; 2869 if( rs_ctx->ma->state == ecp_rsma_norm ) 2870 goto norm; 2871 } 2872 #endif /* MBEDTLS_ECP_RESTARTABLE */ 2873 2874 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pmP, m, P, rs_ctx ) ); 2875 #if defined(MBEDTLS_ECP_RESTARTABLE) 2876 if( rs_ctx != NULL && rs_ctx->ma != NULL ) 2877 rs_ctx->ma->state = ecp_rsma_mul2; 2878 2879 mul2: 2880 #endif 2881 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pR, n, Q, rs_ctx ) ); 2882 2883 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2884 if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) ) 2885 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); 2886 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2887 2888 #if defined(MBEDTLS_ECP_RESTARTABLE) 2889 if( rs_ctx != NULL && rs_ctx->ma != NULL ) 2890 rs_ctx->ma->state = ecp_rsma_add; 2891 2892 add: 2893 #endif 2894 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_ADD ); 2895 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, pR, pmP, pR ) ); 2896 #if defined(MBEDTLS_ECP_RESTARTABLE) 2897 if( rs_ctx != NULL && rs_ctx->ma != NULL ) 2898 rs_ctx->ma->state = ecp_rsma_norm; 2899 2900 norm: 2901 #endif 2902 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV ); 2903 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, pR ) ); 2904 2905 #if defined(MBEDTLS_ECP_RESTARTABLE) 2906 if( rs_ctx != NULL && rs_ctx->ma != NULL ) 2907 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, pR ) ); 2908 #endif 2909 2910 cleanup: 2911 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2912 if( is_grp_capable ) 2913 mbedtls_internal_ecp_free( grp ); 2914 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2915 2916 mbedtls_ecp_point_free( &mP ); 2917 2918 ECP_RS_LEAVE( ma ); 2919 2920 return( ret ); 2921 } 2922 2923 /* 2924 * Linear combination 2925 * NOT constant-time 2926 */ 2927 int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2928 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2929 const mbedtls_mpi *n, const mbedtls_ecp_point *Q ) 2930 { 2931 ECP_VALIDATE_RET( grp != NULL ); 2932 ECP_VALIDATE_RET( R != NULL ); 2933 ECP_VALIDATE_RET( m != NULL ); 2934 ECP_VALIDATE_RET( P != NULL ); 2935 ECP_VALIDATE_RET( n != NULL ); 2936 ECP_VALIDATE_RET( Q != NULL ); 2937 return( mbedtls_ecp_muladd_restartable( grp, R, m, P, n, Q, NULL ) ); 2938 } 2939 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 2940 2941 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 2942 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) 2943 #define ECP_MPI_INIT(s, n, p) {s, 0, (n), (mbedtls_mpi_uint *)(p)} 2944 #define ECP_MPI_INIT_ARRAY(x) \ 2945 ECP_MPI_INIT(1, sizeof(x) / sizeof(mbedtls_mpi_uint), x) 2946 /* 2947 * Constants for the two points other than 0, 1, -1 (mod p) in 2948 * https://cr.yp.to/ecdh.html#validate 2949 * See ecp_check_pubkey_x25519(). 2950 */ 2951 static const mbedtls_mpi_uint x25519_bad_point_1[] = { 2952 MBEDTLS_BYTES_TO_T_UINT_8( 0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae ), 2953 MBEDTLS_BYTES_TO_T_UINT_8( 0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a ), 2954 MBEDTLS_BYTES_TO_T_UINT_8( 0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd ), 2955 MBEDTLS_BYTES_TO_T_UINT_8( 0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00 ), 2956 }; 2957 static const mbedtls_mpi_uint x25519_bad_point_2[] = { 2958 MBEDTLS_BYTES_TO_T_UINT_8( 0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24 ), 2959 MBEDTLS_BYTES_TO_T_UINT_8( 0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b ), 2960 MBEDTLS_BYTES_TO_T_UINT_8( 0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86 ), 2961 MBEDTLS_BYTES_TO_T_UINT_8( 0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57 ), 2962 }; 2963 static const mbedtls_mpi ecp_x25519_bad_point_1 = ECP_MPI_INIT_ARRAY( 2964 x25519_bad_point_1 ); 2965 static const mbedtls_mpi ecp_x25519_bad_point_2 = ECP_MPI_INIT_ARRAY( 2966 x25519_bad_point_2 ); 2967 #endif /* MBEDTLS_ECP_DP_CURVE25519_ENABLED */ 2968 2969 /* 2970 * Check that the input point is not one of the low-order points. 2971 * This is recommended by the "May the Fourth" paper: 2972 * https://eprint.iacr.org/2017/806.pdf 2973 * Those points are never sent by an honest peer. 2974 */ 2975 static int ecp_check_bad_points_mx( const mbedtls_mpi *X, const mbedtls_mpi *P, 2976 const mbedtls_ecp_group_id grp_id ) 2977 { 2978 int ret; 2979 mbedtls_mpi XmP; 2980 2981 mbedtls_mpi_init( &XmP ); 2982 2983 /* Reduce X mod P so that we only need to check values less than P. 2984 * We know X < 2^256 so we can proceed by subtraction. */ 2985 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &XmP, X ) ); 2986 while( mbedtls_mpi_cmp_mpi( &XmP, P ) >= 0 ) 2987 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &XmP, &XmP, P ) ); 2988 2989 /* Check against the known bad values that are less than P. For Curve448 2990 * these are 0, 1 and -1. For Curve25519 we check the values less than P 2991 * from the following list: https://cr.yp.to/ecdh.html#validate */ 2992 if( mbedtls_mpi_cmp_int( &XmP, 1 ) <= 0 ) /* takes care of 0 and 1 */ 2993 { 2994 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 2995 goto cleanup; 2996 } 2997 2998 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) 2999 if( grp_id == MBEDTLS_ECP_DP_CURVE25519 ) 3000 { 3001 if( mbedtls_mpi_cmp_mpi( &XmP, &ecp_x25519_bad_point_1 ) == 0 ) 3002 { 3003 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 3004 goto cleanup; 3005 } 3006 3007 if( mbedtls_mpi_cmp_mpi( &XmP, &ecp_x25519_bad_point_2 ) == 0 ) 3008 { 3009 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 3010 goto cleanup; 3011 } 3012 } 3013 #else 3014 (void) grp_id; 3015 #endif 3016 3017 /* Final check: check if XmP + 1 is P (final because it changes XmP!) */ 3018 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &XmP, &XmP, 1 ) ); 3019 if( mbedtls_mpi_cmp_mpi( &XmP, P ) == 0 ) 3020 { 3021 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 3022 goto cleanup; 3023 } 3024 3025 ret = 0; 3026 3027 cleanup: 3028 mbedtls_mpi_free( &XmP ); 3029 3030 return( ret ); 3031 } 3032 3033 /* 3034 * Check validity of a public key for Montgomery curves with x-only schemes 3035 */ 3036 static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 3037 { 3038 /* [Curve25519 p. 5] Just check X is the correct number of bytes */ 3039 /* Allow any public value, if it's too big then we'll just reduce it mod p 3040 * (RFC 7748 sec. 5 para. 3). */ 3041 if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 ) 3042 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 3043 3044 /* Implicit in all standards (as they don't consider negative numbers): 3045 * X must be non-negative. This is normally ensured by the way it's 3046 * encoded for transmission, but let's be extra sure. */ 3047 if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 ) 3048 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 3049 3050 return( ecp_check_bad_points_mx( &pt->X, &grp->P, grp->id ) ); 3051 } 3052 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3053 3054 /* 3055 * Check that a point is valid as a public key 3056 */ 3057 int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp, 3058 const mbedtls_ecp_point *pt ) 3059 { 3060 ECP_VALIDATE_RET( grp != NULL ); 3061 ECP_VALIDATE_RET( pt != NULL ); 3062 3063 /* Must use affine coordinates */ 3064 if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 ) 3065 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 3066 3067 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3068 if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) 3069 return( ecp_check_pubkey_mx( grp, pt ) ); 3070 #endif 3071 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3072 if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) 3073 return( ecp_check_pubkey_sw( grp, pt ) ); 3074 #endif 3075 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 3076 } 3077 3078 /* 3079 * Check that an mbedtls_mpi is valid as a private key 3080 */ 3081 int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, 3082 const mbedtls_mpi *d ) 3083 { 3084 ECP_VALIDATE_RET( grp != NULL ); 3085 ECP_VALIDATE_RET( d != NULL ); 3086 3087 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3088 if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) 3089 { 3090 /* see RFC 7748 sec. 5 para. 5 */ 3091 if( mbedtls_mpi_get_bit( d, 0 ) != 0 || 3092 mbedtls_mpi_get_bit( d, 1 ) != 0 || 3093 mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */ 3094 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 3095 3096 /* see [Curve25519] page 5 */ 3097 if( grp->nbits == 254 && mbedtls_mpi_get_bit( d, 2 ) != 0 ) 3098 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 3099 3100 return( 0 ); 3101 } 3102 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3103 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3104 if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) 3105 { 3106 /* see SEC1 3.2 */ 3107 if( mbedtls_mpi_cmp_int( d, 1 ) < 0 || 3108 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 ) 3109 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 3110 else 3111 return( 0 ); 3112 } 3113 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 3114 3115 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 3116 } 3117 3118 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3119 MBEDTLS_STATIC_TESTABLE 3120 int mbedtls_ecp_gen_privkey_mx( size_t high_bit, 3121 mbedtls_mpi *d, 3122 int (*f_rng)(void *, unsigned char *, size_t), 3123 void *p_rng ) 3124 { 3125 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 3126 size_t n_random_bytes = high_bit / 8 + 1; 3127 3128 /* [Curve25519] page 5 */ 3129 /* Generate a (high_bit+1)-bit random number by generating just enough 3130 * random bytes, then shifting out extra bits from the top (necessary 3131 * when (high_bit+1) is not a multiple of 8). */ 3132 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_random_bytes, 3133 f_rng, p_rng ) ); 3134 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_random_bytes - high_bit - 1 ) ); 3135 3136 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, high_bit, 1 ) ); 3137 3138 /* Make sure the last two bits are unset for Curve448, three bits for 3139 Curve25519 */ 3140 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) ); 3141 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) ); 3142 if( high_bit == 254 ) 3143 { 3144 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) ); 3145 } 3146 3147 cleanup: 3148 return( ret ); 3149 } 3150 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3151 3152 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3153 static int mbedtls_ecp_gen_privkey_sw( 3154 const mbedtls_mpi *N, mbedtls_mpi *d, 3155 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 3156 { 3157 int ret = mbedtls_mpi_random( d, 1, N, f_rng, p_rng ); 3158 switch( ret ) 3159 { 3160 case MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: 3161 return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); 3162 default: 3163 return( ret ); 3164 } 3165 } 3166 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 3167 3168 /* 3169 * Generate a private key 3170 */ 3171 int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp, 3172 mbedtls_mpi *d, 3173 int (*f_rng)(void *, unsigned char *, size_t), 3174 void *p_rng ) 3175 { 3176 ECP_VALIDATE_RET( grp != NULL ); 3177 ECP_VALIDATE_RET( d != NULL ); 3178 ECP_VALIDATE_RET( f_rng != NULL ); 3179 3180 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3181 if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) 3182 return( mbedtls_ecp_gen_privkey_mx( grp->nbits, d, f_rng, p_rng ) ); 3183 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3184 3185 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3186 if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) 3187 return( mbedtls_ecp_gen_privkey_sw( &grp->N, d, f_rng, p_rng ) ); 3188 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 3189 3190 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 3191 } 3192 3193 /* 3194 * Generate a keypair with configurable base point 3195 */ 3196 int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp, 3197 const mbedtls_ecp_point *G, 3198 mbedtls_mpi *d, mbedtls_ecp_point *Q, 3199 int (*f_rng)(void *, unsigned char *, size_t), 3200 void *p_rng ) 3201 { 3202 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 3203 ECP_VALIDATE_RET( grp != NULL ); 3204 ECP_VALIDATE_RET( d != NULL ); 3205 ECP_VALIDATE_RET( G != NULL ); 3206 ECP_VALIDATE_RET( Q != NULL ); 3207 ECP_VALIDATE_RET( f_rng != NULL ); 3208 3209 MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, d, f_rng, p_rng ) ); 3210 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) ); 3211 3212 cleanup: 3213 return( ret ); 3214 } 3215 3216 /* 3217 * Generate key pair, wrapper for conventional base point 3218 */ 3219 int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp, 3220 mbedtls_mpi *d, mbedtls_ecp_point *Q, 3221 int (*f_rng)(void *, unsigned char *, size_t), 3222 void *p_rng ) 3223 { 3224 ECP_VALIDATE_RET( grp != NULL ); 3225 ECP_VALIDATE_RET( d != NULL ); 3226 ECP_VALIDATE_RET( Q != NULL ); 3227 ECP_VALIDATE_RET( f_rng != NULL ); 3228 3229 return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) ); 3230 } 3231 3232 /* 3233 * Generate a keypair, prettier wrapper 3234 */ 3235 int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, 3236 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 3237 { 3238 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 3239 ECP_VALIDATE_RET( key != NULL ); 3240 ECP_VALIDATE_RET( f_rng != NULL ); 3241 3242 if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 ) 3243 return( ret ); 3244 3245 return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) ); 3246 } 3247 3248 #define ECP_CURVE25519_KEY_SIZE 32 3249 /* 3250 * Read a private key. 3251 */ 3252 int mbedtls_ecp_read_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, 3253 const unsigned char *buf, size_t buflen ) 3254 { 3255 int ret = 0; 3256 3257 ECP_VALIDATE_RET( key != NULL ); 3258 ECP_VALIDATE_RET( buf != NULL ); 3259 3260 if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 ) 3261 return( ret ); 3262 3263 ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 3264 3265 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3266 if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) 3267 { 3268 /* 3269 * If it is Curve25519 curve then mask the key as mandated by RFC7748 3270 */ 3271 if( grp_id == MBEDTLS_ECP_DP_CURVE25519 ) 3272 { 3273 if( buflen != ECP_CURVE25519_KEY_SIZE ) 3274 return MBEDTLS_ERR_ECP_INVALID_KEY; 3275 3276 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary_le( &key->d, buf, buflen ) ); 3277 3278 /* Set the three least significant bits to 0 */ 3279 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d, 0, 0 ) ); 3280 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d, 1, 0 ) ); 3281 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d, 2, 0 ) ); 3282 3283 /* Set the most significant bit to 0 */ 3284 MBEDTLS_MPI_CHK( 3285 mbedtls_mpi_set_bit( &key->d, 3286 ECP_CURVE25519_KEY_SIZE * 8 - 1, 0 ) 3287 ); 3288 3289 /* Set the second most significant bit to 1 */ 3290 MBEDTLS_MPI_CHK( 3291 mbedtls_mpi_set_bit( &key->d, 3292 ECP_CURVE25519_KEY_SIZE * 8 - 2, 1 ) 3293 ); 3294 } 3295 else 3296 ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 3297 } 3298 3299 #endif 3300 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3301 if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) 3302 { 3303 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &key->d, buf, buflen ) ); 3304 3305 MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( &key->grp, &key->d ) ); 3306 } 3307 3308 #endif 3309 cleanup: 3310 3311 if( ret != 0 ) 3312 mbedtls_mpi_free( &key->d ); 3313 3314 return( ret ); 3315 } 3316 3317 /* 3318 * Write a private key. 3319 */ 3320 int mbedtls_ecp_write_key( mbedtls_ecp_keypair *key, 3321 unsigned char *buf, size_t buflen ) 3322 { 3323 int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 3324 3325 ECP_VALIDATE_RET( key != NULL ); 3326 ECP_VALIDATE_RET( buf != NULL ); 3327 3328 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3329 if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY ) 3330 { 3331 if( key->grp.id == MBEDTLS_ECP_DP_CURVE25519 ) 3332 { 3333 if( buflen < ECP_CURVE25519_KEY_SIZE ) 3334 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL; 3335 3336 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary_le( &key->d, buf, buflen ) ); 3337 } 3338 else 3339 ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 3340 } 3341 3342 #endif 3343 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3344 if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS ) 3345 { 3346 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &key->d, buf, buflen ) ); 3347 } 3348 3349 #endif 3350 cleanup: 3351 3352 return( ret ); 3353 } 3354 3355 3356 /* 3357 * Check a public-private key pair 3358 */ 3359 int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv ) 3360 { 3361 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 3362 mbedtls_ecp_point Q; 3363 mbedtls_ecp_group grp; 3364 ECP_VALIDATE_RET( pub != NULL ); 3365 ECP_VALIDATE_RET( prv != NULL ); 3366 3367 if( pub->grp.id == MBEDTLS_ECP_DP_NONE || 3368 pub->grp.id != prv->grp.id || 3369 mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) || 3370 mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) || 3371 mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) ) 3372 { 3373 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 3374 } 3375 3376 mbedtls_ecp_point_init( &Q ); 3377 mbedtls_ecp_group_init( &grp ); 3378 3379 /* mbedtls_ecp_mul() needs a non-const group... */ 3380 mbedtls_ecp_group_copy( &grp, &prv->grp ); 3381 3382 /* Also checks d is valid */ 3383 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) ); 3384 3385 if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) || 3386 mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) || 3387 mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) ) 3388 { 3389 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 3390 goto cleanup; 3391 } 3392 3393 cleanup: 3394 mbedtls_ecp_point_free( &Q ); 3395 mbedtls_ecp_group_free( &grp ); 3396 3397 return( ret ); 3398 } 3399 3400 #if defined(MBEDTLS_SELF_TEST) 3401 3402 /* Adjust the exponent to be a valid private point for the specified curve. 3403 * This is sometimes necessary because we use a single set of exponents 3404 * for all curves but the validity of values depends on the curve. */ 3405 static int self_test_adjust_exponent( const mbedtls_ecp_group *grp, 3406 mbedtls_mpi *m ) 3407 { 3408 int ret = 0; 3409 switch( grp->id ) 3410 { 3411 /* If Curve25519 is available, then that's what we use for the 3412 * Montgomery test, so we don't need the adjustment code. */ 3413 #if ! defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) 3414 #if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED) 3415 case MBEDTLS_ECP_DP_CURVE448: 3416 /* Move highest bit from 254 to N-1. Setting bit N-1 is 3417 * necessary to enforce the highest-bit-set constraint. */ 3418 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( m, 254, 0 ) ); 3419 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( m, grp->nbits, 1 ) ); 3420 /* Copy second-highest bit from 253 to N-2. This is not 3421 * necessary but improves the test variety a bit. */ 3422 MBEDTLS_MPI_CHK( 3423 mbedtls_mpi_set_bit( m, grp->nbits - 1, 3424 mbedtls_mpi_get_bit( m, 253 ) ) ); 3425 break; 3426 #endif 3427 #endif /* ! defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) */ 3428 default: 3429 /* Non-Montgomery curves and Curve25519 need no adjustment. */ 3430 (void) grp; 3431 (void) m; 3432 goto cleanup; 3433 } 3434 cleanup: 3435 return( ret ); 3436 } 3437 3438 /* Calculate R = m.P for each m in exponents. Check that the number of 3439 * basic operations doesn't depend on the value of m. */ 3440 static int self_test_point( int verbose, 3441 mbedtls_ecp_group *grp, 3442 mbedtls_ecp_point *R, 3443 mbedtls_mpi *m, 3444 const mbedtls_ecp_point *P, 3445 const char *const *exponents, 3446 size_t n_exponents ) 3447 { 3448 int ret = 0; 3449 size_t i = 0; 3450 unsigned long add_c_prev, dbl_c_prev, mul_c_prev; 3451 add_count = 0; 3452 dbl_count = 0; 3453 mul_count = 0; 3454 3455 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( m, 16, exponents[0] ) ); 3456 MBEDTLS_MPI_CHK( self_test_adjust_exponent( grp, m ) ); 3457 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, R, m, P, NULL, NULL ) ); 3458 3459 for( i = 1; i < n_exponents; i++ ) 3460 { 3461 add_c_prev = add_count; 3462 dbl_c_prev = dbl_count; 3463 mul_c_prev = mul_count; 3464 add_count = 0; 3465 dbl_count = 0; 3466 mul_count = 0; 3467 3468 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( m, 16, exponents[i] ) ); 3469 MBEDTLS_MPI_CHK( self_test_adjust_exponent( grp, m ) ); 3470 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, R, m, P, NULL, NULL ) ); 3471 3472 if( add_count != add_c_prev || 3473 dbl_count != dbl_c_prev || 3474 mul_count != mul_c_prev ) 3475 { 3476 ret = 1; 3477 break; 3478 } 3479 } 3480 3481 cleanup: 3482 if( verbose != 0 ) 3483 { 3484 if( ret != 0 ) 3485 mbedtls_printf( "failed (%u)\n", (unsigned int) i ); 3486 else 3487 mbedtls_printf( "passed\n" ); 3488 } 3489 return( ret ); 3490 } 3491 3492 /* 3493 * Checkup routine 3494 */ 3495 int mbedtls_ecp_self_test( int verbose ) 3496 { 3497 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 3498 mbedtls_ecp_group grp; 3499 mbedtls_ecp_point R, P; 3500 mbedtls_mpi m; 3501 3502 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3503 /* Exponents especially adapted for secp192k1, which has the lowest 3504 * order n of all supported curves (secp192r1 is in a slightly larger 3505 * field but the order of its base point is slightly smaller). */ 3506 const char *sw_exponents[] = 3507 { 3508 "000000000000000000000000000000000000000000000001", /* one */ 3509 "FFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8C", /* n - 1 */ 3510 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */ 3511 "400000000000000000000000000000000000000000000000", /* one and zeros */ 3512 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */ 3513 "555555555555555555555555555555555555555555555555", /* 101010... */ 3514 }; 3515 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 3516 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3517 const char *m_exponents[] = 3518 { 3519 /* Valid private values for Curve25519. In a build with Curve448 3520 * but not Curve25519, they will be adjusted in 3521 * self_test_adjust_exponent(). */ 3522 "4000000000000000000000000000000000000000000000000000000000000000", 3523 "5C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C30", 3524 "5715ECCE24583F7A7023C24164390586842E816D7280A49EF6DF4EAE6B280BF8", 3525 "41A2B017516F6D254E1F002BCCBADD54BE30F8CEC737A0E912B4963B6BA74460", 3526 "5555555555555555555555555555555555555555555555555555555555555550", 3527 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8", 3528 }; 3529 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3530 3531 mbedtls_ecp_group_init( &grp ); 3532 mbedtls_ecp_point_init( &R ); 3533 mbedtls_ecp_point_init( &P ); 3534 mbedtls_mpi_init( &m ); 3535 3536 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3537 /* Use secp192r1 if available, or any available curve */ 3538 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) 3539 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) ); 3540 #else 3541 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) ); 3542 #endif 3543 3544 if( verbose != 0 ) 3545 mbedtls_printf( " ECP SW test #1 (constant op_count, base point G): " ); 3546 /* Do a dummy multiplication first to trigger precomputation */ 3547 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) ); 3548 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) ); 3549 ret = self_test_point( verbose, 3550 &grp, &R, &m, &grp.G, 3551 sw_exponents, 3552 sizeof( sw_exponents ) / sizeof( sw_exponents[0] )); 3553 if( ret != 0 ) 3554 goto cleanup; 3555 3556 if( verbose != 0 ) 3557 mbedtls_printf( " ECP SW test #2 (constant op_count, other point): " ); 3558 /* We computed P = 2G last time, use it */ 3559 ret = self_test_point( verbose, 3560 &grp, &R, &m, &P, 3561 sw_exponents, 3562 sizeof( sw_exponents ) / sizeof( sw_exponents[0] )); 3563 if( ret != 0 ) 3564 goto cleanup; 3565 3566 mbedtls_ecp_group_free( &grp ); 3567 mbedtls_ecp_point_free( &R ); 3568 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 3569 3570 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3571 if( verbose != 0 ) 3572 mbedtls_printf( " ECP Montgomery test (constant op_count): " ); 3573 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) 3574 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_CURVE25519 ) ); 3575 #elif defined(MBEDTLS_ECP_DP_CURVE448_ENABLED) 3576 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_CURVE448 ) ); 3577 #else 3578 #error "MBEDTLS_ECP_MONTGOMERY_ENABLED is defined, but no curve is supported for self-test" 3579 #endif 3580 ret = self_test_point( verbose, 3581 &grp, &R, &m, &grp.G, 3582 m_exponents, 3583 sizeof( m_exponents ) / sizeof( m_exponents[0] )); 3584 if( ret != 0 ) 3585 goto cleanup; 3586 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3587 3588 cleanup: 3589 3590 if( ret < 0 && verbose != 0 ) 3591 mbedtls_printf( "Unexpected error, return code = %08X\n", (unsigned int) ret ); 3592 3593 mbedtls_ecp_group_free( &grp ); 3594 mbedtls_ecp_point_free( &R ); 3595 mbedtls_ecp_point_free( &P ); 3596 mbedtls_mpi_free( &m ); 3597 3598 if( verbose != 0 ) 3599 mbedtls_printf( "\n" ); 3600 3601 return( ret ); 3602 } 3603 3604 #endif /* MBEDTLS_SELF_TEST */ 3605 3606 #endif /* !MBEDTLS_ECP_ALT */ 3607 3608 #endif /* MBEDTLS_ECP_C */ 3609