-int BN_rand_range(BIGNUM *r, BIGNUM *range)
- {
- int n;
-
- if (range->neg || BN_is_zero(range))
- {
- BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);
- return 0;
- }
-
- n = BN_num_bits(range); /* n > 0 */
-
- if (n == 1)
- {
- if (!BN_zero(r)) return 0;
- }
- else if (BN_is_bit_set(range, n - 2))
- {
- do
- {
- /* range = 11..._2, so each iteration succeeds with probability >= .75 */
- if (!BN_rand(r, n, -1, 0)) return 0;
- }
- while (BN_cmp(r, range) >= 0);
- }
- else
- {
- /* range = 10..._2,
- * so 3*range (= 11..._2) is exactly one bit longer than range */
- do
- {
- if (!BN_rand(r, n + 1, -1, 0)) return 0;
- /* If r < 3*range, use r := r MOD range
- * (which is either r, r - range, or r - 2*range).
- * Otherwise, iterate once more.
- * Since 3*range = 11..._2, each iteration succeeds with
- * probability >= .75. */
- if (BN_cmp(r ,range) >= 0)
- {
- if (!BN_sub(r, r, range)) return 0;
- if (BN_cmp(r, range) >= 0)
- if (!BN_sub(r, r, range)) return 0;
- }
- }
- while (BN_cmp(r, range) >= 0);
- }
-
- return 1;
- }
+static int bnrand_range(BNRAND_FLAG flag, BIGNUM *r, const BIGNUM *range)
+{
+ int b, n;
+ int count = 100;
+
+ if (range->neg || BN_is_zero(range)) {
+ BNerr(BN_F_BNRAND_RANGE, BN_R_INVALID_RANGE);
+ return 0;
+ }
+
+ n = BN_num_bits(range); /* n > 0 */
+
+ /* BN_is_bit_set(range, n - 1) always holds */
+
+ if (n == 1)
+ BN_zero(r);
+ else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) {
+ /*
+ * range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer
+ * than range
+ */
+ do {
+ b = flag == NORMAL
+ ? BN_rand(r, n + 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)
+ : BN_priv_rand(r, n + 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY);
+ if (!b)
+ return 0;
+ /*
+ * If r < 3*range, use r := r MOD range (which is either r, r -
+ * range, or r - 2*range). Otherwise, iterate once more. Since
+ * 3*range = 11..._2, each iteration succeeds with probability >=
+ * .75.
+ */
+ if (BN_cmp(r, range) >= 0) {
+ if (!BN_sub(r, r, range))
+ return 0;
+ if (BN_cmp(r, range) >= 0)
+ if (!BN_sub(r, r, range))
+ return 0;
+ }
+
+ if (!--count) {
+ BNerr(BN_F_BNRAND_RANGE, BN_R_TOO_MANY_ITERATIONS);
+ return 0;
+ }
+
+ }
+ while (BN_cmp(r, range) >= 0);
+ } else {
+ do {
+ /* range = 11..._2 or range = 101..._2 */
+ if (!BN_rand(r, n, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY))
+ return 0;
+
+ if (!--count) {
+ BNerr(BN_F_BNRAND_RANGE, BN_R_TOO_MANY_ITERATIONS);
+ return 0;
+ }
+ }
+ while (BN_cmp(r, range) >= 0);
+ }
+
+ bn_check_top(r);
+ return 1;
+}
+
+int BN_rand_range(BIGNUM *r, const BIGNUM *range)
+{
+ return bnrand_range(NORMAL, r, range);
+}
+
+int BN_priv_rand_range(BIGNUM *r, const BIGNUM *range)
+{
+ return bnrand_range(PRIVATE, r, range);
+}
+
+int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
+{
+ return BN_rand(rnd, bits, top, bottom);
+}
+
+int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range)
+{
+ return BN_rand_range(r, range);
+}
+
+/*
+ * BN_generate_dsa_nonce generates a random number 0 <= out < range. Unlike
+ * BN_rand_range, it also includes the contents of |priv| and |message| in
+ * the generation so that an RNG failure isn't fatal as long as |priv|
+ * remains secret. This is intended for use in DSA and ECDSA where an RNG
+ * weakness leads directly to private key exposure unless this function is
+ * used.
+ */
+int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range,
+ const BIGNUM *priv, const unsigned char *message,
+ size_t message_len, BN_CTX *ctx)
+{
+ SHA512_CTX sha;
+ /*
+ * We use 512 bits of random data per iteration to ensure that we have at
+ * least |range| bits of randomness.
+ */
+ unsigned char random_bytes[64];
+ unsigned char digest[SHA512_DIGEST_LENGTH];
+ unsigned done, todo;
+ /* We generate |range|+8 bytes of random output. */
+ const unsigned num_k_bytes = BN_num_bytes(range) + 8;
+ unsigned char private_bytes[96];
+ unsigned char *k_bytes;
+ int ret = 0;
+
+ k_bytes = OPENSSL_malloc(num_k_bytes);
+ if (k_bytes == NULL)
+ goto err;
+
+ /* We copy |priv| into a local buffer to avoid exposing its length. */
+ todo = sizeof(priv->d[0]) * priv->top;
+ if (todo > sizeof(private_bytes)) {
+ /*
+ * No reasonable DSA or ECDSA key should have a private key this
+ * large and we don't handle this case in order to avoid leaking the
+ * length of the private key.
+ */
+ BNerr(BN_F_BN_GENERATE_DSA_NONCE, BN_R_PRIVATE_KEY_TOO_LARGE);
+ goto err;
+ }
+ memcpy(private_bytes, priv->d, todo);
+ memset(private_bytes + todo, 0, sizeof(private_bytes) - todo);
+
+ for (done = 0; done < num_k_bytes;) {
+ if (RAND_bytes(random_bytes, sizeof(random_bytes)) != 1)
+ goto err;
+ SHA512_Init(&sha);
+ SHA512_Update(&sha, &done, sizeof(done));
+ SHA512_Update(&sha, private_bytes, sizeof(private_bytes));
+ SHA512_Update(&sha, message, message_len);
+ SHA512_Update(&sha, random_bytes, sizeof(random_bytes));
+ SHA512_Final(digest, &sha);
+
+ todo = num_k_bytes - done;
+ if (todo > SHA512_DIGEST_LENGTH)
+ todo = SHA512_DIGEST_LENGTH;
+ memcpy(k_bytes + done, digest, todo);
+ done += todo;
+ }
+
+ if (!BN_bin2bn(k_bytes, num_k_bytes, out))
+ goto err;
+ if (BN_mod(out, out, range, ctx) != 1)
+ goto err;
+ ret = 1;
+
+ err:
+ OPENSSL_free(k_bytes);
+ OPENSSL_cleanse(private_bytes, sizeof(private_bytes));
+ return ret;
+}