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