ecdsa.c

00001 /*
00002  *  Elliptic curve DSA
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  */
00027 
00028 #if !defined(MBEDTLS_CONFIG_FILE)
00029 #include "mbedtls/config.h"
00030 #else
00031 #include MBEDTLS_CONFIG_FILE
00032 #endif
00033 
00034 #if defined(MBEDTLS_ECDSA_C)
00035 
00036 #include "mbedtls/ecdsa.h"
00037 #include "mbedtls/asn1write.h"
00038 
00039 #include <string.h>
00040 
00041 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
00042 #include "mbedtls/hmac_drbg.h"
00043 #endif
00044 
00045 /*
00046  * Derive a suitable integer for group grp from a buffer of length len
00047  * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3
00048  */
00049 static int derive_mpi( const mbedtls_ecp_group *grp, mbedtls_mpi *x,
00050                        const unsigned char *buf, size_t blen )
00051 {
00052     int ret;
00053     size_t n_size = ( grp->nbits  + 7 ) / 8;
00054     size_t use_size = blen > n_size ? n_size : blen;
00055 
00056     MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( x, buf, use_size ) );
00057     if( use_size * 8 > grp->nbits  )
00058         MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( x, use_size * 8 - grp->nbits  ) );
00059 
00060     /* While at it, reduce modulo N */
00061     if( mbedtls_mpi_cmp_mpi( x, &grp->N  ) >= 0 )
00062         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( x, x, &grp->N  ) );
00063 
00064 cleanup:
00065     return( ret );
00066 }
00067 
00068 /*
00069  * Compute ECDSA signature of a hashed message (SEC1 4.1.3)
00070  * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message)
00071  */
00072 int mbedtls_ecdsa_sign( mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,
00073                 const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
00074                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
00075 {
00076     int ret, key_tries, sign_tries, blind_tries;
00077     mbedtls_ecp_point R;
00078     mbedtls_mpi k, e, t;
00079 
00080     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
00081     if( grp->N .p  == NULL )
00082         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00083 
00084     mbedtls_ecp_point_init( &R );
00085     mbedtls_mpi_init( &k ); mbedtls_mpi_init( &e ); mbedtls_mpi_init( &t );
00086 
00087     sign_tries = 0;
00088     do
00089     {
00090         /*
00091          * Steps 1-3: generate a suitable ephemeral keypair
00092          * and set r = xR mod n
00093          */
00094         key_tries = 0;
00095         do
00096         {
00097             MBEDTLS_MPI_CHK( mbedtls_ecp_gen_keypair( grp, &k, &R, f_rng, p_rng ) );
00098             MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( r, &R.X , &grp->N  ) );
00099 
00100             if( key_tries++ > 10 )
00101             {
00102                 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
00103                 goto cleanup;
00104             }
00105         }
00106         while( mbedtls_mpi_cmp_int( r, 0 ) == 0 );
00107 
00108         /*
00109          * Step 5: derive MPI from hashed message
00110          */
00111         MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
00112 
00113         /*
00114          * Generate a random value to blind inv_mod in next step,
00115          * avoiding a potential timing leak.
00116          */
00117         blind_tries = 0;
00118         do
00119         {
00120             size_t n_size = ( grp->nbits  + 7 ) / 8;
00121             MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &t, n_size, f_rng, p_rng ) );
00122             MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &t, 8 * n_size - grp->nbits  ) );
00123 
00124             /* See mbedtls_ecp_gen_keypair() */
00125             if( ++blind_tries > 30 )
00126                 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
00127         }
00128         while( mbedtls_mpi_cmp_int( &t, 1 ) < 0 ||
00129                mbedtls_mpi_cmp_mpi( &t, &grp->N  ) >= 0 );
00130 
00131         /*
00132          * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n
00133          */
00134         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, r, d ) );
00135         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &e, &e, s ) );
00136         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &e, &e, &t ) );
00137         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &k, &k, &t ) );
00138         MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( s, &k, &grp->N  ) );
00139         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, s, &e ) );
00140         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( s, s, &grp->N  ) );
00141 
00142         if( sign_tries++ > 10 )
00143         {
00144             ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
00145             goto cleanup;
00146         }
00147     }
00148     while( mbedtls_mpi_cmp_int( s, 0 ) == 0 );
00149 
00150 cleanup:
00151     mbedtls_ecp_point_free( &R );
00152     mbedtls_mpi_free( &k ); mbedtls_mpi_free( &e ); mbedtls_mpi_free( &t );
00153 
00154     return( ret );
00155 }
00156 
00157 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
00158 /*
00159  * Deterministic signature wrapper
00160  */
00161 int mbedtls_ecdsa_sign_det( mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,
00162                     const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
00163                     mbedtls_md_type_t md_alg )
00164 {
00165     int ret;
00166     mbedtls_hmac_drbg_context rng_ctx;
00167     unsigned char data[2 * MBEDTLS_ECP_MAX_BYTES];
00168     size_t grp_len = ( grp->nbits  + 7 ) / 8;
00169     const mbedtls_md_info_t *md_info;
00170     mbedtls_mpi h;
00171 
00172     if( ( md_info = mbedtls_md_info_from_type( md_alg ) ) == NULL )
00173         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00174 
00175     mbedtls_mpi_init( &h );
00176     mbedtls_hmac_drbg_init( &rng_ctx );
00177 
00178     /* Use private key and message hash (reduced) to initialize HMAC_DRBG */
00179     MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( d, data, grp_len ) );
00180     MBEDTLS_MPI_CHK( derive_mpi( grp, &h, buf, blen ) );
00181     MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &h, data + grp_len, grp_len ) );
00182     mbedtls_hmac_drbg_seed_buf( &rng_ctx, md_info, data, 2 * grp_len );
00183 
00184     ret = mbedtls_ecdsa_sign( grp, r, s, d, buf, blen,
00185                       mbedtls_hmac_drbg_random, &rng_ctx );
00186 
00187 cleanup:
00188     mbedtls_hmac_drbg_free( &rng_ctx );
00189     mbedtls_mpi_free( &h );
00190 
00191     return( ret );
00192 }
00193 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
00194 
00195 /*
00196  * Verify ECDSA signature of hashed message (SEC1 4.1.4)
00197  * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)
00198  */
00199 int mbedtls_ecdsa_verify( mbedtls_ecp_group *grp,
00200                   const unsigned char *buf, size_t blen,
00201                   const mbedtls_ecp_point *Q, const mbedtls_mpi *r, const mbedtls_mpi *s)
00202 {
00203     int ret;
00204     mbedtls_mpi e, s_inv, u1, u2;
00205     mbedtls_ecp_point R;
00206 
00207     mbedtls_ecp_point_init( &R );
00208     mbedtls_mpi_init( &e ); mbedtls_mpi_init( &s_inv ); mbedtls_mpi_init( &u1 ); mbedtls_mpi_init( &u2 );
00209 
00210     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
00211     if( grp->N .p  == NULL )
00212         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00213 
00214     /*
00215      * Step 1: make sure r and s are in range 1..n-1
00216      */
00217     if( mbedtls_mpi_cmp_int( r, 1 ) < 0 || mbedtls_mpi_cmp_mpi( r, &grp->N  ) >= 0 ||
00218         mbedtls_mpi_cmp_int( s, 1 ) < 0 || mbedtls_mpi_cmp_mpi( s, &grp->N  ) >= 0 )
00219     {
00220         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
00221         goto cleanup;
00222     }
00223 
00224     /*
00225      * Additional precaution: make sure Q is valid
00226      */
00227     MBEDTLS_MPI_CHK( mbedtls_ecp_check_pubkey( grp, Q ) );
00228 
00229     /*
00230      * Step 3: derive MPI from hashed message
00231      */
00232     MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
00233 
00234     /*
00235      * Step 4: u1 = e / s mod n, u2 = r / s mod n
00236      */
00237     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &s_inv, s, &grp->N  ) );
00238 
00239     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u1, &e, &s_inv ) );
00240     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &u1, &u1, &grp->N  ) );
00241 
00242     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u2, r, &s_inv ) );
00243     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &u2, &u2, &grp->N  ) );
00244 
00245     /*
00246      * Step 5: R = u1 G + u2 Q
00247      *
00248      * Since we're not using any secret data, no need to pass a RNG to
00249      * mbedtls_ecp_mul() for countermesures.
00250      */
00251     MBEDTLS_MPI_CHK( mbedtls_ecp_muladd( grp, &R, &u1, &grp->G , &u2, Q ) );
00252 
00253     if( mbedtls_ecp_is_zero( &R ) )
00254     {
00255         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
00256         goto cleanup;
00257     }
00258 
00259     /*
00260      * Step 6: convert xR to an integer (no-op)
00261      * Step 7: reduce xR mod n (gives v)
00262      */
00263     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &R.X , &R.X , &grp->N  ) );
00264 
00265     /*
00266      * Step 8: check if v (that is, R.X) is equal to r
00267      */
00268     if( mbedtls_mpi_cmp_mpi( &R.X , r ) != 0 )
00269     {
00270         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
00271         goto cleanup;
00272     }
00273 
00274 cleanup:
00275     mbedtls_ecp_point_free( &R );
00276     mbedtls_mpi_free( &e ); mbedtls_mpi_free( &s_inv ); mbedtls_mpi_free( &u1 ); mbedtls_mpi_free( &u2 );
00277 
00278     return( ret );
00279 }
00280 
00281 /*
00282  * Convert a signature (given by context) to ASN.1
00283  */
00284 static int ecdsa_signature_to_asn1( const mbedtls_mpi *r, const mbedtls_mpi *s,
00285                                     unsigned char *sig, size_t *slen )
00286 {
00287     int ret;
00288     unsigned char buf[MBEDTLS_ECDSA_MAX_LEN];
00289     unsigned char *p = buf + sizeof( buf );
00290     size_t len = 0;
00291 
00292     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, s ) );
00293     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, r ) );
00294 
00295     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_len( &p, buf, len ) );
00296     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_tag( &p, buf,
00297                                        MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) );
00298 
00299     memcpy( sig, p, len );
00300     *slen = len;
00301 
00302     return( 0 );
00303 }
00304 
00305 /*
00306  * Compute and write signature
00307  */
00308 int mbedtls_ecdsa_write_signature( mbedtls_ecdsa_context *ctx, mbedtls_md_type_t md_alg,
00309                            const unsigned char *hash, size_t hlen,
00310                            unsigned char *sig, size_t *slen,
00311                            int (*f_rng)(void *, unsigned char *, size_t),
00312                            void *p_rng )
00313 {
00314     int ret;
00315     mbedtls_mpi r, s;
00316 
00317     mbedtls_mpi_init( &r );
00318     mbedtls_mpi_init( &s );
00319 
00320 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
00321     (void) f_rng;
00322     (void) p_rng;
00323 
00324     MBEDTLS_MPI_CHK( mbedtls_ecdsa_sign_det( &ctx->grp , &r, &s, &ctx->d ,
00325                              hash, hlen, md_alg ) );
00326 #else
00327     (void) md_alg;
00328 
00329     MBEDTLS_MPI_CHK( mbedtls_ecdsa_sign( &ctx->grp , &r, &s, &ctx->d ,
00330                          hash, hlen, f_rng, p_rng ) );
00331 #endif
00332 
00333     MBEDTLS_MPI_CHK( ecdsa_signature_to_asn1( &r, &s, sig, slen ) );
00334 
00335 cleanup:
00336     mbedtls_mpi_free( &r );
00337     mbedtls_mpi_free( &s );
00338 
00339     return( ret );
00340 }
00341 
00342 #if ! defined(MBEDTLS_DEPRECATED_REMOVED) && \
00343     defined(MBEDTLS_ECDSA_DETERMINISTIC)
00344 int mbedtls_ecdsa_write_signature_det( mbedtls_ecdsa_context *ctx,
00345                                const unsigned char *hash, size_t hlen,
00346                                unsigned char *sig, size_t *slen,
00347                                mbedtls_md_type_t md_alg )
00348 {
00349     return( mbedtls_ecdsa_write_signature( ctx, md_alg, hash, hlen, sig, slen,
00350                                    NULL, NULL ) );
00351 }
00352 #endif
00353 
00354 /*
00355  * Read and check signature
00356  */
00357 int mbedtls_ecdsa_read_signature( mbedtls_ecdsa_context *ctx,
00358                           const unsigned char *hash, size_t hlen,
00359                           const unsigned char *sig, size_t slen )
00360 {
00361     int ret;
00362     unsigned char *p = (unsigned char *) sig;
00363     const unsigned char *end = sig + slen;
00364     size_t len;
00365     mbedtls_mpi r, s;
00366 
00367     mbedtls_mpi_init( &r );
00368     mbedtls_mpi_init( &s );
00369 
00370     if( ( ret = mbedtls_asn1_get_tag( &p, end, &len,
00371                     MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) ) != 0 )
00372     {
00373         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
00374         goto cleanup;
00375     }
00376 
00377     if( p + len != end )
00378     {
00379         ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA +
00380               MBEDTLS_ERR_ASN1_LENGTH_MISMATCH;
00381         goto cleanup;
00382     }
00383 
00384     if( ( ret = mbedtls_asn1_get_mpi( &p, end, &r ) ) != 0 ||
00385         ( ret = mbedtls_asn1_get_mpi( &p, end, &s ) ) != 0 )
00386     {
00387         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
00388         goto cleanup;
00389     }
00390 
00391     if( ( ret = mbedtls_ecdsa_verify( &ctx->grp , hash, hlen,
00392                               &ctx->Q , &r, &s ) ) != 0 )
00393         goto cleanup;
00394 
00395     if( p != end )
00396         ret = MBEDTLS_ERR_ECP_SIG_LEN_MISMATCH;
00397 
00398 cleanup:
00399     mbedtls_mpi_free( &r );
00400     mbedtls_mpi_free( &s );
00401 
00402     return( ret );
00403 }
00404 
00405 /*
00406  * Generate key pair
00407  */
00408 int mbedtls_ecdsa_genkey( mbedtls_ecdsa_context *ctx, mbedtls_ecp_group_id gid,
00409                   int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
00410 {
00411     return( mbedtls_ecp_group_load( &ctx->grp , gid ) ||
00412             mbedtls_ecp_gen_keypair( &ctx->grp , &ctx->d , &ctx->Q , f_rng, p_rng ) );
00413 }
00414 
00415 /*
00416  * Set context from an mbedtls_ecp_keypair
00417  */
00418 int mbedtls_ecdsa_from_keypair( mbedtls_ecdsa_context *ctx, const mbedtls_ecp_keypair *key )
00419 {
00420     int ret;
00421 
00422     if( ( ret = mbedtls_ecp_group_copy( &ctx->grp , &key->grp  ) ) != 0 ||
00423         ( ret = mbedtls_mpi_copy( &ctx->d , &key->d  ) ) != 0 ||
00424         ( ret = mbedtls_ecp_copy( &ctx->Q , &key->Q  ) ) != 0 )
00425     {
00426         mbedtls_ecdsa_free( ctx );
00427     }
00428 
00429     return( ret );
00430 }
00431 
00432 /*
00433  * Initialize context
00434  */
00435 void mbedtls_ecdsa_init( mbedtls_ecdsa_context *ctx )
00436 {
00437     mbedtls_ecp_keypair_init( ctx );
00438 }
00439 
00440 /*
00441  * Free context
00442  */
00443 void mbedtls_ecdsa_free( mbedtls_ecdsa_context *ctx )
00444 {
00445     mbedtls_ecp_keypair_free( ctx );
00446 }
00447 
00448 #endif /* MBEDTLS_ECDSA_C */