1 /*
2 * Copyright 2023 The OpenSSL Project Authors. All Rights Reserved.
3 *
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
8 */
9
10 #include "crypto/rand.h"
11 #include "internal/common.h"
12
13 /*
14 * Implementation an optimal random integer in a range function.
15 *
16 * Essentially it boils down to incrementally generating a fixed point
17 * number on the interval [0, 1) and multiplying this number by the upper
18 * range limit. Once it is certain what the fractional part contributes to
19 * the integral part of the product, the algorithm has produced a definitive
20 * result.
21 *
22 * Refer: https://github.com/apple/swift/pull/39143 for a fuller description
23 * of the algorithm.
24 */
ossl_rand_uniform_uint32(OSSL_LIB_CTX * ctx,uint32_t upper,int * err)25 uint32_t ossl_rand_uniform_uint32(OSSL_LIB_CTX *ctx, uint32_t upper, int *err)
26 {
27 uint32_t i, f; /* integer and fractional parts */
28 uint32_t f2, rand; /* extra fractional part and random material */
29 uint64_t prod; /* temporary holding double width product */
30 const int max_followup_iterations = 10;
31 int j;
32
33 if (!ossl_assert(upper > 0)) {
34 *err = 0;
35 return 0;
36 }
37 if (ossl_unlikely(upper == 1))
38 return 0;
39
40 /* Get 32 bits of entropy */
41 if (RAND_bytes_ex(ctx, (unsigned char *)&rand, sizeof(rand), 0) <= 0) {
42 *err = 1;
43 return 0;
44 }
45
46 /*
47 * We are generating a fixed point number on the interval [0, 1).
48 * Multiplying this by the range gives us a number on [0, upper).
49 * The high word of the multiplication result represents the integral
50 * part we want. The lower word is the fractional part. We can early exit if
51 * if the fractional part is small enough that no carry from the next lower
52 * word can cause an overflow and carry into the integer part. This
53 * happens when the fractional part is bounded by 2^32 - upper which
54 * can be simplified to just -upper (as an unsigned integer).
55 */
56 prod = (uint64_t)upper * rand;
57 i = prod >> 32;
58 f = prod & 0xffffffff;
59 if (ossl_likely(f <= 1 + ~upper)) /* 1+~upper == -upper but compilers whine */
60 return i;
61
62 /*
63 * We're in the position where the carry from the next word *might* cause
64 * a carry to the integral part. The process here is to generate the next
65 * word, multiply it by the range and add that to the current word. If
66 * it overflows, the carry propagates to the integer part (return i+1).
67 * If it can no longer overflow regardless of further lower order bits,
68 * we are done (return i). If there is still a chance of overflow, we
69 * repeat the process with the next lower word.
70 *
71 * Each *bit* of randomness has a probability of one half of terminating
72 * this process, so each each word beyond the first has a probability
73 * of 2^-32 of not terminating the process. That is, we're extremely
74 * likely to stop very rapidly.
75 */
76 for (j = 0; j < max_followup_iterations; j++) {
77 if (RAND_bytes_ex(ctx, (unsigned char *)&rand, sizeof(rand), 0) <= 0) {
78 *err = 1;
79 return 0;
80 }
81 prod = (uint64_t)upper * rand;
82 f2 = prod >> 32;
83 f += f2;
84 /* On overflow, add the carry to our result */
85 if (f < f2)
86 return i + 1;
87 /* For not all 1 bits, there is no carry so return the result */
88 if (ossl_likely(f != 0xffffffff))
89 return i;
90 /* setup for the next word of randomness */
91 f = prod & 0xffffffff;
92 }
93 /*
94 * If we get here, we've consumed 32 * max_followup_iterations + 32 bits
95 * with no firm decision, this gives a bias with probability < 2^-(32*n),
96 * which is likely acceptable.
97 */
98 return i;
99 }
100
ossl_rand_range_uint32(OSSL_LIB_CTX * ctx,uint32_t lower,uint32_t upper,int * err)101 uint32_t ossl_rand_range_uint32(OSSL_LIB_CTX *ctx, uint32_t lower, uint32_t upper,
102 int *err)
103 {
104 if (!ossl_assert(lower < upper)) {
105 *err = 1;
106 return 0;
107 }
108 return lower + ossl_rand_uniform_uint32(ctx, upper - lower, err);
109 }
110
