From 35ed8cb8b6655606c2be31d44be942f6724ba405 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bodo=20M=C3=B6ller?= Date: Thu, 8 Feb 2001 12:14:51 +0000 Subject: Integrate my implementation of a countermeasure against Bleichenbacher's DSA attack. With this implementation, the expected number of iterations never exceeds 2. New semantics for BN_rand_range(): BN_rand_range(r, min, range) now generates r such that min <= r < min+range. (Previously, BN_rand_range(r, min, max) generated r such that min <= r < max. It is more convenient to have the range; also the previous prototype was misleading because max was larger than the actual maximum.) --- crypto/bn/bn_rand.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 55 insertions(+), 6 deletions(-) (limited to 'crypto/bn/bn_rand.c') diff --git a/crypto/bn/bn_rand.c b/crypto/bn/bn_rand.c index f2c79b5e31..a7e35357d6 100644 --- a/crypto/bn/bn_rand.c +++ b/crypto/bn/bn_rand.c @@ -169,13 +169,62 @@ int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom) } #endif -/* random number r: min <= r < max */ -int BN_rand_range(BIGNUM *r, BIGNUM *min, BIGNUM *max) +/* random number r: min <= r < min+range */ +int BN_rand_range(BIGNUM *r, BIGNUM *min, BIGNUM *range) { - int n = BN_num_bits(max); - do + 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 > .5 */ + if (!BN_rand(r, n, 0, 0)) return 0; + fprintf(stderr, "?"); + } + while (BN_cmp(r, range) >= 0); + fprintf(stderr, "! (11...)\n"); + } + else { - if (!BN_rand(r, n, 0, 0)) return 0; - } while ((min && BN_cmp(r, min) < 0) || BN_cmp(r, max) >= 0); + /* range = 10..._2, + * so 3*range (= 11..._2) is exactly one bit longer than range */ + do + { + if (!BN_rand(r, n + 1, 0, 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 > .5. */ + 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; + } + fprintf(stderr, "?"); + } + while (BN_cmp(r, range) >= 0); + fprintf(stderr, "! (10...)\n"); + } + + if (min != NULL) + { + if (!BN_add(r, r, min)) return 0; + } + return 1; } -- cgit v1.2.3