PolarSSL v1.3.8
ecdsa.c
Go to the documentation of this file.
1 /*
2  * Elliptic curve DSA
3  *
4  * Copyright (C) 2006-2014, Brainspark B.V.
5  *
6  * This file is part of PolarSSL (http://www.polarssl.org)
7  * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
8  *
9  * All rights reserved.
10  *
11  * This program is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation; either version 2 of the License, or
14  * (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License along
22  * with this program; if not, write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24  */
25 
26 /*
27  * References:
28  *
29  * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
30  */
31 
32 #if !defined(POLARSSL_CONFIG_FILE)
33 #include "polarssl/config.h"
34 #else
35 #include POLARSSL_CONFIG_FILE
36 #endif
37 
38 #if defined(POLARSSL_ECDSA_C)
39 
40 #include "polarssl/ecdsa.h"
41 #include "polarssl/asn1write.h"
42 
43 #if defined(POLARSSL_ECDSA_DETERMINISTIC)
44 #include "polarssl/hmac_drbg.h"
45 #endif
46 
47 #if defined(POLARSSL_ECDSA_DETERMINISTIC)
48 /*
49  * This a hopefully temporary compatibility function.
50  *
51  * Since we can't ensure the caller will pass a valid md_alg before the next
52  * interface change, try to pick up a decent md by size.
53  *
54  * Argument is the minimum size in bytes of the MD output.
55  */
56 static const md_info_t *md_info_by_size( size_t min_size )
57 {
58  const md_info_t *md_cur, *md_picked = NULL;
59  const int *md_alg;
60 
61  for( md_alg = md_list(); *md_alg != 0; md_alg++ )
62  {
63  if( ( md_cur = md_info_from_type( *md_alg ) ) == NULL ||
64  (size_t) md_cur->size < min_size ||
65  ( md_picked != NULL && md_cur->size > md_picked->size ) )
66  continue;
67 
68  md_picked = md_cur;
69  }
70 
71  return( md_picked );
72 }
73 #endif /* POLARSSL_ECDSA_DETERMINISTIC */
74 
75 /*
76  * Derive a suitable integer for group grp from a buffer of length len
77  * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3
78  */
79 static int derive_mpi( const ecp_group *grp, mpi *x,
80  const unsigned char *buf, size_t blen )
81 {
82  int ret;
83  size_t n_size = ( grp->nbits + 7 ) / 8;
84  size_t use_size = blen > n_size ? n_size : blen;
85 
86  MPI_CHK( mpi_read_binary( x, buf, use_size ) );
87  if( use_size * 8 > grp->nbits )
88  MPI_CHK( mpi_shift_r( x, use_size * 8 - grp->nbits ) );
89 
90  /* While at it, reduce modulo N */
91  if( mpi_cmp_mpi( x, &grp->N ) >= 0 )
92  MPI_CHK( mpi_sub_mpi( x, x, &grp->N ) );
93 
94 cleanup:
95  return( ret );
96 }
97 
98 /*
99  * Compute ECDSA signature of a hashed message (SEC1 4.1.3)
100  * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message)
101  */
102 int ecdsa_sign( ecp_group *grp, mpi *r, mpi *s,
103  const mpi *d, const unsigned char *buf, size_t blen,
104  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
105 {
106  int ret, key_tries, sign_tries, blind_tries;
107  ecp_point R;
108  mpi k, e, t;
109 
110  /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
111  if( grp->N.p == NULL )
113 
114  ecp_point_init( &R );
115  mpi_init( &k ); mpi_init( &e ); mpi_init( &t );
116 
117  sign_tries = 0;
118  do
119  {
120  /*
121  * Steps 1-3: generate a suitable ephemeral keypair
122  * and set r = xR mod n
123  */
124  key_tries = 0;
125  do
126  {
127  MPI_CHK( ecp_gen_keypair( grp, &k, &R, f_rng, p_rng ) );
128  MPI_CHK( mpi_mod_mpi( r, &R.X, &grp->N ) );
129 
130  if( key_tries++ > 10 )
131  {
133  goto cleanup;
134  }
135  }
136  while( mpi_cmp_int( r, 0 ) == 0 );
137 
138  /*
139  * Step 5: derive MPI from hashed message
140  */
141  MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
142 
143  /*
144  * Generate a random value to blind inv_mod in next step,
145  * avoiding a potential timing leak.
146  */
147  blind_tries = 0;
148  do
149  {
150  size_t n_size = ( grp->nbits + 7 ) / 8;
151  MPI_CHK( mpi_fill_random( &t, n_size, f_rng, p_rng ) );
152  MPI_CHK( mpi_shift_r( &t, 8 * n_size - grp->nbits ) );
153 
154  /* See ecp_gen_keypair() */
155  if( ++blind_tries > 30 )
157  }
158  while( mpi_cmp_int( &t, 1 ) < 0 ||
159  mpi_cmp_mpi( &t, &grp->N ) >= 0 );
160 
161  /*
162  * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n
163  */
164  MPI_CHK( mpi_mul_mpi( s, r, d ) );
165  MPI_CHK( mpi_add_mpi( &e, &e, s ) );
166  MPI_CHK( mpi_mul_mpi( &e, &e, &t ) );
167  MPI_CHK( mpi_mul_mpi( &k, &k, &t ) );
168  MPI_CHK( mpi_inv_mod( s, &k, &grp->N ) );
169  MPI_CHK( mpi_mul_mpi( s, s, &e ) );
170  MPI_CHK( mpi_mod_mpi( s, s, &grp->N ) );
171 
172  if( sign_tries++ > 10 )
173  {
175  goto cleanup;
176  }
177  }
178  while( mpi_cmp_int( s, 0 ) == 0 );
179 
180 cleanup:
181  ecp_point_free( &R );
182  mpi_free( &k ); mpi_free( &e ); mpi_free( &t );
183 
184  return( ret );
185 }
186 
187 #if defined(POLARSSL_ECDSA_DETERMINISTIC)
188 /*
189  * Deterministic signature wrapper
190  */
191 int ecdsa_sign_det( ecp_group *grp, mpi *r, mpi *s,
192  const mpi *d, const unsigned char *buf, size_t blen,
193  md_type_t md_alg )
194 {
195  int ret;
196  hmac_drbg_context rng_ctx;
197  unsigned char data[2 * POLARSSL_ECP_MAX_BYTES];
198  size_t grp_len = ( grp->nbits + 7 ) / 8;
199  const md_info_t *md_info;
200  mpi h;
201 
202  /* Temporary fallback */
203  if( md_alg == POLARSSL_MD_NONE )
204  md_info = md_info_by_size( blen );
205  else
206  md_info = md_info_from_type( md_alg );
207 
208  if( md_info == NULL )
210 
211  mpi_init( &h );
212  memset( &rng_ctx, 0, sizeof( hmac_drbg_context ) );
213 
214  /* Use private key and message hash (reduced) to initialize HMAC_DRBG */
215  MPI_CHK( mpi_write_binary( d, data, grp_len ) );
216  MPI_CHK( derive_mpi( grp, &h, buf, blen ) );
217  MPI_CHK( mpi_write_binary( &h, data + grp_len, grp_len ) );
218  hmac_drbg_init_buf( &rng_ctx, md_info, data, 2 * grp_len );
219 
220  ret = ecdsa_sign( grp, r, s, d, buf, blen,
221  hmac_drbg_random, &rng_ctx );
222 
223 cleanup:
224  hmac_drbg_free( &rng_ctx );
225  mpi_free( &h );
226 
227  return( ret );
228 }
229 #endif /* POLARSSL_ECDSA_DETERMINISTIC */
230 
231 /*
232  * Verify ECDSA signature of hashed message (SEC1 4.1.4)
233  * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)
234  */
235 int ecdsa_verify( ecp_group *grp,
236  const unsigned char *buf, size_t blen,
237  const ecp_point *Q, const mpi *r, const mpi *s)
238 {
239  int ret;
240  mpi e, s_inv, u1, u2;
241  ecp_point R, P;
242 
243  ecp_point_init( &R ); ecp_point_init( &P );
244  mpi_init( &e ); mpi_init( &s_inv ); mpi_init( &u1 ); mpi_init( &u2 );
245 
246  /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
247  if( grp->N.p == NULL )
249 
250  /*
251  * Step 1: make sure r and s are in range 1..n-1
252  */
253  if( mpi_cmp_int( r, 1 ) < 0 || mpi_cmp_mpi( r, &grp->N ) >= 0 ||
254  mpi_cmp_int( s, 1 ) < 0 || mpi_cmp_mpi( s, &grp->N ) >= 0 )
255  {
257  goto cleanup;
258  }
259 
260  /*
261  * Additional precaution: make sure Q is valid
262  */
263  MPI_CHK( ecp_check_pubkey( grp, Q ) );
264 
265  /*
266  * Step 3: derive MPI from hashed message
267  */
268  MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
269 
270  /*
271  * Step 4: u1 = e / s mod n, u2 = r / s mod n
272  */
273  MPI_CHK( mpi_inv_mod( &s_inv, s, &grp->N ) );
274 
275  MPI_CHK( mpi_mul_mpi( &u1, &e, &s_inv ) );
276  MPI_CHK( mpi_mod_mpi( &u1, &u1, &grp->N ) );
277 
278  MPI_CHK( mpi_mul_mpi( &u2, r, &s_inv ) );
279  MPI_CHK( mpi_mod_mpi( &u2, &u2, &grp->N ) );
280 
281  /*
282  * Step 5: R = u1 G + u2 Q
283  *
284  * Since we're not using any secret data, no need to pass a RNG to
285  * ecp_mul() for countermesures.
286  */
287  MPI_CHK( ecp_mul( grp, &R, &u1, &grp->G, NULL, NULL ) );
288  MPI_CHK( ecp_mul( grp, &P, &u2, Q, NULL, NULL ) );
289  MPI_CHK( ecp_add( grp, &R, &R, &P ) );
290 
291  if( ecp_is_zero( &R ) )
292  {
294  goto cleanup;
295  }
296 
297  /*
298  * Step 6: convert xR to an integer (no-op)
299  * Step 7: reduce xR mod n (gives v)
300  */
301  MPI_CHK( mpi_mod_mpi( &R.X, &R.X, &grp->N ) );
302 
303  /*
304  * Step 8: check if v (that is, R.X) is equal to r
305  */
306  if( mpi_cmp_mpi( &R.X, r ) != 0 )
307  {
309  goto cleanup;
310  }
311 
312 cleanup:
313  ecp_point_free( &R ); ecp_point_free( &P );
314  mpi_free( &e ); mpi_free( &s_inv ); mpi_free( &u1 ); mpi_free( &u2 );
315 
316  return( ret );
317 }
318 
319 /*
320  * RFC 4492 page 20:
321  *
322  * Ecdsa-Sig-Value ::= SEQUENCE {
323  * r INTEGER,
324  * s INTEGER
325  * }
326  *
327  * Size is at most
328  * 1 (tag) + 1 (len) + 1 (initial 0) + ECP_MAX_BYTES for each of r and s,
329  * twice that + 1 (tag) + 2 (len) for the sequence
330  * (assuming ECP_MAX_BYTES is less than 126 for r and s,
331  * and less than 124 (total len <= 255) for the sequence)
332  */
333 #if POLARSSL_ECP_MAX_BYTES > 124
334 #error "POLARSSL_ECP_MAX_BYTES bigger than expected, please fix MAX_SIG_LEN"
335 #endif
336 #define MAX_SIG_LEN ( 3 + 2 * ( 2 + POLARSSL_ECP_MAX_BYTES ) )
337 
338 /*
339  * Convert a signature (given by context) to ASN.1
340  */
341 static int ecdsa_signature_to_asn1( ecdsa_context *ctx,
342  unsigned char *sig, size_t *slen )
343 {
344  int ret;
345  unsigned char buf[MAX_SIG_LEN];
346  unsigned char *p = buf + sizeof( buf );
347  size_t len = 0;
348 
349  ASN1_CHK_ADD( len, asn1_write_mpi( &p, buf, &ctx->s ) );
350  ASN1_CHK_ADD( len, asn1_write_mpi( &p, buf, &ctx->r ) );
351 
352  ASN1_CHK_ADD( len, asn1_write_len( &p, buf, len ) );
353  ASN1_CHK_ADD( len, asn1_write_tag( &p, buf,
355 
356  memcpy( sig, p, len );
357  *slen = len;
358 
359  return( 0 );
360 }
361 
362 /*
363  * Compute and write signature
364  */
366  const unsigned char *hash, size_t hlen,
367  unsigned char *sig, size_t *slen,
368  int (*f_rng)(void *, unsigned char *, size_t),
369  void *p_rng )
370 {
371  int ret;
372 
373  if( ( ret = ecdsa_sign( &ctx->grp, &ctx->r, &ctx->s, &ctx->d,
374  hash, hlen, f_rng, p_rng ) ) != 0 )
375  {
376  return( ret );
377  }
378 
379  return( ecdsa_signature_to_asn1( ctx, sig, slen ) );
380 }
381 
382 #if defined(POLARSSL_ECDSA_DETERMINISTIC)
383 /*
384  * Compute and write signature deterministically
385  */
387  const unsigned char *hash, size_t hlen,
388  unsigned char *sig, size_t *slen,
389  md_type_t md_alg )
390 {
391  int ret;
392 
393  if( ( ret = ecdsa_sign_det( &ctx->grp, &ctx->r, &ctx->s, &ctx->d,
394  hash, hlen, md_alg ) ) != 0 )
395  {
396  return( ret );
397  }
398 
399  return( ecdsa_signature_to_asn1( ctx, sig, slen ) );
400 }
401 #endif /* POLARSSL_ECDSA_DETERMINISTIC */
402 
403 /*
404  * Read and check signature
405  */
407  const unsigned char *hash, size_t hlen,
408  const unsigned char *sig, size_t slen )
409 {
410  int ret;
411  unsigned char *p = (unsigned char *) sig;
412  const unsigned char *end = sig + slen;
413  size_t len;
414 
415  if( ( ret = asn1_get_tag( &p, end, &len,
416  ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 )
417  {
418  return( POLARSSL_ERR_ECP_BAD_INPUT_DATA + ret );
419  }
420 
421  if( p + len != end )
424 
425  if( ( ret = asn1_get_mpi( &p, end, &ctx->r ) ) != 0 ||
426  ( ret = asn1_get_mpi( &p, end, &ctx->s ) ) != 0 )
427  return( POLARSSL_ERR_ECP_BAD_INPUT_DATA + ret );
428 
429  if( ( ret = ecdsa_verify( &ctx->grp, hash, hlen,
430  &ctx->Q, &ctx->r, &ctx->s ) ) != 0 )
431  return( ret );
432 
433  if( p != end )
435 
436  return( 0 );
437 }
438 
439 /*
440  * Generate key pair
441  */
443  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
444 {
445  return( ecp_use_known_dp( &ctx->grp, gid ) ||
446  ecp_gen_keypair( &ctx->grp, &ctx->d, &ctx->Q, f_rng, p_rng ) );
447 }
448 
449 /*
450  * Set context from an ecp_keypair
451  */
452 int ecdsa_from_keypair( ecdsa_context *ctx, const ecp_keypair *key )
453 {
454  int ret;
455 
456  if( ( ret = ecp_group_copy( &ctx->grp, &key->grp ) ) != 0 ||
457  ( ret = mpi_copy( &ctx->d, &key->d ) ) != 0 ||
458  ( ret = ecp_copy( &ctx->Q, &key->Q ) ) != 0 )
459  {
460  ecdsa_free( ctx );
461  }
462 
463  return( ret );
464 }
465 
466 /*
467  * Initialize context
468  */
469 void ecdsa_init( ecdsa_context *ctx )
470 {
471  ecp_group_init( &ctx->grp );
472  mpi_init( &ctx->d );
473  ecp_point_init( &ctx->Q );
474  mpi_init( &ctx->r );
475  mpi_init( &ctx->s );
476 }
477 
478 /*
479  * Free context
480  */
481 void ecdsa_free( ecdsa_context *ctx )
482 {
483  ecp_group_free( &ctx->grp );
484  mpi_free( &ctx->d );
485  ecp_point_free( &ctx->Q );
486  mpi_free( &ctx->r );
487  mpi_free( &ctx->s );
488 }
489 
490 #if defined(POLARSSL_SELF_TEST)
491 
492 /*
493  * Checkup routine
494  */
495 int ecdsa_self_test( int verbose )
496 {
497  ((void) verbose );
498  return( 0 );
499 }
500 
501 #endif /* POLARSSL_SELF_TEST */
502 
503 #endif /* POLARSSL_ECDSA_C */