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