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@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@cryptsoft.com). This product includes software written by Tim 51 * Hudson (tjh@cryptsoft.com). */ 52 53#include <openssl/ecdsa.h> 54 55#include <openssl/bn.h> 56#include <openssl/err.h> 57#include <openssl/mem.h> 58#include <openssl/thread.h> 59 60#include "../ec/internal.h" 61 62 63int ECDSA_sign(int type, const uint8_t *digest, size_t digest_len, uint8_t *sig, 64 unsigned int *sig_len, EC_KEY *eckey) { 65 if (eckey->ecdsa_meth && eckey->ecdsa_meth->sign) { 66 return eckey->ecdsa_meth->sign(digest, digest_len, sig, sig_len, eckey); 67 } 68 69 return ECDSA_sign_ex(type, digest, digest_len, sig, sig_len, NULL, NULL, 70 eckey); 71} 72 73int ECDSA_verify(int type, const uint8_t *digest, size_t digest_len, 74 const uint8_t *sig, size_t sig_len, EC_KEY *eckey) { 75 ECDSA_SIG *s; 76 int ret = 0; 77 78 if (eckey->ecdsa_meth && eckey->ecdsa_meth->verify) { 79 return eckey->ecdsa_meth->verify(digest, digest_len, sig, sig_len, eckey); 80 } 81 82 s = ECDSA_SIG_new(); 83 if (s == NULL || d2i_ECDSA_SIG(&s, &sig, sig_len) == NULL) { 84 goto err; 85 } 86 ret = ECDSA_do_verify(digest, digest_len, s, eckey); 87 88err: 89 if (s != NULL) { 90 ECDSA_SIG_free(s); 91 } 92 return ret; 93} 94 95/* digest_to_bn interprets |digest_len| bytes from |digest| as a big-endian 96 * number and sets |out| to that value. It then truncates |out| so that it's, 97 * at most, as long as |order|. It returns one on success and zero otherwise. */ 98static int digest_to_bn(BIGNUM *out, const uint8_t *digest, size_t digest_len, 99 const BIGNUM *order) { 100 size_t num_bits; 101 102 num_bits = BN_num_bits(order); 103 /* Need to truncate digest if it is too long: first truncate whole 104 * bytes. */ 105 if (8 * digest_len > num_bits) { 106 digest_len = (num_bits + 7) / 8; 107 } 108 if (!BN_bin2bn(digest, digest_len, out)) { 109 OPENSSL_PUT_ERROR(ECDSA, digest_to_bn, ERR_R_BN_LIB); 110 return 0; 111 } 112 113 /* If still too long truncate remaining bits with a shift */ 114 if ((8 * digest_len > num_bits) && 115 !BN_rshift(out, out, 8 - (num_bits & 0x7))) { 116 OPENSSL_PUT_ERROR(ECDSA, digest_to_bn, ERR_R_BN_LIB); 117 return 0; 118 } 119 120 return 1; 121} 122 123ECDSA_SIG *ECDSA_do_sign(const uint8_t *digest, size_t digest_len, 124 EC_KEY *key) { 125 return ECDSA_do_sign_ex(digest, digest_len, NULL, NULL, key); 126} 127 128int ECDSA_do_verify(const uint8_t *digest, size_t digest_len, 129 const ECDSA_SIG *sig, EC_KEY *eckey) { 130 int ret = 0; 131 BN_CTX *ctx; 132 BIGNUM *order, *u1, *u2, *m, *X; 133 EC_POINT *point = NULL; 134 const EC_GROUP *group; 135 const EC_POINT *pub_key; 136 137 if (eckey->ecdsa_meth && eckey->ecdsa_meth->verify) { 138 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ECDSA_R_NOT_IMPLEMENTED); 139 return 0; 140 } 141 142 /* check input values */ 143 if ((group = EC_KEY_get0_group(eckey)) == NULL || 144 (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || 145 sig == NULL) { 146 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ECDSA_R_MISSING_PARAMETERS); 147 return 0; 148 } 149 150 ctx = BN_CTX_new(); 151 if (!ctx) { 152 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ERR_R_MALLOC_FAILURE); 153 return 0; 154 } 155 BN_CTX_start(ctx); 156 order = BN_CTX_get(ctx); 157 u1 = BN_CTX_get(ctx); 158 u2 = BN_CTX_get(ctx); 159 m = BN_CTX_get(ctx); 160 X = BN_CTX_get(ctx); 161 if (!X) { 162 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ERR_R_BN_LIB); 163 goto err; 164 } 165 166 if (!EC_GROUP_get_order(group, order, ctx)) { 167 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ERR_R_EC_LIB); 168 goto err; 169 } 170 171 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 172 BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) || 173 BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) { 174 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ECDSA_R_BAD_SIGNATURE); 175 ret = 0; /* signature is invalid */ 176 goto err; 177 } 178 /* calculate tmp1 = inv(S) mod order */ 179 if (!BN_mod_inverse(u2, sig->s, order, ctx)) { 180 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ERR_R_BN_LIB); 181 goto err; 182 } 183 if (!digest_to_bn(m, digest, digest_len, order)) { 184 goto err; 185 } 186 /* u1 = m * tmp mod order */ 187 if (!BN_mod_mul(u1, m, u2, order, ctx)) { 188 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ERR_R_BN_LIB); 189 goto err; 190 } 191 /* u2 = r * w mod q */ 192 if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) { 193 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ERR_R_BN_LIB); 194 goto err; 195 } 196 197 point = EC_POINT_new(group); 198 if (point == NULL) { 199 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ERR_R_MALLOC_FAILURE); 200 goto err; 201 } 202 if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) { 203 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ERR_R_EC_LIB); 204 goto err; 205 } 206 if (!EC_POINT_get_affine_coordinates_GFp(group, point, X, NULL, ctx)) { 207 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ERR_R_EC_LIB); 208 goto err; 209 } 210 if (!BN_nnmod(u1, X, order, ctx)) { 211 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_verify, ERR_R_BN_LIB); 212 goto err; 213 } 214 /* if the signature is correct u1 is equal to sig->r */ 215 ret = (BN_ucmp(u1, sig->r) == 0); 216 217err: 218 BN_CTX_end(ctx); 219 BN_CTX_free(ctx); 220 if (point) { 221 EC_POINT_free(point); 222 } 223 return ret; 224} 225 226static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 227 BIGNUM **rp, const uint8_t *digest, 228 size_t digest_len) { 229 BN_CTX *ctx = NULL; 230 BIGNUM *k = NULL, *r = NULL, *order = NULL, *X = NULL; 231 EC_POINT *tmp_point = NULL; 232 const EC_GROUP *group; 233 int ret = 0; 234 235 if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) { 236 OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_PASSED_NULL_PARAMETER); 237 return 0; 238 } 239 240 if (ctx_in == NULL) { 241 if ((ctx = BN_CTX_new()) == NULL) { 242 OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_MALLOC_FAILURE); 243 return 0; 244 } 245 } else { 246 ctx = ctx_in; 247 } 248 249 k = BN_new(); /* this value is later returned in *kinvp */ 250 r = BN_new(); /* this value is later returned in *rp */ 251 order = BN_new(); 252 X = BN_new(); 253 if (!k || !r || !order || !X) { 254 OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_MALLOC_FAILURE); 255 goto err; 256 } 257 tmp_point = EC_POINT_new(group); 258 if (tmp_point == NULL) { 259 OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_EC_LIB); 260 goto err; 261 } 262 if (!EC_GROUP_get_order(group, order, ctx)) { 263 OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_EC_LIB); 264 goto err; 265 } 266 267 do { 268 /* If possible, we'll include the private key and message digest in the k 269 * generation. The |digest| argument is only empty if |ECDSA_sign_setup| is 270 * being used. */ 271 do { 272 int ok; 273 274 if (digest_len > 0) { 275 ok = BN_generate_dsa_nonce(k, order, EC_KEY_get0_private_key(eckey), 276 digest, digest_len, ctx); 277 } else { 278 ok = BN_rand_range(k, order); 279 } 280 if (!ok) { 281 OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, 282 ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED); 283 goto err; 284 } 285 } while (BN_is_zero(k)); 286 287 /* We do not want timing information to leak the length of k, 288 * so we compute G*k using an equivalent scalar of fixed 289 * bit-length. */ 290 291 if (!BN_add(k, k, order)) { 292 goto err; 293 } 294 if (BN_num_bits(k) <= BN_num_bits(order)) { 295 if (!BN_add(k, k, order)) { 296 goto err; 297 } 298 } 299 300 /* compute r the x-coordinate of generator * k */ 301 if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) { 302 OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_EC_LIB); 303 goto err; 304 } 305 if (!EC_POINT_get_affine_coordinates_GFp(group, tmp_point, X, NULL, ctx)) { 306 OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_EC_LIB); 307 goto err; 308 } 309 310 if (!BN_nnmod(r, X, order, ctx)) { 311 OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB); 312 goto err; 313 } 314 } while (BN_is_zero(r)); 315 316 /* compute the inverse of k */ 317 if (!BN_mod_inverse(k, k, order, ctx)) { 318 OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB); 319 goto err; 320 } 321 /* clear old values if necessary */ 322 if (*rp != NULL) { 323 BN_clear_free(*rp); 324 } 325 if (*kinvp != NULL) { 326 BN_clear_free(*kinvp); 327 } 328 329 /* save the pre-computed values */ 330 *rp = r; 331 *kinvp = k; 332 ret = 1; 333 334err: 335 if (!ret) { 336 if (k != NULL) { 337 BN_clear_free(k); 338 } 339 if (r != NULL) { 340 BN_clear_free(r); 341 } 342 } 343 if (ctx_in == NULL) 344 BN_CTX_free(ctx); 345 if (order != NULL) 346 BN_free(order); 347 if (tmp_point != NULL) 348 EC_POINT_free(tmp_point); 349 if (X) 350 BN_clear_free(X); 351 return ret; 352} 353 354int ECDSA_sign_setup(EC_KEY *eckey, BN_CTX *ctx, BIGNUM **kinv, BIGNUM **rp) { 355 return ecdsa_sign_setup(eckey, ctx, kinv, rp, NULL, 0); 356} 357 358ECDSA_SIG *ECDSA_do_sign_ex(const uint8_t *digest, size_t digest_len, 359 const BIGNUM *in_kinv, const BIGNUM *in_r, 360 EC_KEY *eckey) { 361 int ok = 0; 362 BIGNUM *kinv = NULL, *s, *m = NULL, *tmp = NULL, *order = NULL; 363 const BIGNUM *ckinv; 364 BN_CTX *ctx = NULL; 365 const EC_GROUP *group; 366 ECDSA_SIG *ret; 367 const BIGNUM *priv_key; 368 369 if (eckey->ecdsa_meth && eckey->ecdsa_meth->sign) { 370 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ECDSA_R_NOT_IMPLEMENTED); 371 return NULL; 372 } 373 374 group = EC_KEY_get0_group(eckey); 375 priv_key = EC_KEY_get0_private_key(eckey); 376 377 if (group == NULL || priv_key == NULL) { 378 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ERR_R_PASSED_NULL_PARAMETER); 379 return NULL; 380 } 381 382 ret = ECDSA_SIG_new(); 383 if (!ret) { 384 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ERR_R_MALLOC_FAILURE); 385 return NULL; 386 } 387 s = ret->s; 388 389 if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL || 390 (tmp = BN_new()) == NULL || (m = BN_new()) == NULL) { 391 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ERR_R_MALLOC_FAILURE); 392 goto err; 393 } 394 395 if (!EC_GROUP_get_order(group, order, ctx)) { 396 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ERR_R_EC_LIB); 397 goto err; 398 } 399 if (!digest_to_bn(m, digest, digest_len, order)) { 400 goto err; 401 } 402 for (;;) { 403 if (in_kinv == NULL || in_r == NULL) { 404 if (!ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, digest, digest_len)) { 405 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ERR_R_ECDSA_LIB); 406 goto err; 407 } 408 ckinv = kinv; 409 } else { 410 ckinv = in_kinv; 411 if (BN_copy(ret->r, in_r) == NULL) { 412 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ERR_R_MALLOC_FAILURE); 413 goto err; 414 } 415 } 416 417 if (!BN_mod_mul(tmp, priv_key, ret->r, order, ctx)) { 418 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ERR_R_BN_LIB); 419 goto err; 420 } 421 if (!BN_mod_add_quick(s, tmp, m, order)) { 422 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ERR_R_BN_LIB); 423 goto err; 424 } 425 if (!BN_mod_mul(s, s, ckinv, order, ctx)) { 426 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ERR_R_BN_LIB); 427 goto err; 428 } 429 if (BN_is_zero(s)) { 430 /* if kinv and r have been supplied by the caller 431 * don't to generate new kinv and r values */ 432 if (in_kinv != NULL && in_r != NULL) { 433 OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ECDSA_R_NEED_NEW_SETUP_VALUES); 434 goto err; 435 } 436 } else { 437 /* s != 0 => we have a valid signature */ 438 break; 439 } 440 } 441 442 ok = 1; 443 444err: 445 if (!ok) { 446 ECDSA_SIG_free(ret); 447 ret = NULL; 448 } 449 if (ctx) 450 BN_CTX_free(ctx); 451 if (m) 452 BN_clear_free(m); 453 if (tmp) 454 BN_clear_free(tmp); 455 if (order) 456 BN_free(order); 457 if (kinv) 458 BN_clear_free(kinv); 459 return ret; 460} 461 462int ECDSA_sign_ex(int type, const uint8_t *digest, size_t digest_len, 463 uint8_t *sig, unsigned int *sig_len, const BIGNUM *kinv, 464 const BIGNUM *r, EC_KEY *eckey) { 465 ECDSA_SIG *s = NULL; 466 467 if (eckey->ecdsa_meth && eckey->ecdsa_meth->sign) { 468 OPENSSL_PUT_ERROR(ECDSA, ECDSA_sign_ex, ECDSA_R_NOT_IMPLEMENTED); 469 *sig_len = 0; 470 return 0; 471 } 472 473 s = ECDSA_do_sign_ex(digest, digest_len, kinv, r, eckey); 474 if (s == NULL) { 475 *sig_len = 0; 476 return 0; 477 } 478 *sig_len = i2d_ECDSA_SIG(s, &sig); 479 ECDSA_SIG_free(s); 480 return 1; 481} 482