aboutsummaryrefslogtreecommitdiff
path: root/src/secp256k1/src/ecdsa_impl.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/secp256k1/src/ecdsa_impl.h')
-rw-r--r--src/secp256k1/src/ecdsa_impl.h244
1 files changed, 142 insertions, 102 deletions
diff --git a/src/secp256k1/src/ecdsa_impl.h b/src/secp256k1/src/ecdsa_impl.h
index ed1d228189..d110b4bb1d 100644
--- a/src/secp256k1/src/ecdsa_impl.h
+++ b/src/secp256k1/src/ecdsa_impl.h
@@ -1,5 +1,5 @@
/**********************************************************************
- * Copyright (c) 2013, 2014 Pieter Wuille *
+ * 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.*
**********************************************************************/
@@ -28,7 +28,7 @@
* sage: '%x' % (EllipticCurve ([F (a), F (b)]).order())
* 'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'
*/
-static const secp256k1_fe_t secp256k1_ecdsa_const_order_as_fe = SECP256K1_FE_CONST(
+static const secp256k1_fe secp256k1_ecdsa_const_order_as_fe = SECP256K1_FE_CONST(
0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL,
0xBAAEDCE6UL, 0xAF48A03BUL, 0xBFD25E8CUL, 0xD0364141UL
);
@@ -42,82 +42,150 @@ static const secp256k1_fe_t secp256k1_ecdsa_const_order_as_fe = SECP256K1_FE_CON
* sage: '%x' % (p - EllipticCurve ([F (a), F (b)]).order())
* '14551231950b75fc4402da1722fc9baee'
*/
-static const secp256k1_fe_t secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CONST(
+static const secp256k1_fe secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CONST(
0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL
);
-static int secp256k1_ecdsa_sig_parse(secp256k1_ecdsa_sig_t *r, 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;
+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;
}
- lenr = sig[3];
- if (5+lenr >= size) {
- return 0;
+ b1 = *((*sigp)++);
+ if (b1 == 0xFF) {
+ /* X.690-0207 8.1.3.5.c the value 0xFF shall not be used. */
+ return -1;
}
- lens = sig[lenr+5];
- if (sig[1] != lenr+lens+4) {
- return 0;
+ if ((b1 & 0x80) == 0) {
+ /* X.690-0207 8.1.3.4 short form length octets */
+ return b1;
}
- if (lenr+lens+6 > size) {
- return 0;
+ 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;
+ 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) {
+ if ((ret >> ((sizeof(size_t) - 1) * 8)) != 0) {
+ }
+ ret = (ret << 8) | **sigp;
+ if (ret + lenleft > (size_t)(sigend - *sigp)) {
+ /* Result exceeds the length of the passed array. */
+ return -1;
+ }
+ (*sigp)++;
+ lenleft--;
+ }
+ if (ret < 128) {
+ /* Not the shortest possible length encoding. */
+ return -1;
}
- if (sig[2] != 0x02) {
+ 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;
}
- if (lenr == 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[lenr+4] != 0x02) {
+ if (**sig == 0x00 && rlen > 1 && (((*sig)[1]) & 0x80) == 0x00) {
+ /* Excessive 0x00 padding. */
return 0;
}
- if (lens == 0) {
+ if (**sig == 0xFF && rlen > 1 && (((*sig)[1]) & 0x80) == 0x80) {
+ /* Excessive 0xFF padding. */
return 0;
}
- sp = sig + 6 + lenr;
- while (lens > 0 && sp[0] == 0) {
- lens--;
- sp++;
+ if ((**sig & 0x80) == 0x80) {
+ /* Negative. */
+ overflow = 1;
+ }
+ while (rlen > 0 && **sig == 0) {
+ /* Skip leading zero bytes */
+ rlen--;
+ (*sig)++;
}
- if (lens > 32) {
+ 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;
}
- rp = sig + 4;
- while (lenr > 0 && rp[0] == 0) {
- lenr--;
- rp++;
+ rlen = secp256k1_der_read_len(&sig, sigend);
+ if (rlen < 0 || sig + rlen > sigend) {
+ /* Tuple exceeds bounds */
+ return 0;
}
- if (lenr > 32) {
+ if (sig + rlen != sigend) {
+ /* Garbage after tuple. */
return 0;
}
- memcpy(ra + 32 - lenr, rp, lenr);
- memcpy(sa + 32 - lens, sp, lens);
- overflow = 0;
- secp256k1_scalar_set_b32(&r->r, ra, &overflow);
- if (overflow) {
+
+ if (!secp256k1_der_parse_integer(rr, &sig, sigend)) {
return 0;
}
- secp256k1_scalar_set_b32(&r->s, sa, &overflow);
- if (overflow) {
+ 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, int *size, const secp256k1_ecdsa_sig_t *a) {
+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;
- int lenR = 33, lenS = 33;
- secp256k1_scalar_get_b32(&r[1], &a->r);
- secp256k1_scalar_get_b32(&s[1], &a->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;
@@ -132,26 +200,26 @@ static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const se
return 1;
}
-static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context_t *ctx, const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
+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_t sn, u1, u2;
- secp256k1_fe_t xr;
- secp256k1_gej_t pubkeyj;
- secp256k1_gej_t pr;
+ secp256k1_scalar sn, u1, u2;
+ secp256k1_fe xr;
+ secp256k1_gej pubkeyj;
+ secp256k1_gej pr;
- if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s)) {
+ if (secp256k1_scalar_is_zero(sigr) || secp256k1_scalar_is_zero(sigs)) {
return 0;
}
- secp256k1_scalar_inverse_var(&sn, &sig->s);
+ secp256k1_scalar_inverse_var(&sn, sigs);
secp256k1_scalar_mul(&u1, &sn, message);
- secp256k1_scalar_mul(&u2, &sn, &sig->r);
+ 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, &sig->r);
+ 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)
@@ -171,11 +239,11 @@ static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context_t *ctx, con
* 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. */
+ /* 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 + p >= n, so we can skip testing the second case. */
+ /* xr + n >= p, so we can skip testing the second case. */
return 0;
}
secp256k1_fe_add(&xr, &secp256k1_ecdsa_const_order_as_fe);
@@ -186,44 +254,11 @@ static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context_t *ctx, con
return 0;
}
-static int secp256k1_ecdsa_sig_recover(const secp256k1_ecmult_context_t *ctx, const secp256k1_ecdsa_sig_t *sig, 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(&sig->r) || secp256k1_scalar_is_zero(&sig->s)) {
- return 0;
- }
-
- secp256k1_scalar_get_b32(brx, &sig->r);
- 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, &sig->r);
- secp256k1_scalar_mul(&u1, &rn, message);
- secp256k1_scalar_negate(&u1, &u1);
- secp256k1_scalar_mul(&u2, &rn, &sig->s);
- 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_ecdsa_sig_t *sig, const secp256k1_scalar_t *seckey, const secp256k1_scalar_t *message, const secp256k1_scalar_t *nonce, int *recid) {
+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_t rp;
- secp256k1_ge_t r;
- secp256k1_scalar_t n;
+ secp256k1_gej rp;
+ secp256k1_ge r;
+ secp256k1_scalar n;
int overflow = 0;
secp256k1_ecmult_gen(ctx, &rp, nonce);
@@ -231,28 +266,33 @@ static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context_t *ctx, s
secp256k1_fe_normalize(&r.x);
secp256k1_fe_normalize(&r.y);
secp256k1_fe_get_b32(b, &r.x);
- secp256k1_scalar_set_b32(&sig->r, b, &overflow);
- if (secp256k1_scalar_is_zero(&sig->r)) {
- /* P.x = order is on the curve, so technically sig->r could end up zero, which would be an invalid signature. */
+ 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.
+ * This branch is cryptographically unreachable as hitting it requires finding the discrete log of P.x = N.
+ */
secp256k1_gej_clear(&rp);
secp256k1_ge_clear(&r);
return 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, &sig->r, seckey);
+ secp256k1_scalar_mul(&n, sigr, seckey);
secp256k1_scalar_add(&n, &n, message);
- secp256k1_scalar_inverse(&sig->s, nonce);
- secp256k1_scalar_mul(&sig->s, &sig->s, &n);
+ 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(&sig->s)) {
+ if (secp256k1_scalar_is_zero(sigs)) {
return 0;
}
- if (secp256k1_scalar_is_high(&sig->s)) {
- secp256k1_scalar_negate(&sig->s, &sig->s);
+ if (secp256k1_scalar_is_high(sigs)) {
+ secp256k1_scalar_negate(sigs, sigs);
if (recid) {
*recid ^= 1;
}
generated by cgit v1.2.3 (git 2.26.2) at 2024-08-25 07:16:04 +0000