PolarSSL v1.3.2
ecdsa.c
Go to the documentation of this file.
1 /*
2  * Elliptic curve DSA
3  *
4  * Copyright (C) 2006-2013, 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 #include "polarssl/config.h"
33 
34 #if defined(POLARSSL_ECDSA_C)
35 
36 #include "polarssl/ecdsa.h"
37 #include "polarssl/asn1write.h"
38 
39 /*
40  * Derive a suitable integer for group grp from a buffer of length len
41  * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3
42  */
43 static int derive_mpi( const ecp_group *grp, mpi *x,
44  const unsigned char *buf, size_t blen )
45 {
46  size_t n_size = (grp->nbits + 7) / 8;
47  return( mpi_read_binary( x, buf, blen > n_size ? n_size : blen ) );
48 }
49 
50 /*
51  * Compute ECDSA signature of a hashed message (SEC1 4.1.3)
52  * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message)
53  */
54 int ecdsa_sign( ecp_group *grp, mpi *r, mpi *s,
55  const mpi *d, const unsigned char *buf, size_t blen,
56  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
57 {
58  int ret, key_tries, sign_tries;
59  ecp_point R;
60  mpi k, e;
61 
62  ecp_point_init( &R );
63  mpi_init( &k );
64  mpi_init( &e );
65 
66  sign_tries = 0;
67  do
68  {
69  /*
70  * Steps 1-3: generate a suitable ephemeral keypair
71  * and set r = xR mod n
72  */
73  key_tries = 0;
74  do
75  {
76  MPI_CHK( ecp_gen_keypair( grp, &k, &R, f_rng, p_rng ) );
77  MPI_CHK( mpi_mod_mpi( r, &R.X, &grp->N ) );
78 
79  if( key_tries++ > 10 )
80  {
82  goto cleanup;
83  }
84  }
85  while( mpi_cmp_int( r, 0 ) == 0 );
86 
87  /*
88  * Step 5: derive MPI from hashed message
89  */
90  MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
91 
92  /*
93  * Step 6: compute s = (e + r * d) / k mod n
94  */
95  MPI_CHK( mpi_mul_mpi( s, r, d ) );
96  MPI_CHK( mpi_add_mpi( &e, &e, s ) );
97  MPI_CHK( mpi_inv_mod( s, &k, &grp->N ) );
98  MPI_CHK( mpi_mul_mpi( s, s, &e ) );
99  MPI_CHK( mpi_mod_mpi( s, s, &grp->N ) );
100 
101  if( sign_tries++ > 10 )
102  {
104  goto cleanup;
105  }
106  }
107  while( mpi_cmp_int( s, 0 ) == 0 );
108 
109 cleanup:
110  ecp_point_free( &R );
111  mpi_free( &k );
112  mpi_free( &e );
113 
114  return( ret );
115 }
116 
117 /*
118  * Verify ECDSA signature of hashed message (SEC1 4.1.4)
119  * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)
120  */
121 int ecdsa_verify( ecp_group *grp,
122  const unsigned char *buf, size_t blen,
123  const ecp_point *Q, const mpi *r, const mpi *s)
124 {
125  int ret;
126  mpi e, s_inv, u1, u2;
127  ecp_point R, P;
128 
129  ecp_point_init( &R ); ecp_point_init( &P );
130  mpi_init( &e ); mpi_init( &s_inv ); mpi_init( &u1 ); mpi_init( &u2 );
131 
132  /*
133  * Step 1: make sure r and s are in range 1..n-1
134  */
135  if( mpi_cmp_int( r, 1 ) < 0 || mpi_cmp_mpi( r, &grp->N ) >= 0 ||
136  mpi_cmp_int( s, 1 ) < 0 || mpi_cmp_mpi( s, &grp->N ) >= 0 )
137  {
139  goto cleanup;
140  }
141 
142  /*
143  * Additional precaution: make sure Q is valid
144  */
145  MPI_CHK( ecp_check_pubkey( grp, Q ) );
146 
147  /*
148  * Step 3: derive MPI from hashed message
149  */
150  MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
151 
152  /*
153  * Step 4: u1 = e / s mod n, u2 = r / s mod n
154  */
155  MPI_CHK( mpi_inv_mod( &s_inv, s, &grp->N ) );
156 
157  MPI_CHK( mpi_mul_mpi( &u1, &e, &s_inv ) );
158  MPI_CHK( mpi_mod_mpi( &u1, &u1, &grp->N ) );
159 
160  MPI_CHK( mpi_mul_mpi( &u2, r, &s_inv ) );
161  MPI_CHK( mpi_mod_mpi( &u2, &u2, &grp->N ) );
162 
163  /*
164  * Step 5: R = u1 G + u2 Q
165  *
166  * Since we're not using any secret data, no need to pass a RNG to
167  * ecp_mul() for countermesures.
168  */
169  MPI_CHK( ecp_mul( grp, &R, &u1, &grp->G, NULL, NULL ) );
170  MPI_CHK( ecp_mul( grp, &P, &u2, Q, NULL, NULL ) );
171  MPI_CHK( ecp_add( grp, &R, &R, &P ) );
172 
173  if( ecp_is_zero( &R ) )
174  {
176  goto cleanup;
177  }
178 
179  /*
180  * Step 6: convert xR to an integer (no-op)
181  * Step 7: reduce xR mod n (gives v)
182  */
183  MPI_CHK( mpi_mod_mpi( &R.X, &R.X, &grp->N ) );
184 
185  /*
186  * Step 8: check if v (that is, R.X) is equal to r
187  */
188  if( mpi_cmp_mpi( &R.X, r ) != 0 )
189  {
191  goto cleanup;
192  }
193 
194 cleanup:
195  ecp_point_free( &R ); ecp_point_free( &P );
196  mpi_free( &e ); mpi_free( &s_inv ); mpi_free( &u1 ); mpi_free( &u2 );
197 
198  return( ret );
199 }
200 
201 /*
202  * RFC 4492 page 20:
203  *
204  * Ecdsa-Sig-Value ::= SEQUENCE {
205  * r INTEGER,
206  * s INTEGER
207  * }
208  *
209  * Size is at most
210  * 1 (tag) + 1 (len) + 1 (initial 0) + ECP_MAX_BYTES for each of r and s,
211  * twice that + 1 (tag) + 2 (len) for the sequence
212  * (assuming ECP_MAX_BYTES is less than 126 for r and s,
213  * and less than 124 (total len <= 255) for the sequence)
214  */
215 #if POLARSSL_ECP_MAX_BYTES > 124
216 #error "POLARSSL_ECP_MAX_BYTES bigger than expected, please fix MAX_SIG_LEN"
217 #endif
218 #define MAX_SIG_LEN ( 3 + 2 * ( 2 + POLARSSL_ECP_MAX_BYTES ) )
219 
220 /*
221  * Compute and write signature
222  */
224  const unsigned char *hash, size_t hlen,
225  unsigned char *sig, size_t *slen,
226  int (*f_rng)(void *, unsigned char *, size_t),
227  void *p_rng )
228 {
229  int ret;
230  unsigned char buf[MAX_SIG_LEN];
231  unsigned char *p = buf + sizeof( buf );
232  size_t len = 0;
233 
234  if( ( ret = ecdsa_sign( &ctx->grp, &ctx->r, &ctx->s, &ctx->d,
235  hash, hlen, f_rng, p_rng ) ) != 0 )
236  {
237  return( ret );
238  }
239 
240  ASN1_CHK_ADD( len, asn1_write_mpi( &p, buf, &ctx->s ) );
241  ASN1_CHK_ADD( len, asn1_write_mpi( &p, buf, &ctx->r ) );
242 
243  ASN1_CHK_ADD( len, asn1_write_len( &p, buf, len ) );
244  ASN1_CHK_ADD( len, asn1_write_tag( &p, buf,
246 
247  memcpy( sig, p, len );
248  *slen = len;
249 
250  return( 0 );
251 }
252 
253 /*
254  * Read and check signature
255  */
257  const unsigned char *hash, size_t hlen,
258  const unsigned char *sig, size_t slen )
259 {
260  int ret;
261  unsigned char *p = (unsigned char *) sig;
262  const unsigned char *end = sig + slen;
263  size_t len;
264 
265  if( ( ret = asn1_get_tag( &p, end, &len,
266  ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 )
267  {
268  return( POLARSSL_ERR_ECP_BAD_INPUT_DATA + ret );
269  }
270 
271  if( p + len != end )
274 
275  if( ( ret = asn1_get_mpi( &p, end, &ctx->r ) ) != 0 ||
276  ( ret = asn1_get_mpi( &p, end, &ctx->s ) ) != 0 )
277  return( POLARSSL_ERR_ECP_BAD_INPUT_DATA + ret );
278 
279  if( p != end )
282 
283  return( ecdsa_verify( &ctx->grp, hash, hlen, &ctx->Q, &ctx->r, &ctx->s ) );
284 }
285 
286 /*
287  * Generate key pair
288  */
290  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
291 {
292  return( ecp_use_known_dp( &ctx->grp, gid ) ||
293  ecp_gen_keypair( &ctx->grp, &ctx->d, &ctx->Q, f_rng, p_rng ) );
294 }
295 
296 /*
297  * Set context from an ecp_keypair
298  */
299 int ecdsa_from_keypair( ecdsa_context *ctx, const ecp_keypair *key )
300 {
301  int ret;
302 
303  if( ( ret = ecp_group_copy( &ctx->grp, &key->grp ) ) != 0 ||
304  ( ret = mpi_copy( &ctx->d, &key->d ) ) != 0 ||
305  ( ret = ecp_copy( &ctx->Q, &key->Q ) ) != 0 )
306  {
307  ecdsa_free( ctx );
308  }
309 
310  return( ret );
311 }
312 
313 /*
314  * Initialize context
315  */
316 void ecdsa_init( ecdsa_context *ctx )
317 {
318  ecp_group_init( &ctx->grp );
319  mpi_init( &ctx->d );
320  ecp_point_init( &ctx->Q );
321  mpi_init( &ctx->r );
322  mpi_init( &ctx->s );
323 }
324 
325 /*
326  * Free context
327  */
328 void ecdsa_free( ecdsa_context *ctx )
329 {
330  ecp_group_free( &ctx->grp );
331  mpi_free( &ctx->d );
332  ecp_point_free( &ctx->Q );
333  mpi_free( &ctx->r );
334  mpi_free( &ctx->s );
335 }
336 
337 #if defined(POLARSSL_SELF_TEST)
338 
339 /*
340  * Checkup routine
341  */
342 int ecdsa_self_test( int verbose )
343 {
344  return( verbose++ );
345 }
346 
347 #endif
348 
349 #endif /* defined(POLARSSL_ECDSA_C) */
int mpi_cmp_int(const mpi *X, t_sint z)
Compare signed values.
int ecdsa_from_keypair(ecdsa_context *ctx, const ecp_keypair *key)
Set an ECDSA context from an EC key pair.
int ecdsa_verify(ecp_group *grp, const unsigned char *buf, size_t blen, const ecp_point *Q, const mpi *r, const mpi *s)
Verify ECDSA signature of a previously hashed message.
#define POLARSSL_ERR_ECP_BAD_INPUT_DATA
Bad input parameters to function.
Definition: ecp.h:35
int ecp_group_copy(ecp_group *dst, const ecp_group *src)
Copy the contents of a group object.
#define POLARSSL_ERR_ASN1_LENGTH_MISMATCH
Actual length differs from expected length.
Definition: asn1.h:53
int ecdsa_write_signature(ecdsa_context *ctx, const unsigned char *hash, size_t hlen, unsigned char *sig, size_t *slen, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Compute ECDSA signature and write it to buffer, serialized as defined in RFC 4492 page 20...
Elliptic curve DSA.
ecp_group grp
Definition: ecp.h:146
#define ASN1_SEQUENCE
Definition: asn1.h:78
int ecdsa_sign(ecp_group *grp, mpi *r, mpi *s, const mpi *d, const unsigned char *buf, size_t blen, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Compute ECDSA signature of a previously hashed message.
ECP group structure.
Definition: ecp.h:117
Configuration options (set of defines)
int ecdsa_self_test(int verbose)
Checkup routine.
ecp_group grp
Definition: ecdsa.h:39
#define ASN1_CONSTRUCTED
Definition: asn1.h:88
ECP key pair structure.
Definition: ecp.h:144
mpi d
Definition: ecp.h:147
MPI structure.
Definition: bignum.h:171
int ecp_mul(ecp_group *grp, ecp_point *R, const mpi *m, const ecp_point *P, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Multiplication by an integer: R = m * P (Not thread-safe to use same group in multiple threads) ...
void mpi_init(mpi *X)
Initialize one MPI.
mpi X
Definition: ecp.h:96
int mpi_cmp_mpi(const mpi *X, const mpi *Y)
Compare signed values.
int asn1_write_len(unsigned char **p, unsigned char *start, size_t len)
Write a length field in ASN.1 format Note: function works backwards in data buffer.
int mpi_add_mpi(mpi *X, const mpi *A, const mpi *B)
Signed addition: X = A + B.
#define POLARSSL_ERR_ECP_VERIFY_FAILED
The signature is not valid.
Definition: ecp.h:38
ecp_point G
Definition: ecp.h:123
ECP point structure (jacobian coordinates)
Definition: ecp.h:94
int ecp_is_zero(ecp_point *pt)
Tell if a point is zero.
void ecp_point_init(ecp_point *pt)
Initialize a point (as zero)
mpi N
Definition: ecp.h:124
int mpi_inv_mod(mpi *X, const mpi *A, const mpi *N)
Modular inverse: X = A^-1 mod N.
ECDSA context structure.
Definition: ecdsa.h:37
void mpi_free(mpi *X)
Unallocate one MPI.
void ecp_group_free(ecp_group *grp)
Free the components of an ECP group.
int ecdsa_read_signature(ecdsa_context *ctx, const unsigned char *hash, size_t hlen, const unsigned char *sig, size_t slen)
Read and verify an ECDSA signature.
ecp_point Q
Definition: ecdsa.h:41
void ecdsa_init(ecdsa_context *ctx)
Initialize context.
int ecp_gen_keypair(ecp_group *grp, mpi *d, ecp_point *Q, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Generate a keypair.
int asn1_write_mpi(unsigned char **p, unsigned char *start, mpi *X)
Write a big number (ASN1_INTEGER) in ASN.1 format Note: function works backwards in data buffer...
int ecp_use_known_dp(ecp_group *grp, ecp_group_id index)
Set a group using well-known domain parameters.
int ecp_copy(ecp_point *P, const ecp_point *Q)
Copy the contents of point Q into P.
int mpi_read_binary(mpi *X, const unsigned char *buf, size_t buflen)
Import X from unsigned binary data, big endian.
ecp_group_id
Domain parameters (curve, subgroup and generator) identifiers.
Definition: ecp.h:56
#define ASN1_CHK_ADD(g, f)
Definition: asn1write.h:32
int ecdsa_genkey(ecdsa_context *ctx, ecp_group_id gid, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Generate an ECDSA keypair on the given curve.
void ecp_group_init(ecp_group *grp)
Initialize a group (to something meaningless)
size_t nbits
Definition: ecp.h:126
#define POLARSSL_ERR_ECP_RANDOM_FAILED
Generation of random value, such as (ephemeral) key, failed.
Definition: ecp.h:40
int mpi_copy(mpi *X, const mpi *Y)
Copy the contents of Y into X.
int mpi_mod_mpi(mpi *R, const mpi *A, const mpi *B)
Modulo: R = A mod B.
int asn1_get_tag(unsigned char **p, const unsigned char *end, size_t *len, int tag)
Get the tag and length of the tag.
void ecdsa_free(ecdsa_context *ctx)
Free context.
ASN.1 buffer writing functionality.
ecp_point Q
Definition: ecp.h:148
int ecp_check_pubkey(const ecp_group *grp, const ecp_point *pt)
Check that a point is a valid public key on this curve.
int ecp_add(const ecp_group *grp, ecp_point *R, const ecp_point *P, const ecp_point *Q)
Addition: R = P + Q.
int asn1_write_tag(unsigned char **p, unsigned char *start, unsigned char tag)
Write a ASN.1 tag in ASN.1 format Note: function works backwards in data buffer.
int mpi_mul_mpi(mpi *X, const mpi *A, const mpi *B)
Baseline multiplication: X = A * B.
int asn1_get_mpi(unsigned char **p, const unsigned char *end, mpi *X)
Retrieve a MPI value from an integer ASN.1 tag.
#define MPI_CHK(f)
Definition: bignum.h:61
void ecp_point_free(ecp_point *pt)
Free the components of a point.