1 /* ==================================================================== 2 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in 13 * the documentation and/or other materials provided with the 14 * distribution. 15 * 16 * 3. All advertising materials mentioning features or use of this 17 * software must display the following acknowledgment: 18 * "This product includes software developed by the OpenSSL Project 19 * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" 20 * 21 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 22 * endorse or promote products derived from this software without 23 * prior written permission. For written permission, please contact 24 * openssl-core (at) OpenSSL.org. 25 * 26 * 5. Products derived from this software may not be called "OpenSSL" 27 * nor may "OpenSSL" appear in their names without prior written 28 * permission of the OpenSSL Project. 29 * 30 * 6. Redistributions of any form whatsoever must retain the following 31 * acknowledgment: 32 * "This product includes software developed by the OpenSSL Project 33 * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" 34 * 35 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 36 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 37 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 38 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 39 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 40 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 41 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 42 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 43 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 44 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 45 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 46 * OF THE POSSIBILITY OF SUCH DAMAGE. 47 * ==================================================================== 48 * 49 * This product includes cryptographic software written by Eric Young 50 * (eay (at) cryptsoft.com). This product includes software written by Tim 51 * Hudson (tjh (at) cryptsoft.com). */ 52 53 #include <openssl/ecdsa.h> 54 55 #include <assert.h> 56 #include <string.h> 57 58 #include <openssl/bn.h> 59 #include <openssl/bytestring.h> 60 #include <openssl/err.h> 61 #include <openssl/mem.h> 62 63 #include "../bn/internal.h" 64 #include "../ec/internal.h" 65 #include "../internal.h" 66 67 68 int ECDSA_sign(int type, const uint8_t *digest, size_t digest_len, uint8_t *sig, 69 unsigned int *sig_len, const EC_KEY *eckey) { 70 if (eckey->ecdsa_meth && eckey->ecdsa_meth->sign) { 71 return eckey->ecdsa_meth->sign(digest, digest_len, sig, sig_len, 72 (EC_KEY*) eckey /* cast away const */); 73 } 74 75 return ECDSA_sign_ex(type, digest, digest_len, sig, sig_len, NULL, NULL, 76 eckey); 77 } 78 79 int ECDSA_verify(int type, const uint8_t *digest, size_t digest_len, 80 const uint8_t *sig, size_t sig_len, const EC_KEY *eckey) { 81 ECDSA_SIG *s; 82 int ret = 0; 83 uint8_t *der = NULL; 84 85 /* Decode the ECDSA signature. */ 86 s = ECDSA_SIG_from_bytes(sig, sig_len); 87 if (s == NULL) { 88 goto err; 89 } 90 91 /* Defend against potential laxness in the DER parser. */ 92 size_t der_len; 93 if (!ECDSA_SIG_to_bytes(&der, &der_len, s) || 94 der_len != sig_len || OPENSSL_memcmp(sig, der, sig_len) != 0) { 95 /* This should never happen. crypto/bytestring is strictly DER. */ 96 OPENSSL_PUT_ERROR(ECDSA, ERR_R_INTERNAL_ERROR); 97 goto err; 98 } 99 100 ret = ECDSA_do_verify(digest, digest_len, s, eckey); 101 102 err: 103 OPENSSL_free(der); 104 ECDSA_SIG_free(s); 105 return ret; 106 } 107 108 /* digest_to_bn interprets |digest_len| bytes from |digest| as a big-endian 109 * number and sets |out| to that value. It then truncates |out| so that it's, 110 * at most, as long as |order|. It returns one on success and zero otherwise. */ 111 static int digest_to_bn(BIGNUM *out, const uint8_t *digest, size_t digest_len, 112 const BIGNUM *order) { 113 size_t num_bits; 114 115 num_bits = BN_num_bits(order); 116 /* Need to truncate digest if it is too long: first truncate whole 117 * bytes. */ 118 if (8 * digest_len > num_bits) { 119 digest_len = (num_bits + 7) / 8; 120 } 121 if (!BN_bin2bn(digest, digest_len, out)) { 122 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 123 return 0; 124 } 125 126 /* If still too long truncate remaining bits with a shift */ 127 if ((8 * digest_len > num_bits) && 128 !BN_rshift(out, out, 8 - (num_bits & 0x7))) { 129 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 130 return 0; 131 } 132 133 return 1; 134 } 135 136 ECDSA_SIG *ECDSA_do_sign(const uint8_t *digest, size_t digest_len, 137 const EC_KEY *key) { 138 return ECDSA_do_sign_ex(digest, digest_len, NULL, NULL, key); 139 } 140 141 int ECDSA_do_verify(const uint8_t *digest, size_t digest_len, 142 const ECDSA_SIG *sig, const EC_KEY *eckey) { 143 int ret = 0; 144 BN_CTX *ctx; 145 BIGNUM *u1, *u2, *m, *X; 146 EC_POINT *point = NULL; 147 const EC_GROUP *group; 148 const EC_POINT *pub_key; 149 150 /* check input values */ 151 if ((group = EC_KEY_get0_group(eckey)) == NULL || 152 (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || 153 sig == NULL) { 154 OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_MISSING_PARAMETERS); 155 return 0; 156 } 157 158 ctx = BN_CTX_new(); 159 if (!ctx) { 160 OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); 161 return 0; 162 } 163 BN_CTX_start(ctx); 164 u1 = BN_CTX_get(ctx); 165 u2 = BN_CTX_get(ctx); 166 m = BN_CTX_get(ctx); 167 X = BN_CTX_get(ctx); 168 if (u1 == NULL || u2 == NULL || m == NULL || X == NULL) { 169 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 170 goto err; 171 } 172 173 const BIGNUM *order = EC_GROUP_get0_order(group); 174 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 175 BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) || 176 BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) { 177 OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_BAD_SIGNATURE); 178 ret = 0; /* signature is invalid */ 179 goto err; 180 } 181 /* calculate tmp1 = inv(S) mod order */ 182 int no_inverse; 183 if (!BN_mod_inverse_odd(u2, &no_inverse, sig->s, order, ctx)) { 184 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 185 goto err; 186 } 187 if (!digest_to_bn(m, digest, digest_len, order)) { 188 goto err; 189 } 190 /* u1 = m * tmp mod order */ 191 if (!BN_mod_mul(u1, m, u2, order, ctx)) { 192 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 193 goto err; 194 } 195 /* u2 = r * w mod q */ 196 if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) { 197 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 198 goto err; 199 } 200 201 point = EC_POINT_new(group); 202 if (point == NULL) { 203 OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); 204 goto err; 205 } 206 if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) { 207 OPENSSL_PUT_ERROR(ECDSA, ERR_R_EC_LIB); 208 goto err; 209 } 210 if (!EC_POINT_get_affine_coordinates_GFp(group, point, X, NULL, ctx)) { 211 OPENSSL_PUT_ERROR(ECDSA, ERR_R_EC_LIB); 212 goto err; 213 } 214 if (!BN_nnmod(u1, X, order, ctx)) { 215 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 216 goto err; 217 } 218 /* if the signature is correct u1 is equal to sig->r */ 219 ret = (BN_ucmp(u1, sig->r) == 0); 220 221 err: 222 BN_CTX_end(ctx); 223 BN_CTX_free(ctx); 224 EC_POINT_free(point); 225 return ret; 226 } 227 228 static int ecdsa_sign_setup(const EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 229 BIGNUM **rp, const uint8_t *digest, 230 size_t digest_len) { 231 BN_CTX *ctx = NULL; 232 BIGNUM *k = NULL, *r = NULL, *tmp = NULL; 233 EC_POINT *tmp_point = NULL; 234 const EC_GROUP *group; 235 int ret = 0; 236 237 if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) { 238 OPENSSL_PUT_ERROR(ECDSA, ERR_R_PASSED_NULL_PARAMETER); 239 return 0; 240 } 241 242 if (ctx_in == NULL) { 243 if ((ctx = BN_CTX_new()) == NULL) { 244 OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); 245 return 0; 246 } 247 } else { 248 ctx = ctx_in; 249 } 250 251 k = BN_new(); /* this value is later returned in *kinvp */ 252 r = BN_new(); /* this value is later returned in *rp */ 253 tmp = BN_new(); 254 if (k == NULL || r == NULL || tmp == NULL) { 255 OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); 256 goto err; 257 } 258 tmp_point = EC_POINT_new(group); 259 if (tmp_point == NULL) { 260 OPENSSL_PUT_ERROR(ECDSA, ERR_R_EC_LIB); 261 goto err; 262 } 263 264 const BIGNUM *order = EC_GROUP_get0_order(group); 265 266 do { 267 /* If possible, we'll include the private key and message digest in the k 268 * generation. The |digest| argument is only empty if |ECDSA_sign_setup| is 269 * being used. */ 270 if (digest_len > 0) { 271 do { 272 if (!BN_generate_dsa_nonce(k, order, EC_KEY_get0_private_key(eckey), 273 digest, digest_len, ctx)) { 274 OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED); 275 goto err; 276 } 277 } while (BN_is_zero(k)); 278 } else if (!BN_rand_range_ex(k, 1, order)) { 279 OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED); 280 goto err; 281 } 282 283 /* We do not want timing information to leak the length of k, 284 * so we compute G*k using an equivalent scalar of fixed 285 * bit-length. */ 286 287 if (!BN_add(k, k, order)) { 288 goto err; 289 } 290 if (BN_num_bits(k) <= BN_num_bits(order)) { 291 if (!BN_add(k, k, order)) { 292 goto err; 293 } 294 } 295 296 /* compute r the x-coordinate of generator * k */ 297 if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) { 298 OPENSSL_PUT_ERROR(ECDSA, ERR_R_EC_LIB); 299 goto err; 300 } 301 if (!EC_POINT_get_affine_coordinates_GFp(group, tmp_point, tmp, NULL, 302 ctx)) { 303 OPENSSL_PUT_ERROR(ECDSA, ERR_R_EC_LIB); 304 goto err; 305 } 306 307 if (!BN_nnmod(r, tmp, order, ctx)) { 308 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 309 goto err; 310 } 311 } while (BN_is_zero(r)); 312 313 /* Compute the inverse of k. The order is a prime, so use Fermat's Little 314 * Theorem. Note |ec_group_get_mont_data| may return NULL but 315 * |bn_mod_inverse_prime| allows this. */ 316 if (!bn_mod_inverse_prime(k, k, order, ctx, ec_group_get_mont_data(group))) { 317 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 318 goto err; 319 } 320 /* clear old values if necessary */ 321 BN_clear_free(*rp); 322 BN_clear_free(*kinvp); 323 324 /* save the pre-computed values */ 325 *rp = r; 326 *kinvp = k; 327 ret = 1; 328 329 err: 330 if (!ret) { 331 BN_clear_free(k); 332 BN_clear_free(r); 333 } 334 if (ctx_in == NULL) { 335 BN_CTX_free(ctx); 336 } 337 EC_POINT_free(tmp_point); 338 BN_clear_free(tmp); 339 return ret; 340 } 341 342 int ECDSA_sign_setup(const EC_KEY *eckey, BN_CTX *ctx, BIGNUM **kinv, 343 BIGNUM **rp) { 344 return ecdsa_sign_setup(eckey, ctx, kinv, rp, NULL, 0); 345 } 346 347 ECDSA_SIG *ECDSA_do_sign_ex(const uint8_t *digest, size_t digest_len, 348 const BIGNUM *in_kinv, const BIGNUM *in_r, 349 const EC_KEY *eckey) { 350 int ok = 0; 351 BIGNUM *kinv = NULL, *s, *m = NULL, *tmp = NULL; 352 const BIGNUM *ckinv; 353 BN_CTX *ctx = NULL; 354 const EC_GROUP *group; 355 ECDSA_SIG *ret; 356 const BIGNUM *priv_key; 357 358 if (eckey->ecdsa_meth && eckey->ecdsa_meth->sign) { 359 OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_NOT_IMPLEMENTED); 360 return NULL; 361 } 362 363 group = EC_KEY_get0_group(eckey); 364 priv_key = EC_KEY_get0_private_key(eckey); 365 366 if (group == NULL || priv_key == NULL) { 367 OPENSSL_PUT_ERROR(ECDSA, ERR_R_PASSED_NULL_PARAMETER); 368 return NULL; 369 } 370 371 ret = ECDSA_SIG_new(); 372 if (!ret) { 373 OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); 374 return NULL; 375 } 376 s = ret->s; 377 378 if ((ctx = BN_CTX_new()) == NULL || 379 (tmp = BN_new()) == NULL || 380 (m = BN_new()) == NULL) { 381 OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); 382 goto err; 383 } 384 385 const BIGNUM *order = EC_GROUP_get0_order(group); 386 387 if (!digest_to_bn(m, digest, digest_len, order)) { 388 goto err; 389 } 390 for (;;) { 391 if (in_kinv == NULL || in_r == NULL) { 392 if (!ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, digest, digest_len)) { 393 OPENSSL_PUT_ERROR(ECDSA, ERR_R_ECDSA_LIB); 394 goto err; 395 } 396 ckinv = kinv; 397 } else { 398 ckinv = in_kinv; 399 if (BN_copy(ret->r, in_r) == NULL) { 400 OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); 401 goto err; 402 } 403 } 404 405 if (!BN_mod_mul(tmp, priv_key, ret->r, order, ctx)) { 406 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 407 goto err; 408 } 409 if (!BN_mod_add_quick(s, tmp, m, order)) { 410 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 411 goto err; 412 } 413 if (!BN_mod_mul(s, s, ckinv, order, ctx)) { 414 OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB); 415 goto err; 416 } 417 if (BN_is_zero(s)) { 418 /* if kinv and r have been supplied by the caller 419 * don't to generate new kinv and r values */ 420 if (in_kinv != NULL && in_r != NULL) { 421 OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_NEED_NEW_SETUP_VALUES); 422 goto err; 423 } 424 } else { 425 /* s != 0 => we have a valid signature */ 426 break; 427 } 428 } 429 430 ok = 1; 431 432 err: 433 if (!ok) { 434 ECDSA_SIG_free(ret); 435 ret = NULL; 436 } 437 BN_CTX_free(ctx); 438 BN_clear_free(m); 439 BN_clear_free(tmp); 440 BN_clear_free(kinv); 441 return ret; 442 } 443 444 int ECDSA_sign_ex(int type, const uint8_t *digest, size_t digest_len, 445 uint8_t *sig, unsigned int *sig_len, const BIGNUM *kinv, 446 const BIGNUM *r, const EC_KEY *eckey) { 447 int ret = 0; 448 ECDSA_SIG *s = NULL; 449 450 if (eckey->ecdsa_meth && eckey->ecdsa_meth->sign) { 451 OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_NOT_IMPLEMENTED); 452 *sig_len = 0; 453 goto err; 454 } 455 456 s = ECDSA_do_sign_ex(digest, digest_len, kinv, r, eckey); 457 if (s == NULL) { 458 *sig_len = 0; 459 goto err; 460 } 461 462 CBB cbb; 463 CBB_zero(&cbb); 464 size_t len; 465 if (!CBB_init_fixed(&cbb, sig, ECDSA_size(eckey)) || 466 !ECDSA_SIG_marshal(&cbb, s) || 467 !CBB_finish(&cbb, NULL, &len)) { 468 OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_ENCODE_ERROR); 469 CBB_cleanup(&cbb); 470 *sig_len = 0; 471 goto err; 472 } 473 *sig_len = (unsigned)len; 474 ret = 1; 475 476 err: 477 ECDSA_SIG_free(s); 478 return ret; 479 } 480
