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