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