This should avoid half of the trial divisions in probable_prime_dh_safe
and avoid bn_probable_prime_dh generating primes with special properties.
Reviewed-by: NTomas Mraz <tmraz@fedoraproject.org>
(Merged from https://github.com/openssl/openssl/pull/9387)

Currently probable_prime makes sure that p-1 does not have
any prime factors from 3..17863, which is useful for safe primes,
but not necessarily for the general case.

Issue was initially reported here:
MIRONOV, I. Factoring RSA Moduli II.
https://windowsontheory.org/2012/05/17/factoring-rsa-moduli-part-ii/Reviewed-by: NTomas Mraz <tmraz@fedoraproject.org>
(Merged from https://github.com/openssl/openssl/pull/9387)

Apart from public and internal header files, there is a third type called
local header files, which are located next to source files in the source
directory. Currently, they have different suffixes like

  '*_lcl.h', '*_local.h', or '*_int.h'

This commit changes the different suffixes to '*_local.h' uniformly.
Reviewed-by: NRichard Levitte <levitte@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/9681)

Happens when trying to generate 4 or 5 bit safe primes.

[extended tests]
Reviewed-by: NPaul Dale <paul.dale@oracle.com>
(Merged from https://github.com/openssl/openssl/pull/9311)

(cherry picked from commit 291f616ced45c924d639d97fc9ca2cbeaad096cf)

Reviewed-by: NMatt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/9034)

Reviewed-by: NPaul Dale <paul.dale@oracle.com>
Reviewed-by: NRichard Levitte <levitte@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/8518)

(cherry picked from commit ce1415ed2ce15305356cd028bcf7b9bc688d6d5c)

Fixed range of random produced in BN_is_prime_fasttest_ex() to be 1 < rand < w-1. It was using 1<= rand < w (which is wrong by 1 on both ends)
Reviewed-by: NPaul Dale <paul.dale@oracle.com>
Reviewed-by: NRich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6547)

Reviewed-by: NRichard Levitte <levitte@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/5851)

Reviewed-by: NDr. Matthias St. Pierre <Matthias.St.Pierre@ncp-e.com>
Reviewed-by: NRich Salz <rsalz@openssl.org>

Fixes: #4641
GH: #4665

Since return is inconsistent, I removed unnecessary parentheses and
unified them.
Reviewed-by: NRich Salz <rsalz@openssl.org>
Reviewed-by: NMatt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/4541)

unified them.
- return (0); -> return 0;
- return (1); -> return 1;
- return (-1); -> return -1;
Reviewed-by: NStephen Henson <steve@openssl.org>
Reviewed-by: NMatt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/4500)

Add a new global DRBG for private keys used by RAND_priv_bytes.

Add BN_priv_rand() and BN_priv_rand_range() which use RAND_priv_bytes().
Change callers to use the appropriate BN_priv... function.
Reviewed-by: NPaul Dale <paul.dale@oracle.com>
(Merged from https://github.com/openssl/openssl/pull/4076)

And BN_pseudo_rand_range is really BN_rand_range.
Document that we might deprecate those functions.
Reviewed-by: NMatt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/3743)

As well as a coding style nit is fixed.
Reviewed-by: NRich Salz <rsalz@openssl.org>
Reviewed-by: NBernd Edlinger <bernd.edlinger@hotmail.de>
(Merged from https://github.com/openssl/openssl/pull/3763)

BN_is_prime_fasttest_ex begins by rejecting if a <= 1. Then it goes to
set A := abs(a), but a cannot be negative at this point.
Reviewed-by: NRichard Levitte <levitte@openssl.org>
Reviewed-by: NRich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/3275)

Previously, BN_is_prime_fasttest_ex, when doing trial-division, would
check whether the candidate is a multiple of a number of small primes
and, if so, reject it. However, three is a multiple of three yet is
still a prime number.

This change accepts small primes as prime when doing trial-division.
Reviewed-by: NKurt Roeckx <kurt@openssl.org>
Reviewed-by: NRich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/3264)

There are a number of symbols in bn which are internal only and never used
by anything. They should be removed.
Reviewed-by: NRich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/2766)

