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