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