X-Git-Url: https://git.openssl.org/?a=blobdiff_plain;f=crypto%2Fbn%2Fbn_prime.c;h=81c2391ef898895d5da886bf6cc888b243670815;hb=d356dc561925ec9cecc58a69e2280c18a49ec41a;hp=b12295e84e4d55bc185999dcbd425425751dba0a;hpb=50e735f9e5d220cdad7db690188b82a69ddcb39e;p=openssl.git diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index b12295e84e..81c2391ef8 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -1,126 +1,20 @@ -/* 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 "cryptlib.h" +#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 * Zimmermann's, as implemented in PGP. I have had a read of his comments @@ -131,7 +25,7 @@ static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont); -static int probable_prime(BIGNUM *rnd, int bits); +static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods); static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); @@ -211,7 +105,8 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, BIGNUM *t; int found = 0; int i, j, c1 = 0; - BN_CTX *ctx; + BN_CTX *ctx = NULL; + prime_t *mods = NULL; int checks = BN_prime_checks_for_size(bits); if (bits < 2) { @@ -224,6 +119,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; @@ -234,7 +133,7 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, loop: /* make a random number and set the top and bottom bits */ if (add == NULL) { - if (!probable_prime(ret, bits)) + if (!probable_prime(ret, bits, mods)) goto err; } else { if (safe) { @@ -285,10 +184,10 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, /* we have a prime :-) */ found = 1; err: - if (ctx != NULL) { + OPENSSL_free(mods); + if (ctx != NULL) BN_CTX_end(ctx); - BN_CTX_free(ctx); - } + BN_CTX_free(ctx); bn_check_top(ret); return found; } @@ -397,8 +296,7 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, if (ctx_passed == NULL) BN_CTX_free(ctx); } - if (mont != NULL) - BN_MONT_CTX_free(mont); + BN_MONT_CTX_free(mont); return (ret); } @@ -442,7 +340,8 @@ 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)) @@ -452,8 +351,9 @@ int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx) 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. */ @@ -499,10 +399,9 @@ static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, return 1; } -static int probable_prime(BIGNUM *rnd, int bits) +static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods) { int i; - prime_t mods[NUMPRIMES]; BN_ULONG delta; BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; char is_single_word = bits <= BN_BITS2; @@ -518,7 +417,17 @@ static int probable_prime(BIGNUM *rnd, int bits) * additionally don't want to exceed that many bits. */ if (is_single_word) { - BN_ULONG size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1; + BN_ULONG size_limit; + + if (bits == BN_BITS2) { + /* + * Shifting by this much has undefined behaviour so we do it a + * different way + */ + size_limit = ~((BN_ULONG)0) - BN_get_word(rnd); + } else { + size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1; + } if (size_limit < maxdelta) maxdelta = size_limit; }