mbed TLS library
Dependents: HTTPClient-SSL WS_SERVER
ecdsa.c
00001 /* 00002 * Elliptic curve DSA 00003 * 00004 * Copyright (C) 2006-2014, ARM Limited, All Rights Reserved 00005 * 00006 * This file is part of mbed TLS (https://tls.mbed.org) 00007 * 00008 * This program is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU General Public License as published by 00010 * the Free Software Foundation; either version 2 of the License, or 00011 * (at your option) any later version. 00012 * 00013 * This program is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00016 * GNU General Public License for more details. 00017 * 00018 * You should have received a copy of the GNU General Public License along 00019 * with this program; if not, write to the Free Software Foundation, Inc., 00020 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 00021 */ 00022 00023 /* 00024 * References: 00025 * 00026 * SEC1 http://www.secg.org/index.php?action=secg,docs_secg 00027 */ 00028 00029 #if !defined(POLARSSL_CONFIG_FILE) 00030 #include "polarssl/config.h" 00031 #else 00032 #include POLARSSL_CONFIG_FILE 00033 #endif 00034 00035 #if defined(POLARSSL_ECDSA_C) 00036 00037 #include "polarssl/ecdsa.h" 00038 #include "polarssl/asn1write.h" 00039 00040 #include <string.h> 00041 00042 #if defined(POLARSSL_ECDSA_DETERMINISTIC) 00043 #include "polarssl/hmac_drbg.h" 00044 #endif 00045 00046 #if defined(POLARSSL_ECDSA_DETERMINISTIC) 00047 /* 00048 * This a hopefully temporary compatibility function. 00049 * 00050 * Since we can't ensure the caller will pass a valid md_alg before the next 00051 * interface change, try to pick up a decent md by size. 00052 * 00053 * Argument is the minimum size in bytes of the MD output. 00054 */ 00055 static const md_info_t *md_info_by_size( size_t min_size ) 00056 { 00057 const md_info_t *md_cur, *md_picked = NULL; 00058 const int *md_alg; 00059 00060 for( md_alg = md_list(); *md_alg != 0; md_alg++ ) 00061 { 00062 if( ( md_cur = md_info_from_type( (md_type_t) *md_alg ) ) == NULL || 00063 (size_t) md_cur->size < min_size || 00064 ( md_picked != NULL && md_cur->size > md_picked->size ) ) 00065 continue; 00066 00067 md_picked = md_cur; 00068 } 00069 00070 return( md_picked ); 00071 } 00072 #endif /* POLARSSL_ECDSA_DETERMINISTIC */ 00073 00074 /* 00075 * Derive a suitable integer for group grp from a buffer of length len 00076 * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3 00077 */ 00078 static int derive_mpi( const ecp_group *grp, mpi *x, 00079 const unsigned char *buf, size_t blen ) 00080 { 00081 int ret; 00082 size_t n_size = ( grp->nbits + 7 ) / 8; 00083 size_t use_size = blen > n_size ? n_size : blen; 00084 00085 MPI_CHK( mpi_read_binary( x, buf, use_size ) ); 00086 if( use_size * 8 > grp->nbits ) 00087 MPI_CHK( mpi_shift_r( x, use_size * 8 - grp->nbits ) ); 00088 00089 /* While at it, reduce modulo N */ 00090 if( mpi_cmp_mpi( x, &grp->N ) >= 0 ) 00091 MPI_CHK( mpi_sub_mpi( x, x, &grp->N ) ); 00092 00093 cleanup: 00094 return( ret ); 00095 } 00096 00097 /* 00098 * Compute ECDSA signature of a hashed message (SEC1 4.1.3) 00099 * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message) 00100 */ 00101 int ecdsa_sign( ecp_group *grp, mpi *r, mpi *s, 00102 const mpi *d, const unsigned char *buf, size_t blen, 00103 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 00104 { 00105 int ret, key_tries, sign_tries, blind_tries; 00106 ecp_point R; 00107 mpi k, e, t; 00108 00109 /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */ 00110 if( grp->N .p == NULL ) 00111 return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); 00112 00113 ecp_point_init( &R ); 00114 mpi_init( &k ); mpi_init( &e ); mpi_init( &t ); 00115 00116 sign_tries = 0; 00117 do 00118 { 00119 /* 00120 * Steps 1-3: generate a suitable ephemeral keypair 00121 * and set r = xR mod n 00122 */ 00123 key_tries = 0; 00124 do 00125 { 00126 MPI_CHK( ecp_gen_keypair( grp, &k, &R, f_rng, p_rng ) ); 00127 MPI_CHK( mpi_mod_mpi( r, &R.X , &grp->N ) ); 00128 00129 if( key_tries++ > 10 ) 00130 { 00131 ret = POLARSSL_ERR_ECP_RANDOM_FAILED; 00132 goto cleanup; 00133 } 00134 } 00135 while( mpi_cmp_int( r, 0 ) == 0 ); 00136 00137 /* 00138 * Step 5: derive MPI from hashed message 00139 */ 00140 MPI_CHK( derive_mpi( grp, &e, buf, blen ) ); 00141 00142 /* 00143 * Generate a random value to blind inv_mod in next step, 00144 * avoiding a potential timing leak. 00145 */ 00146 blind_tries = 0; 00147 do 00148 { 00149 size_t n_size = ( grp->nbits + 7 ) / 8; 00150 MPI_CHK( mpi_fill_random( &t, n_size, f_rng, p_rng ) ); 00151 MPI_CHK( mpi_shift_r( &t, 8 * n_size - grp->nbits ) ); 00152 00153 /* See ecp_gen_keypair() */ 00154 if( ++blind_tries > 30 ) 00155 return( POLARSSL_ERR_ECP_RANDOM_FAILED ); 00156 } 00157 while( mpi_cmp_int( &t, 1 ) < 0 || 00158 mpi_cmp_mpi( &t, &grp->N ) >= 0 ); 00159 00160 /* 00161 * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n 00162 */ 00163 MPI_CHK( mpi_mul_mpi( s, r, d ) ); 00164 MPI_CHK( mpi_add_mpi( &e, &e, s ) ); 00165 MPI_CHK( mpi_mul_mpi( &e, &e, &t ) ); 00166 MPI_CHK( mpi_mul_mpi( &k, &k, &t ) ); 00167 MPI_CHK( mpi_inv_mod( s, &k, &grp->N ) ); 00168 MPI_CHK( mpi_mul_mpi( s, s, &e ) ); 00169 MPI_CHK( mpi_mod_mpi( s, s, &grp->N ) ); 00170 00171 if( sign_tries++ > 10 ) 00172 { 00173 ret = POLARSSL_ERR_ECP_RANDOM_FAILED; 00174 goto cleanup; 00175 } 00176 } 00177 while( mpi_cmp_int( s, 0 ) == 0 ); 00178 00179 cleanup: 00180 ecp_point_free( &R ); 00181 mpi_free( &k ); mpi_free( &e ); mpi_free( &t ); 00182 00183 return( ret ); 00184 } 00185 00186 #if defined(POLARSSL_ECDSA_DETERMINISTIC) 00187 /* 00188 * Deterministic signature wrapper 00189 */ 00190 int ecdsa_sign_det( ecp_group *grp, mpi *r, mpi *s, 00191 const mpi *d, const unsigned char *buf, size_t blen, 00192 md_type_t md_alg ) 00193 { 00194 int ret; 00195 hmac_drbg_context rng_ctx; 00196 unsigned char data[2 * POLARSSL_ECP_MAX_BYTES]; 00197 size_t grp_len = ( grp->nbits + 7 ) / 8; 00198 const md_info_t *md_info; 00199 mpi h; 00200 00201 /* Temporary fallback */ 00202 if( md_alg == POLARSSL_MD_NONE ) 00203 md_info = md_info_by_size( blen ); 00204 else 00205 md_info = md_info_from_type( md_alg ); 00206 00207 if( md_info == NULL ) 00208 return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); 00209 00210 mpi_init( &h ); 00211 memset( &rng_ctx, 0, sizeof( hmac_drbg_context ) ); 00212 00213 /* Use private key and message hash (reduced) to initialize HMAC_DRBG */ 00214 MPI_CHK( mpi_write_binary( d, data, grp_len ) ); 00215 MPI_CHK( derive_mpi( grp, &h, buf, blen ) ); 00216 MPI_CHK( mpi_write_binary( &h, data + grp_len, grp_len ) ); 00217 hmac_drbg_init_buf( &rng_ctx, md_info, data, 2 * grp_len ); 00218 00219 ret = ecdsa_sign( grp, r, s, d, buf, blen, 00220 hmac_drbg_random, &rng_ctx ); 00221 00222 cleanup: 00223 hmac_drbg_free( &rng_ctx ); 00224 mpi_free( &h ); 00225 00226 return( ret ); 00227 } 00228 #endif /* POLARSSL_ECDSA_DETERMINISTIC */ 00229 00230 /* 00231 * Verify ECDSA signature of hashed message (SEC1 4.1.4) 00232 * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message) 00233 */ 00234 int ecdsa_verify( ecp_group *grp, 00235 const unsigned char *buf, size_t blen, 00236 const ecp_point *Q, const mpi *r, const mpi *s) 00237 { 00238 int ret; 00239 mpi e, s_inv, u1, u2; 00240 ecp_point R, P; 00241 00242 ecp_point_init( &R ); ecp_point_init( &P ); 00243 mpi_init( &e ); mpi_init( &s_inv ); mpi_init( &u1 ); mpi_init( &u2 ); 00244 00245 /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */ 00246 if( grp->N .p == NULL ) 00247 return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); 00248 00249 /* 00250 * Step 1: make sure r and s are in range 1..n-1 00251 */ 00252 if( mpi_cmp_int( r, 1 ) < 0 || mpi_cmp_mpi( r, &grp->N ) >= 0 || 00253 mpi_cmp_int( s, 1 ) < 0 || mpi_cmp_mpi( s, &grp->N ) >= 0 ) 00254 { 00255 ret = POLARSSL_ERR_ECP_VERIFY_FAILED; 00256 goto cleanup; 00257 } 00258 00259 /* 00260 * Additional precaution: make sure Q is valid 00261 */ 00262 MPI_CHK( ecp_check_pubkey( grp, Q ) ); 00263 00264 /* 00265 * Step 3: derive MPI from hashed message 00266 */ 00267 MPI_CHK( derive_mpi( grp, &e, buf, blen ) ); 00268 00269 /* 00270 * Step 4: u1 = e / s mod n, u2 = r / s mod n 00271 */ 00272 MPI_CHK( mpi_inv_mod( &s_inv, s, &grp->N ) ); 00273 00274 MPI_CHK( mpi_mul_mpi( &u1, &e, &s_inv ) ); 00275 MPI_CHK( mpi_mod_mpi( &u1, &u1, &grp->N ) ); 00276 00277 MPI_CHK( mpi_mul_mpi( &u2, r, &s_inv ) ); 00278 MPI_CHK( mpi_mod_mpi( &u2, &u2, &grp->N ) ); 00279 00280 /* 00281 * Step 5: R = u1 G + u2 Q 00282 * 00283 * Since we're not using any secret data, no need to pass a RNG to 00284 * ecp_mul() for countermesures. 00285 */ 00286 MPI_CHK( ecp_mul( grp, &R, &u1, &grp->G , NULL, NULL ) ); 00287 MPI_CHK( ecp_mul( grp, &P, &u2, Q, NULL, NULL ) ); 00288 MPI_CHK( ecp_add( grp, &R, &R, &P ) ); 00289 00290 if( ecp_is_zero( &R ) ) 00291 { 00292 ret = POLARSSL_ERR_ECP_VERIFY_FAILED; 00293 goto cleanup; 00294 } 00295 00296 /* 00297 * Step 6: convert xR to an integer (no-op) 00298 * Step 7: reduce xR mod n (gives v) 00299 */ 00300 MPI_CHK( mpi_mod_mpi( &R.X , &R.X , &grp->N ) ); 00301 00302 /* 00303 * Step 8: check if v (that is, R.X) is equal to r 00304 */ 00305 if( mpi_cmp_mpi( &R.X , r ) != 0 ) 00306 { 00307 ret = POLARSSL_ERR_ECP_VERIFY_FAILED; 00308 goto cleanup; 00309 } 00310 00311 cleanup: 00312 ecp_point_free( &R ); ecp_point_free( &P ); 00313 mpi_free( &e ); mpi_free( &s_inv ); mpi_free( &u1 ); mpi_free( &u2 ); 00314 00315 return( ret ); 00316 } 00317 00318 /* 00319 * RFC 4492 page 20: 00320 * 00321 * Ecdsa-Sig-Value ::= SEQUENCE { 00322 * r INTEGER, 00323 * s INTEGER 00324 * } 00325 * 00326 * Size is at most 00327 * 1 (tag) + 1 (len) + 1 (initial 0) + ECP_MAX_BYTES for each of r and s, 00328 * twice that + 1 (tag) + 2 (len) for the sequence 00329 * (assuming ECP_MAX_BYTES is less than 126 for r and s, 00330 * and less than 124 (total len <= 255) for the sequence) 00331 */ 00332 #if POLARSSL_ECP_MAX_BYTES > 124 00333 #error "POLARSSL_ECP_MAX_BYTES bigger than expected, please fix MAX_SIG_LEN" 00334 #endif 00335 #define MAX_SIG_LEN ( 3 + 2 * ( 3 + POLARSSL_ECP_MAX_BYTES ) ) 00336 00337 /* 00338 * Convert a signature (given by context) to ASN.1 00339 */ 00340 static int ecdsa_signature_to_asn1( ecdsa_context *ctx, 00341 unsigned char *sig, size_t *slen ) 00342 { 00343 int ret; 00344 unsigned char buf[MAX_SIG_LEN]; 00345 unsigned char *p = buf + sizeof( buf ); 00346 size_t len = 0; 00347 00348 ASN1_CHK_ADD( len, asn1_write_mpi( &p, buf, &ctx->s ) ); 00349 ASN1_CHK_ADD( len, asn1_write_mpi( &p, buf, &ctx->r ) ); 00350 00351 ASN1_CHK_ADD( len, asn1_write_len( &p, buf, len ) ); 00352 ASN1_CHK_ADD( len, asn1_write_tag( &p, buf, 00353 ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ); 00354 00355 memcpy( sig, p, len ); 00356 *slen = len; 00357 00358 return( 0 ); 00359 } 00360 00361 /* 00362 * Compute and write signature 00363 */ 00364 int ecdsa_write_signature( ecdsa_context *ctx, 00365 const unsigned char *hash, size_t hlen, 00366 unsigned char *sig, size_t *slen, 00367 int (*f_rng)(void *, unsigned char *, size_t), 00368 void *p_rng ) 00369 { 00370 int ret; 00371 00372 if( ( ret = ecdsa_sign( &ctx->grp , &ctx->r , &ctx->s , &ctx->d , 00373 hash, hlen, f_rng, p_rng ) ) != 0 ) 00374 { 00375 return( ret ); 00376 } 00377 00378 return( ecdsa_signature_to_asn1( ctx, sig, slen ) ); 00379 } 00380 00381 #if defined(POLARSSL_ECDSA_DETERMINISTIC) 00382 /* 00383 * Compute and write signature deterministically 00384 */ 00385 int ecdsa_write_signature_det( ecdsa_context *ctx, 00386 const unsigned char *hash, size_t hlen, 00387 unsigned char *sig, size_t *slen, 00388 md_type_t md_alg ) 00389 { 00390 int ret; 00391 00392 if( ( ret = ecdsa_sign_det( &ctx->grp , &ctx->r , &ctx->s , &ctx->d , 00393 hash, hlen, md_alg ) ) != 0 ) 00394 { 00395 return( ret ); 00396 } 00397 00398 return( ecdsa_signature_to_asn1( ctx, sig, slen ) ); 00399 } 00400 #endif /* POLARSSL_ECDSA_DETERMINISTIC */ 00401 00402 /* 00403 * Read and check signature 00404 */ 00405 int ecdsa_read_signature( ecdsa_context *ctx, 00406 const unsigned char *hash, size_t hlen, 00407 const unsigned char *sig, size_t slen ) 00408 { 00409 int ret; 00410 unsigned char *p = (unsigned char *) sig; 00411 const unsigned char *end = sig + slen; 00412 size_t len; 00413 00414 if( ( ret = asn1_get_tag( &p, end, &len, 00415 ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 ) 00416 { 00417 return( POLARSSL_ERR_ECP_BAD_INPUT_DATA + ret ); 00418 } 00419 00420 if( p + len != end ) 00421 return( POLARSSL_ERR_ECP_BAD_INPUT_DATA + 00422 POLARSSL_ERR_ASN1_LENGTH_MISMATCH ); 00423 00424 if( ( ret = asn1_get_mpi( &p, end, &ctx->r ) ) != 0 || 00425 ( ret = asn1_get_mpi( &p, end, &ctx->s ) ) != 0 ) 00426 return( POLARSSL_ERR_ECP_BAD_INPUT_DATA + ret ); 00427 00428 if( ( ret = ecdsa_verify( &ctx->grp , hash, hlen, 00429 &ctx->Q , &ctx->r , &ctx->s ) ) != 0 ) 00430 return( ret ); 00431 00432 if( p != end ) 00433 return( POLARSSL_ERR_ECP_SIG_LEN_MISMATCH ); 00434 00435 return( 0 ); 00436 } 00437 00438 /* 00439 * Generate key pair 00440 */ 00441 int ecdsa_genkey( ecdsa_context *ctx, ecp_group_id gid, 00442 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 00443 { 00444 return( ecp_use_known_dp( &ctx->grp , gid ) || 00445 ecp_gen_keypair( &ctx->grp , &ctx->d , &ctx->Q , f_rng, p_rng ) ); 00446 } 00447 00448 /* 00449 * Set context from an ecp_keypair 00450 */ 00451 int ecdsa_from_keypair( ecdsa_context *ctx, const ecp_keypair *key ) 00452 { 00453 int ret; 00454 00455 if( ( ret = ecp_group_copy( &ctx->grp , &key->grp ) ) != 0 || 00456 ( ret = mpi_copy( &ctx->d , &key->d ) ) != 0 || 00457 ( ret = ecp_copy( &ctx->Q , &key->Q ) ) != 0 ) 00458 { 00459 ecdsa_free( ctx ); 00460 } 00461 00462 return( ret ); 00463 } 00464 00465 /* 00466 * Initialize context 00467 */ 00468 void ecdsa_init( ecdsa_context *ctx ) 00469 { 00470 ecp_group_init( &ctx->grp ); 00471 mpi_init( &ctx->d ); 00472 ecp_point_init( &ctx->Q ); 00473 mpi_init( &ctx->r ); 00474 mpi_init( &ctx->s ); 00475 } 00476 00477 /* 00478 * Free context 00479 */ 00480 void ecdsa_free( ecdsa_context *ctx ) 00481 { 00482 ecp_group_free( &ctx->grp ); 00483 mpi_free( &ctx->d ); 00484 ecp_point_free( &ctx->Q ); 00485 mpi_free( &ctx->r ); 00486 mpi_free( &ctx->s ); 00487 } 00488 00489 #if defined(POLARSSL_SELF_TEST) 00490 00491 /* 00492 * Checkup routine 00493 */ 00494 int ecdsa_self_test( int verbose ) 00495 { 00496 ((void) verbose ); 00497 return( 0 ); 00498 } 00499 00500 #endif /* POLARSSL_SELF_TEST */ 00501 00502 #endif /* POLARSSL_ECDSA_C */ 00503
Generated on Tue Jul 12 2022 13:50:37 by
![doxygen](doxygen.png)