1 /* 2 * Elliptic curves over GF(p): generic functions 3 * 4 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved 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 * This file is part of mbed TLS (https://tls.mbed.org) 47 */ 48 49 /* 50 * References: 51 * 52 * SEC1 http://www.secg.org/index.php?action=secg,docs_secg 53 * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone 54 * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf 55 * RFC 4492 for the related TLS structures and constants 56 * 57 * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf 58 * 59 * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis 60 * for elliptic curve cryptosystems. In : Cryptographic Hardware and 61 * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302. 62 * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25> 63 * 64 * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to 65 * render ECC resistant against Side Channel Attacks. IACR Cryptology 66 * ePrint Archive, 2004, vol. 2004, p. 342. 67 * <http://eprint.iacr.org/2004/342.pdf> 68 */ 69 70 #if !defined(MBEDTLS_CONFIG_FILE) 71 #include "mbedtls/config.h" 72 #else 73 #include MBEDTLS_CONFIG_FILE 74 #endif 75 76 #if defined(MBEDTLS_ECP_C) 77 78 #include "mbedtls/ecp.h" 79 #include "mbedtls/threading.h" 80 81 #include <string.h> 82 83 #if !defined(MBEDTLS_ECP_ALT) 84 85 #if defined(MBEDTLS_PLATFORM_C) 86 #include "mbedtls/platform.h" 87 #else 88 #include <stdlib.h> 89 #include <stdio.h> 90 #define mbedtls_printf printf 91 #define mbedtls_calloc calloc 92 #define mbedtls_free free 93 #endif 94 95 #include "mbedtls/ecp_internal.h" 96 97 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 98 #if defined(MBEDTLS_HMAC_DRBG_C) 99 #include "mbedtls/hmac_drbg.h" 100 #elif defined(MBEDTLS_CTR_DRBG_C) 101 #include "mbedtls/ctr_drbg.h" 102 #elif defined(MBEDTLS_SHA512_C) 103 #include "mbedtls/sha512.h" 104 #elif defined(MBEDTLS_SHA256_C) 105 #include "mbedtls/sha256.h" 106 #else 107 #error "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid." 108 #endif 109 #endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */ 110 111 #if ( defined(__ARMCC_VERSION) || defined(_MSC_VER) ) && \ 112 !defined(inline) && !defined(__cplusplus) 113 #define inline __inline 114 #endif 115 116 /* Implementation that should never be optimized out by the compiler */ 117 static void mbedtls_zeroize( void *v, size_t n ) { 118 volatile unsigned char *p = v; while( n-- ) *p++ = 0; 119 } 120 121 #if defined(MBEDTLS_SELF_TEST) 122 /* 123 * Counts of point addition and doubling, and field multiplications. 124 * Used to test resistance of point multiplication to simple timing attacks. 125 */ 126 static unsigned long add_count, dbl_count, mul_count; 127 #endif 128 129 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 130 /* 131 * Currently ecp_mul() takes a RNG function as an argument, used for 132 * side-channel protection, but it can be NULL. The initial reasoning was 133 * that people will pass non-NULL RNG when they care about side-channels, but 134 * unfortunately we have some APIs that call ecp_mul() with a NULL RNG, with 135 * no opportunity for the user to do anything about it. 136 * 137 * The obvious strategies for addressing that include: 138 * - change those APIs so that they take RNG arguments; 139 * - require a global RNG to be available to all crypto modules. 140 * 141 * Unfortunately those would break compatibility. So what we do instead is 142 * have our own internal DRBG instance, seeded from the secret scalar. 143 * 144 * The following is a light-weight abstraction layer for doing that with 145 * HMAC_DRBG (first choice) or CTR_DRBG. 146 */ 147 148 #if defined(MBEDTLS_HMAC_DRBG_C) 149 150 /* DRBG context type */ 151 typedef mbedtls_hmac_drbg_context ecp_drbg_context; 152 153 /* DRBG context init */ 154 static inline void ecp_drbg_init( ecp_drbg_context *ctx ) 155 { 156 mbedtls_hmac_drbg_init( ctx ); 157 } 158 159 /* DRBG context free */ 160 static inline void ecp_drbg_free( ecp_drbg_context *ctx ) 161 { 162 mbedtls_hmac_drbg_free( ctx ); 163 } 164 165 /* DRBG function */ 166 static inline int ecp_drbg_random( void *p_rng, 167 unsigned char *output, size_t output_len ) 168 { 169 return( mbedtls_hmac_drbg_random( p_rng, output, output_len ) ); 170 } 171 172 /* DRBG context seeding */ 173 static int ecp_drbg_seed( ecp_drbg_context *ctx, 174 const mbedtls_mpi *secret, size_t secret_len ) 175 { 176 int ret; 177 unsigned char secret_bytes[MBEDTLS_ECP_MAX_BYTES]; 178 /* The list starts with strong hashes */ 179 const mbedtls_md_type_t md_type = mbedtls_md_list()[0]; 180 const mbedtls_md_info_t *md_info = mbedtls_md_info_from_type( md_type ); 181 182 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( secret, 183 secret_bytes, secret_len ) ); 184 185 ret = mbedtls_hmac_drbg_seed_buf( ctx, md_info, secret_bytes, secret_len ); 186 187 cleanup: 188 mbedtls_zeroize( secret_bytes, secret_len ); 189 190 return( ret ); 191 } 192 193 #elif defined(MBEDTLS_CTR_DRBG_C) 194 195 /* DRBG context type */ 196 typedef mbedtls_ctr_drbg_context ecp_drbg_context; 197 198 /* DRBG context init */ 199 static inline void ecp_drbg_init( ecp_drbg_context *ctx ) 200 { 201 mbedtls_ctr_drbg_init( ctx ); 202 } 203 204 /* DRBG context free */ 205 static inline void ecp_drbg_free( ecp_drbg_context *ctx ) 206 { 207 mbedtls_ctr_drbg_free( ctx ); 208 } 209 210 /* DRBG function */ 211 static inline int ecp_drbg_random( void *p_rng, 212 unsigned char *output, size_t output_len ) 213 { 214 return( mbedtls_ctr_drbg_random( p_rng, output, output_len ) ); 215 } 216 217 /* 218 * Since CTR_DRBG doesn't have a seed_buf() function the way HMAC_DRBG does, 219 * we need to pass an entropy function when seeding. So we use a dummy 220 * function for that, and pass the actual entropy as customisation string. 221 * (During seeding of CTR_DRBG the entropy input and customisation string are 222 * concatenated before being used to update the secret state.) 223 */ 224 static int ecp_ctr_drbg_null_entropy(void *ctx, unsigned char *out, size_t len) 225 { 226 (void) ctx; 227 memset( out, 0, len ); 228 return( 0 ); 229 } 230 231 /* DRBG context seeding */ 232 static int ecp_drbg_seed( ecp_drbg_context *ctx, 233 const mbedtls_mpi *secret, size_t secret_len ) 234 { 235 int ret; 236 unsigned char secret_bytes[MBEDTLS_ECP_MAX_BYTES]; 237 238 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( secret, 239 secret_bytes, secret_len ) ); 240 241 ret = mbedtls_ctr_drbg_seed( ctx, ecp_ctr_drbg_null_entropy, NULL, 242 secret_bytes, secret_len ); 243 244 cleanup: 245 mbedtls_zeroize( secret_bytes, secret_len ); 246 247 return( ret ); 248 } 249 250 #elif defined(MBEDTLS_SHA512_C) || defined(MBEDTLS_SHA256_C) 251 252 /* This will be used in the self-test function */ 253 #define ECP_ONE_STEP_KDF 254 255 /* 256 * We need to expand secret data (the scalar) into a longer stream of bytes. 257 * 258 * We'll use the One-Step KDF from NIST SP 800-56C, with option 1 (H is a hash 259 * function) and empty FixedInfo. (Though we'll make it fit the DRBG API for 260 * convenience, this is not a full-fledged DRBG, but we don't need one here.) 261 * 262 * We need a basic hash abstraction layer to use whatever SHA-2 is available. 263 */ 264 #if defined(MBEDTLS_SHA512_C) 265 266 #define HASH_FUNC( in, ilen, out ) mbedtls_sha512_ret( in, ilen, out, 0 ); 267 #define HASH_BLOCK_BYTES ( 512 / 8 ) 268 269 #elif defined(MBEDTLS_SHA256_C) 270 271 #define HASH_FUNC( in, ilen, out ) mbedtls_sha256_ret( in, ilen, out, 0 ); 272 #define HASH_BLOCK_BYTES ( 256 / 8 ) 273 274 #endif /* SHA512/SHA256 abstraction */ 275 276 /* 277 * State consists of a 32-bit counter plus the secret value. 278 * 279 * We stored them concatenated in a single buffer as that's what will get 280 * passed to the hash function. 281 */ 282 typedef struct { 283 size_t total_len; 284 uint8_t buf[4 + MBEDTLS_ECP_MAX_BYTES]; 285 } ecp_drbg_context; 286 287 static void ecp_drbg_init( ecp_drbg_context *ctx ) 288 { 289 memset( ctx, 0, sizeof( ecp_drbg_context ) ); 290 } 291 292 static void ecp_drbg_free( ecp_drbg_context *ctx ) 293 { 294 mbedtls_zeroize( ctx, sizeof( ecp_drbg_context ) ); 295 } 296 297 static int ecp_drbg_seed( ecp_drbg_context *ctx, 298 const mbedtls_mpi *secret, size_t secret_len ) 299 { 300 ctx->total_len = 4 + secret_len; 301 memset( ctx->buf, 0, 4); 302 return( mbedtls_mpi_write_binary( secret, ctx->buf + 4, secret_len ) ); 303 } 304 305 static int ecp_drbg_random( void *p_rng, unsigned char *output, size_t output_len ) 306 { 307 ecp_drbg_context *ctx = p_rng; 308 int ret; 309 size_t len_done = 0; 310 uint8_t tmp[HASH_BLOCK_BYTES]; 311 312 while( len_done < output_len ) 313 { 314 uint8_t use_len; 315 316 /* This function is only called for coordinate randomisation, which 317 * happens only twice in a scalar multiplication. Each time needs a 318 * random value in the range [2, p-1], and gets it by drawing len(p) 319 * bytes from this function, and retrying up to 10 times if unlucky. 320 * 321 * So for the largest curve, each scalar multiplication draws at most 322 * 20 * 66 bytes. The minimum block size is 32 (SHA-256), so with 323 * rounding that means a most 20 * 3 blocks. 324 * 325 * Since we don't need to draw more that 255 blocks, don't bother 326 * with carry propagation and just return an error instead. We can 327 * change that it we even need to draw more blinding values. 328 */ 329 ctx->buf[3] += 1; 330 if( ctx->buf[3] == 0 ) 331 return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); 332 333 ret = HASH_FUNC( ctx->buf, ctx->total_len, tmp ); 334 if( ret != 0 ) 335 return( ret ); 336 337 if( output_len - len_done > HASH_BLOCK_BYTES ) 338 use_len = HASH_BLOCK_BYTES; 339 else 340 use_len = output_len - len_done; 341 342 memcpy( output + len_done, tmp, use_len ); 343 len_done += use_len; 344 } 345 346 mbedtls_zeroize( tmp, sizeof( tmp ) ); 347 348 return( 0 ); 349 } 350 351 #else /* DRBG/SHA modules */ 352 #error "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid." 353 #endif /* DRBG/SHA modules */ 354 #endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */ 355 356 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) || \ 357 defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) || \ 358 defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) || \ 359 defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) || \ 360 defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) || \ 361 defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) || \ 362 defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) || \ 363 defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) || \ 364 defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) || \ 365 defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) || \ 366 defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED) 367 #define ECP_SHORTWEIERSTRASS 368 #endif 369 370 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) 371 #define ECP_MONTGOMERY 372 #endif 373 374 /* 375 * Curve types: internal for now, might be exposed later 376 */ 377 typedef enum 378 { 379 ECP_TYPE_NONE = 0, 380 ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */ 381 ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */ 382 } ecp_curve_type; 383 384 /* 385 * List of supported curves: 386 * - internal ID 387 * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2) 388 * - size in bits 389 * - readable name 390 * 391 * Curves are listed in order: largest curves first, and for a given size, 392 * fastest curves first. This provides the default order for the SSL module. 393 * 394 * Reminder: update profiles in x509_crt.c when adding a new curves! 395 */ 396 static const mbedtls_ecp_curve_info ecp_supported_curves[] = 397 { 398 #if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) 399 { MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" }, 400 #endif 401 #if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) 402 { MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" }, 403 #endif 404 #if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) 405 { MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" }, 406 #endif 407 #if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) 408 { MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" }, 409 #endif 410 #if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) 411 { MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" }, 412 #endif 413 #if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED) 414 { MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" }, 415 #endif 416 #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) 417 { MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" }, 418 #endif 419 #if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) 420 { MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" }, 421 #endif 422 #if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) 423 { MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" }, 424 #endif 425 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) 426 { MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" }, 427 #endif 428 #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) 429 { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" }, 430 #endif 431 { MBEDTLS_ECP_DP_NONE, 0, 0, NULL }, 432 }; 433 434 #define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \ 435 sizeof( ecp_supported_curves[0] ) 436 437 static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES]; 438 439 /* 440 * List of supported curves and associated info 441 */ 442 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void ) 443 { 444 return( ecp_supported_curves ); 445 } 446 447 /* 448 * List of supported curves, group ID only 449 */ 450 const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void ) 451 { 452 static int init_done = 0; 453 454 if( ! init_done ) 455 { 456 size_t i = 0; 457 const mbedtls_ecp_curve_info *curve_info; 458 459 for( curve_info = mbedtls_ecp_curve_list(); 460 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 461 curve_info++ ) 462 { 463 ecp_supported_grp_id[i++] = curve_info->grp_id; 464 } 465 ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE; 466 467 init_done = 1; 468 } 469 470 return( ecp_supported_grp_id ); 471 } 472 473 /* 474 * Get the curve info for the internal identifier 475 */ 476 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id ) 477 { 478 const mbedtls_ecp_curve_info *curve_info; 479 480 for( curve_info = mbedtls_ecp_curve_list(); 481 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 482 curve_info++ ) 483 { 484 if( curve_info->grp_id == grp_id ) 485 return( curve_info ); 486 } 487 488 return( NULL ); 489 } 490 491 /* 492 * Get the curve info from the TLS identifier 493 */ 494 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id ) 495 { 496 const mbedtls_ecp_curve_info *curve_info; 497 498 for( curve_info = mbedtls_ecp_curve_list(); 499 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 500 curve_info++ ) 501 { 502 if( curve_info->tls_id == tls_id ) 503 return( curve_info ); 504 } 505 506 return( NULL ); 507 } 508 509 /* 510 * Get the curve info from the name 511 */ 512 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name ) 513 { 514 const mbedtls_ecp_curve_info *curve_info; 515 516 for( curve_info = mbedtls_ecp_curve_list(); 517 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 518 curve_info++ ) 519 { 520 if( strcmp( curve_info->name, name ) == 0 ) 521 return( curve_info ); 522 } 523 524 return( NULL ); 525 } 526 527 /* 528 * Get the type of a curve 529 */ 530 static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp ) 531 { 532 if( grp->G.X.p == NULL ) 533 return( ECP_TYPE_NONE ); 534 535 if( grp->G.Y.p == NULL ) 536 return( ECP_TYPE_MONTGOMERY ); 537 else 538 return( ECP_TYPE_SHORT_WEIERSTRASS ); 539 } 540 541 /* 542 * Initialize (the components of) a point 543 */ 544 void mbedtls_ecp_point_init( mbedtls_ecp_point *pt ) 545 { 546 if( pt == NULL ) 547 return; 548 549 mbedtls_mpi_init( &pt->X ); 550 mbedtls_mpi_init( &pt->Y ); 551 mbedtls_mpi_init( &pt->Z ); 552 } 553 554 /* 555 * Initialize (the components of) a group 556 */ 557 void mbedtls_ecp_group_init( mbedtls_ecp_group *grp ) 558 { 559 if( grp == NULL ) 560 return; 561 562 memset( grp, 0, sizeof( mbedtls_ecp_group ) ); 563 } 564 565 /* 566 * Initialize (the components of) a key pair 567 */ 568 void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key ) 569 { 570 if( key == NULL ) 571 return; 572 573 mbedtls_ecp_group_init( &key->grp ); 574 mbedtls_mpi_init( &key->d ); 575 mbedtls_ecp_point_init( &key->Q ); 576 } 577 578 /* 579 * Unallocate (the components of) a point 580 */ 581 void mbedtls_ecp_point_free( mbedtls_ecp_point *pt ) 582 { 583 if( pt == NULL ) 584 return; 585 586 mbedtls_mpi_free( &( pt->X ) ); 587 mbedtls_mpi_free( &( pt->Y ) ); 588 mbedtls_mpi_free( &( pt->Z ) ); 589 } 590 591 /* 592 * Unallocate (the components of) a group 593 */ 594 void mbedtls_ecp_group_free( mbedtls_ecp_group *grp ) 595 { 596 size_t i; 597 598 if( grp == NULL ) 599 return; 600 601 if( grp->h != 1 ) 602 { 603 mbedtls_mpi_free( &grp->P ); 604 mbedtls_mpi_free( &grp->A ); 605 mbedtls_mpi_free( &grp->B ); 606 mbedtls_ecp_point_free( &grp->G ); 607 mbedtls_mpi_free( &grp->N ); 608 } 609 610 if( grp->T != NULL ) 611 { 612 for( i = 0; i < grp->T_size; i++ ) 613 mbedtls_ecp_point_free( &grp->T[i] ); 614 mbedtls_free( grp->T ); 615 } 616 617 mbedtls_zeroize( grp, sizeof( mbedtls_ecp_group ) ); 618 } 619 620 /* 621 * Unallocate (the components of) a key pair 622 */ 623 void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key ) 624 { 625 if( key == NULL ) 626 return; 627 628 mbedtls_ecp_group_free( &key->grp ); 629 mbedtls_mpi_free( &key->d ); 630 mbedtls_ecp_point_free( &key->Q ); 631 } 632 633 /* 634 * Copy the contents of a point 635 */ 636 int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q ) 637 { 638 int ret; 639 640 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X, &Q->X ) ); 641 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y, &Q->Y ) ); 642 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z, &Q->Z ) ); 643 644 cleanup: 645 return( ret ); 646 } 647 648 /* 649 * Copy the contents of a group object 650 */ 651 int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src ) 652 { 653 return mbedtls_ecp_group_load( dst, src->id ); 654 } 655 656 /* 657 * Set point to zero 658 */ 659 int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt ) 660 { 661 int ret; 662 663 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) ); 664 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y , 1 ) ); 665 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 0 ) ); 666 667 cleanup: 668 return( ret ); 669 } 670 671 /* 672 * Tell if a point is zero 673 */ 674 int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt ) 675 { 676 return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 ); 677 } 678 679 /* 680 * Compare two points lazily 681 */ 682 int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P, 683 const mbedtls_ecp_point *Q ) 684 { 685 if( mbedtls_mpi_cmp_mpi( &P->X, &Q->X ) == 0 && 686 mbedtls_mpi_cmp_mpi( &P->Y, &Q->Y ) == 0 && 687 mbedtls_mpi_cmp_mpi( &P->Z, &Q->Z ) == 0 ) 688 { 689 return( 0 ); 690 } 691 692 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 693 } 694 695 /* 696 * Import a non-zero point from ASCII strings 697 */ 698 int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix, 699 const char *x, const char *y ) 700 { 701 int ret; 702 703 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X, radix, x ) ); 704 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y, radix, y ) ); 705 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) ); 706 707 cleanup: 708 return( ret ); 709 } 710 711 /* 712 * Export a point into unsigned binary data (SEC1 2.3.3) 713 */ 714 int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *P, 715 int format, size_t *olen, 716 unsigned char *buf, size_t buflen ) 717 { 718 int ret = 0; 719 size_t plen; 720 721 if( format != MBEDTLS_ECP_PF_UNCOMPRESSED && 722 format != MBEDTLS_ECP_PF_COMPRESSED ) 723 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 724 725 /* 726 * Common case: P == 0 727 */ 728 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 ) 729 { 730 if( buflen < 1 ) 731 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); 732 733 buf[0] = 0x00; 734 *olen = 1; 735 736 return( 0 ); 737 } 738 739 plen = mbedtls_mpi_size( &grp->P ); 740 741 if( format == MBEDTLS_ECP_PF_UNCOMPRESSED ) 742 { 743 *olen = 2 * plen + 1; 744 745 if( buflen < *olen ) 746 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); 747 748 buf[0] = 0x04; 749 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) ); 750 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) ); 751 } 752 else if( format == MBEDTLS_ECP_PF_COMPRESSED ) 753 { 754 *olen = plen + 1; 755 756 if( buflen < *olen ) 757 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); 758 759 buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 ); 760 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) ); 761 } 762 763 cleanup: 764 return( ret ); 765 } 766 767 /* 768 * Import a point from unsigned binary data (SEC1 2.3.4) 769 */ 770 int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, 771 const unsigned char *buf, size_t ilen ) 772 { 773 int ret; 774 size_t plen; 775 776 if( ilen < 1 ) 777 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 778 779 if( buf[0] == 0x00 ) 780 { 781 if( ilen == 1 ) 782 return( mbedtls_ecp_set_zero( pt ) ); 783 else 784 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 785 } 786 787 plen = mbedtls_mpi_size( &grp->P ); 788 789 if( buf[0] != 0x04 ) 790 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 791 792 if( ilen != 2 * plen + 1 ) 793 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 794 795 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) ); 796 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) ); 797 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) ); 798 799 cleanup: 800 return( ret ); 801 } 802 803 /* 804 * Import a point from a TLS ECPoint record (RFC 4492) 805 * struct { 806 * opaque point <1..2^8-1>; 807 * } ECPoint; 808 */ 809 int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, 810 const unsigned char **buf, size_t buf_len ) 811 { 812 unsigned char data_len; 813 const unsigned char *buf_start; 814 815 /* 816 * We must have at least two bytes (1 for length, at least one for data) 817 */ 818 if( buf_len < 2 ) 819 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 820 821 data_len = *(*buf)++; 822 if( data_len < 1 || data_len > buf_len - 1 ) 823 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 824 825 /* 826 * Save buffer start for read_binary and update buf 827 */ 828 buf_start = *buf; 829 *buf += data_len; 830 831 return mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len ); 832 } 833 834 /* 835 * Export a point as a TLS ECPoint record (RFC 4492) 836 * struct { 837 * opaque point <1..2^8-1>; 838 * } ECPoint; 839 */ 840 int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt, 841 int format, size_t *olen, 842 unsigned char *buf, size_t blen ) 843 { 844 int ret; 845 846 /* 847 * buffer length must be at least one, for our length byte 848 */ 849 if( blen < 1 ) 850 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 851 852 if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format, 853 olen, buf + 1, blen - 1) ) != 0 ) 854 return( ret ); 855 856 /* 857 * write length to the first byte and update total length 858 */ 859 buf[0] = (unsigned char) *olen; 860 ++*olen; 861 862 return( 0 ); 863 } 864 865 /* 866 * Set a group from an ECParameters record (RFC 4492) 867 */ 868 int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp, const unsigned char **buf, size_t len ) 869 { 870 uint16_t tls_id; 871 const mbedtls_ecp_curve_info *curve_info; 872 873 /* 874 * We expect at least three bytes (see below) 875 */ 876 if( len < 3 ) 877 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 878 879 /* 880 * First byte is curve_type; only named_curve is handled 881 */ 882 if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE ) 883 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 884 885 /* 886 * Next two bytes are the namedcurve value 887 */ 888 tls_id = *(*buf)++; 889 tls_id <<= 8; 890 tls_id |= *(*buf)++; 891 892 if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL ) 893 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 894 895 return mbedtls_ecp_group_load( grp, curve_info->grp_id ); 896 } 897 898 /* 899 * Write the ECParameters record corresponding to a group (RFC 4492) 900 */ 901 int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen, 902 unsigned char *buf, size_t blen ) 903 { 904 const mbedtls_ecp_curve_info *curve_info; 905 906 if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL ) 907 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 908 909 /* 910 * We are going to write 3 bytes (see below) 911 */ 912 *olen = 3; 913 if( blen < *olen ) 914 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); 915 916 /* 917 * First byte is curve_type, always named_curve 918 */ 919 *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE; 920 921 /* 922 * Next two bytes are the namedcurve value 923 */ 924 buf[0] = curve_info->tls_id >> 8; 925 buf[1] = curve_info->tls_id & 0xFF; 926 927 return( 0 ); 928 } 929 930 /* 931 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi. 932 * See the documentation of struct mbedtls_ecp_group. 933 * 934 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf. 935 */ 936 static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp ) 937 { 938 int ret; 939 940 if( grp->modp == NULL ) 941 return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) ); 942 943 /* N->s < 0 is a much faster test, which fails only if N is 0 */ 944 if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) || 945 mbedtls_mpi_bitlen( N ) > 2 * grp->pbits ) 946 { 947 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 948 } 949 950 MBEDTLS_MPI_CHK( grp->modp( N ) ); 951 952 /* N->s < 0 is a much faster test, which fails only if N is 0 */ 953 while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) 954 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) ); 955 956 while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 ) 957 /* we known P, N and the result are positive */ 958 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) ); 959 960 cleanup: 961 return( ret ); 962 } 963 964 /* 965 * Fast mod-p functions expect their argument to be in the 0..p^2 range. 966 * 967 * In order to guarantee that, we need to ensure that operands of 968 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will 969 * bring the result back to this range. 970 * 971 * The following macros are shortcuts for doing that. 972 */ 973 974 /* 975 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi 976 */ 977 #if defined(MBEDTLS_SELF_TEST) 978 #define INC_MUL_COUNT mul_count++; 979 #else 980 #define INC_MUL_COUNT 981 #endif 982 983 #define MOD_MUL( N ) do { MBEDTLS_MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \ 984 while( 0 ) 985 986 /* 987 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi 988 * N->s < 0 is a very fast test, which fails only if N is 0 989 */ 990 #define MOD_SUB( N ) \ 991 while( N.s < 0 && mbedtls_mpi_cmp_int( &N, 0 ) != 0 ) \ 992 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &N, &N, &grp->P ) ) 993 994 /* 995 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int. 996 * We known P, N and the result are positive, so sub_abs is correct, and 997 * a bit faster. 998 */ 999 #define MOD_ADD( N ) \ 1000 while( mbedtls_mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \ 1001 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &N, &N, &grp->P ) ) 1002 1003 #if defined(ECP_SHORTWEIERSTRASS) 1004 /* 1005 * For curves in short Weierstrass form, we do all the internal operations in 1006 * Jacobian coordinates. 1007 * 1008 * For multiplication, we'll use a comb method with coutermeasueres against 1009 * SPA, hence timing attacks. 1010 */ 1011 1012 /* 1013 * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1) 1014 * Cost: 1N := 1I + 3M + 1S 1015 */ 1016 static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt ) 1017 { 1018 int ret; 1019 mbedtls_mpi Zi, ZZi; 1020 1021 if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 ) 1022 return( 0 ); 1023 1024 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) 1025 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 1026 { 1027 return mbedtls_internal_ecp_normalize_jac( grp, pt ); 1028 } 1029 #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */ 1030 mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi ); 1031 1032 /* 1033 * X = X / Z^2 mod p 1034 */ 1035 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z, &grp->P ) ); 1036 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); 1037 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X ); 1038 1039 /* 1040 * Y = Y / Z^3 mod p 1041 */ 1042 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y ); 1043 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y ); 1044 1045 /* 1046 * Z = 1 1047 */ 1048 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) ); 1049 1050 cleanup: 1051 1052 mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi ); 1053 1054 return( ret ); 1055 } 1056 1057 /* 1058 * Normalize jacobian coordinates of an array of (pointers to) points, 1059 * using Montgomery's trick to perform only one inversion mod P. 1060 * (See for example Cohen's "A Course in Computational Algebraic Number 1061 * Theory", Algorithm 10.3.4.) 1062 * 1063 * Warning: fails (returning an error) if one of the points is zero! 1064 * This should never happen, see choice of w in ecp_mul_comb(). 1065 * 1066 * Cost: 1N(t) := 1I + (6t - 3)M + 1S 1067 */ 1068 static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp, 1069 mbedtls_ecp_point *T[], size_t t_len ) 1070 { 1071 int ret; 1072 size_t i; 1073 mbedtls_mpi *c, u, Zi, ZZi; 1074 1075 if( t_len < 2 ) 1076 return( ecp_normalize_jac( grp, *T ) ); 1077 1078 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) 1079 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 1080 { 1081 return mbedtls_internal_ecp_normalize_jac_many(grp, T, t_len); 1082 } 1083 #endif 1084 1085 if( ( c = mbedtls_calloc( t_len, sizeof( mbedtls_mpi ) ) ) == NULL ) 1086 return( MBEDTLS_ERR_ECP_ALLOC_FAILED ); 1087 1088 mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi ); 1089 1090 /* 1091 * c[i] = Z_0 * ... * Z_i 1092 */ 1093 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) ); 1094 for( i = 1; i < t_len; i++ ) 1095 { 1096 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) ); 1097 MOD_MUL( c[i] ); 1098 } 1099 1100 /* 1101 * u = 1 / (Z_0 * ... * Z_n) mod P 1102 */ 1103 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[t_len-1], &grp->P ) ); 1104 1105 for( i = t_len - 1; ; i-- ) 1106 { 1107 /* 1108 * Zi = 1 / Z_i mod p 1109 * u = 1 / (Z_0 * ... * Z_i) mod P 1110 */ 1111 if( i == 0 ) { 1112 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) ); 1113 } 1114 else 1115 { 1116 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi ); 1117 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u ); 1118 } 1119 1120 /* 1121 * proceed as in normalize() 1122 */ 1123 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); 1124 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X ); 1125 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y ); 1126 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y ); 1127 1128 /* 1129 * Post-precessing: reclaim some memory by shrinking coordinates 1130 * - not storing Z (always 1) 1131 * - shrinking other coordinates, but still keeping the same number of 1132 * limbs as P, as otherwise it will too likely be regrown too fast. 1133 */ 1134 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) ); 1135 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) ); 1136 mbedtls_mpi_free( &T[i]->Z ); 1137 1138 if( i == 0 ) 1139 break; 1140 } 1141 1142 cleanup: 1143 1144 mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi ); 1145 for( i = 0; i < t_len; i++ ) 1146 mbedtls_mpi_free( &c[i] ); 1147 mbedtls_free( c ); 1148 1149 return( ret ); 1150 } 1151 1152 /* 1153 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak. 1154 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid 1155 */ 1156 static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp, 1157 mbedtls_ecp_point *Q, 1158 unsigned char inv ) 1159 { 1160 int ret; 1161 unsigned char nonzero; 1162 mbedtls_mpi mQY; 1163 1164 mbedtls_mpi_init( &mQY ); 1165 1166 /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */ 1167 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) ); 1168 nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0; 1169 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) ); 1170 1171 cleanup: 1172 mbedtls_mpi_free( &mQY ); 1173 1174 return( ret ); 1175 } 1176 1177 /* 1178 * Point doubling R = 2 P, Jacobian coordinates 1179 * 1180 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 . 1181 * 1182 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR 1183 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring. 1184 * 1185 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }. 1186 * 1187 * Cost: 1D := 3M + 4S (A == 0) 1188 * 4M + 4S (A == -3) 1189 * 3M + 6S + 1a otherwise 1190 */ 1191 static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1192 const mbedtls_ecp_point *P ) 1193 { 1194 int ret; 1195 mbedtls_mpi M, S, T, U; 1196 1197 #if defined(MBEDTLS_SELF_TEST) 1198 dbl_count++; 1199 #endif 1200 1201 #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) 1202 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 1203 { 1204 return mbedtls_internal_ecp_double_jac( grp, R, P ); 1205 } 1206 #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */ 1207 1208 mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U ); 1209 1210 /* Special case for A = -3 */ 1211 if( grp->A.p == NULL ) 1212 { 1213 /* M = 3(X + Z^2)(X - Z^2) */ 1214 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S ); 1215 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T, &P->X, &S ) ); MOD_ADD( T ); 1216 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U, &P->X, &S ) ); MOD_SUB( U ); 1217 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &U ) ); MOD_MUL( S ); 1218 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); 1219 } 1220 else 1221 { 1222 /* M = 3.X^2 */ 1223 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &P->X ) ); MOD_MUL( S ); 1224 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); 1225 1226 /* Optimize away for "koblitz" curves with A = 0 */ 1227 if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 ) 1228 { 1229 /* M += A.Z^4 */ 1230 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S ); 1231 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &S, &S ) ); MOD_MUL( T ); 1232 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &grp->A ) ); MOD_MUL( S ); 1233 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M, &M, &S ) ); MOD_ADD( M ); 1234 } 1235 } 1236 1237 /* S = 4.X.Y^2 */ 1238 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &P->Y, &P->Y ) ); MOD_MUL( T ); 1239 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T, 1 ) ); MOD_ADD( T ); 1240 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &T ) ); MOD_MUL( S ); 1241 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S, 1 ) ); MOD_ADD( S ); 1242 1243 /* U = 8.Y^4 */ 1244 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &T, &T ) ); MOD_MUL( U ); 1245 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); 1246 1247 /* T = M^2 - 2.S */ 1248 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &M, &M ) ); MOD_MUL( T ); 1249 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); 1250 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); 1251 1252 /* S = M(S - T) - U */ 1253 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &T ) ); MOD_SUB( S ); 1254 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &S, &M ) ); MOD_MUL( S ); 1255 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &U ) ); MOD_SUB( S ); 1256 1257 /* U = 2.Y.Z */ 1258 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &P->Y, &P->Z ) ); MOD_MUL( U ); 1259 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); 1260 1261 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) ); 1262 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) ); 1263 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) ); 1264 1265 cleanup: 1266 mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U ); 1267 1268 return( ret ); 1269 } 1270 1271 /* 1272 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22) 1273 * 1274 * The coordinates of Q must be normalized (= affine), 1275 * but those of P don't need to. R is not normalized. 1276 * 1277 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q. 1278 * None of these cases can happen as intermediate step in ecp_mul_comb(): 1279 * - at each step, P, Q and R are multiples of the base point, the factor 1280 * being less than its order, so none of them is zero; 1281 * - Q is an odd multiple of the base point, P an even multiple, 1282 * due to the choice of precomputed points in the modified comb method. 1283 * So branches for these cases do not leak secret information. 1284 * 1285 * We accept Q->Z being unset (saving memory in tables) as meaning 1. 1286 * 1287 * Cost: 1A := 8M + 3S 1288 */ 1289 static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1290 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q ) 1291 { 1292 int ret; 1293 mbedtls_mpi T1, T2, T3, T4, X, Y, Z; 1294 1295 #if defined(MBEDTLS_SELF_TEST) 1296 add_count++; 1297 #endif 1298 1299 #if defined(MBEDTLS_ECP_ADD_MIXED_ALT) 1300 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 1301 { 1302 return mbedtls_internal_ecp_add_mixed( grp, R, P, Q ); 1303 } 1304 #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */ 1305 1306 /* 1307 * Trivial cases: P == 0 or Q == 0 (case 1) 1308 */ 1309 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 ) 1310 return( mbedtls_ecp_copy( R, Q ) ); 1311 1312 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 ) 1313 return( mbedtls_ecp_copy( R, P ) ); 1314 1315 /* 1316 * Make sure Q coordinates are normalized 1317 */ 1318 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 ) 1319 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 1320 1321 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 ); 1322 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z ); 1323 1324 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 ); 1325 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 ); 1326 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 ); 1327 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 ); 1328 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 ); 1329 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 ); 1330 1331 /* Special cases (2) and (3) */ 1332 if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 ) 1333 { 1334 if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 ) 1335 { 1336 ret = ecp_double_jac( grp, R, P ); 1337 goto cleanup; 1338 } 1339 else 1340 { 1341 ret = mbedtls_ecp_set_zero( R ); 1342 goto cleanup; 1343 } 1344 } 1345 1346 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z ); 1347 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 ); 1348 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 ); 1349 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 ); 1350 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 ); 1351 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X ); 1352 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X ); 1353 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X ); 1354 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 ); 1355 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 ); 1356 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 ); 1357 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y ); 1358 1359 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) ); 1360 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) ); 1361 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) ); 1362 1363 cleanup: 1364 1365 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 ); 1366 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z ); 1367 1368 return( ret ); 1369 } 1370 1371 /* 1372 * Randomize jacobian coordinates: 1373 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l 1374 * This is sort of the reverse operation of ecp_normalize_jac(). 1375 * 1376 * This countermeasure was first suggested in [2]. 1377 */ 1378 static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, 1379 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 1380 { 1381 int ret; 1382 mbedtls_mpi l, ll; 1383 size_t p_size; 1384 int count = 0; 1385 1386 #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) 1387 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 1388 { 1389 return mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng ); 1390 } 1391 #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */ 1392 1393 p_size = ( grp->pbits + 7 ) / 8; 1394 mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll ); 1395 1396 /* Generate l such that 1 < l < p */ 1397 do 1398 { 1399 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) ); 1400 1401 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) 1402 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) ); 1403 1404 if( count++ > 10 ) 1405 { 1406 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED; 1407 goto cleanup; 1408 } 1409 } 1410 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ); 1411 1412 /* Z = l * Z */ 1413 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z ); 1414 1415 /* X = l^2 * X */ 1416 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll ); 1417 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X ); 1418 1419 /* Y = l^3 * Y */ 1420 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll ); 1421 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y ); 1422 1423 cleanup: 1424 mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll ); 1425 1426 return( ret ); 1427 } 1428 1429 /* 1430 * Check and define parameters used by the comb method (see below for details) 1431 */ 1432 #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7 1433 #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds" 1434 #endif 1435 1436 /* d = ceil( n / w ) */ 1437 #define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2 1438 1439 /* number of precomputed points */ 1440 #define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) ) 1441 1442 /* 1443 * Compute the representation of m that will be used with our comb method. 1444 * 1445 * The basic comb method is described in GECC 3.44 for example. We use a 1446 * modified version that provides resistance to SPA by avoiding zero 1447 * digits in the representation as in [3]. We modify the method further by 1448 * requiring that all K_i be odd, which has the small cost that our 1449 * representation uses one more K_i, due to carries. 1450 * 1451 * Also, for the sake of compactness, only the seven low-order bits of x[i] 1452 * are used to represent K_i, and the msb of x[i] encodes the the sign (s_i in 1453 * the paper): it is set if and only if if s_i == -1; 1454 * 1455 * Calling conventions: 1456 * - x is an array of size d + 1 1457 * - w is the size, ie number of teeth, of the comb, and must be between 1458 * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE) 1459 * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d 1460 * (the result will be incorrect if these assumptions are not satisfied) 1461 */ 1462 static void ecp_comb_fixed( unsigned char x[], size_t d, 1463 unsigned char w, const mbedtls_mpi *m ) 1464 { 1465 size_t i, j; 1466 unsigned char c, cc, adjust; 1467 1468 memset( x, 0, d+1 ); 1469 1470 /* First get the classical comb values (except for x_d = 0) */ 1471 for( i = 0; i < d; i++ ) 1472 for( j = 0; j < w; j++ ) 1473 x[i] |= mbedtls_mpi_get_bit( m, i + d * j ) << j; 1474 1475 /* Now make sure x_1 .. x_d are odd */ 1476 c = 0; 1477 for( i = 1; i <= d; i++ ) 1478 { 1479 /* Add carry and update it */ 1480 cc = x[i] & c; 1481 x[i] = x[i] ^ c; 1482 c = cc; 1483 1484 /* Adjust if needed, avoiding branches */ 1485 adjust = 1 - ( x[i] & 0x01 ); 1486 c |= x[i] & ( x[i-1] * adjust ); 1487 x[i] = x[i] ^ ( x[i-1] * adjust ); 1488 x[i-1] |= adjust << 7; 1489 } 1490 } 1491 1492 /* 1493 * Precompute points for the comb method 1494 * 1495 * If i = i_{w-1} ... i_1 is the binary representation of i, then 1496 * T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P 1497 * 1498 * T must be able to hold 2^{w - 1} elements 1499 * 1500 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1) 1501 */ 1502 static int ecp_precompute_comb( const mbedtls_ecp_group *grp, 1503 mbedtls_ecp_point T[], const mbedtls_ecp_point *P, 1504 unsigned char w, size_t d ) 1505 { 1506 int ret; 1507 unsigned char i, k; 1508 size_t j; 1509 mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1]; 1510 1511 /* 1512 * Set T[0] = P and 1513 * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value) 1514 */ 1515 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) ); 1516 1517 k = 0; 1518 for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 ) 1519 { 1520 cur = T + i; 1521 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) ); 1522 for( j = 0; j < d; j++ ) 1523 MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) ); 1524 1525 TT[k++] = cur; 1526 } 1527 1528 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) ); 1529 1530 /* 1531 * Compute the remaining ones using the minimal number of additions 1532 * Be careful to update T[2^l] only after using it! 1533 */ 1534 k = 0; 1535 for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 ) 1536 { 1537 j = i; 1538 while( j-- ) 1539 { 1540 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) ); 1541 TT[k++] = &T[i + j]; 1542 } 1543 } 1544 1545 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) ); 1546 1547 cleanup: 1548 1549 return( ret ); 1550 } 1551 1552 /* 1553 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ] 1554 */ 1555 static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1556 const mbedtls_ecp_point T[], unsigned char t_len, 1557 unsigned char i ) 1558 { 1559 int ret; 1560 unsigned char ii, j; 1561 1562 /* Ignore the "sign" bit and scale down */ 1563 ii = ( i & 0x7Fu ) >> 1; 1564 1565 /* Read the whole table to thwart cache-based timing attacks */ 1566 for( j = 0; j < t_len; j++ ) 1567 { 1568 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) ); 1569 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) ); 1570 } 1571 1572 /* Safely invert result if i is "negative" */ 1573 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) ); 1574 1575 cleanup: 1576 return( ret ); 1577 } 1578 1579 /* 1580 * Core multiplication algorithm for the (modified) comb method. 1581 * This part is actually common with the basic comb method (GECC 3.44) 1582 * 1583 * Cost: d A + d D + 1 R 1584 */ 1585 static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1586 const mbedtls_ecp_point T[], unsigned char t_len, 1587 const unsigned char x[], size_t d, 1588 int (*f_rng)(void *, unsigned char *, size_t), 1589 void *p_rng ) 1590 { 1591 int ret; 1592 mbedtls_ecp_point Txi; 1593 size_t i; 1594 1595 mbedtls_ecp_point_init( &Txi ); 1596 1597 /* Start with a non-zero point and randomize its coordinates */ 1598 i = d; 1599 MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) ); 1600 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 1 ) ); 1601 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 1602 if( f_rng != 0 ) 1603 #endif 1604 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) ); 1605 1606 while( i-- != 0 ) 1607 { 1608 MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) ); 1609 MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) ); 1610 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) ); 1611 } 1612 1613 cleanup: 1614 1615 mbedtls_ecp_point_free( &Txi ); 1616 1617 return( ret ); 1618 } 1619 1620 /* 1621 * Multiplication using the comb method, 1622 * for curves in short Weierstrass form 1623 */ 1624 static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1625 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 1626 int (*f_rng)(void *, unsigned char *, size_t), 1627 void *p_rng ) 1628 { 1629 int ret; 1630 unsigned char w, m_is_odd, p_eq_g, pre_len, i; 1631 size_t d; 1632 unsigned char k[COMB_MAX_D + 1]; 1633 mbedtls_ecp_point *T; 1634 mbedtls_mpi M, mm; 1635 1636 mbedtls_mpi_init( &M ); 1637 mbedtls_mpi_init( &mm ); 1638 1639 /* we need N to be odd to trnaform m in an odd number, check now */ 1640 if( mbedtls_mpi_get_bit( &grp->N, 0 ) != 1 ) 1641 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 1642 1643 /* 1644 * Minimize the number of multiplications, that is minimize 1645 * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w ) 1646 * (see costs of the various parts, with 1S = 1M) 1647 */ 1648 w = grp->nbits >= 384 ? 5 : 4; 1649 1650 /* 1651 * If P == G, pre-compute a bit more, since this may be re-used later. 1652 * Just adding one avoids upping the cost of the first mul too much, 1653 * and the memory cost too. 1654 */ 1655 #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1 1656 p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 && 1657 mbedtls_mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 ); 1658 if( p_eq_g ) 1659 w++; 1660 #else 1661 p_eq_g = 0; 1662 #endif 1663 1664 /* 1665 * Make sure w is within bounds. 1666 * (The last test is useful only for very small curves in the test suite.) 1667 */ 1668 if( w > MBEDTLS_ECP_WINDOW_SIZE ) 1669 w = MBEDTLS_ECP_WINDOW_SIZE; 1670 if( w >= grp->nbits ) 1671 w = 2; 1672 1673 /* Other sizes that depend on w */ 1674 pre_len = 1U << ( w - 1 ); 1675 d = ( grp->nbits + w - 1 ) / w; 1676 1677 /* 1678 * Prepare precomputed points: if P == G we want to 1679 * use grp->T if already initialized, or initialize it. 1680 */ 1681 T = p_eq_g ? grp->T : NULL; 1682 1683 if( T == NULL ) 1684 { 1685 T = mbedtls_calloc( pre_len, sizeof( mbedtls_ecp_point ) ); 1686 if( T == NULL ) 1687 { 1688 ret = MBEDTLS_ERR_ECP_ALLOC_FAILED; 1689 goto cleanup; 1690 } 1691 1692 MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) ); 1693 1694 if( p_eq_g ) 1695 { 1696 grp->T = T; 1697 grp->T_size = pre_len; 1698 } 1699 } 1700 1701 /* 1702 * Make sure M is odd (M = m or M = N - m, since N is odd) 1703 * using the fact that m * P = - (N - m) * P 1704 */ 1705 m_is_odd = ( mbedtls_mpi_get_bit( m, 0 ) == 1 ); 1706 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) ); 1707 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N, m ) ); 1708 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, ! m_is_odd ) ); 1709 1710 /* 1711 * Go for comb multiplication, R = M * P 1712 */ 1713 ecp_comb_fixed( k, d, w, &M ); 1714 MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) ); 1715 1716 /* 1717 * Now get m * P from M * P and normalize it 1718 */ 1719 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) ); 1720 1721 /* 1722 * Knowledge of the jacobian coordinates may leak the last few bits of the 1723 * scalar [1], and since our MPI implementation isn't constant-flow, 1724 * inversion (used for coordinate normalization) may leak the full value 1725 * of its input via side-channels [2]. 1726 * 1727 * [1] https://eprint.iacr.org/2003/191 1728 * [2] https://eprint.iacr.org/2020/055 1729 * 1730 * Avoid the leak by randomizing coordinates before we normalize them. 1731 */ 1732 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 1733 if( f_rng != 0 ) 1734 #endif 1735 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) ); 1736 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) ); 1737 1738 cleanup: 1739 1740 /* There are two cases where T is not stored in grp: 1741 * - P != G 1742 * - An intermediate operation failed before setting grp->T 1743 * In either case, T must be freed. 1744 */ 1745 if( T != NULL && T != grp->T ) 1746 { 1747 for( i = 0; i < pre_len; i++ ) 1748 mbedtls_ecp_point_free( &T[i] ); 1749 mbedtls_free( T ); 1750 } 1751 1752 mbedtls_mpi_free( &M ); 1753 mbedtls_mpi_free( &mm ); 1754 1755 if( ret != 0 ) 1756 mbedtls_ecp_point_free( R ); 1757 1758 return( ret ); 1759 } 1760 1761 #endif /* ECP_SHORTWEIERSTRASS */ 1762 1763 #if defined(ECP_MONTGOMERY) 1764 /* 1765 * For Montgomery curves, we do all the internal arithmetic in projective 1766 * coordinates. Import/export of points uses only the x coordinates, which is 1767 * internaly represented as X / Z. 1768 * 1769 * For scalar multiplication, we'll use a Montgomery ladder. 1770 */ 1771 1772 /* 1773 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1 1774 * Cost: 1M + 1I 1775 */ 1776 static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P ) 1777 { 1778 int ret; 1779 1780 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) 1781 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 1782 { 1783 return mbedtls_internal_ecp_normalize_mxz( grp, P ); 1784 } 1785 #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */ 1786 1787 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) ); 1788 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X ); 1789 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) ); 1790 1791 cleanup: 1792 return( ret ); 1793 } 1794 1795 /* 1796 * Randomize projective x/z coordinates: 1797 * (X, Z) -> (l X, l Z) for random l 1798 * This is sort of the reverse operation of ecp_normalize_mxz(). 1799 * 1800 * This countermeasure was first suggested in [2]. 1801 * Cost: 2M 1802 */ 1803 static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P, 1804 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 1805 { 1806 int ret; 1807 mbedtls_mpi l; 1808 size_t p_size; 1809 int count = 0; 1810 1811 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) 1812 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 1813 { 1814 return mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng ); 1815 } 1816 #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */ 1817 1818 p_size = ( grp->pbits + 7 ) / 8; 1819 mbedtls_mpi_init( &l ); 1820 1821 /* Generate l such that 1 < l < p */ 1822 do 1823 { 1824 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) ); 1825 1826 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) 1827 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) ); 1828 1829 if( count++ > 10 ) 1830 { 1831 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED; 1832 goto cleanup; 1833 } 1834 } 1835 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ); 1836 1837 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X ); 1838 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z ); 1839 1840 cleanup: 1841 mbedtls_mpi_free( &l ); 1842 1843 return( ret ); 1844 } 1845 1846 /* 1847 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q), 1848 * for Montgomery curves in x/z coordinates. 1849 * 1850 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3 1851 * with 1852 * d = X1 1853 * P = (X2, Z2) 1854 * Q = (X3, Z3) 1855 * R = (X4, Z4) 1856 * S = (X5, Z5) 1857 * and eliminating temporary variables tO, ..., t4. 1858 * 1859 * Cost: 5M + 4S 1860 */ 1861 static int ecp_double_add_mxz( const mbedtls_ecp_group *grp, 1862 mbedtls_ecp_point *R, mbedtls_ecp_point *S, 1863 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q, 1864 const mbedtls_mpi *d ) 1865 { 1866 int ret; 1867 mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB; 1868 1869 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) 1870 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 1871 { 1872 return mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d ); 1873 } 1874 #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */ 1875 1876 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B ); 1877 mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C ); 1878 mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB ); 1879 1880 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A ); 1881 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA ); 1882 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B ); 1883 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB ); 1884 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E ); 1885 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C ); 1886 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D ); 1887 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA ); 1888 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB ); 1889 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X ); 1890 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X ); 1891 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z ); 1892 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z ); 1893 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z ); 1894 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X ); 1895 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z ); 1896 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z ); 1897 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z ); 1898 1899 cleanup: 1900 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B ); 1901 mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C ); 1902 mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB ); 1903 1904 return( ret ); 1905 } 1906 1907 /* 1908 * Multiplication with Montgomery ladder in x/z coordinates, 1909 * for curves in Montgomery form 1910 */ 1911 static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1912 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 1913 int (*f_rng)(void *, unsigned char *, size_t), 1914 void *p_rng ) 1915 { 1916 int ret; 1917 size_t i; 1918 unsigned char b; 1919 mbedtls_ecp_point RP; 1920 mbedtls_mpi PX; 1921 1922 mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX ); 1923 1924 /* Save PX and read from P before writing to R, in case P == R */ 1925 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) ); 1926 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) ); 1927 1928 /* Set R to zero in modified x/z coordinates */ 1929 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X, 1 ) ); 1930 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) ); 1931 mbedtls_mpi_free( &R->Y ); 1932 1933 /* RP.X might be sligtly larger than P, so reduce it */ 1934 MOD_ADD( RP.X ); 1935 1936 /* Randomize coordinates of the starting point */ 1937 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 1938 if( f_rng != NULL ) 1939 #endif 1940 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) ); 1941 1942 /* Loop invariant: R = result so far, RP = R + P */ 1943 i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */ 1944 while( i-- > 0 ) 1945 { 1946 b = mbedtls_mpi_get_bit( m, i ); 1947 /* 1948 * if (b) R = 2R + P else R = 2R, 1949 * which is: 1950 * if (b) double_add( RP, R, RP, R ) 1951 * else double_add( R, RP, R, RP ) 1952 * but using safe conditional swaps to avoid leaks 1953 */ 1954 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) ); 1955 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); 1956 MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) ); 1957 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) ); 1958 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); 1959 } 1960 1961 /* 1962 * Knowledge of the projective coordinates may leak the last few bits of the 1963 * scalar [1], and since our MPI implementation isn't constant-flow, 1964 * inversion (used for coordinate normalization) may leak the full value 1965 * of its input via side-channels [2]. 1966 * 1967 * [1] https://eprint.iacr.org/2003/191 1968 * [2] https://eprint.iacr.org/2020/055 1969 * 1970 * Avoid the leak by randomizing coordinates before we normalize them. 1971 */ 1972 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 1973 if( f_rng != NULL ) 1974 #endif 1975 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, R, f_rng, p_rng ) ); 1976 1977 MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) ); 1978 1979 cleanup: 1980 mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX ); 1981 1982 return( ret ); 1983 } 1984 1985 #endif /* ECP_MONTGOMERY */ 1986 1987 /* 1988 * Multiplication R = m * P 1989 */ 1990 int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1991 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 1992 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 1993 { 1994 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 1995 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 1996 char is_grp_capable = 0; 1997 #endif 1998 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 1999 ecp_drbg_context drbg_ctx; 2000 2001 ecp_drbg_init( &drbg_ctx ); 2002 #endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */ 2003 2004 /* Common sanity checks */ 2005 if( mbedtls_mpi_cmp_int( &P->Z, 1 ) != 0 ) 2006 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 2007 2008 if( ( ret = mbedtls_ecp_check_privkey( grp, m ) ) != 0 || 2009 ( ret = mbedtls_ecp_check_pubkey( grp, P ) ) != 0 ) 2010 return( ret ); 2011 2012 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2013 if( f_rng == NULL ) 2014 { 2015 const size_t m_len = ( grp->nbits + 7 ) / 8; 2016 MBEDTLS_MPI_CHK( ecp_drbg_seed( &drbg_ctx, m, m_len ) ); 2017 f_rng = &ecp_drbg_random; 2018 p_rng = &drbg_ctx; 2019 } 2020 #endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */ 2021 2022 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2023 if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) 2024 { 2025 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); 2026 } 2027 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2028 2029 #if defined(ECP_MONTGOMERY) 2030 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 2031 ret = ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ); 2032 #endif 2033 #if defined(ECP_SHORTWEIERSTRASS) 2034 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 2035 ret = ecp_mul_comb( grp, R, m, P, f_rng, p_rng ); 2036 #endif 2037 2038 #if defined(MBEDTLS_ECP_INTERNAL_ALT) || !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2039 cleanup: 2040 #endif 2041 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2042 if ( is_grp_capable ) 2043 { 2044 mbedtls_internal_ecp_free( grp ); 2045 } 2046 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2047 2048 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG) 2049 ecp_drbg_free( &drbg_ctx ); 2050 #endif 2051 2052 return( ret ); 2053 } 2054 2055 #if defined(ECP_SHORTWEIERSTRASS) 2056 /* 2057 * Check that an affine point is valid as a public key, 2058 * short weierstrass curves (SEC1 3.2.3.1) 2059 */ 2060 static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 2061 { 2062 int ret; 2063 mbedtls_mpi YY, RHS; 2064 2065 /* pt coordinates must be normalized for our checks */ 2066 if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 || 2067 mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 || 2068 mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 || 2069 mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 ) 2070 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2071 2072 mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS ); 2073 2074 /* 2075 * YY = Y^2 2076 * RHS = X (X^2 + A) + B = X^3 + A X + B 2077 */ 2078 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY ); 2079 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS ); 2080 2081 /* Special case for A = -3 */ 2082 if( grp->A.p == NULL ) 2083 { 2084 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS ); 2085 } 2086 else 2087 { 2088 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS ); 2089 } 2090 2091 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS ); 2092 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS ); 2093 2094 if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 ) 2095 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 2096 2097 cleanup: 2098 2099 mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS ); 2100 2101 return( ret ); 2102 } 2103 #endif /* ECP_SHORTWEIERSTRASS */ 2104 2105 /* 2106 * R = m * P with shortcuts for m == 1 and m == -1 2107 * NOT constant-time - ONLY for short Weierstrass! 2108 */ 2109 static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp, 2110 mbedtls_ecp_point *R, 2111 const mbedtls_mpi *m, 2112 const mbedtls_ecp_point *P ) 2113 { 2114 int ret; 2115 2116 if( mbedtls_mpi_cmp_int( m, 1 ) == 0 ) 2117 { 2118 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); 2119 } 2120 else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 ) 2121 { 2122 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); 2123 if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 ) 2124 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) ); 2125 } 2126 else 2127 { 2128 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, R, m, P, NULL, NULL ) ); 2129 } 2130 2131 cleanup: 2132 return( ret ); 2133 } 2134 2135 /* 2136 * Linear combination 2137 * NOT constant-time 2138 */ 2139 int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2140 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2141 const mbedtls_mpi *n, const mbedtls_ecp_point *Q ) 2142 { 2143 int ret; 2144 mbedtls_ecp_point mP; 2145 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2146 char is_grp_capable = 0; 2147 #endif 2148 2149 if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS ) 2150 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 2151 2152 mbedtls_ecp_point_init( &mP ); 2153 2154 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, &mP, m, P ) ); 2155 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, R, n, Q ) ); 2156 2157 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2158 if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) 2159 { 2160 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); 2161 } 2162 2163 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2164 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, &mP, R ) ); 2165 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) ); 2166 2167 cleanup: 2168 2169 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2170 if ( is_grp_capable ) 2171 { 2172 mbedtls_internal_ecp_free( grp ); 2173 } 2174 2175 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2176 mbedtls_ecp_point_free( &mP ); 2177 2178 return( ret ); 2179 } 2180 2181 2182 #if defined(ECP_MONTGOMERY) 2183 /* 2184 * Check validity of a public key for Montgomery curves with x-only schemes 2185 */ 2186 static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 2187 { 2188 /* [Curve25519 p. 5] Just check X is the correct number of bytes */ 2189 if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 ) 2190 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2191 2192 return( 0 ); 2193 } 2194 #endif /* ECP_MONTGOMERY */ 2195 2196 /* 2197 * Check that a point is valid as a public key 2198 */ 2199 int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 2200 { 2201 /* Must use affine coordinates */ 2202 if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 ) 2203 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2204 2205 #if defined(ECP_MONTGOMERY) 2206 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 2207 return( ecp_check_pubkey_mx( grp, pt ) ); 2208 #endif 2209 #if defined(ECP_SHORTWEIERSTRASS) 2210 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 2211 return( ecp_check_pubkey_sw( grp, pt ) ); 2212 #endif 2213 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 2214 } 2215 2216 /* 2217 * Check that an mbedtls_mpi is valid as a private key 2218 */ 2219 int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, const mbedtls_mpi *d ) 2220 { 2221 #if defined(ECP_MONTGOMERY) 2222 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 2223 { 2224 /* see [Curve25519] page 5 */ 2225 if( mbedtls_mpi_get_bit( d, 0 ) != 0 || 2226 mbedtls_mpi_get_bit( d, 1 ) != 0 || 2227 mbedtls_mpi_get_bit( d, 2 ) != 0 || 2228 mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */ 2229 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2230 else 2231 return( 0 ); 2232 } 2233 #endif /* ECP_MONTGOMERY */ 2234 #if defined(ECP_SHORTWEIERSTRASS) 2235 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 2236 { 2237 /* see SEC1 3.2 */ 2238 if( mbedtls_mpi_cmp_int( d, 1 ) < 0 || 2239 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 ) 2240 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 2241 else 2242 return( 0 ); 2243 } 2244 #endif /* ECP_SHORTWEIERSTRASS */ 2245 2246 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 2247 } 2248 2249 /* 2250 * Generate a private key 2251 */ 2252 int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp, 2253 mbedtls_mpi *d, 2254 int (*f_rng)(void *, unsigned char *, size_t), 2255 void *p_rng ) 2256 { 2257 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2258 size_t n_size = ( grp->nbits + 7 ) / 8; 2259 2260 #if defined(ECP_MONTGOMERY) 2261 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 2262 { 2263 /* [M225] page 5 */ 2264 size_t b; 2265 2266 do { 2267 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) ); 2268 } while( mbedtls_mpi_bitlen( d ) == 0); 2269 2270 /* Make sure the most significant bit is nbits */ 2271 b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */ 2272 if( b > grp->nbits ) 2273 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) ); 2274 else 2275 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits, 1 ) ); 2276 2277 /* Make sure the last three bits are unset */ 2278 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) ); 2279 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) ); 2280 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) ); 2281 } 2282 #endif /* ECP_MONTGOMERY */ 2283 2284 #if defined(ECP_SHORTWEIERSTRASS) 2285 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 2286 { 2287 /* SEC1 3.2.1: Generate d such that 1 <= n < N */ 2288 int count = 0; 2289 unsigned cmp = 0; 2290 2291 /* 2292 * Match the procedure given in RFC 6979 (deterministic ECDSA): 2293 * - use the same byte ordering; 2294 * - keep the leftmost nbits bits of the generated octet string; 2295 * - try until result is in the desired range. 2296 * This also avoids any biais, which is especially important for ECDSA. 2297 */ 2298 do 2299 { 2300 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) ); 2301 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) ); 2302 2303 /* 2304 * Each try has at worst a probability 1/2 of failing (the msb has 2305 * a probability 1/2 of being 0, and then the result will be < N), 2306 * so after 30 tries failure probability is a most 2**(-30). 2307 * 2308 * For most curves, 1 try is enough with overwhelming probability, 2309 * since N starts with a lot of 1s in binary, but some curves 2310 * such as secp224k1 are actually very close to the worst case. 2311 */ 2312 if( ++count > 30 ) 2313 return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); 2314 2315 ret = mbedtls_mpi_lt_mpi_ct( d, &grp->N, &cmp ); 2316 if( ret != 0 ) 2317 { 2318 goto cleanup; 2319 } 2320 } 2321 while( mbedtls_mpi_cmp_int( d, 1 ) < 0 || cmp != 1 ); 2322 } 2323 #endif /* ECP_SHORTWEIERSTRASS */ 2324 2325 cleanup: 2326 return( ret ); 2327 } 2328 2329 /* 2330 * Generate a keypair with configurable base point 2331 */ 2332 int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp, 2333 const mbedtls_ecp_point *G, 2334 mbedtls_mpi *d, mbedtls_ecp_point *Q, 2335 int (*f_rng)(void *, unsigned char *, size_t), 2336 void *p_rng ) 2337 { 2338 int ret; 2339 2340 MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, d, f_rng, p_rng ) ); 2341 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) ); 2342 2343 cleanup: 2344 return( ret ); 2345 } 2346 2347 /* 2348 * Generate key pair, wrapper for conventional base point 2349 */ 2350 int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp, 2351 mbedtls_mpi *d, mbedtls_ecp_point *Q, 2352 int (*f_rng)(void *, unsigned char *, size_t), 2353 void *p_rng ) 2354 { 2355 return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) ); 2356 } 2357 2358 /* 2359 * Generate a keypair, prettier wrapper 2360 */ 2361 int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, 2362 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 2363 { 2364 int ret; 2365 2366 if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 ) 2367 return( ret ); 2368 2369 return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) ); 2370 } 2371 2372 /* 2373 * Check a public-private key pair 2374 */ 2375 int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv ) 2376 { 2377 int ret; 2378 mbedtls_ecp_point Q; 2379 mbedtls_ecp_group grp; 2380 2381 if( pub->grp.id == MBEDTLS_ECP_DP_NONE || 2382 pub->grp.id != prv->grp.id || 2383 mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) || 2384 mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) || 2385 mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) ) 2386 { 2387 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 2388 } 2389 2390 mbedtls_ecp_point_init( &Q ); 2391 mbedtls_ecp_group_init( &grp ); 2392 2393 /* mbedtls_ecp_mul() needs a non-const group... */ 2394 mbedtls_ecp_group_copy( &grp, &prv->grp ); 2395 2396 /* Also checks d is valid */ 2397 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) ); 2398 2399 if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) || 2400 mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) || 2401 mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) ) 2402 { 2403 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2404 goto cleanup; 2405 } 2406 2407 cleanup: 2408 mbedtls_ecp_point_free( &Q ); 2409 mbedtls_ecp_group_free( &grp ); 2410 2411 return( ret ); 2412 } 2413 2414 #if defined(MBEDTLS_SELF_TEST) 2415 2416 #if defined(ECP_ONE_STEP_KDF) 2417 /* 2418 * There are no test vectors from NIST for the One-Step KDF in SP 800-56C, 2419 * but unofficial ones can be found at: 2420 * https://github.com/patrickfav/singlestep-kdf/wiki/NIST-SP-800-56C-Rev1:-Non-Official-Test-Vectors 2421 * 2422 * We only use the ones with empty fixedInfo, and for brevity's sake, only 2423 * 40-bytes output (with SHA-256 that's more than one block, and with SHA-512 2424 * less than one block). 2425 */ 2426 #if defined(MBEDTLS_SHA512_C) 2427 2428 static const uint8_t test_kdf_z[16] = { 2429 0x3b, 0xa9, 0x79, 0xe9, 0xbc, 0x5e, 0x3e, 0xc7, 2430 0x61, 0x30, 0x36, 0xb6, 0xf5, 0x1c, 0xd5, 0xaa, 2431 }; 2432 static const uint8_t test_kdf_out[40] = { 2433 0x3e, 0xf6, 0xda, 0xf9, 0x51, 0x60, 0x70, 0x5f, 2434 0xdf, 0x21, 0xcd, 0xab, 0xac, 0x25, 0x7b, 0x05, 2435 0xfe, 0xc1, 0xab, 0x7c, 0xc9, 0x68, 0x43, 0x25, 2436 0x8a, 0xfc, 0x40, 0x6e, 0x5b, 0xf7, 0x98, 0x27, 2437 0x10, 0xfa, 0x7b, 0x93, 0x52, 0xd4, 0x16, 0xaa, 2438 }; 2439 2440 #elif defined(MBEDTLS_SHA256_C) 2441 2442 static const uint8_t test_kdf_z[16] = { 2443 0xc8, 0x3e, 0x35, 0x8e, 0x99, 0xa6, 0x89, 0xc6, 2444 0x7d, 0xb4, 0xfe, 0x39, 0xcf, 0x8f, 0x26, 0xe1, 2445 }; 2446 static const uint8_t test_kdf_out[40] = { 2447 0x7d, 0xf6, 0x41, 0xf8, 0x3c, 0x47, 0xdc, 0x28, 2448 0x5f, 0x7f, 0xaa, 0xde, 0x05, 0x64, 0xd6, 0x25, 2449 0x00, 0x6a, 0x47, 0xd9, 0x1e, 0xa4, 0xa0, 0x8c, 2450 0xd7, 0xf7, 0x0c, 0x99, 0xaa, 0xa0, 0x72, 0x66, 2451 0x69, 0x0e, 0x25, 0xaa, 0xa1, 0x63, 0x14, 0x79, 2452 }; 2453 2454 #endif 2455 2456 static int ecp_kdf_self_test( void ) 2457 { 2458 int ret; 2459 ecp_drbg_context kdf_ctx; 2460 mbedtls_mpi scalar; 2461 uint8_t out[sizeof( test_kdf_out )]; 2462 2463 ecp_drbg_init( &kdf_ctx ); 2464 mbedtls_mpi_init( &scalar ); 2465 memset( out, 0, sizeof( out ) ); 2466 2467 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &scalar, 2468 test_kdf_z, sizeof( test_kdf_z ) ) ); 2469 2470 MBEDTLS_MPI_CHK( ecp_drbg_seed( &kdf_ctx, 2471 &scalar, sizeof( test_kdf_z ) ) ); 2472 2473 MBEDTLS_MPI_CHK( ecp_drbg_random( &kdf_ctx, out, sizeof( out ) ) ); 2474 2475 if( memcmp( out, test_kdf_out, sizeof( out ) ) != 0 ) 2476 ret = -1; 2477 2478 cleanup: 2479 ecp_drbg_free( &kdf_ctx ); 2480 mbedtls_mpi_free( &scalar ); 2481 2482 return( ret ); 2483 } 2484 #endif /* ECP_ONE_STEP_KDF */ 2485 2486 /* 2487 * Checkup routine 2488 */ 2489 int mbedtls_ecp_self_test( int verbose ) 2490 { 2491 int ret; 2492 size_t i; 2493 mbedtls_ecp_group grp; 2494 mbedtls_ecp_point R, P; 2495 mbedtls_mpi m; 2496 unsigned long add_c_prev, dbl_c_prev, mul_c_prev; 2497 /* exponents especially adapted for secp192r1 */ 2498 const char *exponents[] = 2499 { 2500 "000000000000000000000000000000000000000000000001", /* one */ 2501 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */ 2502 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */ 2503 "400000000000000000000000000000000000000000000000", /* one and zeros */ 2504 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */ 2505 "555555555555555555555555555555555555555555555555", /* 101010... */ 2506 }; 2507 2508 mbedtls_ecp_group_init( &grp ); 2509 mbedtls_ecp_point_init( &R ); 2510 mbedtls_ecp_point_init( &P ); 2511 mbedtls_mpi_init( &m ); 2512 2513 /* Use secp192r1 if available, or any available curve */ 2514 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) 2515 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) ); 2516 #else 2517 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) ); 2518 #endif 2519 2520 if( verbose != 0 ) 2521 mbedtls_printf( " ECP test #1 (constant op_count, base point G): " ); 2522 2523 /* Do a dummy multiplication first to trigger precomputation */ 2524 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) ); 2525 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) ); 2526 2527 add_count = 0; 2528 dbl_count = 0; 2529 mul_count = 0; 2530 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); 2531 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); 2532 2533 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) 2534 { 2535 add_c_prev = add_count; 2536 dbl_c_prev = dbl_count; 2537 mul_c_prev = mul_count; 2538 add_count = 0; 2539 dbl_count = 0; 2540 mul_count = 0; 2541 2542 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); 2543 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); 2544 2545 if( add_count != add_c_prev || 2546 dbl_count != dbl_c_prev || 2547 mul_count != mul_c_prev ) 2548 { 2549 if( verbose != 0 ) 2550 mbedtls_printf( "failed (%u)\n", (unsigned int) i ); 2551 2552 ret = 1; 2553 goto cleanup; 2554 } 2555 } 2556 2557 if( verbose != 0 ) 2558 mbedtls_printf( "passed\n" ); 2559 2560 if( verbose != 0 ) 2561 mbedtls_printf( " ECP test #2 (constant op_count, other point): " ); 2562 /* We computed P = 2G last time, use it */ 2563 2564 add_count = 0; 2565 dbl_count = 0; 2566 mul_count = 0; 2567 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); 2568 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); 2569 2570 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) 2571 { 2572 add_c_prev = add_count; 2573 dbl_c_prev = dbl_count; 2574 mul_c_prev = mul_count; 2575 add_count = 0; 2576 dbl_count = 0; 2577 mul_count = 0; 2578 2579 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); 2580 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); 2581 2582 if( add_count != add_c_prev || 2583 dbl_count != dbl_c_prev || 2584 mul_count != mul_c_prev ) 2585 { 2586 if( verbose != 0 ) 2587 mbedtls_printf( "failed (%u)\n", (unsigned int) i ); 2588 2589 ret = 1; 2590 goto cleanup; 2591 } 2592 } 2593 2594 if( verbose != 0 ) 2595 mbedtls_printf( "passed\n" ); 2596 2597 #if defined(ECP_ONE_STEP_KDF) 2598 if( verbose != 0 ) 2599 mbedtls_printf( " ECP test #3 (internal KDF): " ); 2600 2601 ret = ecp_kdf_self_test(); 2602 if( ret != 0 ) 2603 { 2604 if( verbose != 0 ) 2605 mbedtls_printf( "failed\n" ); 2606 2607 ret = 1; 2608 goto cleanup; 2609 } 2610 2611 if( verbose != 0 ) 2612 mbedtls_printf( "passed\n" ); 2613 #endif /* ECP_ONE_STEP_KDF */ 2614 2615 cleanup: 2616 2617 if( ret < 0 && verbose != 0 ) 2618 mbedtls_printf( "Unexpected error, return code = %08X\n", ret ); 2619 2620 mbedtls_ecp_group_free( &grp ); 2621 mbedtls_ecp_point_free( &R ); 2622 mbedtls_ecp_point_free( &P ); 2623 mbedtls_mpi_free( &m ); 2624 2625 if( verbose != 0 ) 2626 mbedtls_printf( "\n" ); 2627 2628 return( ret ); 2629 } 2630 2631 #endif /* MBEDTLS_SELF_TEST */ 2632 2633 #endif /* !MBEDTLS_ECP_ALT */ 2634 2635 #endif /* MBEDTLS_ECP_C */ 2636