git.sur5r.net Git - freertos/blob - FreeRTOS-Labs/Source/mbedtls/library/ecp.c

   1 /*\r
   2  *  Elliptic curves over GF(p): generic functions\r
   3  *\r
   4  *  Copyright (C) 2006-2015, ARM Limited, All Rights Reserved\r
   5  *  SPDX-License-Identifier: Apache-2.0\r
   6  *\r
   7  *  Licensed under the Apache License, Version 2.0 (the "License"); you may\r
   8  *  not use this file except in compliance with the License.\r
   9  *  You may obtain a copy of the License at\r
  10  *\r
  11  *  http://www.apache.org/licenses/LICENSE-2.0\r
  12  *\r
  13  *  Unless required by applicable law or agreed to in writing, software\r
  14  *  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT\r
  15  *  WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  16  *  See the License for the specific language governing permissions and\r
  17  *  limitations under the License.\r
  18  *\r
  19  *  This file is part of mbed TLS (https://tls.mbed.org)\r
  20  */\r
  21 \r
  22 /*\r
  23  * References:\r
  24  *\r
  25  * SEC1 http://www.secg.org/index.php?action=secg,docs_secg\r
  26  * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone\r
  27  * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf\r
  28  * RFC 4492 for the related TLS structures and constants\r
  29  * RFC 7748 for the Curve448 and Curve25519 curve definitions\r
  30  *\r
  31  * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf\r
  32  *\r
  33  * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis\r
  34  *     for elliptic curve cryptosystems. In : Cryptographic Hardware and\r
  35  *     Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.\r
  36  *     <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>\r
  37  *\r
  38  * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to\r
  39  *     render ECC resistant against Side Channel Attacks. IACR Cryptology\r
  40  *     ePrint Archive, 2004, vol. 2004, p. 342.\r
  41  *     <http://eprint.iacr.org/2004/342.pdf>\r
  42  */\r
  43 \r
  44 #if !defined(MBEDTLS_CONFIG_FILE)\r
  45 #include "mbedtls/config.h"\r
  46 #else\r
  47 #include MBEDTLS_CONFIG_FILE\r
  48 #endif\r
  49 \r
  50 /**\r
  51  * \brief Function level alternative implementation.\r
  52  *\r
  53  * The MBEDTLS_ECP_INTERNAL_ALT macro enables alternative implementations to\r
  54  * replace certain functions in this module. The alternative implementations are\r
  55  * typically hardware accelerators and need to activate the hardware before the\r
  56  * computation starts and deactivate it after it finishes. The\r
  57  * mbedtls_internal_ecp_init() and mbedtls_internal_ecp_free() functions serve\r
  58  * this purpose.\r
  59  *\r
  60  * To preserve the correct functionality the following conditions must hold:\r
  61  *\r
  62  * - The alternative implementation must be activated by\r
  63  *   mbedtls_internal_ecp_init() before any of the replaceable functions is\r
  64  *   called.\r
  65  * - mbedtls_internal_ecp_free() must \b only be called when the alternative\r
  66  *   implementation is activated.\r
  67  * - mbedtls_internal_ecp_init() must \b not be called when the alternative\r
  68  *   implementation is activated.\r
  69  * - Public functions must not return while the alternative implementation is\r
  70  *   activated.\r
  71  * - Replaceable functions are guarded by \c MBEDTLS_ECP_XXX_ALT macros and\r
  72  *   before calling them an \code if( mbedtls_internal_ecp_grp_capable( grp ) )\r
  73  *   \endcode ensures that the alternative implementation supports the current\r
  74  *   group.\r
  75  */\r
  76 #if defined(MBEDTLS_ECP_INTERNAL_ALT)\r
  77 #endif\r
  78 \r
  79 #if defined(MBEDTLS_ECP_C)\r
  80 \r
  81 #include "mbedtls/ecp.h"\r
  82 #include "mbedtls/threading.h"\r
  83 #include "mbedtls/platform_util.h"\r
  84 \r
  85 #include <string.h>\r
  86 \r
  87 #if !defined(MBEDTLS_ECP_ALT)\r
  88 \r
  89 /* Parameter validation macros based on platform_util.h */\r
  90 #define ECP_VALIDATE_RET( cond )    \\r
  91     MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_ECP_BAD_INPUT_DATA )\r
  92 #define ECP_VALIDATE( cond )        \\r
  93     MBEDTLS_INTERNAL_VALIDATE( cond )\r
  94 \r
  95 #if defined(MBEDTLS_PLATFORM_C)\r
  96 #include "mbedtls/platform.h"\r
  97 #else\r
  98 #include <stdlib.h>\r
  99 #include <stdio.h>\r
 100 #define mbedtls_printf     printf\r
 101 #define mbedtls_calloc    calloc\r
 102 #define mbedtls_free       free\r
 103 #endif\r
 104 \r
 105 #include "mbedtls/ecp_internal.h"\r
 106 \r
 107 #if ( defined(__ARMCC_VERSION) || defined(_MSC_VER) ) && \\r
 108     !defined(inline) && !defined(__cplusplus)\r
 109 #define inline __inline\r
 110 #endif\r
 111 \r
 112 #if defined(MBEDTLS_SELF_TEST)\r
 113 /*\r
 114  * Counts of point addition and doubling, and field multiplications.\r
 115  * Used to test resistance of point multiplication to simple timing attacks.\r
 116  */\r
 117 static unsigned long add_count, dbl_count, mul_count;\r
 118 #endif\r
 119 \r
 120 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
 121 /*\r
 122  * Maximum number of "basic operations" to be done in a row.\r
 123  *\r
 124  * Default value 0 means that ECC operations will not yield.\r
 125  * Note that regardless of the value of ecp_max_ops, always at\r
 126  * least one step is performed before yielding.\r
 127  *\r
 128  * Setting ecp_max_ops=1 can be suitable for testing purposes\r
 129  * as it will interrupt computation at all possible points.\r
 130  */\r
 131 static unsigned ecp_max_ops = 0;\r
 132 \r
 133 /*\r
 134  * Set ecp_max_ops\r
 135  */\r
 136 void mbedtls_ecp_set_max_ops( unsigned max_ops )\r
 137 {\r
 138     ecp_max_ops = max_ops;\r
 139 }\r
 140 \r
 141 /*\r
 142  * Check if restart is enabled\r
 143  */\r
 144 int mbedtls_ecp_restart_is_enabled( void )\r
 145 {\r
 146     return( ecp_max_ops != 0 );\r
 147 }\r
 148 \r
 149 /*\r
 150  * Restart sub-context for ecp_mul_comb()\r
 151  */\r
 152 struct mbedtls_ecp_restart_mul\r
 153 {\r
 154     mbedtls_ecp_point R;    /* current intermediate result                  */\r
 155     size_t i;               /* current index in various loops, 0 outside    */\r
 156     mbedtls_ecp_point *T;   /* table for precomputed points                 */\r
 157     unsigned char T_size;   /* number of points in table T                  */\r
 158     enum {                  /* what were we doing last time we returned?    */\r
 159         ecp_rsm_init = 0,       /* nothing so far, dummy initial state      */\r
 160         ecp_rsm_pre_dbl,        /* precompute 2^n multiples                 */\r
 161         ecp_rsm_pre_norm_dbl,   /* normalize precomputed 2^n multiples      */\r
 162         ecp_rsm_pre_add,        /* precompute remaining points by adding    */\r
 163         ecp_rsm_pre_norm_add,   /* normalize all precomputed points         */\r
 164         ecp_rsm_comb_core,      /* ecp_mul_comb_core()                      */\r
 165         ecp_rsm_final_norm,     /* do the final normalization               */\r
 166     } state;\r
 167 };\r
 168 \r
 169 /*\r
 170  * Init restart_mul sub-context\r
 171  */\r
 172 static void ecp_restart_rsm_init( mbedtls_ecp_restart_mul_ctx *ctx )\r
 173 {\r
 174     mbedtls_ecp_point_init( &ctx->R );\r
 175     ctx->i = 0;\r
 176     ctx->T = NULL;\r
 177     ctx->T_size = 0;\r
 178     ctx->state = ecp_rsm_init;\r
 179 }\r
 180 \r
 181 /*\r
 182  * Free the components of a restart_mul sub-context\r
 183  */\r
 184 static void ecp_restart_rsm_free( mbedtls_ecp_restart_mul_ctx *ctx )\r
 185 {\r
 186     unsigned char i;\r
 187 \r
 188     if( ctx == NULL )\r
 189         return;\r
 190 \r
 191     mbedtls_ecp_point_free( &ctx->R );\r
 192 \r
 193     if( ctx->T != NULL )\r
 194     {\r
 195         for( i = 0; i < ctx->T_size; i++ )\r
 196             mbedtls_ecp_point_free( ctx->T + i );\r
 197         mbedtls_free( ctx->T );\r
 198     }\r
 199 \r
 200     ecp_restart_rsm_init( ctx );\r
 201 }\r
 202 \r
 203 /*\r
 204  * Restart context for ecp_muladd()\r
 205  */\r
 206 struct mbedtls_ecp_restart_muladd\r
 207 {\r
 208     mbedtls_ecp_point mP;       /* mP value                             */\r
 209     mbedtls_ecp_point R;        /* R intermediate result                */\r
 210     enum {                      /* what should we do next?              */\r
 211         ecp_rsma_mul1 = 0,      /* first multiplication                 */\r
 212         ecp_rsma_mul2,          /* second multiplication                */\r
 213         ecp_rsma_add,           /* addition                             */\r
 214         ecp_rsma_norm,          /* normalization                        */\r
 215     } state;\r
 216 };\r
 217 \r
 218 /*\r
 219  * Init restart_muladd sub-context\r
 220  */\r
 221 static void ecp_restart_ma_init( mbedtls_ecp_restart_muladd_ctx *ctx )\r
 222 {\r
 223     mbedtls_ecp_point_init( &ctx->mP );\r
 224     mbedtls_ecp_point_init( &ctx->R );\r
 225     ctx->state = ecp_rsma_mul1;\r
 226 }\r
 227 \r
 228 /*\r
 229  * Free the components of a restart_muladd sub-context\r
 230  */\r
 231 static void ecp_restart_ma_free( mbedtls_ecp_restart_muladd_ctx *ctx )\r
 232 {\r
 233     if( ctx == NULL )\r
 234         return;\r
 235 \r
 236     mbedtls_ecp_point_free( &ctx->mP );\r
 237     mbedtls_ecp_point_free( &ctx->R );\r
 238 \r
 239     ecp_restart_ma_init( ctx );\r
 240 }\r
 241 \r
 242 /*\r
 243  * Initialize a restart context\r
 244  */\r
 245 void mbedtls_ecp_restart_init( mbedtls_ecp_restart_ctx *ctx )\r
 246 {\r
 247     ECP_VALIDATE( ctx != NULL );\r
 248     ctx->ops_done = 0;\r
 249     ctx->depth = 0;\r
 250     ctx->rsm = NULL;\r
 251     ctx->ma = NULL;\r
 252 }\r
 253 \r
 254 /*\r
 255  * Free the components of a restart context\r
 256  */\r
 257 void mbedtls_ecp_restart_free( mbedtls_ecp_restart_ctx *ctx )\r
 258 {\r
 259     if( ctx == NULL )\r
 260         return;\r
 261 \r
 262     ecp_restart_rsm_free( ctx->rsm );\r
 263     mbedtls_free( ctx->rsm );\r
 264 \r
 265     ecp_restart_ma_free( ctx->ma );\r
 266     mbedtls_free( ctx->ma );\r
 267 \r
 268     mbedtls_ecp_restart_init( ctx );\r
 269 }\r
 270 \r
 271 /*\r
 272  * Check if we can do the next step\r
 273  */\r
 274 int mbedtls_ecp_check_budget( const mbedtls_ecp_group *grp,\r
 275                               mbedtls_ecp_restart_ctx *rs_ctx,\r
 276                               unsigned ops )\r
 277 {\r
 278     ECP_VALIDATE_RET( grp != NULL );\r
 279 \r
 280     if( rs_ctx != NULL && ecp_max_ops != 0 )\r
 281     {\r
 282         /* scale depending on curve size: the chosen reference is 256-bit,\r
 283          * and multiplication is quadratic. Round to the closest integer. */\r
 284         if( grp->pbits >= 512 )\r
 285             ops *= 4;\r
 286         else if( grp->pbits >= 384 )\r
 287             ops *= 2;\r
 288 \r
 289         /* Avoid infinite loops: always allow first step.\r
 290          * Because of that, however, it's not generally true\r
 291          * that ops_done <= ecp_max_ops, so the check\r
 292          * ops_done > ecp_max_ops below is mandatory. */\r
 293         if( ( rs_ctx->ops_done != 0 ) &&\r
 294             ( rs_ctx->ops_done > ecp_max_ops ||\r
 295               ops > ecp_max_ops - rs_ctx->ops_done ) )\r
 296         {\r
 297             return( MBEDTLS_ERR_ECP_IN_PROGRESS );\r
 298         }\r
 299 \r
 300         /* update running count */\r
 301         rs_ctx->ops_done += ops;\r
 302     }\r
 303 \r
 304     return( 0 );\r
 305 }\r
 306 \r
 307 /* Call this when entering a function that needs its own sub-context */\r
 308 #define ECP_RS_ENTER( SUB )   do {                                      \\r
 309     /* reset ops count for this call if top-level */                    \\r
 310     if( rs_ctx != NULL && rs_ctx->depth++ == 0 )                        \\r
 311         rs_ctx->ops_done = 0;                                           \\r
 312                                                                         \\r
 313     /* set up our own sub-context if needed */                          \\r
 314     if( mbedtls_ecp_restart_is_enabled() &&                             \\r
 315         rs_ctx != NULL && rs_ctx->SUB == NULL )                         \\r
 316     {                                                                   \\r
 317         rs_ctx->SUB = mbedtls_calloc( 1, sizeof( *rs_ctx->SUB ) );      \\r
 318         if( rs_ctx->SUB == NULL )                                       \\r
 319             return( MBEDTLS_ERR_ECP_ALLOC_FAILED );                     \\r
 320                                                                         \\r
 321         ecp_restart_## SUB ##_init( rs_ctx->SUB );                      \\r
 322     }                                                                   \\r
 323 } while( 0 )\r
 324 \r
 325 /* Call this when leaving a function that needs its own sub-context */\r
 326 #define ECP_RS_LEAVE( SUB )   do {                                      \\r
 327     /* clear our sub-context when not in progress (done or error) */    \\r
 328     if( rs_ctx != NULL && rs_ctx->SUB != NULL &&                        \\r
 329         ret != MBEDTLS_ERR_ECP_IN_PROGRESS )                            \\r
 330     {                                                                   \\r
 331         ecp_restart_## SUB ##_free( rs_ctx->SUB );                      \\r
 332         mbedtls_free( rs_ctx->SUB );                                    \\r
 333         rs_ctx->SUB = NULL;                                             \\r
 334     }                                                                   \\r
 335                                                                         \\r
 336     if( rs_ctx != NULL )                                                \\r
 337         rs_ctx->depth--;                                                \\r
 338 } while( 0 )\r
 339 \r
 340 #else /* MBEDTLS_ECP_RESTARTABLE */\r
 341 \r
 342 #define ECP_RS_ENTER( sub )     (void) rs_ctx;\r
 343 #define ECP_RS_LEAVE( sub )     (void) rs_ctx;\r
 344 \r
 345 #endif /* MBEDTLS_ECP_RESTARTABLE */\r
 346 \r
 347 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) ||   \\r
 348     defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) ||   \\r
 349     defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) ||   \\r
 350     defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) ||   \\r
 351     defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) ||   \\r
 352     defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)   ||   \\r
 353     defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)   ||   \\r
 354     defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)   ||   \\r
 355     defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) ||   \\r
 356     defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) ||   \\r
 357     defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)\r
 358 #define ECP_SHORTWEIERSTRASS\r
 359 #endif\r
 360 \r
 361 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) || \\r
 362     defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)\r
 363 #define ECP_MONTGOMERY\r
 364 #endif\r
 365 \r
 366 /*\r
 367  * List of supported curves:\r
 368  *  - internal ID\r
 369  *  - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)\r
 370  *  - size in bits\r
 371  *  - readable name\r
 372  *\r
 373  * Curves are listed in order: largest curves first, and for a given size,\r
 374  * fastest curves first. This provides the default order for the SSL module.\r
 375  *\r
 376  * Reminder: update profiles in x509_crt.c when adding a new curves!\r
 377  */\r
 378 static const mbedtls_ecp_curve_info ecp_supported_curves[] =\r
 379 {\r
 380 #if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)\r
 381     { MBEDTLS_ECP_DP_SECP521R1,    25,     521,    "secp521r1"         },\r
 382 #endif\r
 383 #if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)\r
 384     { MBEDTLS_ECP_DP_BP512R1,      28,     512,    "brainpoolP512r1"   },\r
 385 #endif\r
 386 #if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)\r
 387     { MBEDTLS_ECP_DP_SECP384R1,    24,     384,    "secp384r1"         },\r
 388 #endif\r
 389 #if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)\r
 390     { MBEDTLS_ECP_DP_BP384R1,      27,     384,    "brainpoolP384r1"   },\r
 391 #endif\r
 392 #if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)\r
 393     { MBEDTLS_ECP_DP_SECP256R1,    23,     256,    "secp256r1"         },\r
 394 #endif\r
 395 #if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)\r
 396     { MBEDTLS_ECP_DP_SECP256K1,    22,     256,    "secp256k1"         },\r
 397 #endif\r
 398 #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)\r
 399     { MBEDTLS_ECP_DP_BP256R1,      26,     256,    "brainpoolP256r1"   },\r
 400 #endif\r
 401 #if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)\r
 402     { MBEDTLS_ECP_DP_SECP224R1,    21,     224,    "secp224r1"         },\r
 403 #endif\r
 404 #if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)\r
 405     { MBEDTLS_ECP_DP_SECP224K1,    20,     224,    "secp224k1"         },\r
 406 #endif\r
 407 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)\r
 408     { MBEDTLS_ECP_DP_SECP192R1,    19,     192,    "secp192r1"         },\r
 409 #endif\r
 410 #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)\r
 411     { MBEDTLS_ECP_DP_SECP192K1,    18,     192,    "secp192k1"         },\r
 412 #endif\r
 413     { MBEDTLS_ECP_DP_NONE,          0,     0,      NULL                },\r
 414 };\r
 415 \r
 416 #define ECP_NB_CURVES   sizeof( ecp_supported_curves ) /    \\r
 417                         sizeof( ecp_supported_curves[0] )\r
 418 \r
 419 static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];\r
 420 \r
 421 /*\r
 422  * List of supported curves and associated info\r
 423  */\r
 424 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void )\r
 425 {\r
 426     return( ecp_supported_curves );\r
 427 }\r
 428 \r
 429 /*\r
 430  * List of supported curves, group ID only\r
 431  */\r
 432 const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void )\r
 433 {\r
 434     static int init_done = 0;\r
 435 \r
 436     if( ! init_done )\r
 437     {\r
 438         size_t i = 0;\r
 439         const mbedtls_ecp_curve_info *curve_info;\r
 440 \r
 441         for( curve_info = mbedtls_ecp_curve_list();\r
 442              curve_info->grp_id != MBEDTLS_ECP_DP_NONE;\r
 443              curve_info++ )\r
 444         {\r
 445             ecp_supported_grp_id[i++] = curve_info->grp_id;\r
 446         }\r
 447         ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;\r
 448 \r
 449         init_done = 1;\r
 450     }\r
 451 \r
 452     return( ecp_supported_grp_id );\r
 453 }\r
 454 \r
 455 /*\r
 456  * Get the curve info for the internal identifier\r
 457  */\r
 458 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id )\r
 459 {\r
 460     const mbedtls_ecp_curve_info *curve_info;\r
 461 \r
 462     for( curve_info = mbedtls_ecp_curve_list();\r
 463          curve_info->grp_id != MBEDTLS_ECP_DP_NONE;\r
 464          curve_info++ )\r
 465     {\r
 466         if( curve_info->grp_id == grp_id )\r
 467             return( curve_info );\r
 468     }\r
 469 \r
 470     return( NULL );\r
 471 }\r
 472 \r
 473 /*\r
 474  * Get the curve info from the TLS identifier\r
 475  */\r
 476 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id )\r
 477 {\r
 478     const mbedtls_ecp_curve_info *curve_info;\r
 479 \r
 480     for( curve_info = mbedtls_ecp_curve_list();\r
 481          curve_info->grp_id != MBEDTLS_ECP_DP_NONE;\r
 482          curve_info++ )\r
 483     {\r
 484         if( curve_info->tls_id == tls_id )\r
 485             return( curve_info );\r
 486     }\r
 487 \r
 488     return( NULL );\r
 489 }\r
 490 \r
 491 /*\r
 492  * Get the curve info from the name\r
 493  */\r
 494 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name )\r
 495 {\r
 496     const mbedtls_ecp_curve_info *curve_info;\r
 497 \r
 498     if( name == NULL )\r
 499         return( NULL );\r
 500 \r
 501     for( curve_info = mbedtls_ecp_curve_list();\r
 502          curve_info->grp_id != MBEDTLS_ECP_DP_NONE;\r
 503          curve_info++ )\r
 504     {\r
 505         if( strcmp( curve_info->name, name ) == 0 )\r
 506             return( curve_info );\r
 507     }\r
 508 \r
 509     return( NULL );\r
 510 }\r
 511 \r
 512 /*\r
 513  * Get the type of a curve\r
 514  */\r
 515 mbedtls_ecp_curve_type mbedtls_ecp_get_type( const mbedtls_ecp_group *grp )\r
 516 {\r
 517     if( grp->G.X.p == NULL )\r
 518         return( MBEDTLS_ECP_TYPE_NONE );\r
 519 \r
 520     if( grp->G.Y.p == NULL )\r
 521         return( MBEDTLS_ECP_TYPE_MONTGOMERY );\r
 522     else\r
 523         return( MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS );\r
 524 }\r
 525 \r
 526 /*\r
 527  * Initialize (the components of) a point\r
 528  */\r
 529 void mbedtls_ecp_point_init( mbedtls_ecp_point *pt )\r
 530 {\r
 531     ECP_VALIDATE( pt != NULL );\r
 532 \r
 533     mbedtls_mpi_init( &pt->X );\r
 534     mbedtls_mpi_init( &pt->Y );\r
 535     mbedtls_mpi_init( &pt->Z );\r
 536 }\r
 537 \r
 538 /*\r
 539  * Initialize (the components of) a group\r
 540  */\r
 541 void mbedtls_ecp_group_init( mbedtls_ecp_group *grp )\r
 542 {\r
 543     ECP_VALIDATE( grp != NULL );\r
 544 \r
 545     grp->id = MBEDTLS_ECP_DP_NONE;\r
 546     mbedtls_mpi_init( &grp->P );\r
 547     mbedtls_mpi_init( &grp->A );\r
 548     mbedtls_mpi_init( &grp->B );\r
 549     mbedtls_ecp_point_init( &grp->G );\r
 550     mbedtls_mpi_init( &grp->N );\r
 551     grp->pbits = 0;\r
 552     grp->nbits = 0;\r
 553     grp->h = 0;\r
 554     grp->modp = NULL;\r
 555     grp->t_pre = NULL;\r
 556     grp->t_post = NULL;\r
 557     grp->t_data = NULL;\r
 558     grp->T = NULL;\r
 559     grp->T_size = 0;\r
 560 }\r
 561 \r
 562 /*\r
 563  * Initialize (the components of) a key pair\r
 564  */\r
 565 void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key )\r
 566 {\r
 567     ECP_VALIDATE( key != NULL );\r
 568 \r
 569     mbedtls_ecp_group_init( &key->grp );\r
 570     mbedtls_mpi_init( &key->d );\r
 571     mbedtls_ecp_point_init( &key->Q );\r
 572 }\r
 573 \r
 574 /*\r
 575  * Unallocate (the components of) a point\r
 576  */\r
 577 void mbedtls_ecp_point_free( mbedtls_ecp_point *pt )\r
 578 {\r
 579     if( pt == NULL )\r
 580         return;\r
 581 \r
 582     mbedtls_mpi_free( &( pt->X ) );\r
 583     mbedtls_mpi_free( &( pt->Y ) );\r
 584     mbedtls_mpi_free( &( pt->Z ) );\r
 585 }\r
 586 \r
 587 /*\r
 588  * Unallocate (the components of) a group\r
 589  */\r
 590 void mbedtls_ecp_group_free( mbedtls_ecp_group *grp )\r
 591 {\r
 592     size_t i;\r
 593 \r
 594     if( grp == NULL )\r
 595         return;\r
 596 \r
 597     if( grp->h != 1 )\r
 598     {\r
 599         mbedtls_mpi_free( &grp->P );\r
 600         mbedtls_mpi_free( &grp->A );\r
 601         mbedtls_mpi_free( &grp->B );\r
 602         mbedtls_ecp_point_free( &grp->G );\r
 603         mbedtls_mpi_free( &grp->N );\r
 604     }\r
 605 \r
 606     if( grp->T != NULL )\r
 607     {\r
 608         for( i = 0; i < grp->T_size; i++ )\r
 609             mbedtls_ecp_point_free( &grp->T[i] );\r
 610         mbedtls_free( grp->T );\r
 611     }\r
 612 \r
 613     mbedtls_platform_zeroize( grp, sizeof( mbedtls_ecp_group ) );\r
 614 }\r
 615 \r
 616 /*\r
 617  * Unallocate (the components of) a key pair\r
 618  */\r
 619 void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key )\r
 620 {\r
 621     if( key == NULL )\r
 622         return;\r
 623 \r
 624     mbedtls_ecp_group_free( &key->grp );\r
 625     mbedtls_mpi_free( &key->d );\r
 626     mbedtls_ecp_point_free( &key->Q );\r
 627 }\r
 628 \r
 629 /*\r
 630  * Copy the contents of a point\r
 631  */\r
 632 int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )\r
 633 {\r
 634     int ret;\r
 635     ECP_VALIDATE_RET( P != NULL );\r
 636     ECP_VALIDATE_RET( Q != NULL );\r
 637 \r
 638     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X, &Q->X ) );\r
 639     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y, &Q->Y ) );\r
 640     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z, &Q->Z ) );\r
 641 \r
 642 cleanup:\r
 643     return( ret );\r
 644 }\r
 645 \r
 646 /*\r
 647  * Copy the contents of a group object\r
 648  */\r
 649 int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src )\r
 650 {\r
 651     ECP_VALIDATE_RET( dst != NULL );\r
 652     ECP_VALIDATE_RET( src != NULL );\r
 653 \r
 654     return( mbedtls_ecp_group_load( dst, src->id ) );\r
 655 }\r
 656 \r
 657 /*\r
 658  * Set point to zero\r
 659  */\r
 660 int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt )\r
 661 {\r
 662     int ret;\r
 663     ECP_VALIDATE_RET( pt != NULL );\r
 664 \r
 665     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) );\r
 666     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y , 1 ) );\r
 667     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 0 ) );\r
 668 \r
 669 cleanup:\r
 670     return( ret );\r
 671 }\r
 672 \r
 673 /*\r
 674  * Tell if a point is zero\r
 675  */\r
 676 int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt )\r
 677 {\r
 678     ECP_VALIDATE_RET( pt != NULL );\r
 679 \r
 680     return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 );\r
 681 }\r
 682 \r
 683 /*\r
 684  * Compare two points lazily\r
 685  */\r
 686 int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P,\r
 687                            const mbedtls_ecp_point *Q )\r
 688 {\r
 689     ECP_VALIDATE_RET( P != NULL );\r
 690     ECP_VALIDATE_RET( Q != NULL );\r
 691 \r
 692     if( mbedtls_mpi_cmp_mpi( &P->X, &Q->X ) == 0 &&\r
 693         mbedtls_mpi_cmp_mpi( &P->Y, &Q->Y ) == 0 &&\r
 694         mbedtls_mpi_cmp_mpi( &P->Z, &Q->Z ) == 0 )\r
 695     {\r
 696         return( 0 );\r
 697     }\r
 698 \r
 699     return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 700 }\r
 701 \r
 702 /*\r
 703  * Import a non-zero point from ASCII strings\r
 704  */\r
 705 int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix,\r
 706                            const char *x, const char *y )\r
 707 {\r
 708     int ret;\r
 709     ECP_VALIDATE_RET( P != NULL );\r
 710     ECP_VALIDATE_RET( x != NULL );\r
 711     ECP_VALIDATE_RET( y != NULL );\r
 712 \r
 713     MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X, radix, x ) );\r
 714     MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y, radix, y ) );\r
 715     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );\r
 716 \r
 717 cleanup:\r
 718     return( ret );\r
 719 }\r
 720 \r
 721 /*\r
 722  * Export a point into unsigned binary data (SEC1 2.3.3 and RFC7748)\r
 723  */\r
 724 int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp,\r
 725                                     const mbedtls_ecp_point *P,\r
 726                                     int format, size_t *olen,\r
 727                                     unsigned char *buf, size_t buflen )\r
 728 {\r
 729     int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;\r
 730     size_t plen;\r
 731     ECP_VALIDATE_RET( grp  != NULL );\r
 732     ECP_VALIDATE_RET( P    != NULL );\r
 733     ECP_VALIDATE_RET( olen != NULL );\r
 734     ECP_VALIDATE_RET( buf  != NULL );\r
 735     ECP_VALIDATE_RET( format == MBEDTLS_ECP_PF_UNCOMPRESSED ||\r
 736                       format == MBEDTLS_ECP_PF_COMPRESSED );\r
 737 \r
 738     plen = mbedtls_mpi_size( &grp->P );\r
 739 \r
 740 #if defined(ECP_MONTGOMERY)\r
 741     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )\r
 742     {\r
 743         *olen = plen;\r
 744         if( buflen < *olen )\r
 745             return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );\r
 746 \r
 747         MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary_le( &P->X, buf, plen ) );\r
 748     }\r
 749 #endif\r
 750 #if defined(ECP_SHORTWEIERSTRASS)\r
 751     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )\r
 752     {\r
 753         /*\r
 754          * Common case: P == 0\r
 755          */\r
 756         if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )\r
 757         {\r
 758             if( buflen < 1 )\r
 759                 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );\r
 760 \r
 761             buf[0] = 0x00;\r
 762             *olen = 1;\r
 763 \r
 764             return( 0 );\r
 765         }\r
 766 \r
 767         if( format == MBEDTLS_ECP_PF_UNCOMPRESSED )\r
 768         {\r
 769             *olen = 2 * plen + 1;\r
 770 \r
 771             if( buflen < *olen )\r
 772                 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );\r
 773 \r
 774             buf[0] = 0x04;\r
 775             MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );\r
 776             MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) );\r
 777         }\r
 778         else if( format == MBEDTLS_ECP_PF_COMPRESSED )\r
 779         {\r
 780             *olen = plen + 1;\r
 781 \r
 782             if( buflen < *olen )\r
 783                 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );\r
 784 \r
 785             buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 );\r
 786             MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );\r
 787         }\r
 788     }\r
 789 #endif\r
 790 \r
 791 cleanup:\r
 792     return( ret );\r
 793 }\r
 794 \r
 795 /*\r
 796  * Import a point from unsigned binary data (SEC1 2.3.4 and RFC7748)\r
 797  */\r
 798 int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp,\r
 799                                    mbedtls_ecp_point *pt,\r
 800                                    const unsigned char *buf, size_t ilen )\r
 801 {\r
 802     int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;\r
 803     size_t plen;\r
 804     ECP_VALIDATE_RET( grp != NULL );\r
 805     ECP_VALIDATE_RET( pt  != NULL );\r
 806     ECP_VALIDATE_RET( buf != NULL );\r
 807 \r
 808     if( ilen < 1 )\r
 809         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 810 \r
 811     plen = mbedtls_mpi_size( &grp->P );\r
 812 \r
 813 #if defined(ECP_MONTGOMERY)\r
 814     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )\r
 815     {\r
 816         if( plen != ilen )\r
 817             return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 818 \r
 819         MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary_le( &pt->X, buf, plen ) );\r
 820         mbedtls_mpi_free( &pt->Y );\r
 821 \r
 822         if( grp->id == MBEDTLS_ECP_DP_CURVE25519 )\r
 823             /* Set most significant bit to 0 as prescribed in RFC7748 §5 */\r
 824             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &pt->X, plen * 8 - 1, 0 ) );\r
 825 \r
 826         MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );\r
 827     }\r
 828 #endif\r
 829 #if defined(ECP_SHORTWEIERSTRASS)\r
 830     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )\r
 831     {\r
 832         if( buf[0] == 0x00 )\r
 833         {\r
 834             if( ilen == 1 )\r
 835                 return( mbedtls_ecp_set_zero( pt ) );\r
 836             else\r
 837                 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 838         }\r
 839 \r
 840         if( buf[0] != 0x04 )\r
 841             return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );\r
 842 \r
 843         if( ilen != 2 * plen + 1 )\r
 844             return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 845 \r
 846         MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) );\r
 847         MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y,\r
 848                                                   buf + 1 + plen, plen ) );\r
 849         MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );\r
 850     }\r
 851 #endif\r
 852 \r
 853 cleanup:\r
 854     return( ret );\r
 855 }\r
 856 \r
 857 /*\r
 858  * Import a point from a TLS ECPoint record (RFC 4492)\r
 859  *      struct {\r
 860  *          opaque point <1..2^8-1>;\r
 861  *      } ECPoint;\r
 862  */\r
 863 int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group *grp,\r
 864                                 mbedtls_ecp_point *pt,\r
 865                                 const unsigned char **buf, size_t buf_len )\r
 866 {\r
 867     unsigned char data_len;\r
 868     const unsigned char *buf_start;\r
 869     ECP_VALIDATE_RET( grp != NULL );\r
 870     ECP_VALIDATE_RET( pt  != NULL );\r
 871     ECP_VALIDATE_RET( buf != NULL );\r
 872     ECP_VALIDATE_RET( *buf != NULL );\r
 873 \r
 874     /*\r
 875      * We must have at least two bytes (1 for length, at least one for data)\r
 876      */\r
 877     if( buf_len < 2 )\r
 878         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 879 \r
 880     data_len = *(*buf)++;\r
 881     if( data_len < 1 || data_len > buf_len - 1 )\r
 882         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 883 \r
 884     /*\r
 885      * Save buffer start for read_binary and update buf\r
 886      */\r
 887     buf_start = *buf;\r
 888     *buf += data_len;\r
 889 \r
 890     return( mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len ) );\r
 891 }\r
 892 \r
 893 /*\r
 894  * Export a point as a TLS ECPoint record (RFC 4492)\r
 895  *      struct {\r
 896  *          opaque point <1..2^8-1>;\r
 897  *      } ECPoint;\r
 898  */\r
 899 int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt,\r
 900                          int format, size_t *olen,\r
 901                          unsigned char *buf, size_t blen )\r
 902 {\r
 903     int ret;\r
 904     ECP_VALIDATE_RET( grp  != NULL );\r
 905     ECP_VALIDATE_RET( pt   != NULL );\r
 906     ECP_VALIDATE_RET( olen != NULL );\r
 907     ECP_VALIDATE_RET( buf  != NULL );\r
 908     ECP_VALIDATE_RET( format == MBEDTLS_ECP_PF_UNCOMPRESSED ||\r
 909                       format == MBEDTLS_ECP_PF_COMPRESSED );\r
 910 \r
 911     /*\r
 912      * buffer length must be at least one, for our length byte\r
 913      */\r
 914     if( blen < 1 )\r
 915         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 916 \r
 917     if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format,\r
 918                     olen, buf + 1, blen - 1) ) != 0 )\r
 919         return( ret );\r
 920 \r
 921     /*\r
 922      * write length to the first byte and update total length\r
 923      */\r
 924     buf[0] = (unsigned char) *olen;\r
 925     ++*olen;\r
 926 \r
 927     return( 0 );\r
 928 }\r
 929 \r
 930 /*\r
 931  * Set a group from an ECParameters record (RFC 4492)\r
 932  */\r
 933 int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp,\r
 934                                 const unsigned char **buf, size_t len )\r
 935 {\r
 936     int ret;\r
 937     mbedtls_ecp_group_id grp_id;\r
 938     ECP_VALIDATE_RET( grp  != NULL );\r
 939     ECP_VALIDATE_RET( buf  != NULL );\r
 940     ECP_VALIDATE_RET( *buf != NULL );\r
 941 \r
 942     if( ( ret = mbedtls_ecp_tls_read_group_id( &grp_id, buf, len ) ) != 0 )\r
 943         return( ret );\r
 944 \r
 945     return( mbedtls_ecp_group_load( grp, grp_id ) );\r
 946 }\r
 947 \r
 948 /*\r
 949  * Read a group id from an ECParameters record (RFC 4492) and convert it to\r
 950  * mbedtls_ecp_group_id.\r
 951  */\r
 952 int mbedtls_ecp_tls_read_group_id( mbedtls_ecp_group_id *grp,\r
 953                                    const unsigned char **buf, size_t len )\r
 954 {\r
 955     uint16_t tls_id;\r
 956     const mbedtls_ecp_curve_info *curve_info;\r
 957     ECP_VALIDATE_RET( grp  != NULL );\r
 958     ECP_VALIDATE_RET( buf  != NULL );\r
 959     ECP_VALIDATE_RET( *buf != NULL );\r
 960 \r
 961     /*\r
 962      * We expect at least three bytes (see below)\r
 963      */\r
 964     if( len < 3 )\r
 965         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 966 \r
 967     /*\r
 968      * First byte is curve_type; only named_curve is handled\r
 969      */\r
 970     if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE )\r
 971         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 972 \r
 973     /*\r
 974      * Next two bytes are the namedcurve value\r
 975      */\r
 976     tls_id = *(*buf)++;\r
 977     tls_id <<= 8;\r
 978     tls_id |= *(*buf)++;\r
 979 \r
 980     if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL )\r
 981         return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );\r
 982 \r
 983     *grp = curve_info->grp_id;\r
 984 \r
 985     return( 0 );\r
 986 }\r
 987 \r
 988 /*\r
 989  * Write the ECParameters record corresponding to a group (RFC 4492)\r
 990  */\r
 991 int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen,\r
 992                          unsigned char *buf, size_t blen )\r
 993 {\r
 994     const mbedtls_ecp_curve_info *curve_info;\r
 995     ECP_VALIDATE_RET( grp  != NULL );\r
 996     ECP_VALIDATE_RET( buf  != NULL );\r
 997     ECP_VALIDATE_RET( olen != NULL );\r
 998 \r
 999     if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL )\r
