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