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