third_party/mbedtls/repo/library/ecdsa.c

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