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 ) do { MBEDTLS_MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \ 1050 while( 0 ) 1051 1052 /* 1053 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi 1054 * N->s < 0 is a very fast test, which fails only if N is 0 1055 */ 1056 #define MOD_SUB( N ) \ 1057 while( N.s < 0 && mbedtls_mpi_cmp_int( &N, 0 ) != 0 ) \ 1058 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &N, &N, &grp->P ) ) 1059 1060 /* 1061 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int. 1062 * We known P, N and the result are positive, so sub_abs is correct, and 1063 * a bit faster. 1064 */ 1065 #define MOD_ADD( N ) \ 1066 while( mbedtls_mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \ 1067 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &N, &N, &grp->P ) ) 1068 1069 #if defined(ECP_SHORTWEIERSTRASS) 1070 /* 1071 * For curves in short Weierstrass form, we do all the internal operations in 1072 * Jacobian coordinates. 1073 * 1074 * For multiplication, we'll use a comb method with coutermeasueres against 1075 * SPA, hence timing attacks. 1076 */ 1077 1078 /* 1079 * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1) 1080 * Cost: 1N := 1I + 3M + 1S 1081 */ 1082 static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt ) 1083 { 1084 int ret; 1085 mbedtls_mpi Zi, ZZi; 1086 1087 if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 ) 1088 return( 0 ); 1089 1090 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) 1091 if( mbedtls_internal_ecp_grp_capable( grp ) ) 1092 return( mbedtls_internal_ecp_normalize_jac( grp, pt ) ); 1093 #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */ 1094 1095 mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi ); 1096 1097 /* 1098 * X = X / Z^2 mod p 1099 */ 1100 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z, &grp->P ) ); 1101 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); 1102 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X ); 1103 1104 /* 1105 * Y = Y / Z^3 mod p 1106 */ 1107 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y ); 1108 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y ); 1109 1110 /* 1111 * Z = 1 1112 */ 1113 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) ); 1114 1115 cleanup: 1116 1117 mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi ); 1118 1119 return( ret ); 1120 } 1121 1122 /* 1123 * Normalize jacobian coordinates of an array of (pointers to) points, 1124 * using Montgomery's trick to perform only one inversion mod P. 1125 * (See for example Cohen's "A Course in Computational Algebraic Number 1126 * Theory", Algorithm 10.3.4.) 1127 * 1128 * Warning: fails (returning an error) if one of the points is zero! 1129 * This should never happen, see choice of w in ecp_mul_comb(). 1130 * 1131 * Cost: 1N(t) := 1I + (6t - 3)M + 1S 1132 */ 1133 static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp, 1134 mbedtls_ecp_point *T[], size_t T_size ) 1135 { 1136 int ret; 1137 size_t i; 1138 mbedtls_mpi *c, u, Zi, ZZi; 1139 1140 if( T_size < 2 ) 1141 return( ecp_normalize_jac( grp, *T ) ); 1142 1143 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) 1144 if( mbedtls_internal_ecp_grp_capable( grp ) ) 1145 return( mbedtls_internal_ecp_normalize_jac_many( grp, T, T_size ) ); 1146 #endif 1147 1148 if( ( c = mbedtls_calloc( T_size, sizeof( mbedtls_mpi ) ) ) == NULL ) 1149 return( MBEDTLS_ERR_ECP_ALLOC_FAILED ); 1150 1151 for( i = 0; i < T_size; i++ ) 1152 mbedtls_mpi_init( &c[i] ); 1153 1154 mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi ); 1155 1156 /* 1157 * c[i] = Z_0 * ... * Z_i 1158 */ 1159 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) ); 1160 for( i = 1; i < T_size; i++ ) 1161 { 1162 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) ); 1163 MOD_MUL( c[i] ); 1164 } 1165 1166 /* 1167 * u = 1 / (Z_0 * ... * Z_n) mod P 1168 */ 1169 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[T_size-1], &grp->P ) ); 1170 1171 for( i = T_size - 1; ; i-- ) 1172 { 1173 /* 1174 * Zi = 1 / Z_i mod p 1175 * u = 1 / (Z_0 * ... * Z_i) mod P 1176 */ 1177 if( i == 0 ) { 1178 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) ); 1179 } 1180 else 1181 { 1182 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi ); 1183 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u ); 1184 } 1185 1186 /* 1187 * proceed as in normalize() 1188 */ 1189 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); 1190 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X ); 1191 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y ); 1192 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y ); 1193 1194 /* 1195 * Post-precessing: reclaim some memory by shrinking coordinates 1196 * - not storing Z (always 1) 1197 * - shrinking other coordinates, but still keeping the same number of 1198 * limbs as P, as otherwise it will too likely be regrown too fast. 1199 */ 1200 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) ); 1201 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) ); 1202 mbedtls_mpi_free( &T[i]->Z ); 1203 1204 if( i == 0 ) 1205 break; 1206 } 1207 1208 cleanup: 1209 1210 mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi ); 1211 for( i = 0; i < T_size; i++ ) 1212 mbedtls_mpi_free( &c[i] ); 1213 mbedtls_free( c ); 1214 1215 return( ret ); 1216 } 1217 1218 /* 1219 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak. 1220 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid 1221 */ 1222 static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp, 1223 mbedtls_ecp_point *Q, 1224 unsigned char inv ) 1225 { 1226 int ret; 1227 unsigned char nonzero; 1228 mbedtls_mpi mQY; 1229 1230 mbedtls_mpi_init( &mQY ); 1231 1232 /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */ 1233 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) ); 1234 nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0; 1235 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) ); 1236 1237 cleanup: 1238 mbedtls_mpi_free( &mQY ); 1239 1240 return( ret ); 1241 } 1242 1243 /* 1244 * Point doubling R = 2 P, Jacobian coordinates 1245 * 1246 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 . 1247 * 1248 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR 1249 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring. 1250 * 1251 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }. 1252 * 1253 * Cost: 1D := 3M + 4S (A == 0) 1254 * 4M + 4S (A == -3) 1255 * 3M + 6S + 1a otherwise 1256 */ 1257 static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1258 const mbedtls_ecp_point *P ) 1259 { 1260 int ret; 1261 mbedtls_mpi M, S, T, U; 1262 1263 #if defined(MBEDTLS_SELF_TEST) 1264 dbl_count++; 1265 #endif 1266 1267 #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) 1268 if( mbedtls_internal_ecp_grp_capable( grp ) ) 1269 return( mbedtls_internal_ecp_double_jac( grp, R, P ) ); 1270 #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */ 1271 1272 mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U ); 1273 1274 /* Special case for A = -3 */ 1275 if( grp->A.p == NULL ) 1276 { 1277 /* M = 3(X + Z^2)(X - Z^2) */ 1278 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S ); 1279 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T, &P->X, &S ) ); MOD_ADD( T ); 1280 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U, &P->X, &S ) ); MOD_SUB( U ); 1281 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &U ) ); MOD_MUL( S ); 1282 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); 1283 } 1284 else 1285 { 1286 /* M = 3.X^2 */ 1287 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &P->X ) ); MOD_MUL( S ); 1288 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); 1289 1290 /* Optimize away for "koblitz" curves with A = 0 */ 1291 if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 ) 1292 { 1293 /* M += A.Z^4 */ 1294 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S ); 1295 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &S, &S ) ); MOD_MUL( T ); 1296 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &grp->A ) ); MOD_MUL( S ); 1297 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M, &M, &S ) ); MOD_ADD( M ); 1298 } 1299 } 1300 1301 /* S = 4.X.Y^2 */ 1302 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &P->Y, &P->Y ) ); MOD_MUL( T ); 1303 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T, 1 ) ); MOD_ADD( T ); 1304 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &T ) ); MOD_MUL( S ); 1305 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S, 1 ) ); MOD_ADD( S ); 1306 1307 /* U = 8.Y^4 */ 1308 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &T, &T ) ); MOD_MUL( U ); 1309 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); 1310 1311 /* T = M^2 - 2.S */ 1312 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &M, &M ) ); MOD_MUL( T ); 1313 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); 1314 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); 1315 1316 /* S = M(S - T) - U */ 1317 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &T ) ); MOD_SUB( S ); 1318 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &S, &M ) ); MOD_MUL( S ); 1319 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &U ) ); MOD_SUB( S ); 1320 1321 /* U = 2.Y.Z */ 1322 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &P->Y, &P->Z ) ); MOD_MUL( U ); 1323 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); 1324 1325 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) ); 1326 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) ); 1327 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) ); 1328 1329 cleanup: 1330 mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U ); 1331 1332 return( ret ); 1333 } 1334 1335 /* 1336 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22) 1337 * 1338 * The coordinates of Q must be normalized (= affine), 1339 * but those of P don't need to. R is not normalized. 1340 * 1341 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q. 1342 * None of these cases can happen as intermediate step in ecp_mul_comb(): 1343 * - at each step, P, Q and R are multiples of the base point, the factor 1344 * being less than its order, so none of them is zero; 1345 * - Q is an odd multiple of the base point, P an even multiple, 1346 * due to the choice of precomputed points in the modified comb method. 1347 * So branches for these cases do not leak secret information. 1348 * 1349 * We accept Q->Z being unset (saving memory in tables) as meaning 1. 1350 * 1351 * Cost: 1A := 8M + 3S 1352 */ 1353 static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1354 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q ) 1355 { 1356 int ret; 1357 mbedtls_mpi T1, T2, T3, T4, X, Y, Z; 1358 1359 #if defined(MBEDTLS_SELF_TEST) 1360 add_count++; 1361 #endif 1362 1363 #if defined(MBEDTLS_ECP_ADD_MIXED_ALT) 1364 if( mbedtls_internal_ecp_grp_capable( grp ) ) 1365 return( mbedtls_internal_ecp_add_mixed( grp, R, P, Q ) ); 1366 #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */ 1367 1368 /* 1369 * Trivial cases: P == 0 or Q == 0 (case 1) 1370 */ 1371 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 ) 1372 return( mbedtls_ecp_copy( R, Q ) ); 1373 1374 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 ) 1375 return( mbedtls_ecp_copy( R, P ) ); 1376 1377 /* 1378 * Make sure Q coordinates are normalized 1379 */ 1380 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 ) 1381 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 1382 1383 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 ); 1384 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z ); 1385 1386 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 ); 1387 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 ); 1388 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 ); 1389 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 ); 1390 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 ); 1391 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 ); 1392 1393 /* Special cases (2) and (3) */ 1394 if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 ) 1395 { 1396 if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 ) 1397 { 1398 ret = ecp_double_jac( grp, R, P ); 1399 goto cleanup; 1400 } 1401 else 1402 { 1403 ret = mbedtls_ecp_set_zero( R ); 1404 goto cleanup; 1405 } 1406 } 1407 1408 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z ); 1409 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 ); 1410 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 ); 1411 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 ); 1412 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 ); 1413 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X ); 1414 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X ); 1415 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X ); 1416 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 ); 1417 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 ); 1418 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 ); 1419 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y ); 1420 1421 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) ); 1422 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) ); 1423 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) ); 1424 1425 cleanup: 1426 1427 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 ); 1428 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z ); 1429 1430 return( ret ); 1431 } 1432 1433 /* 1434 * Randomize jacobian coordinates: 1435 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l 1436 * This is sort of the reverse operation of ecp_normalize_jac(). 1437 * 1438 * This countermeasure was first suggested in [2]. 1439 */ 1440 static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, 1441 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 1442 { 1443 int ret; 1444 mbedtls_mpi l, ll; 1445 size_t p_size; 1446 int count = 0; 1447 1448 #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) 1449 if( mbedtls_internal_ecp_grp_capable( grp ) ) 1450 return( mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng ) ); 1451 #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */ 1452 1453 p_size = ( grp->pbits + 7 ) / 8; 1454 mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll ); 1455 1456 /* Generate l such that 1 < l < p */ 1457 do 1458 { 1459 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) ); 1460 1461 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) 1462 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) ); 1463 1464 if( count++ > 10 ) 1465 return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); 1466 } 1467 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ); 1468 1469 /* Z = l * Z */ 1470 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z ); 1471 1472 /* X = l^2 * X */ 1473 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll ); 1474 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X ); 1475 1476 /* Y = l^3 * Y */ 1477 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll ); 1478 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y ); 1479 1480 cleanup: 1481 mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll ); 1482 1483 return( ret ); 1484 } 1485 1486 /* 1487 * Check and define parameters used by the comb method (see below for details) 1488 */ 1489 #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7 1490 #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds" 1491 #endif 1492 1493 /* d = ceil( n / w ) */ 1494 #define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2 1495 1496 /* number of precomputed points */ 1497 #define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) ) 1498 1499 /* 1500 * Compute the representation of m that will be used with our comb method. 1501 * 1502 * The basic comb method is described in GECC 3.44 for example. We use a 1503 * modified version that provides resistance to SPA by avoiding zero 1504 * digits in the representation as in [3]. We modify the method further by 1505 * requiring that all K_i be odd, which has the small cost that our 1506 * representation uses one more K_i, due to carries, but saves on the size of 1507 * the precomputed table. 1508 * 1509 * Summary of the comb method and its modifications: 1510 * 1511 * - The goal is to compute m*P for some w*d-bit integer m. 1512 * 1513 * - The basic comb method splits m into the w-bit integers 1514 * x[0] .. x[d-1] where x[i] consists of the bits in m whose 1515 * index has residue i modulo d, and computes m * P as 1516 * S[x[0]] + 2 * S[x[1]] + .. + 2^(d-1) S[x[d-1]], where 1517 * S[i_{w-1} .. i_0] := i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + i_0 P. 1518 * 1519 * - If it happens that, say, x[i+1]=0 (=> S[x[i+1]]=0), one can replace the sum by 1520 * .. + 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]] .., 1521 * thereby successively converting it into a form where all summands 1522 * are nonzero, at the cost of negative summands. This is the basic idea of [3]. 1523 * 1524 * - More generally, even if x[i+1] != 0, we can first transform the sum as 1525 * .. - 2^i S[x[i]] + 2^{i+1} ( S[x[i]] + S[x[i+1]] ) + 2^{i+2} S[x[i+2]] .., 1526 * and then replace S[x[i]] + S[x[i+1]] = S[x[i] ^ x[i+1]] + 2 S[x[i] & x[i+1]]. 1527 * Performing and iterating this procedure for those x[i] that are even 1528 * (keeping track of carry), we can transform the original sum into one of the form 1529 * S[x'[0]] +- 2 S[x'[1]] +- .. +- 2^{d-1} S[x'[d-1]] + 2^d S[x'[d]] 1530 * with all x'[i] odd. It is therefore only necessary to know S at odd indices, 1531 * which is why we are only computing half of it in the first place in 1532 * ecp_precompute_comb and accessing it with index abs(i) / 2 in ecp_select_comb. 1533 * 1534 * - For the sake of compactness, only the seven low-order bits of x[i] 1535 * are used to represent its absolute value (K_i in the paper), and the msb 1536 * of x[i] encodes the sign (s_i in the paper): it is set if and only if 1537 * if s_i == -1; 1538 * 1539 * Calling conventions: 1540 * - x is an array of size d + 1 1541 * - w is the size, ie number of teeth, of the comb, and must be between 1542 * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE) 1543 * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d 1544 * (the result will be incorrect if these assumptions are not satisfied) 1545 */ 1546 static void ecp_comb_recode_core( unsigned char x[], size_t d, 1547 unsigned char w, const mbedtls_mpi *m ) 1548 { 1549 size_t i, j; 1550 unsigned char c, cc, adjust; 1551 1552 memset( x, 0, d+1 ); 1553 1554 /* First get the classical comb values (except for x_d = 0) */ 1555 for( i = 0; i < d; i++ ) 1556 for( j = 0; j < w; j++ ) 1557 x[i] |= mbedtls_mpi_get_bit( m, i + d * j ) << j; 1558 1559 /* Now make sure x_1 .. x_d are odd */ 1560 c = 0; 1561 for( i = 1; i <= d; i++ ) 1562 { 1563 /* Add carry and update it */ 1564 cc = x[i] & c; 1565 x[i] = x[i] ^ c; 1566 c = cc; 1567 1568 /* Adjust if needed, avoiding branches */ 1569 adjust = 1 - ( x[i] & 0x01 ); 1570 c |= x[i] & ( x[i-1] * adjust ); 1571 x[i] = x[i] ^ ( x[i-1] * adjust ); 1572 x[i-1] |= adjust << 7; 1573 } 1574 } 1575 1576 /* 1577 * Precompute points for the adapted comb method 1578 * 1579 * Assumption: T must be able to hold 2^{w - 1} elements. 1580 * 1581 * Operation: If i = i_{w-1} ... i_1 is the binary representation of i, 1582 * sets T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P. 1583 * 1584 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1) 1585 * 1586 * Note: Even comb values (those where P would be omitted from the 1587 * sum defining T[i] above) are not needed in our adaption 1588 * the comb method. See ecp_comb_recode_core(). 1589 * 1590 * This function currently works in four steps: 1591 * (1) [dbl] Computation of intermediate T[i] for 2-power values of i 1592 * (2) [norm_dbl] Normalization of coordinates of these T[i] 1593 * (3) [add] Computation of all T[i] 1594 * (4) [norm_add] Normalization of all T[i] 1595 * 1596 * Step 1 can be interrupted but not the others; together with the final 1597 * coordinate normalization they are the largest steps done at once, depending 1598 * on the window size. Here are operation counts for P-256: 1599 * 1600 * step (2) (3) (4) 1601 * w = 5 142 165 208 1602 * w = 4 136 77 160 1603 * w = 3 130 33 136 1604 * w = 2 124 11 124 1605 * 1606 * So if ECC operations are blocking for too long even with a low max_ops 1607 * value, it's useful to set MBEDTLS_ECP_WINDOW_SIZE to a lower value in order 1608 * to minimize maximum blocking time. 1609 */ 1610 static int ecp_precompute_comb( const mbedtls_ecp_group *grp, 1611 mbedtls_ecp_point T[], const mbedtls_ecp_point *P, 1612 unsigned char w, size_t d, 1613 mbedtls_ecp_restart_ctx *rs_ctx ) 1614 { 1615 int ret; 1616 unsigned char i; 1617 size_t j = 0; 1618 const unsigned char T_size = 1U << ( w - 1 ); 1619 mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1]; 1620 1621 #if defined(MBEDTLS_ECP_RESTARTABLE) 1622 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1623 { 1624 if( rs_ctx->rsm->state == ecp_rsm_pre_dbl ) 1625 goto dbl; 1626 if( rs_ctx->rsm->state == ecp_rsm_pre_norm_dbl ) 1627 goto norm_dbl; 1628 if( rs_ctx->rsm->state == ecp_rsm_pre_add ) 1629 goto add; 1630 if( rs_ctx->rsm->state == ecp_rsm_pre_norm_add ) 1631 goto norm_add; 1632 } 1633 #else 1634 (void) rs_ctx; 1635 #endif 1636 1637 #if defined(MBEDTLS_ECP_RESTARTABLE) 1638 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1639 { 1640 rs_ctx->rsm->state = ecp_rsm_pre_dbl; 1641 1642 /* initial state for the loop */ 1643 rs_ctx->rsm->i = 0; 1644 } 1645 1646 dbl: 1647 #endif 1648 /* 1649 * Set T[0] = P and 1650 * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value) 1651 */ 1652 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) ); 1653 1654 #if defined(MBEDTLS_ECP_RESTARTABLE) 1655 if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0 ) 1656 j = rs_ctx->rsm->i; 1657 else 1658 #endif 1659 j = 0; 1660 1661 for( ; j < d * ( w - 1 ); j++ ) 1662 { 1663 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL ); 1664 1665 i = 1U << ( j / d ); 1666 cur = T + i; 1667 1668 if( j % d == 0 ) 1669 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) ); 1670 1671 MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) ); 1672 } 1673 1674 #if defined(MBEDTLS_ECP_RESTARTABLE) 1675 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1676 rs_ctx->rsm->state = ecp_rsm_pre_norm_dbl; 1677 1678 norm_dbl: 1679 #endif 1680 /* 1681 * Normalize current elements in T. As T has holes, 1682 * use an auxiliary array of pointers to elements in T. 1683 */ 1684 j = 0; 1685 for( i = 1; i < T_size; i <<= 1 ) 1686 TT[j++] = T + i; 1687 1688 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 ); 1689 1690 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) ); 1691 1692 #if defined(MBEDTLS_ECP_RESTARTABLE) 1693 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1694 rs_ctx->rsm->state = ecp_rsm_pre_add; 1695 1696 add: 1697 #endif 1698 /* 1699 * Compute the remaining ones using the minimal number of additions 1700 * Be careful to update T[2^l] only after using it! 1701 */ 1702 MBEDTLS_ECP_BUDGET( ( T_size - 1 ) * MBEDTLS_ECP_OPS_ADD ); 1703 1704 for( i = 1; i < T_size; i <<= 1 ) 1705 { 1706 j = i; 1707 while( j-- ) 1708 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) ); 1709 } 1710 1711 #if defined(MBEDTLS_ECP_RESTARTABLE) 1712 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1713 rs_ctx->rsm->state = ecp_rsm_pre_norm_add; 1714 1715 norm_add: 1716 #endif 1717 /* 1718 * Normalize final elements in T. Even though there are no holes now, we 1719 * still need the auxiliary array for homogeneity with the previous 1720 * call. Also, skip T[0] which is already normalised, being a copy of P. 1721 */ 1722 for( j = 0; j + 1 < T_size; j++ ) 1723 TT[j] = T + j + 1; 1724 1725 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 ); 1726 1727 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) ); 1728 1729 cleanup: 1730 #if defined(MBEDTLS_ECP_RESTARTABLE) 1731 if( rs_ctx != NULL && rs_ctx->rsm != NULL && 1732 ret == MBEDTLS_ERR_ECP_IN_PROGRESS ) 1733 { 1734 if( rs_ctx->rsm->state == ecp_rsm_pre_dbl ) 1735 rs_ctx->rsm->i = j; 1736 } 1737 #endif 1738 1739 return( ret ); 1740 } 1741 1742 /* 1743 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ] 1744 * 1745 * See ecp_comb_recode_core() for background 1746 */ 1747 static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1748 const mbedtls_ecp_point T[], unsigned char T_size, 1749 unsigned char i ) 1750 { 1751 int ret; 1752 unsigned char ii, j; 1753 1754 /* Ignore the "sign" bit and scale down */ 1755 ii = ( i & 0x7Fu ) >> 1; 1756 1757 /* Read the whole table to thwart cache-based timing attacks */ 1758 for( j = 0; j < T_size; j++ ) 1759 { 1760 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) ); 1761 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) ); 1762 } 1763 1764 /* Safely invert result if i is "negative" */ 1765 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) ); 1766 1767 cleanup: 1768 return( ret ); 1769 } 1770 1771 /* 1772 * Core multiplication algorithm for the (modified) comb method. 1773 * This part is actually common with the basic comb method (GECC 3.44) 1774 * 1775 * Cost: d A + d D + 1 R 1776 */ 1777 static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1778 const mbedtls_ecp_point T[], unsigned char T_size, 1779 const unsigned char x[], size_t d, 1780 int (*f_rng)(void *, unsigned char *, size_t), 1781 void *p_rng, 1782 mbedtls_ecp_restart_ctx *rs_ctx ) 1783 { 1784 int ret; 1785 mbedtls_ecp_point Txi; 1786 size_t i; 1787 1788 mbedtls_ecp_point_init( &Txi ); 1789 1790 #if !defined(MBEDTLS_ECP_RESTARTABLE) 1791 (void) rs_ctx; 1792 #endif 1793 1794 #if defined(MBEDTLS_ECP_RESTARTABLE) 1795 if( rs_ctx != NULL && rs_ctx->rsm != NULL && 1796 rs_ctx->rsm->state != ecp_rsm_comb_core ) 1797 { 1798 rs_ctx->rsm->i = 0; 1799 rs_ctx->rsm->state = ecp_rsm_comb_core; 1800 } 1801 1802 /* new 'if' instead of nested for the sake of the 'else' branch */ 1803 if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0 ) 1804 { 1805 /* restore current index (R already pointing to rs_ctx->rsm->R) */ 1806 i = rs_ctx->rsm->i; 1807 } 1808 else 1809 #endif 1810 { 1811 /* Start with a non-zero point and randomize its coordinates */ 1812 i = d; 1813 MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, T_size, x[i] ) ); 1814 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 1 ) ); 1815 if( f_rng != 0 ) 1816 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) ); 1817 } 1818 1819 while( i != 0 ) 1820 { 1821 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD ); 1822 --i; 1823 1824 MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) ); 1825 MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, T_size, x[i] ) ); 1826 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) ); 1827 } 1828 1829 cleanup: 1830 1831 mbedtls_ecp_point_free( &Txi ); 1832 1833 #if defined(MBEDTLS_ECP_RESTARTABLE) 1834 if( rs_ctx != NULL && rs_ctx->rsm != NULL && 1835 ret == MBEDTLS_ERR_ECP_IN_PROGRESS ) 1836 { 1837 rs_ctx->rsm->i = i; 1838 /* no need to save R, already pointing to rs_ctx->rsm->R */ 1839 } 1840 #endif 1841 1842 return( ret ); 1843 } 1844 1845 /* 1846 * Recode the scalar to get constant-time comb multiplication 1847 * 1848 * As the actual scalar recoding needs an odd scalar as a starting point, 1849 * this wrapper ensures that by replacing m by N - m if necessary, and 1850 * informs the caller that the result of multiplication will be negated. 1851 * 1852 * This works because we only support large prime order for Short Weierstrass 1853 * curves, so N is always odd hence either m or N - m is. 1854 * 1855 * See ecp_comb_recode_core() for background. 1856 */ 1857 static int ecp_comb_recode_scalar( const mbedtls_ecp_group *grp, 1858 const mbedtls_mpi *m, 1859 unsigned char k[COMB_MAX_D + 1], 1860 size_t d, 1861 unsigned char w, 1862 unsigned char *parity_trick ) 1863 { 1864 int ret; 1865 mbedtls_mpi M, mm; 1866 1867 mbedtls_mpi_init( &M ); 1868 mbedtls_mpi_init( &mm ); 1869 1870 /* N is always odd (see above), just make extra sure */ 1871 if( mbedtls_mpi_get_bit( &grp->N, 0 ) != 1 ) 1872 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 1873 1874 /* do we need the parity trick? */ 1875 *parity_trick = ( mbedtls_mpi_get_bit( m, 0 ) == 0 ); 1876 1877 /* execute parity fix in constant time */ 1878 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) ); 1879 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N, m ) ); 1880 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, *parity_trick ) ); 1881 1882 /* actual scalar recoding */ 1883 ecp_comb_recode_core( k, d, w, &M ); 1884 1885 cleanup: 1886 mbedtls_mpi_free( &mm ); 1887 mbedtls_mpi_free( &M ); 1888 1889 return( ret ); 1890 } 1891 1892 /* 1893 * Perform comb multiplication (for short Weierstrass curves) 1894 * once the auxiliary table has been pre-computed. 1895 * 1896 * Scalar recoding may use a parity trick that makes us compute -m * P, 1897 * if that is the case we'll need to recover m * P at the end. 1898 */ 1899 static int ecp_mul_comb_after_precomp( const mbedtls_ecp_group *grp, 1900 mbedtls_ecp_point *R, 1901 const mbedtls_mpi *m, 1902 const mbedtls_ecp_point *T, 1903 unsigned char T_size, 1904 unsigned char w, 1905 size_t d, 1906 int (*f_rng)(void *, unsigned char *, size_t), 1907 void *p_rng, 1908 mbedtls_ecp_restart_ctx *rs_ctx ) 1909 { 1910 int ret; 1911 unsigned char parity_trick; 1912 unsigned char k[COMB_MAX_D + 1]; 1913 mbedtls_ecp_point *RR = R; 1914 1915 #if defined(MBEDTLS_ECP_RESTARTABLE) 1916 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1917 { 1918 RR = &rs_ctx->rsm->R; 1919 1920 if( rs_ctx->rsm->state == ecp_rsm_final_norm ) 1921 goto final_norm; 1922 } 1923 #endif 1924 1925 MBEDTLS_MPI_CHK( ecp_comb_recode_scalar( grp, m, k, d, w, 1926 &parity_trick ) ); 1927 MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, RR, T, T_size, k, d, 1928 f_rng, p_rng, rs_ctx ) ); 1929 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, RR, parity_trick ) ); 1930 1931 #if defined(MBEDTLS_ECP_RESTARTABLE) 1932 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1933 rs_ctx->rsm->state = ecp_rsm_final_norm; 1934 1935 final_norm: 1936 #endif 1937 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV ); 1938 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, RR ) ); 1939 1940 #if defined(MBEDTLS_ECP_RESTARTABLE) 1941 if( rs_ctx != NULL && rs_ctx->rsm != NULL ) 1942 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, RR ) ); 1943 #endif 1944 1945 cleanup: 1946 return( ret ); 1947 } 1948 1949 /* 1950 * Pick window size based on curve size and whether we optimize for base point 1951 */ 1952 static unsigned char ecp_pick_window_size( const mbedtls_ecp_group *grp, 1953 unsigned char p_eq_g ) 1954 { 1955 unsigned char w; 1956 1957 /* 1958 * Minimize the number of multiplications, that is minimize 1959 * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w ) 1960 * (see costs of the various parts, with 1S = 1M) 1961 */ 1962 w = grp->nbits >= 384 ? 5 : 4; 1963 1964 /* 1965 * If P == G, pre-compute a bit more, since this may be re-used later. 1966 * Just adding one avoids upping the cost of the first mul too much, 1967 * and the memory cost too. 1968 */ 1969 if( p_eq_g ) 1970 w++; 1971 1972 /* 1973 * Make sure w is within bounds. 1974 * (The last test is useful only for very small curves in the test suite.) 1975 */ 1976 if( w > MBEDTLS_ECP_WINDOW_SIZE ) 1977 w = MBEDTLS_ECP_WINDOW_SIZE; 1978 if( w >= grp->nbits ) 1979 w = 2; 1980 1981 return( w ); 1982 } 1983 1984 /* 1985 * Multiplication using the comb method - for curves in short Weierstrass form 1986 * 1987 * This function is mainly responsible for administrative work: 1988 * - managing the restart context if enabled 1989 * - managing the table of precomputed points (passed between the below two 1990 * functions): allocation, computation, ownership tranfer, freeing. 1991 * 1992 * It delegates the actual arithmetic work to: 1993 * ecp_precompute_comb() and ecp_mul_comb_with_precomp() 1994 * 1995 * See comments on ecp_comb_recode_core() regarding the computation strategy. 1996 */ 1997 static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1998 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 1999 int (*f_rng)(void *, unsigned char *, size_t), 2000 void *p_rng, 2001 mbedtls_ecp_restart_ctx *rs_ctx ) 2002 { 2003 int ret; 2004 unsigned char w, p_eq_g, i; 2005 size_t d; 2006 unsigned char T_size, T_ok; 2007 mbedtls_ecp_point *T; 2008 2009 ECP_RS_ENTER( rsm ); 2010 2011 /* Is P the base point ? */ 2012 #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1 2013 p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 && 2014 mbedtls_mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 ); 2015 #else 2016 p_eq_g = 0; 2017 #endif 2018 2019 /* Pick window size and deduce related sizes */ 2020 w = ecp_pick_window_size( grp, p_eq_g ); 2021 T_size = 1U << ( w - 1 ); 2022 d = ( grp->nbits + w - 1 ) / w; 2023 2024 /* Pre-computed table: do we have it already for the base point? */ 2025 if( p_eq_g && grp->T != NULL ) 2026 { 2027 /* second pointer to the same table, will be deleted on exit */ 2028 T = grp->T; 2029 T_ok = 1; 2030 } 2031 else 2032 #if defined(MBEDTLS_ECP_RESTARTABLE) 2033 /* Pre-computed table: do we have one in progress? complete? */ 2034 if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->T != NULL ) 2035 { 2036 /* transfer ownership of T from rsm to local function */ 2037 T = rs_ctx->rsm->T; 2038 rs_ctx->rsm->T = NULL; 2039 rs_ctx->rsm->T_size = 0; 2040 2041 /* This effectively jumps to the call to mul_comb_after_precomp() */ 2042 T_ok = rs_ctx->rsm->state >= ecp_rsm_comb_core; 2043 } 2044 else 2045 #endif 2046 /* Allocate table if we didn't have any */ 2047 { 2048 T = mbedtls_calloc( T_size, sizeof( mbedtls_ecp_point ) ); 2049 if( T == NULL ) 2050 { 2051 ret = MBEDTLS_ERR_ECP_ALLOC_FAILED; 2052 goto cleanup; 2053 } 2054 2055 for( i = 0; i < T_size; i++ ) 2056 mbedtls_ecp_point_init( &T[i] ); 2057 2058 T_ok = 0; 2059 } 2060 2061 /* Compute table (or finish computing it) if not done already */ 2062 if( !T_ok ) 2063 { 2064 MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d, rs_ctx ) ); 2065 2066 if( p_eq_g ) 2067 { 2068 /* almost transfer ownership of T to the group, but keep a copy of 2069 * the pointer to use for calling the next function more easily */ 2070 grp->T = T; 2071 grp->T_size = T_size; 2072 } 2073 } 2074 2075 /* Actual comb multiplication using precomputed points */ 2076 MBEDTLS_MPI_CHK( ecp_mul_comb_after_precomp( grp, R, m, 2077 T, T_size, w, d, 2078 f_rng, p_rng, rs_ctx ) ); 2079 2080 cleanup: 2081 2082 /* does T belong to the group? */ 2083 if( T == grp->T ) 2084 T = NULL; 2085 2086 /* does T belong to the restart context? */ 2087 #if defined(MBEDTLS_ECP_RESTARTABLE) 2088 if( rs_ctx != NULL && rs_ctx->rsm != NULL && ret == MBEDTLS_ERR_ECP_IN_PROGRESS && T != NULL ) 2089 { 2090 /* transfer ownership of T from local function to rsm */ 2091 rs_ctx->rsm->T_size = T_size; 2092 rs_ctx->rsm->T = T; 2093 T = NULL; 2094 } 2095 #endif 2096 2097 /* did T belong to us? then let's destroy it! */ 2098 if( T != NULL ) 2099 { 2100 for( i = 0; i < T_size; i++ ) 2101 mbedtls_ecp_point_free( &T[i] ); 2102 mbedtls_free( T ); 2103 } 2104 2105 /* don't free R while in progress in case R == P */ 2106 #if defined(MBEDTLS_ECP_RESTARTABLE) 2107 if( ret != MBEDTLS_ERR_ECP_IN_PROGRESS ) 2108 #endif 2109 /* prevent caller from using invalid value */ 2110 if( ret != 0 ) 2111 mbedtls_ecp_point_free( R ); 2112 2113 ECP_RS_LEAVE( rsm ); 2114 2115 return( ret ); 2116 } 2117 2118 #endif /* ECP_SHORTWEIERSTRASS */ 2119 2120 #if defined(ECP_MONTGOMERY) 2121 /* 2122 * For Montgomery curves, we do all the internal arithmetic in projective 2123 * coordinates. Import/export of points uses only the x coordinates, which is 2124 * internaly represented as X / Z. 2125 * 2126 * For scalar multiplication, we'll use a Montgomery ladder. 2127 */ 2128 2129 /* 2130 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1 2131 * Cost: 1M + 1I 2132 */ 2133 static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P ) 2134 { 2135 int ret; 2136 2137 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) 2138 if( mbedtls_internal_ecp_grp_capable( grp ) ) 2139 return( mbedtls_internal_ecp_normalize_mxz( grp, P ) ); 2140 #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */ 2141 2142 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) ); 2143 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X ); 2144 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) ); 2145 2146 cleanup: 2147 return( ret ); 2148 } 2149 2150 /* 2151 * Randomize projective x/z coordinates: 2152 * (X, Z) -> (l X, l Z) for random l 2153 * This is sort of the reverse operation of ecp_normalize_mxz(). 2154 * 2155 * This countermeasure was first suggested in [2]. 2156 * Cost: 2M 2157 */ 2158 static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P, 2159 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 2160 { 2161 int ret; 2162 mbedtls_mpi l; 2163 size_t p_size; 2164 int count = 0; 2165 2166 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) 2167 if( mbedtls_internal_ecp_grp_capable( grp ) ) 2168 return( mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng ); 2169 #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */ 2170 2171 p_size = ( grp->pbits + 7 ) / 8; 2172 mbedtls_mpi_init( &l ); 2173 2174 /* Generate l such that 1 < l < p */ 2175 do 2176 { 2177 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) ); 2178 2179 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) 2180 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) ); 2181 2182 if( count++ > 10 ) 2183 return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); 2184 } 2185 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ); 2186 2187 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X ); 2188 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z ); 2189 2190 cleanup: 2191 mbedtls_mpi_free( &l ); 2192 2193 return( ret ); 2194 } 2195 2196 /* 2197 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q), 2198 * for Montgomery curves in x/z coordinates. 2199 * 2200 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3 2201 * with 2202 * d = X1 2203 * P = (X2, Z2) 2204 * Q = (X3, Z3) 2205 * R = (X4, Z4) 2206 * S = (X5, Z5) 2207 * and eliminating temporary variables tO, ..., t4. 2208 * 2209 * Cost: 5M + 4S 2210 */ 2211 static int ecp_double_add_mxz( const mbedtls_ecp_group *grp, 2212 mbedtls_ecp_point *R, mbedtls_ecp_point *S, 2213 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q, 2214 const mbedtls_mpi *d ) 2215 { 2216 int ret; 2217 mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB; 2218 2219 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) 2220 if( mbedtls_internal_ecp_grp_capable( grp ) ) 2221 return( mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d ) ); 2222 #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */ 2223 2224 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B ); 2225 mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C ); 2226 mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB ); 2227 2228 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A ); 2229 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA ); 2230 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B ); 2231 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB ); 2232 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E ); 2233 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C ); 2234 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D ); 2235 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA ); 2236 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB ); 2237 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X ); 2238 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X ); 2239 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z ); 2240 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z ); 2241 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z ); 2242 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X ); 2243 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z ); 2244 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z ); 2245 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z ); 2246 2247 cleanup: 2248 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B ); 2249 mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C ); 2250 mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB ); 2251 2252 return( ret ); 2253 } 2254 2255 /* 2256 * Multiplication with Montgomery ladder in x/z coordinates, 2257 * for curves in Montgomery form 2258 */ 2259 static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2260 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2261 int (*f_rng)(void *, unsigned char *, size_t), 2262 void *p_rng ) 2263 { 2264 int ret; 2265 size_t i; 2266 unsigned char b; 2267 mbedtls_ecp_point RP; 2268 mbedtls_mpi PX; 2269 2270 mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX ); 2271 2272 /* Save PX and read from P before writing to R, in case P == R */ 2273 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) ); 2274 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) ); 2275 2276 /* Set R to zero in modified x/z coordinates */ 2277 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X, 1 ) ); 2278 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) ); 2279 mbedtls_mpi_free( &R->Y ); 2280 2281 /* RP.X might be sligtly larger than P, so reduce it */ 2282 MOD_ADD( RP.X ); 2283 2284 /* Randomize coordinates of the starting point */ 2285 if( f_rng != NULL ) 2286 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) ); 2287 2288 /* Loop invariant: R = result so far, RP = R + P */ 2289 i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */ 2290 while( i-- > 0 ) 2291 { 2292 b = mbedtls_mpi_get_bit( m, i ); 2293 /* 2294 * if (b) R = 2R + P else R = 2R, 2295 * which is: 2296 * if (b) double_add( RP, R, RP, R ) 2297 * else double_add( R, RP, R, RP ) 2298 * but using safe conditional swaps to avoid leaks 2299 */ 2300 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) ); 2301 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); 2302 MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) ); 2303 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) ); 2304 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); 2305 } 2306 2307 MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) ); 2308 2309 cleanup: 2310 mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX ); 2311 2312 return( ret ); 2313 } 2314 2315 #endif /* ECP_MONTGOMERY */ 2316 2317 /* 2318 * Restartable multiplication R = m * P 2319 */ 2320 int mbedtls_ecp_mul_restartable( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2321 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2322 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng, 2323 mbedtls_ecp_restart_ctx *rs_ctx ) 2324 { 2325 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2326 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2327 char is_grp_capable = 0; 2328 #endif 2329 ECP_VALIDATE_RET( grp != NULL ); 2330 ECP_VALIDATE_RET( R != NULL ); 2331 ECP_VALIDATE_RET( m != NULL ); 2332 ECP_VALIDATE_RET( P != NULL ); 2333 2334 #if defined(MBEDTLS_ECP_RESTARTABLE) 2335 /* reset ops count for this call if top-level */ 2336 if( rs_ctx != NULL && rs_ctx->depth++ == 0 ) 2337 rs_ctx->ops_done = 0; 2338 #endif 2339 2340 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2341 if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) ) 2342 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); 2343 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2344 2345 #if defined(MBEDTLS_ECP_RESTARTABLE) 2346 /* skip argument check when restarting */ 2347 if( rs_ctx == NULL || rs_ctx->rsm == NULL ) 2348 #endif 2349 { 2350 /* check_privkey is free */ 2351 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_CHK ); 2352 2353 /* Common sanity checks */ 2354 MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( grp, m ) ); 2355 MBEDTLS_MPI_CHK( mbedtls_ecp_check_pubkey( grp, P ) ); 2356 } 2357 2358 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2359 #if defined(ECP_MONTGOMERY) 2360 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 2361 MBEDTLS_MPI_CHK( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) ); 2362 #endif 2363 #if defined(ECP_SHORTWEIERSTRASS) 2364 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 2365 MBEDTLS_MPI_CHK( ecp_mul_comb( grp, R, m, P, f_rng, p_rng, rs_ctx ) ); 2366 #endif 2367 2368 cleanup: 2369 2370 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2371 if( is_grp_capable ) 2372 mbedtls_internal_ecp_free( grp ); 2373 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2374 2375 #if defined(MBEDTLS_ECP_RESTARTABLE) 2376 if( rs_ctx != NULL ) 2377 rs_ctx->depth--; 2378 #endif 2379 2380 return( ret ); 2381 } 2382 2383 /* 2384 * Multiplication R = m * P 2385 */ 2386 int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2387 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2388 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 2389 { 2390 ECP_VALIDATE_RET( grp != NULL ); 2391 ECP_VALIDATE_RET( R != NULL ); 2392 ECP_VALIDATE_RET( m != NULL ); 2393 ECP_VALIDATE_RET( P != NULL ); 2394 return( mbedtls_ecp_mul_restartable( grp, R, m, P, f_rng, p_rng, NULL ) ); 2395 } 2396 2397 #if defined(ECP_SHORTWEIERSTRASS) 2398 /* 2399 * Check that an affine point is valid as a public key, 2400 * short weierstrass curves (SEC1 3.2.3.1) 2401 */ 2402 static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 2403 { 2404 int ret; 2405 mbedtls_mpi YY, RHS; 2406 2407 /* pt coordinates must be normalized for our checks */ 2408 if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 || 2409 mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 || 2410 mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 || 2411 mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 ) 2412 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2413 2414 mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS ); 2415 2416 /* 2417 * YY = Y^2 2418 * RHS = X (X^2 + A) + B = X^3 + A X + B 2419 */ 2420 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY ); 2421 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS ); 2422 2423 /* Special case for A = -3 */ 2424 if( grp->A.p == NULL ) 2425 { 2426 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS ); 2427 } 2428 else 2429 { 2430 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS ); 2431 } 2432 2433 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS ); 2434 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS ); 2435 2436 if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 ) 2437 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 2438 2439 cleanup: 2440 2441 mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS ); 2442 2443 return( ret ); 2444 } 2445 #endif /* ECP_SHORTWEIERSTRASS */ 2446 2447 /* 2448 * R = m * P with shortcuts for m == 1 and m == -1 2449 * NOT constant-time - ONLY for short Weierstrass! 2450 */ 2451 static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp, 2452 mbedtls_ecp_point *R, 2453 const mbedtls_mpi *m, 2454 const mbedtls_ecp_point *P, 2455 mbedtls_ecp_restart_ctx *rs_ctx ) 2456 { 2457 int ret; 2458 2459 if( mbedtls_mpi_cmp_int( m, 1 ) == 0 ) 2460 { 2461 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); 2462 } 2463 else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 ) 2464 { 2465 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); 2466 if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 ) 2467 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) ); 2468 } 2469 else 2470 { 2471 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_restartable( grp, R, m, P, 2472 NULL, NULL, rs_ctx ) ); 2473 } 2474 2475 cleanup: 2476 return( ret ); 2477 } 2478 2479 /* 2480 * Restartable linear combination 2481 * NOT constant-time 2482 */ 2483 int mbedtls_ecp_muladd_restartable( 2484 mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2485 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2486 const mbedtls_mpi *n, const mbedtls_ecp_point *Q, 2487 mbedtls_ecp_restart_ctx *rs_ctx ) 2488 { 2489 int ret; 2490 mbedtls_ecp_point mP; 2491 mbedtls_ecp_point *pmP = &mP; 2492 mbedtls_ecp_point *pR = R; 2493 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2494 char is_grp_capable = 0; 2495 #endif 2496 ECP_VALIDATE_RET( grp != NULL ); 2497 ECP_VALIDATE_RET( R != NULL ); 2498 ECP_VALIDATE_RET( m != NULL ); 2499 ECP_VALIDATE_RET( P != NULL ); 2500 ECP_VALIDATE_RET( n != NULL ); 2501 ECP_VALIDATE_RET( Q != NULL ); 2502 2503 if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS ) 2504 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 2505 2506 mbedtls_ecp_point_init( &mP ); 2507 2508 ECP_RS_ENTER( ma ); 2509 2510 #if defined(MBEDTLS_ECP_RESTARTABLE) 2511 if( rs_ctx != NULL && rs_ctx->ma != NULL ) 2512 { 2513 /* redirect intermediate results to restart context */ 2514 pmP = &rs_ctx->ma->mP; 2515 pR = &rs_ctx->ma->R; 2516 2517 /* jump to next operation */ 2518 if( rs_ctx->ma->state == ecp_rsma_mul2 ) 2519 goto mul2; 2520 if( rs_ctx->ma->state == ecp_rsma_add ) 2521 goto add; 2522 if( rs_ctx->ma->state == ecp_rsma_norm ) 2523 goto norm; 2524 } 2525 #endif /* MBEDTLS_ECP_RESTARTABLE */ 2526 2527 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pmP, m, P, rs_ctx ) ); 2528 #if defined(MBEDTLS_ECP_RESTARTABLE) 2529 if( rs_ctx != NULL && rs_ctx->ma != NULL ) 2530 rs_ctx->ma->state = ecp_rsma_mul2; 2531 2532 mul2: 2533 #endif 2534 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pR, n, Q, rs_ctx ) ); 2535 2536 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2537 if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) ) 2538 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); 2539 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2540 2541 #if defined(MBEDTLS_ECP_RESTARTABLE) 2542 if( rs_ctx != NULL && rs_ctx->ma != NULL ) 2543 rs_ctx->ma->state = ecp_rsma_add; 2544 2545 add: 2546 #endif 2547 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_ADD ); 2548 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, pR, pmP, pR ) ); 2549 #if defined(MBEDTLS_ECP_RESTARTABLE) 2550 if( rs_ctx != NULL && rs_ctx->ma != NULL ) 2551 rs_ctx->ma->state = ecp_rsma_norm; 2552 2553 norm: 2554 #endif 2555 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV ); 2556 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, pR ) ); 2557 2558 #if defined(MBEDTLS_ECP_RESTARTABLE) 2559 if( rs_ctx != NULL && rs_ctx->ma != NULL ) 2560 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, pR ) ); 2561 #endif 2562 2563 cleanup: 2564 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2565 if( is_grp_capable ) 2566 mbedtls_internal_ecp_free( grp ); 2567 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2568 2569 mbedtls_ecp_point_free( &mP ); 2570 2571 ECP_RS_LEAVE( ma ); 2572 2573 return( ret ); 2574 } 2575 2576 /* 2577 * Linear combination 2578 * NOT constant-time 2579 */ 2580 int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2581 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2582 const mbedtls_mpi *n, const mbedtls_ecp_point *Q ) 2583 { 2584 ECP_VALIDATE_RET( grp != NULL ); 2585 ECP_VALIDATE_RET( R != NULL ); 2586 ECP_VALIDATE_RET( m != NULL ); 2587 ECP_VALIDATE_RET( P != NULL ); 2588 ECP_VALIDATE_RET( n != NULL ); 2589 ECP_VALIDATE_RET( Q != NULL ); 2590 return( mbedtls_ecp_muladd_restartable( grp, R, m, P, n, Q, NULL ) ); 2591 } 2592 2593 #if defined(ECP_MONTGOMERY) 2594 /* 2595 * Check validity of a public key for Montgomery curves with x-only schemes 2596 */ 2597 static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 2598 { 2599 /* [Curve25519 p. 5] Just check X is the correct number of bytes */ 2600 /* Allow any public value, if it's too big then we'll just reduce it mod p 2601 * (RFC 7748 sec. 5 para. 3). */ 2602 if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 ) 2603 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2604 2605 return( 0 ); 2606 } 2607 #endif /* ECP_MONTGOMERY */ 2608 2609 /* 2610 * Check that a point is valid as a public key 2611 */ 2612 int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp, 2613 const mbedtls_ecp_point *pt ) 2614 { 2615 ECP_VALIDATE_RET( grp != NULL ); 2616 ECP_VALIDATE_RET( pt != NULL ); 2617 2618 /* Must use affine coordinates */ 2619 if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 ) 2620 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2621 2622 #if defined(ECP_MONTGOMERY) 2623 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 2624 return( ecp_check_pubkey_mx( grp, pt ) ); 2625 #endif 2626 #if defined(ECP_SHORTWEIERSTRASS) 2627 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 2628 return( ecp_check_pubkey_sw( grp, pt ) ); 2629 #endif 2630 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 2631 } 2632 2633 /* 2634 * Check that an mbedtls_mpi is valid as a private key 2635 */ 2636 int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, 2637 const mbedtls_mpi *d ) 2638 { 2639 ECP_VALIDATE_RET( grp != NULL ); 2640 ECP_VALIDATE_RET( d != NULL ); 2641 2642 #if defined(ECP_MONTGOMERY) 2643 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 2644 { 2645 /* see RFC 7748 sec. 5 para. 5 */ 2646 if( mbedtls_mpi_get_bit( d, 0 ) != 0 || 2647 mbedtls_mpi_get_bit( d, 1 ) != 0 || 2648 mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */ 2649 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2650 2651 /* see [Curve25519] page 5 */ 2652 if( grp->nbits == 254 && mbedtls_mpi_get_bit( d, 2 ) != 0 ) 2653 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2654 2655 return( 0 ); 2656 } 2657 #endif /* ECP_MONTGOMERY */ 2658 #if defined(ECP_SHORTWEIERSTRASS) 2659 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 2660 { 2661 /* see SEC1 3.2 */ 2662 if( mbedtls_mpi_cmp_int( d, 1 ) < 0 || 2663 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 ) 2664 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2665 else 2666 return( 0 ); 2667 } 2668 #endif /* ECP_SHORTWEIERSTRASS */ 2669 2670 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 2671 } 2672 2673 /* 2674 * Generate a private key 2675 */ 2676 int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp, 2677 mbedtls_mpi *d, 2678 int (*f_rng)(void *, unsigned char *, size_t), 2679 void *p_rng ) 2680 { 2681 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2682 size_t n_size; 2683 2684 ECP_VALIDATE_RET( grp != NULL ); 2685 ECP_VALIDATE_RET( d != NULL ); 2686 ECP_VALIDATE_RET( f_rng != NULL ); 2687 2688 n_size = ( grp->nbits + 7 ) / 8; 2689 2690 #if defined(ECP_MONTGOMERY) 2691 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 2692 { 2693 /* [M225] page 5 */ 2694 size_t b; 2695 2696 do { 2697 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) ); 2698 } while( mbedtls_mpi_bitlen( d ) == 0); 2699 2700 /* Make sure the most significant bit is nbits */ 2701 b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */ 2702 if( b > grp->nbits ) 2703 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) ); 2704 else 2705 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits, 1 ) ); 2706 2707 /* Make sure the last two bits are unset for Curve448, three bits for 2708 Curve25519 */ 2709 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) ); 2710 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) ); 2711 if( grp->nbits == 254 ) 2712 { 2713 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) ); 2714 } 2715 } 2716 #endif /* ECP_MONTGOMERY */ 2717 2718 #if defined(ECP_SHORTWEIERSTRASS) 2719 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 2720 { 2721 /* SEC1 3.2.1: Generate d such that 1 <= n < N */ 2722 int count = 0; 2723 2724 /* 2725 * Match the procedure given in RFC 6979 (deterministic ECDSA): 2726 * - use the same byte ordering; 2727 * - keep the leftmost nbits bits of the generated octet string; 2728 * - try until result is in the desired range. 2729 * This also avoids any biais, which is especially important for ECDSA. 2730 */ 2731 do 2732 { 2733 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) ); 2734 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) ); 2735 2736 /* 2737 * Each try has at worst a probability 1/2 of failing (the msb has 2738 * a probability 1/2 of being 0, and then the result will be < N), 2739 * so after 30 tries failure probability is a most 2**(-30). 2740 * 2741 * For most curves, 1 try is enough with overwhelming probability, 2742 * since N starts with a lot of 1s in binary, but some curves 2743 * such as secp224k1 are actually very close to the worst case. 2744 */ 2745 if( ++count > 30 ) 2746 return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); 2747 } 2748 while( mbedtls_mpi_cmp_int( d, 1 ) < 0 || 2749 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 ); 2750 } 2751 #endif /* ECP_SHORTWEIERSTRASS */ 2752 2753 cleanup: 2754 return( ret ); 2755 } 2756 2757 /* 2758 * Generate a keypair with configurable base point 2759 */ 2760 int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp, 2761 const mbedtls_ecp_point *G, 2762 mbedtls_mpi *d, mbedtls_ecp_point *Q, 2763 int (*f_rng)(void *, unsigned char *, size_t), 2764 void *p_rng ) 2765 { 2766 int ret; 2767 ECP_VALIDATE_RET( grp != NULL ); 2768 ECP_VALIDATE_RET( d != NULL ); 2769 ECP_VALIDATE_RET( G != NULL ); 2770 ECP_VALIDATE_RET( Q != NULL ); 2771 ECP_VALIDATE_RET( f_rng != NULL ); 2772 2773 MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, d, f_rng, p_rng ) ); 2774 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) ); 2775 2776 cleanup: 2777 return( ret ); 2778 } 2779 2780 /* 2781 * Generate key pair, wrapper for conventional base point 2782 */ 2783 int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp, 2784 mbedtls_mpi *d, mbedtls_ecp_point *Q, 2785 int (*f_rng)(void *, unsigned char *, size_t), 2786 void *p_rng ) 2787 { 2788 ECP_VALIDATE_RET( grp != NULL ); 2789 ECP_VALIDATE_RET( d != NULL ); 2790 ECP_VALIDATE_RET( Q != NULL ); 2791 ECP_VALIDATE_RET( f_rng != NULL ); 2792 2793 return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) ); 2794 } 2795 2796 /* 2797 * Generate a keypair, prettier wrapper 2798 */ 2799 int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, 2800 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 2801 { 2802 int ret; 2803 ECP_VALIDATE_RET( key != NULL ); 2804 ECP_VALIDATE_RET( f_rng != NULL ); 2805 2806 if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 ) 2807 return( ret ); 2808 2809 return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) ); 2810 } 2811 2812 /* 2813 * Check a public-private key pair 2814 */ 2815 int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv ) 2816 { 2817 int ret; 2818 mbedtls_ecp_point Q; 2819 mbedtls_ecp_group grp; 2820 ECP_VALIDATE_RET( pub != NULL ); 2821 ECP_VALIDATE_RET( prv != NULL ); 2822 2823 if( pub->grp.id == MBEDTLS_ECP_DP_NONE || 2824 pub->grp.id != prv->grp.id || 2825 mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) || 2826 mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) || 2827 mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) ) 2828 { 2829 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 2830 } 2831 2832 mbedtls_ecp_point_init( &Q ); 2833 mbedtls_ecp_group_init( &grp ); 2834 2835 /* mbedtls_ecp_mul() needs a non-const group... */ 2836 mbedtls_ecp_group_copy( &grp, &prv->grp ); 2837 2838 /* Also checks d is valid */ 2839 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) ); 2840 2841 if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) || 2842 mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) || 2843 mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) ) 2844 { 2845 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2846 goto cleanup; 2847 } 2848 2849 cleanup: 2850 mbedtls_ecp_point_free( &Q ); 2851 mbedtls_ecp_group_free( &grp ); 2852 2853 return( ret ); 2854 } 2855 2856 #if defined(MBEDTLS_SELF_TEST) 2857 2858 /* 2859 * Checkup routine 2860 */ 2861 int mbedtls_ecp_self_test( int verbose ) 2862 { 2863 int ret; 2864 size_t i; 2865 mbedtls_ecp_group grp; 2866 mbedtls_ecp_point R, P; 2867 mbedtls_mpi m; 2868 unsigned long add_c_prev, dbl_c_prev, mul_c_prev; 2869 /* exponents especially adapted for secp192r1 */ 2870 const char *exponents[] = 2871 { 2872 "000000000000000000000000000000000000000000000001", /* one */ 2873 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */ 2874 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */ 2875 "400000000000000000000000000000000000000000000000", /* one and zeros */ 2876 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */ 2877 "555555555555555555555555555555555555555555555555", /* 101010... */ 2878 }; 2879 2880 mbedtls_ecp_group_init( &grp ); 2881 mbedtls_ecp_point_init( &R ); 2882 mbedtls_ecp_point_init( &P ); 2883 mbedtls_mpi_init( &m ); 2884 2885 /* Use secp192r1 if available, or any available curve */ 2886 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) 2887 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) ); 2888 #else 2889 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) ); 2890 #endif 2891 2892 if( verbose != 0 ) 2893 mbedtls_printf( " ECP test #1 (constant op_count, base point G): " ); 2894 2895 /* Do a dummy multiplication first to trigger precomputation */ 2896 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) ); 2897 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) ); 2898 2899 add_count = 0; 2900 dbl_count = 0; 2901 mul_count = 0; 2902 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); 2903 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); 2904 2905 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) 2906 { 2907 add_c_prev = add_count; 2908 dbl_c_prev = dbl_count; 2909 mul_c_prev = mul_count; 2910 add_count = 0; 2911 dbl_count = 0; 2912 mul_count = 0; 2913 2914 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); 2915 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); 2916 2917 if( add_count != add_c_prev || 2918 dbl_count != dbl_c_prev || 2919 mul_count != mul_c_prev ) 2920 { 2921 if( verbose != 0 ) 2922 mbedtls_printf( "failed (%u)\n", (unsigned int) i ); 2923 2924 ret = 1; 2925 goto cleanup; 2926 } 2927 } 2928 2929 if( verbose != 0 ) 2930 mbedtls_printf( "passed\n" ); 2931 2932 if( verbose != 0 ) 2933 mbedtls_printf( " ECP test #2 (constant op_count, other point): " ); 2934 /* We computed P = 2G last time, use it */ 2935 2936 add_count = 0; 2937 dbl_count = 0; 2938 mul_count = 0; 2939 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); 2940 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); 2941 2942 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) 2943 { 2944 add_c_prev = add_count; 2945 dbl_c_prev = dbl_count; 2946 mul_c_prev = mul_count; 2947 add_count = 0; 2948 dbl_count = 0; 2949 mul_count = 0; 2950 2951 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); 2952 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); 2953 2954 if( add_count != add_c_prev || 2955 dbl_count != dbl_c_prev || 2956 mul_count != mul_c_prev ) 2957 { 2958 if( verbose != 0 ) 2959 mbedtls_printf( "failed (%u)\n", (unsigned int) i ); 2960 2961 ret = 1; 2962 goto cleanup; 2963 } 2964 } 2965 2966 if( verbose != 0 ) 2967 mbedtls_printf( "passed\n" ); 2968 2969 cleanup: 2970 2971 if( ret < 0 && verbose != 0 ) 2972 mbedtls_printf( "Unexpected error, return code = %08X\n", ret ); 2973 2974 mbedtls_ecp_group_free( &grp ); 2975 mbedtls_ecp_point_free( &R ); 2976 mbedtls_ecp_point_free( &P ); 2977 mbedtls_mpi_free( &m ); 2978 2979 if( verbose != 0 ) 2980 mbedtls_printf( "\n" ); 2981 2982 return( ret ); 2983 } 2984 2985 #endif /* MBEDTLS_SELF_TEST */ 2986 2987 #endif /* !MBEDTLS_ECP_ALT */ 2988 2989 #endif /* MBEDTLS_ECP_C */ 2990