[secp256k1.git] / src / ecdsa_impl.h

/**********************************************************************
 * Copyright (c) 2013, 2014 Pieter Wuille                               *
 * Distributed under the MIT software license, see the accompanying   *
 * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
 **********************************************************************/


#ifndef _SECP256K1_ECDSA_IMPL_H_
#define _SECP256K1_ECDSA_IMPL_H_

#include "scalar.h"
#include "field.h"
#include "group.h"
#include "ecmult.h"
#include "ecmult_gen.h"
#include "ecdsa.h"

/** Group order for secp256k1 defined as 'n' in "Standards for Efficient Cryptography" (SEC2) 2.7.1
 *  sage: for t in xrange(1023, -1, -1):
 *     ..   p = 2**256 - 2**32 - t
 *     ..   if p.is_prime():
 *     ..     print '%x'%p
 *     ..     break
 *   'fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f'
 *  sage: a = 0
 *  sage: b = 7
 *  sage: F = FiniteField (p)
 *  sage: '%x' % (EllipticCurve ([F (a), F (b)]).order())
 *   'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'
 */
static const secp256k1_fe_t secp256k1_ecdsa_const_order_as_fe = SECP256K1_FE_CONST(
    0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL,
    0xBAAEDCE6UL, 0xAF48A03BUL, 0xBFD25E8CUL, 0xD0364141UL
);

/** Difference between field and order, values 'p' and 'n' values defined in
 *  "Standards for Efficient Cryptography" (SEC2) 2.7.1.
 *  sage: p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
 *  sage: a = 0
 *  sage: b = 7
 *  sage: F = FiniteField (p)
 *  sage: '%x' % (p - EllipticCurve ([F (a), F (b)]).order())
 *   '14551231950b75fc4402da1722fc9baee'
 */
static const secp256k1_fe_t secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CONST(
    0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL
);

static int secp256k1_ecdsa_sig_parse(secp256k1_scalar_t *rr, secp256k1_scalar_t *rs, const unsigned char *sig, int size) {
    unsigned char ra[32] = {0}, sa[32] = {0};
    const unsigned char *rp;
    const unsigned char *sp;
    int lenr;
    int lens;
    int overflow;
    if (sig[0] != 0x30) {
        return 0;
    }
    lenr = sig[3];
    if (5+lenr >= size) {
        return 0;
    }
    lens = sig[lenr+5];
    if (sig[1] != lenr+lens+4) {
        return 0;
    }
    if (lenr+lens+6 > size) {
        return 0;
    }
    if (sig[2] != 0x02) {
        return 0;
    }
    if (lenr == 0) {
        return 0;
    }
    if (sig[lenr+4] != 0x02) {
        return 0;
    }
    if (lens == 0) {
        return 0;
    }
    sp = sig + 6 + lenr;
    while (lens > 0 && sp[0] == 0) {
        lens--;
        sp++;
    }
    if (lens > 32) {
        return 0;
    }
    rp = sig + 4;
    while (lenr > 0 && rp[0] == 0) {
        lenr--;
        rp++;
    }
    if (lenr > 32) {
        return 0;
    }
    memcpy(ra + 32 - lenr, rp, lenr);
    memcpy(sa + 32 - lens, sp, lens);
    overflow = 0;
    secp256k1_scalar_set_b32(rr, ra, &overflow);
    if (overflow) {
        return 0;
    }
    secp256k1_scalar_set_b32(rs, sa, &overflow);
    if (overflow) {
        return 0;
    }
    return 1;
}

static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const secp256k1_scalar_t* ar, const secp256k1_scalar_t* as) {
    unsigned char r[33] = {0}, s[33] = {0};
    unsigned char *rp = r, *sp = s;
    int lenR = 33, lenS = 33;
    secp256k1_scalar_get_b32(&r[1], ar);
    secp256k1_scalar_get_b32(&s[1], as);
    while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; }
    while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; }
    if (*size < 6+lenS+lenR) {
        *size = 6 + lenS + lenR;
        return 0;
    }
    *size = 6 + lenS + lenR;
    sig[0] = 0x30;
    sig[1] = 4 + lenS + lenR;
    sig[2] = 0x02;
    sig[3] = lenR;
    memcpy(sig+4, rp, lenR);
    sig[4+lenR] = 0x02;
    sig[5+lenR] = lenS;
    memcpy(sig+lenR+6, sp, lenS);
    return 1;
}

