[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"

typedef struct {
    secp256k1_fe_t order_as_fe;
    secp256k1_fe_t p_minus_order;
} secp256k1_ecdsa_consts_t;

static const secp256k1_ecdsa_consts_t *secp256k1_ecdsa_consts = NULL;

static void secp256k1_ecdsa_start(void) {
    if (secp256k1_ecdsa_consts != NULL)
        return;

    /* Allocate. */
    secp256k1_ecdsa_consts_t *ret = (secp256k1_ecdsa_consts_t*)checked_malloc(sizeof(secp256k1_ecdsa_consts_t));

    static const unsigned char order[] = {
        0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
        0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
        0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
        0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41
    };

    secp256k1_fe_set_b32(&ret->order_as_fe, order);
    secp256k1_fe_negate(&ret->p_minus_order, &ret->order_as_fe, 1);
    secp256k1_fe_normalize_var(&ret->p_minus_order);

    /* Set the global pointer. */
    secp256k1_ecdsa_consts = ret;
}

static void secp256k1_ecdsa_stop(void) {
    if (secp256k1_ecdsa_consts == NULL)
        return;

    secp256k1_ecdsa_consts_t *c = (secp256k1_ecdsa_consts_t*)secp256k1_ecdsa_consts;
    secp256k1_ecdsa_consts = NULL;
    free(c);
}

static int secp256k1_ecdsa_sig_parse(secp256k1_ecdsa_sig_t *r, const unsigned char *sig, int size) {
    if (sig[0] != 0x30) return 0;
    int lenr = sig[3];
    if (5+lenr >= size) return 0;
    int 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;
    const unsigned char *sp = sig + 6 + lenr;
    while (lens > 0 && sp[0] == 0) {
        lens--;
        sp++;
    }
    if (lens > 32) return 0;
    const unsigned char *rp = sig + 4;
    while (lenr > 0 && rp[0] == 0) {
        lenr--;
        rp++;
    }
    if (lenr > 32) return 0;
    unsigned char ra[32] = {0}, sa[32] = {0};
    memcpy(ra + 32 - lenr, rp, lenr);
    memcpy(sa + 32 - lens, sp, lens);
    int overflow = 0;
    secp256k1_scalar_set_b32(&r->r, ra, &overflow);
    if (overflow) return 0;
    secp256k1_scalar_set_b32(&r->s, sa, &overflow);
    if (overflow) return 0;
    return 1;
}

static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const secp256k1_ecdsa_sig_t *a) {
    unsigned char r[33] = {0}, s[33] = {0};
    secp256k1_scalar_get_b32(&r[1], &a->r);
    secp256k1_scalar_get_b32(&s[1], &a->s);
    unsigned char *rp = r, *sp = s;
    int lenR = 33, lenS = 33;
    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)
        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_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
    if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
        return 0;

    secp256k1_scalar_t sn, u1, u2;
    secp256k1_scalar_inverse_var(&sn, &sig->s);
    secp256k1_scalar_mul(&u1, &sn, message);
    secp256k1_scalar_mul(&u2, &sn, &sig->r);
    secp256k1_gej_t pubkeyj; secp256k1_gej_set_ge(&pubkeyj, pubkey);
    secp256k1_gej_t pr; secp256k1_ecmult(&pr, &pubkeyj, &u2, &u1);
    if (secp256k1_gej_is_infinity(&pr)) {
        return 0;
    }
    unsigned char c[32];
    secp256k1_scalar_get_b32(c, &sig->r);
    secp256k1_fe_t xr;
    secp256k1_fe_set_b32(&xr, c);
    if (secp256k1_gej_eq_x_var(&xr, &pr)) {
        return 1;
    }
    if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_consts->p_minus_order) >= 0) {
        // We can't add the order to r. This will be the case for almost every r.
        return 0;
    }
    secp256k1_fe_add(&xr, &secp256k1_ecdsa_consts->order_as_fe);
    if (secp256k1_gej_eq_x_var(&xr, &pr)) {
        return 1;
    }
    return 0;
}

