2 * Copyright 1995-2021 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
12 #include "internal/cryptlib.h"
13 #include "crypto/rand.h"
15 #include <openssl/rand.h>
16 #include <openssl/sha.h>
17 #include <openssl/evp.h>
19 typedef enum bnrand_flag_e
{
20 NORMAL
, TESTING
, PRIVATE
23 static int bnrand(BNRAND_FLAG flag
, BIGNUM
*rnd
, int bits
, int top
, int bottom
,
24 unsigned int strength
, BN_CTX
*ctx
)
26 unsigned char *buf
= NULL
;
27 int b
, ret
= 0, bit
, bytes
, mask
;
28 OSSL_LIB_CTX
*libctx
= ossl_bn_get_libctx(ctx
);
31 if (top
!= BN_RAND_TOP_ANY
|| bottom
!= BN_RAND_BOTTOM_ANY
)
36 if (bits
< 0 || (bits
== 1 && top
> 0))
39 bytes
= (bits
+ 7) / 8;
41 mask
= 0xff << (bit
+ 1);
43 buf
= OPENSSL_malloc(bytes
);
47 /* make a random number and set the top and bottom bits */
48 b
= flag
== NORMAL
? RAND_bytes_ex(libctx
, buf
, bytes
, strength
)
49 : RAND_priv_bytes_ex(libctx
, buf
, bytes
, strength
);
53 if (flag
== TESTING
) {
55 * generate patterns that are more likely to trigger BN library bugs
60 for (i
= 0; i
< bytes
; i
++) {
61 if (RAND_bytes_ex(libctx
, &c
, 1, strength
) <= 0)
63 if (c
>= 128 && i
> 0)
78 buf
[0] |= (3 << (bit
- 1));
85 if (bottom
) /* set bottom bit if requested */
87 if (!BN_bin2bn(buf
, bytes
, rnd
))
91 OPENSSL_clear_free(buf
, bytes
);
96 ERR_raise(ERR_LIB_BN
, BN_R_BITS_TOO_SMALL
);
100 int BN_rand_ex(BIGNUM
*rnd
, int bits
, int top
, int bottom
,
101 unsigned int strength
, BN_CTX
*ctx
)
103 return bnrand(NORMAL
, rnd
, bits
, top
, bottom
, strength
, ctx
);
106 int BN_rand(BIGNUM
*rnd
, int bits
, int top
, int bottom
)
108 return bnrand(NORMAL
, rnd
, bits
, top
, bottom
, 0, NULL
);
111 int BN_bntest_rand(BIGNUM
*rnd
, int bits
, int top
, int bottom
)
113 return bnrand(TESTING
, rnd
, bits
, top
, bottom
, 0, NULL
);
117 int BN_priv_rand_ex(BIGNUM
*rnd
, int bits
, int top
, int bottom
,
118 unsigned int strength
, BN_CTX
*ctx
)
120 return bnrand(PRIVATE
, rnd
, bits
, top
, bottom
, strength
, ctx
);
124 int BN_priv_rand(BIGNUM
*rnd
, int bits
, int top
, int bottom
)
126 return bnrand(PRIVATE
, rnd
, bits
, top
, bottom
, 0, NULL
);
130 /* random number r: 0 <= r < range */
131 static int bnrand_range(BNRAND_FLAG flag
, BIGNUM
*r
, const BIGNUM
*range
,
132 unsigned int strength
, BN_CTX
*ctx
)
138 ERR_raise(ERR_LIB_BN
, ERR_R_PASSED_NULL_PARAMETER
);
142 if (range
->neg
|| BN_is_zero(range
)) {
143 ERR_raise(ERR_LIB_BN
, BN_R_INVALID_RANGE
);
147 n
= BN_num_bits(range
); /* n > 0 */
149 /* BN_is_bit_set(range, n - 1) always holds */
153 else if (!BN_is_bit_set(range
, n
- 2) && !BN_is_bit_set(range
, n
- 3)) {
155 * range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer
159 if (!bnrand(flag
, r
, n
+ 1, BN_RAND_TOP_ANY
, BN_RAND_BOTTOM_ANY
,
164 * If r < 3*range, use r := r MOD range (which is either r, r -
165 * range, or r - 2*range). Otherwise, iterate once more. Since
166 * 3*range = 11..._2, each iteration succeeds with probability >=
169 if (BN_cmp(r
, range
) >= 0) {
170 if (!BN_sub(r
, r
, range
))
172 if (BN_cmp(r
, range
) >= 0)
173 if (!BN_sub(r
, r
, range
))
178 ERR_raise(ERR_LIB_BN
, BN_R_TOO_MANY_ITERATIONS
);
183 while (BN_cmp(r
, range
) >= 0);
186 /* range = 11..._2 or range = 101..._2 */
187 if (!bnrand(flag
, r
, n
, BN_RAND_TOP_ANY
, BN_RAND_BOTTOM_ANY
, 0,
192 ERR_raise(ERR_LIB_BN
, BN_R_TOO_MANY_ITERATIONS
);
196 while (BN_cmp(r
, range
) >= 0);
203 int BN_rand_range_ex(BIGNUM
*r
, const BIGNUM
*range
, unsigned int strength
,
206 return bnrand_range(NORMAL
, r
, range
, strength
, ctx
);
210 int BN_rand_range(BIGNUM
*r
, const BIGNUM
*range
)
212 return bnrand_range(NORMAL
, r
, range
, 0, NULL
);
216 int BN_priv_rand_range_ex(BIGNUM
*r
, const BIGNUM
*range
, unsigned int strength
,
219 return bnrand_range(PRIVATE
, r
, range
, strength
, ctx
);
223 int BN_priv_rand_range(BIGNUM
*r
, const BIGNUM
*range
)
225 return bnrand_range(PRIVATE
, r
, range
, 0, NULL
);
228 # ifndef OPENSSL_NO_DEPRECATED_3_0
229 int BN_pseudo_rand(BIGNUM
*rnd
, int bits
, int top
, int bottom
)
231 return BN_rand(rnd
, bits
, top
, bottom
);
234 int BN_pseudo_rand_range(BIGNUM
*r
, const BIGNUM
*range
)
236 return BN_rand_range(r
, range
);
242 * BN_generate_dsa_nonce generates a random number 0 <= out < range. Unlike
243 * BN_rand_range, it also includes the contents of |priv| and |message| in
244 * the generation so that an RNG failure isn't fatal as long as |priv|
245 * remains secret. This is intended for use in DSA and ECDSA where an RNG
246 * weakness leads directly to private key exposure unless this function is
249 int BN_generate_dsa_nonce(BIGNUM
*out
, const BIGNUM
*range
,
250 const BIGNUM
*priv
, const unsigned char *message
,
251 size_t message_len
, BN_CTX
*ctx
)
253 EVP_MD_CTX
*mdctx
= EVP_MD_CTX_new();
255 * We use 512 bits of random data per iteration to ensure that we have at
256 * least |range| bits of randomness.
258 unsigned char random_bytes
[64];
259 unsigned char digest
[SHA512_DIGEST_LENGTH
];
261 /* We generate |range|+8 bytes of random output. */
262 const unsigned num_k_bytes
= BN_num_bytes(range
) + 8;
263 unsigned char private_bytes
[96];
264 unsigned char *k_bytes
= NULL
;
267 OSSL_LIB_CTX
*libctx
= ossl_bn_get_libctx(ctx
);
272 k_bytes
= OPENSSL_malloc(num_k_bytes
);
276 /* We copy |priv| into a local buffer to avoid exposing its length. */
277 if (BN_bn2binpad(priv
, private_bytes
, sizeof(private_bytes
)) < 0) {
279 * No reasonable DSA or ECDSA key should have a private key this
280 * large and we don't handle this case in order to avoid leaking the
281 * length of the private key.
283 ERR_raise(ERR_LIB_BN
, BN_R_PRIVATE_KEY_TOO_LARGE
);
287 md
= EVP_MD_fetch(libctx
, "SHA512", NULL
);
289 ERR_raise(ERR_LIB_BN
, BN_R_NO_SUITABLE_DIGEST
);
292 for (done
= 0; done
< num_k_bytes
;) {
293 if (RAND_priv_bytes_ex(libctx
, random_bytes
, sizeof(random_bytes
), 0) <= 0)
296 if (!EVP_DigestInit_ex(mdctx
, md
, NULL
)
297 || !EVP_DigestUpdate(mdctx
, &done
, sizeof(done
))
298 || !EVP_DigestUpdate(mdctx
, private_bytes
,
299 sizeof(private_bytes
))
300 || !EVP_DigestUpdate(mdctx
, message
, message_len
)
301 || !EVP_DigestUpdate(mdctx
, random_bytes
, sizeof(random_bytes
))
302 || !EVP_DigestFinal_ex(mdctx
, digest
, NULL
))
305 todo
= num_k_bytes
- done
;
306 if (todo
> SHA512_DIGEST_LENGTH
)
307 todo
= SHA512_DIGEST_LENGTH
;
308 memcpy(k_bytes
+ done
, digest
, todo
);
312 if (!BN_bin2bn(k_bytes
, num_k_bytes
, out
))
314 if (BN_mod(out
, out
, range
, ctx
) != 1)
319 EVP_MD_CTX_free(mdctx
);
321 OPENSSL_free(k_bytes
);
322 OPENSSL_cleanse(private_bytes
, sizeof(private_bytes
));