rand_uniform.c 4.1 KB

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