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