ecp.c

00001 /*
00002  *  Elliptic curves over GF(p): generic functions
00003  *
00004  *  Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
00005  *  SPDX-License-Identifier: Apache-2.0
00006  *
00007  *  Licensed under the Apache License, Version 2.0 (the "License"); you may
00008  *  not use this file except in compliance with the License.
00009  *  You may obtain a copy of the License at
00010  *
00011  *  http://www.apache.org/licenses/LICENSE-2.0
00012  *
00013  *  Unless required by applicable law or agreed to in writing, software
00014  *  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
00015  *  WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00016  *  See the License for the specific language governing permissions and
00017  *  limitations under the License.
00018  *
00019  *  This file is part of mbed TLS (https://tls.mbed.org)
00020  */
00021 
00022 /*
00023  * References:
00024  *
00025  * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
00026  * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
00027  * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
00028  * RFC 4492 for the related TLS structures and constants
00029  * RFC 7748 for the Curve448 and Curve25519 curve definitions
00030  *
00031  * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf
00032  *
00033  * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
00034  *     for elliptic curve cryptosystems. In : Cryptographic Hardware and
00035  *     Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
00036  *     <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
00037  *
00038  * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
00039  *     render ECC resistant against Side Channel Attacks. IACR Cryptology
00040  *     ePrint Archive, 2004, vol. 2004, p. 342.
00041  *     <http://eprint.iacr.org/2004/342.pdf>
00042  */
00043 
00044 #if !defined(MBEDTLS_CONFIG_FILE)
00045 #include "mbedtls/config.h"
00046 #else
00047 #include MBEDTLS_CONFIG_FILE
00048 #endif
00049 
00050 /**
00051  * \brief Function level alternative implementation.
00052  *
00053  * The MBEDTLS_ECP_INTERNAL_ALT macro enables alternative implementations to
00054  * replace certain functions in this module. The alternative implementations are
00055  * typically hardware accelerators and need to activate the hardware before the
00056  * computation starts and deactivate it after it finishes. The
00057  * mbedtls_internal_ecp_init() and mbedtls_internal_ecp_free() functions serve
00058  * this purpose.
00059  *
00060  * To preserve the correct functionality the following conditions must hold:
00061  *
00062  * - The alternative implementation must be activated by
00063  *   mbedtls_internal_ecp_init() before any of the replaceable functions is
00064  *   called.
00065  * - mbedtls_internal_ecp_free() must \b only be called when the alternative
00066  *   implementation is activated.
00067  * - mbedtls_internal_ecp_init() must \b not be called when the alternative
00068  *   implementation is activated.
00069  * - Public functions must not return while the alternative implementation is
00070  *   activated.
00071  * - Replaceable functions are guarded by \c MBEDTLS_ECP_XXX_ALT macros and
00072  *   before calling them an \code if( mbedtls_internal_ecp_grp_capable( grp ) )
00073  *   \endcode ensures that the alternative implementation supports the current
00074  *   group.
00075  */
00076 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
00077 #endif
00078 
00079 #if defined(MBEDTLS_ECP_C)
00080 
00081 #include "mbedtls/ecp.h"
00082 #include "mbedtls/threading.h"
00083 #include "mbedtls/platform_util.h"
00084 
00085 #include <string.h>
00086 
00087 #if !defined(MBEDTLS_ECP_ALT)
00088 
00089 /* Parameter validation macros based on platform_util.h */
00090 #define ECP_VALIDATE_RET( cond )    \
00091     MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_ECP_BAD_INPUT_DATA )
00092 #define ECP_VALIDATE( cond )        \
00093     MBEDTLS_INTERNAL_VALIDATE( cond )
00094 
00095 #if defined(MBEDTLS_PLATFORM_C)
00096 #include "mbedtls/platform.h"
00097 #else
00098 #include <stdlib.h>
00099 #include <stdio.h>
00100 #define mbedtls_printf     printf
00101 #define mbedtls_calloc    calloc
00102 #define mbedtls_free       free
00103 #endif
00104 
00105 #include "mbedtls/ecp_internal.h"
00106 
00107 #if ( defined(__ARMCC_VERSION) || defined(_MSC_VER) ) && \
00108     !defined(inline) && !defined(__cplusplus)
00109 #define inline __inline
00110 #endif
00111 
00112 #if defined(MBEDTLS_SELF_TEST)
00113 /*
00114  * Counts of point addition and doubling, and field multiplications.
00115  * Used to test resistance of point multiplication to simple timing attacks.
00116  */
00117 static unsigned long add_count, dbl_count, mul_count;
00118 #endif
00119 
00120 #if defined(MBEDTLS_ECP_RESTARTABLE)
00121 /*
00122  * Maximum number of "basic operations" to be done in a row.
00123  *
00124  * Default value 0 means that ECC operations will not yield.
00125  * Note that regardless of the value of ecp_max_ops, always at
00126  * least one step is performed before yielding.
00127  *
00128  * Setting ecp_max_ops=1 can be suitable for testing purposes
00129  * as it will interrupt computation at all possible points.
00130  */
00131 static unsigned ecp_max_ops = 0;
00132 
00133 /*
00134  * Set ecp_max_ops
00135  */
00136 void mbedtls_ecp_set_max_ops( unsigned max_ops )
00137 {
00138     ecp_max_ops = max_ops;
00139 }
00140 
00141 /*
00142  * Check if restart is enabled
00143  */
00144 int mbedtls_ecp_restart_is_enabled( void )
00145 {
00146     return( ecp_max_ops != 0 );
00147 }
00148 
00149 /*
00150  * Restart sub-context for ecp_mul_comb()
00151  */
00152 struct mbedtls_ecp_restart_mul
00153 {
00154     mbedtls_ecp_point R;    /* current intermediate result                  */
00155     size_t i;               /* current index in various loops, 0 outside    */
00156     mbedtls_ecp_point *T;   /* table for precomputed points                 */
00157     unsigned char T_size;   /* number of points in table T                  */
00158     enum {                  /* what were we doing last time we returned?    */
00159         ecp_rsm_init = 0,       /* nothing so far, dummy initial state      */
00160         ecp_rsm_pre_dbl,        /* precompute 2^n multiples                 */
00161         ecp_rsm_pre_norm_dbl,   /* normalize precomputed 2^n multiples      */
00162         ecp_rsm_pre_add,        /* precompute remaining points by adding    */
00163         ecp_rsm_pre_norm_add,   /* normalize all precomputed points         */
00164         ecp_rsm_comb_core,      /* ecp_mul_comb_core()                      */
00165         ecp_rsm_final_norm,     /* do the final normalization               */
00166     } state;
00167 };
00168 
00169 /*
00170  * Init restart_mul sub-context
00171  */
00172 static void ecp_restart_rsm_init( mbedtls_ecp_restart_mul_ctx *ctx )
00173 {
00174     mbedtls_ecp_point_init( &ctx->R );
00175     ctx->i = 0;
00176     ctx->T = NULL;
00177     ctx->T_size = 0;
00178     ctx->state = ecp_rsm_init;
00179 }
00180 
00181 /*
00182  * Free the components of a restart_mul sub-context
00183  */
00184 static void ecp_restart_rsm_free( mbedtls_ecp_restart_mul_ctx *ctx )
00185 {
00186     unsigned char i;
00187 
00188     if( ctx == NULL )
00189         return;
00190 
00191     mbedtls_ecp_point_free( &ctx->R );
00192 
00193     if( ctx->T != NULL )
00194     {
00195         for( i = 0; i < ctx->T_size; i++ )
00196             mbedtls_ecp_point_free( ctx->T + i );
00197         mbedtls_free( ctx->T );
00198     }
00199 
00200     ecp_restart_rsm_init( ctx );
00201 }
00202 
00203 /*
00204  * Restart context for ecp_muladd()
00205  */
00206 struct mbedtls_ecp_restart_muladd
00207 {
00208     mbedtls_ecp_point mP;       /* mP value                             */
00209     mbedtls_ecp_point R;        /* R intermediate result                */
00210     enum {                      /* what should we do next?              */
00211         ecp_rsma_mul1 = 0,      /* first multiplication                 */
00212         ecp_rsma_mul2,          /* second multiplication                */
00213         ecp_rsma_add,           /* addition                             */
00214         ecp_rsma_norm,          /* normalization                        */
00215     } state;
00216 };
00217 
00218 /*
00219  * Init restart_muladd sub-context
00220  */
00221 static void ecp_restart_ma_init( mbedtls_ecp_restart_muladd_ctx *ctx )
00222 {
00223     mbedtls_ecp_point_init( &ctx->mP );
00224     mbedtls_ecp_point_init( &ctx->R );
00225     ctx->state = ecp_rsma_mul1;
00226 }
00227 
00228 /*
00229  * Free the components of a restart_muladd sub-context
00230  */
00231 static void ecp_restart_ma_free( mbedtls_ecp_restart_muladd_ctx *ctx )
00232 {
00233     if( ctx == NULL )
00234         return;
00235 
00236     mbedtls_ecp_point_free( &ctx->mP );
00237     mbedtls_ecp_point_free( &ctx->R );
00238 
00239     ecp_restart_ma_init( ctx );
00240 }
00241 
00242 /*
00243  * Initialize a restart context
00244  */
00245 void mbedtls_ecp_restart_init( mbedtls_ecp_restart_ctx *ctx )
00246 {
00247     ECP_VALIDATE( ctx != NULL );
00248     ctx->ops_done  = 0;
00249     ctx->depth  = 0;
00250     ctx->rsm  = NULL;
00251     ctx->ma  = NULL;
00252 }
00253 
00254 /*
00255  * Free the components of a restart context
00256  */
00257 void mbedtls_ecp_restart_free( mbedtls_ecp_restart_ctx *ctx )
00258 {
00259     if( ctx == NULL )
00260         return;
00261 
00262     ecp_restart_rsm_free( ctx->rsm  );
00263     mbedtls_free( ctx->rsm  );
00264 
00265     ecp_restart_ma_free( ctx->ma  );
00266     mbedtls_free( ctx->ma  );
00267 
00268     mbedtls_ecp_restart_init( ctx );
00269 }
00270 
00271 /*
00272  * Check if we can do the next step
00273  */
00274 int mbedtls_ecp_check_budget( const mbedtls_ecp_group *grp,
00275                               mbedtls_ecp_restart_ctx *rs_ctx,
00276                               unsigned ops )
00277 {
00278     ECP_VALIDATE_RET( grp != NULL );
00279 
00280     if( rs_ctx != NULL && ecp_max_ops != 0 )
00281     {
00282         /* scale depending on curve size: the chosen reference is 256-bit,
00283          * and multiplication is quadratic. Round to the closest integer. */
00284         if( grp->pbits  >= 512 )
00285             ops *= 4;
00286         else if( grp->pbits  >= 384 )
00287             ops *= 2;
00288 
00289         /* Avoid infinite loops: always allow first step.
00290          * Because of that, however, it's not generally true
00291          * that ops_done <= ecp_max_ops, so the check
00292          * ops_done > ecp_max_ops below is mandatory. */
00293         if( ( rs_ctx->ops_done  != 0 ) &&
00294             ( rs_ctx->ops_done  > ecp_max_ops ||
00295               ops > ecp_max_ops - rs_ctx->ops_done  ) )
00296         {
00297             return( MBEDTLS_ERR_ECP_IN_PROGRESS );
00298         }
00299 
00300         /* update running count */
00301         rs_ctx->ops_done  += ops;
00302     }
00303 
00304     return( 0 );
00305 }
00306 
00307 /* Call this when entering a function that needs its own sub-context */
00308 #define ECP_RS_ENTER( SUB )   do {                                      \
00309     /* reset ops count for this call if top-level */                    \
00310     if( rs_ctx != NULL && rs_ctx->depth++ == 0 )                        \
00311         rs_ctx->ops_done = 0;                                           \
00312                                                                         \
00313     /* set up our own sub-context if needed */                          \
00314     if( mbedtls_ecp_restart_is_enabled() &&                             \
00315         rs_ctx != NULL && rs_ctx->SUB == NULL )                         \
00316     {                                                                   \
00317         rs_ctx->SUB = mbedtls_calloc( 1, sizeof( *rs_ctx->SUB ) );      \
00318         if( rs_ctx->SUB == NULL )                                       \
00319             return( MBEDTLS_ERR_ECP_ALLOC_FAILED );                     \
00320                                                                         \
00321         ecp_restart_## SUB ##_init( rs_ctx->SUB );                      \
00322     }                                                                   \
00323 } while( 0 )
00324 
00325 /* Call this when leaving a function that needs its own sub-context */
00326 #define ECP_RS_LEAVE( SUB )   do {                                      \
00327     /* clear our sub-context when not in progress (done or error) */    \
00328     if( rs_ctx != NULL && rs_ctx->SUB != NULL &&                        \
00329         ret != MBEDTLS_ERR_ECP_IN_PROGRESS )                            \
00330     {                                                                   \
00331         ecp_restart_## SUB ##_free( rs_ctx->SUB );                      \
00332         mbedtls_free( rs_ctx->SUB );                                    \
00333         rs_ctx->SUB = NULL;                                             \
00334     }                                                                   \
00335                                                                         \
00336     if( rs_ctx != NULL )                                                \
00337         rs_ctx->depth--;                                                \
00338 } while( 0 )
00339 
00340 #else /* MBEDTLS_ECP_RESTARTABLE */
00341 
00342 #define ECP_RS_ENTER( sub )     (void) rs_ctx;
00343 #define ECP_RS_LEAVE( sub )     (void) rs_ctx;
00344 
00345 #endif /* MBEDTLS_ECP_RESTARTABLE */
00346 
00347 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) ||   \
00348     defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) ||   \
00349     defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) ||   \
00350     defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) ||   \
00351     defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) ||   \
00352     defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)   ||   \
00353     defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)   ||   \
00354     defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)   ||   \
00355     defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) ||   \
00356     defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) ||   \
00357     defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
00358 #define ECP_SHORTWEIERSTRASS
00359 #endif
00360 
00361 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) || \
00362     defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
00363 #define ECP_MONTGOMERY
00364 #endif
00365 
00366 /*
00367  * List of supported curves:
00368  *  - internal ID
00369  *  - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2, RFC 8446 sec. 4.2.7)
00370  *  - size in bits
00371  *  - readable name
00372  *
00373  * Curves are listed in order: largest curves first, and for a given size,
00374  * fastest curves first. This provides the default order for the SSL module.
00375  *
00376  * Reminder: update profiles in Mbed TLS's x509_crt.c when adding new curves!
00377  */
00378 static const mbedtls_ecp_curve_info ecp_supported_curves[] =
00379 {
00380 #if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
00381     { MBEDTLS_ECP_DP_SECP521R1,    25,     521,    "secp521r1"         },
00382 #endif
00383 #if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
00384     { MBEDTLS_ECP_DP_BP512R1,      28,     512,    "brainpoolP512r1"   },
00385 #endif
00386 #if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
00387     { MBEDTLS_ECP_DP_SECP384R1,    24,     384,    "secp384r1"         },
00388 #endif
00389 #if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
00390     { MBEDTLS_ECP_DP_BP384R1,      27,     384,    "brainpoolP384r1"   },
00391 #endif
00392 #if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
00393     { MBEDTLS_ECP_DP_SECP256R1,    23,     256,    "secp256r1"         },
00394 #endif
00395 #if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
00396     { MBEDTLS_ECP_DP_SECP256K1,    22,     256,    "secp256k1"         },
00397 #endif
00398 #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
00399     { MBEDTLS_ECP_DP_BP256R1,      26,     256,    "brainpoolP256r1"   },
00400 #endif
00401 #if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
00402     { MBEDTLS_ECP_DP_SECP224R1,    21,     224,    "secp224r1"         },
00403 #endif
00404 #if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
00405     { MBEDTLS_ECP_DP_SECP224K1,    20,     224,    "secp224k1"         },
00406 #endif
00407 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
00408     { MBEDTLS_ECP_DP_SECP192R1,    19,     192,    "secp192r1"         },
00409 #endif
00410 #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
00411     { MBEDTLS_ECP_DP_SECP192K1,    18,     192,    "secp192k1"         },
00412 #endif
00413 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) && defined(MBEDTLS_ECDH_VARIANT_EVEREST_ENABLED)
00414     { MBEDTLS_ECP_DP_CURVE25519,   29,     256,    "x25519"            },
00415 #endif
00416     { MBEDTLS_ECP_DP_NONE,          0,     0,      NULL                },
00417 };
00418 
00419 #define ECP_NB_CURVES   sizeof( ecp_supported_curves ) /    \
00420                         sizeof( ecp_supported_curves[0] )
00421 
00422 static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
00423 
00424 /*
00425  * List of supported curves and associated info
00426  */
00427 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void )
00428 {
00429     return( ecp_supported_curves );
00430 }
00431 
00432 /*
00433  * List of supported curves, group ID only
00434  */
00435 const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void )
00436 {
00437     static int init_done = 0;
00438 
00439     if( ! init_done )
00440     {
00441         size_t i = 0;
00442         const mbedtls_ecp_curve_info *curve_info;
00443 
00444         for( curve_info = mbedtls_ecp_curve_list();
00445              curve_info->grp_id  != MBEDTLS_ECP_DP_NONE;
00446              curve_info++ )
00447         {
00448             ecp_supported_grp_id[i++] = curve_info->grp_id ;
00449         }
00450         ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
00451 
00452         init_done = 1;
00453     }
00454 
00455     return( ecp_supported_grp_id );
00456 }
00457 
00458 /*
00459  * Get the curve info for the internal identifier
00460  */
00461 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id )
00462 {
00463     const mbedtls_ecp_curve_info *curve_info;
00464 
00465     for( curve_info = mbedtls_ecp_curve_list();
00466          curve_info->grp_id  != MBEDTLS_ECP_DP_NONE;
00467          curve_info++ )
00468     {
00469         if( curve_info->grp_id  == grp_id )
00470             return( curve_info );
00471     }
00472 
00473     return( NULL );
00474 }
00475 
00476 /*
00477  * Get the curve info from the TLS identifier
00478  */
00479 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id )
00480 {
00481     const mbedtls_ecp_curve_info *curve_info;
00482 
00483     for( curve_info = mbedtls_ecp_curve_list();
00484          curve_info->grp_id  != MBEDTLS_ECP_DP_NONE;
00485          curve_info++ )
00486     {
00487         if( curve_info->tls_id  == tls_id )
00488             return( curve_info );
00489     }
00490 
00491     return( NULL );
00492 }
00493 
00494 /*
00495  * Get the curve info from the name
00496  */
00497 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name )
00498 {
00499     const mbedtls_ecp_curve_info *curve_info;
00500 
00501     if( name == NULL )
00502         return( NULL );
00503 
00504     for( curve_info = mbedtls_ecp_curve_list();
00505          curve_info->grp_id  != MBEDTLS_ECP_DP_NONE;
00506          curve_info++ )
00507     {
00508         if( strcmp( curve_info->name , name ) == 0 )
00509             return( curve_info );
00510     }
00511 
00512     return( NULL );
00513 }
00514 
00515 /*
00516  * Get the type of a curve
00517  */
00518 mbedtls_ecp_curve_type mbedtls_ecp_get_type( const mbedtls_ecp_group *grp )
00519 {
00520     if( grp->G .X .p  == NULL )
00521         return( MBEDTLS_ECP_TYPE_NONE );
00522 
00523     if( grp->G .Y .p  == NULL )
00524         return( MBEDTLS_ECP_TYPE_MONTGOMERY );
00525     else
00526         return( MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS );
00527 }
00528 
00529 /*
00530  * Initialize (the components of) a point
00531  */
00532 void mbedtls_ecp_point_init( mbedtls_ecp_point *pt )
00533 {
00534     ECP_VALIDATE( pt != NULL );
00535 
00536     mbedtls_mpi_init( &pt->X  );
00537     mbedtls_mpi_init( &pt->Y  );
00538     mbedtls_mpi_init( &pt->Z  );
00539 }
00540 
00541 /*
00542  * Initialize (the components of) a group
00543  */
00544 void mbedtls_ecp_group_init( mbedtls_ecp_group *grp )
00545 {
00546     ECP_VALIDATE( grp != NULL );
00547 
00548     grp->id  = MBEDTLS_ECP_DP_NONE;
00549     mbedtls_mpi_init( &grp->P  );
00550     mbedtls_mpi_init( &grp->A  );
00551     mbedtls_mpi_init( &grp->B  );
00552     mbedtls_ecp_point_init( &grp->G  );
00553     mbedtls_mpi_init( &grp->N  );
00554     grp->pbits  = 0;
00555     grp->nbits  = 0;
00556     grp->h = 0;
00557     grp->modp  = NULL;
00558     grp->t_pre  = NULL;
00559     grp->t_post  = NULL;
00560     grp->t_data  = NULL;
00561     grp->T  = NULL;
00562     grp->T_size  = 0;
00563 }
00564 
00565 /*
00566  * Initialize (the components of) a key pair
00567  */
00568 void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key )
00569 {
00570     ECP_VALIDATE( key != NULL );
00571 
00572     mbedtls_ecp_group_init( &key->grp  );
00573     mbedtls_mpi_init( &key->d  );
00574     mbedtls_ecp_point_init( &key->Q  );
00575 }
00576 
00577 /*
00578  * Unallocate (the components of) a point
00579  */
00580 void mbedtls_ecp_point_free( mbedtls_ecp_point *pt )
00581 {
00582     if( pt == NULL )
00583         return;
00584 
00585     mbedtls_mpi_free( &( pt->X  ) );
00586     mbedtls_mpi_free( &( pt->Y  ) );
00587     mbedtls_mpi_free( &( pt->Z  ) );
00588 }
00589 
00590 /*
00591  * Unallocate (the components of) a group
00592  */
00593 void mbedtls_ecp_group_free( mbedtls_ecp_group *grp )
00594 {
00595     size_t i;
00596 
00597     if( grp == NULL )
00598         return;
00599 
00600     if( grp->h != 1 )
00601     {
00602         mbedtls_mpi_free( &grp->P  );
00603         mbedtls_mpi_free( &grp->A  );
00604         mbedtls_mpi_free( &grp->B  );
00605         mbedtls_ecp_point_free( &grp->G  );
00606         mbedtls_mpi_free( &grp->N  );
00607     }
00608 
00609     if( grp->T  != NULL )
00610     {
00611         for( i = 0; i < grp->T_size ; i++ )
00612             mbedtls_ecp_point_free( &grp->T [i] );
00613         mbedtls_free( grp->T  );
00614     }
00615 
00616     mbedtls_platform_zeroize( grp, sizeof( mbedtls_ecp_group ) );
00617 }
00618 
00619 /*
00620  * Unallocate (the components of) a key pair
00621  */
00622 void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key )
00623 {
00624     if( key == NULL )
00625         return;
00626 
00627     mbedtls_ecp_group_free( &key->grp  );
00628     mbedtls_mpi_free( &key->d  );
00629     mbedtls_ecp_point_free( &key->Q  );
00630 }
00631 
00632 /*
00633  * Copy the contents of a point
00634  */
00635 int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
00636 {
00637     int ret;
00638     ECP_VALIDATE_RET( P != NULL );
00639     ECP_VALIDATE_RET( Q != NULL );
00640 
00641     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X , &Q->X  ) );
00642     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y , &Q->Y  ) );
00643     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z , &Q->Z  ) );
00644 
00645 cleanup:
00646     return( ret );
00647 }
00648 
00649 /*
00650  * Copy the contents of a group object
00651  */
00652 int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src )
00653 {
00654     ECP_VALIDATE_RET( dst != NULL );
00655     ECP_VALIDATE_RET( src != NULL );
00656 
00657     return( mbedtls_ecp_group_load( dst, src->id  ) );
00658 }
00659 
00660 /*
00661  * Set point to zero
00662  */
00663 int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt )
00664 {
00665     int ret;
00666     ECP_VALIDATE_RET( pt != NULL );
00667 
00668     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X  , 1 ) );
00669     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y  , 1 ) );
00670     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z  , 0 ) );
00671 
00672 cleanup:
00673     return( ret );
00674 }
00675 
00676 /*
00677  * Tell if a point is zero
00678  */
00679 int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt )
00680 {
00681     ECP_VALIDATE_RET( pt != NULL );
00682 
00683     return( mbedtls_mpi_cmp_int( &pt->Z , 0 ) == 0 );
00684 }
00685 
00686 /*
00687  * Compare two points lazily
00688  */
00689 int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P,
00690                            const mbedtls_ecp_point *Q )
00691 {
00692     ECP_VALIDATE_RET( P != NULL );
00693     ECP_VALIDATE_RET( Q != NULL );
00694 
00695     if( mbedtls_mpi_cmp_mpi( &P->X , &Q->X  ) == 0 &&
00696         mbedtls_mpi_cmp_mpi( &P->Y , &Q->Y  ) == 0 &&
00697         mbedtls_mpi_cmp_mpi( &P->Z , &Q->Z  ) == 0 )
00698     {
00699         return( 0 );
00700     }
00701 
00702     return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00703 }
00704 
00705 /*
00706  * Import a non-zero point from ASCII strings
00707  */
00708 int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix,
00709                            const char *x, const char *y )
00710 {
00711     int ret;
00712     ECP_VALIDATE_RET( P != NULL );
00713     ECP_VALIDATE_RET( x != NULL );
00714     ECP_VALIDATE_RET( y != NULL );
00715 
00716     MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X , radix, x ) );
00717     MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y , radix, y ) );
00718     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z , 1 ) );
00719 
00720 cleanup:
00721     return( ret );
00722 }
00723 
00724 /*
00725  * Export a point into unsigned binary data (SEC1 2.3.3 and RFC7748)
00726  */
00727 int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp,
00728                                     const mbedtls_ecp_point *P,
00729                                     int format, size_t *olen,
00730                                     unsigned char *buf, size_t buflen )
00731 {
00732     int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
00733     size_t plen;
00734     ECP_VALIDATE_RET( grp  != NULL );
00735     ECP_VALIDATE_RET( P    != NULL );
00736     ECP_VALIDATE_RET( olen != NULL );
00737     ECP_VALIDATE_RET( buf  != NULL );
00738     ECP_VALIDATE_RET( format == MBEDTLS_ECP_PF_UNCOMPRESSED ||
00739                       format == MBEDTLS_ECP_PF_COMPRESSED );
00740 
00741     plen = mbedtls_mpi_size( &grp->P  );
00742 
00743 #if defined(ECP_MONTGOMERY)
00744     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )
00745     {
00746         *olen = plen;
00747         if( buflen < *olen )
00748             return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
00749 
00750         MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary_le( &P->X , buf, plen ) );
00751     }
00752 #endif
00753 #if defined(ECP_SHORTWEIERSTRASS)
00754     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
00755     {
00756         /*
00757          * Common case: P == 0
00758          */
00759         if( mbedtls_mpi_cmp_int( &P->Z , 0 ) == 0 )
00760         {
00761             if( buflen < 1 )
00762                 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
00763 
00764             buf[0] = 0x00;
00765             *olen = 1;
00766 
00767             return( 0 );
00768         }
00769 
00770         if( format == MBEDTLS_ECP_PF_UNCOMPRESSED )
00771         {
00772             *olen = 2 * plen + 1;
00773 
00774             if( buflen < *olen )
00775                 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
00776 
00777             buf[0] = 0x04;
00778             MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X , buf + 1, plen ) );
00779             MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y , buf + 1 + plen, plen ) );
00780         }
00781         else if( format == MBEDTLS_ECP_PF_COMPRESSED )
00782         {
00783             *olen = plen + 1;
00784 
00785             if( buflen < *olen )
00786                 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
00787 
00788             buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y , 0 );
00789             MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X , buf + 1, plen ) );
00790         }
00791     }
00792 #endif
00793 
00794 cleanup:
00795     return( ret );
00796 }
00797 
00798 /*
00799  * Import a point from unsigned binary data (SEC1 2.3.4 and RFC7748)
00800  */
00801 int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp,
00802                                    mbedtls_ecp_point *pt,
00803                                    const unsigned char *buf, size_t ilen )
00804 {
00805     int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
00806     size_t plen;
00807     ECP_VALIDATE_RET( grp != NULL );
00808     ECP_VALIDATE_RET( pt  != NULL );
00809     ECP_VALIDATE_RET( buf != NULL );
00810 
00811     if( ilen < 1 )
00812         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00813 
00814     plen = mbedtls_mpi_size( &grp->P  );
00815 
00816 #if defined(ECP_MONTGOMERY)
00817     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )
00818     {
00819         if( plen != ilen )
00820             return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00821 
00822         MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary_le( &pt->X , buf, plen ) );
00823         mbedtls_mpi_free( &pt->Y  );
00824 
00825         if( grp->id  == MBEDTLS_ECP_DP_CURVE25519 )
00826             /* Set most significant bit to 0 as prescribed in RFC7748 §5 */
00827             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &pt->X , plen * 8 - 1, 0 ) );
00828 
00829         MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 1 ) );
00830     }
00831 #endif
00832 #if defined(ECP_SHORTWEIERSTRASS)
00833     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
00834     {
00835         if( buf[0] == 0x00 )
00836         {
00837             if( ilen == 1 )
00838                 return( mbedtls_ecp_set_zero( pt ) );
00839             else
00840                 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00841         }
00842 
00843         if( buf[0] != 0x04 )
00844             return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
00845 
00846         if( ilen != 2 * plen + 1 )
00847             return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00848 
00849         MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X , buf + 1, plen ) );
00850         MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y ,
00851                                                   buf + 1 + plen, plen ) );
00852         MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 1 ) );
00853     }
00854 #endif
00855 
00856 cleanup:
00857     return( ret );
00858 }
00859 
00860 /*
00861  * Import a point from a TLS ECPoint record (RFC 4492)
00862  *      struct {
00863  *          opaque point <1..2^8-1>;
00864  *      } ECPoint;
00865  */
00866 int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group *grp,
00867                                 mbedtls_ecp_point *pt,
00868                                 const unsigned char **buf, size_t buf_len )
00869 {
00870     unsigned char data_len;
00871     const unsigned char *buf_start;
00872     ECP_VALIDATE_RET( grp != NULL );
00873     ECP_VALIDATE_RET( pt  != NULL );
00874     ECP_VALIDATE_RET( buf != NULL );
00875     ECP_VALIDATE_RET( *buf != NULL );
00876 
00877     /*
00878      * We must have at least two bytes (1 for length, at least one for data)
00879      */
00880     if( buf_len < 2 )
00881         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00882 
00883     data_len = *(*buf)++;
00884     if( data_len < 1 || data_len > buf_len - 1 )
00885         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00886 
00887     /*
00888      * Save buffer start for read_binary and update buf
00889      */
00890     buf_start = *buf;
00891     *buf += data_len;
00892 
00893     return( mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len ) );
00894 }
00895 
00896 /*
00897  * Export a point as a TLS ECPoint record (RFC 4492)
00898  *      struct {
00899  *          opaque point <1..2^8-1>;
00900  *      } ECPoint;
00901  */
00902 int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt,
00903                          int format, size_t *olen,
00904                          unsigned char *buf, size_t blen )
00905 {
00906     int ret;
00907     ECP_VALIDATE_RET( grp  != NULL );
00908     ECP_VALIDATE_RET( pt   != NULL );
00909     ECP_VALIDATE_RET( olen != NULL );
00910     ECP_VALIDATE_RET( buf  != NULL );
00911     ECP_VALIDATE_RET( format == MBEDTLS_ECP_PF_UNCOMPRESSED ||
00912                       format == MBEDTLS_ECP_PF_COMPRESSED );
00913 
00914     /*
00915      * buffer length must be at least one, for our length byte
00916      */
00917     if( blen < 1 )
00918         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00919 
00920     if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format,
00921                     olen, buf + 1, blen - 1) ) != 0 )
00922         return( ret );
00923 
00924     /*
00925      * write length to the first byte and update total length
00926      */
00927     buf[0] = (unsigned char) *olen;
00928     ++*olen;
00929 
00930     return( 0 );
00931 }
00932 
00933 /*
00934  * Set a group from an ECParameters record (RFC 4492)
00935  */
00936 int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp,
00937                                 const unsigned char **buf, size_t len )
00938 {
00939     int ret;
00940     mbedtls_ecp_group_id grp_id;
00941     ECP_VALIDATE_RET( grp  != NULL );
00942     ECP_VALIDATE_RET( buf  != NULL );
00943     ECP_VALIDATE_RET( *buf != NULL );
00944 
00945     if( ( ret = mbedtls_ecp_tls_read_group_id( &grp_id, buf, len ) ) != 0 )
00946         return( ret );
00947 
00948     return( mbedtls_ecp_group_load( grp, grp_id ) );
00949 }
00950 
00951 /*
00952  * Read a group id from an ECParameters record (RFC 4492) and convert it to
00953  * mbedtls_ecp_group_id.
00954  */
00955 int mbedtls_ecp_tls_read_group_id( mbedtls_ecp_group_id *grp,
00956                                    const unsigned char **buf, size_t len )
00957 {
00958     uint16_t tls_id;
00959     const mbedtls_ecp_curve_info *curve_info;
00960     ECP_VALIDATE_RET( grp  != NULL );
00961     ECP_VALIDATE_RET( buf  != NULL );
00962     ECP_VALIDATE_RET( *buf != NULL );
00963 
00964     /*
00965      * We expect at least three bytes (see below)
00966      */
00967     if( len < 3 )
00968         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00969 
00970     /*
00971      * First byte is curve_type; only named_curve is handled
00972      */
00973     if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE )
00974         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00975 
00976     /*
00977      * Next two bytes are the namedcurve value
00978      */
00979     tls_id = *(*buf)++;
00980     tls_id <<= 8;
00981     tls_id |= *(*buf)++;
00982 
00983     if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
00984         return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
00985 
00986     *grp = curve_info->grp_id ;
00987 
00988     return( 0 );
00989 }
00990 
00991 /*
00992  * Write the ECParameters record corresponding to a group (RFC 4492)
00993  */
00994 int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen,
00995                          unsigned char *buf, size_t blen )
00996 {
00997     const mbedtls_ecp_curve_info *curve_info;
00998     ECP_VALIDATE_RET( grp  != NULL );
00999     ECP_VALIDATE_RET( buf  != NULL );
01000     ECP_VALIDATE_RET( olen != NULL );
01001 
01002     if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id  ) ) == NULL )
01003         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
01004 
01005     /*
01006      * We are going to write 3 bytes (see below)
01007      */
01008     *olen = 3;
01009     if( blen < *olen )
01010         return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
01011 
01012     /*
01013      * First byte is curve_type, always named_curve
01014      */
01015     *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
01016 
01017     /*
01018      * Next two bytes are the namedcurve value
01019      */
01020     buf[0] = curve_info->tls_id  >> 8;
01021     buf[1] = curve_info->tls_id  & 0xFF;
01022 
01023     return( 0 );
01024 }
01025 
01026 /*
01027  * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
01028  * See the documentation of struct mbedtls_ecp_group.
01029  *
01030  * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
01031  */
01032 static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp )
01033 {
01034     int ret;
01035 
01036     if( grp->modp  == NULL )
01037         return( mbedtls_mpi_mod_mpi( N, N, &grp->P  ) );
01038 
01039     /* N->s < 0 is a much faster test, which fails only if N is 0 */
01040     if( ( N->s  < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) ||
01041         mbedtls_mpi_bitlen( N ) > 2 * grp->pbits  )
01042     {
01043         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
01044     }
01045 
01046     MBEDTLS_MPI_CHK( grp->modp ( N ) );
01047 
01048     /* N->s < 0 is a much faster test, which fails only if N is 0 */
01049     while( N->s  < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 )
01050         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P  ) );
01051 
01052     while( mbedtls_mpi_cmp_mpi( N, &grp->P  ) >= 0 )
01053         /* we known P, N and the result are positive */
01054         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P  ) );
01055 
01056 cleanup:
01057     return( ret );
01058 }
01059 
01060 /*
01061  * Fast mod-p functions expect their argument to be in the 0..p^2 range.
01062  *
01063  * In order to guarantee that, we need to ensure that operands of
01064  * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
01065  * bring the result back to this range.
01066  *
01067  * The following macros are shortcuts for doing that.
01068  */
01069 
01070 /*
01071  * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
01072  */
01073 #if defined(MBEDTLS_SELF_TEST)
01074 #define INC_MUL_COUNT   mul_count++;
01075 #else
01076 #define INC_MUL_COUNT
01077 #endif
01078 
01079 #define MOD_MUL( N )                                                    \
01080     do                                                                  \
01081     {                                                                   \
01082         MBEDTLS_MPI_CHK( ecp_modp( &(N), grp ) );                       \
01083         INC_MUL_COUNT                                                   \
01084     } while( 0 )
01085 
01086 static inline int mbedtls_mpi_mul_mod( const mbedtls_ecp_group *grp,
01087                                        mbedtls_mpi *X,
01088                                        const mbedtls_mpi *A,
01089                                        const mbedtls_mpi *B )
01090 {
01091     int ret;
01092     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( X, A, B ) );
01093     MOD_MUL( *X );
01094 cleanup:
01095     return( ret );
01096 }
01097 
01098 /*
01099  * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
01100  * N->s < 0 is a very fast test, which fails only if N is 0
01101  */
01102 #define MOD_SUB( N )                                                    \
01103     while( (N).s < 0 && mbedtls_mpi_cmp_int( &(N), 0 ) != 0 )           \
01104         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &(N), &(N), &grp->P ) )
01105 
01106 static inline int mbedtls_mpi_sub_mod( const mbedtls_ecp_group *grp,
01107                                        mbedtls_mpi *X,
01108                                        const mbedtls_mpi *A,
01109                                        const mbedtls_mpi *B )
01110 {
01111     int ret;
01112     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( X, A, B ) );
01113     MOD_SUB( *X );
01114 cleanup:
01115     return( ret );
01116 }
01117 
01118 /*
01119  * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
01120  * We known P, N and the result are positive, so sub_abs is correct, and
01121  * a bit faster.
01122  */
01123 #define MOD_ADD( N )                                                    \
01124     while( mbedtls_mpi_cmp_mpi( &(N), &grp->P ) >= 0 )                  \
01125         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &(N), &(N), &grp->P ) )
01126 
01127 static inline int mbedtls_mpi_add_mod( const mbedtls_ecp_group *grp,
01128                                        mbedtls_mpi *X,
01129                                        const mbedtls_mpi *A,
01130                                        const mbedtls_mpi *B )
01131 {
01132     int ret;
01133     MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, A, B ) );
01134     MOD_ADD( *X );
01135 cleanup:
01136     return( ret );
01137 }
01138 
01139 static inline int mbedtls_mpi_shift_l_mod( const mbedtls_ecp_group *grp,
01140                                            mbedtls_mpi *X,
01141                                            size_t count )
01142 {
01143     int ret;
01144     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( X, count ) );
01145     MOD_ADD( *X );
01146 cleanup:
01147     return( ret );
01148 }
01149 
01150 #if defined(ECP_SHORTWEIERSTRASS)
01151 /*
01152  * For curves in short Weierstrass form, we do all the internal operations in
01153  * Jacobian coordinates.
01154  *
01155  * For multiplication, we'll use a comb method with coutermeasueres against
01156  * SPA, hence timing attacks.
01157  */
01158 
01159 /*
01160  * Normalize jacobian coordinates so that Z == 0 || Z == 1  (GECC 3.2.1)
01161  * Cost: 1N := 1I + 3M + 1S
01162  */
01163 static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt )
01164 {
01165     int ret;
01166     mbedtls_mpi Zi, ZZi;
01167 
01168     if( mbedtls_mpi_cmp_int( &pt->Z , 0 ) == 0 )
01169         return( 0 );
01170 
01171 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
01172     if( mbedtls_internal_ecp_grp_capable( grp ) )
01173         return( mbedtls_internal_ecp_normalize_jac( grp, pt ) );
01174 #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */
01175 
01176     mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
01177 
01178     /*
01179      * X = X / Z^2  mod p
01180      */
01181     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi,      &pt->Z ,     &grp->P  ) );
01182     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ZZi,     &Zi,        &Zi     ) );
01183     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->X ,   &pt->X ,     &ZZi    ) );
01184 
01185     /*
01186      * Y = Y / Z^3  mod p
01187      */
01188     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y ,   &pt->Y ,     &ZZi    ) );
01189     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y ,   &pt->Y ,     &Zi     ) );
01190 
01191     /*
01192      * Z = 1
01193      */
01194     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 1 ) );
01195 
01196 cleanup:
01197 
01198     mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
01199 
01200     return( ret );
01201 }
01202 
01203 /*
01204  * Normalize jacobian coordinates of an array of (pointers to) points,
01205  * using Montgomery's trick to perform only one inversion mod P.
01206  * (See for example Cohen's "A Course in Computational Algebraic Number
01207  * Theory", Algorithm 10.3.4.)
01208  *
01209  * Warning: fails (returning an error) if one of the points is zero!
01210  * This should never happen, see choice of w in ecp_mul_comb().
01211  *
01212  * Cost: 1N(t) := 1I + (6t - 3)M + 1S
01213  */
01214 static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
01215                                    mbedtls_ecp_point *T[], size_t T_size )
01216 {
01217     int ret;
01218     size_t i;
01219     mbedtls_mpi *c, u, Zi, ZZi;
01220 
01221     if( T_size < 2 )
01222         return( ecp_normalize_jac( grp, *T ) );
01223 
01224 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
01225     if( mbedtls_internal_ecp_grp_capable( grp ) )
01226         return( mbedtls_internal_ecp_normalize_jac_many( grp, T, T_size ) );
01227 #endif
01228 
01229     if( ( c = mbedtls_calloc( T_size, sizeof( mbedtls_mpi ) ) ) == NULL )
01230         return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
01231 
01232     for( i = 0; i < T_size; i++ )
01233         mbedtls_mpi_init( &c[i] );
01234 
01235     mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
01236 
01237     /*
01238      * c[i] = Z_0 * ... * Z_i
01239      */
01240     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) );
01241     for( i = 1; i < T_size; i++ )
01242     {
01243         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &c[i], &c[i-1], &T[i]->Z ) );
01244     }
01245 
01246     /*
01247      * u = 1 / (Z_0 * ... * Z_n) mod P
01248      */
01249     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[T_size-1], &grp->P  ) );
01250 
01251     for( i = T_size - 1; ; i-- )
01252     {
01253         /*
01254          * Zi = 1 / Z_i mod p
01255          * u = 1 / (Z_0 * ... * Z_i) mod P
01256          */
01257         if( i == 0 ) {
01258             MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) );
01259         }
01260         else
01261         {
01262             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &Zi, &u, &c[i-1]  ) );
01263             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &u,  &u, &T[i]->Z ) );
01264         }
01265 
01266         /*
01267          * proceed as in normalize()
01268          */
01269         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ZZi,     &Zi,      &Zi  ) );
01270         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T[i]->X, &T[i]->X, &ZZi ) );
01271         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T[i]->Y, &T[i]->Y, &ZZi ) );
01272         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T[i]->Y, &T[i]->Y, &Zi  ) );
01273 
01274         /*
01275          * Post-precessing: reclaim some memory by shrinking coordinates
01276          * - not storing Z (always 1)
01277          * - shrinking other coordinates, but still keeping the same number of
01278          *   limbs as P, as otherwise it will too likely be regrown too fast.
01279          */
01280         MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P .n  ) );
01281         MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P .n  ) );
01282         mbedtls_mpi_free( &T[i]->Z );
01283 
01284         if( i == 0 )
01285             break;
01286     }
01287 
01288 cleanup:
01289 
01290     mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
01291     for( i = 0; i < T_size; i++ )
01292         mbedtls_mpi_free( &c[i] );
01293     mbedtls_free( c );
01294 
01295     return( ret );
01296 }
01297 
01298 /*
01299  * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
01300  * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
01301  */
01302 static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp,
01303                             mbedtls_ecp_point *Q,
01304                             unsigned char inv )
01305 {
01306     int ret;
01307     unsigned char nonzero;
01308     mbedtls_mpi mQY;
01309 
01310     mbedtls_mpi_init( &mQY );
01311 
01312     /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
01313     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P , &Q->Y  ) );
01314     nonzero = mbedtls_mpi_cmp_int( &Q->Y , 0 ) != 0;
01315     MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y , &mQY, inv & nonzero ) );
01316 
01317 cleanup:
01318     mbedtls_mpi_free( &mQY );
01319 
01320     return( ret );
01321 }
01322 
01323 /*
01324  * Point doubling R = 2 P, Jacobian coordinates
01325  *
01326  * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
01327  *
01328  * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR
01329  * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.
01330  *
01331  * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
01332  *
01333  * Cost: 1D := 3M + 4S          (A ==  0)
01334  *             4M + 4S          (A == -3)
01335  *             3M + 6S + 1a     otherwise
01336  */
01337 static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
01338                            const mbedtls_ecp_point *P )
01339 {
01340     int ret;
01341     mbedtls_mpi M, S, T, U;
01342 
01343 #if defined(MBEDTLS_SELF_TEST)
01344     dbl_count++;
01345 #endif
01346 
01347 #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
01348     if( mbedtls_internal_ecp_grp_capable( grp ) )
01349         return( mbedtls_internal_ecp_double_jac( grp, R, P ) );
01350 #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */
01351 
01352     mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U );
01353 
01354     /* Special case for A = -3 */
01355     if( grp->A .p  == NULL )
01356     {
01357         /* M = 3(X + Z^2)(X - Z^2) */
01358         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S,  &P->Z ,  &P->Z    ) );
01359         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &T,  &P->X ,  &S      ) );
01360         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &U,  &P->X ,  &S      ) );
01361         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S,  &T,     &U      ) );
01362         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M,  &S,     3       ) ); MOD_ADD( M );
01363     }
01364     else
01365     {
01366         /* M = 3.X^2 */
01367         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S,  &P->X ,  &P->X    ) );
01368         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M,  &S,     3       ) ); MOD_ADD( M );
01369 
01370         /* Optimize away for "koblitz" curves with A = 0 */
01371         if( mbedtls_mpi_cmp_int( &grp->A , 0 ) != 0 )
01372         {
01373             /* M += A.Z^4 */
01374             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S,  &P->Z ,  &P->Z    ) );
01375             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T,  &S,     &S      ) );
01376             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S,  &T,     &grp->A  ) );
01377             MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &M,  &M,     &S      ) );
01378         }
01379     }
01380 
01381     /* S = 4.X.Y^2 */
01382     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T,  &P->Y ,  &P->Y    ) );
01383     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &T,  1               ) );
01384     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S,  &P->X ,  &T      ) );
01385     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &S,  1               ) );
01386 
01387     /* U = 8.Y^4 */
01388     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &U,  &T,     &T      ) );
01389     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &U,  1               ) );
01390 
01391     /* T = M^2 - 2.S */
01392     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T,  &M,     &M      ) );
01393     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T,  &T,     &S      ) );
01394     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T,  &T,     &S      ) );
01395 
01396     /* S = M(S - T) - U */
01397     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &S,  &S,     &T      ) );
01398     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S,  &S,     &M      ) );
01399     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &S,  &S,     &U      ) );
01400 
01401     /* U = 2.Y.Z */
01402     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &U,  &P->Y ,  &P->Z    ) );
01403     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &U,  1               ) );
01404 
01405     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X , &T ) );
01406     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y , &S ) );
01407     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z , &U ) );
01408 
01409 cleanup:
01410     mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U );
01411 
01412     return( ret );
01413 }
01414 
01415 /*
01416  * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
01417  *
01418  * The coordinates of Q must be normalized (= affine),
01419  * but those of P don't need to. R is not normalized.
01420  *
01421  * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
01422  * None of these cases can happen as intermediate step in ecp_mul_comb():
01423  * - at each step, P, Q and R are multiples of the base point, the factor
01424  *   being less than its order, so none of them is zero;
01425  * - Q is an odd multiple of the base point, P an even multiple,
01426  *   due to the choice of precomputed points in the modified comb method.
01427  * So branches for these cases do not leak secret information.
01428  *
01429  * We accept Q->Z being unset (saving memory in tables) as meaning 1.
01430  *
01431  * Cost: 1A := 8M + 3S
01432  */
01433 static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
01434                           const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
01435 {
01436     int ret;
01437     mbedtls_mpi T1, T2, T3, T4, X, Y, Z;
01438 
01439 #if defined(MBEDTLS_SELF_TEST)
01440     add_count++;
01441 #endif
01442 
01443 #if defined(MBEDTLS_ECP_ADD_MIXED_ALT)
01444     if( mbedtls_internal_ecp_grp_capable( grp ) )
01445         return( mbedtls_internal_ecp_add_mixed( grp, R, P, Q ) );
01446 #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */
01447 
01448     /*
01449      * Trivial cases: P == 0 or Q == 0 (case 1)
01450      */
01451     if( mbedtls_mpi_cmp_int( &P->Z , 0 ) == 0 )
01452         return( mbedtls_ecp_copy( R, Q ) );
01453 
01454     if( Q->Z .p  != NULL && mbedtls_mpi_cmp_int( &Q->Z , 0 ) == 0 )
01455         return( mbedtls_ecp_copy( R, P ) );
01456 
01457     /*
01458      * Make sure Q coordinates are normalized
01459      */
01460     if( Q->Z .p  != NULL && mbedtls_mpi_cmp_int( &Q->Z , 1 ) != 0 )
01461         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
01462 
01463     mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 );
01464     mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
01465 
01466     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T1,  &P->Z ,  &P->Z  ) );
01467     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T2,  &T1,    &P->Z  ) );
01468     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T1,  &T1,    &Q->X  ) );
01469     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T2,  &T2,    &Q->Y  ) );
01470     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T1,  &T1,    &P->X  ) );
01471     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T2,  &T2,    &P->Y  ) );
01472 
01473     /* Special cases (2) and (3) */
01474     if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 )
01475     {
01476         if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 )
01477         {
01478             ret = ecp_double_jac( grp, R, P );
01479             goto cleanup;
01480         }
01481         else
01482         {
01483             ret = mbedtls_ecp_set_zero( R );
01484             goto cleanup;
01485         }
01486     }
01487 
01488     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &Z,   &P->Z ,  &T1   ) );
01489     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3,  &T1,    &T1   ) );
01490     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T4,  &T3,    &T1   ) );
01491     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3,  &T3,    &P->X  ) );
01492     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &T3 ) );
01493     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l_mod( grp, &T1,  1     ) );
01494     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &X,   &T2,    &T2   ) );
01495     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &X,   &X,     &T1   ) );
01496     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &X,   &X,     &T4   ) );
01497     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &T3,  &T3,    &X    ) );
01498     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T3,  &T3,    &T2   ) );
01499     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &T4,  &T4,    &P->Y  ) );
01500     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &Y,   &T3,    &T4   ) );
01501 
01502     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X , &X ) );
01503     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y , &Y ) );
01504     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z , &Z ) );
01505 
01506 cleanup:
01507 
01508     mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 );
01509     mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
01510 
01511     return( ret );
01512 }
01513 
01514 /*
01515  * Randomize jacobian coordinates:
01516  * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
01517  * This is sort of the reverse operation of ecp_normalize_jac().
01518  *
01519  * This countermeasure was first suggested in [2].
01520  */
01521 static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
01522                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
01523 {
01524     int ret;
01525     mbedtls_mpi l, ll;
01526     size_t p_size;
01527     int count = 0;
01528 
01529 #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
01530     if( mbedtls_internal_ecp_grp_capable( grp ) )
01531         return( mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng ) );
01532 #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */
01533 
01534     p_size = ( grp->pbits  + 7 ) / 8;
01535     mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll );
01536 
01537     /* Generate l such that 1 < l < p */
01538     do
01539     {
01540         MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
01541 
01542         while( mbedtls_mpi_cmp_mpi( &l, &grp->P  ) >= 0 )
01543             MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
01544 
01545         if( count++ > 10 )
01546             return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
01547     }
01548     while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
01549 
01550     /* Z = l * Z */
01551     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Z ,   &pt->Z ,     &l  ) );
01552 
01553     /* X = l^2 * X */
01554     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ll,      &l,         &l  ) );
01555     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->X ,   &pt->X ,     &ll ) );
01556 
01557     /* Y = l^3 * Y */
01558     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &ll,      &ll,        &l  ) );
01559     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &pt->Y ,   &pt->Y ,     &ll ) );
01560 
01561 cleanup:
01562     mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll );
01563 
01564     return( ret );
01565 }
01566 
01567 /*
01568  * Check and define parameters used by the comb method (see below for details)
01569  */
01570 #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7
01571 #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"
01572 #endif
01573 
01574 /* d = ceil( n / w ) */
01575 #define COMB_MAX_D      ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2
01576 
01577 /* number of precomputed points */
01578 #define COMB_MAX_PRE    ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) )
01579 
01580 /*
01581  * Compute the representation of m that will be used with our comb method.
01582  *
01583  * The basic comb method is described in GECC 3.44 for example. We use a
01584  * modified version that provides resistance to SPA by avoiding zero
01585  * digits in the representation as in [3]. We modify the method further by
01586  * requiring that all K_i be odd, which has the small cost that our
01587  * representation uses one more K_i, due to carries, but saves on the size of
01588  * the precomputed table.
01589  *
01590  * Summary of the comb method and its modifications:
01591  *
01592  * - The goal is to compute m*P for some w*d-bit integer m.
01593  *
01594  * - The basic comb method splits m into the w-bit integers
01595  *   x[0] .. x[d-1] where x[i] consists of the bits in m whose
01596  *   index has residue i modulo d, and computes m * P as
01597  *   S[x[0]] + 2 * S[x[1]] + .. + 2^(d-1) S[x[d-1]], where
01598  *   S[i_{w-1} .. i_0] := i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + i_0 P.
01599  *
01600  * - If it happens that, say, x[i+1]=0 (=> S[x[i+1]]=0), one can replace the sum by
01601  *    .. + 2^{i-1} S[x[i-1]] - 2^i S[x[i]] + 2^{i+1} S[x[i]] + 2^{i+2} S[x[i+2]] ..,
01602  *   thereby successively converting it into a form where all summands
01603  *   are nonzero, at the cost of negative summands. This is the basic idea of [3].
01604  *
01605  * - More generally, even if x[i+1] != 0, we can first transform the sum as
01606  *   .. - 2^i S[x[i]] + 2^{i+1} ( S[x[i]] + S[x[i+1]] ) + 2^{i+2} S[x[i+2]] ..,
01607  *   and then replace S[x[i]] + S[x[i+1]] = S[x[i] ^ x[i+1]] + 2 S[x[i] & x[i+1]].
01608  *   Performing and iterating this procedure for those x[i] that are even
01609  *   (keeping track of carry), we can transform the original sum into one of the form
01610  *   S[x'[0]] +- 2 S[x'[1]] +- .. +- 2^{d-1} S[x'[d-1]] + 2^d S[x'[d]]
01611  *   with all x'[i] odd. It is therefore only necessary to know S at odd indices,
01612  *   which is why we are only computing half of it in the first place in
01613  *   ecp_precompute_comb and accessing it with index abs(i) / 2 in ecp_select_comb.
01614  *
01615  * - For the sake of compactness, only the seven low-order bits of x[i]
01616  *   are used to represent its absolute value (K_i in the paper), and the msb
01617  *   of x[i] encodes the sign (s_i in the paper): it is set if and only if
01618  *   if s_i == -1;
01619  *
01620  * Calling conventions:
01621  * - x is an array of size d + 1
01622  * - w is the size, ie number of teeth, of the comb, and must be between
01623  *   2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE)
01624  * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d
01625  *   (the result will be incorrect if these assumptions are not satisfied)
01626  */
01627 static void ecp_comb_recode_core( unsigned char x[], size_t d,
01628                                   unsigned char w, const mbedtls_mpi *m )
01629 {
01630     size_t i, j;
01631     unsigned char c, cc, adjust;
01632 
01633     memset( x, 0, d+1 );
01634 
01635     /* First get the classical comb values (except for x_d = 0) */
01636     for( i = 0; i < d; i++ )
01637         for( j = 0; j < w; j++ )
01638             x[i] |= mbedtls_mpi_get_bit( m, i + d * j ) << j;
01639 
01640     /* Now make sure x_1 .. x_d are odd */
01641     c = 0;
01642     for( i = 1; i <= d; i++ )
01643     {
01644         /* Add carry and update it */
01645         cc   = x[i] & c;
01646         x[i] = x[i] ^ c;
01647         c = cc;
01648 
01649         /* Adjust if needed, avoiding branches */
01650         adjust = 1 - ( x[i] & 0x01 );
01651         c   |= x[i] & ( x[i-1] * adjust );
01652         x[i] = x[i] ^ ( x[i-1] * adjust );
01653         x[i-1] |= adjust << 7;
01654     }
01655 }
01656 
01657 /*
01658  * Precompute points for the adapted comb method
01659  *
01660  * Assumption: T must be able to hold 2^{w - 1} elements.
01661  *
01662  * Operation: If i = i_{w-1} ... i_1 is the binary representation of i,
01663  *            sets T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P.
01664  *
01665  * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
01666  *
01667  * Note: Even comb values (those where P would be omitted from the
01668  *       sum defining T[i] above) are not needed in our adaption
01669  *       the comb method. See ecp_comb_recode_core().
01670  *
01671  * This function currently works in four steps:
01672  * (1) [dbl]      Computation of intermediate T[i] for 2-power values of i
01673  * (2) [norm_dbl] Normalization of coordinates of these T[i]
01674  * (3) [add]      Computation of all T[i]
01675  * (4) [norm_add] Normalization of all T[i]
01676  *
01677  * Step 1 can be interrupted but not the others; together with the final
01678  * coordinate normalization they are the largest steps done at once, depending
01679  * on the window size. Here are operation counts for P-256:
01680  *
01681  * step     (2)     (3)     (4)
01682  * w = 5    142     165     208
01683  * w = 4    136      77     160
01684  * w = 3    130      33     136
01685  * w = 2    124      11     124
01686  *
01687  * So if ECC operations are blocking for too long even with a low max_ops
01688  * value, it's useful to set MBEDTLS_ECP_WINDOW_SIZE to a lower value in order
01689  * to minimize maximum blocking time.
01690  */
01691 static int ecp_precompute_comb( const mbedtls_ecp_group *grp,
01692                                 mbedtls_ecp_point T[], const mbedtls_ecp_point *P,
01693                                 unsigned char w, size_t d,
01694                                 mbedtls_ecp_restart_ctx *rs_ctx )
01695 {
01696     int ret;
01697     unsigned char i;
01698     size_t j = 0;
01699     const unsigned char T_size = 1U << ( w - 1 );
01700     mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1];
01701 
01702 #if defined(MBEDTLS_ECP_RESTARTABLE)
01703     if( rs_ctx != NULL && rs_ctx->rsm  != NULL )
01704     {
01705         if( rs_ctx->rsm ->state == ecp_rsm_pre_dbl )
01706             goto dbl;
01707         if( rs_ctx->rsm ->state == ecp_rsm_pre_norm_dbl )
01708             goto norm_dbl;
01709         if( rs_ctx->rsm ->state == ecp_rsm_pre_add )
01710             goto add;
01711         if( rs_ctx->rsm ->state == ecp_rsm_pre_norm_add )
01712             goto norm_add;
01713     }
01714 #else
01715     (void) rs_ctx;
01716 #endif
01717 
01718 #if defined(MBEDTLS_ECP_RESTARTABLE)
01719     if( rs_ctx != NULL && rs_ctx->rsm  != NULL )
01720     {
01721         rs_ctx->rsm ->state = ecp_rsm_pre_dbl;
01722 
01723         /* initial state for the loop */
01724         rs_ctx->rsm ->i = 0;
01725     }
01726 
01727 dbl:
01728 #endif
01729     /*
01730      * Set T[0] = P and
01731      * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
01732      */
01733     MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) );
01734 
01735 #if defined(MBEDTLS_ECP_RESTARTABLE)
01736     if( rs_ctx != NULL && rs_ctx->rsm  != NULL && rs_ctx->rsm ->i != 0 )
01737         j = rs_ctx->rsm ->i;
01738     else
01739 #endif
01740         j = 0;
01741 
01742     for( ; j < d * ( w - 1 ); j++ )
01743     {
01744         MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL );
01745 
01746         i = 1U << ( j / d );
01747         cur = T + i;
01748 
01749         if( j % d == 0 )
01750             MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) );
01751 
01752         MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) );
01753     }
01754 
01755 #if defined(MBEDTLS_ECP_RESTARTABLE)
01756     if( rs_ctx != NULL && rs_ctx->rsm  != NULL )
01757         rs_ctx->rsm ->state = ecp_rsm_pre_norm_dbl;
01758 
01759 norm_dbl:
01760 #endif
01761     /*
01762      * Normalize current elements in T. As T has holes,
01763      * use an auxiliary array of pointers to elements in T.
01764      */
01765     j = 0;
01766     for( i = 1; i < T_size; i <<= 1 )
01767         TT[j++] = T + i;
01768 
01769     MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 );
01770 
01771     MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) );
01772 
01773 #if defined(MBEDTLS_ECP_RESTARTABLE)
01774     if( rs_ctx != NULL && rs_ctx->rsm  != NULL )
01775         rs_ctx->rsm ->state = ecp_rsm_pre_add;
01776 
01777 add:
01778 #endif
01779     /*
01780      * Compute the remaining ones using the minimal number of additions
01781      * Be careful to update T[2^l] only after using it!
01782      */
01783     MBEDTLS_ECP_BUDGET( ( T_size - 1 ) * MBEDTLS_ECP_OPS_ADD );
01784 
01785     for( i = 1; i < T_size; i <<= 1 )
01786     {
01787         j = i;
01788         while( j-- )
01789             MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
01790     }
01791 
01792 #if defined(MBEDTLS_ECP_RESTARTABLE)
01793     if( rs_ctx != NULL && rs_ctx->rsm  != NULL )
01794         rs_ctx->rsm ->state = ecp_rsm_pre_norm_add;
01795 
01796 norm_add:
01797 #endif
01798     /*
01799      * Normalize final elements in T. Even though there are no holes now, we
01800      * still need the auxiliary array for homogeneity with the previous
01801      * call. Also, skip T[0] which is already normalised, being a copy of P.
01802      */
01803     for( j = 0; j + 1 < T_size; j++ )
01804         TT[j] = T + j + 1;
01805 
01806     MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 );
01807 
01808     MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) );
01809 
01810 cleanup:
01811 #if defined(MBEDTLS_ECP_RESTARTABLE)
01812     if( rs_ctx != NULL && rs_ctx->rsm  != NULL &&
01813         ret == MBEDTLS_ERR_ECP_IN_PROGRESS )
01814     {
01815         if( rs_ctx->rsm ->state == ecp_rsm_pre_dbl )
01816             rs_ctx->rsm ->i = j;
01817     }
01818 #endif
01819 
01820     return( ret );
01821 }
01822 
01823 /*
01824  * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
01825  *
01826  * See ecp_comb_recode_core() for background
01827  */
01828 static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
01829                             const mbedtls_ecp_point T[], unsigned char T_size,
01830                             unsigned char i )
01831 {
01832     int ret;
01833     unsigned char ii, j;
01834 
01835     /* Ignore the "sign" bit and scale down */
01836     ii =  ( i & 0x7Fu ) >> 1;
01837 
01838     /* Read the whole table to thwart cache-based timing attacks */
01839     for( j = 0; j < T_size; j++ )
01840     {
01841         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X , &T[j].X , j == ii ) );
01842         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y , &T[j].Y , j == ii ) );
01843     }
01844 
01845     /* Safely invert result if i is "negative" */
01846     MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
01847 
01848 cleanup:
01849     return( ret );
01850 }
01851 
01852 /*
01853  * Core multiplication algorithm for the (modified) comb method.
01854  * This part is actually common with the basic comb method (GECC 3.44)
01855  *
01856  * Cost: d A + d D + 1 R
01857  */
01858 static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
01859                               const mbedtls_ecp_point T[], unsigned char T_size,
01860                               const unsigned char x[], size_t d,
01861                               int (*f_rng)(void *, unsigned char *, size_t),
01862                               void *p_rng,
01863                               mbedtls_ecp_restart_ctx *rs_ctx )
01864 {
01865     int ret;
01866     mbedtls_ecp_point Txi;
01867     size_t i;
01868 
01869     mbedtls_ecp_point_init( &Txi );
01870 
01871 #if !defined(MBEDTLS_ECP_RESTARTABLE)
01872     (void) rs_ctx;
01873 #endif
01874 
01875 #if defined(MBEDTLS_ECP_RESTARTABLE)
01876     if( rs_ctx != NULL && rs_ctx->rsm  != NULL &&
01877         rs_ctx->rsm ->state != ecp_rsm_comb_core )
01878     {
01879         rs_ctx->rsm ->i = 0;
01880         rs_ctx->rsm ->state = ecp_rsm_comb_core;
01881     }
01882 
01883     /* new 'if' instead of nested for the sake of the 'else' branch */
01884     if( rs_ctx != NULL && rs_ctx->rsm  != NULL && rs_ctx->rsm ->i != 0 )
01885     {
01886         /* restore current index (R already pointing to rs_ctx->rsm->R) */
01887         i = rs_ctx->rsm ->i;
01888     }
01889     else
01890 #endif
01891     {
01892         /* Start with a non-zero point and randomize its coordinates */
01893         i = d;
01894         MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, T_size, x[i] ) );
01895         MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z , 1 ) );
01896         if( f_rng != 0 )
01897             MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
01898     }
01899 
01900     while( i != 0 )
01901     {
01902         MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD );
01903         --i;
01904 
01905         MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) );
01906         MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, T_size, x[i] ) );
01907         MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
01908     }
01909 
01910 cleanup:
01911 
01912     mbedtls_ecp_point_free( &Txi );
01913 
01914 #if defined(MBEDTLS_ECP_RESTARTABLE)
01915     if( rs_ctx != NULL && rs_ctx->rsm  != NULL &&
01916         ret == MBEDTLS_ERR_ECP_IN_PROGRESS )
01917     {
01918         rs_ctx->rsm ->i = i;
01919         /* no need to save R, already pointing to rs_ctx->rsm->R */
01920     }
01921 #endif
01922 
01923     return( ret );
01924 }
01925 
01926 /*
01927  * Recode the scalar to get constant-time comb multiplication
01928  *
01929  * As the actual scalar recoding needs an odd scalar as a starting point,
01930  * this wrapper ensures that by replacing m by N - m if necessary, and
01931  * informs the caller that the result of multiplication will be negated.
01932  *
01933  * This works because we only support large prime order for Short Weierstrass
01934  * curves, so N is always odd hence either m or N - m is.
01935  *
01936  * See ecp_comb_recode_core() for background.
01937  */
01938 static int ecp_comb_recode_scalar( const mbedtls_ecp_group *grp,
01939                                    const mbedtls_mpi *m,
01940                                    unsigned char k[COMB_MAX_D + 1],
01941                                    size_t d,
01942                                    unsigned char w,
01943                                    unsigned char *parity_trick )
01944 {
01945     int ret;
01946     mbedtls_mpi M, mm;
01947 
01948     mbedtls_mpi_init( &M );
01949     mbedtls_mpi_init( &mm );
01950 
01951     /* N is always odd (see above), just make extra sure */
01952     if( mbedtls_mpi_get_bit( &grp->N , 0 ) != 1 )
01953         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
01954 
01955     /* do we need the parity trick? */
01956     *parity_trick = ( mbedtls_mpi_get_bit( m, 0 ) == 0 );
01957 
01958     /* execute parity fix in constant time */
01959     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) );
01960     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N , m ) );
01961     MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, *parity_trick ) );
01962 
01963     /* actual scalar recoding */
01964     ecp_comb_recode_core( k, d, w, &M );
01965 
01966 cleanup:
01967     mbedtls_mpi_free( &mm );
01968     mbedtls_mpi_free( &M );
01969 
01970     return( ret );
01971 }
01972 
01973 /*
01974  * Perform comb multiplication (for short Weierstrass curves)
01975  * once the auxiliary table has been pre-computed.
01976  *
01977  * Scalar recoding may use a parity trick that makes us compute -m * P,
01978  * if that is the case we'll need to recover m * P at the end.
01979  */
01980 static int ecp_mul_comb_after_precomp( const mbedtls_ecp_group *grp,
01981                                 mbedtls_ecp_point *R,
01982                                 const mbedtls_mpi *m,
01983                                 const mbedtls_ecp_point *T,
01984                                 unsigned char T_size,
01985                                 unsigned char w,
01986                                 size_t d,
01987                                 int (*f_rng)(void *, unsigned char *, size_t),
01988                                 void *p_rng,
01989                                 mbedtls_ecp_restart_ctx *rs_ctx )
01990 {
01991     int ret;
01992     unsigned char parity_trick;
01993     unsigned char k[COMB_MAX_D + 1];
01994     mbedtls_ecp_point *RR = R;
01995 
01996 #if defined(MBEDTLS_ECP_RESTARTABLE)
01997     if( rs_ctx != NULL && rs_ctx->rsm  != NULL )
01998     {
01999         RR = &rs_ctx->rsm ->R;
02000 
02001         if( rs_ctx->rsm ->state == ecp_rsm_final_norm )
02002             goto final_norm;
02003     }
02004 #endif
02005 
02006     MBEDTLS_MPI_CHK( ecp_comb_recode_scalar( grp, m, k, d, w,
02007                                             &parity_trick ) );
02008     MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, RR, T, T_size, k, d,
02009                                         f_rng, p_rng, rs_ctx ) );
02010     MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, RR, parity_trick ) );
02011 
02012 #if defined(MBEDTLS_ECP_RESTARTABLE)
02013     if( rs_ctx != NULL && rs_ctx->rsm  != NULL )
02014         rs_ctx->rsm ->state = ecp_rsm_final_norm;
02015 
02016 final_norm:
02017 #endif
02018     MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV );
02019     MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, RR ) );
02020 
02021 #if defined(MBEDTLS_ECP_RESTARTABLE)
02022     if( rs_ctx != NULL && rs_ctx->rsm  != NULL )
02023         MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, RR ) );
02024 #endif
02025 
02026 cleanup:
02027     return( ret );
02028 }
02029 
02030 /*
02031  * Pick window size based on curve size and whether we optimize for base point
02032  */
02033 static unsigned char ecp_pick_window_size( const mbedtls_ecp_group *grp,
02034                                            unsigned char p_eq_g )
02035 {
02036     unsigned char w;
02037 
02038     /*
02039      * Minimize the number of multiplications, that is minimize
02040      * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
02041      * (see costs of the various parts, with 1S = 1M)
02042      */
02043     w = grp->nbits  >= 384 ? 5 : 4;
02044 
02045     /*
02046      * If P == G, pre-compute a bit more, since this may be re-used later.
02047      * Just adding one avoids upping the cost of the first mul too much,
02048      * and the memory cost too.
02049      */
02050     if( p_eq_g )
02051         w++;
02052 
02053     /*
02054      * Make sure w is within bounds.
02055      * (The last test is useful only for very small curves in the test suite.)
02056      */
02057 #if( MBEDTLS_ECP_WINDOW_SIZE < 6 )
02058     if( w > MBEDTLS_ECP_WINDOW_SIZE )
02059         w = MBEDTLS_ECP_WINDOW_SIZE;
02060 #endif
02061     if( w >= grp->nbits  )
02062         w = 2;
02063 
02064     return( w );
02065 }
02066 
02067 /*
02068  * Multiplication using the comb method - for curves in short Weierstrass form
02069  *
02070  * This function is mainly responsible for administrative work:
02071  * - managing the restart context if enabled
02072  * - managing the table of precomputed points (passed between the below two
02073  *   functions): allocation, computation, ownership tranfer, freeing.
02074  *
02075  * It delegates the actual arithmetic work to:
02076  *      ecp_precompute_comb() and ecp_mul_comb_with_precomp()
02077  *
02078  * See comments on ecp_comb_recode_core() regarding the computation strategy.
02079  */
02080 static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
02081                          const mbedtls_mpi *m, const mbedtls_ecp_point *P,
02082                          int (*f_rng)(void *, unsigned char *, size_t),
02083                          void *p_rng,
02084                          mbedtls_ecp_restart_ctx *rs_ctx )
02085 {
02086     int ret;
02087     unsigned char w, p_eq_g, i;
02088     size_t d;
02089     unsigned char T_size, T_ok;
02090     mbedtls_ecp_point *T;
02091 
02092     ECP_RS_ENTER( rsm );
02093 
02094     /* Is P the base point ? */
02095 #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
02096     p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y , &grp->G .Y  ) == 0 &&
02097                mbedtls_mpi_cmp_mpi( &P->X , &grp->G .X  ) == 0 );
02098 #else
02099     p_eq_g = 0;
02100 #endif
02101 
02102     /* Pick window size and deduce related sizes */
02103     w = ecp_pick_window_size( grp, p_eq_g );
02104     T_size = 1U << ( w - 1 );
02105     d = ( grp->nbits  + w - 1 ) / w;
02106 
02107     /* Pre-computed table: do we have it already for the base point? */
02108     if( p_eq_g && grp->T  != NULL )
02109     {
02110         /* second pointer to the same table, will be deleted on exit */
02111         T = grp->T ;
02112         T_ok = 1;
02113     }
02114     else
02115 #if defined(MBEDTLS_ECP_RESTARTABLE)
02116     /* Pre-computed table: do we have one in progress? complete? */
02117     if( rs_ctx != NULL && rs_ctx->rsm  != NULL && rs_ctx->rsm ->T != NULL )
02118     {
02119         /* transfer ownership of T from rsm to local function */
02120         T = rs_ctx->rsm ->T;
02121         rs_ctx->rsm ->T = NULL;
02122         rs_ctx->rsm ->T_size = 0;
02123 
02124         /* This effectively jumps to the call to mul_comb_after_precomp() */
02125         T_ok = rs_ctx->rsm ->state >= ecp_rsm_comb_core;
02126     }
02127     else
02128 #endif
02129     /* Allocate table if we didn't have any */
02130     {
02131         T = mbedtls_calloc( T_size, sizeof( mbedtls_ecp_point ) );
02132         if( T == NULL )
02133         {
02134             ret = MBEDTLS_ERR_ECP_ALLOC_FAILED;
02135             goto cleanup;
02136         }
02137 
02138         for( i = 0; i < T_size; i++ )
02139             mbedtls_ecp_point_init( &T[i] );
02140 
02141         T_ok = 0;
02142     }
02143 
02144     /* Compute table (or finish computing it) if not done already */
02145     if( !T_ok )
02146     {
02147         MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d, rs_ctx ) );
02148 
02149         if( p_eq_g )
02150         {
02151             /* almost transfer ownership of T to the group, but keep a copy of
02152              * the pointer to use for calling the next function more easily */
02153             grp->T  = T;
02154             grp->T_size  = T_size;
02155         }
02156     }
02157 
02158     /* Actual comb multiplication using precomputed points */
02159     MBEDTLS_MPI_CHK( ecp_mul_comb_after_precomp( grp, R, m,
02160                                                  T, T_size, w, d,
02161                                                  f_rng, p_rng, rs_ctx ) );
02162 
02163 cleanup:
02164 
02165     /* does T belong to the group? */
02166     if( T == grp->T  )
02167         T = NULL;
02168 
02169     /* does T belong to the restart context? */
02170 #if defined(MBEDTLS_ECP_RESTARTABLE)
02171     if( rs_ctx != NULL && rs_ctx->rsm  != NULL && ret == MBEDTLS_ERR_ECP_IN_PROGRESS && T != NULL )
02172     {
02173         /* transfer ownership of T from local function to rsm */
02174         rs_ctx->rsm ->T_size = T_size;
02175         rs_ctx->rsm ->T = T;
02176         T = NULL;
02177     }
02178 #endif
02179 
02180     /* did T belong to us? then let's destroy it! */
02181     if( T != NULL )
02182     {
02183         for( i = 0; i < T_size; i++ )
02184             mbedtls_ecp_point_free( &T[i] );
02185         mbedtls_free( T );
02186     }
02187 
02188     /* don't free R while in progress in case R == P */
02189 #if defined(MBEDTLS_ECP_RESTARTABLE)
02190     if( ret != MBEDTLS_ERR_ECP_IN_PROGRESS )
02191 #endif
02192     /* prevent caller from using invalid value */
02193     if( ret != 0 )
02194         mbedtls_ecp_point_free( R );
02195 
02196     ECP_RS_LEAVE( rsm );
02197 
02198     return( ret );
02199 }
02200 
02201 #endif /* ECP_SHORTWEIERSTRASS */
02202 
02203 #if defined(ECP_MONTGOMERY)
02204 /*
02205  * For Montgomery curves, we do all the internal arithmetic in projective
02206  * coordinates. Import/export of points uses only the x coordinates, which is
02207  * internaly represented as X / Z.
02208  *
02209  * For scalar multiplication, we'll use a Montgomery ladder.
02210  */
02211 
02212 /*
02213  * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
02214  * Cost: 1M + 1I
02215  */
02216 static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P )
02217 {
02218     int ret;
02219 
02220 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
02221     if( mbedtls_internal_ecp_grp_capable( grp ) )
02222         return( mbedtls_internal_ecp_normalize_mxz( grp, P ) );
02223 #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */
02224 
02225     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z , &P->Z , &grp->P  ) );
02226     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &P->X , &P->X , &P->Z  ) );
02227     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z , 1 ) );
02228 
02229 cleanup:
02230     return( ret );
02231 }
02232 
02233 /*
02234  * Randomize projective x/z coordinates:
02235  * (X, Z) -> (l X, l Z) for random l
02236  * This is sort of the reverse operation of ecp_normalize_mxz().
02237  *
02238  * This countermeasure was first suggested in [2].
02239  * Cost: 2M
02240  */
02241 static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P,
02242                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
02243 {
02244     int ret;
02245     mbedtls_mpi l;
02246     size_t p_size;
02247     int count = 0;
02248 
02249 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
02250     if( mbedtls_internal_ecp_grp_capable( grp ) )
02251         return( mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng );
02252 #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */
02253 
02254     p_size = ( grp->pbits  + 7 ) / 8;
02255     mbedtls_mpi_init( &l );
02256 
02257     /* Generate l such that 1 < l < p */
02258     do
02259     {
02260         MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
02261 
02262         while( mbedtls_mpi_cmp_mpi( &l, &grp->P  ) >= 0 )
02263             MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
02264 
02265         if( count++ > 10 )
02266             return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
02267     }
02268     while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
02269 
02270     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &P->X , &P->X , &l ) );
02271     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &P->Z , &P->Z , &l ) );
02272 
02273 cleanup:
02274     mbedtls_mpi_free( &l );
02275 
02276     return( ret );
02277 }
02278 
02279 /*
02280  * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
02281  * for Montgomery curves in x/z coordinates.
02282  *
02283  * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
02284  * with
02285  * d =  X1
02286  * P = (X2, Z2)
02287  * Q = (X3, Z3)
02288  * R = (X4, Z4)
02289  * S = (X5, Z5)
02290  * and eliminating temporary variables tO, ..., t4.
02291  *
02292  * Cost: 5M + 4S
02293  */
02294 static int ecp_double_add_mxz( const mbedtls_ecp_group *grp,
02295                                mbedtls_ecp_point *R, mbedtls_ecp_point *S,
02296                                const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q,
02297                                const mbedtls_mpi *d )
02298 {
02299     int ret;
02300     mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB;
02301 
02302 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
02303     if( mbedtls_internal_ecp_grp_capable( grp ) )
02304         return( mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d ) );
02305 #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */
02306 
02307     mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B );
02308     mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C );
02309     mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB );
02310 
02311     MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &A,    &P->X ,   &P->Z  ) );
02312     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &AA,   &A,      &A    ) );
02313     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &B,    &P->X ,   &P->Z  ) );
02314     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &BB,   &B,      &B    ) );
02315     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &E,    &AA,     &BB   ) );
02316     MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &C,    &Q->X ,   &Q->Z  ) );
02317     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &D,    &Q->X ,   &Q->Z  ) );
02318     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &DA,   &D,      &A    ) );
02319     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &CB,   &C,      &B    ) );
02320     MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X , &DA,     &CB   ) ); MOD_MUL( S->X  );
02321     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S->X , &S->X ,   &S->X  ) );
02322     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mod( grp, &S->Z , &DA,     &CB   ) );
02323     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S->Z , &S->Z ,   &S->Z  ) );
02324     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &S->Z , d,       &S->Z  ) );
02325     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &R->X , &AA,     &BB   ) );
02326     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &R->Z , &grp->A , &E    ) );
02327     MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &R->Z , &BB,     &R->Z  ) );
02328     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &R->Z , &E,      &R->Z  ) );
02329 
02330 cleanup:
02331     mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B );
02332     mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C );
02333     mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB );
02334 
02335     return( ret );
02336 }
02337 
02338 /*
02339  * Multiplication with Montgomery ladder in x/z coordinates,
02340  * for curves in Montgomery form
02341  */
02342 static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
02343                         const mbedtls_mpi *m, const mbedtls_ecp_point *P,
02344                         int (*f_rng)(void *, unsigned char *, size_t),
02345                         void *p_rng )
02346 {
02347     int ret;
02348     size_t i;
02349     unsigned char b;
02350     mbedtls_ecp_point RP;
02351     mbedtls_mpi PX;
02352 
02353     mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX );
02354 
02355     /* Save PX and read from P before writing to R, in case P == R */
02356     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X  ) );
02357     MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) );
02358 
02359     /* Set R to zero in modified x/z coordinates */
02360     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X , 1 ) );
02361     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z , 0 ) );
02362     mbedtls_mpi_free( &R->Y  );
02363 
02364     /* RP.X might be sligtly larger than P, so reduce it */
02365     MOD_ADD( RP.X  );
02366 
02367     /* Randomize coordinates of the starting point */
02368     if( f_rng != NULL )
02369         MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
02370 
02371     /* Loop invariant: R = result so far, RP = R + P */
02372     i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */
02373     while( i-- > 0 )
02374     {
02375         b = mbedtls_mpi_get_bit( m, i );
02376         /*
02377          *  if (b) R = 2R + P else R = 2R,
02378          * which is:
02379          *  if (b) double_add( RP, R, RP, R )
02380          *  else   double_add( R, RP, R, RP )
02381          * but using safe conditional swaps to avoid leaks
02382          */
02383         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X , &RP.X , b ) );
02384         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z , &RP.Z , b ) );
02385         MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
02386         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X , &RP.X , b ) );
02387         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z , &RP.Z , b ) );
02388     }
02389 
02390     MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) );
02391 
02392 cleanup:
02393     mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX );
02394 
02395     return( ret );
02396 }
02397 
02398 #endif /* ECP_MONTGOMERY */
02399 
02400 /*
02401  * Restartable multiplication R = m * P
02402  */
02403 int mbedtls_ecp_mul_restartable( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
02404              const mbedtls_mpi *m, const mbedtls_ecp_point *P,
02405              int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,
02406              mbedtls_ecp_restart_ctx *rs_ctx )
02407 {
02408     int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
02409 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
02410     char is_grp_capable = 0;
02411 #endif
02412     ECP_VALIDATE_RET( grp != NULL );
02413     ECP_VALIDATE_RET( R   != NULL );
02414     ECP_VALIDATE_RET( m   != NULL );
02415     ECP_VALIDATE_RET( P   != NULL );
02416 
02417 #if defined(MBEDTLS_ECP_RESTARTABLE)
02418     /* reset ops count for this call if top-level */
02419     if( rs_ctx != NULL && rs_ctx->depth ++ == 0 )
02420         rs_ctx->ops_done  = 0;
02421 #endif
02422 
02423 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
02424     if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) )
02425         MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );
02426 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
02427 
02428 #if defined(MBEDTLS_ECP_RESTARTABLE)
02429     /* skip argument check when restarting */
02430     if( rs_ctx == NULL || rs_ctx->rsm  == NULL )
02431 #endif
02432     {
02433         /* check_privkey is free */
02434         MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_CHK );
02435 
02436         /* Common sanity checks */
02437         MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( grp, m ) );
02438         MBEDTLS_MPI_CHK( mbedtls_ecp_check_pubkey( grp, P ) );
02439     }
02440 
02441     ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
02442 #if defined(ECP_MONTGOMERY)
02443     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )
02444         MBEDTLS_MPI_CHK( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) );
02445 #endif
02446 #if defined(ECP_SHORTWEIERSTRASS)
02447     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
02448         MBEDTLS_MPI_CHK( ecp_mul_comb( grp, R, m, P, f_rng, p_rng, rs_ctx ) );
02449 #endif
02450 
02451 cleanup:
02452 
02453 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
02454     if( is_grp_capable )
02455         mbedtls_internal_ecp_free( grp );
02456 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
02457 
02458 #if defined(MBEDTLS_ECP_RESTARTABLE)
02459     if( rs_ctx != NULL )
02460         rs_ctx->depth --;
02461 #endif
02462 
02463     return( ret );
02464 }
02465 
02466 /*
02467  * Multiplication R = m * P
02468  */
02469 int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
02470              const mbedtls_mpi *m, const mbedtls_ecp_point *P,
02471              int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
02472 {
02473     ECP_VALIDATE_RET( grp != NULL );
02474     ECP_VALIDATE_RET( R   != NULL );
02475     ECP_VALIDATE_RET( m   != NULL );
02476     ECP_VALIDATE_RET( P   != NULL );
02477     return( mbedtls_ecp_mul_restartable( grp, R, m, P, f_rng, p_rng, NULL ) );
02478 }
02479 
02480 #if defined(ECP_SHORTWEIERSTRASS)
02481 /*
02482  * Check that an affine point is valid as a public key,
02483  * short weierstrass curves (SEC1 3.2.3.1)
02484  */
02485 static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
02486 {
02487     int ret;
02488     mbedtls_mpi YY, RHS;
02489 
02490     /* pt coordinates must be normalized for our checks */
02491     if( mbedtls_mpi_cmp_int( &pt->X , 0 ) < 0 ||
02492         mbedtls_mpi_cmp_int( &pt->Y , 0 ) < 0 ||
02493         mbedtls_mpi_cmp_mpi( &pt->X , &grp->P  ) >= 0 ||
02494         mbedtls_mpi_cmp_mpi( &pt->Y , &grp->P  ) >= 0 )
02495         return( MBEDTLS_ERR_ECP_INVALID_KEY );
02496 
02497     mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS );
02498 
02499     /*
02500      * YY = Y^2
02501      * RHS = X (X^2 + A) + B = X^3 + A X + B
02502      */
02503     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &YY,  &pt->Y ,   &pt->Y   ) );
02504     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &RHS, &pt->X ,   &pt->X   ) );
02505 
02506     /* Special case for A = -3 */
02507     if( grp->A .p  == NULL )
02508     {
02509         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3       ) );  MOD_SUB( RHS );
02510     }
02511     else
02512     {
02513         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &RHS, &RHS, &grp->A  ) );
02514     }
02515 
02516     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mod( grp, &RHS, &RHS,     &pt->X   ) );
02517     MBEDTLS_MPI_CHK( mbedtls_mpi_add_mod( grp, &RHS, &RHS,     &grp->B  ) );
02518 
02519     if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 )
02520         ret = MBEDTLS_ERR_ECP_INVALID_KEY;
02521 
02522 cleanup:
02523 
02524     mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS );
02525 
02526     return( ret );
02527 }
02528 #endif /* ECP_SHORTWEIERSTRASS */
02529 
02530 /*
02531  * R = m * P with shortcuts for m == 1 and m == -1
02532  * NOT constant-time - ONLY for short Weierstrass!
02533  */
02534 static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp,
02535                                       mbedtls_ecp_point *R,
02536                                       const mbedtls_mpi *m,
02537                                       const mbedtls_ecp_point *P,
02538                                       mbedtls_ecp_restart_ctx *rs_ctx )
02539 {
02540     int ret;
02541 
02542     if( mbedtls_mpi_cmp_int( m, 1 ) == 0 )
02543     {
02544         MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
02545     }
02546     else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 )
02547     {
02548         MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
02549         if( mbedtls_mpi_cmp_int( &R->Y , 0 ) != 0 )
02550             MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y , &grp->P , &R->Y  ) );
02551     }
02552     else
02553     {
02554         MBEDTLS_MPI_CHK( mbedtls_ecp_mul_restartable( grp, R, m, P,
02555                                                       NULL, NULL, rs_ctx ) );
02556     }
02557 
02558 cleanup:
02559     return( ret );
02560 }
02561 
02562 /*
02563  * Restartable linear combination
02564  * NOT constant-time
02565  */
02566 int mbedtls_ecp_muladd_restartable(
02567              mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
02568              const mbedtls_mpi *m, const mbedtls_ecp_point *P,
02569              const mbedtls_mpi *n, const mbedtls_ecp_point *Q,
02570              mbedtls_ecp_restart_ctx *rs_ctx )
02571 {
02572     int ret;
02573     mbedtls_ecp_point mP;
02574     mbedtls_ecp_point *pmP = &mP;
02575     mbedtls_ecp_point *pR = R;
02576 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
02577     char is_grp_capable = 0;
02578 #endif
02579     ECP_VALIDATE_RET( grp != NULL );
02580     ECP_VALIDATE_RET( R   != NULL );
02581     ECP_VALIDATE_RET( m   != NULL );
02582     ECP_VALIDATE_RET( P   != NULL );
02583     ECP_VALIDATE_RET( n   != NULL );
02584     ECP_VALIDATE_RET( Q   != NULL );
02585 
02586     if( mbedtls_ecp_get_type( grp ) != MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
02587         return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
02588 
02589     mbedtls_ecp_point_init( &mP );
02590 
02591     ECP_RS_ENTER( ma );
02592 
02593 #if defined(MBEDTLS_ECP_RESTARTABLE)
02594     if( rs_ctx != NULL && rs_ctx->ma  != NULL )
02595     {
02596         /* redirect intermediate results to restart context */
02597         pmP = &rs_ctx->ma ->mP;
02598         pR  = &rs_ctx->ma ->R;
02599 
02600         /* jump to next operation */
02601         if( rs_ctx->ma ->state == ecp_rsma_mul2 )
02602             goto mul2;
02603         if( rs_ctx->ma ->state == ecp_rsma_add )
02604             goto add;
02605         if( rs_ctx->ma ->state == ecp_rsma_norm )
02606             goto norm;
02607     }
02608 #endif /* MBEDTLS_ECP_RESTARTABLE */
02609 
02610     MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pmP, m, P, rs_ctx ) );
02611 #if defined(MBEDTLS_ECP_RESTARTABLE)
02612     if( rs_ctx != NULL && rs_ctx->ma  != NULL )
02613         rs_ctx->ma ->state = ecp_rsma_mul2;
02614 
02615 mul2:
02616 #endif
02617     MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pR,  n, Q, rs_ctx ) );
02618 
02619 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
02620     if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) )
02621         MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );
02622 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
02623 
02624 #if defined(MBEDTLS_ECP_RESTARTABLE)
02625     if( rs_ctx != NULL && rs_ctx->ma  != NULL )
02626         rs_ctx->ma ->state = ecp_rsma_add;
02627 
02628 add:
02629 #endif
02630     MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_ADD );
02631     MBEDTLS_MPI_CHK( ecp_add_mixed( grp, pR, pmP, pR ) );
02632 #if defined(MBEDTLS_ECP_RESTARTABLE)
02633     if( rs_ctx != NULL && rs_ctx->ma  != NULL )
02634         rs_ctx->ma ->state = ecp_rsma_norm;
02635 
02636 norm:
02637 #endif
02638     MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV );
02639     MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, pR ) );
02640 
02641 #if defined(MBEDTLS_ECP_RESTARTABLE)
02642     if( rs_ctx != NULL && rs_ctx->ma  != NULL )
02643         MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, pR ) );
02644 #endif
02645 
02646 cleanup:
02647 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
02648     if( is_grp_capable )
02649         mbedtls_internal_ecp_free( grp );
02650 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
02651 
02652     mbedtls_ecp_point_free( &mP );
02653 
02654     ECP_RS_LEAVE( ma );
02655 
02656     return( ret );
02657 }
02658 
02659 /*
02660  * Linear combination
02661  * NOT constant-time
02662  */
02663 int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
02664              const mbedtls_mpi *m, const mbedtls_ecp_point *P,
02665              const mbedtls_mpi *n, const mbedtls_ecp_point *Q )
02666 {
02667     ECP_VALIDATE_RET( grp != NULL );
02668     ECP_VALIDATE_RET( R   != NULL );
02669     ECP_VALIDATE_RET( m   != NULL );
02670     ECP_VALIDATE_RET( P   != NULL );
02671     ECP_VALIDATE_RET( n   != NULL );
02672     ECP_VALIDATE_RET( Q   != NULL );
02673     return( mbedtls_ecp_muladd_restartable( grp, R, m, P, n, Q, NULL ) );
02674 }
02675 
02676 #if defined(ECP_MONTGOMERY)
02677 /*
02678  * Check validity of a public key for Montgomery curves with x-only schemes
02679  */
02680 static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
02681 {
02682     /* [Curve25519 p. 5] Just check X is the correct number of bytes */
02683     /* Allow any public value, if it's too big then we'll just reduce it mod p
02684      * (RFC 7748 sec. 5 para. 3). */
02685     if( mbedtls_mpi_size( &pt->X  ) > ( grp->nbits  + 7 ) / 8 )
02686         return( MBEDTLS_ERR_ECP_INVALID_KEY );
02687 
02688     return( 0 );
02689 }
02690 #endif /* ECP_MONTGOMERY */
02691 
02692 /*
02693  * Check that a point is valid as a public key
02694  */
02695 int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp,
02696                               const mbedtls_ecp_point *pt )
02697 {
02698     ECP_VALIDATE_RET( grp != NULL );
02699     ECP_VALIDATE_RET( pt  != NULL );
02700 
02701     /* Must use affine coordinates */
02702     if( mbedtls_mpi_cmp_int( &pt->Z , 1 ) != 0 )
02703         return( MBEDTLS_ERR_ECP_INVALID_KEY );
02704 
02705 #if defined(ECP_MONTGOMERY)
02706     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )
02707         return( ecp_check_pubkey_mx( grp, pt ) );
02708 #endif
02709 #if defined(ECP_SHORTWEIERSTRASS)
02710     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
02711         return( ecp_check_pubkey_sw( grp, pt ) );
02712 #endif
02713     return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
02714 }
02715 
02716 /*
02717  * Check that an mbedtls_mpi is valid as a private key
02718  */
02719 int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp,
02720                                const mbedtls_mpi *d )
02721 {
02722     ECP_VALIDATE_RET( grp != NULL );
02723     ECP_VALIDATE_RET( d   != NULL );
02724 
02725 #if defined(ECP_MONTGOMERY)
02726     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )
02727     {
02728         /* see RFC 7748 sec. 5 para. 5 */
02729         if( mbedtls_mpi_get_bit( d, 0 ) != 0 ||
02730             mbedtls_mpi_get_bit( d, 1 ) != 0 ||
02731             mbedtls_mpi_bitlen( d ) - 1 != grp->nbits  ) /* mbedtls_mpi_bitlen is one-based! */
02732             return( MBEDTLS_ERR_ECP_INVALID_KEY );
02733 
02734         /* see [Curve25519] page 5 */
02735         if( grp->nbits  == 254 && mbedtls_mpi_get_bit( d, 2 ) != 0 )
02736             return( MBEDTLS_ERR_ECP_INVALID_KEY );
02737 
02738         return( 0 );
02739     }
02740 #endif /* ECP_MONTGOMERY */
02741 #if defined(ECP_SHORTWEIERSTRASS)
02742     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
02743     {
02744         /* see SEC1 3.2 */
02745         if( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
02746             mbedtls_mpi_cmp_mpi( d, &grp->N  ) >= 0 )
02747             return( MBEDTLS_ERR_ECP_INVALID_KEY );
02748         else
02749             return( 0 );
02750     }
02751 #endif /* ECP_SHORTWEIERSTRASS */
02752 
02753     return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
02754 }
02755 
02756 /*
02757  * Generate a private key
02758  */
02759 int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp,
02760                      mbedtls_mpi *d,
02761                      int (*f_rng)(void *, unsigned char *, size_t),
02762                      void *p_rng )
02763 {
02764     int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
02765     size_t n_size;
02766 
02767     ECP_VALIDATE_RET( grp   != NULL );
02768     ECP_VALIDATE_RET( d     != NULL );
02769     ECP_VALIDATE_RET( f_rng != NULL );
02770 
02771     n_size = ( grp->nbits  + 7 ) / 8;
02772 
02773 #if defined(ECP_MONTGOMERY)
02774     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )
02775     {
02776         /* [M225] page 5 */
02777         size_t b;
02778 
02779         do {
02780             MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
02781         } while( mbedtls_mpi_bitlen( d ) == 0);
02782 
02783         /* Make sure the most significant bit is nbits */
02784         b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */
02785         if( b > grp->nbits  )
02786             MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits  ) );
02787         else
02788             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits , 1 ) );
02789 
02790         /* Make sure the last two bits are unset for Curve448, three bits for
02791            Curve25519 */
02792         MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) );
02793         MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) );
02794         if( grp->nbits  == 254 )
02795         {
02796             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) );
02797         }
02798     }
02799 #endif /* ECP_MONTGOMERY */
02800 
02801 #if defined(ECP_SHORTWEIERSTRASS)
02802     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
02803     {
02804         /* SEC1 3.2.1: Generate d such that 1 <= n < N */
02805         int count = 0;
02806 
02807         /*
02808          * Match the procedure given in RFC 6979 (deterministic ECDSA):
02809          * - use the same byte ordering;
02810          * - keep the leftmost nbits bits of the generated octet string;
02811          * - try until result is in the desired range.
02812          * This also avoids any biais, which is especially important for ECDSA.
02813          */
02814         do
02815         {
02816             MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
02817             MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits  ) );
02818 
02819             /*
02820              * Each try has at worst a probability 1/2 of failing (the msb has
02821              * a probability 1/2 of being 0, and then the result will be < N),
02822              * so after 30 tries failure probability is a most 2**(-30).
02823              *
02824              * For most curves, 1 try is enough with overwhelming probability,
02825              * since N starts with a lot of 1s in binary, but some curves
02826              * such as secp224k1 are actually very close to the worst case.
02827              */
02828             if( ++count > 30 )
02829                 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
02830         }
02831         while( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
02832                mbedtls_mpi_cmp_mpi( d, &grp->N  ) >= 0 );
02833     }
02834 #endif /* ECP_SHORTWEIERSTRASS */
02835 
02836 cleanup:
02837     return( ret );
02838 }
02839 
02840 /*
02841  * Generate a keypair with configurable base point
02842  */
02843 int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp,
02844                      const mbedtls_ecp_point *G,
02845                      mbedtls_mpi *d, mbedtls_ecp_point *Q,
02846                      int (*f_rng)(void *, unsigned char *, size_t),
02847                      void *p_rng )
02848 {
02849     int ret;
02850     ECP_VALIDATE_RET( grp   != NULL );
02851     ECP_VALIDATE_RET( d     != NULL );
02852     ECP_VALIDATE_RET( G     != NULL );
02853     ECP_VALIDATE_RET( Q     != NULL );
02854     ECP_VALIDATE_RET( f_rng != NULL );
02855 
02856     MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, d, f_rng, p_rng ) );
02857     MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) );
02858 
02859 cleanup:
02860     return( ret );
02861 }
02862 
02863 /*
02864  * Generate key pair, wrapper for conventional base point
02865  */
02866 int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp,
02867                              mbedtls_mpi *d, mbedtls_ecp_point *Q,
02868                              int (*f_rng)(void *, unsigned char *, size_t),
02869                              void *p_rng )
02870 {
02871     ECP_VALIDATE_RET( grp   != NULL );
02872     ECP_VALIDATE_RET( d     != NULL );
02873     ECP_VALIDATE_RET( Q     != NULL );
02874     ECP_VALIDATE_RET( f_rng != NULL );
02875 
02876     return( mbedtls_ecp_gen_keypair_base( grp, &grp->G , d, Q, f_rng, p_rng ) );
02877 }
02878 
02879 /*
02880  * Generate a keypair, prettier wrapper
02881  */
02882 int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
02883                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
02884 {
02885     int ret;
02886     ECP_VALIDATE_RET( key   != NULL );
02887     ECP_VALIDATE_RET( f_rng != NULL );
02888 
02889     if( ( ret = mbedtls_ecp_group_load( &key->grp , grp_id ) ) != 0 )
02890         return( ret );
02891 
02892     return( mbedtls_ecp_gen_keypair( &key->grp , &key->d , &key->Q , f_rng, p_rng ) );
02893 }
02894 
02895 #define ECP_CURVE25519_KEY_SIZE 32
02896 /*
02897  * Read a private key.
02898  */
02899 int mbedtls_ecp_read_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
02900                           const unsigned char *buf, size_t buflen )
02901 {
02902     int ret = 0;
02903 
02904     ECP_VALIDATE_RET( key  != NULL );
02905     ECP_VALIDATE_RET( buf  != NULL );
02906 
02907     if( ( ret = mbedtls_ecp_group_load( &key->grp , grp_id ) ) != 0 )
02908         return( ret );
02909 
02910     ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
02911 
02912 #if defined(ECP_MONTGOMERY)
02913     if( mbedtls_ecp_get_type( &key->grp  ) == MBEDTLS_ECP_TYPE_MONTGOMERY )
02914     {
02915         /*
02916          * If it is Curve25519 curve then mask the key as mandated by RFC7748
02917          */
02918         if( grp_id == MBEDTLS_ECP_DP_CURVE25519 )
02919         {
02920             if( buflen != ECP_CURVE25519_KEY_SIZE )
02921                 return MBEDTLS_ERR_ECP_INVALID_KEY;
02922 
02923             MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary_le( &key->d , buf, buflen ) );
02924 
02925             /* Set the three least significant bits to 0 */
02926             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d , 0, 0 ) );
02927             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d , 1, 0 ) );
02928             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d , 2, 0 ) );
02929 
02930             /* Set the most significant bit to 0 */
02931             MBEDTLS_MPI_CHK(
02932                     mbedtls_mpi_set_bit( &key->d ,
02933                                          ECP_CURVE25519_KEY_SIZE * 8 - 1, 0 )
02934                     );
02935 
02936             /* Set the second most significant bit to 1 */
02937             MBEDTLS_MPI_CHK(
02938                     mbedtls_mpi_set_bit( &key->d ,
02939                                          ECP_CURVE25519_KEY_SIZE * 8 - 2, 1 )
02940                     );
02941         }
02942         else
02943             ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
02944     }
02945 
02946 #endif
02947 #if defined(ECP_SHORTWEIERSTRASS)
02948     if( mbedtls_ecp_get_type( &key->grp  ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )
02949     {
02950         MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &key->d , buf, buflen ) );
02951 
02952         MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( &key->grp , &key->d  ) );
02953     }
02954 
02955 #endif
02956 cleanup:
02957 
02958     if( ret != 0 )
02959         mbedtls_mpi_free( &key->d  );
02960 
02961     return( ret );
02962 }
02963 
02964 /*
02965  * Check a public-private key pair
02966  */
02967 int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv )
02968 {
02969     int ret;
02970     mbedtls_ecp_point Q;
02971     mbedtls_ecp_group grp;
02972     ECP_VALIDATE_RET( pub != NULL );
02973     ECP_VALIDATE_RET( prv != NULL );
02974 
02975     if( pub->grp .id  == MBEDTLS_ECP_DP_NONE ||
02976         pub->grp .id  != prv->grp .id  ||
02977         mbedtls_mpi_cmp_mpi( &pub->Q .X , &prv->Q .X  ) ||
02978         mbedtls_mpi_cmp_mpi( &pub->Q .Y , &prv->Q .Y  ) ||
02979         mbedtls_mpi_cmp_mpi( &pub->Q .Z , &prv->Q .Z  ) )
02980     {
02981         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
02982     }
02983 
02984     mbedtls_ecp_point_init( &Q );
02985     mbedtls_ecp_group_init( &grp );
02986 
02987     /* mbedtls_ecp_mul() needs a non-const group... */
02988     mbedtls_ecp_group_copy( &grp, &prv->grp  );
02989 
02990     /* Also checks d is valid */
02991     MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d , &prv->grp .G , NULL, NULL ) );
02992 
02993     if( mbedtls_mpi_cmp_mpi( &Q.X , &prv->Q .X  ) ||
02994         mbedtls_mpi_cmp_mpi( &Q.Y , &prv->Q .Y  ) ||
02995         mbedtls_mpi_cmp_mpi( &Q.Z , &prv->Q .Z  ) )
02996     {
02997         ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
02998         goto cleanup;
02999     }
03000 
03001 cleanup:
03002     mbedtls_ecp_point_free( &Q );
03003     mbedtls_ecp_group_free( &grp );
03004 
03005     return( ret );
03006 }
03007 
03008 #if defined(MBEDTLS_SELF_TEST)
03009 
03010 /*
03011  * Checkup routine
03012  */
03013 int mbedtls_ecp_self_test( int verbose )
03014 {
03015     int ret;
03016     size_t i;
03017     mbedtls_ecp_group grp;
03018     mbedtls_ecp_point R, P;
03019     mbedtls_mpi m;
03020     unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
03021     /* exponents especially adapted for secp192r1 */
03022     const char *exponents[] =
03023     {
03024         "000000000000000000000000000000000000000000000001", /* one */
03025         "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */
03026         "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
03027         "400000000000000000000000000000000000000000000000", /* one and zeros */
03028         "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
03029         "555555555555555555555555555555555555555555555555", /* 101010... */
03030     };
03031 
03032     mbedtls_ecp_group_init( &grp );
03033     mbedtls_ecp_point_init( &R );
03034     mbedtls_ecp_point_init( &P );
03035     mbedtls_mpi_init( &m );
03036 
03037     /* Use secp192r1 if available, or any available curve */
03038 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
03039     MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) );
03040 #else
03041     MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) );
03042 #endif
03043 
03044     if( verbose != 0 )
03045         mbedtls_printf( "  ECP test #1 (constant op_count, base point G): " );
03046 
03047     /* Do a dummy multiplication first to trigger precomputation */
03048     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) );
03049     MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G , NULL, NULL ) );
03050 
03051     add_count = 0;
03052     dbl_count = 0;
03053     mul_count = 0;
03054     MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
03055     MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G , NULL, NULL ) );
03056 
03057     for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
03058     {
03059         add_c_prev = add_count;
03060         dbl_c_prev = dbl_count;
03061         mul_c_prev = mul_count;
03062         add_count = 0;
03063         dbl_count = 0;
03064         mul_count = 0;
03065 
03066         MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
03067         MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G , NULL, NULL ) );
03068 
03069         if( add_count != add_c_prev ||
03070             dbl_count != dbl_c_prev ||
03071             mul_count != mul_c_prev )
03072         {
03073             if( verbose != 0 )
03074                 mbedtls_printf( "failed (%u)\n", (unsigned int) i );
03075 
03076             ret = 1;
03077             goto cleanup;
03078         }
03079     }
03080 
03081     if( verbose != 0 )
03082         mbedtls_printf( "passed\n" );
03083 
03084     if( verbose != 0 )
03085         mbedtls_printf( "  ECP test #2 (constant op_count, other point): " );
03086     /* We computed P = 2G last time, use it */
03087 
03088     add_count = 0;
03089     dbl_count = 0;
03090     mul_count = 0;
03091     MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
03092     MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
03093 
03094     for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
03095     {
03096         add_c_prev = add_count;
03097         dbl_c_prev = dbl_count;
03098         mul_c_prev = mul_count;
03099         add_count = 0;
03100         dbl_count = 0;
03101         mul_count = 0;
03102 
03103         MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
03104         MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
03105 
03106         if( add_count != add_c_prev ||
03107             dbl_count != dbl_c_prev ||
03108             mul_count != mul_c_prev )
03109         {
03110             if( verbose != 0 )
03111                 mbedtls_printf( "failed (%u)\n", (unsigned int) i );
03112 
03113             ret = 1;
03114             goto cleanup;
03115         }
03116     }
03117 
03118     if( verbose != 0 )
03119         mbedtls_printf( "passed\n" );
03120 
03121 cleanup:
03122 
03123     if( ret < 0 && verbose != 0 )
03124         mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
03125 
03126     mbedtls_ecp_group_free( &grp );
03127     mbedtls_ecp_point_free( &R );
03128     mbedtls_ecp_point_free( &P );
03129     mbedtls_mpi_free( &m );
03130 
03131     if( verbose != 0 )
03132         mbedtls_printf( "\n" );
03133 
03134     return( ret );
03135 }
03136 
03137 #endif /* MBEDTLS_SELF_TEST */
03138 
03139 #endif /* !MBEDTLS_ECP_ALT */
03140 
03141 #endif /* MBEDTLS_ECP_C */