1000         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
1001 \r
1002     /*\r
1003      * We are going to write 3 bytes (see below)\r
1004      */\r
1005     *olen = 3;\r
1006     if( blen < *olen )\r
1007         return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );\r
1008 \r
1009     /*\r
1010      * First byte is curve_type, always named_curve\r
1011      */\r
1012     *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;\r
1013 \r
1014     /*\r
1015      * Next two bytes are the namedcurve value\r
1016      */\r
1017     buf[0] = curve_info->tls_id >> 8;\r
1018     buf[1] = curve_info->tls_id & 0xFF;\r
1019 \r
1020     return( 0 );\r
1021 }\r
1022 \r
1023 /*\r
1024  * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.\r
1025  * See the documentation of struct mbedtls_ecp_group.\r
1026  *\r
1027  * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.\r
1028  */\r
1029 static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp )\r
1030 {\r
1031     int ret;\r
1032 \r
1033     if( grp->modp == NULL )\r
1034         return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) );\r
1035 \r
1036     /* N->s < 0 is a much faster test, which fails only if N is 0 */\r
1037     if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) ||\r
1038         mbedtls_mpi_bitlen( N ) > 2 * grp->pbits )\r
1039     {\r
1040         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
1041     }\r
1042 \r
1043     MBEDTLS_MPI_CHK( grp->modp( N ) );\r
1044 \r
1045     /* N->s < 0 is a much faster test, which fails only if N is 0 */\r
1046     while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 )\r
1047         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) );\r
1048 \r
1049     while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 )\r
1050         /* we known P, N and the result are positive */\r
1051         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) );\r
1052 \r
1053 cleanup:\r
1054     return( ret );\r
1055 }\r
1056 \r
1057 /*\r
1058  * Fast mod-p functions expect their argument to be in the 0..p^2 range.\r
1059  *\r
1060  * In order to guarantee that, we need to ensure that operands of\r
1061  * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will\r
1062  * bring the result back to this range.\r
1063  *\r
1064  * The following macros are shortcuts for doing that.\r
1065  */\r
1066 \r
1067 /*\r
1068  * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi\r
1069  */\r
1070 #if defined(MBEDTLS_SELF_TEST)\r
1071 #define INC_MUL_COUNT   mul_count++;\r
1072 #else\r
1073 #define INC_MUL_COUNT\r
1074 #endif\r
1075 \r
1076 #define MOD_MUL( N )                                                    \\r
1077     do                                                                  \\r
1078     {                                                                   \\r
1079         MBEDTLS_MPI_CHK( ecp_modp( &(N), grp ) );                       \\r
1080         INC_MUL_COUNT                                                   \\r
1081     } while( 0 )\r
1082 \r
1083 /*\r
1084  * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi\r
1085  * N->s < 0 is a very fast test, which fails only if N is 0\r
1086  */\r
1087 #define MOD_SUB( N )                                                    \\r
1088     while( (N).s < 0 && mbedtls_mpi_cmp_int( &(N), 0 ) != 0 )           \\r
1089         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &(N), &(N), &grp->P ) )\r
1090 \r
1091 /*\r
1092  * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.\r
1093  * We known P, N and the result are positive, so sub_abs is correct, and\r
1094  * a bit faster.\r
1095  */\r
1096 #define MOD_ADD( N )                                                    \\r
1097     while( mbedtls_mpi_cmp_mpi( &(N), &grp->P ) >= 0 )                  \\r
1098         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &(N), &(N), &grp->P ) )\r
1099 \r
1100 #if defined(ECP_SHORTWEIERSTRASS)\r
1101 /*\r
1102  * For curves in short Weierstrass form, we do all the internal operations in\r
1103  * Jacobian coordinates.\r
1104  *\r
1105  * For multiplication, we'll use a comb method with coutermeasueres against\r
1106  * SPA, hence timing attacks.\r
1107  */\r
1108 \r
1109 /*\r
1110  * Normalize jacobian coordinates so that Z == 0 || Z == 1  (GECC 3.2.1)\r
1111  * Cost: 1N := 1I + 3M + 1S\r
1112  */\r
1113 static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt )\r
1114 {\r
1115     int ret;\r
1116     mbedtls_mpi Zi, ZZi;\r
1117 \r
1118     if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 )\r
1119         return( 0 );\r
1120 \r
1121 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)\r
1122     if( mbedtls_internal_ecp_grp_capable( grp ) )\r
1123         return( mbedtls_internal_ecp_normalize_jac( grp, pt ) );\r
1124 #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */\r
1125 \r
1126     mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );\r
1127 \r
1128     /*\r
1129      * X = X / Z^2  mod p\r
1130      */\r
1131     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi,      &pt->Z,     &grp->P ) );\r
1132     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi,     &Zi,        &Zi     ) ); MOD_MUL( ZZi );\r
1133     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X,   &pt->X,     &ZZi    ) ); MOD_MUL( pt->X );\r
1134 \r
1135     /*\r
1136      * Y = Y / Z^3  mod p\r
1137      */\r
1138     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y,   &pt->Y,     &ZZi    ) ); MOD_MUL( pt->Y );\r
1139     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y,   &pt->Y,     &Zi     ) ); MOD_MUL( pt->Y );\r
1140 \r
1141     /*\r
1142      * Z = 1\r
1143      */\r
1144     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );\r
1145 \r
1146 cleanup:\r
1147 \r
1148     mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );\r
1149 \r
1150     return( ret );\r
1151 }\r
1152 \r
1153 /*\r
1154  * Normalize jacobian coordinates of an array of (pointers to) points,\r
1155  * using Montgomery's trick to perform only one inversion mod P.\r
1156  * (See for example Cohen's "A Course in Computational Algebraic Number\r
1157  * Theory", Algorithm 10.3.4.)\r
1158  *\r
1159  * Warning: fails (returning an error) if one of the points is zero!\r
1160  * This should never happen, see choice of w in ecp_mul_comb().\r
1161  *\r
1162  * Cost: 1N(t) := 1I + (6t - 3)M + 1S\r
1163  */\r
1164 static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp,\r
1165                                    mbedtls_ecp_point *T[], size_t T_size )\r
1166 {\r
1167     int ret;\r
1168     size_t i;\r
1169     mbedtls_mpi *c, u, Zi, ZZi;\r
1170 \r
1171     if( T_size < 2 )\r
1172         return( ecp_normalize_jac( grp, *T ) );\r
1173 \r
1174 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)\r
1175     if( mbedtls_internal_ecp_grp_capable( grp ) )\r
1176         return( mbedtls_internal_ecp_normalize_jac_many( grp, T, T_size ) );\r
1177 #endif\r
1178 \r
1179     if( ( c = mbedtls_calloc( T_size, sizeof( mbedtls_mpi ) ) ) == NULL )\r
1180         return( MBEDTLS_ERR_ECP_ALLOC_FAILED );\r
1181 \r
1182     for( i = 0; i < T_size; i++ )\r
1183         mbedtls_mpi_init( &c[i] );\r
1184 \r
1185     mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );\r
1186 \r
1187     /*\r
1188      * c[i] = Z_0 * ... * Z_i\r
1189      */\r
1190     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) );\r
1191     for( i = 1; i < T_size; i++ )\r
1192     {\r
1193         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );\r
1194         MOD_MUL( c[i] );\r
1195     }\r
1196 \r
1197     /*\r
1198      * u = 1 / (Z_0 * ... * Z_n) mod P\r
1199      */\r
1200     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[T_size-1], &grp->P ) );\r
1201 \r
1202     for( i = T_size - 1; ; i-- )\r
1203     {\r
1204         /*\r
1205          * Zi = 1 / Z_i mod p\r
1206          * u = 1 / (Z_0 * ... * Z_i) mod P\r
1207          */\r
1208         if( i == 0 ) {\r
1209             MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) );\r
1210         }\r
1211         else\r
1212         {\r
1213             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1]  ) ); MOD_MUL( Zi );\r
1214             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u,  &u, &T[i]->Z ) ); MOD_MUL( u );\r
1215         }\r
1216 \r
1217         /*\r
1218          * proceed as in normalize()\r
1219          */\r
1220         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi,     &Zi,      &Zi  ) ); MOD_MUL( ZZi );\r
1221         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X );\r
1222         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y );\r
1223         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi  ) ); MOD_MUL( T[i]->Y );\r
1224 \r
1225         /*\r
1226          * Post-precessing: reclaim some memory by shrinking coordinates\r
1227          * - not storing Z (always 1)\r
1228          * - shrinking other coordinates, but still keeping the same number of\r
1229          *   limbs as P, as otherwise it will too likely be regrown too fast.\r
1230          */\r
1231         MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) );\r
1232         MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) );\r
1233         mbedtls_mpi_free( &T[i]->Z );\r
1234 \r
1235         if( i == 0 )\r
1236             break;\r
1237     }\r
1238 \r
1239 cleanup:\r
1240 \r
1241     mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );\r
1242     for( i = 0; i < T_size; i++ )\r
1243         mbedtls_mpi_free( &c[i] );\r
1244     mbedtls_free( c );\r
1245 \r
1246     return( ret );\r
1247 }\r
1248 \r
1249 /*\r
1250  * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.\r
1251  * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid\r
1252  */\r
1253 static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp,\r
1254                             mbedtls_ecp_point *Q,\r
1255                             unsigned char inv )\r
1256 {\r
1257     int ret;\r
1258     unsigned char nonzero;\r
1259     mbedtls_mpi mQY;\r
1260 \r
1261     mbedtls_mpi_init( &mQY );\r
1262 \r
1263     /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */\r
1264     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) );\r
1265     nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0;\r
1266     MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) );\r
1267 \r
1268 cleanup:\r
1269     mbedtls_mpi_free( &mQY );\r
1270 \r
1271     return( ret );\r
1272 }\r
1273 \r
1274 /*\r
1275  * Point doubling R = 2 P, Jacobian coordinates\r
1276  *\r
1277  * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .\r
1278  *\r
1279  * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR\r
1280  * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.\r
1281  *\r
1282  * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.\r
1283  *\r
1284  * Cost: 1D := 3M + 4S          (A ==  0)\r
1285  *             4M + 4S          (A == -3)\r
1286  *             3M + 6S + 1a     otherwise\r
1287  */\r
1288 static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,\r
1289                            const mbedtls_ecp_point *P )\r
1290 {\r
1291     int ret;\r
1292     mbedtls_mpi M, S, T, U;\r
1293 \r
1294 #if defined(MBEDTLS_SELF_TEST)\r
1295     dbl_count++;\r
1296 #endif\r
1297 \r
1298 #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)\r
1299     if( mbedtls_internal_ecp_grp_capable( grp ) )\r
1300         return( mbedtls_internal_ecp_double_jac( grp, R, P ) );\r
1301 #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */\r
1302 \r
1303     mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U );\r
1304 \r
1305     /* Special case for A = -3 */\r
1306     if( grp->A.p == NULL )\r
1307     {\r
1308         /* M = 3(X + Z^2)(X - Z^2) */\r
1309         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &P->Z,  &P->Z   ) ); MOD_MUL( S );\r
1310         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T,  &P->X,  &S      ) ); MOD_ADD( T );\r
1311         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U,  &P->X,  &S      ) ); MOD_SUB( U );\r
1312         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &T,     &U      ) ); MOD_MUL( S );\r
1313         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M,  &S,     3       ) ); MOD_ADD( M );\r
1314     }\r
1315     else\r
1316     {\r
1317         /* M = 3.X^2 */\r
1318         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &P->X,  &P->X   ) ); MOD_MUL( S );\r
1319         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M,  &S,     3       ) ); MOD_ADD( M );\r
1320 \r
1321         /* Optimize away for "koblitz" curves with A = 0 */\r
1322         if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 )\r
1323         {\r
1324             /* M += A.Z^4 */\r
1325             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &P->Z,  &P->Z   ) ); MOD_MUL( S );\r
1326             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T,  &S,     &S      ) ); MOD_MUL( T );\r
1327             MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &T,     &grp->A ) ); MOD_MUL( S );\r
1328             MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M,  &M,     &S      ) ); MOD_ADD( M );\r
1329         }\r
1330     }\r
1331 \r
1332     /* S = 4.X.Y^2 */\r
1333     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T,  &P->Y,  &P->Y   ) ); MOD_MUL( T );\r
1334     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T,  1               ) ); MOD_ADD( T );\r
1335     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &P->X,  &T      ) ); MOD_MUL( S );\r
1336     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S,  1               ) ); MOD_ADD( S );\r
1337 \r
1338     /* U = 8.Y^4 */\r
1339     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U,  &T,     &T      ) ); MOD_MUL( U );\r
1340     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U,  1               ) ); MOD_ADD( U );\r
1341 \r
1342     /* T = M^2 - 2.S */\r
1343     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T,  &M,     &M      ) ); MOD_MUL( T );\r
1344     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T,  &T,     &S      ) ); MOD_SUB( T );\r
1345     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T,  &T,     &S      ) ); MOD_SUB( T );\r
1346 \r
1347     /* S = M(S - T) - U */\r
1348     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S,  &S,     &T      ) ); MOD_SUB( S );\r
1349     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &S,     &M      ) ); MOD_MUL( S );\r
1350     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S,  &S,     &U      ) ); MOD_SUB( S );\r
1351 \r
1352     /* U = 2.Y.Z */\r
1353     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U,  &P->Y,  &P->Z   ) ); MOD_MUL( U );\r
1354     MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U,  1               ) ); MOD_ADD( U );\r
1355 \r
1356     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) );\r
1357     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) );\r
1358     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) );\r
1359 \r
1360 cleanup:\r
1361     mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U );\r
1362 \r
1363     return( ret );\r
1364 }\r
1365 \r
1366 /*\r
1367  * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)\r
1368  *\r
1369  * The coordinates of Q must be normalized (= affine),\r
1370  * but those of P don't need to. R is not normalized.\r
1371  *\r
1372  * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.\r
1373  * None of these cases can happen as intermediate step in ecp_mul_comb():\r
1374  * - at each step, P, Q and R are multiples of the base point, the factor\r
1375  *   being less than its order, so none of them is zero;\r
1376  * - Q is an odd multiple of the base point, P an even multiple,\r
1377  *   due to the choice of precomputed points in the modified comb method.\r
1378  * So branches for these cases do not leak secret information.\r
1379  *\r
1380  * We accept Q->Z being unset (saving memory in tables) as meaning 1.\r
1381  *\r
1382  * Cost: 1A := 8M + 3S\r
1383  */\r
1384 static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,\r
1385                           const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )\r
1386 {\r
1387     int ret;\r
1388     mbedtls_mpi T1, T2, T3, T4, X, Y, Z;\r
1389 \r
1390 #if defined(MBEDTLS_SELF_TEST)\r
1391     add_count++;\r
1392 #endif\r
1393 \r
1394 #if defined(MBEDTLS_ECP_ADD_MIXED_ALT)\r
1395     if( mbedtls_internal_ecp_grp_capable( grp ) )\r
1396         return( mbedtls_internal_ecp_add_mixed( grp, R, P, Q ) );\r
1397 #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */\r
1398 \r
1399     /*\r
1400      * Trivial cases: P == 0 or Q == 0 (case 1)\r
1401      */\r
1402     if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )\r
1403         return( mbedtls_ecp_copy( R, Q ) );\r
1404 \r
1405     if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 )\r
1406         return( mbedtls_ecp_copy( R, P ) );\r
1407 \r
1408     /*\r
1409      * Make sure Q coordinates are normalized\r
1410      */\r
1411     if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 )\r
1412         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
1413 \r
1414     mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 );\r
1415     mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );\r
1416 \r
1417     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1,  &P->Z,  &P->Z ) );  MOD_MUL( T1 );\r
1418     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2,  &T1,    &P->Z ) );  MOD_MUL( T2 );\r
1419     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1,  &T1,    &Q->X ) );  MOD_MUL( T1 );\r
1420     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2,  &T2,    &Q->Y ) );  MOD_MUL( T2 );\r
1421     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1,  &T1,    &P->X ) );  MOD_SUB( T1 );\r
1422     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2,  &T2,    &P->Y ) );  MOD_SUB( T2 );\r
1423 \r
1424     /* Special cases (2) and (3) */\r
1425     if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 )\r
1426     {\r
1427         if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 )\r
1428         {\r
1429             ret = ecp_double_jac( grp, R, P );\r
1430             goto cleanup;\r
1431         }\r
1432         else\r
1433         {\r
1434             ret = mbedtls_ecp_set_zero( R );\r
1435             goto cleanup;\r
1436         }\r
1437     }\r
1438 \r
1439     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z,   &P->Z,  &T1   ) );  MOD_MUL( Z  );\r
1440     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3,  &T1,    &T1   ) );  MOD_MUL( T3 );\r
1441     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4,  &T3,    &T1   ) );  MOD_MUL( T4 );\r
1442     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3,  &T3,    &P->X ) );  MOD_MUL( T3 );\r
1443     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1,  &T3,    2     ) );  MOD_ADD( T1 );\r
1444     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X,   &T2,    &T2   ) );  MOD_MUL( X  );\r
1445     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X,   &X,     &T1   ) );  MOD_SUB( X  );\r
1446     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X,   &X,     &T4   ) );  MOD_SUB( X  );\r
1447     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3,  &T3,    &X    ) );  MOD_SUB( T3 );\r
1448     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3,  &T3,    &T2   ) );  MOD_MUL( T3 );\r
1449     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4,  &T4,    &P->Y ) );  MOD_MUL( T4 );\r
1450     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y,   &T3,    &T4   ) );  MOD_SUB( Y  );\r
1451 \r
1452     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) );\r
1453     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) );\r
1454     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) );\r
1455 \r
1456 cleanup:\r
1457 \r
1458     mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 );\r
1459     mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );\r
1460 \r
1461     return( ret );\r
1462 }\r
1463 \r
1464 /*\r
1465  * Randomize jacobian coordinates:\r
1466  * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l\r
1467  * This is sort of the reverse operation of ecp_normalize_jac().\r
1468  *\r
1469  * This countermeasure was first suggested in [2].\r
1470  */\r
1471 static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,\r
1472                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )\r
1473 {\r
1474     int ret;\r
1475     mbedtls_mpi l, ll;\r
1476     size_t p_size;\r
1477     int count = 0;\r
1478 \r
1479 #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)\r
1480     if( mbedtls_internal_ecp_grp_capable( grp ) )\r
1481         return( mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng ) );\r
1482 #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */\r
1483 \r
1484     p_size = ( grp->pbits + 7 ) / 8;\r
1485     mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll );\r
1486 \r
1487     /* Generate l such that 1 < l < p */\r
1488     do\r
1489     {\r
1490         MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );\r
1491 \r
1492         while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )\r
1493             MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );\r
1494 \r
1495         if( count++ > 10 )\r
1496             return( MBEDTLS_ERR_ECP_RANDOM_FAILED );\r
1497     }\r
1498     while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );\r
1499 \r
1500     /* Z = l * Z */\r
1501     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z,   &pt->Z,     &l  ) ); MOD_MUL( pt->Z );\r
1502 \r
1503     /* X = l^2 * X */\r
1504     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll,      &l,         &l  ) ); MOD_MUL( ll );\r
1505     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X,   &pt->X,     &ll ) ); MOD_MUL( pt->X );\r
1506 \r
1507     /* Y = l^3 * Y */\r
1508     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll,      &ll,        &l  ) ); MOD_MUL( ll );\r
1509     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y,   &pt->Y,     &ll ) ); MOD_MUL( pt->Y );\r
1510 \r
1511 cleanup:\r
1512     mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll );\r
1513 \r
1514     return( ret );\r
1515 }\r
1516 \r
1517 /*\r
1518  * Check and define parameters used by the comb method (see below for details)\r
1519  */\r
1520 #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7\r
1521 #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"\r
1522 #endif\r
1523 \r
1524 /* d = ceil( n / w ) */\r
1525 #define COMB_MAX_D      ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2\r
1526 \r
1527 /* number of precomputed points */\r
1528 #define COMB_MAX_PRE    ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) )\r
1529 \r
1530 /*\r
1531  * Compute the representation of m that will be used with our comb method.\r
1532  *\r
1533  * The basic comb method is described in GECC 3.44 for example. We use a\r
1534  * modified version that provides resistance to SPA by avoiding zero\r
1535  * digits in the representation as in [3]. We modify the method further by\r
1536  * requiring that all K_i be odd, which has the small cost that our\r
1537  * representation uses one more K_i, due to carries, but saves on the size of\r
1538  * the precomputed table.\r
1539  *\r
1540  * Summary of the comb method and its modifications:\r
1541  *\r
1542  * - The goal is to compute m*P for some w*d-bit integer m.\r
1543  *\r
1544  * - The basic comb method splits m into the w-bit integers\r
1545  *   x[0] .. x[d-1] where x[i] consists of the bits in m whose\r
1546  *   index has residue i modulo d, and computes m * P as\r
1547  *   S[x[0]] + 2 * S[x[1]] + .. + 2^(d-1) S[x[d-1]], where\r
1548  *   S[i_{w-1} .. i_0] := i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + i_0 P.\r
1549  *\r
1550  * - If it happens that, say, x[i+1]=0 (=> S[x[i+1]]=0), one can replace the sum by\r
1551  *    .. + 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]] ..,\r
1552  *   thereby successively converting it into a form where all summands\r
1553  *   are nonzero, at the cost of negative summands. This is the basic idea of [3].\r
1554  *\r
1555  * - More generally, even if x[i+1] != 0, we can first transform the sum as\r
1556  *   .. - 2^i S[x[i]] + 2^{i+1} ( S[x[i]] + S[x[i+1]] ) + 2^{i+2} S[x[i+2]] ..,\r
1557  *   and then replace S[x[i]] + S[x[i+1]] = S[x[i] ^ x[i+1]] + 2 S[x[i] & x[i+1]].\r
1558  *   Performing and iterating this procedure for those x[i] that are even\r
1559  *   (keeping track of carry), we can transform the original sum into one of the form\r
1560  *   S[x'[0]] +- 2 S[x'[1]] +- .. +- 2^{d-1} S[x'[d-1]] + 2^d S[x'[d]]\r
1561  *   with all x'[i] odd. It is therefore only necessary to know S at odd indices,\r
1562  *   which is why we are only computing half of it in the first place in\r
1563  *   ecp_precompute_comb and accessing it with index abs(i) / 2 in ecp_select_comb.\r
1564  *\r
1565  * - For the sake of compactness, only the seven low-order bits of x[i]\r
1566  *   are used to represent its absolute value (K_i in the paper), and the msb\r
1567  *   of x[i] encodes the sign (s_i in the paper): it is set if and only if\r
1568  *   if s_i == -1;\r
1569  *\r
1570  * Calling conventions:\r
1571  * - x is an array of size d + 1\r
1572  * - w is the size, ie number of teeth, of the comb, and must be between\r
1573  *   2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE)\r
1574  * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d\r
1575  *   (the result will be incorrect if these assumptions are not satisfied)\r
1576  */\r
1577 static void ecp_comb_recode_core( unsigned char x[], size_t d,\r
1578                                   unsigned char w, const mbedtls_mpi *m )\r
1579 {\r
1580     size_t i, j;\r
1581     unsigned char c, cc, adjust;\r
1582 \r
1583     memset( x, 0, d+1 );\r
1584 \r
1585     /* First get the classical comb values (except for x_d = 0) */\r
1586     for( i = 0; i < d; i++ )\r
1587         for( j = 0; j < w; j++ )\r
1588             x[i] |= mbedtls_mpi_get_bit( m, i + d * j ) << j;\r
1589 \r
1590     /* Now make sure x_1 .. x_d are odd */\r
1591     c = 0;\r
1592     for( i = 1; i <= d; i++ )\r
1593     {\r
1594         /* Add carry and update it */\r
1595         cc   = x[i] & c;\r
1596         x[i] = x[i] ^ c;\r
1597         c = cc;\r
1598 \r
1599         /* Adjust if needed, avoiding branches */\r
1600         adjust = 1 - ( x[i] & 0x01 );\r
1601         c   |= x[i] & ( x[i-1] * adjust );\r
1602         x[i] = x[i] ^ ( x[i-1] * adjust );\r
1603         x[i-1] |= adjust << 7;\r
1604     }\r
1605 }\r
1606 \r
1607 /*\r
1608  * Precompute points for the adapted comb method\r
1609  *\r
1610  * Assumption: T must be able to hold 2^{w - 1} elements.\r
1611  *\r
1612  * Operation: If i = i_{w-1} ... i_1 is the binary representation of i,\r
1613  *            sets T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P.\r
1614  *\r
1615  * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)\r
1616  *\r
1617  * Note: Even comb values (those where P would be omitted from the\r
1618  *       sum defining T[i] above) are not needed in our adaption\r
1619  *       the comb method. See ecp_comb_recode_core().\r
1620  *\r
1621  * This function currently works in four steps:\r
1622  * (1) [dbl]      Computation of intermediate T[i] for 2-power values of i\r
1623  * (2) [norm_dbl] Normalization of coordinates of these T[i]\r
1624  * (3) [add]      Computation of all T[i]\r
1625  * (4) [norm_add] Normalization of all T[i]\r
1626  *\r
1627  * Step 1 can be interrupted but not the others; together with the final\r
1628  * coordinate normalization they are the largest steps done at once, depending\r
1629  * on the window size. Here are operation counts for P-256:\r
1630  *\r
1631  * step     (2)     (3)     (4)\r
1632  * w = 5    142     165     208\r
1633  * w = 4    136      77     160\r
1634  * w = 3    130      33     136\r
1635  * w = 2    124      11     124\r
1636  *\r
1637  * So if ECC operations are blocking for too long even with a low max_ops\r
1638  * value, it's useful to set MBEDTLS_ECP_WINDOW_SIZE to a lower value in order\r
1639  * to minimize maximum blocking time.\r
1640  */\r
1641 static int ecp_precompute_comb( const mbedtls_ecp_group *grp,\r
1642                                 mbedtls_ecp_point T[], const mbedtls_ecp_point *P,\r
1643                                 unsigned char w, size_t d,\r
1644                                 mbedtls_ecp_restart_ctx *rs_ctx )\r
1645 {\r
1646     int ret;\r
1647     unsigned char i;\r
1648     size_t j = 0;\r
1649     const unsigned char T_size = 1U << ( w - 1 );\r
1650     mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1];\r
1651 \r
1652 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1653     if( rs_ctx != NULL && rs_ctx->rsm != NULL )\r
1654     {\r
1655         if( rs_ctx->rsm->state == ecp_rsm_pre_dbl )\r
1656             goto dbl;\r
1657         if( rs_ctx->rsm->state == ecp_rsm_pre_norm_dbl )\r
1658             goto norm_dbl;\r
1659         if( rs_ctx->rsm->state == ecp_rsm_pre_add )\r
1660             goto add;\r
1661         if( rs_ctx->rsm->state == ecp_rsm_pre_norm_add )\r
1662             goto norm_add;\r
1663     }\r
1664 #else\r
1665     (void) rs_ctx;\r
1666 #endif\r
1667 \r
1668 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1669     if( rs_ctx != NULL && rs_ctx->rsm != NULL )\r
1670     {\r
1671         rs_ctx->rsm->state = ecp_rsm_pre_dbl;\r
1672 \r
1673         /* initial state for the loop */\r
1674         rs_ctx->rsm->i = 0;\r
1675     }\r
1676 \r
1677 dbl:\r
1678 #endif\r
1679     /*\r
1680      * Set T[0] = P and\r
1681      * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)\r
1682      */\r
1683     MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) );\r
1684 \r
1685 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1686     if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0 )\r
1687         j = rs_ctx->rsm->i;\r
1688     else\r
1689 #endif\r
1690         j = 0;\r
1691 \r
1692     for( ; j < d * ( w - 1 ); j++ )\r
1693     {\r
1694         MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL );\r
1695 \r
1696         i = 1U << ( j / d );\r
1697         cur = T + i;\r
1698 \r
1699         if( j % d == 0 )\r
1700             MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) );\r
1701 \r
1702         MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) );\r
1703     }\r
1704 \r
1705 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1706     if( rs_ctx != NULL && rs_ctx->rsm != NULL )\r
1707         rs_ctx->rsm->state = ecp_rsm_pre_norm_dbl;\r
1708 \r
1709 norm_dbl:\r
1710 #endif\r
1711     /*\r
1712      * Normalize current elements in T. As T has holes,\r
1713      * use an auxiliary array of pointers to elements in T.\r
1714      */\r
1715     j = 0;\r
1716     for( i = 1; i < T_size; i <<= 1 )\r
1717         TT[j++] = T + i;\r
1718 \r
1719     MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 );\r
1720 \r
1721     MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) );\r
1722 \r
1723 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1724     if( rs_ctx != NULL && rs_ctx->rsm != NULL )\r
1725         rs_ctx->rsm->state = ecp_rsm_pre_add;\r
1726 \r
1727 add:\r
1728 #endif\r
1729     /*\r
1730      * Compute the remaining ones using the minimal number of additions\r
1731      * Be careful to update T[2^l] only after using it!\r
1732      */\r
1733     MBEDTLS_ECP_BUDGET( ( T_size - 1 ) * MBEDTLS_ECP_OPS_ADD );\r
1734 \r
1735     for( i = 1; i < T_size; i <<= 1 )\r
1736     {\r
1737         j = i;\r
1738         while( j-- )\r
1739             MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );\r
1740     }\r
1741 \r
1742 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1743     if( rs_ctx != NULL && rs_ctx->rsm != NULL )\r
1744         rs_ctx->rsm->state = ecp_rsm_pre_norm_add;\r
1745 \r
1746 norm_add:\r
1747 #endif\r
1748     /*\r
1749      * Normalize final elements in T. Even though there are no holes now, we\r
1750      * still need the auxiliary array for homogeneity with the previous\r
1751      * call. Also, skip T[0] which is already normalised, being a copy of P.\r
1752      */\r
1753     for( j = 0; j + 1 < T_size; j++ )\r
1754         TT[j] = T + j + 1;\r
1755 \r
1756     MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 );\r
1757 \r
1758     MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) );\r
1759 \r
1760 cleanup:\r
1761 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1762     if( rs_ctx != NULL && rs_ctx->rsm != NULL &&\r
1763         ret == MBEDTLS_ERR_ECP_IN_PROGRESS )\r
1764     {\r
1765         if( rs_ctx->rsm->state == ecp_rsm_pre_dbl )\r
1766             rs_ctx->rsm->i = j;\r
1767     }\r
1768 #endif\r
1769 \r
1770     return( ret );\r
1771 }\r
1772 \r
1773 /*\r
1774  * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]\r
1775  *\r
1776  * See ecp_comb_recode_core() for background\r
1777  */\r
1778 static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,\r
1779                             const mbedtls_ecp_point T[], unsigned char T_size,\r
1780                             unsigned char i )\r
1781 {\r
1782     int ret;\r
1783     unsigned char ii, j;\r
1784 \r
1785     /* Ignore the "sign" bit and scale down */\r
1786     ii =  ( i & 0x7Fu ) >> 1;\r
1787 \r
1788     /* Read the whole table to thwart cache-based timing attacks */\r
1789     for( j = 0; j < T_size; j++ )\r
1790     {\r
1791         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) );\r
1792         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) );\r
1793     }\r
1794 \r
1795     /* Safely invert result if i is "negative" */\r
1796     MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );\r
1797 \r
1798 cleanup:\r
1799     return( ret );\r
1800 }\r
1801 \r
1802 /*\r
1803  * Core multiplication algorithm for the (modified) comb method.\r
1804  * This part is actually common with the basic comb method (GECC 3.44)\r
1805  *\r
1806  * Cost: d A + d D + 1 R\r
1807  */\r
1808 static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,\r
1809                               const mbedtls_ecp_point T[], unsigned char T_size,\r
1810                               const unsigned char x[], size_t d,\r
1811                               int (*f_rng)(void *, unsigned char *, size_t),\r
1812                               void *p_rng,\r
1813                               mbedtls_ecp_restart_ctx *rs_ctx )\r
1814 {\r
1815     int ret;\r
1816     mbedtls_ecp_point Txi;\r
1817     size_t i;\r
1818 \r
1819     mbedtls_ecp_point_init( &Txi );\r
1820 \r
1821 #if !defined(MBEDTLS_ECP_RESTARTABLE)\r
1822     (void) rs_ctx;\r
1823 #endif\r
1824 \r
1825 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1826     if( rs_ctx != NULL && rs_ctx->rsm != NULL &&\r
1827         rs_ctx->rsm->state != ecp_rsm_comb_core )\r
1828     {\r
1829         rs_ctx->rsm->i = 0;\r
1830         rs_ctx->rsm->state = ecp_rsm_comb_core;\r
1831     }\r
1832 \r
1833     /* new 'if' instead of nested for the sake of the 'else' branch */\r
1834     if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0 )\r
1835     {\r
1836         /* restore current index (R already pointing to rs_ctx->rsm->R) */\r
1837         i = rs_ctx->rsm->i;\r
1838     }\r
1839     else\r
1840 #endif\r
1841     {\r
1842         /* Start with a non-zero point and randomize its coordinates */\r
1843         i = d;\r
1844         MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, T_size, x[i] ) );\r
1845         MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 1 ) );\r
1846         if( f_rng != 0 )\r
1847             MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );\r
1848     }\r
1849 \r
1850     while( i != 0 )\r
1851     {\r
1852         MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD );\r
1853         --i;\r
1854 \r
1855         MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) );\r
1856         MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, T_size, x[i] ) );\r
1857         MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );\r
1858     }\r
1859 \r
1860 cleanup:\r
1861 \r
1862     mbedtls_ecp_point_free( &Txi );\r
1863 \r
1864 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1865     if( rs_ctx != NULL && rs_ctx->rsm != NULL &&\r
1866         ret == MBEDTLS_ERR_ECP_IN_PROGRESS )\r
1867     {\r
1868         rs_ctx->rsm->i = i;\r
1869         /* no need to save R, already pointing to rs_ctx->rsm->R */\r
1870     }\r
1871 #endif\r
1872 \r
1873     return( ret );\r
1874 }\r
1875 \r
1876 /*\r
1877  * Recode the scalar to get constant-time comb multiplication\r
1878  *\r
1879  * As the actual scalar recoding needs an odd scalar as a starting point,\r
1880  * this wrapper ensures that by replacing m by N - m if necessary, and\r
1881  * informs the caller that the result of multiplication will be negated.\r
1882  *\r
1883  * This works because we only support large prime order for Short Weierstrass\r
1884  * curves, so N is always odd hence either m or N - m is.\r
1885  *\r
1886  * See ecp_comb_recode_core() for background.\r
1887  */\r
1888 static int ecp_comb_recode_scalar( const mbedtls_ecp_group *grp,\r
1889                                    const mbedtls_mpi *m,\r
1890                                    unsigned char k[COMB_MAX_D + 1],\r
1891                                    size_t d,\r
1892                                    unsigned char w,\r
1893                                    unsigned char *parity_trick )\r
1894 {\r
1895     int ret;\r
1896     mbedtls_mpi M, mm;\r
1897 \r
1898     mbedtls_mpi_init( &M );\r
1899     mbedtls_mpi_init( &mm );\r
1900 \r
1901     /* N is always odd (see above), just make extra sure */\r
1902     if( mbedtls_mpi_get_bit( &grp->N, 0 ) != 1 )\r
1903         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
1904 \r
1905     /* do we need the parity trick? */\r
1906     *parity_trick = ( mbedtls_mpi_get_bit( m, 0 ) == 0 );\r
1907 \r
1908     /* execute parity fix in constant time */\r
1909     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) );\r
1910     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N, m ) );\r
1911     MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, *parity_trick ) );\r
1912 \r
1913     /* actual scalar recoding */\r
1914     ecp_comb_recode_core( k, d, w, &M );\r
1915 \r
1916 cleanup:\r
1917     mbedtls_mpi_free( &mm );\r
1918     mbedtls_mpi_free( &M );\r
1919 \r
1920     return( ret );\r
1921 }\r
1922 \r
1923 /*\r
1924  * Perform comb multiplication (for short Weierstrass curves)\r
1925  * once the auxiliary table has been pre-computed.\r
1926  *\r
1927  * Scalar recoding may use a parity trick that makes us compute -m * P,\r
1928  * if that is the case we'll need to recover m * P at the end.\r
1929  */\r
1930 static int ecp_mul_comb_after_precomp( const mbedtls_ecp_group *grp,\r
1931                                 mbedtls_ecp_point *R,\r
1932                                 const mbedtls_mpi *m,\r
1933                                 const mbedtls_ecp_point *T,\r
1934                                 unsigned char T_size,\r
1935                                 unsigned char w,\r
1936                                 size_t d,\r
1937                                 int (*f_rng)(void *, unsigned char *, size_t),\r
1938                                 void *p_rng,\r
1939                                 mbedtls_ecp_restart_ctx *rs_ctx )\r
1940 {\r
1941     int ret;\r
1942     unsigned char parity_trick;\r
1943     unsigned char k[COMB_MAX_D + 1];\r
1944     mbedtls_ecp_point *RR = R;\r
1945 \r
1946 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1947     if( rs_ctx != NULL && rs_ctx->rsm != NULL )\r
1948     {\r
1949         RR = &rs_ctx->rsm->R;\r
1950 \r
1951         if( rs_ctx->rsm->state == ecp_rsm_final_norm )\r
1952             goto final_norm;\r
1953     }\r
1954 #endif\r
1955 \r
1956     MBEDTLS_MPI_CHK( ecp_comb_recode_scalar( grp, m, k, d, w,\r
1957                                             &parity_trick ) );\r
1958     MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, RR, T, T_size, k, d,\r
1959                                         f_rng, p_rng, rs_ctx ) );\r
1960     MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, RR, parity_trick ) );\r
1961 \r
1962 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1963     if( rs_ctx != NULL && rs_ctx->rsm != NULL )\r
1964         rs_ctx->rsm->state = ecp_rsm_final_norm;\r
1965 \r
1966 final_norm:\r
1967 #endif\r
1968     MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV );\r
1969     MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, RR ) );\r
1970 \r
1971 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
1972     if( rs_ctx != NULL && rs_ctx->rsm != NULL )\r
1973         MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, RR ) );\r
1974 #endif\r
1975 \r
1976 cleanup:\r
1977     return( ret );\r
1978 }\r
1979 \r
1980 /*\r
1981  * Pick window size based on curve size and whether we optimize for base point\r
1982  */\r
1983 static unsigned char ecp_pick_window_size( const mbedtls_ecp_group *grp,\r
1984                                            unsigned char p_eq_g )\r
1985 {\r
1986     unsigned char w;\r
1987 \r
1988     /*\r
1989      * Minimize the number of multiplications, that is minimize\r
1990      * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )\r
1991      * (see costs of the various parts, with 1S = 1M)\r
1992      */\r
1993     w = grp->nbits >= 384 ? 5 : 4;\r
1994 \r
1995     /*\r
1996      * If P == G, pre-compute a bit more, since this may be re-used later.\r
1997      * Just adding one avoids upping the cost of the first mul too much,\r
1998      * and the memory cost too.\r
1999      */\r
2000     if( p_eq_g )\r
2001         w++;\r
2002 \r
2003     /*\r
2004      * Make sure w is within bounds.\r
2005      * (The last test is useful only for very small curves in the test suite.)\r
2006      */\r
2007     if( w > MBEDTLS_ECP_WINDOW_SIZE )\r
2008         w = MBEDTLS_ECP_WINDOW_SIZE;\r
2009     if( w >= grp->nbits )\r
2010         w = 2;\r
2011 \r
2012     return( w );\r
2013 }\r
2014 \r
2015 /*\r
2016  * Multiplication using the comb method - for curves in short Weierstrass form\r
2017  *\r
2018  * This function is mainly responsible for administrative work:\r
2019  * - managing the restart context if enabled\r
2020  * - managing the table of precomputed points (passed between the below two\r
2021  *   functions): allocation, computation, ownership tranfer, freeing.\r
2022  *\r
2023  * It delegates the actual arithmetic work to:\r
2024  *      ecp_precompute_comb() and ecp_mul_comb_with_precomp()\r
2025  *\r
2026  * See comments on ecp_comb_recode_core() regarding the computation strategy.\r
2027  */\r
2028 static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,\r
2029                          const mbedtls_mpi *m, const mbedtls_ecp_point *P,\r
2030                          int (*f_rng)(void *, unsigned char *, size_t),\r
2031                          void *p_rng,\r
2032                          mbedtls_ecp_restart_ctx *rs_ctx )\r
2033 {\r
2034     int ret;\r
2035     unsigned char w, p_eq_g, i;\r
2036     size_t d;\r
2037     unsigned char T_size, T_ok;\r
2038     mbedtls_ecp_point *T;\r
2039 \r
2040     ECP_RS_ENTER( rsm );\r
2041 \r
2042     /* Is P the base point ? */\r
2043 #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1\r
2044     p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&\r
2045                mbedtls_mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 );\r
2046 #else\r
2047     p_eq_g = 0;\r
2048 #endif\r
2049 \r
2050     /* Pick window size and deduce related sizes */\r
2051     w = ecp_pick_window_size( grp, p_eq_g );\r
2052     T_size = 1U << ( w - 1 );\r
2053     d = ( grp->nbits + w - 1 ) / w;\r
2054 \r
2055     /* Pre-computed table: do we have it already for the base point? */\r
2056     if( p_eq_g && grp->T != NULL )\r
2057     {\r
2058         /* second pointer to the same table, will be deleted on exit */\r
2059         T = grp->T;\r
2060         T_ok = 1;\r
2061     }\r
2062     else\r
2063 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
2064     /* Pre-computed table: do we have one in progress? complete? */\r
2065     if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->T != NULL )\r
2066     {\r
2067         /* transfer ownership of T from rsm to local function */\r
2068         T = rs_ctx->rsm->T;\r
2069         rs_ctx->rsm->T = NULL;\r
2070         rs_ctx->rsm->T_size = 0;\r
2071 \r
2072         /* This effectively jumps to the call to mul_comb_after_precomp() */\r
2073         T_ok = rs_ctx->rsm->state >= ecp_rsm_comb_core;\r
2074     }\r
2075     else\r
2076 #endif\r
2077     /* Allocate table if we didn't have any */\r
2078     {\r
2079         T = mbedtls_calloc( T_size, sizeof( mbedtls_ecp_point ) );\r
2080         if( T == NULL )\r
2081         {\r
2082             ret = MBEDTLS_ERR_ECP_ALLOC_FAILED;\r
2083             goto cleanup;\r
2084         }\r
2085 \r
2086         for( i = 0; i < T_size; i++ )\r
2087             mbedtls_ecp_point_init( &T[i] );\r
2088 \r
2089         T_ok = 0;\r
2090     }\r
2091 \r
2092     /* Compute table (or finish computing it) if not done already */\r
2093     if( !T_ok )\r
2094     {\r
2095         MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d, rs_ctx ) );\r
2096 \r
2097         if( p_eq_g )\r
2098         {\r
2099             /* almost transfer ownership of T to the group, but keep a copy of\r
2100              * the pointer to use for calling the next function more easily */\r
2101             grp->T = T;\r
2102             grp->T_size = T_size;\r
2103         }\r
2104     }\r
2105 \r
2106     /* Actual comb multiplication using precomputed points */\r
2107     MBEDTLS_MPI_CHK( ecp_mul_comb_after_precomp( grp, R, m,\r
2108                                                  T, T_size, w, d,\r
2109                                                  f_rng, p_rng, rs_ctx ) );\r
2110 \r
2111 cleanup:\r
2112 \r
2113     /* does T belong to the group? */\r
2114     if( T == grp->T )\r
2115         T = NULL;\r
2116 \r
2117     /* does T belong to the restart context? */\r
2118 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
2119     if( rs_ctx != NULL && rs_ctx->rsm != NULL && ret == MBEDTLS_ERR_ECP_IN_PROGRESS && T != NULL )\r
2120     {\r
2121         /* transfer ownership of T from local function to rsm */\r
2122         rs_ctx->rsm->T_size = T_size;\r
2123         rs_ctx->rsm->T = T;\r
2124         T = NULL;\r
2125     }\r
2126 #endif\r
2127 \r
2128     /* did T belong to us? then let's destroy it! */\r
2129     if( T != NULL )\r
2130     {\r
2131         for( i = 0; i < T_size; i++ )\r
2132             mbedtls_ecp_point_free( &T[i] );\r
2133         mbedtls_free( T );\r
2134     }\r
2135 \r
2136     /* don't free R while in progress in case R == P */\r
2137 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
2138     if( ret != MBEDTLS_ERR_ECP_IN_PROGRESS )\r
2139 #endif\r
2140     /* prevent caller from using invalid value */\r
2141     if( ret != 0 )\r
2142         mbedtls_ecp_point_free( R );\r
2143 \r
2144     ECP_RS_LEAVE( rsm );\r
2145 \r
2146     return( ret );\r
2147 }\r
2148 \r
2149 #endif /* ECP_SHORTWEIERSTRASS */\r
2150 \r
2151 #if defined(ECP_MONTGOMERY)\r
2152 /*\r
2153  * For Montgomery curves, we do all the internal arithmetic in projective\r
2154  * coordinates. Import/export of points uses only the x coordinates, which is\r
2155  * internaly represented as X / Z.\r
2156  *\r
2157  * For scalar multiplication, we'll use a Montgomery ladder.\r
2158  */\r
2159 \r
2160 /*\r
2161  * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1\r
2162  * Cost: 1M + 1I\r
2163  */\r
2164 static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P )\r
2165 {\r
2166     int ret;\r
2167 \r
2168 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)\r
2169     if( mbedtls_internal_ecp_grp_capable( grp ) )\r
2170         return( mbedtls_internal_ecp_normalize_mxz( grp, P ) );\r
2171 #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */\r
2172 \r
2173     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) );\r
2174     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X );\r
2175     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );\r
2176 \r
2177 cleanup:\r
2178     return( ret );\r
2179 }\r
2180 \r
2181 /*\r
2182  * Randomize projective x/z coordinates:\r
2183  * (X, Z) -> (l X, l Z) for random l\r
2184  * This is sort of the reverse operation of ecp_normalize_mxz().\r
2185  *\r
2186  * This countermeasure was first suggested in [2].\r
2187  * Cost: 2M\r
2188  */\r
2189 static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P,\r
2190                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )\r
2191 {\r
2192     int ret;\r
2193     mbedtls_mpi l;\r
2194     size_t p_size;\r
2195     int count = 0;\r
2196 \r
2197 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)\r
2198     if( mbedtls_internal_ecp_grp_capable( grp ) )\r
2199         return( mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng );\r
2200 #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */\r
2201 \r
2202     p_size = ( grp->pbits + 7 ) / 8;\r
2203     mbedtls_mpi_init( &l );\r
2204 \r
2205     /* Generate l such that 1 < l < p */\r
2206     do\r
2207     {\r
2208         MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );\r
2209 \r
2210         while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )\r
2211             MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );\r
2212 \r
2213         if( count++ > 10 )\r
2214             return( MBEDTLS_ERR_ECP_RANDOM_FAILED );\r
2215     }\r
2216     while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );\r
2217 \r
2218     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X );\r
2219     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z );\r
2220 \r
2221 cleanup:\r
2222     mbedtls_mpi_free( &l );\r
2223 \r
2224     return( ret );\r
2225 }\r
2226 \r
2227 /*\r
2228  * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),\r
2229  * for Montgomery curves in x/z coordinates.\r
2230  *\r
2231  * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3\r
2232  * with\r
2233  * d =  X1\r
2234  * P = (X2, Z2)\r
2235  * Q = (X3, Z3)\r
2236  * R = (X4, Z4)\r
2237  * S = (X5, Z5)\r
2238  * and eliminating temporary variables tO, ..., t4.\r
2239  *\r
2240  * Cost: 5M + 4S\r
2241  */\r
2242 static int ecp_double_add_mxz( const mbedtls_ecp_group *grp,\r
2243                                mbedtls_ecp_point *R, mbedtls_ecp_point *S,\r
2244                                const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q,\r
2245                                const mbedtls_mpi *d )\r
2246 {\r
2247     int ret;\r
2248     mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB;\r
2249 \r
2250 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)\r
2251     if( mbedtls_internal_ecp_grp_capable( grp ) )\r
2252         return( mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d ) );\r
2253 #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */\r
2254 \r
2255     mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B );\r
2256     mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C );\r
2257     mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB );\r
2258 \r
2259     MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A,    &P->X,   &P->Z ) ); MOD_ADD( A    );\r
2260     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA,   &A,      &A    ) ); MOD_MUL( AA   );\r
2261     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B,    &P->X,   &P->Z ) ); MOD_SUB( B    );\r
2262     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB,   &B,      &B    ) ); MOD_MUL( BB   );\r
2263     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E,    &AA,     &BB   ) ); MOD_SUB( E    );\r
2264     MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C,    &Q->X,   &Q->Z ) ); MOD_ADD( C    );\r
2265     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D,    &Q->X,   &Q->Z ) ); MOD_SUB( D    );\r
2266     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA,   &D,      &A    ) ); MOD_MUL( DA   );\r
2267     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB,   &C,      &B    ) ); MOD_MUL( CB   );\r
2268     MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X, &DA,     &CB   ) ); MOD_MUL( S->X );\r
2269     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X, &S->X,   &S->X ) ); MOD_MUL( S->X );\r
2270     MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z, &DA,     &CB   ) ); MOD_SUB( S->Z );\r
2271     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, &S->Z,   &S->Z ) ); MOD_MUL( S->Z );\r
2272     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, d,       &S->Z ) ); MOD_MUL( S->Z );\r
2273     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X, &AA,     &BB   ) ); MOD_MUL( R->X );\r
2274     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &grp->A, &E    ) ); MOD_MUL( R->Z );\r
2275     MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z, &BB,     &R->Z ) ); MOD_ADD( R->Z );\r
2276     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &E,      &R->Z ) ); MOD_MUL( R->Z );\r
2277 \r
2278 cleanup:\r
2279     mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B );\r
2280     mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C );\r
2281     mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB );\r
2282 \r
2283     return( ret );\r
2284 }\r
2285 \r
2286 /*\r
2287  * Multiplication with Montgomery ladder in x/z coordinates,\r
2288  * for curves in Montgomery form\r
2289  */\r
2290 static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,\r
2291                         const mbedtls_mpi *m, const mbedtls_ecp_point *P,\r
2292                         int (*f_rng)(void *, unsigned char *, size_t),\r
2293                         void *p_rng )\r
2294 {\r
2295     int ret;\r
2296     size_t i;\r
2297     unsigned char b;\r
2298     mbedtls_ecp_point RP;\r
2299     mbedtls_mpi PX;\r
2300 \r
2301     mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX );\r
2302 \r
2303     /* Save PX and read from P before writing to R, in case P == R */\r
2304     MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) );\r
2305     MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) );\r
2306 \r
2307     /* Set R to zero in modified x/z coordinates */\r
2308     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X, 1 ) );\r
2309     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) );\r
2310     mbedtls_mpi_free( &R->Y );\r
2311 \r
2312     /* RP.X might be sligtly larger than P, so reduce it */\r
2313     MOD_ADD( RP.X );\r
2314 \r
2315     /* Randomize coordinates of the starting point */\r
2316     if( f_rng != NULL )\r
2317         MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );\r
2318 \r
2319     /* Loop invariant: R = result so far, RP = R + P */\r
2320     i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */\r
2321     while( i-- > 0 )\r
2322     {\r
2323         b = mbedtls_mpi_get_bit( m, i );\r
2324         /*\r
2325          *  if (b) R = 2R + P else R = 2R,\r
2326          * which is:\r
2327          *  if (b) double_add( RP, R, RP, R )\r
2328          *  else   double_add( R, RP, R, RP )\r
2329          * but using safe conditional swaps to avoid leaks\r
2330          */\r
2331         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );\r
2332         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );\r
2333         MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );\r
2334         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );\r
2335         MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );\r
2336     }\r
2337 \r
2338     MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) );\r
2339 \r
2340 cleanup:\r
2341     mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX );\r
2342 \r
2343     return( ret );\r
2344 }\r
2345 \r
2346 #endif /* ECP_MONTGOMERY */\r
2347 \r
2348 /*\r
2349  * Restartable multiplication R = m * P\r
2350  */\r
2351 int mbedtls_ecp_mul_restartable( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,\r
2352              const mbedtls_mpi *m, const mbedtls_ecp_point *P,\r
2353              int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,\r
2354              mbedtls_ecp_restart_ctx *rs_ctx )\r
2355 {\r
2356     int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;\r
2357 #if defined(MBEDTLS_ECP_INTERNAL_ALT)\r
2358     char is_grp_capable = 0;\r
2359 #endif\r
2360     ECP_VALIDATE_RET( grp != NULL );\r
2361     ECP_VALIDATE_RET( R   != NULL );\r
2362     ECP_VALIDATE_RET( m   != NULL );\r
2363     ECP_VALIDATE_RET( P   != NULL );\r
2364 \r
2365 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
2366     /* reset ops count for this call if top-level */\r
2367     if( rs_ctx != NULL && rs_ctx->depth++ == 0 )\r
2368         rs_ctx->ops_done = 0;\r
2369 #endif\r
2370 \r
2371 #if defined(MBEDTLS_ECP_INTERNAL_ALT)\r
2372     if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) )\r
2373         MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );\r
2374 #endif /* MBEDTLS_ECP_INTERNAL_ALT */\r
2375 \r
2376 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
2377     /* skip argument check when restarting */\r
2378     if( rs_ctx == NULL || rs_ctx->rsm == NULL )\r
2379 #endif\r
2380     {\r
2381         /* check_privkey is free */\r
2382         MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_CHK );\r
2383 \r
2384         /* Common sanity checks */\r
2385         MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( grp, m ) );\r
2386         MBEDTLS_MPI_CHK( mbedtls_ecp_check_pubkey( grp, P ) );\r
2387     }\r
2388 \r
2389     ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;\r
2390 #if defined(ECP_MONTGOMERY)\r
2391     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )\r
2392         MBEDTLS_MPI_CHK( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) );\r
2393 #endif\r
2394 #if defined(ECP_SHORTWEIERSTRASS)\r
2395     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )\r
2396         MBEDTLS_MPI_CHK( ecp_mul_comb( grp, R, m, P, f_rng, p_rng, rs_ctx ) );\r
2397 #endif\r
2398 \r
2399 cleanup:\r
2400 \r
2401 #if defined(MBEDTLS_ECP_INTERNAL_ALT)\r
2402     if( is_grp_capable )\r
2403         mbedtls_internal_ecp_free( grp );\r
2404 #endif /* MBEDTLS_ECP_INTERNAL_ALT */\r
2405 \r
2406 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
2407     if( rs_ctx != NULL )\r
2408         rs_ctx->depth--;\r
2409 #endif\r
2410 \r
2411     return( ret );\r
2412 }\r
2413 \r
2414 /*\r
2415  * Multiplication R = m * P\r
2416  */\r
2417 int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,\r
2418              const mbedtls_mpi *m, const mbedtls_ecp_point *P,\r
2419              int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )\r
2420 {\r
2421     ECP_VALIDATE_RET( grp != NULL );\r
2422     ECP_VALIDATE_RET( R   != NULL );\r
2423     ECP_VALIDATE_RET( m   != NULL );\r
2424     ECP_VALIDATE_RET( P   != NULL );\r
2425     return( mbedtls_ecp_mul_restartable( grp, R, m, P, f_rng, p_rng, NULL ) );\r
2426 }\r
2427 \r
2428 #if defined(ECP_SHORTWEIERSTRASS)\r
2429 /*\r
2430  * Check that an affine point is valid as a public key,\r
2431  * short weierstrass curves (SEC1 3.2.3.1)\r
2432  */\r
2433 static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )\r
2434 {\r
2435     int ret;\r
2436     mbedtls_mpi YY, RHS;\r
2437 \r
2438     /* pt coordinates must be normalized for our checks */\r
2439     if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 ||\r
2440         mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 ||\r
2441         mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 ||\r
2442         mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 )\r
2443         return( MBEDTLS_ERR_ECP_INVALID_KEY );\r
2444 \r
2445     mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS );\r
2446 \r
2447     /*\r
2448      * YY = Y^2\r
2449      * RHS = X (X^2 + A) + B = X^3 + A X + B\r
2450      */\r
2451     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY,  &pt->Y,   &pt->Y  ) );  MOD_MUL( YY  );\r
2452     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X,   &pt->X  ) );  MOD_MUL( RHS );\r
2453 \r
2454     /* Special case for A = -3 */\r
2455     if( grp->A.p == NULL )\r
2456     {\r
2457         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3       ) );  MOD_SUB( RHS );\r
2458     }\r
2459     else\r
2460     {\r
2461         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) );  MOD_ADD( RHS );\r
2462     }\r
2463 \r
2464     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS,     &pt->X  ) );  MOD_MUL( RHS );\r
2465     MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS,     &grp->B ) );  MOD_ADD( RHS );\r
2466 \r
2467     if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 )\r
2468         ret = MBEDTLS_ERR_ECP_INVALID_KEY;\r
2469 \r
2470 cleanup:\r
2471 \r
2472     mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS );\r
2473 \r
2474     return( ret );\r
2475 }\r
2476 #endif /* ECP_SHORTWEIERSTRASS */\r
2477 \r
2478 /*\r
2479  * R = m * P with shortcuts for m == 1 and m == -1\r
2480  * NOT constant-time - ONLY for short Weierstrass!\r
2481  */\r
2482 static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp,\r
2483                                       mbedtls_ecp_point *R,\r
2484                                       const mbedtls_mpi *m,\r
2485                                       const mbedtls_ecp_point *P,\r
2486                                       mbedtls_ecp_restart_ctx *rs_ctx )\r
2487 {\r
2488     int ret;\r
2489 \r
2490     if( mbedtls_mpi_cmp_int( m, 1 ) == 0 )\r
2491     {\r
2492         MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );\r
2493     }\r
2494     else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 )\r
2495     {\r
2496         MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );\r
2497         if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 )\r
2498             MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) );\r
2499     }\r
2500     else\r
2501     {\r
2502         MBEDTLS_MPI_CHK( mbedtls_ecp_mul_restartable( grp, R, m, P,\r
2503                                                       NULL, NULL, rs_ctx ) );\r
2504     }\r
2505 \r
2506 cleanup:\r
2507     return( ret );\r
2508 }\r
2509 \r
2510 /*\r
2511  * Restartable linear combination\r
2512  * NOT constant-time\r
2513  */\r
2514 int mbedtls_ecp_muladd_restartable(\r
2515              mbedtls_ecp_group *grp, mbedtls_ecp_point *R,\r
2516              const mbedtls_mpi *m, const mbedtls_ecp_point *P,\r
2517              const mbedtls_mpi *n, const mbedtls_ecp_point *Q,\r
2518              mbedtls_ecp_restart_ctx *rs_ctx )\r
2519 {\r
2520     int ret;\r
2521     mbedtls_ecp_point mP;\r
2522     mbedtls_ecp_point *pmP = &mP;\r
2523     mbedtls_ecp_point *pR = R;\r
2524 #if defined(MBEDTLS_ECP_INTERNAL_ALT)\r
2525     char is_grp_capable = 0;\r
2526 #endif\r
2527     ECP_VALIDATE_RET( grp != NULL );\r
2528     ECP_VALIDATE_RET( R   != NULL );\r
2529     ECP_VALIDATE_RET( m   != NULL );\r
2530     ECP_VALIDATE_RET( P   != NULL );\r
2531     ECP_VALIDATE_RET( n   != NULL );\r
2532     ECP_VALIDATE_RET( Q   != NULL );\r
2533 \r
2534     if( mbedtls_ecp_get_type( grp ) != MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )\r
2535         return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );\r
2536 \r
2537     mbedtls_ecp_point_init( &mP );\r
2538 \r
2539     ECP_RS_ENTER( ma );\r
2540 \r
2541 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
2542     if( rs_ctx != NULL && rs_ctx->ma != NULL )\r
2543     {\r
2544         /* redirect intermediate results to restart context */\r
2545         pmP = &rs_ctx->ma->mP;\r
2546         pR  = &rs_ctx->ma->R;\r
2547 \r
2548         /* jump to next operation */\r
2549         if( rs_ctx->ma->state == ecp_rsma_mul2 )\r
2550             goto mul2;\r
2551         if( rs_ctx->ma->state == ecp_rsma_add )\r
2552             goto add;\r
2553         if( rs_ctx->ma->state == ecp_rsma_norm )\r
2554             goto norm;\r
2555     }\r
2556 #endif /* MBEDTLS_ECP_RESTARTABLE */\r
2557 \r
2558     MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pmP, m, P, rs_ctx ) );\r
2559 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
2560     if( rs_ctx != NULL && rs_ctx->ma != NULL )\r
2561         rs_ctx->ma->state = ecp_rsma_mul2;\r
2562 \r
2563 mul2:\r
2564 #endif\r
2565     MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pR,  n, Q, rs_ctx ) );\r
2566 \r
2567 #if defined(MBEDTLS_ECP_INTERNAL_ALT)\r
2568     if( ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) ) )\r
2569         MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );\r
2570 #endif /* MBEDTLS_ECP_INTERNAL_ALT */\r
2571 \r
2572 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
2573     if( rs_ctx != NULL && rs_ctx->ma != NULL )\r
2574         rs_ctx->ma->state = ecp_rsma_add;\r
2575 \r
2576 add:\r
2577 #endif\r
2578     MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_ADD );\r
2579     MBEDTLS_MPI_CHK( ecp_add_mixed( grp, pR, pmP, pR ) );\r
2580 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
2581     if( rs_ctx != NULL && rs_ctx->ma != NULL )\r
2582         rs_ctx->ma->state = ecp_rsma_norm;\r
2583 \r
2584 norm:\r
2585 #endif\r
2586     MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV );\r
2587     MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, pR ) );\r
2588 \r
2589 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
2590     if( rs_ctx != NULL && rs_ctx->ma != NULL )\r
2591         MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, pR ) );\r
2592 #endif\r
2593 \r
2594 cleanup:\r
2595 #if defined(MBEDTLS_ECP_INTERNAL_ALT)\r
2596     if( is_grp_capable )\r
2597         mbedtls_internal_ecp_free( grp );\r
2598 #endif /* MBEDTLS_ECP_INTERNAL_ALT */\r
2599 \r
2600     mbedtls_ecp_point_free( &mP );\r
2601 \r
2602     ECP_RS_LEAVE( ma );\r
2603 \r
2604     return( ret );\r
2605 }\r
2606 \r
2607 /*\r
2608  * Linear combination\r
2609  * NOT constant-time\r
2610  */\r
2611 int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,\r
2612              const mbedtls_mpi *m, const mbedtls_ecp_point *P,\r
2613              const mbedtls_mpi *n, const mbedtls_ecp_point *Q )\r
2614 {\r
2615     ECP_VALIDATE_RET( grp != NULL );\r
2616     ECP_VALIDATE_RET( R   != NULL );\r
2617     ECP_VALIDATE_RET( m   != NULL );\r
2618     ECP_VALIDATE_RET( P   != NULL );\r
2619     ECP_VALIDATE_RET( n   != NULL );\r
2620     ECP_VALIDATE_RET( Q   != NULL );\r
2621     return( mbedtls_ecp_muladd_restartable( grp, R, m, P, n, Q, NULL ) );\r
2622 }\r
2623 \r
2624 #if defined(ECP_MONTGOMERY)\r
2625 /*\r
2626  * Check validity of a public key for Montgomery curves with x-only schemes\r
2627  */\r
2628 static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )\r
2629 {\r
2630     /* [Curve25519 p. 5] Just check X is the correct number of bytes */\r
2631     /* Allow any public value, if it's too big then we'll just reduce it mod p\r
2632      * (RFC 7748 sec. 5 para. 3). */\r
2633     if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 )\r
2634         return( MBEDTLS_ERR_ECP_INVALID_KEY );\r
2635 \r
2636     return( 0 );\r
2637 }\r
2638 #endif /* ECP_MONTGOMERY */\r
2639 \r
2640 /*\r
2641  * Check that a point is valid as a public key\r
2642  */\r
2643 int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp,\r
2644                               const mbedtls_ecp_point *pt )\r
2645 {\r
2646     ECP_VALIDATE_RET( grp != NULL );\r
2647     ECP_VALIDATE_RET( pt  != NULL );\r
2648 \r
2649     /* Must use affine coordinates */\r
2650     if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 )\r
2651         return( MBEDTLS_ERR_ECP_INVALID_KEY );\r
2652 \r
2653 #if defined(ECP_MONTGOMERY)\r
2654     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )\r
2655         return( ecp_check_pubkey_mx( grp, pt ) );\r
2656 #endif\r
2657 #if defined(ECP_SHORTWEIERSTRASS)\r
2658     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )\r
2659         return( ecp_check_pubkey_sw( grp, pt ) );\r
2660 #endif\r
2661     return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
2662 }\r
2663 \r
2664 /*\r
2665  * Check that an mbedtls_mpi is valid as a private key\r
2666  */\r
2667 int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp,\r
2668                                const mbedtls_mpi *d )\r
2669 {\r
2670     ECP_VALIDATE_RET( grp != NULL );\r
2671     ECP_VALIDATE_RET( d   != NULL );\r
2672 \r
2673 #if defined(ECP_MONTGOMERY)\r
2674     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )\r
2675     {\r
2676         /* see RFC 7748 sec. 5 para. 5 */\r
2677         if( mbedtls_mpi_get_bit( d, 0 ) != 0 ||\r
2678             mbedtls_mpi_get_bit( d, 1 ) != 0 ||\r
2679             mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */\r
2680             return( MBEDTLS_ERR_ECP_INVALID_KEY );\r
2681 \r
2682         /* see [Curve25519] page 5 */\r
2683         if( grp->nbits == 254 && mbedtls_mpi_get_bit( d, 2 ) != 0 )\r
2684             return( MBEDTLS_ERR_ECP_INVALID_KEY );\r
2685 \r
2686         return( 0 );\r
2687     }\r
2688 #endif /* ECP_MONTGOMERY */\r
2689 #if defined(ECP_SHORTWEIERSTRASS)\r
2690     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )\r
2691     {\r
2692         /* see SEC1 3.2 */\r
2693         if( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||\r
2694             mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 )\r
2695             return( MBEDTLS_ERR_ECP_INVALID_KEY );\r
2696         else\r
2697             return( 0 );\r
2698     }\r
2699 #endif /* ECP_SHORTWEIERSTRASS */\r
2700 \r
2701     return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
2702 }\r
2703 \r
2704 /*\r
2705  * Generate a private key\r
2706  */\r
2707 int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group *grp,\r
2708                      mbedtls_mpi *d,\r
2709                      int (*f_rng)(void *, unsigned char *, size_t),\r
2710                      void *p_rng )\r
2711 {\r
2712     int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;\r
2713     size_t n_size;\r
2714 \r
2715     ECP_VALIDATE_RET( grp   != NULL );\r
2716     ECP_VALIDATE_RET( d     != NULL );\r
2717     ECP_VALIDATE_RET( f_rng != NULL );\r
2718 \r
2719     n_size = ( grp->nbits + 7 ) / 8;\r
2720 \r
2721 #if defined(ECP_MONTGOMERY)\r
2722     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )\r
2723     {\r
2724         /* [M225] page 5 */\r
2725         size_t b;\r
2726 \r
2727         do {\r
2728             MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );\r
2729         } while( mbedtls_mpi_bitlen( d ) == 0);\r
2730 \r
2731         /* Make sure the most significant bit is nbits */\r
2732         b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */\r
2733         if( b > grp->nbits )\r
2734             MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) );\r
2735         else\r
2736             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits, 1 ) );\r
2737 \r
2738         /* Make sure the last two bits are unset for Curve448, three bits for\r
2739            Curve25519 */\r
2740         MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) );\r
2741         MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) );\r
2742         if( grp->nbits == 254 )\r
2743         {\r
2744             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) );\r
2745         }\r
2746     }\r
2747 #endif /* ECP_MONTGOMERY */\r
2748 \r
2749 #if defined(ECP_SHORTWEIERSTRASS)\r
2750     if( mbedtls_ecp_get_type( grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )\r
2751     {\r
2752         /* SEC1 3.2.1: Generate d such that 1 <= n < N */\r
2753         int count = 0;\r
2754 \r
2755         /*\r
2756          * Match the procedure given in RFC 6979 (deterministic ECDSA):\r
2757          * - use the same byte ordering;\r
2758          * - keep the leftmost nbits bits of the generated octet string;\r
2759          * - try until result is in the desired range.\r
2760          * This also avoids any biais, which is especially important for ECDSA.\r
2761          */\r
2762         do\r
2763         {\r
2764             MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );\r
2765             MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) );\r
2766 \r
2767             /*\r
2768              * Each try has at worst a probability 1/2 of failing (the msb has\r
2769              * a probability 1/2 of being 0, and then the result will be < N),\r
2770              * so after 30 tries failure probability is a most 2**(-30).\r
2771              *\r
2772              * For most curves, 1 try is enough with overwhelming probability,\r
2773              * since N starts with a lot of 1s in binary, but some curves\r
2774              * such as secp224k1 are actually very close to the worst case.\r
2775              */\r
2776             if( ++count > 30 )\r
2777                 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );\r
2778         }\r
2779         while( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||\r
2780                mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 );\r
2781     }\r
2782 #endif /* ECP_SHORTWEIERSTRASS */\r
2783 \r
2784 cleanup:\r
2785     return( ret );\r
2786 }\r
2787 \r
2788 /*\r
2789  * Generate a keypair with configurable base point\r
2790  */\r
2791 int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp,\r
2792                      const mbedtls_ecp_point *G,\r
2793                      mbedtls_mpi *d, mbedtls_ecp_point *Q,\r
2794                      int (*f_rng)(void *, unsigned char *, size_t),\r
2795                      void *p_rng )\r
2796 {\r
2797     int ret;\r
2798     ECP_VALIDATE_RET( grp   != NULL );\r
2799     ECP_VALIDATE_RET( d     != NULL );\r
2800     ECP_VALIDATE_RET( G     != NULL );\r
2801     ECP_VALIDATE_RET( Q     != NULL );\r
2802     ECP_VALIDATE_RET( f_rng != NULL );\r
2803 \r
2804     MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, d, f_rng, p_rng ) );\r
2805     MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) );\r
2806 \r
2807 cleanup:\r
2808     return( ret );\r
2809 }\r
2810 \r
2811 /*\r
2812  * Generate key pair, wrapper for conventional base point\r
2813  */\r
2814 int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp,\r
2815                              mbedtls_mpi *d, mbedtls_ecp_point *Q,\r
2816                              int (*f_rng)(void *, unsigned char *, size_t),\r
2817                              void *p_rng )\r
2818 {\r
2819     ECP_VALIDATE_RET( grp   != NULL );\r
2820     ECP_VALIDATE_RET( d     != NULL );\r
2821     ECP_VALIDATE_RET( Q     != NULL );\r
2822     ECP_VALIDATE_RET( f_rng != NULL );\r
2823 \r
2824     return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) );\r
2825 }\r
2826 \r
2827 /*\r
2828  * Generate a keypair, prettier wrapper\r
2829  */\r
2830 int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,\r
2831                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )\r
2832 {\r
2833     int ret;\r
2834     ECP_VALIDATE_RET( key   != NULL );\r
2835     ECP_VALIDATE_RET( f_rng != NULL );\r
2836 \r
2837     if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 )\r
2838         return( ret );\r
2839 \r
2840     return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) );\r
2841 }\r
2842 \r
2843 #define ECP_CURVE25519_KEY_SIZE 32\r
2844 /*\r
2845  * Read a private key.\r
2846  */\r
2847 int mbedtls_ecp_read_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,\r
2848                           const unsigned char *buf, size_t buflen )\r
2849 {\r
2850     int ret = 0;\r
2851 \r
2852     ECP_VALIDATE_RET( key  != NULL );\r
2853     ECP_VALIDATE_RET( buf  != NULL );\r
2854 \r
2855     if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 )\r
2856         return( ret );\r
2857 \r
2858     ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;\r
2859 \r
2860 #if defined(ECP_MONTGOMERY)\r
2861     if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_MONTGOMERY )\r
2862     {\r
2863         /*\r
2864          * If it is Curve25519 curve then mask the key as mandated by RFC7748\r
2865          */\r
2866         if( grp_id == MBEDTLS_ECP_DP_CURVE25519 )\r
2867         {\r
2868             if( buflen != ECP_CURVE25519_KEY_SIZE )\r
2869                 return MBEDTLS_ERR_ECP_INVALID_KEY;\r
2870 \r
2871             MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary_le( &key->d, buf, buflen ) );\r
2872 \r
2873             /* Set the three least significant bits to 0 */\r
2874             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d, 0, 0 ) );\r
2875             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d, 1, 0 ) );\r
2876             MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( &key->d, 2, 0 ) );\r
2877 \r
2878             /* Set the most significant bit to 0 */\r
2879             MBEDTLS_MPI_CHK(\r
2880                     mbedtls_mpi_set_bit( &key->d,\r
2881                                          ECP_CURVE25519_KEY_SIZE * 8 - 1, 0 )\r
2882                     );\r
2883 \r
2884             /* Set the second most significant bit to 1 */\r
2885             MBEDTLS_MPI_CHK(\r
2886                     mbedtls_mpi_set_bit( &key->d,\r
2887                                          ECP_CURVE25519_KEY_SIZE * 8 - 2, 1 )\r
2888                     );\r
2889         }\r
2890         else\r
2891             ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;\r
2892     }\r
2893 \r
2894 #endif\r
2895 #if defined(ECP_SHORTWEIERSTRASS)\r
2896     if( mbedtls_ecp_get_type( &key->grp ) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS )\r
2897     {\r
2898         MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &key->d, buf, buflen ) );\r
2899 \r
2900         MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( &key->grp, &key->d ) );\r
2901     }\r
2902 \r
2903 #endif\r
2904 cleanup:\r
2905 \r
2906     if( ret != 0 )\r
2907         mbedtls_mpi_free( &key->d );\r
2908 \r
2909     return( ret );\r
2910 }\r
2911 \r
2912 /*\r
2913  * Check a public-private key pair\r
2914  */\r
2915 int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv )\r
2916 {\r
2917     int ret;\r
2918     mbedtls_ecp_point Q;\r
2919     mbedtls_ecp_group grp;\r
2920     ECP_VALIDATE_RET( pub != NULL );\r
2921     ECP_VALIDATE_RET( prv != NULL );\r
2922 \r
2923     if( pub->grp.id == MBEDTLS_ECP_DP_NONE ||\r
2924         pub->grp.id != prv->grp.id ||\r
2925         mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) ||\r
2926         mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) ||\r
2927         mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) )\r
2928     {\r
2929         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
2930     }\r
2931 \r
2932     mbedtls_ecp_point_init( &Q );\r
2933     mbedtls_ecp_group_init( &grp );\r
2934 \r
2935     /* mbedtls_ecp_mul() needs a non-const group... */\r
2936     mbedtls_ecp_group_copy( &grp, &prv->grp );\r
2937 \r
2938     /* Also checks d is valid */\r
2939     MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) );\r
2940 \r
2941     if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) ||\r
2942         mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) ||\r
2943         mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) )\r
2944     {\r
2945         ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;\r
2946         goto cleanup;\r
2947     }\r
2948 \r
2949 cleanup:\r
2950     mbedtls_ecp_point_free( &Q );\r
2951     mbedtls_ecp_group_free( &grp );\r
2952 \r
2953     return( ret );\r
2954 }\r
2955 \r
2956 #if defined(MBEDTLS_SELF_TEST)\r
2957 \r
2958 /*\r
2959  * Checkup routine\r
2960  */\r
2961 int mbedtls_ecp_self_test( int verbose )\r
2962 {\r
2963     int ret;\r
2964     size_t i;\r
2965     mbedtls_ecp_group grp;\r
2966     mbedtls_ecp_point R, P;\r
2967     mbedtls_mpi m;\r
2968     unsigned long add_c_prev, dbl_c_prev, mul_c_prev;\r
2969     /* exponents especially adapted for secp192r1 */\r
2970     const char *exponents[] =\r
2971     {\r
2972         "000000000000000000000000000000000000000000000001", /* one */\r
2973         "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */\r
2974         "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */\r
2975         "400000000000000000000000000000000000000000000000", /* one and zeros */\r
2976         "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */\r
2977         "555555555555555555555555555555555555555555555555", /* 101010... */\r
2978     };\r
2979 \r
2980     mbedtls_ecp_group_init( &grp );\r
2981     mbedtls_ecp_point_init( &R );\r
2982     mbedtls_ecp_point_init( &P );\r
2983     mbedtls_mpi_init( &m );\r
2984 \r
2985     /* Use secp192r1 if available, or any available curve */\r
2986 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)\r
2987     MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) );\r
2988 #else\r
2989     MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) );\r
2990 #endif\r
2991 \r
2992     if( verbose != 0 )\r
2993         mbedtls_printf( "  ECP test #1 (constant op_count, base point G): " );\r
2994 \r
2995     /* Do a dummy multiplication first to trigger precomputation */\r
2996     MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) );\r
2997     MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) );\r
2998 \r
2999     add_count = 0;\r
3000     dbl_count = 0;\r
3001     mul_count = 0;\r
3002     MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );\r
3003     MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );\r
3004 \r
3005     for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )\r
3006     {\r
3007         add_c_prev = add_count;\r
3008         dbl_c_prev = dbl_count;\r
3009         mul_c_prev = mul_count;\r
3010         add_count = 0;\r
3011         dbl_count = 0;\r
3012         mul_count = 0;\r
3013 \r
3014         MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );\r
3015         MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );\r
3016 \r
3017         if( add_count != add_c_prev ||\r
3018             dbl_count != dbl_c_prev ||\r
3019             mul_count != mul_c_prev )\r
3020         {\r
3021             if( verbose != 0 )\r
3022                 mbedtls_printf( "failed (%u)\n", (unsigned int) i );\r
3023 \r
3024             ret = 1;\r
3025             goto cleanup;\r
3026         }\r
3027     }\r
3028 \r
3029     if( verbose != 0 )\r
3030         mbedtls_printf( "passed\n" );\r
3031 \r
3032     if( verbose != 0 )\r
3033         mbedtls_printf( "  ECP test #2 (constant op_count, other point): " );\r
3034     /* We computed P = 2G last time, use it */\r
3035 \r
3036     add_count = 0;\r
3037     dbl_count = 0;\r
3038     mul_count = 0;\r
3039     MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );\r
3040     MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );\r
3041 \r
3042     for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )\r
3043     {\r
3044         add_c_prev = add_count;\r
3045         dbl_c_prev = dbl_count;\r
3046         mul_c_prev = mul_count;\r
3047         add_count = 0;\r
3048         dbl_count = 0;\r
3049         mul_count = 0;\r
3050 \r
3051         MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );\r
3052         MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );\r
3053 \r
3054         if( add_count != add_c_prev ||\r
3055             dbl_count != dbl_c_prev ||\r
3056             mul_count != mul_c_prev )\r
3057         {\r
3058             if( verbose != 0 )\r
3059                 mbedtls_printf( "failed (%u)\n", (unsigned int) i );\r
3060 \r
3061             ret = 1;\r
3062             goto cleanup;\r
3063         }\r
3064     }\r
3065 \r
3066     if( verbose != 0 )\r
3067         mbedtls_printf( "passed\n" );\r
3068 \r
3069 cleanup:\r
3070 \r
3071     if( ret < 0 && verbose != 0 )\r
3072         mbedtls_printf( "Unexpected error, return code = %08X\n", ret );\r
3073 \r
3074     mbedtls_ecp_group_free( &grp );\r
3075     mbedtls_ecp_point_free( &R );\r
3076     mbedtls_ecp_point_free( &P );\r
3077     mbedtls_mpi_free( &m );\r
3078 \r
3079     if( verbose != 0 )\r
3080         mbedtls_printf( "\n" );\r
3081 \r
3082     return( ret );\r
3083 }\r
3084 \r
3085 #endif /* MBEDTLS_SELF_TEST */\r
3086 \r
3087 #endif /* !MBEDTLS_ECP_ALT */\r
3088 \r
3089 #endif /* MBEDTLS_ECP_C */\r