[thirdparty/openssl.git] / crypto / bn / bn_rand.c

/* crypto/bn/bn_rand.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.]
 */

#include <stdio.h>
#include <time.h>
#include "cryptlib.h"
#include "bn_lcl.h"
#include <openssl/rand.h>

static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
	{
	unsigned char *buf=NULL;
	int ret=0,bit,bytes,mask;
	time_t tim;

	if (bits == 0)
		{
		BN_zero(rnd);
		return 1;
		}

	bytes=(bits+7)/8;
	bit=(bits-1)%8;
	mask=0xff<<bit;

	buf=(unsigned char *)OPENSSL_malloc(bytes);
	if (buf == NULL)
		{
		BNerr(BN_F_BN_RAND,ERR_R_MALLOC_FAILURE);
		goto err;
		}

	/* make a random number and set the top and bottom bits */
	time(&tim);
	RAND_add(&tim,sizeof(tim),0);

	if (pseudorand)
		{
		if (RAND_pseudo_bytes(buf, bytes) == -1)
			goto err;
		}
	else
		{
		if (RAND_bytes(buf, bytes) <= 0)
			goto err;
		}

#if 1
	if (pseudorand == 2)
		{
		/* generate patterns that are more likely to trigger BN
		   library bugs */
		int i;
		unsigned char c;

		for (i = 0; i < bytes; i++)
			{
			RAND_pseudo_bytes(&c, 1);
			if (c >= 128 && i > 0)
				buf[i] = buf[i-1];
			else if (c < 42)
				buf[i] = 0;
			else if (c < 84)
				buf[i] = 255;
			}
		}
#endif

	if (top)
		{
		if (bit == 0)
			{
			buf[0]=1;
			buf[1]|=0x80;
			}
		else
			{
			buf[0]|=(3<<(bit-1));
			buf[0]&= ~(mask<<1);
			}
		}
	else
		{
		buf[0]|=(1<<bit);
		buf[0]&= ~(mask<<1);
		}
	if (bottom) /* set bottom bits to whatever odd is */
		buf[bytes-1]|=1;
	if (!BN_bin2bn(buf,bytes,rnd)) goto err;
	ret=1;
err:
	if (buf != NULL)
		{
		memset(buf,0,bytes);
		OPENSSL_free(buf);
		}
	return(ret);
	}

int     BN_rand(BIGNUM *rnd, int bits, int top, int bottom)
	{
	return bnrand(0, rnd, bits, top, bottom);
	}

int     BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
	{
	return bnrand(1, rnd, bits, top, bottom);
	}

#if 1
int     BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom)
	{
	return bnrand(2, rnd, bits, top, bottom);
	}
#endif

/* random number r: min <= r < min+range */
int	BN_rand_range(BIGNUM *r, BIGNUM *min, BIGNUM *range)
	{
	int n;

	if (range->neg || BN_is_zero(range))
		{
		BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);
		return 0;
		}

	n = BN_num_bits(range); /* n > 0 */

	if (n == 1)
		{
		if (!BN_zero(r)) return 0;
		}
	else if (BN_is_bit_set(range, n - 2))
		{
		do
			{
			/* range = 11..._2, so each iteration succeeds with probability >= .75 */
			if (!BN_rand(r, n, 0, 0)) return 0;
			}
		while (BN_cmp(r, range) >= 0);
		}
	else
		{
		/* range = 10..._2,
		 * so  3*range (= 11..._2)  is exactly one bit longer than  range */
		do
			{
			if (!BN_rand(r, n + 1, 0, 0)) return 0;
			/* If  r < 3*range,  use  r := r MOD range
			 * (which is either  r, r - range,  or  r - 2*range).
			 * Otherwise, iterate once more.
			 * Since  3*range = 11..._2, each iteration succeeds with
			 * probability >= .75. */
			if (BN_cmp(r ,range) >= 0)
				{
				if (!BN_sub(r, r, range)) return 0;
				if (BN_cmp(r, range) >= 0)
					if (!BN_sub(r, r, range)) return 0;
				}
			}
		while (BN_cmp(r, range) >= 0);
		}

	if (min != NULL)
		{
		if (!BN_add(r, r, min)) return 0;
		}
	
	return 1;
	}
