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