ecp.c

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