Commit	Line	Data
d02b48c6	1	/* crypto/bn/bn_rand.c */
58964a49	2	/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
d02b48c6 RE	3	* All rights reserved.
	4	*
	5	* This package is an SSL implementation written
	6	* by Eric Young (eay@cryptsoft.com).
	7	* The implementation was written so as to conform with Netscapes SSL.
	8	*
	9	* This library is free for commercial and non-commercial use as long as
	10	* the following conditions are aheared to. The following conditions
	11	* apply to all code found in this distribution, be it the RC4, RSA,
	12	* lhash, DES, etc., code; not just the SSL code. The SSL documentation
	13	* included with this distribution is covered by the same copyright terms
	14	* except that the holder is Tim Hudson (tjh@cryptsoft.com).
	15	*
	16	* Copyright remains Eric Young's, and as such any Copyright notices in
	17	* the code are not to be removed.
	18	* If this package is used in a product, Eric Young should be given attribution
	19	* as the author of the parts of the library used.
	20	* This can be in the form of a textual message at program startup or
	21	* in documentation (online or textual) provided with the package.
	22	*
	23	* Redistribution and use in source and binary forms, with or without
	24	* modification, are permitted provided that the following conditions
	25	* are met:
	26	* 1. Redistributions of source code must retain the copyright
	27	* notice, this list of conditions and the following disclaimer.
	28	* 2. Redistributions in binary form must reproduce the above copyright
	29	* notice, this list of conditions and the following disclaimer in the
	30	* documentation and/or other materials provided with the distribution.
	31	* 3. All advertising materials mentioning features or use of this software
	32	* must display the following acknowledgement:
	33	* "This product includes cryptographic software written by
	34	* Eric Young (eay@cryptsoft.com)"
	35	* The word 'cryptographic' can be left out if the rouines from the library
	36	* being used are not cryptographic related :-).
	37	* 4. If you include any Windows specific code (or a derivative thereof) from
	38	* the apps directory (application code) you must include an acknowledgement:
	39	* "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
	40	*
	41	* THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
	42	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	43	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	44	* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
	45	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	46	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	47	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	48	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	49	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	50	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	51	* SUCH DAMAGE.
	52	*
	53	* The licence and distribution terms for any publically available version or
	54	* derivative of this code cannot be changed. i.e. this code cannot simply be
	55	* copied and put under another distribution licence
	56	* [including the GNU Public Licence.]
	57	*/
	58
	59	#include <stdio.h>
	60	#include <time.h>
	61	#include "cryptlib.h"
	62	#include "bn_lcl.h"
ec577822	63	#include <openssl/rand.h>
d02b48c6	64
38e33cef	65	static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
d02b48c6 RE	66	{
	67	unsigned char *buf=NULL;
	68	int ret=0,bit,bytes,mask;
	69	time_t tim;
	70
904cb691 BM	71	if (bits == 0)
	72	{
	73	BN_zero(rnd);
	74	return 1;
	75	}
	76
d02b48c6 RE	77	bytes=(bits+7)/8;
	78	bit=(bits-1)%8;
	79	mask=0xff<<bit;
	80
26a3a48d	81	buf=(unsigned char *)OPENSSL_malloc(bytes);
d02b48c6 RE	82	if (buf == NULL)
	83	{
	84	BNerr(BN_F_BN_RAND,ERR_R_MALLOC_FAILURE);
	85	goto err;
	86	}
	87
	88	/* make a random number and set the top and bottom bits */
	89	time(&tim);
eb952088	90	RAND_add(&tim,sizeof(tim),0);
d02b48c6	91
38e33cef UM	92	if (pseudorand)
	93	{
	94	if (RAND_pseudo_bytes(buf, bytes) == -1)
	95	goto err;
	96	}
	97	else
	98	{
	99	if (RAND_bytes(buf, bytes) <= 0)
	100	goto err;
	101	}
	102
111482cf UM	103	#if 1
	104	if (pseudorand == 2)
	105	{
	106	/* generate patterns that are more likely to trigger BN
	107	library bugs */
	108	int i;
	109	unsigned char c;
	110
	111	for (i = 0; i < bytes; i++)
	112	{
	113	RAND_pseudo_bytes(&c, 1);
	114	if (c >= 128 && i > 0)
	115	buf[i] = buf[i-1];
	116	else if (c < 42)
	117	buf[i] = 0;
	118	else if (c < 84)
	119	buf[i] = 255;
	120	}
	121	}
	122	#endif
	123
d02b48c6 RE	124	if (top)
	125	{
	126	if (bit == 0)
	127	{
	128	buf[0]=1;
	129	buf[1]\|=0x80;
	130	}
	131	else
	132	{
	133	buf[0]\|=(3<<(bit-1));
	134	buf[0]&= ~(mask<<1);
	135	}
	136	}
	137	else
	138	{
	139	buf[0]\|=(1<<bit);
	140	buf[0]&= ~(mask<<1);
	141	}
	142	if (bottom) /* set bottom bits to whatever odd is */
	143	buf[bytes-1]\|=1;
	144	if (!BN_bin2bn(buf,bytes,rnd)) goto err;
	145	ret=1;
	146	err:
	147	if (buf != NULL)
	148	{
	149	memset(buf,0,bytes);
26a3a48d	150	OPENSSL_free(buf);
d02b48c6 RE	151	}
	152	return(ret);
	153	}
	154
