1*de0e0e4dSAntonio Huete Jimenez /* $OpenBSD: bn_rand.c,v 1.25 2021/08/31 11:19:19 tb Exp $ */
2f5b1c8a1SJohn Marino /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3f5b1c8a1SJohn Marino * All rights reserved.
4f5b1c8a1SJohn Marino *
5f5b1c8a1SJohn Marino * This package is an SSL implementation written
6f5b1c8a1SJohn Marino * by Eric Young (eay@cryptsoft.com).
7f5b1c8a1SJohn Marino * The implementation was written so as to conform with Netscapes SSL.
8f5b1c8a1SJohn Marino *
9f5b1c8a1SJohn Marino * This library is free for commercial and non-commercial use as long as
10f5b1c8a1SJohn Marino * the following conditions are aheared to. The following conditions
11f5b1c8a1SJohn Marino * apply to all code found in this distribution, be it the RC4, RSA,
12f5b1c8a1SJohn Marino * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13f5b1c8a1SJohn Marino * included with this distribution is covered by the same copyright terms
14f5b1c8a1SJohn Marino * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15f5b1c8a1SJohn Marino *
16f5b1c8a1SJohn Marino * Copyright remains Eric Young's, and as such any Copyright notices in
17f5b1c8a1SJohn Marino * the code are not to be removed.
18f5b1c8a1SJohn Marino * If this package is used in a product, Eric Young should be given attribution
19f5b1c8a1SJohn Marino * as the author of the parts of the library used.
20f5b1c8a1SJohn Marino * This can be in the form of a textual message at program startup or
21f5b1c8a1SJohn Marino * in documentation (online or textual) provided with the package.
22f5b1c8a1SJohn Marino *
23f5b1c8a1SJohn Marino * Redistribution and use in source and binary forms, with or without
24f5b1c8a1SJohn Marino * modification, are permitted provided that the following conditions
25f5b1c8a1SJohn Marino * are met:
26f5b1c8a1SJohn Marino * 1. Redistributions of source code must retain the copyright
27f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer.
28f5b1c8a1SJohn Marino * 2. Redistributions in binary form must reproduce the above copyright
29f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer in the
30f5b1c8a1SJohn Marino * documentation and/or other materials provided with the distribution.
31f5b1c8a1SJohn Marino * 3. All advertising materials mentioning features or use of this software
32f5b1c8a1SJohn Marino * must display the following acknowledgement:
33f5b1c8a1SJohn Marino * "This product includes cryptographic software written by
34f5b1c8a1SJohn Marino * Eric Young (eay@cryptsoft.com)"
35f5b1c8a1SJohn Marino * The word 'cryptographic' can be left out if the rouines from the library
36f5b1c8a1SJohn Marino * being used are not cryptographic related :-).
37f5b1c8a1SJohn Marino * 4. If you include any Windows specific code (or a derivative thereof) from
38f5b1c8a1SJohn Marino * the apps directory (application code) you must include an acknowledgement:
39f5b1c8a1SJohn Marino * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40f5b1c8a1SJohn Marino *
41f5b1c8a1SJohn Marino * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42f5b1c8a1SJohn Marino * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43f5b1c8a1SJohn Marino * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44f5b1c8a1SJohn Marino * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45f5b1c8a1SJohn Marino * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46f5b1c8a1SJohn Marino * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47f5b1c8a1SJohn Marino * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48f5b1c8a1SJohn Marino * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49f5b1c8a1SJohn Marino * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50f5b1c8a1SJohn Marino * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51f5b1c8a1SJohn Marino * SUCH DAMAGE.
52f5b1c8a1SJohn Marino *
53f5b1c8a1SJohn Marino * The licence and distribution terms for any publically available version or
54f5b1c8a1SJohn Marino * derivative of this code cannot be changed. i.e. this code cannot simply be
55f5b1c8a1SJohn Marino * copied and put under another distribution licence
56f5b1c8a1SJohn Marino * [including the GNU Public Licence.]
57f5b1c8a1SJohn Marino */
58f5b1c8a1SJohn Marino /* ====================================================================
59f5b1c8a1SJohn Marino * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved.
60f5b1c8a1SJohn Marino *
61f5b1c8a1SJohn Marino * Redistribution and use in source and binary forms, with or without
62f5b1c8a1SJohn Marino * modification, are permitted provided that the following conditions
63f5b1c8a1SJohn Marino * are met:
64f5b1c8a1SJohn Marino *
65f5b1c8a1SJohn Marino * 1. Redistributions of source code must retain the above copyright
66f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer.
67f5b1c8a1SJohn Marino *
68f5b1c8a1SJohn Marino * 2. Redistributions in binary form must reproduce the above copyright
69f5b1c8a1SJohn Marino * notice, this list of conditions and the following disclaimer in
70f5b1c8a1SJohn Marino * the documentation and/or other materials provided with the
71f5b1c8a1SJohn Marino * distribution.
72f5b1c8a1SJohn Marino *
73f5b1c8a1SJohn Marino * 3. All advertising materials mentioning features or use of this
74f5b1c8a1SJohn Marino * software must display the following acknowledgment:
75f5b1c8a1SJohn Marino * "This product includes software developed by the OpenSSL Project
76f5b1c8a1SJohn Marino * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
77f5b1c8a1SJohn Marino *
78f5b1c8a1SJohn Marino * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
79f5b1c8a1SJohn Marino * endorse or promote products derived from this software without
80f5b1c8a1SJohn Marino * prior written permission. For written permission, please contact
81f5b1c8a1SJohn Marino * openssl-core@openssl.org.
82f5b1c8a1SJohn Marino *
83f5b1c8a1SJohn Marino * 5. Products derived from this software may not be called "OpenSSL"
84f5b1c8a1SJohn Marino * nor may "OpenSSL" appear in their names without prior written
85f5b1c8a1SJohn Marino * permission of the OpenSSL Project.
86f5b1c8a1SJohn Marino *
87f5b1c8a1SJohn Marino * 6. Redistributions of any form whatsoever must retain the following
88f5b1c8a1SJohn Marino * acknowledgment:
89f5b1c8a1SJohn Marino * "This product includes software developed by the OpenSSL Project
90f5b1c8a1SJohn Marino * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
91f5b1c8a1SJohn Marino *
92f5b1c8a1SJohn Marino * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
93f5b1c8a1SJohn Marino * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
94f5b1c8a1SJohn Marino * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
95f5b1c8a1SJohn Marino * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
96f5b1c8a1SJohn Marino * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
97f5b1c8a1SJohn Marino * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
98f5b1c8a1SJohn Marino * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
99f5b1c8a1SJohn Marino * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
100f5b1c8a1SJohn Marino * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
101f5b1c8a1SJohn Marino * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
102f5b1c8a1SJohn Marino * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
103f5b1c8a1SJohn Marino * OF THE POSSIBILITY OF SUCH DAMAGE.
104f5b1c8a1SJohn Marino * ====================================================================
105f5b1c8a1SJohn Marino *
106f5b1c8a1SJohn Marino * This product includes cryptographic software written by Eric Young
107f5b1c8a1SJohn Marino * (eay@cryptsoft.com). This product includes software written by Tim
108f5b1c8a1SJohn Marino * Hudson (tjh@cryptsoft.com).
109f5b1c8a1SJohn Marino *
110f5b1c8a1SJohn Marino */
111f5b1c8a1SJohn Marino
112f5b1c8a1SJohn Marino #include <stdio.h>
113f5b1c8a1SJohn Marino #include <stdlib.h>
114f5b1c8a1SJohn Marino #include <string.h>
115f5b1c8a1SJohn Marino #include <time.h>
116f5b1c8a1SJohn Marino
117f5b1c8a1SJohn Marino #include <openssl/err.h>
118f5b1c8a1SJohn Marino
119f5b1c8a1SJohn Marino #include "bn_lcl.h"
120f5b1c8a1SJohn Marino
121f5b1c8a1SJohn Marino static int
bnrand(int pseudorand,BIGNUM * rnd,int bits,int top,int bottom)122f5b1c8a1SJohn Marino bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
123f5b1c8a1SJohn Marino {
124f5b1c8a1SJohn Marino unsigned char *buf = NULL;
125f5b1c8a1SJohn Marino int ret = 0, bit, bytes, mask;
126f5b1c8a1SJohn Marino
127f5b1c8a1SJohn Marino if (rnd == NULL) {
12872c33676SMaxim Ag BNerror(ERR_R_PASSED_NULL_PARAMETER);
129f5b1c8a1SJohn Marino return (0);
130f5b1c8a1SJohn Marino }
131f5b1c8a1SJohn Marino
1328edacedfSDaniel Fojt if (bits < 0 || (bits == 1 && top > 0)) {
1338edacedfSDaniel Fojt BNerror(BN_R_BITS_TOO_SMALL);
1348edacedfSDaniel Fojt return (0);
1358edacedfSDaniel Fojt }
1368edacedfSDaniel Fojt
137f5b1c8a1SJohn Marino if (bits == 0) {
138f5b1c8a1SJohn Marino BN_zero(rnd);
139f5b1c8a1SJohn Marino return (1);
140f5b1c8a1SJohn Marino }
141f5b1c8a1SJohn Marino
142f5b1c8a1SJohn Marino bytes = (bits + 7) / 8;
143f5b1c8a1SJohn Marino bit = (bits - 1) % 8;
144f5b1c8a1SJohn Marino mask = 0xff << (bit + 1);
145f5b1c8a1SJohn Marino
146f5b1c8a1SJohn Marino buf = malloc(bytes);
147f5b1c8a1SJohn Marino if (buf == NULL) {
14872c33676SMaxim Ag BNerror(ERR_R_MALLOC_FAILURE);
149f5b1c8a1SJohn Marino goto err;
150f5b1c8a1SJohn Marino }
151f5b1c8a1SJohn Marino
152f5b1c8a1SJohn Marino /* make a random number and set the top and bottom bits */
153f5b1c8a1SJohn Marino arc4random_buf(buf, bytes);
154f5b1c8a1SJohn Marino
155f5b1c8a1SJohn Marino #if 1
156f5b1c8a1SJohn Marino if (pseudorand == 2) {
157f5b1c8a1SJohn Marino /* generate patterns that are more likely to trigger BN
158f5b1c8a1SJohn Marino library bugs */
159f5b1c8a1SJohn Marino int i;
160f5b1c8a1SJohn Marino unsigned char c;
161f5b1c8a1SJohn Marino
162f5b1c8a1SJohn Marino for (i = 0; i < bytes; i++) {
163f5b1c8a1SJohn Marino arc4random_buf(&c, 1);
164f5b1c8a1SJohn Marino if (c >= 128 && i > 0)
165f5b1c8a1SJohn Marino buf[i] = buf[i - 1];
166f5b1c8a1SJohn Marino else if (c < 42)
167f5b1c8a1SJohn Marino buf[i] = 0;
168f5b1c8a1SJohn Marino else if (c < 84)
169f5b1c8a1SJohn Marino buf[i] = 255;
170f5b1c8a1SJohn Marino }
171f5b1c8a1SJohn Marino }
172f5b1c8a1SJohn Marino #endif
173f5b1c8a1SJohn Marino
1748edacedfSDaniel Fojt if (top > 0) {
175f5b1c8a1SJohn Marino if (bit == 0) {
176f5b1c8a1SJohn Marino buf[0] = 1;
177f5b1c8a1SJohn Marino buf[1] |= 0x80;
178f5b1c8a1SJohn Marino } else {
179f5b1c8a1SJohn Marino buf[0] |= (3 << (bit - 1));
180f5b1c8a1SJohn Marino }
1818edacedfSDaniel Fojt }
1828edacedfSDaniel Fojt if (top == 0)
183f5b1c8a1SJohn Marino buf[0] |= (1 << bit);
184f5b1c8a1SJohn Marino buf[0] &= ~mask;
185f5b1c8a1SJohn Marino if (bottom) /* set bottom bit if requested */
186f5b1c8a1SJohn Marino buf[bytes - 1] |= 1;
187f5b1c8a1SJohn Marino if (BN_bin2bn(buf, bytes, rnd) == NULL)
188f5b1c8a1SJohn Marino goto err;
189f5b1c8a1SJohn Marino ret = 1;
190f5b1c8a1SJohn Marino
191f5b1c8a1SJohn Marino err:
19272c33676SMaxim Ag freezero(buf, bytes);
193f5b1c8a1SJohn Marino bn_check_top(rnd);
194f5b1c8a1SJohn Marino return (ret);
195f5b1c8a1SJohn Marino }
196f5b1c8a1SJohn Marino
197f5b1c8a1SJohn Marino int
BN_rand(BIGNUM * rnd,int bits,int top,int bottom)198f5b1c8a1SJohn Marino BN_rand(BIGNUM *rnd, int bits, int top, int bottom)
199f5b1c8a1SJohn Marino {
200f5b1c8a1SJohn Marino return bnrand(0, rnd, bits, top, bottom);
201f5b1c8a1SJohn Marino }
202f5b1c8a1SJohn Marino
203f5b1c8a1SJohn Marino int
BN_pseudo_rand(BIGNUM * rnd,int bits,int top,int bottom)204f5b1c8a1SJohn Marino BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
205f5b1c8a1SJohn Marino {
206f5b1c8a1SJohn Marino return bnrand(1, rnd, bits, top, bottom);
207f5b1c8a1SJohn Marino }
208f5b1c8a1SJohn Marino
209f5b1c8a1SJohn Marino #if 1
210f5b1c8a1SJohn Marino int
BN_bntest_rand(BIGNUM * rnd,int bits,int top,int bottom)211f5b1c8a1SJohn Marino BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom)
212f5b1c8a1SJohn Marino {
213f5b1c8a1SJohn Marino return bnrand(2, rnd, bits, top, bottom);
214f5b1c8a1SJohn Marino }
215f5b1c8a1SJohn Marino #endif
216f5b1c8a1SJohn Marino
217f5b1c8a1SJohn Marino
218f5b1c8a1SJohn Marino /* random number r: 0 <= r < range */
219f5b1c8a1SJohn Marino static int
bn_rand_range(int pseudo,BIGNUM * r,const BIGNUM * range)220f5b1c8a1SJohn Marino bn_rand_range(int pseudo, BIGNUM *r, const BIGNUM *range)
221f5b1c8a1SJohn Marino {
222f5b1c8a1SJohn Marino int (*bn_rand)(BIGNUM *, int, int, int) = pseudo ? BN_pseudo_rand : BN_rand;
223f5b1c8a1SJohn Marino int n;
224f5b1c8a1SJohn Marino int count = 100;
225f5b1c8a1SJohn Marino
226f5b1c8a1SJohn Marino if (range->neg || BN_is_zero(range)) {
22772c33676SMaxim Ag BNerror(BN_R_INVALID_RANGE);
228f5b1c8a1SJohn Marino return 0;
229f5b1c8a1SJohn Marino }
230f5b1c8a1SJohn Marino
231f5b1c8a1SJohn Marino n = BN_num_bits(range); /* n > 0 */
232f5b1c8a1SJohn Marino
233f5b1c8a1SJohn Marino /* BN_is_bit_set(range, n - 1) always holds */
234f5b1c8a1SJohn Marino
235f5b1c8a1SJohn Marino if (n == 1)
236f5b1c8a1SJohn Marino BN_zero(r);
237f5b1c8a1SJohn Marino else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) {
238f5b1c8a1SJohn Marino /* range = 100..._2,
239f5b1c8a1SJohn Marino * so 3*range (= 11..._2) is exactly one bit longer than range */
240f5b1c8a1SJohn Marino do {
241f5b1c8a1SJohn Marino if (!bn_rand(r, n + 1, -1, 0))
242f5b1c8a1SJohn Marino return 0;
243f5b1c8a1SJohn Marino /* If r < 3*range, use r := r MOD range
244f5b1c8a1SJohn Marino * (which is either r, r - range, or r - 2*range).
245f5b1c8a1SJohn Marino * Otherwise, iterate once more.
246f5b1c8a1SJohn Marino * Since 3*range = 11..._2, each iteration succeeds with
247f5b1c8a1SJohn Marino * probability >= .75. */
248f5b1c8a1SJohn Marino if (BN_cmp(r, range) >= 0) {
249f5b1c8a1SJohn Marino if (!BN_sub(r, r, range))
250f5b1c8a1SJohn Marino return 0;
251f5b1c8a1SJohn Marino if (BN_cmp(r, range) >= 0)
252f5b1c8a1SJohn Marino if (!BN_sub(r, r, range))
253f5b1c8a1SJohn Marino return 0;
254f5b1c8a1SJohn Marino }
255f5b1c8a1SJohn Marino
256f5b1c8a1SJohn Marino if (!--count) {
25772c33676SMaxim Ag BNerror(BN_R_TOO_MANY_ITERATIONS);
258f5b1c8a1SJohn Marino return 0;
259f5b1c8a1SJohn Marino }
260f5b1c8a1SJohn Marino
261f5b1c8a1SJohn Marino } while (BN_cmp(r, range) >= 0);
262f5b1c8a1SJohn Marino } else {
263f5b1c8a1SJohn Marino do {
264f5b1c8a1SJohn Marino /* range = 11..._2 or range = 101..._2 */
265f5b1c8a1SJohn Marino if (!bn_rand(r, n, -1, 0))
266f5b1c8a1SJohn Marino return 0;
267f5b1c8a1SJohn Marino
268f5b1c8a1SJohn Marino if (!--count) {
26972c33676SMaxim Ag BNerror(BN_R_TOO_MANY_ITERATIONS);
270f5b1c8a1SJohn Marino return 0;
271f5b1c8a1SJohn Marino }
272f5b1c8a1SJohn Marino } while (BN_cmp(r, range) >= 0);
273f5b1c8a1SJohn Marino }
274f5b1c8a1SJohn Marino
275f5b1c8a1SJohn Marino bn_check_top(r);
276f5b1c8a1SJohn Marino return 1;
277f5b1c8a1SJohn Marino }
278f5b1c8a1SJohn Marino
279f5b1c8a1SJohn Marino int
BN_rand_range(BIGNUM * r,const BIGNUM * range)280f5b1c8a1SJohn Marino BN_rand_range(BIGNUM *r, const BIGNUM *range)
281f5b1c8a1SJohn Marino {
282f5b1c8a1SJohn Marino return bn_rand_range(0, r, range);
283f5b1c8a1SJohn Marino }
284f5b1c8a1SJohn Marino
285f5b1c8a1SJohn Marino int
bn_rand_interval(BIGNUM * rnd,const BIGNUM * lower_inc,const BIGNUM * upper_exc)28672c33676SMaxim Ag bn_rand_interval(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc)
28772c33676SMaxim Ag {
28872c33676SMaxim Ag BIGNUM *len = NULL;
28972c33676SMaxim Ag int ret = 0;
29072c33676SMaxim Ag
29172c33676SMaxim Ag if (BN_cmp(lower_inc, upper_exc) >= 0)
29272c33676SMaxim Ag goto err;
29372c33676SMaxim Ag
29472c33676SMaxim Ag if ((len = BN_new()) == NULL)
29572c33676SMaxim Ag goto err;
29672c33676SMaxim Ag
29772c33676SMaxim Ag if (!BN_sub(len, upper_exc, lower_inc))
29872c33676SMaxim Ag goto err;
29972c33676SMaxim Ag
30072c33676SMaxim Ag if (!bn_rand_range(0, rnd, len))
30172c33676SMaxim Ag goto err;
30272c33676SMaxim Ag
30372c33676SMaxim Ag if (!BN_add(rnd, rnd, lower_inc))
30472c33676SMaxim Ag goto err;
30572c33676SMaxim Ag
30672c33676SMaxim Ag ret = 1;
30772c33676SMaxim Ag err:
30872c33676SMaxim Ag BN_free(len);
30972c33676SMaxim Ag return ret;
31072c33676SMaxim Ag }
31172c33676SMaxim Ag
31272c33676SMaxim Ag int
BN_pseudo_rand_range(BIGNUM * r,const BIGNUM * range)313f5b1c8a1SJohn Marino BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range)
314f5b1c8a1SJohn Marino {
315f5b1c8a1SJohn Marino return bn_rand_range(1, r, range);
316f5b1c8a1SJohn Marino }
317