static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context_t *ctx, const secp256k1_scalar_t *sigr, const secp256k1_scalar_t *sigs, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
    unsigned char c[32];
    secp256k1_scalar_t sn, u1, u2;
    secp256k1_fe_t xr;
    secp256k1_gej_t pubkeyj;
    secp256k1_gej_t pr;

    if (secp256k1_scalar_is_zero(sigr) || secp256k1_scalar_is_zero(sigs)) {
        return 0;
    }

    secp256k1_scalar_inverse_var(&sn, sigs);
    secp256k1_scalar_mul(&u1, &sn, message);
    secp256k1_scalar_mul(&u2, &sn, sigr);
    secp256k1_gej_set_ge(&pubkeyj, pubkey);
    secp256k1_ecmult(ctx, &pr, &pubkeyj, &u2, &u1);
    if (secp256k1_gej_is_infinity(&pr)) {
        return 0;
    }
    secp256k1_scalar_get_b32(c, sigr);
    secp256k1_fe_set_b32(&xr, c);

    /** We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
     *  in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
     *  compute the remainder modulo n, and compare it to xr. However:
     *
     *        xr == X(pr) mod n
     *    <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
     *    [Since 2 * n > p, h can only be 0 or 1]
     *    <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr))
     *    [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
     *    <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
     *    [Multiplying both sides of the equations by pr.z^2 mod p]
     *    <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
     *
     *  Thus, we can avoid the inversion, but we have to check both cases separately.
     *  secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
     */
    if (secp256k1_gej_eq_x_var(&xr, &pr)) {
        /* xr.x == xr * xr.z^2 mod p, so the signature is valid. */
        return 1;
    }
    if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
        /* xr + p >= n, so we can skip testing the second case. */
        return 0;
    }
    secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
    if (secp256k1_gej_eq_x_var(&xr, &pr)) {
        /* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */
        return 1;
    }
    return 0;
}

static int secp256k1_ecdsa_sig_recover(const secp256k1_ecmult_context_t *ctx, const secp256k1_scalar_t *sigr, const secp256k1_scalar_t* sigs, secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message, int recid) {
    unsigned char brx[32];
    secp256k1_fe_t fx;
    secp256k1_ge_t x;
    secp256k1_gej_t xj;
    secp256k1_scalar_t rn, u1, u2;
    secp256k1_gej_t qj;

    if (secp256k1_scalar_is_zero(sigr) || secp256k1_scalar_is_zero(sigs)) {
        return 0;
    }

    secp256k1_scalar_get_b32(brx, sigr);
    VERIFY_CHECK(secp256k1_fe_set_b32(&fx, brx)); /* brx comes from a scalar, so is less than the order; certainly less than p */
    if (recid & 2) {
        if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
            return 0;
        }
        secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
    }
    if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1)) {
        return 0;
    }
    secp256k1_gej_set_ge(&xj, &x);
    secp256k1_scalar_inverse_var(&rn, sigr);
    secp256k1_scalar_mul(&u1, &rn, message);
    secp256k1_scalar_negate(&u1, &u1);
    secp256k1_scalar_mul(&u2, &rn, sigs);
    secp256k1_ecmult(ctx, &qj, &xj, &u2, &u1);
    secp256k1_ge_set_gej_var(pubkey, &qj);
    return !secp256k1_gej_is_infinity(&qj);
}

static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context_t *ctx, secp256k1_scalar_t *sigr, secp256k1_scalar_t *sigs, const secp256k1_scalar_t *seckey, const secp256k1_scalar_t *message, const secp256k1_scalar_t *nonce, int *recid) {
    unsigned char b[32];
    secp256k1_gej_t rp;
    secp256k1_ge_t r;
    secp256k1_scalar_t n;
    int overflow = 0;

    secp256k1_ecmult_gen(ctx, &rp, nonce);
    secp256k1_ge_set_gej(&r, &rp);
    secp256k1_fe_normalize(&r.x);
    secp256k1_fe_normalize(&r.y);
    secp256k1_fe_get_b32(b, &r.x);
    secp256k1_scalar_set_b32(sigr, b, &overflow);
    if (secp256k1_scalar_is_zero(sigr)) {
        /* P.x = order is on the curve, so technically sig->r could end up zero, which would be an invalid signature. */
        secp256k1_gej_clear(&rp);
        secp256k1_ge_clear(&r);
        return 0;
    }
    if (recid) {
        *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
    }
    secp256k1_scalar_mul(&n, sigr, seckey);
    secp256k1_scalar_add(&n, &n, message);
    secp256k1_scalar_inverse(sigs, nonce);
    secp256k1_scalar_mul(sigs, sigs, &n);
    secp256k1_scalar_clear(&n);
    secp256k1_gej_clear(&rp);
    secp256k1_ge_clear(&r);
    if (secp256k1_scalar_is_zero(sigs)) {
        return 0;
    }
    if (secp256k1_scalar_is_high(sigs)) {
        secp256k1_scalar_negate(sigs, sigs);
        if (recid) {
            *recid ^= 1;
        }
    }
    return 1;
}