38e33cef UM	155	int BN_rand(BIGNUM *rnd, int bits, int top, int bottom)
38e33cef UM	156	{
953aa790	157	return bnrand(0, rnd, bits, top, bottom);
38e33cef UM	158	}
	159
	160	int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
	161	{
953aa790	162	return bnrand(1, rnd, bits, top, bottom);
38e33cef	163	}
111482cf UM	164
	165	#if 1
	166	int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom)
	167	{
	168	return bnrand(2, rnd, bits, top, bottom);
	169	}
	170	#endif
57e7d3ce	171
35ed8cb8 BM	172	/* random number r: min <= r < min+range */
35ed8cb8 BM	173	int BN_rand_range(BIGNUM r, BIGNUM min, BIGNUM *range)
57e7d3ce	174	{
35ed8cb8 BM	175	int n;
	176
	177	if (range->neg \|\| BN_is_zero(range))
	178	{
	179	BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);
	180	return 0;
	181	}
	182
	183	n = BN_num_bits(range); /* n > 0 */
	184
	185	if (n == 1)
	186	{
	187	if (!BN_zero(r)) return 0;
	188	}
	189	else if (BN_is_bit_set(range, n - 2))
	190	{
	191	do
	192	{
792e2ce7	193	/* range = 11..._2, so each iteration succeeds with probability >= .75 */
35ed8cb8	194	if (!BN_rand(r, n, 0, 0)) return 0;
35ed8cb8 BM	195	}
35ed8cb8 BM	196	while (BN_cmp(r, range) >= 0);
35ed8cb8 BM	197	}
35ed8cb8 BM	198	else
57e7d3ce	199	{
35ed8cb8 BM	200	/* range = 10..._2,
	201	* so 3range (= 11..._2) is exactly one bit longer than range /
	202	do
	203	{
	204	if (!BN_rand(r, n + 1, 0, 0)) return 0;
	205	/* If r < 3*range, use r := r MOD range
	206	* (which is either r, r - range, or r - 2*range).
	207	* Otherwise, iterate once more.
	208	* Since 3*range = 11..._2, each iteration succeeds with
792e2ce7	209	* probability >= .75. */
35ed8cb8 BM	210	if (BN_cmp(r ,range) >= 0)
	211	{
	212	if (!BN_sub(r, r, range)) return 0;
	213	if (BN_cmp(r, range) >= 0)
	214	if (!BN_sub(r, r, range)) return 0;
	215	}
35ed8cb8 BM	216	}
35ed8cb8 BM	217	while (BN_cmp(r, range) >= 0);
35ed8cb8 BM	218	}
	219
	220	if (min != NULL)
	221	{
	222	if (!BN_add(r, r, min)) return 0;
	223	}
	224
57e7d3ce UM	225	return 1;
57e7d3ce UM	226	}