takashi kadono
/
Nucleo446_SSD1331
Important changes to repositories hosted on mbed.com
Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.
To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.
It is also possible to export all your personal repositories from the account settings page.
Embed:
(wiki syntax)
Show/hide line numbers
ecp.c
00001 /* 00002 * Elliptic curves over GF(p): generic functions 00003 * 00004 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved 00005 * SPDX-License-Identifier: Apache-2.0 00006 * 00007 * Licensed under the Apache License, Version 2.0 (the "License"); you may 00008 * not use this file except in compliance with the License. 00009 * You may obtain a copy of the License at 00010 * 00011 * http://www.apache.org/licenses/LICENSE-2.0 00012 * 00013 * Unless required by applicable law or agreed to in writing, software 00014 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 00015 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00016 * See the License for the specific language governing permissions and 00017 * limitations under the License. 00018 * 00019 * This file is part of mbed TLS (https://tls.mbed.org) 00020 */ 00021 00022 /* 00023 * References: 00024 * 00025 * SEC1 http://www.secg.org/index.php?action=secg,docs_secg 00026 * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone 00027 * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf 00028 * RFC 4492 for the related TLS structures and constants 00029 * RFC 7748 for the Curve448 and Curve25519 curve definitions 00030 * 00031 * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf 00032 * 00033 * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis 00034 * for elliptic curve cryptosystems. In : Cryptographic Hardware and 00035 * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302. 00036 * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25> 00037 * 00038 * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to 00039 * render ECC resistant against Side Channel Attacks. IACR Cryptology 00040 * ePrint Archive, 2004, vol. 2004, p. 342. 00041 * <http://eprint.iacr.org/2004/342.pdf> 00042 */ 00043 00044 #if !defined(MBEDTLS_CONFIG_FILE) 00045 #include "mbedtls/config.h" 00046 #else 00047 #include MBEDTLS_CONFIG_FILE 00048 #endif 00049 00050 #if defined(MBEDTLS_ECP_C) 00051 00052 #include "mbedtls/ecp.h" 00053 #include "mbedtls/threading.h" 00054 #include "mbedtls/platform_util.h" 00055 00056 #include <string.h> 00057 00058 #if !defined(MBEDTLS_ECP_ALT) 00059 00060 #if defined(MBEDTLS_PLATFORM_C) 00061 #include "mbedtls/platform.h" 00062 #else 00063 #include <stdlib.h> 00064 #include <stdio.h> 00065 #define mbedtls_printf printf 00066 #define mbedtls_calloc calloc 00067 #define mbedtls_free free 00068 #endif 00069 00070 #include "mbedtls/ecp_internal.h" 00071 00072 #if ( defined(__ARMCC_VERSION) || defined(_MSC_VER) ) && \ 00073 !defined(inline) && !defined(__cplusplus) 00074 #define inline __inline 00075 #endif 00076 00077 #if defined(MBEDTLS_SELF_TEST) 00078 /* 00079 * Counts of point addition and doubling, and field multiplications. 00080 * Used to test resistance of point multiplication to simple timing attacks. 00081 */ 00082 static unsigned long add_count, dbl_count, mul_count; 00083 #endif 00084 00085 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) || \ 00086 defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) || \ 00087 defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) || \ 00088 defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) || \ 00089 defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) || \ 00090 defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) || \ 00091 defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) || \ 00092 defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) || \ 00093 defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) || \ 00094 defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) || \ 00095 defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED) 00096 #define ECP_SHORTWEIERSTRASS 00097 #endif 00098 00099 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) || \ 00100 defined(MBEDTLS_ECP_DP_CURVE448_ENABLED) 00101 #define ECP_MONTGOMERY 00102 #endif 00103 00104 /* 00105 * Curve types: internal for now, might be exposed later 00106 */ 00107 typedef enum 00108 { 00109 ECP_TYPE_NONE = 0, 00110 ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */ 00111 ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */ 00112 } ecp_curve_type; 00113 00114 /* 00115 * List of supported curves: 00116 * - internal ID 00117 * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2) 00118 * - size in bits 00119 * - readable name 00120 * 00121 * Curves are listed in order: largest curves first, and for a given size, 00122 * fastest curves first. This provides the default order for the SSL module. 00123 * 00124 * Reminder: update profiles in x509_crt.c when adding a new curves! 00125 */ 00126 static const mbedtls_ecp_curve_info ecp_supported_curves[] = 00127 { 00128 #if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) 00129 { MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" }, 00130 #endif 00131 #if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) 00132 { MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" }, 00133 #endif 00134 #if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) 00135 { MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" }, 00136 #endif 00137 #if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) 00138 { MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" }, 00139 #endif 00140 #if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) 00141 { MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" }, 00142 #endif 00143 #if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED) 00144 { MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" }, 00145 #endif 00146 #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) 00147 { MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" }, 00148 #endif 00149 #if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) 00150 { MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" }, 00151 #endif 00152 #if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) 00153 { MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" }, 00154 #endif 00155 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) 00156 { MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" }, 00157 #endif 00158 #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) 00159 { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" }, 00160 #endif 00161 { MBEDTLS_ECP_DP_NONE, 0, 0, NULL }, 00162 }; 00163 00164 #define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \ 00165 sizeof( ecp_supported_curves[0] ) 00166 00167 static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES]; 00168 00169 /* 00170 * List of supported curves and associated info 00171 */ 00172 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void ) 00173 { 00174 return( ecp_supported_curves ); 00175 } 00176 00177 /* 00178 * List of supported curves, group ID only 00179 */ 00180 const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void ) 00181 { 00182 static int init_done = 0; 00183 00184 if( ! init_done ) 00185 { 00186 size_t i = 0; 00187 const mbedtls_ecp_curve_info *curve_info; 00188 00189 for( curve_info = mbedtls_ecp_curve_list(); 00190 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 00191 curve_info++ ) 00192 { 00193 ecp_supported_grp_id[i++] = curve_info->grp_id ; 00194 } 00195 ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE; 00196 00197 init_done = 1; 00198 } 00199 00200 return( ecp_supported_grp_id ); 00201 } 00202 00203 /* 00204 * Get the curve info for the internal identifier 00205 */ 00206 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id ) 00207 { 00208 const mbedtls_ecp_curve_info *curve_info; 00209 00210 for( curve_info = mbedtls_ecp_curve_list(); 00211 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 00212 curve_info++ ) 00213 { 00214 if( curve_info->grp_id == grp_id ) 00215 return( curve_info ); 00216 } 00217 00218 return( NULL ); 00219 } 00220 00221 /* 00222 * Get the curve info from the TLS identifier 00223 */ 00224 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id ) 00225 { 00226 const mbedtls_ecp_curve_info *curve_info; 00227 00228 for( curve_info = mbedtls_ecp_curve_list(); 00229 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 00230 curve_info++ ) 00231 { 00232 if( curve_info->tls_id == tls_id ) 00233 return( curve_info ); 00234 } 00235 00236 return( NULL ); 00237 } 00238 00239 /* 00240 * Get the curve info from the name 00241 */ 00242 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name ) 00243 { 00244 const mbedtls_ecp_curve_info *curve_info; 00245 00246 for( curve_info = mbedtls_ecp_curve_list(); 00247 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 00248 curve_info++ ) 00249 { 00250 if( strcmp( curve_info->name , name ) == 0 ) 00251 return( curve_info ); 00252 } 00253 00254 return( NULL ); 00255 } 00256 00257 /* 00258 * Get the type of a curve 00259 */ 00260 static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp ) 00261 { 00262 if( grp->G .X .p == NULL ) 00263 return( ECP_TYPE_NONE ); 00264 00265 if( grp->G .Y .p == NULL ) 00266 return( ECP_TYPE_MONTGOMERY ); 00267 else 00268 return( ECP_TYPE_SHORT_WEIERSTRASS ); 00269 } 00270 00271 /* 00272 * Initialize (the components of) a point 00273 */ 00274 void mbedtls_ecp_point_init( mbedtls_ecp_point *pt ) 00275 { 00276 if( pt == NULL ) 00277 return; 00278 00279 mbedtls_mpi_init( &pt->X ); 00280 mbedtls_mpi_init( &pt->Y ); 00281 mbedtls_mpi_init( &pt->Z ); 00282 } 00283 00284 /* 00285 * Initialize (the components of) a group 00286 */ 00287 void mbedtls_ecp_group_init( mbedtls_ecp_group *grp ) 00288 { 00289 if( grp == NULL ) 00290 return; 00291 00292 memset( grp, 0, sizeof( mbedtls_ecp_group ) ); 00293 } 00294 00295 /* 00296 * Initialize (the components of) a key pair 00297 */ 00298 void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key ) 00299 { 00300 if( key == NULL ) 00301 return; 00302 00303 mbedtls_ecp_group_init( &key->grp ); 00304 mbedtls_mpi_init( &key->d ); 00305 mbedtls_ecp_point_init( &key->Q ); 00306 } 00307 00308 /* 00309 * Unallocate (the components of) a point 00310 */ 00311 void mbedtls_ecp_point_free( mbedtls_ecp_point *pt ) 00312 { 00313 if( pt == NULL ) 00314 return; 00315 00316 mbedtls_mpi_free( &( pt->X ) ); 00317 mbedtls_mpi_free( &( pt->Y ) ); 00318 mbedtls_mpi_free( &( pt->Z ) ); 00319 } 00320 00321 /* 00322 * Unallocate (the components of) a group 00323 */ 00324 void mbedtls_ecp_group_free( mbedtls_ecp_group *grp ) 00325 { 00326 size_t i; 00327 00328 if( grp == NULL ) 00329 return; 00330 00331 if( grp->h != 1 ) 00332 { 00333 mbedtls_mpi_free( &grp->P ); 00334 mbedtls_mpi_free( &grp->A ); 00335 mbedtls_mpi_free( &grp->B ); 00336 mbedtls_ecp_point_free( &grp->G ); 00337 mbedtls_mpi_free( &grp->N ); 00338 } 00339 00340 if( grp->T != NULL ) 00341 { 00342 for( i = 0; i < grp->T_size ; i++ ) 00343 mbedtls_ecp_point_free( &grp->T [i] ); 00344 mbedtls_free( grp->T ); 00345 } 00346 00347 mbedtls_platform_zeroize( grp, sizeof( mbedtls_ecp_group ) ); 00348 } 00349 00350 /* 00351 * Unallocate (the components of) a key pair 00352 */ 00353 void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key ) 00354 { 00355 if( key == NULL ) 00356 return; 00357 00358 mbedtls_ecp_group_free( &key->grp ); 00359 mbedtls_mpi_free( &key->d ); 00360 mbedtls_ecp_point_free( &key->Q ); 00361 } 00362 00363 /* 00364 * Copy the contents of a point 00365 */ 00366 int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q ) 00367 { 00368 int ret; 00369 00370 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X , &Q->X ) ); 00371 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y , &Q->Y ) ); 00372 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z , &Q->Z ) ); 00373 00374 cleanup: 00375 return( ret ); 00376 } 00377 00378 /* 00379 * Copy the contents of a group object 00380 */ 00381 int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src ) 00382 { 00383 return mbedtls_ecp_group_load( dst, src->id ); 00384 } 00385 00386 /* 00387 * Set point to zero 00388 */ 00389 int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt ) 00390 { 00391 int ret; 00392 00393 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) ); 00394 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y , 1 ) ); 00395 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 0 ) ); 00396 00397 cleanup: 00398 return( ret ); 00399 } 00400 00401 /* 00402 * Tell if a point is zero 00403 */ 00404 int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt ) 00405 { 00406 return( mbedtls_mpi_cmp_int( &pt->Z , 0 ) == 0 ); 00407 } 00408 00409 /* 00410 * Compare two points lazyly 00411 */ 00412 int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P, 00413 const mbedtls_ecp_point *Q ) 00414 { 00415 if( mbedtls_mpi_cmp_mpi( &P->X , &Q->X ) == 0 && 00416 mbedtls_mpi_cmp_mpi( &P->Y , &Q->Y ) == 0 && 00417 mbedtls_mpi_cmp_mpi( &P->Z , &Q->Z ) == 0 ) 00418 { 00419 return( 0 ); 00420 } 00421 00422 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00423 } 00424 00425 /* 00426 * Import a non-zero point from ASCII strings 00427 */ 00428 int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix, 00429 const char *x, const char *y ) 00430 { 00431 int ret; 00432 00433 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X , radix, x ) ); 00434 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y , radix, y ) ); 00435 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z , 1 ) ); 00436 00437 cleanup: 00438 return( ret ); 00439 } 00440 00441 /* 00442 * Export a point into unsigned binary data (SEC1 2.3.3) 00443 */ 00444 int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *P, 00445 int format, size_t *olen, 00446 unsigned char *buf, size_t buflen ) 00447 { 00448 int ret = 0; 00449 size_t plen; 00450 00451 if( format != MBEDTLS_ECP_PF_UNCOMPRESSED && 00452 format != MBEDTLS_ECP_PF_COMPRESSED ) 00453 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00454 00455 /* 00456 * Common case: P == 0 00457 */ 00458 if( mbedtls_mpi_cmp_int( &P->Z , 0 ) == 0 ) 00459 { 00460 if( buflen < 1 ) 00461 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); 00462 00463 buf[0] = 0x00; 00464 *olen = 1; 00465 00466 return( 0 ); 00467 } 00468 00469 plen = mbedtls_mpi_size( &grp->P ); 00470 00471 if( format == MBEDTLS_ECP_PF_UNCOMPRESSED ) 00472 { 00473 *olen = 2 * plen + 1; 00474 00475 if( buflen < *olen ) 00476 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); 00477 00478 buf[0] = 0x04; 00479 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X , buf + 1, plen ) ); 00480 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y , buf + 1 + plen, plen ) ); 00481 } 00482 else if( format == MBEDTLS_ECP_PF_COMPRESSED ) 00483 { 00484 *olen = plen + 1; 00485 00486 if( buflen < *olen ) 00487 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); 00488 00489 buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y , 0 ); 00490 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X , buf + 1, plen ) ); 00491 } 00492 00493 cleanup: 00494 return( ret ); 00495 } 00496 00497 /* 00498 * Import a point from unsigned binary data (SEC1 2.3.4) 00499 */ 00500 int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, 00501 const unsigned char *buf, size_t ilen ) 00502 { 00503 int ret; 00504 size_t plen; 00505 00506 if( ilen < 1 ) 00507 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00508 00509 if( buf[0] == 0x00 ) 00510 { 00511 if( ilen == 1 ) 00512 return( mbedtls_ecp_set_zero( pt ) ); 00513 else 00514 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00515 } 00516 00517 plen = mbedtls_mpi_size( &grp->P ); 00518 00519 if( buf[0] != 0x04 ) 00520 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 00521 00522 if( ilen != 2 * plen + 1 ) 00523 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00524 00525 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X , buf + 1, plen ) ); 00526 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y , buf + 1 + plen, plen ) ); 00527 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 1 ) ); 00528 00529 cleanup: 00530 return( ret ); 00531 } 00532 00533 /* 00534 * Import a point from a TLS ECPoint record (RFC 4492) 00535 * struct { 00536 * opaque point <1..2^8-1>; 00537 * } ECPoint; 00538 */ 00539 int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, 00540 const unsigned char **buf, size_t buf_len ) 00541 { 00542 unsigned char data_len; 00543 const unsigned char *buf_start; 00544 00545 /* 00546 * We must have at least two bytes (1 for length, at least one for data) 00547 */ 00548 if( buf_len < 2 ) 00549 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00550 00551 data_len = *(*buf)++; 00552 if( data_len < 1 || data_len > buf_len - 1 ) 00553 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00554 00555 /* 00556 * Save buffer start for read_binary and update buf 00557 */ 00558 buf_start = *buf; 00559 *buf += data_len; 00560 00561 return mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len ); 00562 } 00563 00564 /* 00565 * Export a point as a TLS ECPoint record (RFC 4492) 00566 * struct { 00567 * opaque point <1..2^8-1>; 00568 * } ECPoint; 00569 */ 00570 int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt, 00571 int format, size_t *olen, 00572 unsigned char *buf, size_t blen ) 00573 { 00574 int ret; 00575 00576 /* 00577 * buffer length must be at least one, for our length byte 00578 */ 00579 if( blen < 1 ) 00580 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00581 00582 if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format, 00583 olen, buf + 1, blen - 1) ) != 0 ) 00584 return( ret ); 00585 00586 /* 00587 * write length to the first byte and update total length 00588 */ 00589 buf[0] = (unsigned char) *olen; 00590 ++*olen; 00591 00592 return( 0 ); 00593 } 00594 00595 /* 00596 * Set a group from an ECParameters record (RFC 4492) 00597 */ 00598 int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp, const unsigned char **buf, size_t len ) 00599 { 00600 uint16_t tls_id; 00601 const mbedtls_ecp_curve_info *curve_info; 00602 00603 /* 00604 * We expect at least three bytes (see below) 00605 */ 00606 if( len < 3 ) 00607 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00608 00609 /* 00610 * First byte is curve_type; only named_curve is handled 00611 */ 00612 if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE ) 00613 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00614 00615 /* 00616 * Next two bytes are the namedcurve value 00617 */ 00618 tls_id = *(*buf)++; 00619 tls_id <<= 8; 00620 tls_id |= *(*buf)++; 00621 00622 if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL ) 00623 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 00624 00625 return mbedtls_ecp_group_load( grp, curve_info->grp_id ); 00626 } 00627 00628 /* 00629 * Write the ECParameters record corresponding to a group (RFC 4492) 00630 */ 00631 int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen, 00632 unsigned char *buf, size_t blen ) 00633 { 00634 const mbedtls_ecp_curve_info *curve_info; 00635 00636 if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL ) 00637 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00638 00639 /* 00640 * We are going to write 3 bytes (see below) 00641 */ 00642 *olen = 3; 00643 if( blen < *olen ) 00644 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL ); 00645 00646 /* 00647 * First byte is curve_type, always named_curve 00648 */ 00649 *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE; 00650 00651 /* 00652 * Next two bytes are the namedcurve value 00653 */ 00654 buf[0] = curve_info->tls_id >> 8; 00655 buf[1] = curve_info->tls_id & 0xFF; 00656 00657 return( 0 ); 00658 } 00659 00660 /* 00661 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi. 00662 * See the documentation of struct mbedtls_ecp_group. 00663 * 00664 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf. 00665 */ 00666 static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp ) 00667 { 00668 int ret; 00669 00670 if( grp->modp == NULL ) 00671 return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) ); 00672 00673 /* N->s < 0 is a much faster test, which fails only if N is 0 */ 00674 if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) || 00675 mbedtls_mpi_bitlen( N ) > 2 * grp->pbits ) 00676 { 00677 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 00678 } 00679 00680 MBEDTLS_MPI_CHK( grp->modp ( N ) ); 00681 00682 /* N->s < 0 is a much faster test, which fails only if N is 0 */ 00683 while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) 00684 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) ); 00685 00686 while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 ) 00687 /* we known P, N and the result are positive */ 00688 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) ); 00689 00690 cleanup: 00691 return( ret ); 00692 } 00693 00694 /* 00695 * Fast mod-p functions expect their argument to be in the 0..p^2 range. 00696 * 00697 * In order to guarantee that, we need to ensure that operands of 00698 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will 00699 * bring the result back to this range. 00700 * 00701 * The following macros are shortcuts for doing that. 00702 */ 00703 00704 /* 00705 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi 00706 */ 00707 #if defined(MBEDTLS_SELF_TEST) 00708 #define INC_MUL_COUNT mul_count++; 00709 #else 00710 #define INC_MUL_COUNT 00711 #endif 00712 00713 #define MOD_MUL( N ) do { MBEDTLS_MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \ 00714 while( 0 ) 00715 00716 /* 00717 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi 00718 * N->s < 0 is a very fast test, which fails only if N is 0 00719 */ 00720 #define MOD_SUB( N ) \ 00721 while( N.s < 0 && mbedtls_mpi_cmp_int( &N, 0 ) != 0 ) \ 00722 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &N, &N, &grp->P ) ) 00723 00724 /* 00725 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int. 00726 * We known P, N and the result are positive, so sub_abs is correct, and 00727 * a bit faster. 00728 */ 00729 #define MOD_ADD( N ) \ 00730 while( mbedtls_mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \ 00731 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &N, &N, &grp->P ) ) 00732 00733 #if defined(ECP_SHORTWEIERSTRASS) 00734 /* 00735 * For curves in short Weierstrass form, we do all the internal operations in 00736 * Jacobian coordinates. 00737 * 00738 * For multiplication, we'll use a comb method with coutermeasueres against 00739 * SPA, hence timing attacks. 00740 */ 00741 00742 /* 00743 * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1) 00744 * Cost: 1N := 1I + 3M + 1S 00745 */ 00746 static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt ) 00747 { 00748 int ret; 00749 mbedtls_mpi Zi, ZZi; 00750 00751 if( mbedtls_mpi_cmp_int( &pt->Z , 0 ) == 0 ) 00752 return( 0 ); 00753 00754 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) 00755 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 00756 { 00757 return mbedtls_internal_ecp_normalize_jac( grp, pt ); 00758 } 00759 #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */ 00760 mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi ); 00761 00762 /* 00763 * X = X / Z^2 mod p 00764 */ 00765 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z , &grp->P ) ); 00766 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); 00767 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X , &pt->X , &ZZi ) ); MOD_MUL( pt->X ); 00768 00769 /* 00770 * Y = Y / Z^3 mod p 00771 */ 00772 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y , &pt->Y , &ZZi ) ); MOD_MUL( pt->Y ); 00773 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y , &pt->Y , &Zi ) ); MOD_MUL( pt->Y ); 00774 00775 /* 00776 * Z = 1 00777 */ 00778 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 1 ) ); 00779 00780 cleanup: 00781 00782 mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi ); 00783 00784 return( ret ); 00785 } 00786 00787 /* 00788 * Normalize jacobian coordinates of an array of (pointers to) points, 00789 * using Montgomery's trick to perform only one inversion mod P. 00790 * (See for example Cohen's "A Course in Computational Algebraic Number 00791 * Theory", Algorithm 10.3.4.) 00792 * 00793 * Warning: fails (returning an error) if one of the points is zero! 00794 * This should never happen, see choice of w in ecp_mul_comb(). 00795 * 00796 * Cost: 1N(t) := 1I + (6t - 3)M + 1S 00797 */ 00798 static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp, 00799 mbedtls_ecp_point *T[], size_t t_len ) 00800 { 00801 int ret; 00802 size_t i; 00803 mbedtls_mpi *c, u, Zi, ZZi; 00804 00805 if( t_len < 2 ) 00806 return( ecp_normalize_jac( grp, *T ) ); 00807 00808 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) 00809 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 00810 { 00811 return mbedtls_internal_ecp_normalize_jac_many(grp, T, t_len); 00812 } 00813 #endif 00814 00815 if( ( c = mbedtls_calloc( t_len, sizeof( mbedtls_mpi ) ) ) == NULL ) 00816 return( MBEDTLS_ERR_ECP_ALLOC_FAILED ); 00817 00818 mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi ); 00819 00820 /* 00821 * c[i] = Z_0 * ... * Z_i 00822 */ 00823 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) ); 00824 for( i = 1; i < t_len; i++ ) 00825 { 00826 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) ); 00827 MOD_MUL( c[i] ); 00828 } 00829 00830 /* 00831 * u = 1 / (Z_0 * ... * Z_n) mod P 00832 */ 00833 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[t_len-1], &grp->P ) ); 00834 00835 for( i = t_len - 1; ; i-- ) 00836 { 00837 /* 00838 * Zi = 1 / Z_i mod p 00839 * u = 1 / (Z_0 * ... * Z_i) mod P 00840 */ 00841 if( i == 0 ) { 00842 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) ); 00843 } 00844 else 00845 { 00846 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi ); 00847 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u ); 00848 } 00849 00850 /* 00851 * proceed as in normalize() 00852 */ 00853 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); 00854 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X ); 00855 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y ); 00856 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y ); 00857 00858 /* 00859 * Post-precessing: reclaim some memory by shrinking coordinates 00860 * - not storing Z (always 1) 00861 * - shrinking other coordinates, but still keeping the same number of 00862 * limbs as P, as otherwise it will too likely be regrown too fast. 00863 */ 00864 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P .n ) ); 00865 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P .n ) ); 00866 mbedtls_mpi_free( &T[i]->Z ); 00867 00868 if( i == 0 ) 00869 break; 00870 } 00871 00872 cleanup: 00873 00874 mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi ); 00875 for( i = 0; i < t_len; i++ ) 00876 mbedtls_mpi_free( &c[i] ); 00877 mbedtls_free( c ); 00878 00879 return( ret ); 00880 } 00881 00882 /* 00883 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak. 00884 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid 00885 */ 00886 static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp, 00887 mbedtls_ecp_point *Q, 00888 unsigned char inv ) 00889 { 00890 int ret; 00891 unsigned char nonzero; 00892 mbedtls_mpi mQY; 00893 00894 mbedtls_mpi_init( &mQY ); 00895 00896 /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */ 00897 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P , &Q->Y ) ); 00898 nonzero = mbedtls_mpi_cmp_int( &Q->Y , 0 ) != 0; 00899 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y , &mQY, inv & nonzero ) ); 00900 00901 cleanup: 00902 mbedtls_mpi_free( &mQY ); 00903 00904 return( ret ); 00905 } 00906 00907 /* 00908 * Point doubling R = 2 P, Jacobian coordinates 00909 * 00910 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 . 00911 * 00912 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR 00913 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring. 00914 * 00915 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }. 00916 * 00917 * Cost: 1D := 3M + 4S (A == 0) 00918 * 4M + 4S (A == -3) 00919 * 3M + 6S + 1a otherwise 00920 */ 00921 static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 00922 const mbedtls_ecp_point *P ) 00923 { 00924 int ret; 00925 mbedtls_mpi M, S, T, U; 00926 00927 #if defined(MBEDTLS_SELF_TEST) 00928 dbl_count++; 00929 #endif 00930 00931 #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) 00932 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 00933 { 00934 return mbedtls_internal_ecp_double_jac( grp, R, P ); 00935 } 00936 #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */ 00937 00938 mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U ); 00939 00940 /* Special case for A = -3 */ 00941 if( grp->A .p == NULL ) 00942 { 00943 /* M = 3(X + Z^2)(X - Z^2) */ 00944 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z , &P->Z ) ); MOD_MUL( S ); 00945 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T, &P->X , &S ) ); MOD_ADD( T ); 00946 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U, &P->X , &S ) ); MOD_SUB( U ); 00947 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &U ) ); MOD_MUL( S ); 00948 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); 00949 } 00950 else 00951 { 00952 /* M = 3.X^2 */ 00953 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X , &P->X ) ); MOD_MUL( S ); 00954 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); 00955 00956 /* Optimize away for "koblitz" curves with A = 0 */ 00957 if( mbedtls_mpi_cmp_int( &grp->A , 0 ) != 0 ) 00958 { 00959 /* M += A.Z^4 */ 00960 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z , &P->Z ) ); MOD_MUL( S ); 00961 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &S, &S ) ); MOD_MUL( T ); 00962 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &grp->A ) ); MOD_MUL( S ); 00963 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M, &M, &S ) ); MOD_ADD( M ); 00964 } 00965 } 00966 00967 /* S = 4.X.Y^2 */ 00968 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &P->Y , &P->Y ) ); MOD_MUL( T ); 00969 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T, 1 ) ); MOD_ADD( T ); 00970 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X , &T ) ); MOD_MUL( S ); 00971 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S, 1 ) ); MOD_ADD( S ); 00972 00973 /* U = 8.Y^4 */ 00974 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &T, &T ) ); MOD_MUL( U ); 00975 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); 00976 00977 /* T = M^2 - 2.S */ 00978 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &M, &M ) ); MOD_MUL( T ); 00979 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); 00980 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); 00981 00982 /* S = M(S - T) - U */ 00983 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &T ) ); MOD_SUB( S ); 00984 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &S, &M ) ); MOD_MUL( S ); 00985 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &U ) ); MOD_SUB( S ); 00986 00987 /* U = 2.Y.Z */ 00988 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &P->Y , &P->Z ) ); MOD_MUL( U ); 00989 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); 00990 00991 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X , &T ) ); 00992 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y , &S ) ); 00993 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z , &U ) ); 00994 00995 cleanup: 00996 mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U ); 00997 00998 return( ret ); 00999 } 01000 01001 /* 01002 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22) 01003 * 01004 * The coordinates of Q must be normalized (= affine), 01005 * but those of P don't need to. R is not normalized. 01006 * 01007 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q. 01008 * None of these cases can happen as intermediate step in ecp_mul_comb(): 01009 * - at each step, P, Q and R are multiples of the base point, the factor 01010 * being less than its order, so none of them is zero; 01011 * - Q is an odd multiple of the base point, P an even multiple, 01012 * due to the choice of precomputed points in the modified comb method. 01013 * So branches for these cases do not leak secret information. 01014 * 01015 * We accept Q->Z being unset (saving memory in tables) as meaning 1. 01016 * 01017 * Cost: 1A := 8M + 3S 01018 */ 01019 static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 01020 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q ) 01021 { 01022 int ret; 01023 mbedtls_mpi T1, T2, T3, T4, X, Y, Z; 01024 01025 #if defined(MBEDTLS_SELF_TEST) 01026 add_count++; 01027 #endif 01028 01029 #if defined(MBEDTLS_ECP_ADD_MIXED_ALT) 01030 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 01031 { 01032 return mbedtls_internal_ecp_add_mixed( grp, R, P, Q ); 01033 } 01034 #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */ 01035 01036 /* 01037 * Trivial cases: P == 0 or Q == 0 (case 1) 01038 */ 01039 if( mbedtls_mpi_cmp_int( &P->Z , 0 ) == 0 ) 01040 return( mbedtls_ecp_copy( R, Q ) ); 01041 01042 if( Q->Z .p != NULL && mbedtls_mpi_cmp_int( &Q->Z , 0 ) == 0 ) 01043 return( mbedtls_ecp_copy( R, P ) ); 01044 01045 /* 01046 * Make sure Q coordinates are normalized 01047 */ 01048 if( Q->Z .p != NULL && mbedtls_mpi_cmp_int( &Q->Z , 1 ) != 0 ) 01049 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 01050 01051 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 ); 01052 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z ); 01053 01054 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &P->Z , &P->Z ) ); MOD_MUL( T1 ); 01055 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 ); 01056 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 ); 01057 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 ); 01058 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 ); 01059 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 ); 01060 01061 /* Special cases (2) and (3) */ 01062 if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 ) 01063 { 01064 if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 ) 01065 { 01066 ret = ecp_double_jac( grp, R, P ); 01067 goto cleanup; 01068 } 01069 else 01070 { 01071 ret = mbedtls_ecp_set_zero( R ); 01072 goto cleanup; 01073 } 01074 } 01075 01076 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z, &P->Z , &T1 ) ); MOD_MUL( Z ); 01077 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 ); 01078 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 ); 01079 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 ); 01080 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 ); 01081 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X ); 01082 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X ); 01083 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X ); 01084 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 ); 01085 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 ); 01086 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 ); 01087 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y ); 01088 01089 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X , &X ) ); 01090 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y , &Y ) ); 01091 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z , &Z ) ); 01092 01093 cleanup: 01094 01095 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 ); 01096 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z ); 01097 01098 return( ret ); 01099 } 01100 01101 /* 01102 * Randomize jacobian coordinates: 01103 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l 01104 * This is sort of the reverse operation of ecp_normalize_jac(). 01105 * 01106 * This countermeasure was first suggested in [2]. 01107 */ 01108 static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, 01109 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 01110 { 01111 int ret; 01112 mbedtls_mpi l, ll; 01113 size_t p_size; 01114 int count = 0; 01115 01116 #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) 01117 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 01118 { 01119 return mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng ); 01120 } 01121 #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */ 01122 01123 p_size = ( grp->pbits + 7 ) / 8; 01124 mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll ); 01125 01126 /* Generate l such that 1 < l < p */ 01127 do 01128 { 01129 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) ); 01130 01131 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) 01132 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) ); 01133 01134 if( count++ > 10 ) 01135 return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); 01136 } 01137 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ); 01138 01139 /* Z = l * Z */ 01140 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z , &pt->Z , &l ) ); MOD_MUL( pt->Z ); 01141 01142 /* X = l^2 * X */ 01143 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll ); 01144 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X , &pt->X , &ll ) ); MOD_MUL( pt->X ); 01145 01146 /* Y = l^3 * Y */ 01147 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll ); 01148 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y , &pt->Y , &ll ) ); MOD_MUL( pt->Y ); 01149 01150 cleanup: 01151 mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll ); 01152 01153 return( ret ); 01154 } 01155 01156 /* 01157 * Check and define parameters used by the comb method (see below for details) 01158 */ 01159 #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7 01160 #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds" 01161 #endif 01162 01163 /* d = ceil( n / w ) */ 01164 #define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2 01165 01166 /* number of precomputed points */ 01167 #define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) ) 01168 01169 /* 01170 * Compute the representation of m that will be used with our comb method. 01171 * 01172 * The basic comb method is described in GECC 3.44 for example. We use a 01173 * modified version that provides resistance to SPA by avoiding zero 01174 * digits in the representation as in [3]. We modify the method further by 01175 * requiring that all K_i be odd, which has the small cost that our 01176 * representation uses one more K_i, due to carries. 01177 * 01178 * Also, for the sake of compactness, only the seven low-order bits of x[i] 01179 * are used to represent K_i, and the msb of x[i] encodes the the sign (s_i in 01180 * the paper): it is set if and only if if s_i == -1; 01181 * 01182 * Calling conventions: 01183 * - x is an array of size d + 1 01184 * - w is the size, ie number of teeth, of the comb, and must be between 01185 * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE) 01186 * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d 01187 * (the result will be incorrect if these assumptions are not satisfied) 01188 */ 01189 static void ecp_comb_fixed( unsigned char x[], size_t d, 01190 unsigned char w, const mbedtls_mpi *m ) 01191 { 01192 size_t i, j; 01193 unsigned char c, cc, adjust; 01194 01195 memset( x, 0, d+1 ); 01196 01197 /* First get the classical comb values (except for x_d = 0) */ 01198 for( i = 0; i < d; i++ ) 01199 for( j = 0; j < w; j++ ) 01200 x[i] |= mbedtls_mpi_get_bit( m, i + d * j ) << j; 01201 01202 /* Now make sure x_1 .. x_d are odd */ 01203 c = 0; 01204 for( i = 1; i <= d; i++ ) 01205 { 01206 /* Add carry and update it */ 01207 cc = x[i] & c; 01208 x[i] = x[i] ^ c; 01209 c = cc; 01210 01211 /* Adjust if needed, avoiding branches */ 01212 adjust = 1 - ( x[i] & 0x01 ); 01213 c |= x[i] & ( x[i-1] * adjust ); 01214 x[i] = x[i] ^ ( x[i-1] * adjust ); 01215 x[i-1] |= adjust << 7; 01216 } 01217 } 01218 01219 /* 01220 * Precompute points for the comb method 01221 * 01222 * If i = i_{w-1} ... i_1 is the binary representation of i, then 01223 * T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P 01224 * 01225 * T must be able to hold 2^{w - 1} elements 01226 * 01227 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1) 01228 */ 01229 static int ecp_precompute_comb( const mbedtls_ecp_group *grp, 01230 mbedtls_ecp_point T[], const mbedtls_ecp_point *P, 01231 unsigned char w, size_t d ) 01232 { 01233 int ret; 01234 unsigned char i, k; 01235 size_t j; 01236 mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1]; 01237 01238 /* 01239 * Set T[0] = P and 01240 * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value) 01241 */ 01242 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) ); 01243 01244 k = 0; 01245 for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 ) 01246 { 01247 cur = T + i; 01248 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) ); 01249 for( j = 0; j < d; j++ ) 01250 MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) ); 01251 01252 TT[k++] = cur; 01253 } 01254 01255 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) ); 01256 01257 /* 01258 * Compute the remaining ones using the minimal number of additions 01259 * Be careful to update T[2^l] only after using it! 01260 */ 01261 k = 0; 01262 for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 ) 01263 { 01264 j = i; 01265 while( j-- ) 01266 { 01267 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) ); 01268 TT[k++] = &T[i + j]; 01269 } 01270 } 01271 01272 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) ); 01273 01274 cleanup: 01275 01276 return( ret ); 01277 } 01278 01279 /* 01280 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ] 01281 */ 01282 static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 01283 const mbedtls_ecp_point T[], unsigned char t_len, 01284 unsigned char i ) 01285 { 01286 int ret; 01287 unsigned char ii, j; 01288 01289 /* Ignore the "sign" bit and scale down */ 01290 ii = ( i & 0x7Fu ) >> 1; 01291 01292 /* Read the whole table to thwart cache-based timing attacks */ 01293 for( j = 0; j < t_len; j++ ) 01294 { 01295 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X , &T[j].X , j == ii ) ); 01296 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y , &T[j].Y , j == ii ) ); 01297 } 01298 01299 /* Safely invert result if i is "negative" */ 01300 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) ); 01301 01302 cleanup: 01303 return( ret ); 01304 } 01305 01306 /* 01307 * Core multiplication algorithm for the (modified) comb method. 01308 * This part is actually common with the basic comb method (GECC 3.44) 01309 * 01310 * Cost: d A + d D + 1 R 01311 */ 01312 static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 01313 const mbedtls_ecp_point T[], unsigned char t_len, 01314 const unsigned char x[], size_t d, 01315 int (*f_rng)(void *, unsigned char *, size_t), 01316 void *p_rng ) 01317 { 01318 int ret; 01319 mbedtls_ecp_point Txi; 01320 size_t i; 01321 01322 mbedtls_ecp_point_init( &Txi ); 01323 01324 /* Start with a non-zero point and randomize its coordinates */ 01325 i = d; 01326 MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) ); 01327 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z , 1 ) ); 01328 if( f_rng != 0 ) 01329 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) ); 01330 01331 while( i-- != 0 ) 01332 { 01333 MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) ); 01334 MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) ); 01335 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) ); 01336 } 01337 01338 cleanup: 01339 01340 mbedtls_ecp_point_free( &Txi ); 01341 01342 return( ret ); 01343 } 01344 01345 /* 01346 * Multiplication using the comb method, 01347 * for curves in short Weierstrass form 01348 */ 01349 static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 01350 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 01351 int (*f_rng)(void *, unsigned char *, size_t), 01352 void *p_rng ) 01353 { 01354 int ret; 01355 unsigned char w, m_is_odd, p_eq_g, pre_len, i; 01356 size_t d; 01357 unsigned char k[COMB_MAX_D + 1]; 01358 mbedtls_ecp_point *T; 01359 mbedtls_mpi M, mm; 01360 01361 mbedtls_mpi_init( &M ); 01362 mbedtls_mpi_init( &mm ); 01363 01364 /* we need N to be odd to trnaform m in an odd number, check now */ 01365 if( mbedtls_mpi_get_bit( &grp->N , 0 ) != 1 ) 01366 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 01367 01368 /* 01369 * Minimize the number of multiplications, that is minimize 01370 * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w ) 01371 * (see costs of the various parts, with 1S = 1M) 01372 */ 01373 w = grp->nbits >= 384 ? 5 : 4; 01374 01375 /* 01376 * If P == G, pre-compute a bit more, since this may be re-used later. 01377 * Just adding one avoids upping the cost of the first mul too much, 01378 * and the memory cost too. 01379 */ 01380 #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1 01381 p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y , &grp->G .Y ) == 0 && 01382 mbedtls_mpi_cmp_mpi( &P->X , &grp->G .X ) == 0 ); 01383 if( p_eq_g ) 01384 w++; 01385 #else 01386 p_eq_g = 0; 01387 #endif 01388 01389 /* 01390 * Make sure w is within bounds. 01391 * (The last test is useful only for very small curves in the test suite.) 01392 */ 01393 if( w > MBEDTLS_ECP_WINDOW_SIZE ) 01394 w = MBEDTLS_ECP_WINDOW_SIZE; 01395 if( w >= grp->nbits ) 01396 w = 2; 01397 01398 /* Other sizes that depend on w */ 01399 pre_len = 1U << ( w - 1 ); 01400 d = ( grp->nbits + w - 1 ) / w; 01401 01402 /* 01403 * Prepare precomputed points: if P == G we want to 01404 * use grp->T if already initialized, or initialize it. 01405 */ 01406 T = p_eq_g ? grp->T : NULL; 01407 01408 if( T == NULL ) 01409 { 01410 T = mbedtls_calloc( pre_len, sizeof( mbedtls_ecp_point ) ); 01411 if( T == NULL ) 01412 { 01413 ret = MBEDTLS_ERR_ECP_ALLOC_FAILED; 01414 goto cleanup; 01415 } 01416 01417 MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) ); 01418 01419 if( p_eq_g ) 01420 { 01421 grp->T = T; 01422 grp->T_size = pre_len; 01423 } 01424 } 01425 01426 /* 01427 * Make sure M is odd (M = m or M = N - m, since N is odd) 01428 * using the fact that m * P = - (N - m) * P 01429 */ 01430 m_is_odd = ( mbedtls_mpi_get_bit( m, 0 ) == 1 ); 01431 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) ); 01432 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N , m ) ); 01433 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, ! m_is_odd ) ); 01434 01435 /* 01436 * Go for comb multiplication, R = M * P 01437 */ 01438 ecp_comb_fixed( k, d, w, &M ); 01439 MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) ); 01440 01441 /* 01442 * Now get m * P from M * P and normalize it 01443 */ 01444 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) ); 01445 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) ); 01446 01447 cleanup: 01448 01449 /* There are two cases where T is not stored in grp: 01450 * - P != G 01451 * - An intermediate operation failed before setting grp->T 01452 * In either case, T must be freed. 01453 */ 01454 if( T != NULL && T != grp->T ) 01455 { 01456 for( i = 0; i < pre_len; i++ ) 01457 mbedtls_ecp_point_free( &T[i] ); 01458 mbedtls_free( T ); 01459 } 01460 01461 mbedtls_mpi_free( &M ); 01462 mbedtls_mpi_free( &mm ); 01463 01464 if( ret != 0 ) 01465 mbedtls_ecp_point_free( R ); 01466 01467 return( ret ); 01468 } 01469 01470 #endif /* ECP_SHORTWEIERSTRASS */ 01471 01472 #if defined(ECP_MONTGOMERY) 01473 /* 01474 * For Montgomery curves, we do all the internal arithmetic in projective 01475 * coordinates. Import/export of points uses only the x coordinates, which is 01476 * internaly represented as X / Z. 01477 * 01478 * For scalar multiplication, we'll use a Montgomery ladder. 01479 */ 01480 01481 /* 01482 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1 01483 * Cost: 1M + 1I 01484 */ 01485 static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P ) 01486 { 01487 int ret; 01488 01489 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) 01490 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 01491 { 01492 return mbedtls_internal_ecp_normalize_mxz( grp, P ); 01493 } 01494 #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */ 01495 01496 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z , &P->Z , &grp->P ) ); 01497 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X , &P->X , &P->Z ) ); MOD_MUL( P->X ); 01498 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z , 1 ) ); 01499 01500 cleanup: 01501 return( ret ); 01502 } 01503 01504 /* 01505 * Randomize projective x/z coordinates: 01506 * (X, Z) -> (l X, l Z) for random l 01507 * This is sort of the reverse operation of ecp_normalize_mxz(). 01508 * 01509 * This countermeasure was first suggested in [2]. 01510 * Cost: 2M 01511 */ 01512 static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P, 01513 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 01514 { 01515 int ret; 01516 mbedtls_mpi l; 01517 size_t p_size; 01518 int count = 0; 01519 01520 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) 01521 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 01522 { 01523 return mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng ); 01524 } 01525 #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */ 01526 01527 p_size = ( grp->pbits + 7 ) / 8; 01528 mbedtls_mpi_init( &l ); 01529 01530 /* Generate l such that 1 < l < p */ 01531 do 01532 { 01533 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) ); 01534 01535 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) 01536 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) ); 01537 01538 if( count++ > 10 ) 01539 return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); 01540 } 01541 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ); 01542 01543 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X , &P->X , &l ) ); MOD_MUL( P->X ); 01544 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z , &P->Z , &l ) ); MOD_MUL( P->Z ); 01545 01546 cleanup: 01547 mbedtls_mpi_free( &l ); 01548 01549 return( ret ); 01550 } 01551 01552 /* 01553 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q), 01554 * for Montgomery curves in x/z coordinates. 01555 * 01556 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3 01557 * with 01558 * d = X1 01559 * P = (X2, Z2) 01560 * Q = (X3, Z3) 01561 * R = (X4, Z4) 01562 * S = (X5, Z5) 01563 * and eliminating temporary variables tO, ..., t4. 01564 * 01565 * Cost: 5M + 4S 01566 */ 01567 static int ecp_double_add_mxz( const mbedtls_ecp_group *grp, 01568 mbedtls_ecp_point *R, mbedtls_ecp_point *S, 01569 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q, 01570 const mbedtls_mpi *d ) 01571 { 01572 int ret; 01573 mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB; 01574 01575 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) 01576 if ( mbedtls_internal_ecp_grp_capable( grp ) ) 01577 { 01578 return mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d ); 01579 } 01580 #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */ 01581 01582 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B ); 01583 mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C ); 01584 mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB ); 01585 01586 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A, &P->X , &P->Z ) ); MOD_ADD( A ); 01587 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA ); 01588 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B, &P->X , &P->Z ) ); MOD_SUB( B ); 01589 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB ); 01590 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E ); 01591 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C, &Q->X , &Q->Z ) ); MOD_ADD( C ); 01592 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D, &Q->X , &Q->Z ) ); MOD_SUB( D ); 01593 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA ); 01594 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB ); 01595 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X , &DA, &CB ) ); MOD_MUL( S->X ); 01596 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X , &S->X , &S->X ) ); MOD_MUL( S->X ); 01597 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z , &DA, &CB ) ); MOD_SUB( S->Z ); 01598 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z , &S->Z , &S->Z ) ); MOD_MUL( S->Z ); 01599 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z , d, &S->Z ) ); MOD_MUL( S->Z ); 01600 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X , &AA, &BB ) ); MOD_MUL( R->X ); 01601 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z , &grp->A , &E ) ); MOD_MUL( R->Z ); 01602 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z , &BB, &R->Z ) ); MOD_ADD( R->Z ); 01603 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z , &E, &R->Z ) ); MOD_MUL( R->Z ); 01604 01605 cleanup: 01606 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B ); 01607 mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C ); 01608 mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB ); 01609 01610 return( ret ); 01611 } 01612 01613 /* 01614 * Multiplication with Montgomery ladder in x/z coordinates, 01615 * for curves in Montgomery form 01616 */ 01617 static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 01618 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 01619 int (*f_rng)(void *, unsigned char *, size_t), 01620 void *p_rng ) 01621 { 01622 int ret; 01623 size_t i; 01624 unsigned char b; 01625 mbedtls_ecp_point RP; 01626 mbedtls_mpi PX; 01627 01628 mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX ); 01629 01630 /* Save PX and read from P before writing to R, in case P == R */ 01631 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) ); 01632 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) ); 01633 01634 /* Set R to zero in modified x/z coordinates */ 01635 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X , 1 ) ); 01636 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z , 0 ) ); 01637 mbedtls_mpi_free( &R->Y ); 01638 01639 /* RP.X might be sligtly larger than P, so reduce it */ 01640 MOD_ADD( RP.X ); 01641 01642 /* Randomize coordinates of the starting point */ 01643 if( f_rng != NULL ) 01644 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) ); 01645 01646 /* Loop invariant: R = result so far, RP = R + P */ 01647 i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */ 01648 while( i-- > 0 ) 01649 { 01650 b = mbedtls_mpi_get_bit( m, i ); 01651 /* 01652 * if (b) R = 2R + P else R = 2R, 01653 * which is: 01654 * if (b) double_add( RP, R, RP, R ) 01655 * else double_add( R, RP, R, RP ) 01656 * but using safe conditional swaps to avoid leaks 01657 */ 01658 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X , &RP.X , b ) ); 01659 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z , &RP.Z , b ) ); 01660 MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) ); 01661 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X , &RP.X , b ) ); 01662 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z , &RP.Z , b ) ); 01663 } 01664 01665 MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) ); 01666 01667 cleanup: 01668 mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX ); 01669 01670 return( ret ); 01671 } 01672 01673 #endif /* ECP_MONTGOMERY */ 01674 01675 /* 01676 * Multiplication R = m * P 01677 */ 01678 int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 01679 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 01680 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 01681 { 01682 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 01683 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 01684 char is_grp_capable = 0; 01685 #endif 01686 01687 /* Common sanity checks */ 01688 if( mbedtls_mpi_cmp_int( &P->Z , 1 ) != 0 ) 01689 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 01690 01691 if( ( ret = mbedtls_ecp_check_privkey( grp, m ) ) != 0 || 01692 ( ret = mbedtls_ecp_check_pubkey( grp, P ) ) != 0 ) 01693 return( ret ); 01694 01695 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 01696 if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) 01697 { 01698 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); 01699 } 01700 01701 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 01702 #if defined(ECP_MONTGOMERY) 01703 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 01704 ret = ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ); 01705 01706 #endif 01707 #if defined(ECP_SHORTWEIERSTRASS) 01708 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 01709 ret = ecp_mul_comb( grp, R, m, P, f_rng, p_rng ); 01710 01711 #endif 01712 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 01713 cleanup: 01714 01715 if ( is_grp_capable ) 01716 { 01717 mbedtls_internal_ecp_free( grp ); 01718 } 01719 01720 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 01721 return( ret ); 01722 } 01723 01724 #if defined(ECP_SHORTWEIERSTRASS) 01725 /* 01726 * Check that an affine point is valid as a public key, 01727 * short weierstrass curves (SEC1 3.2.3.1) 01728 */ 01729 static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 01730 { 01731 int ret; 01732 mbedtls_mpi YY, RHS; 01733 01734 /* pt coordinates must be normalized for our checks */ 01735 if( mbedtls_mpi_cmp_int( &pt->X , 0 ) < 0 || 01736 mbedtls_mpi_cmp_int( &pt->Y , 0 ) < 0 || 01737 mbedtls_mpi_cmp_mpi( &pt->X , &grp->P ) >= 0 || 01738 mbedtls_mpi_cmp_mpi( &pt->Y , &grp->P ) >= 0 ) 01739 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 01740 01741 mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS ); 01742 01743 /* 01744 * YY = Y^2 01745 * RHS = X (X^2 + A) + B = X^3 + A X + B 01746 */ 01747 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY, &pt->Y , &pt->Y ) ); MOD_MUL( YY ); 01748 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X , &pt->X ) ); MOD_MUL( RHS ); 01749 01750 /* Special case for A = -3 */ 01751 if( grp->A .p == NULL ) 01752 { 01753 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS ); 01754 } 01755 else 01756 { 01757 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS ); 01758 } 01759 01760 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS ); 01761 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS ); 01762 01763 if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 ) 01764 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 01765 01766 cleanup: 01767 01768 mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS ); 01769 01770 return( ret ); 01771 } 01772 #endif /* ECP_SHORTWEIERSTRASS */ 01773 01774 /* 01775 * R = m * P with shortcuts for m == 1 and m == -1 01776 * NOT constant-time - ONLY for short Weierstrass! 01777 */ 01778 static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp, 01779 mbedtls_ecp_point *R, 01780 const mbedtls_mpi *m, 01781 const mbedtls_ecp_point *P ) 01782 { 01783 int ret; 01784 01785 if( mbedtls_mpi_cmp_int( m, 1 ) == 0 ) 01786 { 01787 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); 01788 } 01789 else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 ) 01790 { 01791 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) ); 01792 if( mbedtls_mpi_cmp_int( &R->Y , 0 ) != 0 ) 01793 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y , &grp->P , &R->Y ) ); 01794 } 01795 else 01796 { 01797 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, R, m, P, NULL, NULL ) ); 01798 } 01799 01800 cleanup: 01801 return( ret ); 01802 } 01803 01804 /* 01805 * Linear combination 01806 * NOT constant-time 01807 */ 01808 int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 01809 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 01810 const mbedtls_mpi *n, const mbedtls_ecp_point *Q ) 01811 { 01812 int ret; 01813 mbedtls_ecp_point mP; 01814 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 01815 char is_grp_capable = 0; 01816 #endif 01817 01818 if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS ) 01819 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE ); 01820 01821 mbedtls_ecp_point_init( &mP ); 01822 01823 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, &mP, m, P ) ); 01824 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, R, n, Q ) ); 01825 01826 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 01827 if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) 01828 { 01829 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) ); 01830 } 01831 01832 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 01833 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, &mP, R ) ); 01834 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) ); 01835 01836 cleanup: 01837 01838 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 01839 if ( is_grp_capable ) 01840 { 01841 mbedtls_internal_ecp_free( grp ); 01842 } 01843 01844 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 01845 mbedtls_ecp_point_free( &mP ); 01846 01847 return( ret ); 01848 } 01849 01850 01851 #if defined(ECP_MONTGOMERY) 01852 /* 01853 * Check validity of a public key for Montgomery curves with x-only schemes 01854 */ 01855 static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 01856 { 01857 /* [Curve25519 p. 5] Just check X is the correct number of bytes */ 01858 /* Allow any public value, if it's too big then we'll just reduce it mod p 01859 * (RFC 7748 sec. 5 para. 3). */ 01860 if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 ) 01861 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 01862 01863 return( 0 ); 01864 } 01865 #endif /* ECP_MONTGOMERY */ 01866 01867 /* 01868 * Check that a point is valid as a public key 01869 */ 01870 int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt ) 01871 { 01872 /* Must use affine coordinates */ 01873 if( mbedtls_mpi_cmp_int( &pt->Z , 1 ) != 0 ) 01874 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 01875 01876 #if defined(ECP_MONTGOMERY) 01877 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 01878 return( ecp_check_pubkey_mx( grp, pt ) ); 01879 #endif 01880 #if defined(ECP_SHORTWEIERSTRASS) 01881 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 01882 return( ecp_check_pubkey_sw( grp, pt ) ); 01883 #endif 01884 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 01885 } 01886 01887 /* 01888 * Check that an mbedtls_mpi is valid as a private key 01889 */ 01890 int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, const mbedtls_mpi *d ) 01891 { 01892 #if defined(ECP_MONTGOMERY) 01893 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 01894 { 01895 /* see RFC 7748 sec. 5 para. 5 */ 01896 if( mbedtls_mpi_get_bit( d, 0 ) != 0 || 01897 mbedtls_mpi_get_bit( d, 1 ) != 0 || 01898 mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */ 01899 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 01900 01901 /* see [Curve25519] page 5 */ 01902 if( grp->nbits == 254 && mbedtls_mpi_get_bit( d, 2 ) != 0 ) 01903 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 01904 01905 return( 0 ); 01906 } 01907 #endif /* ECP_MONTGOMERY */ 01908 #if defined(ECP_SHORTWEIERSTRASS) 01909 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 01910 { 01911 /* see SEC1 3.2 */ 01912 if( mbedtls_mpi_cmp_int( d, 1 ) < 0 || 01913 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 ) 01914 return( MBEDTLS_ERR_ECP_INVALID_KEY ); 01915 else 01916 return( 0 ); 01917 } 01918 #endif /* ECP_SHORTWEIERSTRASS */ 01919 01920 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 01921 } 01922 01923 /* 01924 * Generate a keypair with configurable base point 01925 */ 01926 int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp, 01927 const mbedtls_ecp_point *G, 01928 mbedtls_mpi *d, mbedtls_ecp_point *Q, 01929 int (*f_rng)(void *, unsigned char *, size_t), 01930 void *p_rng ) 01931 { 01932 int ret; 01933 size_t n_size = ( grp->nbits + 7 ) / 8; 01934 01935 #if defined(ECP_MONTGOMERY) 01936 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY ) 01937 { 01938 /* [M225] page 5 */ 01939 size_t b; 01940 01941 do { 01942 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) ); 01943 } while( mbedtls_mpi_bitlen( d ) == 0); 01944 01945 /* Make sure the most significant bit is nbits */ 01946 b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */ 01947 if( b > grp->nbits ) 01948 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) ); 01949 else 01950 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits , 1 ) ); 01951 01952 /* Make sure the last two bits are unset for Curve448, three bits for 01953 Curve25519 */ 01954 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) ); 01955 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) ); 01956 if( grp->nbits == 254 ) 01957 { 01958 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) ); 01959 } 01960 } 01961 else 01962 #endif /* ECP_MONTGOMERY */ 01963 #if defined(ECP_SHORTWEIERSTRASS) 01964 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS ) 01965 { 01966 /* SEC1 3.2.1: Generate d such that 1 <= n < N */ 01967 int count = 0; 01968 01969 /* 01970 * Match the procedure given in RFC 6979 (deterministic ECDSA): 01971 * - use the same byte ordering; 01972 * - keep the leftmost nbits bits of the generated octet string; 01973 * - try until result is in the desired range. 01974 * This also avoids any biais, which is especially important for ECDSA. 01975 */ 01976 do 01977 { 01978 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) ); 01979 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) ); 01980 01981 /* 01982 * Each try has at worst a probability 1/2 of failing (the msb has 01983 * a probability 1/2 of being 0, and then the result will be < N), 01984 * so after 30 tries failure probability is a most 2**(-30). 01985 * 01986 * For most curves, 1 try is enough with overwhelming probability, 01987 * since N starts with a lot of 1s in binary, but some curves 01988 * such as secp224k1 are actually very close to the worst case. 01989 */ 01990 if( ++count > 30 ) 01991 return( MBEDTLS_ERR_ECP_RANDOM_FAILED ); 01992 } 01993 while( mbedtls_mpi_cmp_int( d, 1 ) < 0 || 01994 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 ); 01995 } 01996 else 01997 #endif /* ECP_SHORTWEIERSTRASS */ 01998 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 01999 02000 cleanup: 02001 if( ret != 0 ) 02002 return( ret ); 02003 02004 return( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) ); 02005 } 02006 02007 /* 02008 * Generate key pair, wrapper for conventional base point 02009 */ 02010 int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp, 02011 mbedtls_mpi *d, mbedtls_ecp_point *Q, 02012 int (*f_rng)(void *, unsigned char *, size_t), 02013 void *p_rng ) 02014 { 02015 return( mbedtls_ecp_gen_keypair_base( grp, &grp->G , d, Q, f_rng, p_rng ) ); 02016 } 02017 02018 /* 02019 * Generate a keypair, prettier wrapper 02020 */ 02021 int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, 02022 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 02023 { 02024 int ret; 02025 02026 if( ( ret = mbedtls_ecp_group_load( &key->grp , grp_id ) ) != 0 ) 02027 return( ret ); 02028 02029 return( mbedtls_ecp_gen_keypair( &key->grp , &key->d , &key->Q , f_rng, p_rng ) ); 02030 } 02031 02032 /* 02033 * Check a public-private key pair 02034 */ 02035 int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv ) 02036 { 02037 int ret; 02038 mbedtls_ecp_point Q; 02039 mbedtls_ecp_group grp; 02040 02041 if( pub->grp .id == MBEDTLS_ECP_DP_NONE || 02042 pub->grp .id != prv->grp .id || 02043 mbedtls_mpi_cmp_mpi( &pub->Q .X , &prv->Q .X ) || 02044 mbedtls_mpi_cmp_mpi( &pub->Q .Y , &prv->Q .Y ) || 02045 mbedtls_mpi_cmp_mpi( &pub->Q .Z , &prv->Q .Z ) ) 02046 { 02047 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA ); 02048 } 02049 02050 mbedtls_ecp_point_init( &Q ); 02051 mbedtls_ecp_group_init( &grp ); 02052 02053 /* mbedtls_ecp_mul() needs a non-const group... */ 02054 mbedtls_ecp_group_copy( &grp, &prv->grp ); 02055 02056 /* Also checks d is valid */ 02057 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d , &prv->grp .G , NULL, NULL ) ); 02058 02059 if( mbedtls_mpi_cmp_mpi( &Q.X , &prv->Q .X ) || 02060 mbedtls_mpi_cmp_mpi( &Q.Y , &prv->Q .Y ) || 02061 mbedtls_mpi_cmp_mpi( &Q.Z , &prv->Q .Z ) ) 02062 { 02063 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 02064 goto cleanup; 02065 } 02066 02067 cleanup: 02068 mbedtls_ecp_point_free( &Q ); 02069 mbedtls_ecp_group_free( &grp ); 02070 02071 return( ret ); 02072 } 02073 02074 #if defined(MBEDTLS_SELF_TEST) 02075 02076 /* 02077 * Checkup routine 02078 */ 02079 int mbedtls_ecp_self_test( int verbose ) 02080 { 02081 int ret; 02082 size_t i; 02083 mbedtls_ecp_group grp; 02084 mbedtls_ecp_point R, P; 02085 mbedtls_mpi m; 02086 unsigned long add_c_prev, dbl_c_prev, mul_c_prev; 02087 /* exponents especially adapted for secp192r1 */ 02088 const char *exponents[] = 02089 { 02090 "000000000000000000000000000000000000000000000001", /* one */ 02091 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */ 02092 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */ 02093 "400000000000000000000000000000000000000000000000", /* one and zeros */ 02094 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */ 02095 "555555555555555555555555555555555555555555555555", /* 101010... */ 02096 }; 02097 02098 mbedtls_ecp_group_init( &grp ); 02099 mbedtls_ecp_point_init( &R ); 02100 mbedtls_ecp_point_init( &P ); 02101 mbedtls_mpi_init( &m ); 02102 02103 /* Use secp192r1 if available, or any available curve */ 02104 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) 02105 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) ); 02106 #else 02107 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) ); 02108 #endif 02109 02110 if( verbose != 0 ) 02111 mbedtls_printf( " ECP test #1 (constant op_count, base point G): " ); 02112 02113 /* Do a dummy multiplication first to trigger precomputation */ 02114 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) ); 02115 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G , NULL, NULL ) ); 02116 02117 add_count = 0; 02118 dbl_count = 0; 02119 mul_count = 0; 02120 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); 02121 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G , NULL, NULL ) ); 02122 02123 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) 02124 { 02125 add_c_prev = add_count; 02126 dbl_c_prev = dbl_count; 02127 mul_c_prev = mul_count; 02128 add_count = 0; 02129 dbl_count = 0; 02130 mul_count = 0; 02131 02132 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); 02133 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G , NULL, NULL ) ); 02134 02135 if( add_count != add_c_prev || 02136 dbl_count != dbl_c_prev || 02137 mul_count != mul_c_prev ) 02138 { 02139 if( verbose != 0 ) 02140 mbedtls_printf( "failed (%u)\n", (unsigned int) i ); 02141 02142 ret = 1; 02143 goto cleanup; 02144 } 02145 } 02146 02147 if( verbose != 0 ) 02148 mbedtls_printf( "passed\n" ); 02149 02150 if( verbose != 0 ) 02151 mbedtls_printf( " ECP test #2 (constant op_count, other point): " ); 02152 /* We computed P = 2G last time, use it */ 02153 02154 add_count = 0; 02155 dbl_count = 0; 02156 mul_count = 0; 02157 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) ); 02158 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); 02159 02160 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) 02161 { 02162 add_c_prev = add_count; 02163 dbl_c_prev = dbl_count; 02164 mul_c_prev = mul_count; 02165 add_count = 0; 02166 dbl_count = 0; 02167 mul_count = 0; 02168 02169 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) ); 02170 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); 02171 02172 if( add_count != add_c_prev || 02173 dbl_count != dbl_c_prev || 02174 mul_count != mul_c_prev ) 02175 { 02176 if( verbose != 0 ) 02177 mbedtls_printf( "failed (%u)\n", (unsigned int) i ); 02178 02179 ret = 1; 02180 goto cleanup; 02181 } 02182 } 02183 02184 if( verbose != 0 ) 02185 mbedtls_printf( "passed\n" ); 02186 02187 cleanup: 02188 02189 if( ret < 0 && verbose != 0 ) 02190 mbedtls_printf( "Unexpected error, return code = %08X\n", ret ); 02191 02192 mbedtls_ecp_group_free( &grp ); 02193 mbedtls_ecp_point_free( &R ); 02194 mbedtls_ecp_point_free( &P ); 02195 mbedtls_mpi_free( &m ); 02196 02197 if( verbose != 0 ) 02198 mbedtls_printf( "\n" ); 02199 02200 return( ret ); 02201 } 02202 02203 #endif /* MBEDTLS_SELF_TEST */ 02204 02205 #endif /* !MBEDTLS_ECP_ALT */ 02206 02207 #endif /* MBEDTLS_ECP_C */
Generated on Tue Jul 12 2022 13:53:06 by
1.7.2