PolarSSL v1.3.3
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  /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
63  if( grp->N.p == NULL )
65 
66  ecp_point_init( &R );
67  mpi_init( &k );
68  mpi_init( &e );
69 
70  sign_tries = 0;
71  do
72  {
73  /*
74  * Steps 1-3: generate a suitable ephemeral keypair
75  * and set r = xR mod n
76  */
77  key_tries = 0;
78  do
79  {
80  MPI_CHK( ecp_gen_keypair( grp, &k, &R, f_rng, p_rng ) );
81  MPI_CHK( mpi_mod_mpi( r, &R.X, &grp->N ) );
82 
83  if( key_tries++ > 10 )
84  {
86  goto cleanup;
87  }
88  }
89  while( mpi_cmp_int( r, 0 ) == 0 );
90 
91  /*
92  * Step 5: derive MPI from hashed message
93  */
94  MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
95 
96  /*
97  * Step 6: compute s = (e + r * d) / k mod n
98  */
99  MPI_CHK( mpi_mul_mpi( s, r, d ) );
100  MPI_CHK( mpi_add_mpi( &e, &e, s ) );
101  MPI_CHK( mpi_inv_mod( s, &k, &grp->N ) );
102  MPI_CHK( mpi_mul_mpi( s, s, &e ) );
103  MPI_CHK( mpi_mod_mpi( s, s, &grp->N ) );
104 
105  if( sign_tries++ > 10 )
106  {
108  goto cleanup;
109  }
110  }
111  while( mpi_cmp_int( s, 0 ) == 0 );
112 
113 cleanup:
114  ecp_point_free( &R );
115  mpi_free( &k );
116  mpi_free( &e );
117 
118  return( ret );
119 }
120 
121 /*
122  * Verify ECDSA signature of hashed message (SEC1 4.1.4)
123  * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)
124  */
125 int ecdsa_verify( ecp_group *grp,
126  const unsigned char *buf, size_t blen,
127  const ecp_point *Q, const mpi *r, const mpi *s)
128 {
129  int ret;
130  mpi e, s_inv, u1, u2;
131  ecp_point R, P;
132 
133  ecp_point_init( &R ); ecp_point_init( &P );
134  mpi_init( &e ); mpi_init( &s_inv ); mpi_init( &u1 ); mpi_init( &u2 );
135 
136  /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
137  if( grp->N.p == NULL )
139 
140  /*
141  * Step 1: make sure r and s are in range 1..n-1
142  */
143  if( mpi_cmp_int( r, 1 ) < 0 || mpi_cmp_mpi( r, &grp->N ) >= 0 ||
144  mpi_cmp_int( s, 1 ) < 0 || mpi_cmp_mpi( s, &grp->N ) >= 0 )
145  {
147  goto cleanup;
148  }
149 
150  /*
151  * Additional precaution: make sure Q is valid
152  */
153  MPI_CHK( ecp_check_pubkey( grp, Q ) );
154 
155  /*
156  * Step 3: derive MPI from hashed message
157  */
158  MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
159 
160  /*
161  * Step 4: u1 = e / s mod n, u2 = r / s mod n
162  */
163  MPI_CHK( mpi_inv_mod( &s_inv, s, &grp->N ) );
164 
165  MPI_CHK( mpi_mul_mpi( &u1, &e, &s_inv ) );
166  MPI_CHK( mpi_mod_mpi( &u1, &u1, &grp->N ) );
167 
168  MPI_CHK( mpi_mul_mpi( &u2, r, &s_inv ) );
169  MPI_CHK( mpi_mod_mpi( &u2, &u2, &grp->N ) );
170 
171  /*
172  * Step 5: R = u1 G + u2 Q
173  *
174  * Since we're not using any secret data, no need to pass a RNG to
175  * ecp_mul() for countermesures.
176  */
177  MPI_CHK( ecp_mul( grp, &R, &u1, &grp->G, NULL, NULL ) );
178  MPI_CHK( ecp_mul( grp, &P, &u2, Q, NULL, NULL ) );
179  MPI_CHK( ecp_add( grp, &R, &R, &P ) );
180 
181  if( ecp_is_zero( &R ) )
182  {
184  goto cleanup;
185  }
186 
187  /*
188  * Step 6: convert xR to an integer (no-op)
189  * Step 7: reduce xR mod n (gives v)
190  */
191  MPI_CHK( mpi_mod_mpi( &R.X, &R.X, &grp->N ) );
192 
193  /*
194  * Step 8: check if v (that is, R.X) is equal to r
195  */
196  if( mpi_cmp_mpi( &R.X, r ) != 0 )
197  {
199  goto cleanup;
200  }
201 
202 cleanup:
203  ecp_point_free( &R ); ecp_point_free( &P );
204  mpi_free( &e ); mpi_free( &s_inv ); mpi_free( &u1 ); mpi_free( &u2 );
205 
206  return( ret );
207 }
208 
209 /*
210  * RFC 4492 page 20:
211  *
212  * Ecdsa-Sig-Value ::= SEQUENCE {
213  * r INTEGER,
214  * s INTEGER
215  * }
216  *
217  * Size is at most
218  * 1 (tag) + 1 (len) + 1 (initial 0) + ECP_MAX_BYTES for each of r and s,
219  * twice that + 1 (tag) + 2 (len) for the sequence
220  * (assuming ECP_MAX_BYTES is less than 126 for r and s,
221  * and less than 124 (total len <= 255) for the sequence)
222  */
223 #if POLARSSL_ECP_MAX_BYTES > 124
224 #error "POLARSSL_ECP_MAX_BYTES bigger than expected, please fix MAX_SIG_LEN"
225 #endif
226 #define MAX_SIG_LEN ( 3 + 2 * ( 2 + POLARSSL_ECP_MAX_BYTES ) )
227 
228 /*
229  * Compute and write signature
230  */
232  const unsigned char *hash, size_t hlen,
233  unsigned char *sig, size_t *slen,
234  int (*f_rng)(void *, unsigned char *, size_t),
235  void *p_rng )
236 {
237  int ret;
238  unsigned char buf[MAX_SIG_LEN];
239  unsigned char *p = buf + sizeof( buf );
240  size_t len = 0;
241 
242  if( ( ret = ecdsa_sign( &ctx->grp, &ctx->r, &ctx->s, &ctx->d,
243  hash, hlen, f_rng, p_rng ) ) != 0 )
244  {
245  return( ret );
246  }
247 
248  ASN1_CHK_ADD( len, asn1_write_mpi( &p, buf, &ctx->s ) );
249  ASN1_CHK_ADD( len, asn1_write_mpi( &p, buf, &ctx->r ) );
250 
251  ASN1_CHK_ADD( len, asn1_write_len( &p, buf, len ) );
252  ASN1_CHK_ADD( len, asn1_write_tag( &p, buf,
254 
255  memcpy( sig, p, len );
256  *slen = len;
257 
258  return( 0 );
259 }
260 
261 /*
262  * Read and check signature
263  */
265  const unsigned char *hash, size_t hlen,
266  const unsigned char *sig, size_t slen )
267 {
268  int ret;
269  unsigned char *p = (unsigned char *) sig;
270  const unsigned char *end = sig + slen;
271  size_t len;
272 
273  if( ( ret = asn1_get_tag( &p, end, &len,
274  ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 )
275  {
276  return( POLARSSL_ERR_ECP_BAD_INPUT_DATA + ret );
277  }
278 
279  if( p + len != end )
282 
283  if( ( ret = asn1_get_mpi( &p, end, &ctx->r ) ) != 0 ||
284  ( ret = asn1_get_mpi( &p, end, &ctx->s ) ) != 0 )
285  return( POLARSSL_ERR_ECP_BAD_INPUT_DATA + ret );
286 
287  if( p != end )
290 
291  return( ecdsa_verify( &ctx->grp, hash, hlen, &ctx->Q, &ctx->r, &ctx->s ) );
292 }
293 
294 /*
295  * Generate key pair
296  */
298  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
299 {
300  return( ecp_use_known_dp( &ctx->grp, gid ) ||
301  ecp_gen_keypair( &ctx->grp, &ctx->d, &ctx->Q, f_rng, p_rng ) );
302 }
303 
304 /*
305  * Set context from an ecp_keypair
306  */
307 int ecdsa_from_keypair( ecdsa_context *ctx, const ecp_keypair *key )
308 {
309  int ret;
310 
311  if( ( ret = ecp_group_copy( &ctx->grp, &key->grp ) ) != 0 ||
312  ( ret = mpi_copy( &ctx->d, &key->d ) ) != 0 ||
313  ( ret = ecp_copy( &ctx->Q, &key->Q ) ) != 0 )
314  {
315  ecdsa_free( ctx );
316  }
317 
318  return( ret );
319 }
320 
321 /*
322  * Initialize context
323  */
324 void ecdsa_init( ecdsa_context *ctx )
325 {
326  ecp_group_init( &ctx->grp );
327  mpi_init( &ctx->d );
328  ecp_point_init( &ctx->Q );
329  mpi_init( &ctx->r );
330  mpi_init( &ctx->s );
331 }
332 
333 /*
334  * Free context
335  */
336 void ecdsa_free( ecdsa_context *ctx )
337 {
338  ecp_group_free( &ctx->grp );
339  mpi_free( &ctx->d );
340  ecp_point_free( &ctx->Q );
341  mpi_free( &ctx->r );
342  mpi_free( &ctx->s );
343 }
344 
345 #if defined(POLARSSL_SELF_TEST)
346 
347 /*
348  * Checkup routine
349  */
350 int ecdsa_self_test( int verbose )
351 {
352  return( verbose++ );
353 }
354 
355 #endif
356 
357 #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:158
#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:129
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:156
mpi d
Definition: ecp.h:159
MPI structure.
Definition: bignum.h:177
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:102
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:135
ECP point structure (jacobian coordinates)
Definition: ecp.h:100
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:136
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.
t_uint * p
Definition: bignum.h:181
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:138
#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:160
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.