xref: /openbsd-src/lib/libcrypto/ecdsa/ecdsa.c (revision 1c55417ba1e3ce6f9c9d14c9f34b35fa70d532a8)
1 /* $OpenBSD: ecdsa.c,v 1.10 2023/07/05 17:10:10 tb 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 
108 int
109 i2d_ECDSA_SIG(const ECDSA_SIG *a, unsigned char **out)
110 {
111 	return ASN1_item_i2d((ASN1_VALUE *)a, out, &ECDSA_SIG_it);
112 }
113 
114 ECDSA_SIG *
115 ECDSA_SIG_new(void)
116 {
117 	return (ECDSA_SIG *)ASN1_item_new(&ECDSA_SIG_it);
118 }
119 
120 void
121 ECDSA_SIG_free(ECDSA_SIG *a)
122 {
123 	ASN1_item_free((ASN1_VALUE *)a, &ECDSA_SIG_it);
124 }
125 
126 void
127 ECDSA_SIG_get0(const ECDSA_SIG *sig, const BIGNUM **pr, const BIGNUM **ps)
128 {
129 	if (pr != NULL)
130 		*pr = sig->r;
131 	if (ps != NULL)
132 		*ps = sig->s;
133 }
134 
135 const BIGNUM *
136 ECDSA_SIG_get0_r(const ECDSA_SIG *sig)
137 {
138 	return sig->r;
139 }
140 
141 const BIGNUM *
142 ECDSA_SIG_get0_s(const ECDSA_SIG *sig)
143 {
144 	return sig->s;
145 }
146 
147 int
148 ECDSA_SIG_set0(ECDSA_SIG *sig, BIGNUM *r, BIGNUM *s)
149 {
150 	if (r == NULL || s == NULL)
151 		return 0;
152 
153 	BN_free(sig->r);
154 	BN_free(sig->s);
155 	sig->r = r;
156 	sig->s = s;
157 	return 1;
158 }
159 
160 int
161 ECDSA_size(const EC_KEY *r)
162 {
163 	const EC_GROUP *group;
164 	const BIGNUM *order = NULL;
165 	ECDSA_SIG sig;
166 	int ret = 0;
167 
168 	if (r == NULL)
169 		goto err;
170 
171 	if ((group = EC_KEY_get0_group(r)) == NULL)
172 		goto err;
173 
174 	if ((order = EC_GROUP_get0_order(group)) == NULL)
175 		goto err;
176 
177 	sig.r = (BIGNUM *)order;
178 	sig.s = (BIGNUM *)order;
179 
180 	if ((ret = i2d_ECDSA_SIG(&sig, NULL)) < 0)
181 		ret = 0;
182 
183  err:
184 	return ret;
185 }
186 
187 /*
188  * FIPS 186-5, section 6.4.1, step 2: convert hashed message into an integer.
189  * Use the order_bits leftmost bits if it exceeds the group order.
190  */
191 static int
192 ecdsa_prepare_digest(const unsigned char *digest, int digest_len,
193     const EC_KEY *key, BIGNUM *e)
194 {
195 	const EC_GROUP *group;
196 	int digest_bits, order_bits;
197 
198 	if (BN_bin2bn(digest, digest_len, e) == NULL) {
199 		ECerror(ERR_R_BN_LIB);
200 		return 0;
201 	}
202 
203 	if ((group = EC_KEY_get0_group(key)) == NULL)
204 		return 0;
205 	order_bits = EC_GROUP_order_bits(group);
206 
207 	digest_bits = 8 * digest_len;
208 	if (digest_bits <= order_bits)
209 		return 1;
210 
211 	return BN_rshift(e, e, digest_bits - order_bits);
212 }
213 
214 int
215 ecdsa_sign(int type, const unsigned char *digest, int digest_len,
216     unsigned char *signature, unsigned int *signature_len, const BIGNUM *kinv,
217     const BIGNUM *r, EC_KEY *key)
218 {
219 	ECDSA_SIG *sig;
220 	int out_len = 0;
221 	int ret = 0;
222 
223 	if ((sig = ECDSA_do_sign_ex(digest, digest_len, kinv, r, key)) == NULL)
224 		goto err;
225 
226 	if ((out_len = i2d_ECDSA_SIG(sig, &signature)) < 0) {
227 		out_len = 0;
228 		goto err;
229 	}
230 
231 	ret = 1;
232 
233  err:
234 	*signature_len = out_len;
235 	ECDSA_SIG_free(sig);
236 
237 	return ret;
238 }
239 
240 /*
241  * FIPS 186-5, section 6.4.1, steps 3-8 and 11: Generate k, calculate r and
242  * kinv. If r == 0, try again with a new random k.
243  */
244 
245 int
246 ecdsa_sign_setup(EC_KEY *key, BN_CTX *in_ctx, BIGNUM **out_kinv, BIGNUM **out_r)
247 {
248 	const EC_GROUP *group;
249 	EC_POINT *point = NULL;
250 	BN_CTX *ctx = NULL;
251 	BIGNUM *k = NULL, *r = NULL;
252 	const BIGNUM *order;
253 	BIGNUM *x;
254 	int order_bits;
255 	int ret = 0;
256 
257 	BN_free(*out_kinv);
258 	*out_kinv = NULL;
259 
260 	BN_free(*out_r);
261 	*out_r = NULL;
262 
263 	if (key == NULL) {
264 		ECerror(ERR_R_PASSED_NULL_PARAMETER);
265 		goto err;
266 	}
267 	if ((group = EC_KEY_get0_group(key)) == NULL) {
268 		ECerror(ERR_R_PASSED_NULL_PARAMETER);
269 		goto err;
270 	}
271 
272 	if ((k = BN_new()) == NULL)
273 		goto err;
274 	if ((r = BN_new()) == NULL)
275 		goto err;
276 
277 	if ((ctx = in_ctx) == NULL)
278 		ctx = BN_CTX_new();
279 	if (ctx == NULL) {
280 		ECerror(ERR_R_MALLOC_FAILURE);
281 		goto err;
282 	}
283 
284 	BN_CTX_start(ctx);
285 
286 	if ((x = BN_CTX_get(ctx)) == NULL)
287 		goto err;
288 
289 	if ((point = EC_POINT_new(group)) == NULL) {
290 		ECerror(ERR_R_EC_LIB);
291 		goto err;
292 	}
293 	if ((order = EC_GROUP_get0_order(group)) == NULL) {
294 		ECerror(ERR_R_EC_LIB);
295 		goto err;
296 	}
297 
298 	if (BN_cmp(order, BN_value_one()) <= 0) {
299 		ECerror(EC_R_INVALID_GROUP_ORDER);
300 		goto err;
301 	}
302 
303 	/* Reject curves with an order that is smaller than 80 bits. */
304 	if ((order_bits = BN_num_bits(order)) < 80) {
305 		ECerror(EC_R_INVALID_GROUP_ORDER);
306 		goto err;
307 	}
308 
309 	/* Preallocate space. */
310 	if (!BN_set_bit(k, order_bits) ||
311 	    !BN_set_bit(r, order_bits) ||
312 	    !BN_set_bit(x, order_bits))
313 		goto err;
314 
315 	/* Step 11: repeat until r != 0. */
316 	do {
317 		/* Step 3: generate random k. */
318 		if (!bn_rand_interval(k, BN_value_one(), order))
319 			goto err;
320 
321 		/*
322 		 * We do not want timing information to leak the length of k,
323 		 * so we compute G * k using an equivalent scalar of fixed
324 		 * bit-length.
325 		 *
326 		 * We unconditionally perform both of these additions to prevent
327 		 * a small timing information leakage.  We then choose the sum
328 		 * that is one bit longer than the order.  This guarantees the
329 		 * code path used in the constant time implementations
330 		 * elsewhere.
331 		 *
332 		 * TODO: revisit the bn_copy aiming for a memory access agnostic
333 		 * conditional copy.
334 		 */
335 		if (!BN_add(r, k, order) ||
336 		    !BN_add(x, r, order) ||
337 		    !bn_copy(k, BN_num_bits(r) > order_bits ? r : x))
338 			goto err;
339 
340 		BN_set_flags(k, BN_FLG_CONSTTIME);
341 
342 		/* Step 5: P = k * G. */
343 		if (!EC_POINT_mul(group, point, k, NULL, NULL, ctx)) {
344 			ECerror(ERR_R_EC_LIB);
345 			goto err;
346 		}
347 		/* Steps 6 (and 7): from P = (x, y) retain the x-coordinate. */
348 		if (!EC_POINT_get_affine_coordinates(group, point, x, NULL,
349 		    ctx)) {
350 			ECerror(ERR_R_EC_LIB);
351 			goto err;
352 		}
353 		/* Step 8: r = x (mod order). */
354 		if (!BN_nnmod(r, x, order, ctx)) {
355 			ECerror(ERR_R_BN_LIB);
356 			goto err;
357 		}
358 	} while (BN_is_zero(r));
359 
360 	/* Step 4: calculate kinv. */
361 	if (BN_mod_inverse_ct(k, k, order, ctx) == NULL) {
362 		ECerror(ERR_R_BN_LIB);
363 		goto err;
364 	}
365 
366 	*out_kinv = k;
367 	k = NULL;
368 
369 	*out_r = r;
370 	r = NULL;
371 
372 	ret = 1;
373 
374  err:
375 	BN_CTX_end(ctx);
376 	if (ctx != in_ctx)
377 		BN_CTX_free(ctx);
378 	BN_free(k);
379 	BN_free(r);
380 	EC_POINT_free(point);
381 
382 	return ret;
383 }
384 
385 /*
386  * FIPS 186-5, section 6.4.1, step 9: compute s = inv(k)(e + xr) mod order.
387  * In order to reduce the possibility of a side-channel attack, the following
388  * is calculated using a random blinding value b in [1, order):
389  * s = inv(b)(be + bxr)inv(k) mod order.
390  */
391 
392 static int
393 ecdsa_compute_s(BIGNUM **out_s, const BIGNUM *e, const BIGNUM *kinv,
394     const BIGNUM *r, const EC_KEY *key, BN_CTX *ctx)
395 {
396 	const EC_GROUP *group;
397 	const BIGNUM *order, *priv_key;
398 	BIGNUM *b, *binv, *be, *bxr;
399 	BIGNUM *s = NULL;
400 	int ret = 0;
401 
402 	*out_s = NULL;
403 
404 	BN_CTX_start(ctx);
405 
406 	if ((group = EC_KEY_get0_group(key)) == NULL) {
407 		ECerror(ERR_R_PASSED_NULL_PARAMETER);
408 		goto err;
409 	}
410 	if ((order = EC_GROUP_get0_order(group)) == NULL) {
411 		ECerror(ERR_R_EC_LIB);
412 		goto err;
413 	}
414 	if ((priv_key = EC_KEY_get0_private_key(key)) == NULL) {
415 		ECerror(ERR_R_PASSED_NULL_PARAMETER);
416 		goto err;
417 	}
418 
419 	if ((b = BN_CTX_get(ctx)) == NULL)
420 		goto err;
421 	if ((binv = BN_CTX_get(ctx)) == NULL)
422 		goto err;
423 	if ((be = BN_CTX_get(ctx)) == NULL)
424 		goto err;
425 	if ((bxr = BN_CTX_get(ctx)) == NULL)
426 		goto err;
427 
428 	if ((s = BN_new()) == NULL)
429 		goto err;
430 
431 	/*
432 	 * In a valid ECDSA signature, r must be in [1, order). Since r can be
433 	 * caller provided - either directly or by replacing sign_setup() - we
434 	 * can't rely on this being the case.
435 	 */
436 	if (BN_cmp(r, BN_value_one()) < 0 || BN_cmp(r, order) >= 0) {
437 		ECerror(EC_R_BAD_SIGNATURE);
438 		goto err;
439 	}
440 
441 	if (!bn_rand_interval(b, BN_value_one(), order)) {
442 		ECerror(ERR_R_BN_LIB);
443 		goto err;
444 	}
445 
446 	if (BN_mod_inverse_ct(binv, b, order, ctx) == NULL) {
447 		ECerror(ERR_R_BN_LIB);
448 		goto err;
449 	}
450 
451 	if (!BN_mod_mul(bxr, b, priv_key, order, ctx)) {
452 		ECerror(ERR_R_BN_LIB);
453 		goto err;
454 	}
455 	if (!BN_mod_mul(bxr, bxr, r, order, ctx)) {
456 		ECerror(ERR_R_BN_LIB);
457 		goto err;
458 	}
459 	if (!BN_mod_mul(be, b, e, order, ctx)) {
460 		ECerror(ERR_R_BN_LIB);
461 		goto err;
462 	}
463 	if (!BN_mod_add(s, be, bxr, order, ctx)) {
464 		ECerror(ERR_R_BN_LIB);
465 		goto err;
466 	}
467 	/* s = b(e + xr)k^-1 */
468 	if (!BN_mod_mul(s, s, kinv, order, ctx)) {
469 		ECerror(ERR_R_BN_LIB);
470 		goto err;
471 	}
472 	/* s = (e + xr)k^-1 */
473 	if (!BN_mod_mul(s, s, binv, order, ctx)) {
474 		ECerror(ERR_R_BN_LIB);
475 		goto err;
476 	}
477 
478 	/* Step 11: if s == 0 start over. */
479 	if (!BN_is_zero(s)) {
480 		*out_s = s;
481 		s = NULL;
482 	}
483 
484 	ret = 1;
485 
486  err:
487 	BN_CTX_end(ctx);
488 	BN_free(s);
489 
490 	return ret;
491 }
492 
493 /*
494  * It is too expensive to check curve parameters on every sign operation.
495  * Instead, cap the number of retries. A single retry is very unlikely, so
496  * allowing 32 retries is amply enough.
497  */
498 #define ECDSA_MAX_SIGN_ITERATIONS		32
499 
500 /*
501  * FIPS 186-5: Section 6.4.1: ECDSA signature generation, steps 2-12.
502  * The caller provides the hash of the message, thus performs step 1.
503  * Step 10, zeroing k and kinv, is done by BN_free().
504  */
505 
506 ECDSA_SIG *
507 ecdsa_sign_sig(const unsigned char *digest, int digest_len,
508     const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *key)
509 {
510 	BN_CTX *ctx = NULL;
511 	BIGNUM *kinv = NULL, *r = NULL, *s = NULL;
512 	BIGNUM *e;
513 	int caller_supplied_values = 0;
514 	int attempts = 0;
515 	ECDSA_SIG *sig = NULL;
516 
517 	if ((ctx = BN_CTX_new()) == NULL) {
518 		ECerror(ERR_R_MALLOC_FAILURE);
519 		goto err;
520 	}
521 
522 	BN_CTX_start(ctx);
523 
524 	if ((e = BN_CTX_get(ctx)) == NULL)
525 		goto err;
526 
527 	/* Step 2: convert hash into an integer. */
528 	if (!ecdsa_prepare_digest(digest, digest_len, key, e))
529 		goto err;
530 
531 	if (in_kinv != NULL && in_r != NULL) {
532 		/*
533 		 * Use the caller's kinv and r. Don't call ECDSA_sign_setup().
534 		 * If we're unable to compute a valid signature, the caller
535 		 * must provide new values.
536 		 */
537 		caller_supplied_values = 1;
538 
539 		if ((kinv = BN_dup(in_kinv)) == NULL) {
540 			ECerror(ERR_R_MALLOC_FAILURE);
541 			goto err;
542 		}
543 		if ((r = BN_dup(in_r)) == NULL) {
544 			ECerror(ERR_R_MALLOC_FAILURE);
545 			goto err;
546 		}
547 	}
548 
549 	do {
550 		/* Steps 3-8: calculate kinv and r. */
551 		if (!caller_supplied_values) {
552 			if (!ECDSA_sign_setup(key, ctx, &kinv, &r)) {
553 				ECerror(ERR_R_EC_LIB);
554 				goto err;
555 			}
556 		}
557 
558 		/*
559 		 * Steps 9 and 11: if s is non-NULL, we have a valid signature.
560 		 */
561 		if (!ecdsa_compute_s(&s, e, kinv, r, key, ctx))
562 			goto err;
563 		if (s != NULL)
564 			break;
565 
566 		if (caller_supplied_values) {
567 			ECerror(EC_R_NEED_NEW_SETUP_VALUES);
568 			goto err;
569 		}
570 
571 		if (++attempts > ECDSA_MAX_SIGN_ITERATIONS) {
572 			ECerror(EC_R_WRONG_CURVE_PARAMETERS);
573 			goto err;
574 		}
575 	} while (1);
576 
577 	/* Step 12: output (r, s). */
578 	if ((sig = ECDSA_SIG_new()) == NULL) {
579 		ECerror(ERR_R_MALLOC_FAILURE);
580 		goto err;
581 	}
582 	if (!ECDSA_SIG_set0(sig, r, s)) {
583 		ECDSA_SIG_free(sig);
584 		goto err;
585 	}
586 	r = NULL;
587 	s = NULL;
588 
589  err:
590 	BN_CTX_end(ctx);
591 	BN_CTX_free(ctx);
592 	BN_free(kinv);
593 	BN_free(r);
594 	BN_free(s);
595 
596 	return sig;
597 }
598 
599 int
600 ecdsa_verify(int type, const unsigned char *digest, int digest_len,
601     const unsigned char *sigbuf, int sig_len, EC_KEY *key)
602 {
603 	ECDSA_SIG *s;
604 	unsigned char *der = NULL;
605 	const unsigned char *p;
606 	int der_len = 0;
607 	int ret = -1;
608 
609 	if ((s = ECDSA_SIG_new()) == NULL)
610 		goto err;
611 
612 	p = sigbuf;
613 	if (d2i_ECDSA_SIG(&s, &p, sig_len) == NULL)
614 		goto err;
615 
616 	/* Ensure signature uses DER and doesn't have trailing garbage. */
617 	if ((der_len = i2d_ECDSA_SIG(s, &der)) != sig_len)
618 		goto err;
619 	if (timingsafe_memcmp(sigbuf, der, der_len))
620 		goto err;
621 
622 	ret = ECDSA_do_verify(digest, digest_len, s, key);
623 
624  err:
625 	freezero(der, der_len);
626 	ECDSA_SIG_free(s);
627 
628 	return ret;
629 }
630 
631 /*
632  * FIPS 186-5, section 6.4.2: ECDSA signature verification.
633  * The caller provides us with the hash of the message, so has performed step 2.
634  */
635 
636 int
637 ecdsa_verify_sig(const unsigned char *digest, int digest_len,
638     const ECDSA_SIG *sig, EC_KEY *key)
639 {
640 	const EC_GROUP *group;
641 	const EC_POINT *pub_key;
642 	EC_POINT *point = NULL;
643 	const BIGNUM *order;
644 	BN_CTX *ctx = NULL;
645 	BIGNUM *e, *sinv, *u, *v, *x;
646 	int ret = -1;
647 
648 	if (key == NULL || sig == NULL) {
649 		ECerror(EC_R_MISSING_PARAMETERS);
650 		goto err;
651 	}
652 	if ((group = EC_KEY_get0_group(key)) == NULL) {
653 		ECerror(EC_R_MISSING_PARAMETERS);
654 		goto err;
655 	}
656 	if ((pub_key = EC_KEY_get0_public_key(key)) == NULL) {
657 		ECerror(EC_R_MISSING_PARAMETERS);
658 		goto err;
659 	}
660 
661 	if ((ctx = BN_CTX_new()) == NULL) {
662 		ECerror(ERR_R_MALLOC_FAILURE);
663 		goto err;
664 	}
665 
666 	BN_CTX_start(ctx);
667 
668 	if ((e = BN_CTX_get(ctx)) == NULL)
669 		goto err;
670 	if ((sinv = BN_CTX_get(ctx)) == NULL)
671 		goto err;
672 	if ((u = BN_CTX_get(ctx)) == NULL)
673 		goto err;
674 	if ((v = BN_CTX_get(ctx)) == NULL)
675 		goto err;
676 	if ((x = BN_CTX_get(ctx)) == NULL)
677 		goto err;
678 
679 	if ((order = EC_GROUP_get0_order(group)) == NULL) {
680 		ECerror(ERR_R_EC_LIB);
681 		goto err;
682 	}
683 
684 	/* Step 1: verify that r and s are in the range [1, order). */
685 	if (BN_cmp(sig->r, BN_value_one()) < 0 || BN_cmp(sig->r, order) >= 0) {
686 		ECerror(EC_R_BAD_SIGNATURE);
687 		ret = 0;
688 		goto err;
689 	}
690 	if (BN_cmp(sig->s, BN_value_one()) < 0 || BN_cmp(sig->s, order) >= 0) {
691 		ECerror(EC_R_BAD_SIGNATURE);
692 		ret = 0;
693 		goto err;
694 	}
695 
696 	/* Step 3: convert the hash into an integer. */
697 	if (!ecdsa_prepare_digest(digest, digest_len, key, e))
698 		goto err;
699 
700 	/* Step 4: compute the inverse of s modulo order. */
701 	if (BN_mod_inverse_ct(sinv, sig->s, order, ctx) == NULL) {
702 		ECerror(ERR_R_BN_LIB);
703 		goto err;
704 	}
705 	/* Step 5: compute u = s^-1 * e and v = s^-1 * r (modulo order). */
706 	if (!BN_mod_mul(u, e, sinv, order, ctx)) {
707 		ECerror(ERR_R_BN_LIB);
708 		goto err;
709 	}
710 	if (!BN_mod_mul(v, sig->r, sinv, order, ctx)) {
711 		ECerror(ERR_R_BN_LIB);
712 		goto err;
713 	}
714 
715 	/*
716 	 * Steps 6 and 7: compute R = G * u + pub_key * v = (x, y). Reject if
717 	 * it's the point at infinity - getting affine coordinates fails. Keep
718 	 * the x coordinate.
719 	 */
720 	if ((point = EC_POINT_new(group)) == NULL) {
721 		ECerror(ERR_R_MALLOC_FAILURE);
722 		goto err;
723 	}
724 	if (!EC_POINT_mul(group, point, u, pub_key, v, ctx)) {
725 		ECerror(ERR_R_EC_LIB);
726 		goto err;
727 	}
728 	if (!EC_POINT_get_affine_coordinates(group, point, x, NULL, ctx)) {
729 		ECerror(ERR_R_EC_LIB);
730 		goto err;
731 	}
732 	/* Step 8: convert x to a number in [0, order). */
733 	if (!BN_nnmod(x, x, order, ctx)) {
734 		ECerror(ERR_R_BN_LIB);
735 		goto err;
736 	}
737 
738 	/* Step 9: the signature is valid iff the x-coordinate is equal to r. */
739 	ret = (BN_cmp(x, sig->r) == 0);
740 
741  err:
742 	BN_CTX_end(ctx);
743 	BN_CTX_free(ctx);
744 	EC_POINT_free(point);
745 
746 	return ret;
747 }
748 
749 ECDSA_SIG *
750 ECDSA_do_sign(const unsigned char *digest, int digest_len, EC_KEY *key)
751 {
752 	return ECDSA_do_sign_ex(digest, digest_len, NULL, NULL, key);
753 }
754 
755 ECDSA_SIG *
756 ECDSA_do_sign_ex(const unsigned char *digest, int digest_len,
757     const BIGNUM *kinv, const BIGNUM *out_r, EC_KEY *key)
758 {
759 	if (key->meth->sign_sig == NULL) {
760 		ECerror(EC_R_NOT_IMPLEMENTED);
761 		return 0;
762 	}
763 	return key->meth->sign_sig(digest, digest_len, kinv, out_r, key);
764 }
765 
766 int
767 ECDSA_sign(int type, const unsigned char *digest, int digest_len,
768     unsigned char *signature, unsigned int *signature_len, EC_KEY *key)
769 {
770 	return ECDSA_sign_ex(type, digest, digest_len, signature, signature_len,
771 	    NULL, NULL, key);
772 }
773 
774 int
775 ECDSA_sign_ex(int type, const unsigned char *digest, int digest_len,
776     unsigned char *signature, unsigned int *signature_len, const BIGNUM *kinv,
777     const BIGNUM *r, EC_KEY *key)
778 {
779 	if (key->meth->sign == NULL) {
780 		ECerror(EC_R_NOT_IMPLEMENTED);
781 		return 0;
782 	}
783 	return key->meth->sign(type, digest, digest_len, signature,
784 	    signature_len, kinv, r, key);
785 }
786 
787 int
788 ECDSA_sign_setup(EC_KEY *key, BN_CTX *in_ctx, BIGNUM **out_kinv,
789     BIGNUM **out_r)
790 {
791 	if (key->meth->sign_setup == NULL) {
792 		ECerror(EC_R_NOT_IMPLEMENTED);
793 		return 0;
794 	}
795 	return key->meth->sign_setup(key, in_ctx, out_kinv, out_r);
796 }
797 
798 int
799 ECDSA_do_verify(const unsigned char *digest, int digest_len,
800     const ECDSA_SIG *sig, EC_KEY *key)
801 {
802 	if (key->meth->verify_sig == NULL) {
803 		ECerror(EC_R_NOT_IMPLEMENTED);
804 		return 0;
805 	}
806 	return key->meth->verify_sig(digest, digest_len, sig, key);
807 }
808 
809 int
810 ECDSA_verify(int type, const unsigned char *digest, int digest_len,
811     const unsigned char *sigbuf, int sig_len, EC_KEY *key)
812 {
813 	if (key->meth->verify == NULL) {
814 		ECerror(EC_R_NOT_IMPLEMENTED);
815 		return 0;
816 	}
817 	return key->meth->verify(type, digest, digest_len, sigbuf, sig_len, key);
818 }
819