static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t *sig, secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message, int recid) {
    if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
        return 0;

    unsigned char brx[32];
    secp256k1_scalar_get_b32(brx, &sig->r);
    secp256k1_fe_t fx;
    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_consts->p_minus_order) >= 0)
            return 0;
        secp256k1_fe_add(&fx, &secp256k1_ecdsa_consts->order_as_fe);
    }
    secp256k1_ge_t x;
    if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1))
        return 0;
    secp256k1_gej_t xj;
    secp256k1_gej_set_ge(&xj, &x);
    secp256k1_scalar_t rn, u1, u2;
    secp256k1_scalar_inverse_var(&rn, &sig->r);
    secp256k1_scalar_mul(&u1, &rn, message);
    secp256k1_scalar_negate(&u1, &u1);
    secp256k1_scalar_mul(&u2, &rn, &sig->s);
    secp256k1_gej_t qj;
    secp256k1_ecmult(&qj, &xj, &u2, &u1);
    secp256k1_ge_set_gej_var(pubkey, &qj);
    return !secp256k1_gej_is_infinity(&qj);
}

static int secp256k1_ecdsa_sig_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *seckey, const secp256k1_scalar_t *message, const secp256k1_scalar_t *nonce, int *recid) {
    secp256k1_gej_t rp;
    secp256k1_ecmult_gen(&rp, nonce);
    secp256k1_ge_t r;
    secp256k1_ge_set_gej(&r, &rp);
    unsigned char b[32];
    secp256k1_fe_normalize(&r.x);
    secp256k1_fe_normalize(&r.y);
    secp256k1_fe_get_b32(b, &r.x);
    int overflow = 0;
    secp256k1_scalar_set_b32(&sig->r, b, &overflow);
    if (recid)
        *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
    secp256k1_scalar_t n;
    secp256k1_scalar_mul(&n, &sig->r, seckey);
    secp256k1_scalar_add(&n, &n, message);
    secp256k1_scalar_inverse(&sig->s, nonce);
    secp256k1_scalar_mul(&sig->s, &sig->s, &n);
    secp256k1_scalar_clear(&n);
    secp256k1_gej_clear(&rp);
    secp256k1_ge_clear(&r);
    if (secp256k1_scalar_is_zero(&sig->s))
        return 0;
    if (secp256k1_scalar_is_high(&sig->s)) {
        secp256k1_scalar_negate(&sig->s, &sig->s);
        if (recid)
            *recid ^= 1;
    }
    return 1;
}

static void secp256k1_ecdsa_sig_set_rs(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *r, const secp256k1_scalar_t *s) {
    sig->r = *r;
    sig->s = *s;
}

#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
f24041d6 PW	18	typedef struct {
	19	secp256k1_fe_t order_as_fe;
	20	secp256k1_fe_t p_minus_order;
	21	} secp256k1_ecdsa_consts_t;
	22
	23	static const secp256k1_ecdsa_consts_t *secp256k1_ecdsa_consts = NULL;
	24
	25	static void secp256k1_ecdsa_start(void) {
	26	if (secp256k1_ecdsa_consts != NULL)
	27	return;
	28
	29	/* Allocate. */
a5759c57	30	secp256k1_ecdsa_consts_t ret = (secp256k1_ecdsa_consts_t)checked_malloc(sizeof(secp256k1_ecdsa_consts_t));
f24041d6	31
659b554d PW	32	static const unsigned char order[] = {
	33	0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
	34	0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
	35	0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
	36	0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41
	37	};
	38
	39	secp256k1_fe_set_b32(&ret->order_as_fe, order);
f24041d6	40	secp256k1_fe_negate(&ret->p_minus_order, &ret->order_as_fe, 1);
39bd94d8	41	secp256k1_fe_normalize_var(&ret->p_minus_order);
f24041d6 PW	42
	43	/* Set the global pointer. */
	44	secp256k1_ecdsa_consts = ret;
	45	}
	46
	47	static void secp256k1_ecdsa_stop(void) {
	48	if (secp256k1_ecdsa_consts == NULL)
	49	return;
	50
ee3eb4be	51	secp256k1_ecdsa_consts_t c = (secp256k1_ecdsa_consts_t)secp256k1_ecdsa_consts;
f24041d6 PW	52	secp256k1_ecdsa_consts = NULL;
	53	free(c);
	54	}
	55
