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