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

   1 /*\r
   2  *  Elliptic curve DSA\r
   3  *\r
   4  *  Copyright (C) 2006-2015, ARM Limited, All Rights Reserved\r
   5  *  SPDX-License-Identifier: Apache-2.0\r
   6  *\r
   7  *  Licensed under the Apache License, Version 2.0 (the "License"); you may\r
   8  *  not use this file except in compliance with the License.\r
   9  *  You may obtain a copy of the License at\r
  10  *\r
  11  *  http://www.apache.org/licenses/LICENSE-2.0\r
  12  *\r
  13  *  Unless required by applicable law or agreed to in writing, software\r
  14  *  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT\r
  15  *  WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  16  *  See the License for the specific language governing permissions and\r
  17  *  limitations under the License.\r
  18  *\r
  19  *  This file is part of mbed TLS (https://tls.mbed.org)\r
  20  */\r
  21 \r
  22 /*\r
  23  * References:\r
  24  *\r
  25  * SEC1 http://www.secg.org/index.php?action=secg,docs_secg\r
  26  */\r
  27 \r
  28 #if !defined(MBEDTLS_CONFIG_FILE)\r
  29 #include "mbedtls/config.h"\r
  30 #else\r
  31 #include MBEDTLS_CONFIG_FILE\r
  32 #endif\r
  33 \r
  34 #if defined(MBEDTLS_ECDSA_C)\r
  35 \r
  36 #include "mbedtls/ecdsa.h"\r
  37 #include "mbedtls/asn1write.h"\r
  38 \r
  39 #include <string.h>\r
  40 \r
  41 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)\r
  42 #include "mbedtls/hmac_drbg.h"\r
  43 #endif\r
  44 \r
  45 #if defined(MBEDTLS_PLATFORM_C)\r
  46 #include "mbedtls/platform.h"\r
  47 #else\r
  48 #include <stdlib.h>\r
  49 #define mbedtls_calloc    calloc\r
  50 #define mbedtls_free       free\r
  51 #endif\r
  52 \r
  53 #include "mbedtls/platform_util.h"\r
  54 \r
  55 /* Parameter validation macros based on platform_util.h */\r
  56 #define ECDSA_VALIDATE_RET( cond )    \\r
  57     MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_ECP_BAD_INPUT_DATA )\r
  58 #define ECDSA_VALIDATE( cond )        \\r
  59     MBEDTLS_INTERNAL_VALIDATE( cond )\r
  60 \r
  61 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
  62 \r
  63 /*\r
  64  * Sub-context for ecdsa_verify()\r
  65  */\r
  66 struct mbedtls_ecdsa_restart_ver\r
  67 {\r
  68     mbedtls_mpi u1, u2;     /* intermediate values  */\r
  69     enum {                  /* what to do next?     */\r
  70         ecdsa_ver_init = 0, /* getting started      */\r
  71         ecdsa_ver_muladd,   /* muladd step          */\r
  72     } state;\r
  73 };\r
  74 \r
  75 /*\r
  76  * Init verify restart sub-context\r
  77  */\r
  78 static void ecdsa_restart_ver_init( mbedtls_ecdsa_restart_ver_ctx *ctx )\r
  79 {\r
  80     mbedtls_mpi_init( &ctx->u1 );\r
  81     mbedtls_mpi_init( &ctx->u2 );\r
  82     ctx->state = ecdsa_ver_init;\r
  83 }\r
  84 \r
  85 /*\r
  86  * Free the components of a verify restart sub-context\r
  87  */\r
  88 static void ecdsa_restart_ver_free( mbedtls_ecdsa_restart_ver_ctx *ctx )\r
  89 {\r
  90     if( ctx == NULL )\r
  91         return;\r
  92 \r
  93     mbedtls_mpi_free( &ctx->u1 );\r
  94     mbedtls_mpi_free( &ctx->u2 );\r
  95 \r
  96     ecdsa_restart_ver_init( ctx );\r
  97 }\r
  98 \r
  99 /*\r
 100  * Sub-context for ecdsa_sign()\r
 101  */\r
 102 struct mbedtls_ecdsa_restart_sig\r
 103 {\r
 104     int sign_tries;\r
 105     int key_tries;\r
 106     mbedtls_mpi k;          /* per-signature random */\r
 107     mbedtls_mpi r;          /* r value              */\r
 108     enum {                  /* what to do next?     */\r
 109         ecdsa_sig_init = 0, /* getting started      */\r
 110         ecdsa_sig_mul,      /* doing ecp_mul()      */\r
 111         ecdsa_sig_modn,     /* mod N computations   */\r
 112     } state;\r
 113 };\r
 114 \r
 115 /*\r
 116  * Init verify sign sub-context\r
 117  */\r
 118 static void ecdsa_restart_sig_init( mbedtls_ecdsa_restart_sig_ctx *ctx )\r
 119 {\r
 120     ctx->sign_tries = 0;\r
 121     ctx->key_tries = 0;\r
 122     mbedtls_mpi_init( &ctx->k );\r
 123     mbedtls_mpi_init( &ctx->r );\r
 124     ctx->state = ecdsa_sig_init;\r
 125 }\r
 126 \r
 127 /*\r
 128  * Free the components of a sign restart sub-context\r
 129  */\r
 130 static void ecdsa_restart_sig_free( mbedtls_ecdsa_restart_sig_ctx *ctx )\r
 131 {\r
 132     if( ctx == NULL )\r
 133         return;\r
 134 \r
 135     mbedtls_mpi_free( &ctx->k );\r
 136     mbedtls_mpi_free( &ctx->r );\r
 137 }\r
 138 \r
 139 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)\r
 140 /*\r
 141  * Sub-context for ecdsa_sign_det()\r
 142  */\r
 143 struct mbedtls_ecdsa_restart_det\r
 144 {\r
 145     mbedtls_hmac_drbg_context rng_ctx;  /* DRBG state   */\r
 146     enum {                      /* what to do next?     */\r
 147         ecdsa_det_init = 0,     /* getting started      */\r
 148         ecdsa_det_sign,         /* make signature       */\r
 149     } state;\r
 150 };\r
 151 \r
 152 /*\r
 153  * Init verify sign_det sub-context\r
 154  */\r
 155 static void ecdsa_restart_det_init( mbedtls_ecdsa_restart_det_ctx *ctx )\r
 156 {\r
 157     mbedtls_hmac_drbg_init( &ctx->rng_ctx );\r
 158     ctx->state = ecdsa_det_init;\r
 159 }\r
 160 \r
 161 /*\r
 162  * Free the components of a sign_det restart sub-context\r
 163  */\r
 164 static void ecdsa_restart_det_free( mbedtls_ecdsa_restart_det_ctx *ctx )\r
 165 {\r
 166     if( ctx == NULL )\r
 167         return;\r
 168 \r
 169     mbedtls_hmac_drbg_free( &ctx->rng_ctx );\r
 170 \r
 171     ecdsa_restart_det_init( ctx );\r
 172 }\r
 173 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */\r
 174 \r
 175 #define ECDSA_RS_ECP    &rs_ctx->ecp\r
 176 \r
 177 /* Utility macro for checking and updating ops budget */\r
 178 #define ECDSA_BUDGET( ops )   \\r
 179     MBEDTLS_MPI_CHK( mbedtls_ecp_check_budget( grp, &rs_ctx->ecp, ops ) );\r
 180 \r
 181 /* Call this when entering a function that needs its own sub-context */\r
 182 #define ECDSA_RS_ENTER( SUB )   do {                                 \\r
 183     /* reset ops count for this call if top-level */                 \\r
 184     if( rs_ctx != NULL && rs_ctx->ecp.depth++ == 0 )                 \\r
 185         rs_ctx->ecp.ops_done = 0;                                    \\r
 186                                                                      \\r
 187     /* set up our own sub-context if needed */                       \\r
 188     if( mbedtls_ecp_restart_is_enabled() &&                          \\r
 189         rs_ctx != NULL && rs_ctx->SUB == NULL )                      \\r
 190     {                                                                \\r
 191         rs_ctx->SUB = mbedtls_calloc( 1, sizeof( *rs_ctx->SUB ) );   \\r
 192         if( rs_ctx->SUB == NULL )                                    \\r
 193             return( MBEDTLS_ERR_ECP_ALLOC_FAILED );                  \\r
 194                                                                      \\r
 195         ecdsa_restart_## SUB ##_init( rs_ctx->SUB );                 \\r
 196     }                                                                \\r
 197 } while( 0 )\r
 198 \r
 199 /* Call this when leaving a function that needs its own sub-context */\r
 200 #define ECDSA_RS_LEAVE( SUB )   do {                                 \\r
 201     /* clear our sub-context when not in progress (done or error) */ \\r
 202     if( rs_ctx != NULL && rs_ctx->SUB != NULL &&                     \\r
 203         ret != MBEDTLS_ERR_ECP_IN_PROGRESS )                         \\r
 204     {                                                                \\r
 205         ecdsa_restart_## SUB ##_free( rs_ctx->SUB );                 \\r
 206         mbedtls_free( rs_ctx->SUB );                                 \\r
 207         rs_ctx->SUB = NULL;                                          \\r
 208     }                                                                \\r
 209                                                                      \\r
 210     if( rs_ctx != NULL )                                             \\r
 211         rs_ctx->ecp.depth--;                                         \\r
 212 } while( 0 )\r
 213 \r
 214 #else /* MBEDTLS_ECP_RESTARTABLE */\r
 215 \r
 216 #define ECDSA_RS_ECP    NULL\r
 217 \r
 218 #define ECDSA_BUDGET( ops )   /* no-op; for compatibility */\r
 219 \r
 220 #define ECDSA_RS_ENTER( SUB )   (void) rs_ctx\r
 221 #define ECDSA_RS_LEAVE( SUB )   (void) rs_ctx\r
 222 \r
 223 #endif /* MBEDTLS_ECP_RESTARTABLE */\r
 224 \r
 225 /*\r
 226  * Derive a suitable integer for group grp from a buffer of length len\r
 227  * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3\r
 228  */\r
 229 static int derive_mpi( const mbedtls_ecp_group *grp, mbedtls_mpi *x,\r
 230                        const unsigned char *buf, size_t blen )\r
 231 {\r
 232     int ret;\r
 233     size_t n_size = ( grp->nbits + 7 ) / 8;\r
 234     size_t use_size = blen > n_size ? n_size : blen;\r
 235 \r
 236     MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( x, buf, use_size ) );\r
 237     if( use_size * 8 > grp->nbits )\r
 238         MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( x, use_size * 8 - grp->nbits ) );\r
 239 \r
 240     /* While at it, reduce modulo N */\r
 241     if( mbedtls_mpi_cmp_mpi( x, &grp->N ) >= 0 )\r
 242         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( x, x, &grp->N ) );\r
 243 \r
 244 cleanup:\r
 245     return( ret );\r
 246 }\r
 247 \r
 248 #if !defined(MBEDTLS_ECDSA_SIGN_ALT)\r
 249 /*\r
 250  * Compute ECDSA signature of a hashed message (SEC1 4.1.3)\r
 251  * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message)\r
 252  */\r
 253 static int ecdsa_sign_restartable( mbedtls_ecp_group *grp,\r
 254                 mbedtls_mpi *r, mbedtls_mpi *s,\r
 255                 const mbedtls_mpi *d, const unsigned char *buf, size_t blen,\r
 256                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,\r
 257                 mbedtls_ecdsa_restart_ctx *rs_ctx )\r
 258 {\r
 259     int ret, key_tries, sign_tries;\r
 260     int *p_sign_tries = &sign_tries, *p_key_tries = &key_tries;\r
 261     mbedtls_ecp_point R;\r
 262     mbedtls_mpi k, e, t;\r
 263     mbedtls_mpi *pk = &k, *pr = r;\r
 264 \r
 265     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */\r
 266     if( grp->N.p == NULL )\r
 267         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 268 \r
 269     /* Make sure d is in range 1..n-1 */\r
 270     if( mbedtls_mpi_cmp_int( d, 1 ) < 0 || mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 )\r
 271         return( MBEDTLS_ERR_ECP_INVALID_KEY );\r
 272 \r
 273     mbedtls_ecp_point_init( &R );\r
 274     mbedtls_mpi_init( &k ); mbedtls_mpi_init( &e ); mbedtls_mpi_init( &t );\r
 275 \r
 276     ECDSA_RS_ENTER( sig );\r
 277 \r
 278 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
 279     if( rs_ctx != NULL && rs_ctx->sig != NULL )\r
 280     {\r
 281         /* redirect to our context */\r
 282         p_sign_tries = &rs_ctx->sig->sign_tries;\r
 283         p_key_tries = &rs_ctx->sig->key_tries;\r
 284         pk = &rs_ctx->sig->k;\r
 285         pr = &rs_ctx->sig->r;\r
 286 \r
 287         /* jump to current step */\r
 288         if( rs_ctx->sig->state == ecdsa_sig_mul )\r
 289             goto mul;\r
 290         if( rs_ctx->sig->state == ecdsa_sig_modn )\r
 291             goto modn;\r
 292     }\r
 293 #endif /* MBEDTLS_ECP_RESTARTABLE */\r
 294 \r
 295     *p_sign_tries = 0;\r
 296     do\r
 297     {\r
 298         if( *p_sign_tries++ > 10 )\r
 299         {\r
 300             ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;\r
 301             goto cleanup;\r
 302         }\r
 303 \r
 304         /*\r
 305          * Steps 1-3: generate a suitable ephemeral keypair\r
 306          * and set r = xR mod n\r
 307          */\r
 308         *p_key_tries = 0;\r
 309         do\r
 310         {\r
 311             if( *p_key_tries++ > 10 )\r
 312             {\r
 313                 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;\r
 314                 goto cleanup;\r
 315             }\r
 316 \r
 317             MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, pk, f_rng, p_rng ) );\r
 318 \r
 319 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
 320             if( rs_ctx != NULL && rs_ctx->sig != NULL )\r
 321                 rs_ctx->sig->state = ecdsa_sig_mul;\r
 322 \r
 323 mul:\r
 324 #endif\r
 325             MBEDTLS_MPI_CHK( mbedtls_ecp_mul_restartable( grp, &R, pk, &grp->G,\r
 326                                                   f_rng, p_rng, ECDSA_RS_ECP ) );\r
 327             MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( pr, &R.X, &grp->N ) );\r
 328         }\r
 329         while( mbedtls_mpi_cmp_int( pr, 0 ) == 0 );\r
 330 \r
 331 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
 332         if( rs_ctx != NULL && rs_ctx->sig != NULL )\r
 333             rs_ctx->sig->state = ecdsa_sig_modn;\r
 334 \r
 335 modn:\r
 336 #endif\r
 337         /*\r
 338          * Accounting for everything up to the end of the loop\r
 339          * (step 6, but checking now avoids saving e and t)\r
 340          */\r
 341         ECDSA_BUDGET( MBEDTLS_ECP_OPS_INV + 4 );\r
 342 \r
 343         /*\r
 344          * Step 5: derive MPI from hashed message\r
 345          */\r
 346         MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );\r
 347 \r
 348         /*\r
 349          * Generate a random value to blind inv_mod in next step,\r
 350          * avoiding a potential timing leak.\r
 351          */\r
 352         MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, &t, f_rng, p_rng ) );\r
 353 \r
 354         /*\r
 355          * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n\r
 356          */\r
 357         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, pr, d ) );\r
 358         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &e, &e, s ) );\r
 359         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &e, &e, &t ) );\r
 360         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( pk, pk, &t ) );\r
 361         MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( s, pk, &grp->N ) );\r
 362         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, s, &e ) );\r
 363         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( s, s, &grp->N ) );\r
 364     }\r
 365     while( mbedtls_mpi_cmp_int( s, 0 ) == 0 );\r
 366 \r
 367 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
 368     if( rs_ctx != NULL && rs_ctx->sig != NULL )\r
 369         mbedtls_mpi_copy( r, pr );\r
 370 #endif\r
 371 \r
 372 cleanup:\r
 373     mbedtls_ecp_point_free( &R );\r
 374     mbedtls_mpi_free( &k ); mbedtls_mpi_free( &e ); mbedtls_mpi_free( &t );\r
 375 \r
 376     ECDSA_RS_LEAVE( sig );\r
 377 \r
 378     return( ret );\r
 379 }\r
 380 \r
 381 /*\r
 382  * Compute ECDSA signature of a hashed message\r
 383  */\r
 384 int mbedtls_ecdsa_sign( mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,\r
 385                 const mbedtls_mpi *d, const unsigned char *buf, size_t blen,\r
 386                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )\r
 387 {\r
 388     ECDSA_VALIDATE_RET( grp   != NULL );\r
 389     ECDSA_VALIDATE_RET( r     != NULL );\r
 390     ECDSA_VALIDATE_RET( s     != NULL );\r
 391     ECDSA_VALIDATE_RET( d     != NULL );\r
 392     ECDSA_VALIDATE_RET( f_rng != NULL );\r
 393     ECDSA_VALIDATE_RET( buf   != NULL || blen == 0 );\r
 394 \r
 395     return( ecdsa_sign_restartable( grp, r, s, d, buf, blen,\r
 396                                     f_rng, p_rng, NULL ) );\r
 397 }\r
 398 #endif /* !MBEDTLS_ECDSA_SIGN_ALT */\r
 399 \r
 400 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)\r
 401 /*\r
 402  * Deterministic signature wrapper\r
 403  */\r
 404 static int ecdsa_sign_det_restartable( mbedtls_ecp_group *grp,\r
 405                     mbedtls_mpi *r, mbedtls_mpi *s,\r
 406                     const mbedtls_mpi *d, const unsigned char *buf, size_t blen,\r
 407                     mbedtls_md_type_t md_alg,\r
 408                     mbedtls_ecdsa_restart_ctx *rs_ctx )\r
 409 {\r
 410     int ret;\r
 411     mbedtls_hmac_drbg_context rng_ctx;\r
 412     mbedtls_hmac_drbg_context *p_rng = &rng_ctx;\r
 413     unsigned char data[2 * MBEDTLS_ECP_MAX_BYTES];\r
 414     size_t grp_len = ( grp->nbits + 7 ) / 8;\r
 415     const mbedtls_md_info_t *md_info;\r
 416     mbedtls_mpi h;\r
 417 \r
 418     if( ( md_info = mbedtls_md_info_from_type( md_alg ) ) == NULL )\r
 419         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 420 \r
 421     mbedtls_mpi_init( &h );\r
 422     mbedtls_hmac_drbg_init( &rng_ctx );\r
 423 \r
 424     ECDSA_RS_ENTER( det );\r
 425 \r
 426 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
 427     if( rs_ctx != NULL && rs_ctx->det != NULL )\r
 428     {\r
 429         /* redirect to our context */\r
 430         p_rng = &rs_ctx->det->rng_ctx;\r
 431 \r
 432         /* jump to current step */\r
 433         if( rs_ctx->det->state == ecdsa_det_sign )\r
 434             goto sign;\r
 435     }\r
 436 #endif /* MBEDTLS_ECP_RESTARTABLE */\r
 437 \r
 438     /* Use private key and message hash (reduced) to initialize HMAC_DRBG */\r
 439     MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( d, data, grp_len ) );\r
 440     MBEDTLS_MPI_CHK( derive_mpi( grp, &h, buf, blen ) );\r
 441     MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &h, data + grp_len, grp_len ) );\r
 442     mbedtls_hmac_drbg_seed_buf( p_rng, md_info, data, 2 * grp_len );\r
 443 \r
 444 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
 445     if( rs_ctx != NULL && rs_ctx->det != NULL )\r
 446         rs_ctx->det->state = ecdsa_det_sign;\r
 447 \r
 448 sign:\r
 449 #endif\r
 450 #if defined(MBEDTLS_ECDSA_SIGN_ALT)\r
 451     ret = mbedtls_ecdsa_sign( grp, r, s, d, buf, blen,\r
 452                               mbedtls_hmac_drbg_random, p_rng );\r
 453 #else\r
 454     ret = ecdsa_sign_restartable( grp, r, s, d, buf, blen,\r
 455                       mbedtls_hmac_drbg_random, p_rng, rs_ctx );\r
 456 #endif /* MBEDTLS_ECDSA_SIGN_ALT */\r
 457 \r
 458 cleanup:\r
 459     mbedtls_hmac_drbg_free( &rng_ctx );\r
 460     mbedtls_mpi_free( &h );\r
 461 \r
 462     ECDSA_RS_LEAVE( det );\r
 463 \r
 464     return( ret );\r
 465 }\r
 466 \r
 467 /*\r
 468  * Deterministic signature wrapper\r
 469  */\r
 470 int mbedtls_ecdsa_sign_det( mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,\r
 471                     const mbedtls_mpi *d, const unsigned char *buf, size_t blen,\r
 472                     mbedtls_md_type_t md_alg )\r
 473 {\r
 474     ECDSA_VALIDATE_RET( grp   != NULL );\r
 475     ECDSA_VALIDATE_RET( r     != NULL );\r
 476     ECDSA_VALIDATE_RET( s     != NULL );\r
 477     ECDSA_VALIDATE_RET( d     != NULL );\r
 478     ECDSA_VALIDATE_RET( buf   != NULL || blen == 0 );\r
 479 \r
 480     return( ecdsa_sign_det_restartable( grp, r, s, d, buf, blen, md_alg, NULL ) );\r
 481 }\r
 482 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */\r
 483 \r
 484 #if !defined(MBEDTLS_ECDSA_VERIFY_ALT)\r
 485 /*\r
 486  * Verify ECDSA signature of hashed message (SEC1 4.1.4)\r
 487  * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)\r
 488  */\r
 489 static int ecdsa_verify_restartable( mbedtls_ecp_group *grp,\r
 490                                      const unsigned char *buf, size_t blen,\r
 491                                      const mbedtls_ecp_point *Q,\r
 492                                      const mbedtls_mpi *r, const mbedtls_mpi *s,\r
 493                                      mbedtls_ecdsa_restart_ctx *rs_ctx )\r
 494 {\r
 495     int ret;\r
 496     mbedtls_mpi e, s_inv, u1, u2;\r
 497     mbedtls_ecp_point R;\r
 498     mbedtls_mpi *pu1 = &u1, *pu2 = &u2;\r
 499 \r
 500     mbedtls_ecp_point_init( &R );\r
 501     mbedtls_mpi_init( &e ); mbedtls_mpi_init( &s_inv );\r
 502     mbedtls_mpi_init( &u1 ); mbedtls_mpi_init( &u2 );\r
 503 \r
 504     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */\r
 505     if( grp->N.p == NULL )\r
 506         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );\r
 507 \r
 508     ECDSA_RS_ENTER( ver );\r
 509 \r
 510 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
 511     if( rs_ctx != NULL && rs_ctx->ver != NULL )\r
 512     {\r
 513         /* redirect to our context */\r
 514         pu1 = &rs_ctx->ver->u1;\r
 515         pu2 = &rs_ctx->ver->u2;\r
 516 \r
 517         /* jump to current step */\r
 518         if( rs_ctx->ver->state == ecdsa_ver_muladd )\r
 519             goto muladd;\r
 520     }\r
 521 #endif /* MBEDTLS_ECP_RESTARTABLE */\r
 522 \r
 523     /*\r
 524      * Step 1: make sure r and s are in range 1..n-1\r
 525      */\r
 526     if( mbedtls_mpi_cmp_int( r, 1 ) < 0 || mbedtls_mpi_cmp_mpi( r, &grp->N ) >= 0 ||\r
 527         mbedtls_mpi_cmp_int( s, 1 ) < 0 || mbedtls_mpi_cmp_mpi( s, &grp->N ) >= 0 )\r
 528     {\r
 529         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;\r
 530         goto cleanup;\r
 531     }\r
 532 \r
 533     /*\r
 534      * Step 3: derive MPI from hashed message\r
 535      */\r
 536     MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );\r
 537 \r
 538     /*\r
 539      * Step 4: u1 = e / s mod n, u2 = r / s mod n\r
 540      */\r
 541     ECDSA_BUDGET( MBEDTLS_ECP_OPS_CHK + MBEDTLS_ECP_OPS_INV + 2 );\r
 542 \r
 543     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &s_inv, s, &grp->N ) );\r
 544 \r
 545     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( pu1, &e, &s_inv ) );\r
 546     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( pu1, pu1, &grp->N ) );\r
 547 \r
 548     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( pu2, r, &s_inv ) );\r
 549     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( pu2, pu2, &grp->N ) );\r
 550 \r
 551 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
 552     if( rs_ctx != NULL && rs_ctx->ver != NULL )\r
 553         rs_ctx->ver->state = ecdsa_ver_muladd;\r
 554 \r
 555 muladd:\r
 556 #endif\r
 557     /*\r
 558      * Step 5: R = u1 G + u2 Q\r
 559      */\r
 560     MBEDTLS_MPI_CHK( mbedtls_ecp_muladd_restartable( grp,\r
 561                      &R, pu1, &grp->G, pu2, Q, ECDSA_RS_ECP ) );\r
 562 \r
 563     if( mbedtls_ecp_is_zero( &R ) )\r
 564     {\r
 565         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;\r
 566         goto cleanup;\r
 567     }\r
 568 \r
 569     /*\r
 570      * Step 6: convert xR to an integer (no-op)\r
 571      * Step 7: reduce xR mod n (gives v)\r
 572      */\r
 573     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &R.X, &R.X, &grp->N ) );\r
 574 \r
 575     /*\r
 576      * Step 8: check if v (that is, R.X) is equal to r\r
 577      */\r
 578     if( mbedtls_mpi_cmp_mpi( &R.X, r ) != 0 )\r
 579     {\r
 580         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;\r
 581         goto cleanup;\r
 582     }\r
 583 \r
 584 cleanup:\r
 585     mbedtls_ecp_point_free( &R );\r
 586     mbedtls_mpi_free( &e ); mbedtls_mpi_free( &s_inv );\r
 587     mbedtls_mpi_free( &u1 ); mbedtls_mpi_free( &u2 );\r
 588 \r
 589     ECDSA_RS_LEAVE( ver );\r
 590 \r
 591     return( ret );\r
 592 }\r
 593 \r
 594 /*\r
 595  * Verify ECDSA signature of hashed message\r
 596  */\r
 597 int mbedtls_ecdsa_verify( mbedtls_ecp_group *grp,\r
 598                           const unsigned char *buf, size_t blen,\r
 599                           const mbedtls_ecp_point *Q,\r
 600                           const mbedtls_mpi *r,\r
 601                           const mbedtls_mpi *s)\r
 602 {\r
 603     ECDSA_VALIDATE_RET( grp != NULL );\r
 604     ECDSA_VALIDATE_RET( Q   != NULL );\r
 605     ECDSA_VALIDATE_RET( r   != NULL );\r
 606     ECDSA_VALIDATE_RET( s   != NULL );\r
 607     ECDSA_VALIDATE_RET( buf != NULL || blen == 0 );\r
 608 \r
 609     return( ecdsa_verify_restartable( grp, buf, blen, Q, r, s, NULL ) );\r
 610 }\r
 611 #endif /* !MBEDTLS_ECDSA_VERIFY_ALT */\r
 612 \r
 613 /*\r
 614  * Convert a signature (given by context) to ASN.1\r
 615  */\r
 616 static int ecdsa_signature_to_asn1( const mbedtls_mpi *r, const mbedtls_mpi *s,\r
 617                                     unsigned char *sig, size_t *slen )\r
 618 {\r
 619     int ret;\r
 620     unsigned char buf[MBEDTLS_ECDSA_MAX_LEN];\r
 621     unsigned char *p = buf + sizeof( buf );\r
 622     size_t len = 0;\r
 623 \r
 624     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, s ) );\r
 625     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, r ) );\r
 626 \r
 627     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_len( &p, buf, len ) );\r
 628     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_tag( &p, buf,\r
 629                                        MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) );\r
 630 \r
 631     memcpy( sig, p, len );\r
 632     *slen = len;\r
 633 \r
 634     return( 0 );\r
 635 }\r
 636 \r
 637 /*\r
 638  * Compute and write signature\r
 639  */\r
 640 int mbedtls_ecdsa_write_signature_restartable( mbedtls_ecdsa_context *ctx,\r
 641                            mbedtls_md_type_t md_alg,\r
 642                            const unsigned char *hash, size_t hlen,\r
 643                            unsigned char *sig, size_t *slen,\r
 644                            int (*f_rng)(void *, unsigned char *, size_t),\r
 645                            void *p_rng,\r
 646                            mbedtls_ecdsa_restart_ctx *rs_ctx )\r
 647 {\r
 648     int ret;\r
 649     mbedtls_mpi r, s;\r
 650     ECDSA_VALIDATE_RET( ctx  != NULL );\r
 651     ECDSA_VALIDATE_RET( hash != NULL );\r
 652     ECDSA_VALIDATE_RET( sig  != NULL );\r
 653     ECDSA_VALIDATE_RET( slen != NULL );\r
 654 \r
 655     mbedtls_mpi_init( &r );\r
 656     mbedtls_mpi_init( &s );\r
 657 \r
 658 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)\r
 659     (void) f_rng;\r
 660     (void) p_rng;\r
 661 \r
 662     MBEDTLS_MPI_CHK( ecdsa_sign_det_restartable( &ctx->grp, &r, &s, &ctx->d,\r
 663                              hash, hlen, md_alg, rs_ctx ) );\r
 664 #else\r
 665     (void) md_alg;\r
 666 \r
 667 #if defined(MBEDTLS_ECDSA_SIGN_ALT)\r
 668     MBEDTLS_MPI_CHK( mbedtls_ecdsa_sign( &ctx->grp, &r, &s, &ctx->d,\r
 669                          hash, hlen, f_rng, p_rng ) );\r
 670 #else\r
 671     MBEDTLS_MPI_CHK( ecdsa_sign_restartable( &ctx->grp, &r, &s, &ctx->d,\r
 672                          hash, hlen, f_rng, p_rng, rs_ctx ) );\r
 673 #endif /* MBEDTLS_ECDSA_SIGN_ALT */\r
 674 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */\r
 675 \r
 676     MBEDTLS_MPI_CHK( ecdsa_signature_to_asn1( &r, &s, sig, slen ) );\r
 677 \r
 678 cleanup:\r
 679     mbedtls_mpi_free( &r );\r
 680     mbedtls_mpi_free( &s );\r
 681 \r
 682     return( ret );\r
 683 }\r
 684 \r
 685 /*\r
 686  * Compute and write signature\r
 687  */\r
 688 int mbedtls_ecdsa_write_signature( mbedtls_ecdsa_context *ctx,\r
 689                                  mbedtls_md_type_t md_alg,\r
 690                                  const unsigned char *hash, size_t hlen,\r
 691                                  unsigned char *sig, size_t *slen,\r
 692                                  int (*f_rng)(void *, unsigned char *, size_t),\r
 693                                  void *p_rng )\r
 694 {\r
 695     ECDSA_VALIDATE_RET( ctx  != NULL );\r
 696     ECDSA_VALIDATE_RET( hash != NULL );\r
 697     ECDSA_VALIDATE_RET( sig  != NULL );\r
 698     ECDSA_VALIDATE_RET( slen != NULL );\r
 699     return( mbedtls_ecdsa_write_signature_restartable(\r
 700                 ctx, md_alg, hash, hlen, sig, slen, f_rng, p_rng, NULL ) );\r
 701 }\r
 702 \r
 703 #if !defined(MBEDTLS_DEPRECATED_REMOVED) && \\r
 704     defined(MBEDTLS_ECDSA_DETERMINISTIC)\r
 705 int mbedtls_ecdsa_write_signature_det( mbedtls_ecdsa_context *ctx,\r
 706                                const unsigned char *hash, size_t hlen,\r
 707                                unsigned char *sig, size_t *slen,\r
 708                                mbedtls_md_type_t md_alg )\r
 709 {\r
 710     ECDSA_VALIDATE_RET( ctx  != NULL );\r
 711     ECDSA_VALIDATE_RET( hash != NULL );\r
 712     ECDSA_VALIDATE_RET( sig  != NULL );\r
 713     ECDSA_VALIDATE_RET( slen != NULL );\r
 714     return( mbedtls_ecdsa_write_signature( ctx, md_alg, hash, hlen, sig, slen,\r
 715                                    NULL, NULL ) );\r
 716 }\r
 717 #endif\r
 718 \r
 719 /*\r
 720  * Read and check signature\r
 721  */\r
 722 int mbedtls_ecdsa_read_signature( mbedtls_ecdsa_context *ctx,\r
 723                           const unsigned char *hash, size_t hlen,\r
 724                           const unsigned char *sig, size_t slen )\r
 725 {\r
 726     ECDSA_VALIDATE_RET( ctx  != NULL );\r
 727     ECDSA_VALIDATE_RET( hash != NULL );\r
 728     ECDSA_VALIDATE_RET( sig  != NULL );\r
 729     return( mbedtls_ecdsa_read_signature_restartable(\r
 730                 ctx, hash, hlen, sig, slen, NULL ) );\r
 731 }\r
 732 \r
 733 /*\r
 734  * Restartable read and check signature\r
 735  */\r
 736 int mbedtls_ecdsa_read_signature_restartable( mbedtls_ecdsa_context *ctx,\r
 737                           const unsigned char *hash, size_t hlen,\r
 738                           const unsigned char *sig, size_t slen,\r
 739                           mbedtls_ecdsa_restart_ctx *rs_ctx )\r
 740 {\r
 741     int ret;\r
 742     unsigned char *p = (unsigned char *) sig;\r
 743     const unsigned char *end = sig + slen;\r
 744     size_t len;\r
 745     mbedtls_mpi r, s;\r
 746     ECDSA_VALIDATE_RET( ctx  != NULL );\r
 747     ECDSA_VALIDATE_RET( hash != NULL );\r
 748     ECDSA_VALIDATE_RET( sig  != NULL );\r
 749 \r
 750     mbedtls_mpi_init( &r );\r
 751     mbedtls_mpi_init( &s );\r
 752 \r
 753     if( ( ret = mbedtls_asn1_get_tag( &p, end, &len,\r
 754                     MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) ) != 0 )\r
 755     {\r
 756         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;\r
 757         goto cleanup;\r
 758     }\r
 759 \r
 760     if( p + len != end )\r
 761     {\r
 762         ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA +\r
 763               MBEDTLS_ERR_ASN1_LENGTH_MISMATCH;\r
 764         goto cleanup;\r
 765     }\r
 766 \r
 767     if( ( ret = mbedtls_asn1_get_mpi( &p, end, &r ) ) != 0 ||\r
 768         ( ret = mbedtls_asn1_get_mpi( &p, end, &s ) ) != 0 )\r
 769     {\r
 770         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;\r
 771         goto cleanup;\r
 772     }\r
 773 #if defined(MBEDTLS_ECDSA_VERIFY_ALT)\r
 774     if( ( ret = mbedtls_ecdsa_verify( &ctx->grp, hash, hlen,\r
 775                                       &ctx->Q, &r, &s ) ) != 0 )\r
 776         goto cleanup;\r
 777 #else\r
 778     if( ( ret = ecdsa_verify_restartable( &ctx->grp, hash, hlen,\r
 779                               &ctx->Q, &r, &s, rs_ctx ) ) != 0 )\r
 780         goto cleanup;\r
 781 #endif /* MBEDTLS_ECDSA_VERIFY_ALT */\r
 782 \r
 783     /* At this point we know that the buffer starts with a valid signature.\r
 784      * Return 0 if the buffer just contains the signature, and a specific\r
 785      * error code if the valid signature is followed by more data. */\r
 786     if( p != end )\r
 787         ret = MBEDTLS_ERR_ECP_SIG_LEN_MISMATCH;\r
 788 \r
 789 cleanup:\r
 790     mbedtls_mpi_free( &r );\r
 791     mbedtls_mpi_free( &s );\r
 792 \r
 793     return( ret );\r
 794 }\r
 795 \r
 796 #if !defined(MBEDTLS_ECDSA_GENKEY_ALT)\r
 797 /*\r
 798  * Generate key pair\r
 799  */\r
 800 int mbedtls_ecdsa_genkey( mbedtls_ecdsa_context *ctx, mbedtls_ecp_group_id gid,\r
 801                   int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )\r
 802 {\r
 803     int ret = 0;\r
 804     ECDSA_VALIDATE_RET( ctx   != NULL );\r
 805     ECDSA_VALIDATE_RET( f_rng != NULL );\r
 806 \r
 807     ret = mbedtls_ecp_group_load( &ctx->grp, gid );\r
 808     if( ret != 0 )\r
 809         return( ret );\r
 810 \r
 811    return( mbedtls_ecp_gen_keypair( &ctx->grp, &ctx->d,\r
 812                                     &ctx->Q, f_rng, p_rng ) );\r
 813 }\r
 814 #endif /* !MBEDTLS_ECDSA_GENKEY_ALT */\r
 815 \r
 816 /*\r
 817  * Set context from an mbedtls_ecp_keypair\r
 818  */\r
 819 int mbedtls_ecdsa_from_keypair( mbedtls_ecdsa_context *ctx, const mbedtls_ecp_keypair *key )\r
 820 {\r
 821     int ret;\r
 822     ECDSA_VALIDATE_RET( ctx != NULL );\r
 823     ECDSA_VALIDATE_RET( key != NULL );\r
 824 \r
 825     if( ( ret = mbedtls_ecp_group_copy( &ctx->grp, &key->grp ) ) != 0 ||\r
 826         ( ret = mbedtls_mpi_copy( &ctx->d, &key->d ) ) != 0 ||\r
 827         ( ret = mbedtls_ecp_copy( &ctx->Q, &key->Q ) ) != 0 )\r
 828     {\r
 829         mbedtls_ecdsa_free( ctx );\r
 830     }\r
 831 \r
 832     return( ret );\r
 833 }\r
 834 \r
 835 /*\r
 836  * Initialize context\r
 837  */\r
 838 void mbedtls_ecdsa_init( mbedtls_ecdsa_context *ctx )\r
 839 {\r
 840     ECDSA_VALIDATE( ctx != NULL );\r
 841 \r
 842     mbedtls_ecp_keypair_init( ctx );\r
 843 }\r
 844 \r
 845 /*\r
 846  * Free context\r
 847  */\r
 848 void mbedtls_ecdsa_free( mbedtls_ecdsa_context *ctx )\r
 849 {\r
 850     if( ctx == NULL )\r
 851         return;\r
 852 \r
 853     mbedtls_ecp_keypair_free( ctx );\r
 854 }\r
 855 \r
 856 #if defined(MBEDTLS_ECP_RESTARTABLE)\r
 857 /*\r
 858  * Initialize a restart context\r
 859  */\r
 860 void mbedtls_ecdsa_restart_init( mbedtls_ecdsa_restart_ctx *ctx )\r
 861 {\r
 862     ECDSA_VALIDATE( ctx != NULL );\r
 863 \r
 864     mbedtls_ecp_restart_init( &ctx->ecp );\r
 865 \r
 866     ctx->ver = NULL;\r
 867     ctx->sig = NULL;\r
 868 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)\r
 869     ctx->det = NULL;\r
 870 #endif\r
 871 }\r
 872 \r
 873 /*\r
 874  * Free the components of a restart context\r
 875  */\r
 876 void mbedtls_ecdsa_restart_free( mbedtls_ecdsa_restart_ctx *ctx )\r
 877 {\r
 878     if( ctx == NULL )\r
 879         return;\r
 880 \r
 881     mbedtls_ecp_restart_free( &ctx->ecp );\r
 882 \r
 883     ecdsa_restart_ver_free( ctx->ver );\r
 884     mbedtls_free( ctx->ver );\r
 885     ctx->ver = NULL;\r
 886 \r
 887     ecdsa_restart_sig_free( ctx->sig );\r
 888     mbedtls_free( ctx->sig );\r
 889     ctx->sig = NULL;\r
 890 \r
 891 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)\r
 892     ecdsa_restart_det_free( ctx->det );\r
 893     mbedtls_free( ctx->det );\r
 894     ctx->det = NULL;\r
 895 #endif\r
 896 }\r
 897 #endif /* MBEDTLS_ECP_RESTARTABLE */\r
 898 \r
 899 #endif /* MBEDTLS_ECDSA_C */\r