Factorise multiple bn_get_top(group->field) calls
Add missing checks on some conditional BN_copy return value
Add missing checks on some BN_copy return value
Add missing checks on a few bn_wexpand return value
Reviewed-by: NRichard Levitte <levitte@openssl.org>
Reviewed-by: NRich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/1626)

Reviewed-by: NMatt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/1429)

Reviewed-by: NAndy Polyakov <appro@openssl.org>
Reviewed-by: NKurt Roeckx <kurt@openssl.org>
Reviewed-by: NRich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/1264)

As of 37258dad and the corresponding upstream
change, BN_mod_word may fail, like BN_div_word. Handle this properly. Thanks to
Brian Smith for pointing this out. See BoringSSL's
44bedc348d9491e63c7ed1438db100a4b8a830be.
Signed-off-by: NKurt Roeckx <kurt@roeckx.be>
Reviewed-by: NRich Salz <rsalz@openssl.org>

GH: #1251

Reviewed-by: NKurt Roeckx <kurt@openssl.org>
Reviewed-by: NRich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/1168)

Some misc return value checks
Reviewed-by: NRich Salz <rsalz@openssl.org>

Reviewed-by: NRichard Levitte <levitte@openssl.org>

In BN_generate_prime_ex() we do some sanity checks first and return
with an error if they fail. We should do that *before* allocating any
resources to avoid a memory leak.
Reviewed-by: NRichard Levitte <levitte@openssl.org>

This fixes clang compilation problem with size_t NUMPRIMES and int
loop counters.
Reviewed-by: NRich Salz <rsalz@openssl.org>

Also cleaned up bn_prime.pl to current coding style.
Reviewed-by: NAndy Polyakov <appro@openssl.org>

This was done by the following
        find . -name '*.[ch]' | /tmp/pl
where /tmp/pl is the following three-line script:
        print unless $. == 1 && m@/\* .*\.[ch] \*/@;
        close ARGV if eof; # Close file to reset $.

And then some hand-editing of other files.
Reviewed-by: NViktor Dukhovni <viktor@openssl.org>

Use malloc/free instead of big onstack buffers.
Reviewed-by: NTim Hudson <tjh@openssl.org>

There are header files in crypto/ that are used by a number of crypto/
submodules.  Move those to crypto/include/internal and adapt the
affected source code and Makefiles.

The header files that got moved are:

crypto/cryptolib.h
crypto/md32_common.h
Reviewed-by: NRich Salz <rsalz@openssl.org>

This gets BN_.*free:
    BN_BLINDING_free BN_CTX_free BN_FLG_FREE BN_GENCB_free
    BN_MONT_CTX_free BN_RECP_CTX_free BN_clear_free BN_free BUF_MEM_free

Also fix a call to DSA_SIG_free to ccgost engine and remove some #ifdef'd
dead code in engines/e_ubsec.
Reviewed-by: NRichard Levitte <levitte@openssl.org>

In the probable_prime() function we behave slightly different if the number
of bits we are interested in is <= BN_BITS2 (the num of bits in a BN_ULONG).
As part of the calculation we work out a size_limit as follows:

    size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;

There is a problem though if bits == BN_BITS2. Shifting by that much causes
undefined behaviour. I did some tests. On my system BN_BITS2 == 64. So I
set bits to 64 and calculated the result of:

    (((BN_ULONG)1) << bits)

I was expecting to get the result 0. I actually got 1! Strangely this...

    (((BN_ULONG)0) << BN_BITS2)

...does equal 0! This means that, on my system at least, size_limit will be
off by 1 when bits == BN_BITS2.

This commit fixes the behaviour so that we always get consistent results.
Reviewed-by: NAndy Polyakov <appro@openssl.org>

This should be a one off operation (subsequent invokation of the
script should not move them)
Reviewed-by: NTim Hudson <tjh@openssl.org>

Reviewed-by: NTim Hudson <tjh@openssl.org>

indent will not alter them when reformatting comments
Reviewed-by: NRich Salz <rsalz@openssl.org>
Reviewed-by: NMatt Caswell <matt@openssl.org>