Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

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