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