xref: /openbsd-src/lib/libcrypto/ecdsa/ecdsa.c (revision ea2baf45ff427a396d0e07bc3399b0103438903c)
1 /* $OpenBSD: ecdsa.c,v 1.11 2023/07/07 13:54:45 beck Exp $ */
2 /* ====================================================================
3  * Copyright (c) 2000-2002 The OpenSSL Project.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  *
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in
14  *    the documentation and/or other materials provided with the
15  *    distribution.
16  *
17  * 3. All advertising materials mentioning features or use of this
18  *    software must display the following acknowledgment:
19  *    "This product includes software developed by the OpenSSL Project
20  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
21  *
22  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23  *    endorse or promote products derived from this software without
24  *    prior written permission. For written permission, please contact
25  *    licensing@OpenSSL.org.
26  *
27  * 5. Products derived from this software may not be called "OpenSSL"
28  *    nor may "OpenSSL" appear in their names without prior written
29  *    permission of the OpenSSL Project.
30  *
31  * 6. Redistributions of any form whatsoever must retain the following
32  *    acknowledgment:
33  *    "This product includes software developed by the OpenSSL Project
34  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
35  *
36  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47  * OF THE POSSIBILITY OF SUCH DAMAGE.
48  * ====================================================================
49  *
50  * This product includes cryptographic software written by Eric Young
51  * (eay@cryptsoft.com).  This product includes software written by Tim
52  * Hudson (tjh@cryptsoft.com).
53  *
54  */
55 
56 #include <stddef.h>
57 #include <stdlib.h>
58 #include <string.h>
59 
60 #include <openssl/opensslconf.h>
61 
62 #include <openssl/asn1.h>
63 #include <openssl/asn1t.h>
64 #include <openssl/bn.h>
65 #include <openssl/ecdsa.h>
66 #include <openssl/ec.h>
67 #include <openssl/err.h>
68 #include <openssl/evp.h>
69 
70 #include "bn_local.h"
71 #include "ec_local.h"
72 #include "ecdsa_local.h"
73 
74 static const ASN1_TEMPLATE ECDSA_SIG_seq_tt[] = {
75 	{
76 		.flags = 0,
77 		.tag = 0,
78 		.offset = offsetof(ECDSA_SIG, r),
79 		.field_name = "r",
80 		.item = &BIGNUM_it,
81 	},
82 	{
83 		.flags = 0,
84 		.tag = 0,
85 		.offset = offsetof(ECDSA_SIG, s),
86 		.field_name = "s",
87 		.item = &BIGNUM_it,
88 	},
89 };
90 
91 const ASN1_ITEM ECDSA_SIG_it = {
92 	.itype = ASN1_ITYPE_SEQUENCE,
93 	.utype = V_ASN1_SEQUENCE,
94 	.templates = ECDSA_SIG_seq_tt,
95 	.tcount = sizeof(ECDSA_SIG_seq_tt) / sizeof(ASN1_TEMPLATE),
96 	.funcs = NULL,
97 	.size = sizeof(ECDSA_SIG),
98 	.sname = "ECDSA_SIG",
99 };
100 
101 ECDSA_SIG *
102 d2i_ECDSA_SIG(ECDSA_SIG **a, const unsigned char **in, long len)
103 {
104 	return (ECDSA_SIG *)ASN1_item_d2i((ASN1_VALUE **)a, in, len,
105 	    &ECDSA_SIG_it);
106 }
107 LCRYPTO_ALIAS(d2i_ECDSA_SIG);
108 
109 int
110 i2d_ECDSA_SIG(const ECDSA_SIG *a, unsigned char **out)
111 {
112 	return ASN1_item_i2d((ASN1_VALUE *)a, out, &ECDSA_SIG_it);
113 }
114 LCRYPTO_ALIAS(i2d_ECDSA_SIG);
115 
116 ECDSA_SIG *
117 ECDSA_SIG_new(void)
118 {
119 	return (ECDSA_SIG *)ASN1_item_new(&ECDSA_SIG_it);
120 }
121 LCRYPTO_ALIAS(ECDSA_SIG_new);
122 
123 void
124 ECDSA_SIG_free(ECDSA_SIG *a)
125 {
126 	ASN1_item_free((ASN1_VALUE *)a, &ECDSA_SIG_it);
127 }
128 LCRYPTO_ALIAS(ECDSA_SIG_free);
129 
130 void
131 ECDSA_SIG_get0(const ECDSA_SIG *sig, const BIGNUM **pr, const BIGNUM **ps)
132 {
133 	if (pr != NULL)
134 		*pr = sig->r;
135 	if (ps != NULL)
136 		*ps = sig->s;
137 }
138 LCRYPTO_ALIAS(ECDSA_SIG_get0);
139 
140 const BIGNUM *
141 ECDSA_SIG_get0_r(const ECDSA_SIG *sig)
142 {
143 	return sig->r;
144 }
145 LCRYPTO_ALIAS(ECDSA_SIG_get0_r);
146 
147 const BIGNUM *
148 ECDSA_SIG_get0_s(const ECDSA_SIG *sig)
149 {
150 	return sig->s;
151 }
152 LCRYPTO_ALIAS(ECDSA_SIG_get0_s);
153 
154 int
155 ECDSA_SIG_set0(ECDSA_SIG *sig, BIGNUM *r, BIGNUM *s)
156 {
157 	if (r == NULL || s == NULL)
158 		return 0;
159 
160 	BN_free(sig->r);
161 	BN_free(sig->s);
162 	sig->r = r;
163 	sig->s = s;
164 	return 1;
165 }
166 LCRYPTO_ALIAS(ECDSA_SIG_set0);
167 
168 int
169 ECDSA_size(const EC_KEY *r)
170 {
171 	const EC_GROUP *group;
172 	const BIGNUM *order = NULL;
173 	ECDSA_SIG sig;
174 	int ret = 0;
175 
176 	if (r == NULL)
177 		goto err;
178 
179 	if ((group = EC_KEY_get0_group(r)) == NULL)
180 		goto err;
181 
182 	if ((order = EC_GROUP_get0_order(group)) == NULL)
183 		goto err;
184 
185 	sig.r = (BIGNUM *)order;
186 	sig.s = (BIGNUM *)order;
187 
188 	if ((ret = i2d_ECDSA_SIG(&sig, NULL)) < 0)
189 		ret = 0;
190 
191  err:
192 	return ret;
193 }
194 LCRYPTO_ALIAS(ECDSA_size);
195 
196 /*
197  * FIPS 186-5, section 6.4.1, step 2: convert hashed message into an integer.
198  * Use the order_bits leftmost bits if it exceeds the group order.
199  */
200 static int
201 ecdsa_prepare_digest(const unsigned char *digest, int digest_len,
202     const EC_KEY *key, BIGNUM *e)
203 {
204 	const EC_GROUP *group;
205 	int digest_bits, order_bits;
206 
207 	if (BN_bin2bn(digest, digest_len, e) == NULL) {
208 		ECerror(ERR_R_BN_LIB);
209 		return 0;
210 	}
211 
212 	if ((group = EC_KEY_get0_group(key)) == NULL)
213 		return 0;
214 	order_bits = EC_GROUP_order_bits(group);
215 
216 	digest_bits = 8 * digest_len;
217 	if (digest_bits <= order_bits)
218 		return 1;
219 
220 	return BN_rshift(e, e, digest_bits - order_bits);
221 }
222 
223 int
224 ecdsa_sign(int type, const unsigned char *digest, int digest_len,
225     unsigned char *signature, unsigned int *signature_len, const BIGNUM *kinv,
226     const BIGNUM *r, EC_KEY *key)
227 {
228 	ECDSA_SIG *sig;
229 	int out_len = 0;
230 	int ret = 0;
231 
232 	if ((sig = ECDSA_do_sign_ex(digest, digest_len, kinv, r, key)) == NULL)
233 		goto err;
234 
235 	if ((out_len = i2d_ECDSA_SIG(sig, &signature)) < 0) {
236 		out_len = 0;
237 		goto err;
238 	}
239 
240 	ret = 1;
241 
242  err:
243 	*signature_len = out_len;
244 	ECDSA_SIG_free(sig);
245 
246 	return ret;
247 }
248 
249 /*
250  * FIPS 186-5, section 6.4.1, steps 3-8 and 11: Generate k, calculate r and
251  * kinv. If r == 0, try again with a new random k.
252  */
253 
254 int
255 ecdsa_sign_setup(EC_KEY *key, BN_CTX *in_ctx, BIGNUM **out_kinv, BIGNUM **out_r)
256 {
257 	const EC_GROUP *group;
258 	EC_POINT *point = NULL;
259 	BN_CTX *ctx = NULL;
260 	BIGNUM *k = NULL, *r = NULL;
261 	const BIGNUM *order;
262 	BIGNUM *x;
263 	int order_bits;
264 	int ret = 0;
265 
266 	BN_free(*out_kinv);
267 	*out_kinv = NULL;
268 
269 	BN_free(*out_r);
270 	*out_r = NULL;
271 
272 	if (key == NULL) {
273 		ECerror(ERR_R_PASSED_NULL_PARAMETER);
274 		goto err;
275 	}
276 	if ((group = EC_KEY_get0_group(key)) == NULL) {
277 		ECerror(ERR_R_PASSED_NULL_PARAMETER);
278 		goto err;
279 	}
280 
281 	if ((k = BN_new()) == NULL)
282 		goto err;
283 	if ((r = BN_new()) == NULL)
284 		goto err;
285 
286 	if ((ctx = in_ctx) == NULL)
287 		ctx = BN_CTX_new();
288 	if (ctx == NULL) {
289 		ECerror(ERR_R_MALLOC_FAILURE);
290 		goto err;
291 	}
292 
293 	BN_CTX_start(ctx);
294 
295 	if ((x = BN_CTX_get(ctx)) == NULL)
296 		goto err;
297 
298 	if ((point = EC_POINT_new(group)) == NULL) {
299 		ECerror(ERR_R_EC_LIB);
300 		goto err;
301 	}
302 	if ((order = EC_GROUP_get0_order(group)) == NULL) {
303 		ECerror(ERR_R_EC_LIB);
304 		goto err;
305 	}
306 
307 	if (BN_cmp(order, BN_value_one()) <= 0) {
308 		ECerror(EC_R_INVALID_GROUP_ORDER);
309 		goto err;
310 	}
311 
312 	/* Reject curves with an order that is smaller than 80 bits. */
313 	if ((order_bits = BN_num_bits(order)) < 80) {
314 		ECerror(EC_R_INVALID_GROUP_ORDER);
315 		goto err;
316 	}
317 
318 	/* Preallocate space. */
319 	if (!BN_set_bit(k, order_bits) ||
320 	    !BN_set_bit(r, order_bits) ||
321 	    !BN_set_bit(x, order_bits))
322 		goto err;
323 
324 	/* Step 11: repeat until r != 0. */
325 	do {
326 		/* Step 3: generate random k. */
327 		if (!bn_rand_interval(k, BN_value_one(), order))
328 			goto err;
329 
330 		/*
331 		 * We do not want timing information to leak the length of k,
332 		 * so we compute G * k using an equivalent scalar of fixed
333 		 * bit-length.
334 		 *
335 		 * We unconditionally perform both of these additions to prevent
336 		 * a small timing information leakage.  We then choose the sum
337 		 * that is one bit longer than the order.  This guarantees the
338 		 * code path used in the constant time implementations
339 		 * elsewhere.
340 		 *
341 		 * TODO: revisit the bn_copy aiming for a memory access agnostic
342 		 * conditional copy.
343 		 */
344 		if (!BN_add(r, k, order) ||
345 		    !BN_add(x, r, order) ||
346 		    !bn_copy(k, BN_num_bits(r) > order_bits ? r : x))
347 			goto err;
348 
349 		BN_set_flags(k, BN_FLG_CONSTTIME);
350 
351 		/* Step 5: P = k * G. */
352 		if (!EC_POINT_mul(group, point, k, NULL, NULL, ctx)) {
353 			ECerror(ERR_R_EC_LIB);
354 			goto err;
355 		}
356 		/* Steps 6 (and 7): from P = (x, y) retain the x-coordinate. */
357 		if (!EC_POINT_get_affine_coordinates(group, point, x, NULL,
358 		    ctx)) {
359 			ECerror(ERR_R_EC_LIB);
360 			goto err;
361 		}
362 		/* Step 8: r = x (mod order). */
363 		if (!BN_nnmod(r, x, order, ctx)) {
364 			ECerror(ERR_R_BN_LIB);
365 			goto err;
366 		}
367 	} while (BN_is_zero(r));
368 
369 	/* Step 4: calculate kinv. */
370 	if (BN_mod_inverse_ct(k, k, order, ctx) == NULL) {
371 		ECerror(ERR_R_BN_LIB);
372 		goto err;
373 	}
374 
375 	*out_kinv = k;
376 	k = NULL;
377 
378 	*out_r = r;
379 	r = NULL;
380 
381 	ret = 1;
382 
383  err:
384 	BN_CTX_end(ctx);
385 	if (ctx != in_ctx)
386 		BN_CTX_free(ctx);
387 	BN_free(k);
388 	BN_free(r);
389 	EC_POINT_free(point);
390 
391 	return ret;
392 }
393 
394 /*
395  * FIPS 186-5, section 6.4.1, step 9: compute s = inv(k)(e + xr) mod order.
396  * In order to reduce the possibility of a side-channel attack, the following
397  * is calculated using a random blinding value b in [1, order):
398  * s = inv(b)(be + bxr)inv(k) mod order.
399  */
400 
401 static int
402 ecdsa_compute_s(BIGNUM **out_s, const BIGNUM *e, const BIGNUM *kinv,
403     const BIGNUM *r, const EC_KEY *key, BN_CTX *ctx)
404 {
405 	const EC_GROUP *group;
406 	const BIGNUM *order, *priv_key;
407 	BIGNUM *b, *binv, *be, *bxr;
408 	BIGNUM *s = NULL;
409 	int ret = 0;
410 
411 	*out_s = NULL;
412 
413 	BN_CTX_start(ctx);
414 
415 	if ((group = EC_KEY_get0_group(key)) == NULL) {
416 		ECerror(ERR_R_PASSED_NULL_PARAMETER);
417 		goto err;
418 	}
419 	if ((order = EC_GROUP_get0_order(group)) == NULL) {
420 		ECerror(ERR_R_EC_LIB);
421 		goto err;
422 	}
423 	if ((priv_key = EC_KEY_get0_private_key(key)) == NULL) {
424 		ECerror(ERR_R_PASSED_NULL_PARAMETER);
425 		goto err;
426 	}
427 
428 	if ((b = BN_CTX_get(ctx)) == NULL)
429 		goto err;
430 	if ((binv = BN_CTX_get(ctx)) == NULL)
431 		goto err;
432 	if ((be = BN_CTX_get(ctx)) == NULL)
433 		goto err;
434 	if ((bxr = BN_CTX_get(ctx)) == NULL)
435 		goto err;
436 
437 	if ((s = BN_new()) == NULL)
438 		goto err;
439 
440 	/*
441 	 * In a valid ECDSA signature, r must be in [1, order). Since r can be
442 	 * caller provided - either directly or by replacing sign_setup() - we
443 	 * can't rely on this being the case.
444 	 */
445 	if (BN_cmp(r, BN_value_one()) < 0 || BN_cmp(r, order) >= 0) {
446 		ECerror(EC_R_BAD_SIGNATURE);
447 		goto err;
448 	}
449 
450 	if (!bn_rand_interval(b, BN_value_one(), order)) {
451 		ECerror(ERR_R_BN_LIB);
452 		goto err;
453 	}
454 
455 	if (BN_mod_inverse_ct(binv, b, order, ctx) == NULL) {
456 		ECerror(ERR_R_BN_LIB);
457 		goto err;
458 	}
459 
460 	if (!BN_mod_mul(bxr, b, priv_key, order, ctx)) {
461 		ECerror(ERR_R_BN_LIB);
462 		goto err;
463 	}
464 	if (!BN_mod_mul(bxr, bxr, r, order, ctx)) {
465 		ECerror(ERR_R_BN_LIB);
466 		goto err;
467 	}
468 	if (!BN_mod_mul(be, b, e, order, ctx)) {
469 		ECerror(ERR_R_BN_LIB);
470 		goto err;
471 	}
472 	if (!BN_mod_add(s, be, bxr, order, ctx)) {
473 		ECerror(ERR_R_BN_LIB);
474 		goto err;
475 	}
476 	/* s = b(e + xr)k^-1 */
477 	if (!BN_mod_mul(s, s, kinv, order, ctx)) {
478 		ECerror(ERR_R_BN_LIB);
479 		goto err;
480 	}
481 	/* s = (e + xr)k^-1 */
482 	if (!BN_mod_mul(s, s, binv, order, ctx)) {
483 		ECerror(ERR_R_BN_LIB);
484 		goto err;
485 	}
486 
487 	/* Step 11: if s == 0 start over. */
488 	if (!BN_is_zero(s)) {
489 		*out_s = s;
490 		s = NULL;
491 	}
492 
493 	ret = 1;
494 
495  err:
496 	BN_CTX_end(ctx);
497 	BN_free(s);
498 
499 	return ret;
500 }
501 
502 /*
503  * It is too expensive to check curve parameters on every sign operation.
504  * Instead, cap the number of retries. A single retry is very unlikely, so
505  * allowing 32 retries is amply enough.
506  */
507 #define ECDSA_MAX_SIGN_ITERATIONS		32
508 
509 /*
510  * FIPS 186-5: Section 6.4.1: ECDSA signature generation, steps 2-12.
511  * The caller provides the hash of the message, thus performs step 1.
512  * Step 10, zeroing k and kinv, is done by BN_free().
513  */
514 
515 ECDSA_SIG *
516 ecdsa_sign_sig(const unsigned char *digest, int digest_len,
517     const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *key)
518 {
519 	BN_CTX *ctx = NULL;
520 	BIGNUM *kinv = NULL, *r = NULL, *s = NULL;
521 	BIGNUM *e;
522 	int caller_supplied_values = 0;
523 	int attempts = 0;
524 	ECDSA_SIG *sig = NULL;
525 
526 	if ((ctx = BN_CTX_new()) == NULL) {
527 		ECerror(ERR_R_MALLOC_FAILURE);
528 		goto err;
529 	}
530 
531 	BN_CTX_start(ctx);
532 
533 	if ((e = BN_CTX_get(ctx)) == NULL)
534 		goto err;
535 
536 	/* Step 2: convert hash into an integer. */
537 	if (!ecdsa_prepare_digest(digest, digest_len, key, e))
538 		goto err;
539 
540 	if (in_kinv != NULL && in_r != NULL) {
541 		/*
542 		 * Use the caller's kinv and r. Don't call ECDSA_sign_setup().
543 		 * If we're unable to compute a valid signature, the caller
544 		 * must provide new values.
545 		 */
546 		caller_supplied_values = 1;
547 
548 		if ((kinv = BN_dup(in_kinv)) == NULL) {
549 			ECerror(ERR_R_MALLOC_FAILURE);
550 			goto err;
551 		}
552 		if ((r = BN_dup(in_r)) == NULL) {
553 			ECerror(ERR_R_MALLOC_FAILURE);
554 			goto err;
555 		}
556 	}
557 
558 	do {
559 		/* Steps 3-8: calculate kinv and r. */
560 		if (!caller_supplied_values) {
561 			if (!ECDSA_sign_setup(key, ctx, &kinv, &r)) {
562 				ECerror(ERR_R_EC_LIB);
563 				goto err;
564 			}
565 		}
566 
567 		/*
568 		 * Steps 9 and 11: if s is non-NULL, we have a valid signature.
569 		 */
570 		if (!ecdsa_compute_s(&s, e, kinv, r, key, ctx))
571 			goto err;
572 		if (s != NULL)
573 			break;
574 
575 		if (caller_supplied_values) {
576 			ECerror(EC_R_NEED_NEW_SETUP_VALUES);
577 			goto err;
578 		}
579 
580 		if (++attempts > ECDSA_MAX_SIGN_ITERATIONS) {
581 			ECerror(EC_R_WRONG_CURVE_PARAMETERS);
582 			goto err;
583 		}
584 	} while (1);
585 
586 	/* Step 12: output (r, s). */
587 	if ((sig = ECDSA_SIG_new()) == NULL) {
588 		ECerror(ERR_R_MALLOC_FAILURE);
589 		goto err;
590 	}
591 	if (!ECDSA_SIG_set0(sig, r, s)) {
592 		ECDSA_SIG_free(sig);
593 		goto err;
594 	}
595 	r = NULL;
596 	s = NULL;
597 
598  err:
599 	BN_CTX_end(ctx);
600 	BN_CTX_free(ctx);
601 	BN_free(kinv);
602 	BN_free(r);
603 	BN_free(s);
604 
605 	return sig;
606 }
607 
608 int
609 ecdsa_verify(int type, const unsigned char *digest, int digest_len,
610     const unsigned char *sigbuf, int sig_len, EC_KEY *key)
611 {
612 	ECDSA_SIG *s;
613 	unsigned char *der = NULL;
614 	const unsigned char *p;
615 	int der_len = 0;
616 	int ret = -1;
617 
618 	if ((s = ECDSA_SIG_new()) == NULL)
619 		goto err;
620 
621 	p = sigbuf;
622 	if (d2i_ECDSA_SIG(&s, &p, sig_len) == NULL)
623 		goto err;
624 
625 	/* Ensure signature uses DER and doesn't have trailing garbage. */
626 	if ((der_len = i2d_ECDSA_SIG(s, &der)) != sig_len)
627 		goto err;
628 	if (timingsafe_memcmp(sigbuf, der, der_len))
629 		goto err;
630 
631 	ret = ECDSA_do_verify(digest, digest_len, s, key);
632 
633  err:
634 	freezero(der, der_len);
635 	ECDSA_SIG_free(s);
636 
637 	return ret;
638 }
639 
640 /*
641  * FIPS 186-5, section 6.4.2: ECDSA signature verification.
642  * The caller provides us with the hash of the message, so has performed step 2.
643  */
644 
645 int
646 ecdsa_verify_sig(const unsigned char *digest, int digest_len,
647     const ECDSA_SIG *sig, EC_KEY *key)
648 {
649 	const EC_GROUP *group;
650 	const EC_POINT *pub_key;
651 	EC_POINT *point = NULL;
652 	const BIGNUM *order;
653 	BN_CTX *ctx = NULL;
654 	BIGNUM *e, *sinv, *u, *v, *x;
655 	int ret = -1;
656 
657 	if (key == NULL || sig == NULL) {
658 		ECerror(EC_R_MISSING_PARAMETERS);
659 		goto err;
660 	}
661 	if ((group = EC_KEY_get0_group(key)) == NULL) {
662 		ECerror(EC_R_MISSING_PARAMETERS);
663 		goto err;
664 	}
665 	if ((pub_key = EC_KEY_get0_public_key(key)) == NULL) {
666 		ECerror(EC_R_MISSING_PARAMETERS);
667 		goto err;
668 	}
669 
670 	if ((ctx = BN_CTX_new()) == NULL) {
671 		ECerror(ERR_R_MALLOC_FAILURE);
672 		goto err;
673 	}
674 
675 	BN_CTX_start(ctx);
676 
677 	if ((e = BN_CTX_get(ctx)) == NULL)
678 		goto err;
679 	if ((sinv = BN_CTX_get(ctx)) == NULL)
680 		goto err;
681 	if ((u = BN_CTX_get(ctx)) == NULL)
682 		goto err;
683 	if ((v = BN_CTX_get(ctx)) == NULL)
684 		goto err;
685 	if ((x = BN_CTX_get(ctx)) == NULL)
686 		goto err;
687 
688 	if ((order = EC_GROUP_get0_order(group)) == NULL) {
689 		ECerror(ERR_R_EC_LIB);
690 		goto err;
691 	}
692 
693 	/* Step 1: verify that r and s are in the range [1, order). */
694 	if (BN_cmp(sig->r, BN_value_one()) < 0 || BN_cmp(sig->r, order) >= 0) {
695 		ECerror(EC_R_BAD_SIGNATURE);
696 		ret = 0;
697 		goto err;
698 	}
699 	if (BN_cmp(sig->s, BN_value_one()) < 0 || BN_cmp(sig->s, order) >= 0) {
700 		ECerror(EC_R_BAD_SIGNATURE);
701 		ret = 0;
702 		goto err;
703 	}
704 
705 	/* Step 3: convert the hash into an integer. */
706 	if (!ecdsa_prepare_digest(digest, digest_len, key, e))
707 		goto err;
708 
709 	/* Step 4: compute the inverse of s modulo order. */
710 	if (BN_mod_inverse_ct(sinv, sig->s, order, ctx) == NULL) {
711 		ECerror(ERR_R_BN_LIB);
712 		goto err;
713 	}
714 	/* Step 5: compute u = s^-1 * e and v = s^-1 * r (modulo order). */
715 	if (!BN_mod_mul(u, e, sinv, order, ctx)) {
716 		ECerror(ERR_R_BN_LIB);
717 		goto err;
718 	}
719 	if (!BN_mod_mul(v, sig->r, sinv, order, ctx)) {
720 		ECerror(ERR_R_BN_LIB);
721 		goto err;
722 	}
723 
724 	/*
725 	 * Steps 6 and 7: compute R = G * u + pub_key * v = (x, y). Reject if
726 	 * it's the point at infinity - getting affine coordinates fails. Keep
727 	 * the x coordinate.
728 	 */
729 	if ((point = EC_POINT_new(group)) == NULL) {
730 		ECerror(ERR_R_MALLOC_FAILURE);
731 		goto err;
732 	}
733 	if (!EC_POINT_mul(group, point, u, pub_key, v, ctx)) {
734 		ECerror(ERR_R_EC_LIB);
735 		goto err;
736 	}
737 	if (!EC_POINT_get_affine_coordinates(group, point, x, NULL, ctx)) {
738 		ECerror(ERR_R_EC_LIB);
739 		goto err;
740 	}
741 	/* Step 8: convert x to a number in [0, order). */
742 	if (!BN_nnmod(x, x, order, ctx)) {
743 		ECerror(ERR_R_BN_LIB);
744 		goto err;
745 	}
746 
747 	/* Step 9: the signature is valid iff the x-coordinate is equal to r. */
748 	ret = (BN_cmp(x, sig->r) == 0);
749 
750  err:
751 	BN_CTX_end(ctx);
752 	BN_CTX_free(ctx);
753 	EC_POINT_free(point);
754 
755 	return ret;
756 }
757 
758 ECDSA_SIG *
759 ECDSA_do_sign(const unsigned char *digest, int digest_len, EC_KEY *key)
760 {
761 	return ECDSA_do_sign_ex(digest, digest_len, NULL, NULL, key);
762 }
763 LCRYPTO_ALIAS(ECDSA_do_sign);
764 
765 ECDSA_SIG *
766 ECDSA_do_sign_ex(const unsigned char *digest, int digest_len,
767     const BIGNUM *kinv, const BIGNUM *out_r, EC_KEY *key)
768 {
769 	if (key->meth->sign_sig == NULL) {
770 		ECerror(EC_R_NOT_IMPLEMENTED);
771 		return 0;
772 	}
773 	return key->meth->sign_sig(digest, digest_len, kinv, out_r, key);
774 }
775 LCRYPTO_ALIAS(ECDSA_do_sign_ex);
776 
777 int
778 ECDSA_sign(int type, const unsigned char *digest, int digest_len,
779     unsigned char *signature, unsigned int *signature_len, EC_KEY *key)
780 {
781 	return ECDSA_sign_ex(type, digest, digest_len, signature, signature_len,
782 	    NULL, NULL, key);
783 }
784 LCRYPTO_ALIAS(ECDSA_sign);
785 
786 int
787 ECDSA_sign_ex(int type, const unsigned char *digest, int digest_len,
788     unsigned char *signature, unsigned int *signature_len, const BIGNUM *kinv,
789     const BIGNUM *r, EC_KEY *key)
790 {
791 	if (key->meth->sign == NULL) {
792 		ECerror(EC_R_NOT_IMPLEMENTED);
793 		return 0;
794 	}
795 	return key->meth->sign(type, digest, digest_len, signature,
796 	    signature_len, kinv, r, key);
797 }
798 LCRYPTO_ALIAS(ECDSA_sign_ex);
799 
800 int
801 ECDSA_sign_setup(EC_KEY *key, BN_CTX *in_ctx, BIGNUM **out_kinv,
802     BIGNUM **out_r)
803 {
804 	if (key->meth->sign_setup == NULL) {
805 		ECerror(EC_R_NOT_IMPLEMENTED);
806 		return 0;
807 	}
808 	return key->meth->sign_setup(key, in_ctx, out_kinv, out_r);
809 }
810 LCRYPTO_ALIAS(ECDSA_sign_setup);
811 
812 int
813 ECDSA_do_verify(const unsigned char *digest, int digest_len,
814     const ECDSA_SIG *sig, EC_KEY *key)
815 {
816 	if (key->meth->verify_sig == NULL) {
817 		ECerror(EC_R_NOT_IMPLEMENTED);
818 		return 0;
819 	}
820 	return key->meth->verify_sig(digest, digest_len, sig, key);
821 }
822 LCRYPTO_ALIAS(ECDSA_do_verify);
823 
824 int
825 ECDSA_verify(int type, const unsigned char *digest, int digest_len,
826     const unsigned char *sigbuf, int sig_len, EC_KEY *key)
827 {
828 	if (key->meth->verify == NULL) {
829 		ECerror(EC_R_NOT_IMPLEMENTED);
830 		return 0;
831 	}
832 	return key->meth->verify(type, digest, digest_len, sigbuf, sig_len, key);
833 }
834 LCRYPTO_ALIAS(ECDSA_verify);
835