sandbox
/
mbedtls
Important changes to repositories hosted on mbed.com
Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.
To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.
It is also possible to export all your personal repositories from the account settings page.
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