diff options
author | Pauli <pauli@openssl.org> | 2023-10-25 17:48:43 +1100 |
---|---|---|
committer | Tomas Mraz <tomas@openssl.org> | 2023-11-01 12:07:13 +0100 |
commit | 3fe56baf936373daa39b944e3194a6f234fbe8bf (patch) | |
tree | aecb94f3ddf0c292ba0d01b27edf3d2f9e0a1106 /crypto | |
parent | b4a33ba9aaf8022589dd15261f41d35729277a68 (diff) |
rand: implement an unbiased random integer from a range
Refer: https://github.com/apple/swift/pull/39143 for a description
of the algorithm.
It is optimal in the sense of having:
* no divisions
* minimal number of blocks of random bits from the generator
Reviewed-by: Tom Cosgrove <tom.cosgrove@arm.com>
Reviewed-by: Matthias St. Pierre <Matthias.St.Pierre@ncp-e.com>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/22499)
(cherry picked from commit 55755fbf42ec073e86651065c5cce6f64662c9e6)
Diffstat (limited to 'crypto')
-rw-r--r-- | crypto/rand/build.info | 3 | ||||
-rw-r--r-- | crypto/rand/rand_uniform.c | 76 |
2 files changed, 78 insertions, 1 deletions
diff --git a/crypto/rand/build.info b/crypto/rand/build.info index a74282516f..7c01577b0d 100644 --- a/crypto/rand/build.info +++ b/crypto/rand/build.info @@ -1,7 +1,8 @@ LIBS=../../libcrypto $COMMON=rand_lib.c -$CRYPTO=randfile.c rand_err.c rand_deprecated.c prov_seed.c rand_pool.c +$CRYPTO=randfile.c rand_err.c rand_deprecated.c prov_seed.c rand_pool.c \ + rand_uniform.c IF[{- !$disabled{'egd'} -}] $CRYPTO=$CRYPTO rand_egd.c diff --git a/crypto/rand/rand_uniform.c b/crypto/rand/rand_uniform.c new file mode 100644 index 0000000000..d37e38b9b6 --- /dev/null +++ b/crypto/rand/rand_uniform.c @@ -0,0 +1,76 @@ +/* + * Copyright 2023 The OpenSSL Project Authors. All Rights Reserved. + * + * Licensed under the Apache License 2.0 (the "License"). You may not use + * this file except in compliance with the License. You can obtain a copy + * in the file LICENSE in the source distribution or at + * https://www.openssl.org/source/license.html + */ + +#include "crypto/rand.h" +#include "internal/common.h" + +/* + * Implementation an optimal random integer in a range function. + * Refer: https://github.com/apple/swift/pull/39143 for a description + * of the algorithm. + */ +uint32_t ossl_rand_uniform_uint32(OSSL_LIB_CTX *ctx, uint32_t upper, int *err) +{ + uint32_t i, f; /* integer and fractional parts */ + uint32_t f2, rand; /* extra fractional part and random material */ + uint64_t prod; /* temporary holding double width product */ + const int max_followup_iterations = 10; + int j; + + if (!ossl_assert(upper > 0)) { + *err = 0; + return 0; + } + if (unlikely(upper == 1)) + return 0; + /* Get 32 bits of entropy */ + if (RAND_bytes_ex(ctx, (unsigned char *)&rand, sizeof(rand), 0) <= 0) { + *err = 1; + return 0; + } + prod = (uint64_t)upper * rand; + i = prod >> 32; + f = prod & 0xffffffff; + if (likely(f <= 1 + ~upper)) /* 1+~upper == -upper but compilers whine */ + return i; + + for (j = 0; j < max_followup_iterations; j++) { + if (RAND_bytes_ex(ctx, (unsigned char *)&rand, sizeof(rand), 0) <= 0) { + *err = 1; + return 0; + } + prod = (uint64_t)upper * rand; + f2 = prod >> 32; + f += f2; + /* On overflow, add the carry to our result */ + if (f < f2) + return i + 1; + /* For not all 1 bits, there is no carry so return the result */ + if (unlikely(f != 0xffffffff)) + return i; + /* setup for the next word of randomness */ + f = prod & 0xffffffff; + } + /* + * If we get here, we've consumed 32 * max_followup_iterations + 32 bits + * with no firm decision, this gives a bias with probability < 2^(32*n), + * likely acceptable. + */ + return i; +} + +uint32_t ossl_rand_range_uint32(OSSL_LIB_CTX *ctx, uint32_t lower, uint32_t upper, + int *err) +{ + if (!ossl_assert(lower < upper)) { + *err = 1; + return 0; + } + return lower + ossl_rand_uniform_uint32(ctx, upper - lower, err); +} |