X-Git-Url: https://git.openssl.org/?p=openssl.git;a=blobdiff_plain;f=crypto%2Fbn%2Fbn_prime.c;h=7103acfe0bace910ebacc3f7501151c756ba9002;hp=42d574bb2ebd7740a403adfcad7cdc273ecc6f79;hb=78e09b53a40729f5e99829ccc733b592bd22fea1;hpb=8e704858f21983383be2b77e986f475b51719a1e diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index 42d574bb2e..7103acfe0b 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -1,125 +1,18 @@ -/* crypto/bn/bn_prime.c */ -/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) - * All rights reserved. - * - * This package is an SSL implementation written - * by Eric Young (eay@cryptsoft.com). - * The implementation was written so as to conform with Netscapes SSL. - * - * This library is free for commercial and non-commercial use as long as - * the following conditions are aheared to. The following conditions - * apply to all code found in this distribution, be it the RC4, RSA, - * lhash, DES, etc., code; not just the SSL code. The SSL documentation - * included with this distribution is covered by the same copyright terms - * except that the holder is Tim Hudson (tjh@cryptsoft.com). - * - * Copyright remains Eric Young's, and as such any Copyright notices in - * the code are not to be removed. - * If this package is used in a product, Eric Young should be given attribution - * as the author of the parts of the library used. - * This can be in the form of a textual message at program startup or - * in documentation (online or textual) provided with the package. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * "This product includes cryptographic software written by - * Eric Young (eay@cryptsoft.com)" - * The word 'cryptographic' can be left out if the rouines from the library - * being used are not cryptographic related :-). - * 4. If you include any Windows specific code (or a derivative thereof) from - * the apps directory (application code) you must include an acknowledgement: - * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" - * - * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * The licence and distribution terms for any publically available version or - * derivative of this code cannot be changed. i.e. this code cannot simply be - * copied and put under another distribution licence - * [including the GNU Public Licence.] - */ -/* ==================================================================== - * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in - * the documentation and/or other materials provided with the - * distribution. - * - * 3. All advertising materials mentioning features or use of this - * software must display the following acknowledgment: - * "This product includes software developed by the OpenSSL Project - * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" - * - * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to - * endorse or promote products derived from this software without - * prior written permission. For written permission, please contact - * openssl-core@openssl.org. - * - * 5. Products derived from this software may not be called "OpenSSL" - * nor may "OpenSSL" appear in their names without prior written - * permission of the OpenSSL Project. - * - * 6. Redistributions of any form whatsoever must retain the following - * acknowledgment: - * "This product includes software developed by the OpenSSL Project - * for use in the OpenSSL Toolkit (http://www.openssl.org/)" - * - * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY - * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR - * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, - * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED - * OF THE POSSIBILITY OF SUCH DAMAGE. - * ==================================================================== - * - * This product includes cryptographic software written by Eric Young - * (eay@cryptsoft.com). This product includes software written by Tim - * Hudson (tjh@cryptsoft.com). +/* + * WARNING: do not edit! + * Generated by crypto/bn/bn_prime.pl + * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. * + * Licensed under the OpenSSL license (the "License"). You may not use + * this file except in compliance with the License. You can obtain a copy + * in the file LICENSE in the source distribution or at + * https://www.openssl.org/source/license.html */ #include #include #include "internal/cryptlib.h" #include "bn_lcl.h" -#include - -/* - * NB: these functions have been "upgraded", the deprecated versions (which - * are compatibility wrappers using these functions) are in bn_depr.c. - - * Geoff - */ /* * The quick sieve algorithm approach to weeding out primes is Philip @@ -215,9 +108,6 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, prime_t *mods = NULL; int checks = BN_prime_checks_for_size(bits); - mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES); - if (mods == NULL) - goto err; if (bits < 2) { /* There are no prime numbers this small. */ BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); @@ -228,6 +118,10 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, return 0; } + mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES); + if (mods == NULL) + goto err; + ctx = BN_CTX_new(); if (ctx == NULL) goto err; @@ -249,7 +143,7 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, goto err; } } - /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */ + if (!BN_GENCB_call(cb, 0, c1++)) /* aborted */ goto err; @@ -324,9 +218,13 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, /* a is even => a is prime if and only if a == 2 */ return BN_is_word(a, 2); if (do_trial_division) { - for (i = 1; i < NUMPRIMES; i++) - if (BN_mod_word(a, primes[i]) == 0) + for (i = 1; i < NUMPRIMES; i++) { + BN_ULONG mod = BN_mod_word(a, primes[i]); + if (mod == (BN_ULONG)-1) + goto err; + if (mod == 0) return 0; + } if (!BN_GENCB_call(cb, 1, -1)) goto err; } @@ -342,7 +240,8 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BIGNUM *t; if ((t = BN_CTX_get(ctx)) == NULL) goto err; - BN_copy(t, a); + if (BN_copy(t, a) == NULL) + goto err; t->neg = 0; A = t; } else @@ -412,14 +311,17 @@ int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx) int ret = 0; loop: - if (!BN_rand(rnd, bits, 0, 1)) + if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) goto err; /* we now have a random number 'rand' to test. */ for (i = 1; i < NUMPRIMES; i++) { /* check that rnd is a prime */ - if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) { + BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); + if (mod == (BN_ULONG)-1) + goto err; + if (mod <= 1) { goto loop; } } @@ -445,27 +347,32 @@ int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx) if ((offset_count = BN_CTX_get(ctx)) == NULL) goto err; - BN_add_word(offset_count, prime_offset_count); + if (!BN_add_word(offset_count, prime_offset_count)) + goto err; loop: - if (!BN_rand(rnd, bits - prime_multiplier_bits, 0, 1)) + if (!BN_rand(rnd, bits - prime_multiplier_bits, + BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) goto err; if (BN_is_bit_set(rnd, bits)) goto loop; if (!BN_rand_range(offset_index, offset_count)) goto err; - BN_mul_word(rnd, prime_multiplier); - BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]); + if (!BN_mul_word(rnd, prime_multiplier) + || !BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)])) + goto err; /* we now have a random number 'rand' to test. */ /* skip coprimes */ for (i = first_prime_index; i < NUMPRIMES; i++) { /* check that rnd is a prime */ - if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) { + BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); + if (mod == (BN_ULONG)-1) + goto err; + if (mod <= 1) goto loop; - } } ret = 1; @@ -510,18 +417,22 @@ static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods) char is_single_word = bits <= BN_BITS2; again: - if (!BN_rand(rnd, bits, 1, 1)) + if (!BN_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) return (0); /* we now have a random number 'rnd' to test. */ - for (i = 1; i < NUMPRIMES; i++) - mods[i] = (prime_t) BN_mod_word(rnd, (BN_ULONG)primes[i]); + for (i = 1; i < NUMPRIMES; i++) { + BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); + if (mod == (BN_ULONG)-1) + return 0; + mods[i] = (prime_t) mod; + } /* * If bits is so small that it fits into a single word then we * additionally don't want to exceed that many bits. */ if (is_single_word) { BN_ULONG size_limit; - + if (bits == BN_BITS2) { /* * Shifting by this much has undefined behaviour so we do it a @@ -590,7 +501,7 @@ int bn_probable_prime_dh(BIGNUM *rnd, int bits, if ((t1 = BN_CTX_get(ctx)) == NULL) goto err; - if (!BN_rand(rnd, bits, 0, 1)) + if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) goto err; /* we need ((rnd-rem) % add) == 0 */ @@ -612,7 +523,10 @@ int bn_probable_prime_dh(BIGNUM *rnd, int bits, loop: for (i = 1; i < NUMPRIMES; i++) { /* check that rnd is a prime */ - if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) { + BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); + if (mod == (BN_ULONG)-1) + goto err; + if (mod <= 1) { if (!BN_add(rnd, rnd, add)) goto err; goto loop; @@ -643,7 +557,7 @@ static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, if (!BN_rshift1(qadd, padd)) goto err; - if (!BN_rand(q, bits, 0, 1)) + if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) goto err; /* we need ((rnd-rem) % add) == 0 */ @@ -673,8 +587,11 @@ static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, /* * check that for p and q gcd(p-1,primes) == 1 (except for 2) */ - if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) || - (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) { + BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]); + BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]); + if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1) + goto err; + if (pmod == 0 || qmod == 0) { if (!BN_add(p, p, padd)) goto err; if (!BN_add(q, q, qadd))