aboutsummaryrefslogtreecommitdiff
path: root/ecdsa.c
diff options
context:
space:
mode:
Diffstat (limited to 'ecdsa.c')
-rw-r--r--ecdsa.c259
1 files changed, 194 insertions, 65 deletions
diff --git a/ecdsa.c b/ecdsa.c
index 8e715f4..38a5b31 100644
--- a/ecdsa.c
+++ b/ecdsa.c
@@ -218,35 +218,6 @@ static const ecdsa_curve_t * const get_curve(const hal_ecdsa_curve_t curve)
}
/*
- * Test whether two points are equal: x and z coordinates identical, y
- * coordinates either identical or negated.
- */
-
-static inline int point_equal(const ec_point_t * const P,
- const ec_point_t * const Q,
- const ecdsa_curve_t * const curve)
-{
- assert(P != NULL && Q != NULL && curve != NULL);
-
- if (fp_cmp(unconst_fp_int(P->x), unconst_fp_int(Q->x)) != FP_EQ ||
- fp_cmp(unconst_fp_int(P->z), unconst_fp_int(Q->z)) != FP_EQ)
- return 0;
-
- if (fp_cmp(unconst_fp_int(P->y), unconst_fp_int(Q->y)) == FP_EQ)
- return 1;
-
- fp_int Qy_neg[1];
-
- fp_sub(unconst_fp_int(curve->q), unconst_fp_int(Q->y), Qy_neg);
-
- const int result = fp_cmp(unconst_fp_int(P->y), Qy_neg) == FP_EQ;
-
- fp_zero(Qy_neg);
-
- return result;
-}
-
-/*
* Finite field operations (hence "ff_"). These are basically just
* the usual bignum operations, constrained by the field modulus.
*
@@ -314,6 +285,47 @@ static inline void ff_sqr(const ecdsa_curve_t * const curve,
fp_montgomery_reduce(b, unconst_fp_int(curve->q), curve->rho);
}
+/*
+ * Test whether a point is the point at infinity.
+ *
+ * In Jacobian projective coordinate, any point of the form
+ *
+ * (j ** 2, j **3, 0) for j in [1..q-1]
+ *
+ * is on the line at infinity, but for practical purposes simply
+ * checking the z coordinate is probably sufficient.
+ */
+
+static inline int point_is_infinite(const ec_point_t * const P)
+{
+ assert(P != NULL);
+ return fp_iszero(P->z);
+}
+
+/*
+ * Set a point to be the point at infinity. For Jacobian projective
+ * coordinates, it's customary to use (1 : 1 : 0) as the
+ * representitive value.
+ */
+
+static inline void point_set_infinite(ec_point_t *P)
+{
+ assert(P != NULL);
+ fp_set(P->x, 1);
+ fp_set(P->y, 1);
+ fp_set(P->z, 0);
+}
+
+/*
+ * Copy a point.
+ */
+
+static inline void point_copy(const ec_point_t * const P, ec_point_t *R)
+{
+ if (P != NULL && R != NULL && P != R)
+ *R = *P;
+}
+
/**
* Double an EC point.
* @param P The point to double
@@ -330,6 +342,8 @@ static inline void point_double(const ec_point_t * const P,
{
assert(P != NULL && R != NULL && curve != NULL);
+ assert(!point_is_infinite(P));
+
fp_int alpha[1], beta[1], gamma[1], delta[1], t1[1], t2[1];
fp_init(alpha); fp_init(beta); fp_init(gamma); fp_init(delta); fp_init(t1); fp_init(t2);
@@ -376,6 +390,9 @@ static inline void point_double(const ec_point_t * const P,
*
* Algorithm is add-2007-bl from
* http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html
+ *
+ * The special cases for P == Q and P == -Q are unfortunate, but are
+ * probably unavoidable for this type of curve.
*/
static inline void point_add(const ec_point_t * const P,
@@ -385,8 +402,30 @@ static inline void point_add(const ec_point_t * const P,
{
assert(P != NULL && Q != NULL && R != NULL && curve != NULL);
- if (point_equal(P, Q, curve))
- return point_double(P, R, curve);
+ if (fp_cmp(unconst_fp_int(P->x), unconst_fp_int(Q->x)) == FP_EQ &&
+ fp_cmp(unconst_fp_int(P->z), unconst_fp_int(Q->z)) == FP_EQ) {
+
+ /*
+ * If P == Q, we have to use the doubling algorithm instead.
+ */
+
+ if (fp_cmp(unconst_fp_int(P->y), unconst_fp_int(Q->y)) == FP_EQ)
+ return point_double(P, R, curve);
+
+ fp_int Qy_neg[1];
+ fp_sub(unconst_fp_int(curve->q), unconst_fp_int(Q->y), Qy_neg);
+ const int zero_sum = fp_cmp(unconst_fp_int(P->y), Qy_neg) == FP_EQ;
+ fp_zero(Qy_neg);
+
+ /*
+ * If P == -Q, P + Q is the point at infinity. Which can't be
+ * expressed in affine coordinates, but that's not this function's
+ * problem.
+ */
+
+ if (zero_sum)
+ return point_set_infinite(R);
+ }
fp_int Z1Z1[1], Z2Z2[1], U1[1], U2[1], S1[1], S2[1], H[1], I[1], J[1], r[1], V[1], t[1];
@@ -441,9 +480,14 @@ static inline void point_add(const ec_point_t * const P,
}
/**
- * Map a projective jacbobian point back to affine space
+ * Map a point in projective Jacbobian coordinates back to affine space
* @param P [in/out] The point to map
* @param curve The curve parameters structure
+ *
+ * It's not possible to represent the point at infinity in affine
+ * coordinates, and the calling function will have to handle this
+ * specially in any case, so we declare this to be the calling
+ * function's problem.
*/
static inline hal_error_t point_to_affine(ec_point_t *P,
@@ -451,6 +495,9 @@ static inline hal_error_t point_to_affine(ec_point_t *P,
{
assert(P != NULL && curve != NULL);
+ if (point_is_infinite(P))
+ return HAL_ERROR_IMPOSSIBLE;
+
hal_error_t err = HAL_ERROR_IMPOSSIBLE;
fp_int t1[1]; fp_init(t1);
@@ -585,20 +632,25 @@ static hal_error_t point_pick_random(const ecdsa_curve_t * const curve,
*
* We're picking a point out of the subgroup generated by the base
* point on the elliptic curve, so the modulus for this calculation
- * is order of the base point.
+ * is the order of the base point.
*
* Zero is an excluded value, but the chance of a non-broken CSPRNG
* returning zero is so low that it would almost certainly indicate
* an undiagnosed bug in the CSPRNG.
*/
+
uint8_t k_buf[fp_unsigned_bin_size(unconst_fp_int(curve->n)) + 8];
do {
+
if ((err = hal_get_random(k_buf, sizeof(k_buf))) != HAL_OK)
return err;
+
fp_read_unsigned_bin(k, k_buf, sizeof(k_buf));
+
if (fp_iszero(k) || fp_mod(k, unconst_fp_int(curve->n), k) != FP_OKAY)
return HAL_ERROR_IMPOSSIBLE;
+
} while (fp_iszero(k));
memset(k_buf, 0, sizeof(k_buf));
@@ -970,13 +1022,15 @@ hal_error_t hal_ecdsa_key_from_der(hal_ecdsa_key_t **key_,
return err;
}
+/*
+ * Sign a caller-supplied hash.
+ */
+
hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key,
- const hal_hash_descriptor_t * const hash_descriptor,
- const uint8_t * const input, const size_t input_len,
- uint8_t *output, size_t *output_len, const size_t output_max)
+ const uint8_t * const hash, const size_t hash_len,
+ uint8_t *signature, size_t *signature_len, const size_t signature_max)
{
- if (key == NULL || hash_descriptor == NULL || input == NULL ||
- output == NULL || output_len == NULL || key->type != HAL_ECDSA_PRIVATE)
+ if (key == NULL || hash == NULL || signature == NULL || signature_len == NULL || key->type != HAL_ECDSA_PRIVATE)
return HAL_ERROR_BAD_ARGUMENTS;
const ecdsa_curve_t * const curve = get_curve(key->curve);
@@ -996,25 +1050,7 @@ hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key,
hal_error_t err;
-#warning Should we be hashing here, or should API have caller do it? What does PKCS 11 do for ECDSA?
-
- /*
- * Hash the input and load result into e.
- */
-
- {
- uint8_t statebuf[hash_descriptor->hash_state_length];
- uint8_t hashbuf[hash_descriptor->digest_length];
- hal_hash_state_t state = { NULL };
-
- if ((err = hal_hash_initialize(hash_descriptor, &state,
- statebuf, sizeof(statebuf))) != HAL_OK ||
- (err = hal_hash_update(state, input, input_len)) != HAL_OK ||
- (err = hal_hash_finalize(state, hashbuf, sizeof(hashbuf))) != HAL_OK)
- return err;
-
- fp_read_unsigned_bin(e, hashbuf, sizeof(hashbuf));
- }
+ fp_read_unsigned_bin(e, unconst_uint8_t(hash), sizeof(hash_len));
do {
@@ -1059,16 +1095,17 @@ hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key,
if ((err = hal_asn1_encode_integer(r, NULL, &r_len, 0)) != HAL_OK ||
(err = hal_asn1_encode_integer(s, NULL, &s_len, 0)) != HAL_OK ||
- (err = hal_asn1_encode_header(ASN1_SEQUENCE, r_len + s_len, output, output_len, output_max)) != HAL_OK)
+ (err = hal_asn1_encode_header(ASN1_SEQUENCE, r_len + s_len,
+ signature, signature_len, signature_max)) != HAL_OK)
goto fail;
- uint8_t * const r_out = output + *output_len;
+ uint8_t * const r_out = signature + *signature_len;
uint8_t * const s_out = r_out + r_len;
- output_len += r_len + s_len;
- assert(*output_len <= output_max);
+ signature_len += r_len + s_len;
+ assert(*signature_len <= signature_max);
- if ((err = hal_asn1_encode_integer(r, r_out, NULL, output_max - (r_out - output))) != HAL_OK ||
- (err = hal_asn1_encode_integer(s, s_out, NULL, output_max - (s_out - output))) != HAL_OK)
+ if ((err = hal_asn1_encode_integer(r, r_out, NULL, signature_max - (r_out - signature))) != HAL_OK ||
+ (err = hal_asn1_encode_integer(s, s_out, NULL, signature_max - (s_out - signature))) != HAL_OK)
goto fail;
err = HAL_OK;
@@ -1080,9 +1117,101 @@ hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key,
}
hal_error_t hal_ecdsa_verify(const hal_ecdsa_key_t * const key,
- const hal_hash_descriptor_t * const hash_descriptor,
- const uint8_t * const input, const size_t input_len)
+ const uint8_t * const hash, const size_t hash_len,
+ const uint8_t * const signature, const size_t signature_len)
{
+ assert(key != NULL && hash != NULL && signature != NULL);
+
+ const ecdsa_curve_t * const curve = get_curve(key->curve);
+
+ if (curve == NULL)
+ return HAL_ERROR_IMPOSSIBLE;
+
+ fp_int * const n = unconst_fp_int(curve->n);
+
+ size_t len1, len2;
+ hal_error_t err;
+ fp_int r[1], s[1], e[1], w[1], u1[1], u2[1], v[1];
+ ec_point_t u1G[1], u2Q[1], R[1];
+
+ fp_init(w); fp_init(u1); fp_init(u2); fp_init(v);
+ memset(u1G, 0, sizeof(u1G));
+ memset(u2Q, 0, sizeof(u2Q));
+ memset(R, 0, sizeof(R));
+
+ /*
+ * First, we have to parse the ASN.1 SEQUENCE { INTEGER r, INTEGER s }.
+ */
+
+ if ((err = hal_asn1_decode_header(ASN1_SEQUENCE, signature, signature_len, &len1, &len2)) != HAL_OK)
+ return err;
+
+ const uint8_t * der = signature + len1;
+ const uint8_t * const der_end = der + len2;
+
+ if ((err = hal_asn1_decode_integer(r, der, &len1, der_end - der)) != HAL_OK)
+ return err;
+ der += len1;
+
+ if ((err = hal_asn1_decode_integer(s, der, &len1, der_end - der)) != HAL_OK)
+ return err;
+ der += len1;
+
+ if (der != der_end)
+ return HAL_ERROR_ASN1_PARSE_FAILED;
+
+ /*
+ * Check that r and s are in the allowed range, read the hash, then
+ * compute:
+ *
+ * w = 1 / s
+ * u1 = e * w
+ * u2 = r * w
+ * R = u1 * G + u2 * Q.
+ */
+
+ if (fp_cmp_d(r, 1) == FP_LT || fp_cmp(r, n) != FP_LT ||
+ fp_cmp_d(s, 1) == FP_LT || fp_cmp(s, n) != FP_LT)
+ return HAL_ERROR_INVALID_SIGNATURE;
+
+ fp_read_unsigned_bin(e, unconst_uint8_t(hash), sizeof(hash_len));
+
+ if (fp_invmod(s, n, w) != FP_OKAY ||
+ fp_mulmod(e, w, n, u1) != FP_OKAY ||
+ fp_mulmod(r, w, n, u2) != FP_OKAY)
+ return HAL_ERROR_IMPOSSIBLE;
+
+ fp_copy(unconst_fp_int(curve->Gx), u1G->x);
+ fp_copy(unconst_fp_int(curve->Gy), u1G->y);
+ fp_set(u1G->z, 1);
+
+ if ((err = point_scalar_multiply(u1, u1G, u1G, curve, 0)) != HAL_OK ||
+ (err = point_scalar_multiply(u2, key->Q, u2Q, curve, 0)) != HAL_OK)
+ return err;
+
+ if (point_is_infinite(u1G))
+ point_copy(u2Q, R);
+ else if (point_is_infinite(u2Q))
+ point_copy(u1G, R);
+ else
+ point_add(u1G, u2Q, R, curve);
+
+ /*
+ * Signature is OK if
+ * R is not the point at infinity, and
+ * Rx is congruent to r mod n.
+ */
+
+ if (point_is_infinite(R))
+ return HAL_ERROR_INVALID_SIGNATURE;
+
+ if ((err = point_to_affine(R, curve)) != HAL_OK)
+ return err;
+
+ if (fp_mod(R->x, n, v) != FP_OKAY)
+ return HAL_ERROR_IMPOSSIBLE;
+
+ return fp_cmp(v, r) == FP_EQ ? HAL_OK : HAL_ERROR_INVALID_SIGNATURE;
}
/*