[secp256k1.git] / src / ecdsa_impl.h

/**********************************************************************
 * Copyright (c) 2013-2015 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 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 secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CONST(
    0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL
);

static int secp256k1_der_read_len(const unsigned char **sigp, const unsigned char *sigend) {
    int lenleft, b1;
    size_t ret = 0;
    if (*sigp >= sigend) {
        return -1;
    }
    b1 = *((*sigp)++);
    if (b1 == 0xFF) {
        /* X.690-0207 8.1.3.5.c the value 0xFF shall not be used. */
        return -1;
    }
    if ((b1 & 0x80) == 0) {
        /* X.690-0207 8.1.3.4 short form length octets */
        return b1;
    }
    if (b1 == 0x80) {
        /* Indefinite length is not allowed in DER. */
        return -1;
    }
    /* X.690-207 8.1.3.5 long form length octets */
    lenleft = b1 & 0x7F; /* lenleft is at least 1 */
    if (lenleft > sigend - *sigp) {
        return -1;
    }
    if (**sigp == 0) {
        /* Not the shortest possible length encoding. */
        return -1;
    }
    if ((size_t)lenleft > sizeof(size_t)) {
        /* The resulting length would exceed the range of a size_t, so
         * certainly longer than the passed array size.
         */
        return -1;
    }
    while (lenleft > 0) {
        ret = (ret << 8) | **sigp;
        (*sigp)++;
        lenleft--;
    }
    if (ret > (size_t)(sigend - *sigp)) {
        /* Result exceeds the length of the passed array. */
        return -1;
    }
    if (ret < 128) {
        /* Not the shortest possible length encoding. */
        return -1;
    }
    return ret;
}

static int secp256k1_der_parse_integer(secp256k1_scalar *r, const unsigned char **sig, const unsigned char *sigend) {
    int overflow = 0;
    unsigned char ra[32] = {0};
    int rlen;

    if (*sig == sigend || **sig != 0x02) {
        /* Not a primitive integer (X.690-0207 8.3.1). */
        return 0;
    }
    (*sig)++;
    rlen = secp256k1_der_read_len(sig, sigend);
    if (rlen <= 0 || (*sig) + rlen > sigend) {
        /* Exceeds bounds or not at least length 1 (X.690-0207 8.3.1).  */
        return 0;
    }
    if (**sig == 0x00 && rlen > 1 && (((*sig)[1]) & 0x80) == 0x00) {
        /* Excessive 0x00 padding. */
        return 0;
    }
    if (**sig == 0xFF && rlen > 1 && (((*sig)[1]) & 0x80) == 0x80) {
        /* Excessive 0xFF padding. */
        return 0;
    }
    if ((**sig & 0x80) == 0x80) {
        /* Negative. */
        overflow = 1;
    }
    while (rlen > 0 && **sig == 0) {
        /* Skip leading zero bytes */
        rlen--;
        (*sig)++;
    }
    if (rlen > 32) {
        overflow = 1;
    }
    if (!overflow) {
        memcpy(ra + 32 - rlen, *sig, rlen);
        secp256k1_scalar_set_b32(r, ra, &overflow);
    }
    if (overflow) {
        secp256k1_scalar_set_int(r, 0);
    }
    (*sig) += rlen;
    return 1;
}

static int secp256k1_ecdsa_sig_parse(secp256k1_scalar *rr, secp256k1_scalar *rs, const unsigned char *sig, size_t size) {
    const unsigned char *sigend = sig + size;
    int rlen;
    if (sig == sigend || *(sig++) != 0x30) {
        /* The encoding doesn't start with a constructed sequence (X.690-0207 8.9.1). */
        return 0;
    }
    rlen = secp256k1_der_read_len(&sig, sigend);
    if (rlen < 0 || sig + rlen > sigend) {
        /* Tuple exceeds bounds */
        return 0;
    }
    if (sig + rlen != sigend) {
        /* Garbage after tuple. */
        return 0;
    }

    if (!secp256k1_der_parse_integer(rr, &sig, sigend)) {
        return 0;
    }
    if (!secp256k1_der_parse_integer(rs, &sig, sigend)) {
        return 0;
    }

    if (sig != sigend) {
        /* Trailing garbage inside tuple. */
        return 0;
    }

    return 1;
}

