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 lazily 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 /* There are two cases where T is not stored in grp: 1454 * - P != G 1455 * - An intermediate operation failed before setting grp->T 1456 * In either case, T must be freed. 1457 */ 1458 if( T != NULL && T != grp->T ) 1459 { 1460 for( i = 0; i < pre_len; i++ ) 1461 mbedtls_ecp_point_free( &T[i] ); 1462 mbedtls_free( T ); 1463 } 1464 1465 mbedtls_mpi_free( &M ); 1466 mbedtls_mpi_free( &mm ); 1467 1468 if( ret != 0 ) 1469 mbedtls_ecp_point_free( R ); 1470 1471 return( ret ); 1472 } 1473 1474 #endif /* ECP_SHORTWEIERSTRASS */ 1475 1476 #if defined(ECP_MONTGOMERY) 1477 /* 1478 * For Montgomery curves, we do all the internal arithmetic in projective 1479 * coordinates. Import/export of points uses only the x coordinates, which is 1480 * internaly represented as X / Z. 1481 * 1482 * For scalar multiplication, we'll use a Montgomery ladder. 1483 */ 1484 1485 /* 1486 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1 1487 * Cost: 1M + 1I 1488 */ 1489 static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P ) 1490 { 1491 int ret; 1492 1493 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) 1494 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 1495 { 1496 return mbedtls_internal_ecp_normalize_mxz( grp, P ); 1497 } 1498 #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */ 1499 1500 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) ); 1501 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X ); 1502 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) ); 1503 1504 cleanup: 1505 return( ret ); 1506 } 1507 1508 /* 1509 * Randomize projective x/z coordinates: 1510 * (X, Z) -> (l X, l Z) for random l 1511 * This is sort of the reverse operation of ecp_normalize_mxz(). 1512 * 1513 * This countermeasure was first suggested in [2]. 1514 * Cost: 2M 1515 */ 1516 static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P, 1517 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 1518 { 1519 int ret; 1520 mbedtls_mpi l; 1521 size_t p_size; 1522 int count = 0; 1523 1524 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) 1525 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 1526 { 1527 return mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng ); 1528 } 1529 #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */ 1530 1531 p_size = ( grp->pbits + 7 ) / 8; 1532 mbedtls_mpi_init( &l ); 1533 1534 /* Generate l such that 1 < l < p */ 1535 do 1536 { 1537 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) ); 1538 1539 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) 1540 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) ); 1541 1542 if( count++ > 10 ) 1543 return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); 1544 } 1545 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ); 1546 1547 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X ); 1548 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z ); 1549 1550 cleanup: 1551 mbedtls_mpi_free( &l ); 1552 1553 return( ret ); 1554 } 1555 1556 /* 1557 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q), 1558 * for Montgomery curves in x/z coordinates. 1559 * 1560 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3 1561 * with 1562 * d = X1 1563 * P = (X2, Z2) 1564 * Q = (X3, Z3) 1565 * R = (X4, Z4) 1566 * S = (X5, Z5) 1567 * and eliminating temporary variables tO, ..., t4. 1568 * 1569 * Cost: 5M + 4S 1570 */ 1571 static int ecp_double_add_mxz( const mbedtls_ecp_group *grp, 1572 mbedtls_ecp_point *R, mbedtls_ecp_point *S, 1573 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q, 1574 const mbedtls_mpi *d ) 1575 { 1576 int ret; 1577 mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB; 1578 1579 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) 1580 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 1581 { 1582 return mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d ); 1583 } 1584 #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */ 1585 1586 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B ); 1587 mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C ); 1588 mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB ); 1589 1590 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A ); 1591 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA ); 1592 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B ); 1593 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB ); 1594 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E ); 1595 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C ); 1596 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D ); 1597 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA ); 1598 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB ); 1599 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X ); 1600 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X ); 1601 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z ); 1602 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z ); 1603 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z ); 1604 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X ); 1605 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z ); 1606 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z ); 1607 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z ); 1608 1609 cleanup: 1610 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B ); 1611 mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C ); 1612 mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB ); 1613 1614 return( ret ); 1615 } 1616 1617 /* 1618 * Multiplication with Montgomery ladder in x/z coordinates, 1619 * for curves in Montgomery form 1620 */ 1621 static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1622 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 1623 int (*f_rng)(void *, unsigned char *, size_t), 1624 void *p_rng ) 1625 { 1626 int ret; 1627 size_t i; 1628 unsigned char b; 1629 mbedtls_ecp_point RP; 1630 mbedtls_mpi PX; 1631 1632 mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX ); 1633 1634 /* Save PX and read from P before writing to R, in case P == R */ 1635 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) ); 1636 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) ); 1637 1638 /* Set R to zero in modified x/z coordinates */ 1639 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X, 1 ) ); 1640 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) ); 1641 mbedtls_mpi_free( &R->Y ); 1642 1643 /* RP.X might be sligtly larger than P, so reduce it */ 1644 MOD_ADD( RP.X ); 1645 1646 /* Randomize coordinates of the starting point */ 1647 if( f_rng != NULL ) 1648 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) ); 1649 1650 /* Loop invariant: R = result so far, RP = R + P */ 1651 i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */ 1652 while( i-- > 0 ) 1653 { 1654 b = mbedtls_mpi_get_bit( m, i ); 1655 /* 1656 * if (b) R = 2R + P else R = 2R, 1657 * which is: 1658 * if (b) double_add( RP, R, RP, R ) 1659 * else double_add( R, RP, R, RP ) 1660 * but using safe conditional swaps to avoid leaks 1661 */ 1662 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) ); 1663 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); 1664 MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) ); 1665 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) ); 1666 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); 1667 } 1668 1669 MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) ); 1670 1671 cleanup: 1672 mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX ); 1673 1674 return( ret ); 1675 } 1676 1677 #endif /* ECP_MONTGOMERY */ 1678 1679 /* 1680 * Multiplication R = m * P 1681 */ 1682 int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1683 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 1684 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 1685 { 1686 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 1687 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 1688 char is_grp_capable = 0; 1689 #endif 1690 1691 /* Common sanity checks */ 1692 if( mbedtls_mpi_cmp_int( &P->Z, 1 ) != 0 ) 1693 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 1694 1695 if( ( ret = mbedtls_ecp_check_privkey( grp, m ) ) != 0 || 1696 ( ret = mbedtls_ecp_check_pubkey( grp, P ) ) != 0 ) 1697 return( ret ); 1698 1699 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 1700 if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) 1701 { 1702 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); 1703 } 1704 1705 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 1706 #if defined(ECP_MONTGOMERY) 1707 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 1708 ret = ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ); 1709 1710 #endif 1711 #if defined(ECP_SHORTWEIERSTRASS) 1712 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 1713 ret = ecp_mul_comb( grp, R, m, P, f_rng, p_rng ); 1714 1715 #endif 1716 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 1717 cleanup: 1718 1719 if ( is_grp_capable ) 1720 { 1721 mbedtls_internal_ecp_free( grp ); 1722 } 1723 1724 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 1725 return( ret ); 1726 } 1727 1728 #if defined(ECP_SHORTWEIERSTRASS) 1729 /* 1730 * Check that an affine point is valid as a public key, 1731 * short weierstrass curves (SEC1 3.2.3.1) 1732 */ 1733 static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 1734 { 1735 int ret; 1736 mbedtls_mpi YY, RHS; 1737 1738 /* pt coordinates must be normalized for our checks */ 1739 if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 || 1740 mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 || 1741 mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 || 1742 mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 ) 1743 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 1744 1745 mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS ); 1746 1747 /* 1748 * YY = Y^2 1749 * RHS = X (X^2 + A) + B = X^3 + A X + B 1750 */ 1751 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY ); 1752 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS ); 1753 1754 /* Special case for A = -3 */ 1755 if( grp->A.p == NULL ) 1756 { 1757 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS ); 1758 } 1759 else 1760 { 1761 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS ); 1762 } 1763 1764 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS ); 1765 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS ); 1766 1767 if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 ) 1768 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 1769 1770 cleanup: 1771 1772 mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS ); 1773 1774 return( ret ); 1775 } 1776 #endif /* ECP_SHORTWEIERSTRASS */ 1777 1778 /* 1779 * R = m * P with shortcuts for m == 1 and m == -1 1780 * NOT constant-time - ONLY for short Weierstrass! 1781 */ 1782 static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp, 1783 mbedtls_ecp_point *R, 1784 const mbedtls_mpi *m, 1785 const mbedtls_ecp_point *P ) 1786 { 1787 int ret; 1788 1789 if( mbedtls_mpi_cmp_int( m, 1 ) == 0 ) 1790 { 1791 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); 1792 } 1793 else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 ) 1794 { 1795 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); 1796 if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 ) 1797 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) ); 1798 } 1799 else 1800 { 1801 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, R, m, P, NULL, NULL ) ); 1802 } 1803 1804 cleanup: 1805 return( ret ); 1806 } 1807 1808 /* 1809 * Linear combination 1810 * NOT constant-time 1811 */ 1812 int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1813 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 1814 const mbedtls_mpi *n, const mbedtls_ecp_point *Q ) 1815 { 1816 int ret; 1817 mbedtls_ecp_point mP; 1818 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 1819 char is_grp_capable = 0; 1820 #endif 1821 1822 if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS ) 1823 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 1824 1825 mbedtls_ecp_point_init( &mP ); 1826 1827 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, &mP, m, P ) ); 1828 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, R, n, Q ) ); 1829 1830 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 1831 if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) 1832 { 1833 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); 1834 } 1835 1836 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 1837 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, &mP, R ) ); 1838 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) ); 1839 1840 cleanup: 1841 1842 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 1843 if ( is_grp_capable ) 1844 { 1845 mbedtls_internal_ecp_free( grp ); 1846 } 1847 1848 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 1849 mbedtls_ecp_point_free( &mP ); 1850 1851 return( ret ); 1852 } 1853 1854 1855 #if defined(ECP_MONTGOMERY) 1856 /* 1857 * Check validity of a public key for Montgomery curves with x-only schemes 1858 */ 1859 static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 1860 { 1861 /* [Curve25519 p. 5] Just check X is the correct number of bytes */ 1862 if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 ) 1863 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 1864 1865 return( 0 ); 1866 } 1867 #endif /* ECP_MONTGOMERY */ 1868 1869 /* 1870 * Check that a point is valid as a public key 1871 */ 1872 int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 1873 { 1874 /* Must use affine coordinates */ 1875 if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 ) 1876 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 1877 1878 #if defined(ECP_MONTGOMERY) 1879 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 1880 return( ecp_check_pubkey_mx( grp, pt ) ); 1881 #endif 1882 #if defined(ECP_SHORTWEIERSTRASS) 1883 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 1884 return( ecp_check_pubkey_sw( grp, pt ) ); 1885 #endif 1886 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 1887 } 1888 1889 /* 1890 * Check that an mbedtls_mpi is valid as a private key 1891 */ 1892 int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, const mbedtls_mpi *d ) 1893 { 1894 #if defined(ECP_MONTGOMERY) 1895 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 1896 { 1897 /* see [Curve25519] page 5 */ 1898 if( mbedtls_mpi_get_bit( d, 0 ) != 0 || 1899 mbedtls_mpi_get_bit( d, 1 ) != 0 || 1900 mbedtls_mpi_get_bit( d, 2 ) != 0 || 1901 mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */ 1902 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 1903 else 1904 return( 0 ); 1905 } 1906 #endif /* ECP_MONTGOMERY */ 1907 #if defined(ECP_SHORTWEIERSTRASS) 1908 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 1909 { 1910 /* see SEC1 3.2 */ 1911 if( mbedtls_mpi_cmp_int( d, 1 ) < 0 || 1912 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 ) 1913 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 1914 else 1915 return( 0 ); 1916 } 1917 #endif /* ECP_SHORTWEIERSTRASS */ 1918 1919 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 1920 } 1921 1922 /* 1923 * Generate a private key 1924 */ 1925 int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp, 1926 mbedtls_mpi *d, 1927 int (*f_rng)(void *, unsigned char *, size_t), 1928 void *p_rng ) 1929 { 1930 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 1931 size_t n_size = ( grp->nbits + 7 ) / 8; 1932 1933 #if defined(ECP_MONTGOMERY) 1934 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 1935 { 1936 /* [M225] page 5 */ 1937 size_t b; 1938 1939 do { 1940 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) ); 1941 } while( mbedtls_mpi_bitlen( d ) == 0); 1942 1943 /* Make sure the most significant bit is nbits */ 1944 b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */ 1945 if( b > grp->nbits ) 1946 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) ); 1947 else 1948 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits, 1 ) ); 1949 1950 /* Make sure the last three bits are unset */ 1951 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) ); 1952 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) ); 1953 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) ); 1954 } 1955 #endif /* ECP_MONTGOMERY */ 1956 1957 #if defined(ECP_SHORTWEIERSTRASS) 1958 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 1959 { 1960 /* SEC1 3.2.1: Generate d such that 1 <= n < N */ 1961 int count = 0; 1962 1963 /* 1964 * Match the procedure given in RFC 6979 (deterministic ECDSA): 1965 * - use the same byte ordering; 1966 * - keep the leftmost nbits bits of the generated octet string; 1967 * - try until result is in the desired range. 1968 * This also avoids any biais, which is especially important for ECDSA. 1969 */ 1970 do 1971 { 1972 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) ); 1973 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) ); 1974 1975 /* 1976 * Each try has at worst a probability 1/2 of failing (the msb has 1977 * a probability 1/2 of being 0, and then the result will be < N), 1978 * so after 30 tries failure probability is a most 2**(-30). 1979 * 1980 * For most curves, 1 try is enough with overwhelming probability, 1981 * since N starts with a lot of 1s in binary, but some curves 1982 * such as secp224k1 are actually very close to the worst case. 1983 */ 1984 if( ++count > 30 ) 1985 return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); 1986 } 1987 while( mbedtls_mpi_cmp_int( d, 1 ) < 0 || 1988 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 ); 1989 } 1990 #endif /* ECP_SHORTWEIERSTRASS */ 1991 1992 cleanup: 1993 return( ret ); 1994 } 1995 1996 /* 1997 * Generate a keypair with configurable base point 1998 */ 1999 int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp, 2000 const mbedtls_ecp_point *G, 2001 mbedtls_mpi *d, mbedtls_ecp_point *Q, 2002 int (*f_rng)(void *, unsigned char *, size_t), 2003 void *p_rng ) 2004 { 2005 int ret; 2006 2007 MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, d, f_rng, p_rng ) ); 2008 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) ); 2009 2010 cleanup: 2011 return( ret ); 2012 } 2013 2014 /* 2015 * Generate key pair, wrapper for conventional base point 2016 */ 2017 int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp, 2018 mbedtls_mpi *d, mbedtls_ecp_point *Q, 2019 int (*f_rng)(void *, unsigned char *, size_t), 2020 void *p_rng ) 2021 { 2022 return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) ); 2023 } 2024 2025 /* 2026 * Generate a keypair, prettier wrapper 2027 */ 2028 int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, 2029 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 2030 { 2031 int ret; 2032 2033 if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 ) 2034 return( ret ); 2035 2036 return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) ); 2037 } 2038 2039 /* 2040 * Check a public-private key pair 2041 */ 2042 int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv ) 2043 { 2044 int ret; 2045 mbedtls_ecp_point Q; 2046 mbedtls_ecp_group grp; 2047 2048 if( pub->grp.id == MBEDTLS_ECP_DP_NONE || 2049 pub->grp.id != prv->grp.id || 2050 mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) || 2051 mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) || 2052 mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) ) 2053 { 2054 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 2055 } 2056 2057 mbedtls_ecp_point_init( &Q ); 2058 mbedtls_ecp_group_init( &grp ); 2059 2060 /* mbedtls_ecp_mul() needs a non-const group... */ 2061 mbedtls_ecp_group_copy( &grp, &prv->grp ); 2062 2063 /* Also checks d is valid */ 2064 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) ); 2065 2066 if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) || 2067 mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) || 2068 mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) ) 2069 { 2070 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2071 goto cleanup; 2072 } 2073 2074 cleanup: 2075 mbedtls_ecp_point_free( &Q ); 2076 mbedtls_ecp_group_free( &grp ); 2077 2078 return( ret ); 2079 } 2080 2081 #if defined(MBEDTLS_SELF_TEST) 2082 2083 /* 2084 * Checkup routine 2085 */ 2086 int mbedtls_ecp_self_test( int verbose ) 2087 { 2088 int ret; 2089 size_t i; 2090 mbedtls_ecp_group grp; 2091 mbedtls_ecp_point R, P; 2092 mbedtls_mpi m; 2093 unsigned long add_c_prev, dbl_c_prev, mul_c_prev; 2094 /* exponents especially adapted for secp192r1 */ 2095 const char *exponents[] = 2096 { 2097 "000000000000000000000000000000000000000000000001", /* one */ 2098 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */ 2099 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */ 2100 "400000000000000000000000000000000000000000000000", /* one and zeros */ 2101 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */ 2102 "555555555555555555555555555555555555555555555555", /* 101010... */ 2103 }; 2104 2105 mbedtls_ecp_group_init( &grp ); 2106 mbedtls_ecp_point_init( &R ); 2107 mbedtls_ecp_point_init( &P ); 2108 mbedtls_mpi_init( &m ); 2109 2110 /* Use secp192r1 if available, or any available curve */ 2111 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) 2112 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) ); 2113 #else 2114 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) ); 2115 #endif 2116 2117 if( verbose != 0 ) 2118 mbedtls_printf( " ECP test #1 (constant op_count, base point G): " ); 2119 2120 /* Do a dummy multiplication first to trigger precomputation */ 2121 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) ); 2122 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) ); 2123 2124 add_count = 0; 2125 dbl_count = 0; 2126 mul_count = 0; 2127 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); 2128 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); 2129 2130 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) 2131 { 2132 add_c_prev = add_count; 2133 dbl_c_prev = dbl_count; 2134 mul_c_prev = mul_count; 2135 add_count = 0; 2136 dbl_count = 0; 2137 mul_count = 0; 2138 2139 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); 2140 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); 2141 2142 if( add_count != add_c_prev || 2143 dbl_count != dbl_c_prev || 2144 mul_count != mul_c_prev ) 2145 { 2146 if( verbose != 0 ) 2147 mbedtls_printf( "failed (%u)\n", (unsigned int) i ); 2148 2149 ret = 1; 2150 goto cleanup; 2151 } 2152 } 2153 2154 if( verbose != 0 ) 2155 mbedtls_printf( "passed\n" ); 2156 2157 if( verbose != 0 ) 2158 mbedtls_printf( " ECP test #2 (constant op_count, other point): " ); 2159 /* We computed P = 2G last time, use it */ 2160 2161 add_count = 0; 2162 dbl_count = 0; 2163 mul_count = 0; 2164 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); 2165 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); 2166 2167 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) 2168 { 2169 add_c_prev = add_count; 2170 dbl_c_prev = dbl_count; 2171 mul_c_prev = mul_count; 2172 add_count = 0; 2173 dbl_count = 0; 2174 mul_count = 0; 2175 2176 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); 2177 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); 2178 2179 if( add_count != add_c_prev || 2180 dbl_count != dbl_c_prev || 2181 mul_count != mul_c_prev ) 2182 { 2183 if( verbose != 0 ) 2184 mbedtls_printf( "failed (%u)\n", (unsigned int) i ); 2185 2186 ret = 1; 2187 goto cleanup; 2188 } 2189 } 2190 2191 if( verbose != 0 ) 2192 mbedtls_printf( "passed\n" ); 2193 2194 cleanup: 2195 2196 if( ret < 0 && verbose != 0 ) 2197 mbedtls_printf( "Unexpected error, return code = %08X\n", ret ); 2198 2199 mbedtls_ecp_group_free( &grp ); 2200 mbedtls_ecp_point_free( &R ); 2201 mbedtls_ecp_point_free( &P ); 2202 mbedtls_mpi_free( &m ); 2203 2204 if( verbose != 0 ) 2205 mbedtls_printf( "\n" ); 2206 2207 return( ret ); 2208 } 2209 2210 #endif /* MBEDTLS_SELF_TEST */ 2211 2212 #endif /* !MBEDTLS_ECP_ALT */ 2213 2214 #endif /* MBEDTLS_ECP_C */ 2215