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