static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, size_t *size, const secp256k1_scalar* ar, const secp256k1_scalar* as) {
    unsigned char r[33] = {0}, s[33] = {0};
    unsigned char *rp = r, *sp = s;
    size_t 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 *ctx, const secp256k1_scalar *sigr, const secp256k1_scalar *sigs, const secp256k1_ge *pubkey, const secp256k1_scalar *message) {
    unsigned char c[32];
    secp256k1_scalar sn, u1, u2;
#if !defined(EXHAUSTIVE_TEST_ORDER)
    secp256k1_fe xr;
#endif
    secp256k1_gej pubkeyj;
    secp256k1_gej 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;
    }

#if defined(EXHAUSTIVE_TEST_ORDER)
{
    secp256k1_scalar computed_r;
    secp256k1_ge pr_ge;
    secp256k1_ge_set_gej(&pr_ge, &pr);
    secp256k1_fe_normalize(&pr_ge.x);

    secp256k1_fe_get_b32(c, &pr_ge.x);
    secp256k1_scalar_set_b32(&computed_r, c, NULL);
    return secp256k1_scalar_eq(sigr, &computed_r);
}
#else
    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 * pr.z^2 mod p == pr.x, so the signature is valid. */
        return 1;
    }
    if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
        /* xr + n >= p, 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;
#endif
}

static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, secp256k1_scalar *sigr, secp256k1_scalar *sigs, const secp256k1_scalar *seckey, const secp256k1_scalar *message, const secp256k1_scalar *nonce, int *recid) {
    unsigned char b[32];
    secp256k1_gej rp;
    secp256k1_ge r;
    secp256k1_scalar 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);
    /* These two conditions should be checked before calling */
    VERIFY_CHECK(!secp256k1_scalar_is_zero(sigr));
    VERIFY_CHECK(overflow == 0);

    if (recid) {
        /* The overflow condition is cryptographically unreachable as hitting it requires finding the discrete log
         * of some P where P.x >= order, and only 1 in about 2^127 points meet this criteria.
         */
        *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 /* SECP256K1_ECDSA_IMPL_H */
Commit	Line	Data
71712b27	1	/**********************************************************************
fea19e7b	2	* Copyright (c) 2013-2015 Pieter Wuille *
71712b27 GM	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
abe2d3e8 DR	8	#ifndef SECP256K1_ECDSA_IMPL_H
abe2d3e8 DR	9	#define SECP256K1_ECDSA_IMPL_H
7a4b7691	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	*/
dd891e0e	31	static const secp256k1_fe secp256k1_ecdsa_const_order_as_fe = SECP256K1_FE_CONST(
4732d260 PW	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	*/
dd891e0e	45	static const secp256k1_fe secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CONST(
4732d260 PW	46	0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL
4732d260 PW	47	);
f24041d6	48
3bb9c447 PW	49	static int secp256k1_der_read_len(const unsigned char *sigp, const unsigned char sigend) {
	50	int lenleft, b1;
	51	size_t ret = 0;
	52	if (*sigp >= sigend) {
	53	return -1;
26320197	54	}
3bb9c447 PW	55	b1 = ((sigp)++);
	56	if (b1 == 0xFF) {
	57	/* X.690-0207 8.1.3.5.c the value 0xFF shall not be used. */
	58	return -1;
26320197	59	}
3bb9c447 PW	60	if ((b1 & 0x80) == 0) {
	61	/* X.690-0207 8.1.3.4 short form length octets */
	62	return b1;
26320197	63	}
3bb9c447 PW	64	if (b1 == 0x80) {
	65	/* Indefinite length is not allowed in DER. */
	66	return -1;
	67	}
	68	/* X.690-207 8.1.3.5 long form length octets */
3cb057f8	69	lenleft = b1 & 0x7F; /* lenleft is at least 1 */
3bb9c447 PW	70	if (lenleft > sigend - *sigp) {
	71	return -1;
	72	}
	73	if (**sigp == 0) {
	74	/* Not the shortest possible length encoding. */
	75	return -1;
	76	}
	77	if ((size_t)lenleft > sizeof(size_t)) {
269d4227 GM	78	/* The resulting length would exceed the range of a size_t, so
	79	* certainly longer than the passed array size.
	80	*/
3bb9c447	81	return -1;
26320197	82	}
3bb9c447	83	while (lenleft > 0) {
3bb9c447	84	ret = (ret << 8) \| **sigp;
3bb9c447 PW	85	(*sigp)++;
	86	lenleft--;
	87	}
3cb057f8 TR	88	if (ret > (size_t)(sigend - *sigp)) {
	89	/* Result exceeds the length of the passed array. */
	90	return -1;
	91	}
3bb9c447 PW	92	if (ret < 128) {
	93	/* Not the shortest possible length encoding. */
	94	return -1;
	95	}
	96	return ret;
	97	}
	98
	99	static int secp256k1_der_parse_integer(secp256k1_scalar r, const unsigned char sig, const unsigned char sigend) {
	100	int overflow = 0;
	101	unsigned char ra[32] = {0};
	102	int rlen;
	103
	104	if (sig == sigend \|\| *sig != 0x02) {
	105	/* Not a primitive integer (X.690-0207 8.3.1). */
26320197 GM	106	return 0;
26320197 GM	107	}
3bb9c447 PW	108	(*sig)++;
	109	rlen = secp256k1_der_read_len(sig, sigend);
	110	if (rlen <= 0 \|\| (*sig) + rlen > sigend) {
	111	/* Exceeds bounds or not at least length 1 (X.690-0207 8.3.1). */
26320197 GM	112	return 0;
26320197 GM	113	}
3bb9c447 PW	114	if (*sig == 0x00 && rlen > 1 && (((sig)[1]) & 0x80) == 0x00) {
3bb9c447 PW	115	/* Excessive 0x00 padding. */
26320197 GM	116	return 0;
26320197 GM	117	}
3bb9c447 PW	118	if (*sig == 0xFF && rlen > 1 && (((sig)[1]) & 0x80) == 0x80) {
3bb9c447 PW	119	/* Excessive 0xFF padding. */
26320197 GM	120	return 0;
26320197 GM	121	}
3bb9c447 PW	122	if ((**sig & 0x80) == 0x80) {
	123	/* Negative. */
	124	overflow = 1;
	125	}
	126	while (rlen > 0 && **sig == 0) {
	127	/* Skip leading zero bytes */
	128	rlen--;
	129	(*sig)++;
	130	}
	131	if (rlen > 32) {
	132	overflow = 1;
f24041d6	133	}
3bb9c447 PW	134	if (!overflow) {
	135	memcpy(ra + 32 - rlen, *sig, rlen);
	136	secp256k1_scalar_set_b32(r, ra, &overflow);
	137	}
	138	if (overflow) {
	139	secp256k1_scalar_set_int(r, 0);
	140	}
	141	(*sig) += rlen;
	142	return 1;
	143	}
	144
	145	static int secp256k1_ecdsa_sig_parse(secp256k1_scalar rr, secp256k1_scalar rs, const unsigned char *sig, size_t size) {
	146	const unsigned char *sigend = sig + size;
	147	int rlen;
	148	if (sig == sigend \|\| *(sig++) != 0x30) {
	149	/* The encoding doesn't start with a constructed sequence (X.690-0207 8.9.1). */
26320197 GM	150	return 0;
26320197 GM	151	}
3bb9c447 PW	152	rlen = secp256k1_der_read_len(&sig, sigend);
	153	if (rlen < 0 \|\| sig + rlen > sigend) {
	154	/* Tuple exceeds bounds */
	155	return 0;
f24041d6	156	}
3bb9c447 PW	157	if (sig + rlen != sigend) {
3bb9c447 PW	158	/* Garbage after tuple. */
26320197 GM	159	return 0;
26320197 GM	160	}
3bb9c447 PW	161
3bb9c447 PW	162	if (!secp256k1_der_parse_integer(rr, &sig, sigend)) {
26320197 GM	163	return 0;
26320197 GM	164	}
3bb9c447	165	if (!secp256k1_der_parse_integer(rs, &sig, sigend)) {
26320197 GM	166	return 0;
26320197 GM	167	}
3bb9c447 PW	168
	169	if (sig != sigend) {
	170	/* Trailing garbage inside tuple. */
	171	return 0;
	172	}
	173
d41e93a5	174	return 1;
607884fc PW	175	}
607884fc PW	176
dd891e0e	177	static int secp256k1_ecdsa_sig_serialize(unsigned char sig, size_t size, const secp256k1_scalar* ar, const secp256k1_scalar* as) {
f24041d6	178	unsigned char r[33] = {0}, s[33] = {0};
f24041d6	179	unsigned char rp = r, sp = s;
788038d3	180	size_t lenR = 33, lenS = 33;
18c329c5 PW	181	secp256k1_scalar_get_b32(&r[1], ar);
18c329c5 PW	182	secp256k1_scalar_get_b32(&s[1], as);
f24041d6 PW	183	while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; }
f24041d6 PW	184	while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; }
26320197	185	if (*size < 6+lenS+lenR) {
74a2acdb	186	*size = 6 + lenS + lenR;
d41e93a5	187	return 0;
26320197	188	}
0a07e62f PW	189	*size = 6 + lenS + lenR;
	190	sig[0] = 0x30;
	191	sig[1] = 4 + lenS + lenR;
	192	sig[2] = 0x02;
	193	sig[3] = lenR;
f24041d6	194	memcpy(sig+4, rp, lenR);
0a07e62f PW	195	sig[4+lenR] = 0x02;
0a07e62f PW	196	sig[5+lenR] = lenS;
f24041d6	197	memcpy(sig+lenR+6, sp, lenS);
d41e93a5	198	return 1;
0a07e62f PW	199	}
0a07e62f PW	200
dd891e0e	201	static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context ctx, const secp256k1_scalar sigr, const secp256k1_scalar sigs, const secp256k1_ge pubkey, const secp256k1_scalar *message) {
792bcdb0	202	unsigned char c[32];
dd891e0e	203	secp256k1_scalar sn, u1, u2;
b4ceedf1	204	#if !defined(EXHAUSTIVE_TEST_ORDER)
dd891e0e	205	secp256k1_fe xr;
b4ceedf1	206	#endif
dd891e0e PW	207	secp256k1_gej pubkeyj;
dd891e0e PW	208	secp256k1_gej pr;
792bcdb0	209
18c329c5	210	if (secp256k1_scalar_is_zero(sigr) \|\| secp256k1_scalar_is_zero(sigs)) {
d41e93a5	211	return 0;
26320197	212	}
607884fc	213
18c329c5	214	secp256k1_scalar_inverse_var(&sn, sigs);
f24041d6	215	secp256k1_scalar_mul(&u1, &sn, message);
18c329c5	216	secp256k1_scalar_mul(&u2, &sn, sigr);
792bcdb0	217	secp256k1_gej_set_ge(&pubkeyj, pubkey);
a9b6595e	218	secp256k1_ecmult(ctx, &pr, &pubkeyj, &u2, &u1);
ce7eb6fb PW	219	if (secp256k1_gej_is_infinity(&pr)) {
	220	return 0;
	221	}
b4ceedf1 AP	222
	223	#if defined(EXHAUSTIVE_TEST_ORDER)
	224	{
	225	secp256k1_scalar computed_r;
b4ceedf1 AP	226	secp256k1_ge pr_ge;
	227	secp256k1_ge_set_gej(&pr_ge, &pr);
	228	secp256k1_fe_normalize(&pr_ge.x);
	229
	230	secp256k1_fe_get_b32(c, &pr_ge.x);
678b0e54	231	secp256k1_scalar_set_b32(&computed_r, c, NULL);
b4ceedf1 AP	232	return secp256k1_scalar_eq(sigr, &computed_r);
	233	}
	234	#else
18c329c5	235	secp256k1_scalar_get_b32(c, sigr);
ce7eb6fb	236	secp256k1_fe_set_b32(&xr, c);
13278f64	237
3627437d GM	238	/** We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
	239	* in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
	240	* compute the remainder modulo n, and compare it to xr. However:
	241	*
	242	* xr == X(pr) mod n
	243	* <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
	244	* [Since 2 * n > p, h can only be 0 or 1]
	245	* <=> (xr == X(pr)) \|\| (xr + n < p && xr + n == X(pr))
	246	* [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
	247	* <=> (xr == pr.x / pr.z^2 mod p) \|\| (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
	248	* [Multiplying both sides of the equations by pr.z^2 mod p]
	249	* <=> (xr * pr.z^2 mod p == pr.x) \|\| (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
	250	*
	251	* Thus, we can avoid the inversion, but we have to check both cases separately.
	252	* secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
	253	*/
ce7eb6fb	254	if (secp256k1_gej_eq_x_var(&xr, &pr)) {
6c476a8a	255	/* xr * pr.z^2 mod p == pr.x, so the signature is valid. */
ce7eb6fb PW	256	return 1;
ce7eb6fb PW	257	}
4732d260	258	if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
6c476a8a	259	/* xr + n >= p, so we can skip testing the second case. */
ce7eb6fb	260	return 0;
4adf6b2a	261	}
4732d260	262	secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
ce7eb6fb	263	if (secp256k1_gej_eq_x_var(&xr, &pr)) {
3627437d	264	/* (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid. */
ce7eb6fb PW	265	return 1;
	266	}
	267	return 0;