a4a43d75	56	static int secp256k1_ecdsa_sig_parse(secp256k1_ecdsa_sig_t r, const unsigned char sig, int size) {
d41e93a5	57	if (sig[0] != 0x30) return 0;
607884fc	58	int lenr = sig[3];
d41e93a5	59	if (5+lenr >= size) return 0;
607884fc	60	int lens = sig[lenr+5];
d41e93a5 PW	61	if (sig[1] != lenr+lens+4) return 0;
	62	if (lenr+lens+6 > size) return 0;
	63	if (sig[2] != 0x02) return 0;
	64	if (lenr == 0) return 0;
	65	if (sig[lenr+4] != 0x02) return 0;
	66	if (lens == 0) return 0;
f24041d6 PW	67	const unsigned char *sp = sig + 6 + lenr;
	68	while (lens > 0 && sp[0] == 0) {
	69	lens--;
	70	sp++;
	71	}
	72	if (lens > 32) return 0;
	73	const unsigned char *rp = sig + 4;
	74	while (lenr > 0 && rp[0] == 0) {
	75	lenr--;
	76	rp++;
	77	}
	78	if (lenr > 32) return 0;
	79	unsigned char ra[32] = {0}, sa[32] = {0};
	80	memcpy(ra + 32 - lenr, rp, lenr);
	81	memcpy(sa + 32 - lens, sp, lens);
	82	int overflow = 0;
	83	secp256k1_scalar_set_b32(&r->r, ra, &overflow);
	84	if (overflow) return 0;
	85	secp256k1_scalar_set_b32(&r->s, sa, &overflow);
	86	if (overflow) return 0;
d41e93a5	87	return 1;
607884fc PW	88	}
607884fc PW	89
a4a43d75	90	static int secp256k1_ecdsa_sig_serialize(unsigned char sig, int size, const secp256k1_ecdsa_sig_t *a) {
f24041d6 PW	91	unsigned char r[33] = {0}, s[33] = {0};
	92	secp256k1_scalar_get_b32(&r[1], &a->r);
	93	secp256k1_scalar_get_b32(&s[1], &a->s);
	94	unsigned char rp = r, sp = s;
	95	int lenR = 33, lenS = 33;
	96	while (lenR > 1 && rp[0] == 0 && rp[1] < 0x80) { lenR--; rp++; }
	97	while (lenS > 1 && sp[0] == 0 && sp[1] < 0x80) { lenS--; sp++; }
0a07e62f	98	if (*size < 6+lenS+lenR)
d41e93a5	99	return 0;
0a07e62f PW	100	*size = 6 + lenS + lenR;
	101	sig[0] = 0x30;
	102	sig[1] = 4 + lenS + lenR;
	103	sig[2] = 0x02;
	104	sig[3] = lenR;
f24041d6	105	memcpy(sig+4, rp, lenR);
0a07e62f PW	106	sig[4+lenR] = 0x02;
0a07e62f PW	107	sig[5+lenR] = lenS;
f24041d6	108	memcpy(sig+lenR+6, sp, lenS);
d41e93a5	109	return 1;
0a07e62f PW	110	}
0a07e62f PW	111
ce7eb6fb	112	static int secp256k1_ecdsa_sig_verify(const secp256k1_ecdsa_sig_t sig, const secp256k1_ge_t pubkey, const secp256k1_scalar_t *message) {
f24041d6	113	if (secp256k1_scalar_is_zero(&sig->r) \|\| secp256k1_scalar_is_zero(&sig->s))
d41e93a5	114	return 0;
607884fc	115
f24041d6 PW	116	secp256k1_scalar_t sn, u1, u2;
	117	secp256k1_scalar_inverse_var(&sn, &sig->s);
	118	secp256k1_scalar_mul(&u1, &sn, message);
	119	secp256k1_scalar_mul(&u2, &sn, &sig->r);
764332d0 PW	120	secp256k1_gej_t pubkeyj; secp256k1_gej_set_ge(&pubkeyj, pubkey);
764332d0 PW	121	secp256k1_gej_t pr; secp256k1_ecmult(&pr, &pubkeyj, &u2, &u1);
ce7eb6fb PW	122	if (secp256k1_gej_is_infinity(&pr)) {
	123	return 0;
	124	}
	125	unsigned char c[32];
	126	secp256k1_scalar_get_b32(c, &sig->r);
	127	secp256k1_fe_t xr;
	128	secp256k1_fe_set_b32(&xr, c);
	129	if (secp256k1_gej_eq_x_var(&xr, &pr)) {
	130	return 1;
	131	}
	132	if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_consts->p_minus_order) >= 0) {
	133	// We can't add the order to r. This will be the case for almost every r.
	134	return 0;
4adf6b2a	135	}
ce7eb6fb PW	136	secp256k1_fe_add(&xr, &secp256k1_ecdsa_consts->order_as_fe);
	137	if (secp256k1_gej_eq_x_var(&xr, &pr)) {
	138	return 1;
	139	}
	140	return 0;
