Line data Source code
1 : /* crypto/bn/bn_rand.c */
2 : /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
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 : * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved.
60 : *
61 : * Redistribution and use in source and binary forms, with or without
62 : * modification, are permitted provided that the following conditions
63 : * are met:
64 : *
65 : * 1. Redistributions of source code must retain the above copyright
66 : * notice, this list of conditions and the following disclaimer.
67 : *
68 : * 2. Redistributions in binary form must reproduce the above copyright
69 : * notice, this list of conditions and the following disclaimer in
70 : * the documentation and/or other materials provided with the
71 : * distribution.
72 : *
73 : * 3. All advertising materials mentioning features or use of this
74 : * software must display the following acknowledgment:
75 : * "This product includes software developed by the OpenSSL Project
76 : * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
77 : *
78 : * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
79 : * endorse or promote products derived from this software without
80 : * prior written permission. For written permission, please contact
81 : * openssl-core@openssl.org.
82 : *
83 : * 5. Products derived from this software may not be called "OpenSSL"
84 : * nor may "OpenSSL" appear in their names without prior written
85 : * permission of the OpenSSL Project.
86 : *
87 : * 6. Redistributions of any form whatsoever must retain the following
88 : * acknowledgment:
89 : * "This product includes software developed by the OpenSSL Project
90 : * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
91 : *
92 : * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
93 : * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
94 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
95 : * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
96 : * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
97 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
98 : * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
99 : * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
100 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
101 : * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
102 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
103 : * OF THE POSSIBILITY OF SUCH DAMAGE.
104 : * ====================================================================
105 : *
106 : * This product includes cryptographic software written by Eric Young
107 : * (eay@cryptsoft.com). This product includes software written by Tim
108 : * Hudson (tjh@cryptsoft.com).
109 : *
110 : */
111 :
112 : #include <stdio.h>
113 : #include <time.h>
114 : #include "cryptlib.h"
115 : #include "bn_lcl.h"
116 : #include <openssl/rand.h>
117 :
118 2052 : static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
119 : {
120 : unsigned char *buf = NULL;
121 : int ret = 0, bit, bytes, mask;
122 : time_t tim;
123 :
124 2052 : if (bits < 0 || (bits == 1 && top > 0)) {
125 0 : BNerr(BN_F_BNRAND, BN_R_BITS_TOO_SMALL);
126 0 : return 0;
127 : }
128 :
129 2052 : if (bits == 0) {
130 0 : BN_zero(rnd);
131 0 : return 1;
132 : }
133 :
134 2052 : bytes = (bits + 7) / 8;
135 2052 : bit = (bits - 1) % 8;
136 2052 : mask = 0xff << (bit + 1);
137 :
138 2052 : buf = (unsigned char *)OPENSSL_malloc(bytes);
139 2052 : if (buf == NULL) {
140 0 : BNerr(BN_F_BNRAND, ERR_R_MALLOC_FAILURE);
141 0 : goto err;
142 : }
143 :
144 : /* make a random number and set the top and bottom bits */
145 2052 : time(&tim);
146 2052 : RAND_add(&tim, sizeof(tim), 0.0);
147 :
148 2052 : if (pseudorand) {
149 41 : if (RAND_pseudo_bytes(buf, bytes) == -1)
150 : goto err;
151 : } else {
152 2011 : if (RAND_bytes(buf, bytes) <= 0)
153 : goto err;
154 : }
155 :
156 : #if 1
157 2052 : if (pseudorand == 2) {
158 : /*
159 : * generate patterns that are more likely to trigger BN library bugs
160 : */
161 : int i;
162 : unsigned char c;
163 :
164 0 : for (i = 0; i < bytes; i++) {
165 0 : if (RAND_pseudo_bytes(&c, 1) < 0)
166 : goto err;
167 0 : if (c >= 128 && i > 0)
168 0 : buf[i] = buf[i - 1];
169 0 : else if (c < 42)
170 0 : buf[i] = 0;
171 0 : else if (c < 84)
172 0 : buf[i] = 255;
173 : }
174 : }
175 : #endif
176 :
177 2052 : if (top >= 0) {
178 0 : if (top) {
179 0 : if (bit == 0) {
180 0 : buf[0] = 1;
181 0 : buf[1] |= 0x80;
182 : } else {
183 0 : buf[0] |= (3 << (bit - 1));
184 : }
185 : } else {
186 0 : buf[0] |= (1 << bit);
187 : }
188 : }
189 2052 : buf[0] &= ~mask;
190 2052 : if (bottom) /* set bottom bit if requested */
191 0 : buf[bytes - 1] |= 1;
192 2052 : if (!BN_bin2bn(buf, bytes, rnd))
193 : goto err;
194 : ret = 1;
195 : err:
196 2052 : if (buf != NULL) {
197 2052 : OPENSSL_cleanse(buf, bytes);
198 2052 : OPENSSL_free(buf);
199 : }
200 : bn_check_top(rnd);
201 2052 : return (ret);
202 : }
203 :
204 2011 : int BN_rand(BIGNUM *rnd, int bits, int top, int bottom)
205 : {
206 2011 : return bnrand(0, rnd, bits, top, bottom);
207 : }
208 :
209 41 : int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
210 : {
211 41 : return bnrand(1, rnd, bits, top, bottom);
212 : }
213 :
214 : #if 1
215 0 : int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom)
216 : {
217 0 : return bnrand(2, rnd, bits, top, bottom);
218 : }
219 : #endif
220 :
221 : /* random number r: 0 <= r < range */
222 1996 : static int bn_rand_range(int pseudo, BIGNUM *r, const BIGNUM *range)
223 : {
224 : int (*bn_rand) (BIGNUM *, int, int, int) =
225 1996 : pseudo ? BN_pseudo_rand : BN_rand;
226 : int n;
227 : int count = 100;
228 :
229 1996 : if (range->neg || BN_is_zero(range)) {
230 0 : BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);
231 0 : return 0;
232 : }
233 :
234 1996 : n = BN_num_bits(range); /* n > 0 */
235 :
236 : /* BN_is_bit_set(range, n - 1) always holds */
237 :
238 1996 : if (n == 1)
239 0 : BN_zero(r);
240 1996 : else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) {
241 : /*
242 : * range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer
243 : * than range
244 : */
245 : do {
246 0 : if (!bn_rand(r, n + 1, -1, 0))
247 : return 0;
248 : /*
249 : * If r < 3*range, use r := r MOD range (which is either r, r -
250 : * range, or r - 2*range). Otherwise, iterate once more. Since
251 : * 3*range = 11..._2, each iteration succeeds with probability >=
252 : * .75.
253 : */
254 0 : if (BN_cmp(r, range) >= 0) {
255 0 : if (!BN_sub(r, r, range))
256 : return 0;
257 0 : if (BN_cmp(r, range) >= 0)
258 0 : if (!BN_sub(r, r, range))
259 : return 0;
260 : }
261 :
262 0 : if (!--count) {
263 0 : BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS);
264 0 : return 0;
265 : }
266 :
267 : }
268 0 : while (BN_cmp(r, range) >= 0);
269 : } else {
270 : do {
271 : /* range = 11..._2 or range = 101..._2 */
272 2052 : if (!bn_rand(r, n, -1, 0))
273 : return 0;
274 :
275 2052 : if (!--count) {
276 0 : BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS);
277 0 : return 0;
278 : }
279 : }
280 2052 : while (BN_cmp(r, range) >= 0);
281 : }
282 :
283 : bn_check_top(r);
284 : return 1;
285 : }
286 :
287 1960 : int BN_rand_range(BIGNUM *r, const BIGNUM *range)
288 : {
289 1960 : return bn_rand_range(0, r, range);
290 : }
291 :
292 36 : int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range)
293 : {
294 36 : return bn_rand_range(1, r, range);
295 : }
|