#endif
Commit	Line	Data
71712b27 GM	1	/**********************************************************************
	2	* Copyright (c) 2013, 2014 Pieter Wuille *
	3	* Distributed under the MIT software license, see the accompanying *
	4	* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
	5	**********************************************************************/
	6
0a433ea2	7
7a4b7691 PW	8	#ifndef _SECP256K1_ECDSA_IMPL_H_
	9	#define _SECP256K1_ECDSA_IMPL_H_
	10
f24041d6	11	#include "scalar.h"
11ab5622 PW	12	#include "field.h"
	13	#include "group.h"
	14	#include "ecmult.h"
949c1ebb	15	#include "ecmult_gen.h"
11ab5622	16	#include "ecdsa.h"
607884fc	17
6efd6e77 GM	18	/** Group order for secp256k1 defined as 'n' in "Standards for Efficient Cryptography" (SEC2) 2.7.1
	19	* sage: for t in xrange(1023, -1, -1):
	20	* .. p = 2256 - 232 - t
	21	* .. if p.is_prime():
	22	* .. print '%x'%p
	23	* .. break
	24	* 'fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f'
	25	* sage: a = 0
	26	* sage: b = 7
	27	* sage: F = FiniteField (p)
	28	* sage: '%x' % (EllipticCurve ([F (a), F (b)]).order())
	29	* 'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'
	30	*/
4732d260 PW	31	static const secp256k1_fe_t secp256k1_ecdsa_const_order_as_fe = SECP256K1_FE_CONST(
	32	0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL,
	33	0xBAAEDCE6UL, 0xAF48A03BUL, 0xBFD25E8CUL, 0xD0364141UL
	34	);
f24041d6	35
6efd6e77 GM	36	/** Difference between field and order, values 'p' and 'n' values defined in
	37	* "Standards for Efficient Cryptography" (SEC2) 2.7.1.
	38	* sage: p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
	39	* sage: a = 0
	40	* sage: b = 7
	41	* sage: F = FiniteField (p)
	42	* sage: '%x' % (p - EllipticCurve ([F (a), F (b)]).order())
	43	* '14551231950b75fc4402da1722fc9baee'
	44	*/
4732d260 PW	45	static const secp256k1_fe_t secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CONST(
	46	0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL
	47	);
f24041d6	48
18c329c5	49	static int secp256k1_ecdsa_sig_parse(secp256k1_scalar_t rr, secp256k1_scalar_t rs, const unsigned char *sig, int size) {
792bcdb0 GM	50	unsigned char ra[32] = {0}, sa[32] = {0};
	51	const unsigned char *rp;
	52	const unsigned char *sp;
	53	int lenr;
	54	int lens;
	55	int overflow;
26320197 GM	56	if (sig[0] != 0x30) {
	57	return 0;
	58	}
792bcdb0	59	lenr = sig[3];
26320197 GM	60	if (5+lenr >= size) {
	61	return 0;
	62	}
792bcdb0	63	lens = sig[lenr+5];
26320197 GM	64	if (sig[1] != lenr+lens+4) {
	65	return 0;
	66	}
	67	if (lenr+lens+6 > size) {
	68	return 0;
	69	}
	70	if (sig[2] != 0x02) {
	71	return 0;
	72	}
	73	if (lenr == 0) {
	74	return 0;
	75	}
	76	if (sig[lenr+4] != 0x02) {
	77	return 0;
	78	}
	79	if (lens == 0) {
	80	return 0;
	81	}
792bcdb0	82	sp = sig + 6 + lenr;
f24041d6 PW	83	while (lens > 0 && sp[0] == 0) {
	84	lens--;
	85	sp++;
	86	}
26320197 GM	87	if (lens > 32) {
	88	return 0;
	89	}
792bcdb0	90	rp = sig + 4;
f24041d6 PW	91	while (lenr > 0 && rp[0] == 0) {
	92	lenr--;
	93	rp++;
	94	}
26320197 GM	95	if (lenr > 32) {
	96	return 0;
	97	}
f24041d6 PW	98	memcpy(ra + 32 - lenr, rp, lenr);
f24041d6 PW	99	memcpy(sa + 32 - lens, sp, lens);
792bcdb0	100	overflow = 0;
18c329c5	101	secp256k1_scalar_set_b32(rr, ra, &overflow);
26320197 GM	102	if (overflow) {
	103	return 0;
	104	}
18c329c5	105	secp256k1_scalar_set_b32(rs, sa, &overflow);
26320197 GM	106	if (overflow) {
	107	return 0;
	108	}
d41e93a5	109	return 1;
607884fc PW	110	}
607884fc PW	111
18c329c5	112	static int secp256k1_ecdsa_sig_serialize(unsigned char sig, int size, const secp256k1_scalar_t* ar, const secp256k1_scalar_t* as) {
f24041d6	113	unsigned char r[33] = {0}, s[33] = {0};
f24041d6 PW	114	unsigned char rp = r, sp = s;
f24041d6 PW	115	int lenR = 33, lenS = 33;
18c329c5 PW	116	secp256k1_scalar_get_b32(&r[1], ar);
18c329c5 PW	117	secp256k1_scalar_get_b32(&s[1], as);
f24041d6 PW	118	while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; }
f24041d6 PW	119	while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; }
26320197	120	if (*size < 6+lenS+lenR) {
74a2acdb	121	*size = 6 + lenS + lenR;
d41e93a5	122	return 0;
26320197	123	}
0a07e62f PW	124	*size = 6 + lenS + lenR;
	125	sig[0] = 0x30;
	126	sig[1] = 4 + lenS + lenR;
	127	sig[2] = 0x02;
	128	sig[3] = lenR;
