1 /*
2 * Elliptic curve DSA
3 *
4 * Copyright The Mbed TLS Contributors
5 * SPDX-License-Identifier: Apache-2.0
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License"); you may
8 * not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20 /*
21 * References:
22 *
23 * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
24 */
25
26 #include "common.h"
27
28 #if defined(MBEDTLS_ECDSA_C)
29
30 #include "mbedtls/ecdsa.h"
31 #include "mbedtls/asn1write.h"
32
33 #include <string.h>
34
35 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
36 #include "mbedtls/hmac_drbg.h"
37 #endif
38
39 #include "mbedtls/platform.h"
40
41 #include "mbedtls/platform_util.h"
42 #include "mbedtls/error.h"
43
44 #if defined(MBEDTLS_ECP_RESTARTABLE)
45
46 /*
47 * Sub-context for ecdsa_verify()
48 */
49 struct mbedtls_ecdsa_restart_ver
50 {
51 mbedtls_mpi u1, u2; /* intermediate values */
52 enum { /* what to do next? */
53 ecdsa_ver_init = 0, /* getting started */
54 ecdsa_ver_muladd, /* muladd step */
55 } state;
56 };
57
58 /*
59 * Init verify restart sub-context
60 */
ecdsa_restart_ver_init(mbedtls_ecdsa_restart_ver_ctx * ctx)61 static void ecdsa_restart_ver_init( mbedtls_ecdsa_restart_ver_ctx *ctx )
62 {
63 mbedtls_mpi_init( &ctx->u1 );
64 mbedtls_mpi_init( &ctx->u2 );
65 ctx->state = ecdsa_ver_init;
66 }
67
68 /*
69 * Free the components of a verify restart sub-context
70 */
ecdsa_restart_ver_free(mbedtls_ecdsa_restart_ver_ctx * ctx)71 static void ecdsa_restart_ver_free( mbedtls_ecdsa_restart_ver_ctx *ctx )
72 {
73 if( ctx == NULL )
74 return;
75
76 mbedtls_mpi_free( &ctx->u1 );
77 mbedtls_mpi_free( &ctx->u2 );
78
79 ecdsa_restart_ver_init( ctx );
80 }
81
82 /*
83 * Sub-context for ecdsa_sign()
84 */
85 struct mbedtls_ecdsa_restart_sig
86 {
87 int sign_tries;
88 int key_tries;
89 mbedtls_mpi k; /* per-signature random */
90 mbedtls_mpi r; /* r value */
91 enum { /* what to do next? */
92 ecdsa_sig_init = 0, /* getting started */
93 ecdsa_sig_mul, /* doing ecp_mul() */
94 ecdsa_sig_modn, /* mod N computations */
95 } state;
96 };
97
98 /*
99 * Init verify sign sub-context
100 */
ecdsa_restart_sig_init(mbedtls_ecdsa_restart_sig_ctx * ctx)101 static void ecdsa_restart_sig_init( mbedtls_ecdsa_restart_sig_ctx *ctx )
102 {
103 ctx->sign_tries = 0;
104 ctx->key_tries = 0;
105 mbedtls_mpi_init( &ctx->k );
106 mbedtls_mpi_init( &ctx->r );
107 ctx->state = ecdsa_sig_init;
108 }
109
110 /*
111 * Free the components of a sign restart sub-context
112 */
ecdsa_restart_sig_free(mbedtls_ecdsa_restart_sig_ctx * ctx)113 static void ecdsa_restart_sig_free( mbedtls_ecdsa_restart_sig_ctx *ctx )
114 {
115 if( ctx == NULL )
116 return;
117
118 mbedtls_mpi_free( &ctx->k );
119 mbedtls_mpi_free( &ctx->r );
120 }
121
122 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
123 /*
124 * Sub-context for ecdsa_sign_det()
125 */
126 struct mbedtls_ecdsa_restart_det
127 {
128 mbedtls_hmac_drbg_context rng_ctx; /* DRBG state */
129 enum { /* what to do next? */
130 ecdsa_det_init = 0, /* getting started */
131 ecdsa_det_sign, /* make signature */
132 } state;
133 };
134
135 /*
136 * Init verify sign_det sub-context
137 */
ecdsa_restart_det_init(mbedtls_ecdsa_restart_det_ctx * ctx)138 static void ecdsa_restart_det_init( mbedtls_ecdsa_restart_det_ctx *ctx )
139 {
140 mbedtls_hmac_drbg_init( &ctx->rng_ctx );
141 ctx->state = ecdsa_det_init;
142 }
143
144 /*
145 * Free the components of a sign_det restart sub-context
146 */
ecdsa_restart_det_free(mbedtls_ecdsa_restart_det_ctx * ctx)147 static void ecdsa_restart_det_free( mbedtls_ecdsa_restart_det_ctx *ctx )
148 {
149 if( ctx == NULL )
150 return;
151
152 mbedtls_hmac_drbg_free( &ctx->rng_ctx );
153
154 ecdsa_restart_det_init( ctx );
155 }
156 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
157
158 #define ECDSA_RS_ECP ( rs_ctx == NULL ? NULL : &rs_ctx->ecp )
159
160 /* Utility macro for checking and updating ops budget */
161 #define ECDSA_BUDGET( ops ) \
162 MBEDTLS_MPI_CHK( mbedtls_ecp_check_budget( grp, ECDSA_RS_ECP, ops ) );
163
164 /* Call this when entering a function that needs its own sub-context */
165 #define ECDSA_RS_ENTER( SUB ) do { \
166 /* reset ops count for this call if top-level */ \
167 if( rs_ctx != NULL && rs_ctx->ecp.depth++ == 0 ) \
168 rs_ctx->ecp.ops_done = 0; \
169 \
170 /* set up our own sub-context if needed */ \
171 if( mbedtls_ecp_restart_is_enabled() && \
172 rs_ctx != NULL && rs_ctx->SUB == NULL ) \
173 { \
174 rs_ctx->SUB = mbedtls_calloc( 1, sizeof( *rs_ctx->SUB ) ); \
175 if( rs_ctx->SUB == NULL ) \
176 return( MBEDTLS_ERR_ECP_ALLOC_FAILED ); \
177 \
178 ecdsa_restart_## SUB ##_init( rs_ctx->SUB ); \
179 } \
180 } while( 0 )
181
182 /* Call this when leaving a function that needs its own sub-context */
183 #define ECDSA_RS_LEAVE( SUB ) do { \
184 /* clear our sub-context when not in progress (done or error) */ \
185 if( rs_ctx != NULL && rs_ctx->SUB != NULL && \
186 ret != MBEDTLS_ERR_ECP_IN_PROGRESS ) \
187 { \
188 ecdsa_restart_## SUB ##_free( rs_ctx->SUB ); \
189 mbedtls_free( rs_ctx->SUB ); \
190 rs_ctx->SUB = NULL; \
191 } \
192 \
193 if( rs_ctx != NULL ) \
194 rs_ctx->ecp.depth--; \
195 } while( 0 )
196
197 #else /* MBEDTLS_ECP_RESTARTABLE */
198
199 #define ECDSA_RS_ECP NULL
200
201 #define ECDSA_BUDGET( ops ) /* no-op; for compatibility */
202
203 #define ECDSA_RS_ENTER( SUB ) (void) rs_ctx
204 #define ECDSA_RS_LEAVE( SUB ) (void) rs_ctx
205
206 #endif /* MBEDTLS_ECP_RESTARTABLE */
207
208 #if defined(MBEDTLS_ECDSA_DETERMINISTIC) || \
209 !defined(MBEDTLS_ECDSA_SIGN_ALT) || \
210 !defined(MBEDTLS_ECDSA_VERIFY_ALT)
211 /*
212 * Derive a suitable integer for group grp from a buffer of length len
213 * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3
214 */
derive_mpi(const mbedtls_ecp_group * grp,mbedtls_mpi * x,const unsigned char * buf,size_t blen)215 static int derive_mpi( const mbedtls_ecp_group *grp, mbedtls_mpi *x,
216 const unsigned char *buf, size_t blen )
217 {
218 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
219 size_t n_size = ( grp->nbits + 7 ) / 8;
220 size_t use_size = blen > n_size ? n_size : blen;
221
222 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( x, buf, use_size ) );
223 if( use_size * 8 > grp->nbits )
224 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( x, use_size * 8 - grp->nbits ) );
225
226 /* While at it, reduce modulo N */
227 if( mbedtls_mpi_cmp_mpi( x, &grp->N ) >= 0 )
228 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( x, x, &grp->N ) );
229
230 cleanup:
231 return( ret );
232 }
233 #endif /* ECDSA_DETERMINISTIC || !ECDSA_SIGN_ALT || !ECDSA_VERIFY_ALT */
234
235 #if !defined(MBEDTLS_ECDSA_SIGN_ALT)
236 /*
237 * Compute ECDSA signature of a hashed message (SEC1 4.1.3)
238 * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message)
239 */
ecdsa_sign_restartable(mbedtls_ecp_group * grp,mbedtls_mpi * r,mbedtls_mpi * s,const mbedtls_mpi * d,const unsigned char * buf,size_t blen,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng,int (* f_rng_blind)(void *,unsigned char *,size_t),void * p_rng_blind,mbedtls_ecdsa_restart_ctx * rs_ctx)240 static int ecdsa_sign_restartable( mbedtls_ecp_group *grp,
241 mbedtls_mpi *r, mbedtls_mpi *s,
242 const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
243 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,
244 int (*f_rng_blind)(void *, unsigned char *, size_t),
245 void *p_rng_blind,
246 mbedtls_ecdsa_restart_ctx *rs_ctx )
247 {
248 int ret, key_tries, sign_tries;
249 int *p_sign_tries = &sign_tries, *p_key_tries = &key_tries;
250 mbedtls_ecp_point R;
251 mbedtls_mpi k, e, t;
252 mbedtls_mpi *pk = &k, *pr = r;
253
254 /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
255 if( ! mbedtls_ecdsa_can_do( grp->id ) || grp->N.p == NULL )
256 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
257
258 /* Make sure d is in range 1..n-1 */
259 if( mbedtls_mpi_cmp_int( d, 1 ) < 0 || mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 )
260 return( MBEDTLS_ERR_ECP_INVALID_KEY );
261
262 mbedtls_ecp_point_init( &R );
263 mbedtls_mpi_init( &k ); mbedtls_mpi_init( &e ); mbedtls_mpi_init( &t );
264
265 ECDSA_RS_ENTER( sig );
266
267 #if defined(MBEDTLS_ECP_RESTARTABLE)
268 if( rs_ctx != NULL && rs_ctx->sig != NULL )
269 {
270 /* redirect to our context */
271 p_sign_tries = &rs_ctx->sig->sign_tries;
272 p_key_tries = &rs_ctx->sig->key_tries;
273 pk = &rs_ctx->sig->k;
274 pr = &rs_ctx->sig->r;
275
276 /* jump to current step */
277 if( rs_ctx->sig->state == ecdsa_sig_mul )
278 goto mul;
279 if( rs_ctx->sig->state == ecdsa_sig_modn )
280 goto modn;
281 }
282 #endif /* MBEDTLS_ECP_RESTARTABLE */
283
284 *p_sign_tries = 0;
285 do
286 {
287 if( (*p_sign_tries)++ > 10 )
288 {
289 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
290 goto cleanup;
291 }
292
293 /*
294 * Steps 1-3: generate a suitable ephemeral keypair
295 * and set r = xR mod n
296 */
297 *p_key_tries = 0;
298 do
299 {
300 if( (*p_key_tries)++ > 10 )
301 {
302 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
303 goto cleanup;
304 }
305
306 MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, pk, f_rng, p_rng ) );
307
308 #if defined(MBEDTLS_ECP_RESTARTABLE)
309 if( rs_ctx != NULL && rs_ctx->sig != NULL )
310 rs_ctx->sig->state = ecdsa_sig_mul;
311
312 mul:
313 #endif
314 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_restartable( grp, &R, pk, &grp->G,
315 f_rng_blind,
316 p_rng_blind,
317 ECDSA_RS_ECP ) );
318 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( pr, &R.X, &grp->N ) );
319 }
320 while( mbedtls_mpi_cmp_int( pr, 0 ) == 0 );
321
322 #if defined(MBEDTLS_ECP_RESTARTABLE)
323 if( rs_ctx != NULL && rs_ctx->sig != NULL )
324 rs_ctx->sig->state = ecdsa_sig_modn;
325
326 modn:
327 #endif
328 /*
329 * Accounting for everything up to the end of the loop
330 * (step 6, but checking now avoids saving e and t)
331 */
332 ECDSA_BUDGET( MBEDTLS_ECP_OPS_INV + 4 );
333
334 /*
335 * Step 5: derive MPI from hashed message
336 */
337 MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
338
339 /*
340 * Generate a random value to blind inv_mod in next step,
341 * avoiding a potential timing leak.
342 */
343 MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, &t, f_rng_blind,
344 p_rng_blind ) );
345
346 /*
347 * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n
348 */
349 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, pr, d ) );
350 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &e, &e, s ) );
351 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &e, &e, &t ) );
352 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( pk, pk, &t ) );
353 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( pk, pk, &grp->N ) );
354 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( s, pk, &grp->N ) );
355 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, s, &e ) );
356 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( s, s, &grp->N ) );
357 }
358 while( mbedtls_mpi_cmp_int( s, 0 ) == 0 );
359
360 #if defined(MBEDTLS_ECP_RESTARTABLE)
361 if( rs_ctx != NULL && rs_ctx->sig != NULL )
362 mbedtls_mpi_copy( r, pr );
363 #endif
364
365 cleanup:
366 mbedtls_ecp_point_free( &R );
367 mbedtls_mpi_free( &k ); mbedtls_mpi_free( &e ); mbedtls_mpi_free( &t );
368
369 ECDSA_RS_LEAVE( sig );
370
371 return( ret );
372 }
373
mbedtls_ecdsa_can_do(mbedtls_ecp_group_id gid)374 int mbedtls_ecdsa_can_do( mbedtls_ecp_group_id gid )
375 {
376 switch( gid )
377 {
378 #ifdef MBEDTLS_ECP_DP_CURVE25519_ENABLED
379 case MBEDTLS_ECP_DP_CURVE25519: return 0;
380 #endif
381 #ifdef MBEDTLS_ECP_DP_CURVE448_ENABLED
382 case MBEDTLS_ECP_DP_CURVE448: return 0;
383 #endif
384 default: return 1;
385 }
386 }
387
388 /*
389 * Compute ECDSA signature of a hashed message
390 */
mbedtls_ecdsa_sign(mbedtls_ecp_group * grp,mbedtls_mpi * r,mbedtls_mpi * s,const mbedtls_mpi * d,const unsigned char * buf,size_t blen,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)391 int mbedtls_ecdsa_sign( mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,
392 const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
393 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
394 {
395 /* Use the same RNG for both blinding and ephemeral key generation */
396 return( ecdsa_sign_restartable( grp, r, s, d, buf, blen,
397 f_rng, p_rng, f_rng, p_rng, NULL ) );
398 }
399 #endif /* !MBEDTLS_ECDSA_SIGN_ALT */
400
401 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
402 /*
403 * Deterministic signature wrapper
404 *
405 * note: The f_rng_blind parameter must not be NULL.
406 *
407 */
ecdsa_sign_det_restartable(mbedtls_ecp_group * grp,mbedtls_mpi * r,mbedtls_mpi * s,const mbedtls_mpi * d,const unsigned char * buf,size_t blen,mbedtls_md_type_t md_alg,int (* f_rng_blind)(void *,unsigned char *,size_t),void * p_rng_blind,mbedtls_ecdsa_restart_ctx * rs_ctx)408 static int ecdsa_sign_det_restartable( mbedtls_ecp_group *grp,
409 mbedtls_mpi *r, mbedtls_mpi *s,
410 const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
411 mbedtls_md_type_t md_alg,
412 int (*f_rng_blind)(void *, unsigned char *, size_t),
413 void *p_rng_blind,
414 mbedtls_ecdsa_restart_ctx *rs_ctx )
415 {
416 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
417 mbedtls_hmac_drbg_context rng_ctx;
418 mbedtls_hmac_drbg_context *p_rng = &rng_ctx;
419 unsigned char data[2 * MBEDTLS_ECP_MAX_BYTES];
420 size_t grp_len = ( grp->nbits + 7 ) / 8;
421 const mbedtls_md_info_t *md_info;
422 mbedtls_mpi h;
423
424 if( ( md_info = mbedtls_md_info_from_type( md_alg ) ) == NULL )
425 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
426
427 mbedtls_mpi_init( &h );
428 mbedtls_hmac_drbg_init( &rng_ctx );
429
430 ECDSA_RS_ENTER( det );
431
432 #if defined(MBEDTLS_ECP_RESTARTABLE)
433 if( rs_ctx != NULL && rs_ctx->det != NULL )
434 {
435 /* redirect to our context */
436 p_rng = &rs_ctx->det->rng_ctx;
437
438 /* jump to current step */
439 if( rs_ctx->det->state == ecdsa_det_sign )
440 goto sign;
441 }
442 #endif /* MBEDTLS_ECP_RESTARTABLE */
443
444 /* Use private key and message hash (reduced) to initialize HMAC_DRBG */
445 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( d, data, grp_len ) );
446 MBEDTLS_MPI_CHK( derive_mpi( grp, &h, buf, blen ) );
447 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &h, data + grp_len, grp_len ) );
448 mbedtls_hmac_drbg_seed_buf( p_rng, md_info, data, 2 * grp_len );
449
450 #if defined(MBEDTLS_ECP_RESTARTABLE)
451 if( rs_ctx != NULL && rs_ctx->det != NULL )
452 rs_ctx->det->state = ecdsa_det_sign;
453
454 sign:
455 #endif
456 #if defined(MBEDTLS_ECDSA_SIGN_ALT)
457 (void) f_rng_blind;
458 (void) p_rng_blind;
459 ret = mbedtls_ecdsa_sign( grp, r, s, d, buf, blen,
460 mbedtls_hmac_drbg_random, p_rng );
461 #else
462 ret = ecdsa_sign_restartable( grp, r, s, d, buf, blen,
463 mbedtls_hmac_drbg_random, p_rng,
464 f_rng_blind, p_rng_blind, rs_ctx );
465 #endif /* MBEDTLS_ECDSA_SIGN_ALT */
466
467 cleanup:
468 mbedtls_hmac_drbg_free( &rng_ctx );
469 mbedtls_mpi_free( &h );
470
471 ECDSA_RS_LEAVE( det );
472
473 return( ret );
474 }
475
476 /*
477 * Deterministic signature wrapper
478 */
mbedtls_ecdsa_sign_det_ext(mbedtls_ecp_group * grp,mbedtls_mpi * r,mbedtls_mpi * s,const mbedtls_mpi * d,const unsigned char * buf,size_t blen,mbedtls_md_type_t md_alg,int (* f_rng_blind)(void *,unsigned char *,size_t),void * p_rng_blind)479 int mbedtls_ecdsa_sign_det_ext( mbedtls_ecp_group *grp, mbedtls_mpi *r,
480 mbedtls_mpi *s, const mbedtls_mpi *d,
481 const unsigned char *buf, size_t blen,
482 mbedtls_md_type_t md_alg,
483 int (*f_rng_blind)(void *, unsigned char *,
484 size_t),
485 void *p_rng_blind )
486 {
487 return( ecdsa_sign_det_restartable( grp, r, s, d, buf, blen, md_alg,
488 f_rng_blind, p_rng_blind, NULL ) );
489 }
490 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
491
492 #if !defined(MBEDTLS_ECDSA_VERIFY_ALT)
493 /*
494 * Verify ECDSA signature of hashed message (SEC1 4.1.4)
495 * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)
496 */
ecdsa_verify_restartable(mbedtls_ecp_group * grp,const unsigned char * buf,size_t blen,const mbedtls_ecp_point * Q,const mbedtls_mpi * r,const mbedtls_mpi * s,mbedtls_ecdsa_restart_ctx * rs_ctx)497 static int ecdsa_verify_restartable( mbedtls_ecp_group *grp,
498 const unsigned char *buf, size_t blen,
499 const mbedtls_ecp_point *Q,
500 const mbedtls_mpi *r, const mbedtls_mpi *s,
501 mbedtls_ecdsa_restart_ctx *rs_ctx )
502 {
503 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
504 mbedtls_mpi e, s_inv, u1, u2;
505 mbedtls_ecp_point R;
506 mbedtls_mpi *pu1 = &u1, *pu2 = &u2;
507
508 mbedtls_ecp_point_init( &R );
509 mbedtls_mpi_init( &e ); mbedtls_mpi_init( &s_inv );
510 mbedtls_mpi_init( &u1 ); mbedtls_mpi_init( &u2 );
511
512 /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
513 if( ! mbedtls_ecdsa_can_do( grp->id ) || grp->N.p == NULL )
514 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
515
516 ECDSA_RS_ENTER( ver );
517
518 #if defined(MBEDTLS_ECP_RESTARTABLE)
519 if( rs_ctx != NULL && rs_ctx->ver != NULL )
520 {
521 /* redirect to our context */
522 pu1 = &rs_ctx->ver->u1;
523 pu2 = &rs_ctx->ver->u2;
524
525 /* jump to current step */
526 if( rs_ctx->ver->state == ecdsa_ver_muladd )
527 goto muladd;
528 }
529 #endif /* MBEDTLS_ECP_RESTARTABLE */
530
531 /*
532 * Step 1: make sure r and s are in range 1..n-1
533 */
534 if( mbedtls_mpi_cmp_int( r, 1 ) < 0 || mbedtls_mpi_cmp_mpi( r, &grp->N ) >= 0 ||
535 mbedtls_mpi_cmp_int( s, 1 ) < 0 || mbedtls_mpi_cmp_mpi( s, &grp->N ) >= 0 )
536 {
537 ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
538 goto cleanup;
539 }
540
541 /*
542 * Step 3: derive MPI from hashed message
543 */
544 MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
545
546 /*
547 * Step 4: u1 = e / s mod n, u2 = r / s mod n
548 */
549 ECDSA_BUDGET( MBEDTLS_ECP_OPS_CHK + MBEDTLS_ECP_OPS_INV + 2 );
550
551 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &s_inv, s, &grp->N ) );
552
553 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( pu1, &e, &s_inv ) );
554 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( pu1, pu1, &grp->N ) );
555
556 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( pu2, r, &s_inv ) );
557 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( pu2, pu2, &grp->N ) );
558
559 #if defined(MBEDTLS_ECP_RESTARTABLE)
560 if( rs_ctx != NULL && rs_ctx->ver != NULL )
561 rs_ctx->ver->state = ecdsa_ver_muladd;
562
563 muladd:
564 #endif
565 /*
566 * Step 5: R = u1 G + u2 Q
567 */
568 MBEDTLS_MPI_CHK( mbedtls_ecp_muladd_restartable( grp,
569 &R, pu1, &grp->G, pu2, Q, ECDSA_RS_ECP ) );
570
571 if( mbedtls_ecp_is_zero( &R ) )
572 {
573 ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
574 goto cleanup;
575 }
576
577 /*
578 * Step 6: convert xR to an integer (no-op)
579 * Step 7: reduce xR mod n (gives v)
580 */
581 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &R.X, &R.X, &grp->N ) );
582
583 /*
584 * Step 8: check if v (that is, R.X) is equal to r
585 */
586 if( mbedtls_mpi_cmp_mpi( &R.X, r ) != 0 )
587 {
588 ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
589 goto cleanup;
590 }
591
592 cleanup:
593 mbedtls_ecp_point_free( &R );
594 mbedtls_mpi_free( &e ); mbedtls_mpi_free( &s_inv );
595 mbedtls_mpi_free( &u1 ); mbedtls_mpi_free( &u2 );
596
597 ECDSA_RS_LEAVE( ver );
598
599 return( ret );
600 }
601
602 /*
603 * Verify ECDSA signature of hashed message
604 */
mbedtls_ecdsa_verify(mbedtls_ecp_group * grp,const unsigned char * buf,size_t blen,const mbedtls_ecp_point * Q,const mbedtls_mpi * r,const mbedtls_mpi * s)605 int mbedtls_ecdsa_verify( mbedtls_ecp_group *grp,
606 const unsigned char *buf, size_t blen,
607 const mbedtls_ecp_point *Q,
608 const mbedtls_mpi *r,
609 const mbedtls_mpi *s)
610 {
611 return( ecdsa_verify_restartable( grp, buf, blen, Q, r, s, NULL ) );
612 }
613 #endif /* !MBEDTLS_ECDSA_VERIFY_ALT */
614
615 /*
616 * Convert a signature (given by context) to ASN.1
617 */
ecdsa_signature_to_asn1(const mbedtls_mpi * r,const mbedtls_mpi * s,unsigned char * sig,size_t sig_size,size_t * slen)618 static int ecdsa_signature_to_asn1( const mbedtls_mpi *r, const mbedtls_mpi *s,
619 unsigned char *sig, size_t sig_size,
620 size_t *slen )
621 {
622 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
623 unsigned char buf[MBEDTLS_ECDSA_MAX_LEN] = {0};
624 unsigned char *p = buf + sizeof( buf );
625 size_t len = 0;
626
627 MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, s ) );
628 MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, r ) );
629
630 MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_len( &p, buf, len ) );
631 MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_tag( &p, buf,
632 MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) );
633
634 if( len > sig_size )
635 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
636
637 memcpy( sig, p, len );
638 *slen = len;
639
640 return( 0 );
641 }
642
643 /*
644 * Compute and write signature
645 */
mbedtls_ecdsa_write_signature_restartable(mbedtls_ecdsa_context * ctx,mbedtls_md_type_t md_alg,const unsigned char * hash,size_t hlen,unsigned char * sig,size_t sig_size,size_t * slen,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng,mbedtls_ecdsa_restart_ctx * rs_ctx)646 int mbedtls_ecdsa_write_signature_restartable( mbedtls_ecdsa_context *ctx,
647 mbedtls_md_type_t md_alg,
648 const unsigned char *hash, size_t hlen,
649 unsigned char *sig, size_t sig_size, size_t *slen,
650 int (*f_rng)(void *, unsigned char *, size_t),
651 void *p_rng,
652 mbedtls_ecdsa_restart_ctx *rs_ctx )
653 {
654 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
655 mbedtls_mpi r, s;
656 if( f_rng == NULL )
657 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
658
659 mbedtls_mpi_init( &r );
660 mbedtls_mpi_init( &s );
661
662 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
663 MBEDTLS_MPI_CHK( ecdsa_sign_det_restartable( &ctx->grp, &r, &s, &ctx->d,
664 hash, hlen, md_alg, f_rng,
665 p_rng, rs_ctx ) );
666 #else
667 (void) md_alg;
668
669 #if defined(MBEDTLS_ECDSA_SIGN_ALT)
670 (void) rs_ctx;
671
672 MBEDTLS_MPI_CHK( mbedtls_ecdsa_sign( &ctx->grp, &r, &s, &ctx->d,
673 hash, hlen, f_rng, p_rng ) );
674 #else
675 /* Use the same RNG for both blinding and ephemeral key generation */
676 MBEDTLS_MPI_CHK( ecdsa_sign_restartable( &ctx->grp, &r, &s, &ctx->d,
677 hash, hlen, f_rng, p_rng, f_rng,
678 p_rng, rs_ctx ) );
679 #endif /* MBEDTLS_ECDSA_SIGN_ALT */
680 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
681
682 MBEDTLS_MPI_CHK( ecdsa_signature_to_asn1( &r, &s, sig, sig_size, slen ) );
683
684 cleanup:
685 mbedtls_mpi_free( &r );
686 mbedtls_mpi_free( &s );
687
688 return( ret );
689 }
690
691 /*
692 * Compute and write signature
693 */
mbedtls_ecdsa_write_signature(mbedtls_ecdsa_context * ctx,mbedtls_md_type_t md_alg,const unsigned char * hash,size_t hlen,unsigned char * sig,size_t sig_size,size_t * slen,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)694 int mbedtls_ecdsa_write_signature( mbedtls_ecdsa_context *ctx,
695 mbedtls_md_type_t md_alg,
696 const unsigned char *hash, size_t hlen,
697 unsigned char *sig, size_t sig_size, size_t *slen,
698 int (*f_rng)(void *, unsigned char *, size_t),
699 void *p_rng )
700 {
701 return( mbedtls_ecdsa_write_signature_restartable(
702 ctx, md_alg, hash, hlen, sig, sig_size, slen,
703 f_rng, p_rng, NULL ) );
704 }
705
706 /*
707 * Read and check signature
708 */
mbedtls_ecdsa_read_signature(mbedtls_ecdsa_context * ctx,const unsigned char * hash,size_t hlen,const unsigned char * sig,size_t slen)709 int mbedtls_ecdsa_read_signature( mbedtls_ecdsa_context *ctx,
710 const unsigned char *hash, size_t hlen,
711 const unsigned char *sig, size_t slen )
712 {
713 return( mbedtls_ecdsa_read_signature_restartable(
714 ctx, hash, hlen, sig, slen, NULL ) );
715 }
716
717 /*
718 * Restartable read and check signature
719 */
mbedtls_ecdsa_read_signature_restartable(mbedtls_ecdsa_context * ctx,const unsigned char * hash,size_t hlen,const unsigned char * sig,size_t slen,mbedtls_ecdsa_restart_ctx * rs_ctx)720 int mbedtls_ecdsa_read_signature_restartable( mbedtls_ecdsa_context *ctx,
721 const unsigned char *hash, size_t hlen,
722 const unsigned char *sig, size_t slen,
723 mbedtls_ecdsa_restart_ctx *rs_ctx )
724 {
725 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
726 unsigned char *p = (unsigned char *) sig;
727 const unsigned char *end = sig + slen;
728 size_t len;
729 mbedtls_mpi r, s;
730 mbedtls_mpi_init( &r );
731 mbedtls_mpi_init( &s );
732
733 if( ( ret = mbedtls_asn1_get_tag( &p, end, &len,
734 MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) ) != 0 )
735 {
736 ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
737 goto cleanup;
738 }
739
740 if( p + len != end )
741 {
742 ret = MBEDTLS_ERROR_ADD( MBEDTLS_ERR_ECP_BAD_INPUT_DATA,
743 MBEDTLS_ERR_ASN1_LENGTH_MISMATCH );
744 goto cleanup;
745 }
746
747 if( ( ret = mbedtls_asn1_get_mpi( &p, end, &r ) ) != 0 ||
748 ( ret = mbedtls_asn1_get_mpi( &p, end, &s ) ) != 0 )
749 {
750 ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
751 goto cleanup;
752 }
753 #if defined(MBEDTLS_ECDSA_VERIFY_ALT)
754 (void) rs_ctx;
755
756 if( ( ret = mbedtls_ecdsa_verify( &ctx->grp, hash, hlen,
757 &ctx->Q, &r, &s ) ) != 0 )
758 goto cleanup;
759 #else
760 if( ( ret = ecdsa_verify_restartable( &ctx->grp, hash, hlen,
761 &ctx->Q, &r, &s, rs_ctx ) ) != 0 )
762 goto cleanup;
763 #endif /* MBEDTLS_ECDSA_VERIFY_ALT */
764
765 /* At this point we know that the buffer starts with a valid signature.
766 * Return 0 if the buffer just contains the signature, and a specific
767 * error code if the valid signature is followed by more data. */
768 if( p != end )
769 ret = MBEDTLS_ERR_ECP_SIG_LEN_MISMATCH;
770
771 cleanup:
772 mbedtls_mpi_free( &r );
773 mbedtls_mpi_free( &s );
774
775 return( ret );
776 }
777
778 #if !defined(MBEDTLS_ECDSA_GENKEY_ALT)
779 /*
780 * Generate key pair
781 */
mbedtls_ecdsa_genkey(mbedtls_ecdsa_context * ctx,mbedtls_ecp_group_id gid,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)782 int mbedtls_ecdsa_genkey( mbedtls_ecdsa_context *ctx, mbedtls_ecp_group_id gid,
783 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
784 {
785 int ret = 0;
786 ret = mbedtls_ecp_group_load( &ctx->grp, gid );
787 if( ret != 0 )
788 return( ret );
789
790 return( mbedtls_ecp_gen_keypair( &ctx->grp, &ctx->d,
791 &ctx->Q, f_rng, p_rng ) );
792 }
793 #endif /* !MBEDTLS_ECDSA_GENKEY_ALT */
794
795 /*
796 * Set context from an mbedtls_ecp_keypair
797 */
mbedtls_ecdsa_from_keypair(mbedtls_ecdsa_context * ctx,const mbedtls_ecp_keypair * key)798 int mbedtls_ecdsa_from_keypair( mbedtls_ecdsa_context *ctx, const mbedtls_ecp_keypair *key )
799 {
800 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
801 if( ( ret = mbedtls_ecp_group_copy( &ctx->grp, &key->grp ) ) != 0 ||
802 ( ret = mbedtls_mpi_copy( &ctx->d, &key->d ) ) != 0 ||
803 ( ret = mbedtls_ecp_copy( &ctx->Q, &key->Q ) ) != 0 )
804 {
805 mbedtls_ecdsa_free( ctx );
806 }
807
808 return( ret );
809 }
810
811 /*
812 * Initialize context
813 */
mbedtls_ecdsa_init(mbedtls_ecdsa_context * ctx)814 void mbedtls_ecdsa_init( mbedtls_ecdsa_context *ctx )
815 {
816 mbedtls_ecp_keypair_init( ctx );
817 }
818
819 /*
820 * Free context
821 */
mbedtls_ecdsa_free(mbedtls_ecdsa_context * ctx)822 void mbedtls_ecdsa_free( mbedtls_ecdsa_context *ctx )
823 {
824 if( ctx == NULL )
825 return;
826
827 mbedtls_ecp_keypair_free( ctx );
828 }
829
830 #if defined(MBEDTLS_ECP_RESTARTABLE)
831 /*
832 * Initialize a restart context
833 */
mbedtls_ecdsa_restart_init(mbedtls_ecdsa_restart_ctx * ctx)834 void mbedtls_ecdsa_restart_init( mbedtls_ecdsa_restart_ctx *ctx )
835 {
836 mbedtls_ecp_restart_init( &ctx->ecp );
837
838 ctx->ver = NULL;
839 ctx->sig = NULL;
840 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
841 ctx->det = NULL;
842 #endif
843 }
844
845 /*
846 * Free the components of a restart context
847 */
mbedtls_ecdsa_restart_free(mbedtls_ecdsa_restart_ctx * ctx)848 void mbedtls_ecdsa_restart_free( mbedtls_ecdsa_restart_ctx *ctx )
849 {
850 if( ctx == NULL )
851 return;
852
853 mbedtls_ecp_restart_free( &ctx->ecp );
854
855 ecdsa_restart_ver_free( ctx->ver );
856 mbedtls_free( ctx->ver );
857 ctx->ver = NULL;
858
859 ecdsa_restart_sig_free( ctx->sig );
860 mbedtls_free( ctx->sig );
861 ctx->sig = NULL;
862
863 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
864 ecdsa_restart_det_free( ctx->det );
865 mbedtls_free( ctx->det );
866 ctx->det = NULL;
867 #endif
868 }
869 #endif /* MBEDTLS_ECP_RESTARTABLE */
870
871 #endif /* MBEDTLS_ECDSA_C */
872
