2 * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the OpenSSL license (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"
14 #include <openssl/rand.h>
15 #include <openssl/sha.h>
17 static int bnrand(int testing
, BIGNUM
*rnd
, int bits
, int top
, int bottom
)
19 unsigned char *buf
= NULL
;
20 int ret
= 0, bit
, bytes
, mask
;
24 if (top
!= BN_RAND_TOP_ANY
|| bottom
!= BN_RAND_BOTTOM_ANY
)
29 if (bits
< 0 || (bits
== 1 && top
> 0))
32 bytes
= (bits
+ 7) / 8;
34 mask
= 0xff << (bit
+ 1);
36 buf
= OPENSSL_malloc(bytes
);
38 BNerr(BN_F_BNRAND
, ERR_R_MALLOC_FAILURE
);
42 /* make a random number and set the top and bottom bits */
44 RAND_add(&tim
, sizeof(tim
), 0.0);
46 if (RAND_bytes(buf
, bytes
) <= 0)
51 * generate patterns that are more likely to trigger BN library bugs
56 for (i
= 0; i
< bytes
; i
++) {
57 if (RAND_bytes(&c
, 1) <= 0)
59 if (c
>= 128 && i
> 0)
74 buf
[0] |= (3 << (bit
- 1));
81 if (bottom
) /* set bottom bit if requested */
83 if (!BN_bin2bn(buf
, bytes
, rnd
))
87 OPENSSL_clear_free(buf
, bytes
);
92 BNerr(BN_F_BNRAND
, BN_R_BITS_TOO_SMALL
);
96 int BN_rand(BIGNUM
*rnd
, int bits
, int top
, int bottom
)
98 return bnrand(0, rnd
, bits
, top
, bottom
);
101 int BN_bntest_rand(BIGNUM
*rnd
, int bits
, int top
, int bottom
)
103 return bnrand(1, rnd
, bits
, top
, bottom
);
106 /* random number r: 0 <= r < range */
107 int BN_rand_range(BIGNUM
*r
, const BIGNUM
*range
)
112 if (range
->neg
|| BN_is_zero(range
)) {
113 BNerr(BN_F_BN_RAND_RANGE
, BN_R_INVALID_RANGE
);
117 n
= BN_num_bits(range
); /* n > 0 */
119 /* BN_is_bit_set(range, n - 1) always holds */
123 else if (!BN_is_bit_set(range
, n
- 2) && !BN_is_bit_set(range
, n
- 3)) {
125 * range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer
129 if (!BN_rand(r
, n
+ 1, BN_RAND_TOP_ANY
, BN_RAND_BOTTOM_ANY
))
132 * If r < 3*range, use r := r MOD range (which is either r, r -
133 * range, or r - 2*range). Otherwise, iterate once more. Since
134 * 3*range = 11..._2, each iteration succeeds with probability >=
137 if (BN_cmp(r
, range
) >= 0) {
138 if (!BN_sub(r
, r
, range
))
140 if (BN_cmp(r
, range
) >= 0)
141 if (!BN_sub(r
, r
, range
))
146 BNerr(BN_F_BN_RAND_RANGE
, BN_R_TOO_MANY_ITERATIONS
);
151 while (BN_cmp(r
, range
) >= 0);
154 /* range = 11..._2 or range = 101..._2 */
155 if (!BN_rand(r
, n
, BN_RAND_TOP_ANY
, BN_RAND_BOTTOM_ANY
))
159 BNerr(BN_F_BN_RAND_RANGE
, BN_R_TOO_MANY_ITERATIONS
);
163 while (BN_cmp(r
, range
) >= 0);
170 int BN_pseudo_rand(BIGNUM
*rnd
, int bits
, int top
, int bottom
)
172 return BN_rand(rnd
, bits
, top
, bottom
);
175 int BN_pseudo_rand_range(BIGNUM
*r
, const BIGNUM
*range
)
177 return BN_rand_range(r
, range
);
181 * BN_generate_dsa_nonce generates a random number 0 <= out < range. Unlike
182 * BN_rand_range, it also includes the contents of |priv| and |message| in
183 * the generation so that an RNG failure isn't fatal as long as |priv|
184 * remains secret. This is intended for use in DSA and ECDSA where an RNG
185 * weakness leads directly to private key exposure unless this function is
188 int BN_generate_dsa_nonce(BIGNUM
*out
, const BIGNUM
*range
,
189 const BIGNUM
*priv
, const unsigned char *message
,
190 size_t message_len
, BN_CTX
*ctx
)
194 * We use 512 bits of random data per iteration to ensure that we have at
195 * least |range| bits of randomness.
197 unsigned char random_bytes
[64];
198 unsigned char digest
[SHA512_DIGEST_LENGTH
];
200 /* We generate |range|+8 bytes of random output. */
201 const unsigned num_k_bytes
= BN_num_bytes(range
) + 8;
202 unsigned char private_bytes
[96];
203 unsigned char *k_bytes
;
206 k_bytes
= OPENSSL_malloc(num_k_bytes
);
210 /* We copy |priv| into a local buffer to avoid exposing its length. */
211 todo
= sizeof(priv
->d
[0]) * priv
->top
;
212 if (todo
> sizeof(private_bytes
)) {
214 * No reasonable DSA or ECDSA key should have a private key this
215 * large and we don't handle this case in order to avoid leaking the
216 * length of the private key.
218 BNerr(BN_F_BN_GENERATE_DSA_NONCE
, BN_R_PRIVATE_KEY_TOO_LARGE
);
221 memcpy(private_bytes
, priv
->d
, todo
);
222 memset(private_bytes
+ todo
, 0, sizeof(private_bytes
) - todo
);
224 for (done
= 0; done
< num_k_bytes
;) {
225 if (RAND_bytes(random_bytes
, sizeof(random_bytes
)) != 1)
228 SHA512_Update(&sha
, &done
, sizeof(done
));
229 SHA512_Update(&sha
, private_bytes
, sizeof(private_bytes
));
230 SHA512_Update(&sha
, message
, message_len
);
231 SHA512_Update(&sha
, random_bytes
, sizeof(random_bytes
));
232 SHA512_Final(digest
, &sha
);
234 todo
= num_k_bytes
- done
;
235 if (todo
> SHA512_DIGEST_LENGTH
)
236 todo
= SHA512_DIGEST_LENGTH
;
237 memcpy(k_bytes
+ done
, digest
, todo
);
241 if (!BN_bin2bn(k_bytes
, num_k_bytes
, out
))
243 if (BN_mod(out
, out
, range
, ctx
) != 1)
248 OPENSSL_free(k_bytes
);
249 OPENSSL_cleanse(private_bytes
, sizeof(private_bytes
));