b4ceedf1	268	#endif
607884fc PW	269	}
607884fc PW	270
dd891e0e	271	static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context ctx, secp256k1_scalar sigr, secp256k1_scalar sigs, const secp256k1_scalar seckey, const secp256k1_scalar message, const secp256k1_scalar nonce, int *recid) {
792bcdb0	272	unsigned char b[32];
dd891e0e PW	273	secp256k1_gej rp;
	274	secp256k1_ge r;
	275	secp256k1_scalar n;
792bcdb0 GM	276	int overflow = 0;
792bcdb0 GM	277
a9b6595e	278	secp256k1_ecmult_gen(ctx, &rp, nonce);
50eb498e	279	secp256k1_ge_set_gej(&r, &rp);
50eb498e PW	280	secp256k1_fe_normalize(&r.x);
	281	secp256k1_fe_normalize(&r.y);
	282	secp256k1_fe_get_b32(b, &r.x);
18c329c5	283	secp256k1_scalar_set_b32(sigr, b, &overflow);
25e3cfbf AP	284	/* These two conditions should be checked before calling */
	285	VERIFY_CHECK(!secp256k1_scalar_is_zero(sigr));
	286	VERIFY_CHECK(overflow == 0);
	287
26320197	288	if (recid) {
269d4227 GM	289	/* The overflow condition is cryptographically unreachable as hitting it requires finding the discrete log
	290	* of some P where P.x >= order, and only 1 in about 2^127 points meet this criteria.
	291	*/
a9f5c8b8	292	*recid = (overflow ? 2 : 0) \| (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
26320197	293	}
18c329c5	294	secp256k1_scalar_mul(&n, sigr, seckey);
a9f5c8b8	295	secp256k1_scalar_add(&n, &n, message);
18c329c5 PW	296	secp256k1_scalar_inverse(sigs, nonce);
18c329c5 PW	297	secp256k1_scalar_mul(sigs, sigs, &n);
a9f5c8b8	298	secp256k1_scalar_clear(&n);
2f6c8019 GM	299	secp256k1_gej_clear(&rp);
2f6c8019 GM	300	secp256k1_ge_clear(&r);
18c329c5	301	if (secp256k1_scalar_is_zero(sigs)) {
d41e93a5	302	return 0;
26320197	303	}
18c329c5 PW	304	if (secp256k1_scalar_is_high(sigs)) {
18c329c5 PW	305	secp256k1_scalar_negate(sigs, sigs);
26320197	306	if (recid) {
50eb498e	307	*recid ^= 1;
26320197	308	}
50eb498e	309	}
eb0be8ee	310	return 1;
0a07e62f PW	311	}
0a07e62f PW	312
abe2d3e8	313	#endif /* SECP256K1_ECDSA_IMPL_H */