607884fc PW	141	}
607884fc PW	142
f24041d6 PW	143	static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t sig, secp256k1_ge_t pubkey, const secp256k1_scalar_t *message, int recid) {
f24041d6 PW	144	if (secp256k1_scalar_is_zero(&sig->r) \|\| secp256k1_scalar_is_zero(&sig->s))
50eb498e PW	145	return 0;
50eb498e PW	146
f24041d6 PW	147	unsigned char brx[32];
	148	secp256k1_scalar_get_b32(brx, &sig->r);
	149	secp256k1_fe_t fx;
	150	VERIFY_CHECK(secp256k1_fe_set_b32(&fx, brx)); /* brx comes from a scalar, so is less than the order; certainly less than p */
ad52495d	151	if (recid & 2) {
f24041d6	152	if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_consts->p_minus_order) >= 0)
ad52495d	153	return 0;
f24041d6	154	secp256k1_fe_add(&fx, &secp256k1_ecdsa_consts->order_as_fe);
ad52495d	155	}
50eb498e	156	secp256k1_ge_t x;
39bd94d8	157	if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1))
50eb498e PW	158	return 0;
	159	secp256k1_gej_t xj;
	160	secp256k1_gej_set_ge(&xj, &x);
f24041d6 PW	161	secp256k1_scalar_t rn, u1, u2;
	162	secp256k1_scalar_inverse_var(&rn, &sig->r);
	163	secp256k1_scalar_mul(&u1, &rn, message);
	164	secp256k1_scalar_negate(&u1, &u1);
	165	secp256k1_scalar_mul(&u2, &rn, &sig->s);
50eb498e PW	166	secp256k1_gej_t qj;
50eb498e PW	167	secp256k1_ecmult(&qj, &xj, &u2, &u1);
da55986f	168	secp256k1_ge_set_gej_var(pubkey, &qj);
4861f836	169	return !secp256k1_gej_is_infinity(&qj);
50eb498e PW	170	}
50eb498e PW	171
a4a43d75	172	static int secp256k1_ecdsa_sig_sign(secp256k1_ecdsa_sig_t sig, const secp256k1_scalar_t seckey, const secp256k1_scalar_t message, const secp256k1_scalar_t nonce, int *recid) {
f11ff5be	173	secp256k1_gej_t rp;
d41e93a5	174	secp256k1_ecmult_gen(&rp, nonce);
50eb498e PW	175	secp256k1_ge_t r;
50eb498e PW	176	secp256k1_ge_set_gej(&r, &rp);
0a07e62f	177	unsigned char b[32];
50eb498e PW	178	secp256k1_fe_normalize(&r.x);
	179	secp256k1_fe_normalize(&r.y);
	180	secp256k1_fe_get_b32(b, &r.x);
a9f5c8b8	181	int overflow = 0;
f24041d6	182	secp256k1_scalar_set_b32(&sig->r, b, &overflow);
50eb498e	183	if (recid)
a9f5c8b8 PW	184	*recid = (overflow ? 2 : 0) \| (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
a9f5c8b8 PW	185	secp256k1_scalar_t n;
f24041d6	186	secp256k1_scalar_mul(&n, &sig->r, seckey);
a9f5c8b8	187	secp256k1_scalar_add(&n, &n, message);
f24041d6 PW	188	secp256k1_scalar_inverse(&sig->s, nonce);
f24041d6 PW	189	secp256k1_scalar_mul(&sig->s, &sig->s, &n);
a9f5c8b8	190	secp256k1_scalar_clear(&n);
2f6c8019 GM	191	secp256k1_gej_clear(&rp);
2f6c8019 GM	192	secp256k1_ge_clear(&r);
f24041d6	193	if (secp256k1_scalar_is_zero(&sig->s))
d41e93a5	194	return 0;
f24041d6 PW	195	if (secp256k1_scalar_is_high(&sig->s)) {
f24041d6 PW	196	secp256k1_scalar_negate(&sig->s, &sig->s);
50eb498e PW	197	if (recid)
	198	*recid ^= 1;
	199	}
eb0be8ee	200	return 1;
0a07e62f PW	201	}
0a07e62f PW	202
f24041d6 PW	203	static void secp256k1_ecdsa_sig_set_rs(secp256k1_ecdsa_sig_t sig, const secp256k1_scalar_t r, const secp256k1_scalar_t *s) {
	204	sig->r = *r;
	205	sig->s = *s;
607884fc	206	}
7a4b7691 PW	207
7a4b7691 PW	208	#endif