Example program to test AES-GCM functionality. Used for a workshop

Dependencies:   mbed

Embed: (wiki syntax)

« Back to documentation index

Show/hide line numbers ecp.c Source File

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