f24041d6	129	memcpy(sig+4, rp, lenR);
0a07e62f PW	130	sig[4+lenR] = 0x02;
0a07e62f PW	131	sig[5+lenR] = lenS;
f24041d6	132	memcpy(sig+lenR+6, sp, lenS);
d41e93a5	133	return 1;
0a07e62f PW	134	}
0a07e62f PW	135
18c329c5	136	static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context_t ctx, const secp256k1_scalar_t sigr, const secp256k1_scalar_t sigs, const secp256k1_ge_t pubkey, const secp256k1_scalar_t *message) {
792bcdb0 GM	137	unsigned char c[32];
	138	secp256k1_scalar_t sn, u1, u2;
	139	secp256k1_fe_t xr;
	140	secp256k1_gej_t pubkeyj;
	141	secp256k1_gej_t pr;
	142
18c329c5	143	if (secp256k1_scalar_is_zero(sigr) \|\| secp256k1_scalar_is_zero(sigs)) {
d41e93a5	144	return 0;
26320197	145	}
607884fc	146
18c329c5	147	secp256k1_scalar_inverse_var(&sn, sigs);
f24041d6	148	secp256k1_scalar_mul(&u1, &sn, message);
18c329c5	149	secp256k1_scalar_mul(&u2, &sn, sigr);
792bcdb0	150	secp256k1_gej_set_ge(&pubkeyj, pubkey);
a9b6595e	151	secp256k1_ecmult(ctx, &pr, &pubkeyj, &u2, &u1);
ce7eb6fb PW	152	if (secp256k1_gej_is_infinity(&pr)) {
	153	return 0;
	154	}
18c329c5	155	secp256k1_scalar_get_b32(c, sigr);
ce7eb6fb	156	secp256k1_fe_set_b32(&xr, c);
13278f64	157
3627437d GM	158	/** We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
	159	* in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
	160	* compute the remainder modulo n, and compare it to xr. However:
	161	*
	162	* xr == X(pr) mod n
	163	* <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
	164	* [Since 2 * n > p, h can only be 0 or 1]
	165	* <=> (xr == X(pr)) \|\| (xr + n < p && xr + n == X(pr))
	166	* [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
	167	* <=> (xr == pr.x / pr.z^2 mod p) \|\| (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
	168	* [Multiplying both sides of the equations by pr.z^2 mod p]
	169	* <=> (xr * pr.z^2 mod p == pr.x) \|\| (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
	170	*
	171	* Thus, we can avoid the inversion, but we have to check both cases separately.
	172	* secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
	173	*/
ce7eb6fb	174	if (secp256k1_gej_eq_x_var(&xr, &pr)) {
3627437d	175	/* xr.x == xr * xr.z^2 mod p, so the signature is valid. */
ce7eb6fb PW	176	return 1;
ce7eb6fb PW	177	}
4732d260	178	if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
3627437d	179	/* xr + p >= n, so we can skip testing the second case. */
ce7eb6fb	180	return 0;
4adf6b2a	181	}
4732d260	182	secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
ce7eb6fb	183	if (secp256k1_gej_eq_x_var(&xr, &pr)) {
3627437d	184	/* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */
ce7eb6fb PW	185	return 1;
	186	}
	187	return 0;
