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