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