607884fc PW	188	}
607884fc PW	189
18c329c5	190	static int secp256k1_ecdsa_sig_recover(const secp256k1_ecmult_context_t ctx, const secp256k1_scalar_t sigr, const secp256k1_scalar_t* sigs, secp256k1_ge_t pubkey, const secp256k1_scalar_t message, int recid) {
792bcdb0 GM	191	unsigned char brx[32];
	192	secp256k1_fe_t fx;
	193	secp256k1_ge_t x;
	194	secp256k1_gej_t xj;
	195	secp256k1_scalar_t rn, u1, u2;
	196	secp256k1_gej_t qj;
	197
18c329c5	198	if (secp256k1_scalar_is_zero(sigr) \|\| secp256k1_scalar_is_zero(sigs)) {
50eb498e	199	return 0;
26320197	200	}
50eb498e	201
18c329c5	202	secp256k1_scalar_get_b32(brx, sigr);
f24041d6	203	VERIFY_CHECK(secp256k1_fe_set_b32(&fx, brx)); /* brx comes from a scalar, so is less than the order; certainly less than p */
ad52495d	204	if (recid & 2) {
26320197	205	if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
ad52495d	206	return 0;
26320197	207	}
4732d260	208	secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
ad52495d	209	}
26320197	210	if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1)) {
50eb498e	211	return 0;
26320197	212	}
50eb498e	213	secp256k1_gej_set_ge(&xj, &x);
18c329c5	214	secp256k1_scalar_inverse_var(&rn, sigr);
f24041d6 PW	215	secp256k1_scalar_mul(&u1, &rn, message);
f24041d6 PW	216	secp256k1_scalar_negate(&u1, &u1);
18c329c5	217	secp256k1_scalar_mul(&u2, &rn, sigs);
a9b6595e	218	secp256k1_ecmult(ctx, &qj, &xj, &u2, &u1);
da55986f	219	secp256k1_ge_set_gej_var(pubkey, &qj);
4861f836	220	return !secp256k1_gej_is_infinity(&qj);
50eb498e PW	221	}
50eb498e PW	222
18c329c5	223	static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context_t ctx, secp256k1_scalar_t sigr, secp256k1_scalar_t sigs, const secp256k1_scalar_t seckey, const secp256k1_scalar_t message, const secp256k1_scalar_t nonce, int *recid) {
792bcdb0	224	unsigned char b[32];
f11ff5be	225	secp256k1_gej_t rp;
50eb498e	226	secp256k1_ge_t r;
792bcdb0 GM	227	secp256k1_scalar_t n;
	228	int overflow = 0;
	229
a9b6595e	230	secp256k1_ecmult_gen(ctx, &rp, nonce);
50eb498e	231	secp256k1_ge_set_gej(&r, &rp);
50eb498e PW	232	secp256k1_fe_normalize(&r.x);
	233	secp256k1_fe_normalize(&r.y);
	234	secp256k1_fe_get_b32(b, &r.x);
18c329c5 PW	235	secp256k1_scalar_set_b32(sigr, b, &overflow);
18c329c5 PW	236	if (secp256k1_scalar_is_zero(sigr)) {
d26e26f2 GM	237	/* P.x = order is on the curve, so technically sig->r could end up zero, which would be an invalid signature. */
	238	secp256k1_gej_clear(&rp);
	239	secp256k1_ge_clear(&r);
	240	return 0;
	241	}
26320197	242	if (recid) {
a9f5c8b8	243	*recid = (overflow ? 2 : 0) \| (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
26320197	244	}
18c329c5	245	secp256k1_scalar_mul(&n, sigr, seckey);
a9f5c8b8	246	secp256k1_scalar_add(&n, &n, message);
18c329c5 PW	247	secp256k1_scalar_inverse(sigs, nonce);
18c329c5 PW	248	secp256k1_scalar_mul(sigs, sigs, &n);
a9f5c8b8	249	secp256k1_scalar_clear(&n);
2f6c8019 GM	250	secp256k1_gej_clear(&rp);
2f6c8019 GM	251	secp256k1_ge_clear(&r);
18c329c5	252	if (secp256k1_scalar_is_zero(sigs)) {
d41e93a5	253	return 0;
26320197	254	}
18c329c5 PW	255	if (secp256k1_scalar_is_high(sigs)) {
18c329c5 PW	256	secp256k1_scalar_negate(sigs, sigs);
26320197	257	if (recid) {
50eb498e	258	*recid ^= 1;
26320197	259	}
50eb498e	260	}
eb0be8ee	261	return 1;
0a07e62f PW	262	}
0a07e62f PW	263
7a4b7691	264	#endif