summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_rand.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_rand.c')
-rw-r--r--src/lib/libcrypto/bn/bn_rand.c208
1 files changed, 98 insertions, 110 deletions
diff --git a/src/lib/libcrypto/bn/bn_rand.c b/src/lib/libcrypto/bn/bn_rand.c
index baa62d584c..488b7c6e63 100644
--- a/src/lib/libcrypto/bn/bn_rand.c
+++ b/src/lib/libcrypto/bn/bn_rand.c
@@ -5,21 +5,21 @@
5 * This package is an SSL implementation written 5 * This package is an SSL implementation written
6 * by Eric Young (eay@cryptsoft.com). 6 * by Eric Young (eay@cryptsoft.com).
7 * The implementation was written so as to conform with Netscapes SSL. 7 * The implementation was written so as to conform with Netscapes SSL.
8 * 8 *
9 * This library is free for commercial and non-commercial use as long as 9 * This library is free for commercial and non-commercial use as long as
10 * the following conditions are aheared to. The following conditions 10 * the following conditions are aheared to. The following conditions
11 * apply to all code found in this distribution, be it the RC4, RSA, 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 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 13 * included with this distribution is covered by the same copyright terms
14 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 14 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 * 15 *
16 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * Copyright remains Eric Young's, and as such any Copyright notices in
17 * the code are not to be removed. 17 * the code are not to be removed.
18 * If this package is used in a product, Eric Young should be given attribution 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. 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 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. 21 * in documentation (online or textual) provided with the package.
22 * 22 *
23 * Redistribution and use in source and binary forms, with or without 23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions 24 * modification, are permitted provided that the following conditions
25 * are met: 25 * are met:
@@ -34,10 +34,10 @@
34 * Eric Young (eay@cryptsoft.com)" 34 * Eric Young (eay@cryptsoft.com)"
35 * The word 'cryptographic' can be left out if the rouines from the library 35 * The word 'cryptographic' can be left out if the rouines from the library
36 * being used are not cryptographic related :-). 36 * being used are not cryptographic related :-).
37 * 4. If you include any Windows specific code (or a derivative thereof) from 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: 38 * the apps directory (application code) you must include an acknowledgement:
39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 * 40 *
41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
@@ -49,7 +49,7 @@
49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 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 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 * SUCH DAMAGE. 51 * SUCH DAMAGE.
52 * 52 *
53 * The licence and distribution terms for any publically available version or 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 54 * derivative of this code cannot be changed. i.e. this code cannot simply be
55 * copied and put under another distribution licence 55 * copied and put under another distribution licence
@@ -63,7 +63,7 @@
63 * are met: 63 * are met:
64 * 64 *
65 * 1. Redistributions of source code must retain the above copyright 65 * 1. Redistributions of source code must retain the above copyright
66 * notice, this list of conditions and the following disclaimer. 66 * notice, this list of conditions and the following disclaimer.
67 * 67 *
68 * 2. Redistributions in binary form must reproduce the above copyright 68 * 2. Redistributions in binary form must reproduce the above copyright
69 * notice, this list of conditions and the following disclaimer in 69 * notice, this list of conditions and the following disclaimer in
@@ -115,126 +115,117 @@
115#include "bn_lcl.h" 115#include "bn_lcl.h"
116#include <openssl/rand.h> 116#include <openssl/rand.h>
117 117
118static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom) 118static int
119 { 119bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
120 unsigned char *buf=NULL; 120{
121 int ret=0,bit,bytes,mask; 121 unsigned char *buf = NULL;
122 int ret = 0, bit, bytes, mask;
122 123
123 if (bits == 0) 124 if (bits == 0) {
124 {
125 BN_zero(rnd); 125 BN_zero(rnd);
126 return 1; 126 return 1;
127 } 127 }
128 128
129 bytes=(bits+7)/8; 129 bytes = (bits + 7) / 8;
130 bit=(bits-1)%8; 130 bit = (bits - 1) % 8;
131 mask=0xff<<(bit+1); 131 mask = 0xff << (bit + 1);
132 132
133 buf=(unsigned char *)malloc(bytes); 133 buf = (unsigned char *)malloc(bytes);
134 if (buf == NULL) 134 if (buf == NULL) {
135 { 135 BNerr(BN_F_BNRAND, ERR_R_MALLOC_FAILURE);
136 BNerr(BN_F_BNRAND,ERR_R_MALLOC_FAILURE);
137 goto err; 136 goto err;
138 } 137 }
139 138
140 /* make a random number and set the top and bottom bits */ 139 /* make a random number and set the top and bottom bits */
141 140
142 if (pseudorand) 141 if (pseudorand) {
143 {
144 if (RAND_pseudo_bytes(buf, bytes) == -1) 142 if (RAND_pseudo_bytes(buf, bytes) == -1)
145 goto err; 143 goto err;
146 } 144 } else {
147 else
148 {
149 if (RAND_bytes(buf, bytes) <= 0) 145 if (RAND_bytes(buf, bytes) <= 0)
150 goto err; 146 goto err;
151 } 147 }
152 148
153#if 1 149#if 1
154 if (pseudorand == 2) 150 if (pseudorand == 2) {
155 {
156 /* generate patterns that are more likely to trigger BN 151 /* generate patterns that are more likely to trigger BN
157 library bugs */ 152 library bugs */
158 int i; 153 int i;
159 unsigned char c; 154 unsigned char c;
160 155
161 for (i = 0; i < bytes; i++) 156 for (i = 0; i < bytes; i++) {
162 {
163 RAND_pseudo_bytes(&c, 1); 157 RAND_pseudo_bytes(&c, 1);
164 if (c >= 128 && i > 0) 158 if (c >= 128 && i > 0)
165 buf[i] = buf[i-1]; 159 buf[i] = buf[i - 1];
166 else if (c < 42) 160 else if (c < 42)
167 buf[i] = 0; 161 buf[i] = 0;
168 else if (c < 84) 162 else if (c < 84)
169 buf[i] = 255; 163 buf[i] = 255;
170 }
171 } 164 }
165 }
172#endif 166#endif
173 167
174 if (top != -1) 168 if (top != -1) {
175 { 169 if (top) {
176 if (top) 170 if (bit == 0) {
177 { 171 buf[0] = 1;
178 if (bit == 0) 172 buf[1] |= 0x80;
179 { 173 } else {
180 buf[0]=1; 174 buf[0] |= (3 << (bit - 1));
181 buf[1]|=0x80;
182 }
183 else
184 {
185 buf[0]|=(3<<(bit-1));
186 }
187 }
188 else
189 {
190 buf[0]|=(1<<bit);
191 } 175 }
176 } else {
177 buf[0] |= (1 << bit);
192 } 178 }
179 }
193 buf[0] &= ~mask; 180 buf[0] &= ~mask;
194 if (bottom) /* set bottom bit if requested */ 181 if (bottom) /* set bottom bit if requested */
195 buf[bytes-1]|=1; 182 buf[bytes - 1] |= 1;
196 if (!BN_bin2bn(buf,bytes,rnd)) goto err; 183 if (!BN_bin2bn(buf, bytes, rnd))
197 ret=1; 184 goto err;
185 ret = 1;
186
198err: 187err:
199 if (buf != NULL) 188 if (buf != NULL) {
200 { 189 OPENSSL_cleanse(buf, bytes);
201 OPENSSL_cleanse(buf,bytes);
202 free(buf); 190 free(buf);
203 }
204 bn_check_top(rnd);
205 return(ret);
206 } 191 }
192 bn_check_top(rnd);
193 return (ret);
194}
207 195
208int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) 196int
209 { 197BN_rand(BIGNUM *rnd, int bits, int top, int bottom)
198{
210 return bnrand(0, rnd, bits, top, bottom); 199 return bnrand(0, rnd, bits, top, bottom);
211 } 200}
212 201
213int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) 202int
214 { 203BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
204{
215 return bnrand(1, rnd, bits, top, bottom); 205 return bnrand(1, rnd, bits, top, bottom);
216 } 206}
217 207
218#if 1 208#if 1
219int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) 209int
220 { 210BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom)
211{
221 return bnrand(2, rnd, bits, top, bottom); 212 return bnrand(2, rnd, bits, top, bottom);
222 } 213}
223#endif 214#endif
224 215
225 216
226/* random number r: 0 <= r < range */ 217/* random number r: 0 <= r < range */
227static int bn_rand_range(int pseudo, BIGNUM *r, const BIGNUM *range) 218static int
228 { 219bn_rand_range(int pseudo, BIGNUM *r, const BIGNUM *range)
220{
229 int (*bn_rand)(BIGNUM *, int, int, int) = pseudo ? BN_pseudo_rand : BN_rand; 221 int (*bn_rand)(BIGNUM *, int, int, int) = pseudo ? BN_pseudo_rand : BN_rand;
230 int n; 222 int n;
231 int count = 100; 223 int count = 100;
232 224
233 if (range->neg || BN_is_zero(range)) 225 if (range->neg || BN_is_zero(range)) {
234 {
235 BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE); 226 BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);
236 return 0; 227 return 0;
237 } 228 }
238 229
239 n = BN_num_bits(range); /* n > 0 */ 230 n = BN_num_bits(range); /* n > 0 */
240 231
@@ -242,61 +233,58 @@ static int bn_rand_range(int pseudo, BIGNUM *r, const BIGNUM *range)
242 233
243 if (n == 1) 234 if (n == 1)
244 BN_zero(r); 235 BN_zero(r);
245 else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) 236 else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) {
246 {
247 /* range = 100..._2, 237 /* range = 100..._2,
248 * so 3*range (= 11..._2) is exactly one bit longer than range */ 238 * so 3*range (= 11..._2) is exactly one bit longer than range */
249 do 239 do {
250 { 240 if (!bn_rand(r, n + 1, -1, 0))
251 if (!bn_rand(r, n + 1, -1, 0)) return 0; 241 return 0;
252 /* If r < 3*range, use r := r MOD range 242 /* If r < 3*range, use r := r MOD range
253 * (which is either r, r - range, or r - 2*range). 243 * (which is either r, r - range, or r - 2*range).
254 * Otherwise, iterate once more. 244 * Otherwise, iterate once more.
255 * Since 3*range = 11..._2, each iteration succeeds with 245 * Since 3*range = 11..._2, each iteration succeeds with
256 * probability >= .75. */ 246 * probability >= .75. */
257 if (BN_cmp(r ,range) >= 0) 247 if (BN_cmp(r, range) >= 0) {
258 { 248 if (!BN_sub(r, r, range))
259 if (!BN_sub(r, r, range)) return 0; 249 return 0;
260 if (BN_cmp(r, range) >= 0) 250 if (BN_cmp(r, range) >= 0)
261 if (!BN_sub(r, r, range)) return 0; 251 if (!BN_sub(r, r, range))
262 } 252 return 0;
253 }
263 254
264 if (!--count) 255 if (!--count) {
265 { 256 BNerr(BN_F_BN_RAND_RANGE,
266 BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS); 257 BN_R_TOO_MANY_ITERATIONS);
267 return 0; 258 return 0;
268 }
269
270 } 259 }
271 while (BN_cmp(r, range) >= 0); 260
272 } 261 } while (BN_cmp(r, range) >= 0);
273 else 262 } else {
274 { 263 do {
275 do
276 {
277 /* range = 11..._2 or range = 101..._2 */ 264 /* range = 11..._2 or range = 101..._2 */
278 if (!bn_rand(r, n, -1, 0)) return 0; 265 if (!bn_rand(r, n, -1, 0))
266 return 0;
279 267
280 if (!--count) 268 if (!--count) {
281 { 269 BNerr(BN_F_BN_RAND_RANGE,
282 BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS); 270 BN_R_TOO_MANY_ITERATIONS);
283 return 0; 271 return 0;
284 }
285 } 272 }
286 while (BN_cmp(r, range) >= 0); 273 } while (BN_cmp(r, range) >= 0);
287 } 274 }
288 275
289 bn_check_top(r); 276 bn_check_top(r);
290 return 1; 277 return 1;
291 } 278}
292
293 279
294int BN_rand_range(BIGNUM *r, const BIGNUM *range) 280int
295 { 281BN_rand_range(BIGNUM *r, const BIGNUM *range)
282{
296 return bn_rand_range(0, r, range); 283 return bn_rand_range(0, r, range);
297 } 284}
298 285
299int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) 286int
300 { 287BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range)
288{
301 return bn_rand_range(1, r, range); 289 return bn_rand_range(1, r, range);
302 } 290}