1 /* 2 * Copyright 2002-2018 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the OpenSSL license (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 #include <string.h> 11 #include <openssl/err.h> 12 #include <openssl/obj_mac.h> 13 #include <openssl/rand.h> 14 #include "internal/bn_int.h" 15 #include "ec_lcl.h" 16 17 int ossl_ecdsa_sign(int type, const unsigned char *dgst, int dlen, 18 unsigned char *sig, unsigned int *siglen, 19 const BIGNUM *kinv, const BIGNUM *r, EC_KEY *eckey) 20 { 21 ECDSA_SIG *s; 22 23 s = ECDSA_do_sign_ex(dgst, dlen, kinv, r, eckey); 24 if (s == NULL) { 25 *siglen = 0; 26 return 0; 27 } 28 *siglen = i2d_ECDSA_SIG(s, &sig); 29 ECDSA_SIG_free(s); 30 return 1; 31 } 32 33 static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, 34 BIGNUM **kinvp, BIGNUM **rp, 35 const unsigned char *dgst, int dlen) 36 { 37 BN_CTX *ctx = NULL; 38 BIGNUM *k = NULL, *r = NULL, *X = NULL; 39 const BIGNUM *order; 40 EC_POINT *tmp_point = NULL; 41 const EC_GROUP *group; 42 int ret = 0; 43 int order_bits; 44 45 if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) { 46 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER); 47 return 0; 48 } 49 50 if (!EC_KEY_can_sign(eckey)) { 51 ECerr(EC_F_ECDSA_SIGN_SETUP, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING); 52 return 0; 53 } 54 55 if ((ctx = ctx_in) == NULL) { 56 if ((ctx = BN_CTX_new()) == NULL) { 57 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE); 58 return 0; 59 } 60 } 61 62 k = BN_new(); /* this value is later returned in *kinvp */ 63 r = BN_new(); /* this value is later returned in *rp */ 64 X = BN_new(); 65 if (k == NULL || r == NULL || X == NULL) { 66 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE); 67 goto err; 68 } 69 if ((tmp_point = EC_POINT_new(group)) == NULL) { 70 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 71 goto err; 72 } 73 order = EC_GROUP_get0_order(group); 74 75 /* Preallocate space */ 76 order_bits = BN_num_bits(order); 77 if (!BN_set_bit(k, order_bits) 78 || !BN_set_bit(r, order_bits) 79 || !BN_set_bit(X, order_bits)) 80 goto err; 81 82 do { 83 /* get random k */ 84 do { 85 if (dgst != NULL) { 86 if (!BN_generate_dsa_nonce(k, order, 87 EC_KEY_get0_private_key(eckey), 88 dgst, dlen, ctx)) { 89 ECerr(EC_F_ECDSA_SIGN_SETUP, 90 EC_R_RANDOM_NUMBER_GENERATION_FAILED); 91 goto err; 92 } 93 } else { 94 if (!BN_priv_rand_range(k, order)) { 95 ECerr(EC_F_ECDSA_SIGN_SETUP, 96 EC_R_RANDOM_NUMBER_GENERATION_FAILED); 97 goto err; 98 } 99 } 100 } while (BN_is_zero(k)); 101 102 /* compute r the x-coordinate of generator * k */ 103 if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) { 104 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 105 goto err; 106 } 107 108 if (!EC_POINT_get_affine_coordinates(group, tmp_point, X, NULL, ctx)) { 109 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 110 goto err; 111 } 112 113 if (!BN_nnmod(r, X, order, ctx)) { 114 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); 115 goto err; 116 } 117 } while (BN_is_zero(r)); 118 119 /* compute the inverse of k */ 120 if (!ec_group_do_inverse_ord(group, k, k, ctx)) { 121 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); 122 goto err; 123 } 124 125 /* clear old values if necessary */ 126 BN_clear_free(*rp); 127 BN_clear_free(*kinvp); 128 /* save the pre-computed values */ 129 *rp = r; 130 *kinvp = k; 131 ret = 1; 132 err: 133 if (!ret) { 134 BN_clear_free(k); 135 BN_clear_free(r); 136 } 137 if (ctx != ctx_in) 138 BN_CTX_free(ctx); 139 EC_POINT_free(tmp_point); 140 BN_clear_free(X); 141 return ret; 142 } 143 144 int ossl_ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 145 BIGNUM **rp) 146 { 147 return ecdsa_sign_setup(eckey, ctx_in, kinvp, rp, NULL, 0); 148 } 149 150 ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len, 151 const BIGNUM *in_kinv, const BIGNUM *in_r, 152 EC_KEY *eckey) 153 { 154 int ok = 0, i; 155 BIGNUM *kinv = NULL, *s, *m = NULL; 156 const BIGNUM *order, *ckinv; 157 BN_CTX *ctx = NULL; 158 const EC_GROUP *group; 159 ECDSA_SIG *ret; 160 const BIGNUM *priv_key; 161 162 group = EC_KEY_get0_group(eckey); 163 priv_key = EC_KEY_get0_private_key(eckey); 164 165 if (group == NULL || priv_key == NULL) { 166 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_PASSED_NULL_PARAMETER); 167 return NULL; 168 } 169 170 if (!EC_KEY_can_sign(eckey)) { 171 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING); 172 return NULL; 173 } 174 175 ret = ECDSA_SIG_new(); 176 if (ret == NULL) { 177 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE); 178 return NULL; 179 } 180 ret->r = BN_new(); 181 ret->s = BN_new(); 182 if (ret->r == NULL || ret->s == NULL) { 183 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE); 184 goto err; 185 } 186 s = ret->s; 187 188 if ((ctx = BN_CTX_new()) == NULL 189 || (m = BN_new()) == NULL) { 190 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE); 191 goto err; 192 } 193 194 order = EC_GROUP_get0_order(group); 195 i = BN_num_bits(order); 196 /* 197 * Need to truncate digest if it is too long: first truncate whole bytes. 198 */ 199 if (8 * dgst_len > i) 200 dgst_len = (i + 7) / 8; 201 if (!BN_bin2bn(dgst, dgst_len, m)) { 202 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); 203 goto err; 204 } 205 /* If still too long, truncate remaining bits with a shift */ 206 if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) { 207 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); 208 goto err; 209 } 210 do { 211 if (in_kinv == NULL || in_r == NULL) { 212 if (!ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, dgst, dgst_len)) { 213 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_ECDSA_LIB); 214 goto err; 215 } 216 ckinv = kinv; 217 } else { 218 ckinv = in_kinv; 219 if (BN_copy(ret->r, in_r) == NULL) { 220 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE); 221 goto err; 222 } 223 } 224 225 /* 226 * With only one multiplicant being in Montgomery domain 227 * multiplication yields real result without post-conversion. 228 * Also note that all operations but last are performed with 229 * zero-padded vectors. Last operation, BN_mod_mul_montgomery 230 * below, returns user-visible value with removed zero padding. 231 */ 232 if (!bn_to_mont_fixed_top(s, ret->r, group->mont_data, ctx) 233 || !bn_mul_mont_fixed_top(s, s, priv_key, group->mont_data, ctx)) { 234 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); 235 goto err; 236 } 237 if (!bn_mod_add_fixed_top(s, s, m, order)) { 238 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); 239 goto err; 240 } 241 /* 242 * |s| can still be larger than modulus, because |m| can be. In 243 * such case we count on Montgomery reduction to tie it up. 244 */ 245 if (!bn_to_mont_fixed_top(s, s, group->mont_data, ctx) 246 || !BN_mod_mul_montgomery(s, s, ckinv, group->mont_data, ctx)) { 247 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB); 248 goto err; 249 } 250 251 if (BN_is_zero(s)) { 252 /* 253 * if kinv and r have been supplied by the caller, don't 254 * generate new kinv and r values 255 */ 256 if (in_kinv != NULL && in_r != NULL) { 257 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, EC_R_NEED_NEW_SETUP_VALUES); 258 goto err; 259 } 260 } else { 261 /* s != 0 => we have a valid signature */ 262 break; 263 } 264 } while (1); 265 266 ok = 1; 267 err: 268 if (!ok) { 269 ECDSA_SIG_free(ret); 270 ret = NULL; 271 } 272 BN_CTX_free(ctx); 273 BN_clear_free(m); 274 BN_clear_free(kinv); 275 return ret; 276 } 277 278 /*- 279 * returns 280 * 1: correct signature 281 * 0: incorrect signature 282 * -1: error 283 */ 284 int ossl_ecdsa_verify(int type, const unsigned char *dgst, int dgst_len, 285 const unsigned char *sigbuf, int sig_len, EC_KEY *eckey) 286 { 287 ECDSA_SIG *s; 288 const unsigned char *p = sigbuf; 289 unsigned char *der = NULL; 290 int derlen = -1; 291 int ret = -1; 292 293 s = ECDSA_SIG_new(); 294 if (s == NULL) 295 return ret; 296 if (d2i_ECDSA_SIG(&s, &p, sig_len) == NULL) 297 goto err; 298 /* Ensure signature uses DER and doesn't have trailing garbage */ 299 derlen = i2d_ECDSA_SIG(s, &der); 300 if (derlen != sig_len || memcmp(sigbuf, der, derlen) != 0) 301 goto err; 302 ret = ECDSA_do_verify(dgst, dgst_len, s, eckey); 303 err: 304 OPENSSL_clear_free(der, derlen); 305 ECDSA_SIG_free(s); 306 return ret; 307 } 308 309 int ossl_ecdsa_verify_sig(const unsigned char *dgst, int dgst_len, 310 const ECDSA_SIG *sig, EC_KEY *eckey) 311 { 312 int ret = -1, i; 313 BN_CTX *ctx; 314 const BIGNUM *order; 315 BIGNUM *u1, *u2, *m, *X; 316 EC_POINT *point = NULL; 317 const EC_GROUP *group; 318 const EC_POINT *pub_key; 319 320 /* check input values */ 321 if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL || 322 (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) { 323 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, EC_R_MISSING_PARAMETERS); 324 return -1; 325 } 326 327 if (!EC_KEY_can_sign(eckey)) { 328 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING); 329 return -1; 330 } 331 332 ctx = BN_CTX_new(); 333 if (ctx == NULL) { 334 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_MALLOC_FAILURE); 335 return -1; 336 } 337 BN_CTX_start(ctx); 338 u1 = BN_CTX_get(ctx); 339 u2 = BN_CTX_get(ctx); 340 m = BN_CTX_get(ctx); 341 X = BN_CTX_get(ctx); 342 if (X == NULL) { 343 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB); 344 goto err; 345 } 346 347 order = EC_GROUP_get0_order(group); 348 if (order == NULL) { 349 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_EC_LIB); 350 goto err; 351 } 352 353 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 354 BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) || 355 BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) { 356 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, EC_R_BAD_SIGNATURE); 357 ret = 0; /* signature is invalid */ 358 goto err; 359 } 360 /* calculate tmp1 = inv(S) mod order */ 361 if (!ec_group_do_inverse_ord(group, u2, sig->s, ctx)) { 362 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB); 363 goto err; 364 } 365 /* digest -> m */ 366 i = BN_num_bits(order); 367 /* 368 * Need to truncate digest if it is too long: first truncate whole bytes. 369 */ 370 if (8 * dgst_len > i) 371 dgst_len = (i + 7) / 8; 372 if (!BN_bin2bn(dgst, dgst_len, m)) { 373 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB); 374 goto err; 375 } 376 /* If still too long truncate remaining bits with a shift */ 377 if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) { 378 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB); 379 goto err; 380 } 381 /* u1 = m * tmp mod order */ 382 if (!BN_mod_mul(u1, m, u2, order, ctx)) { 383 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB); 384 goto err; 385 } 386 /* u2 = r * w mod q */ 387 if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) { 388 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB); 389 goto err; 390 } 391 392 if ((point = EC_POINT_new(group)) == NULL) { 393 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_MALLOC_FAILURE); 394 goto err; 395 } 396 if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) { 397 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_EC_LIB); 398 goto err; 399 } 400 401 if (!EC_POINT_get_affine_coordinates(group, point, X, NULL, ctx)) { 402 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_EC_LIB); 403 goto err; 404 } 405 406 if (!BN_nnmod(u1, X, order, ctx)) { 407 ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB); 408 goto err; 409 } 410 /* if the signature is correct u1 is equal to sig->r */ 411 ret = (BN_ucmp(u1, sig->r) == 0); 412 err: 413 BN_CTX_end(ctx); 414 BN_CTX_free(ctx); 415 EC_POINT_free(point); 416 return ret; 417 } 418