I'm using a function randInt that takes as input two integers as upper and lower bounds (inclusive) and outputs a pseudorandom number in that interval. Unfortunately, the function's range can be an interval no greater than $10^{14} - 2$ (meaning the difference of the inputs can be no more than that value). As a workaround, I want this function to generate a number in the closed interval $[0, p-2]$ where $p$ is a large prime (for example: 246,494,430,254,053,509,990,478,163,925,484,154,219).

I can't simply break it into digit groups and generate each group randomly because then the generated number could be 246,494,430,... and then all nines. I also want to avoid looping until I get a number smaller than $p$. How can this be done?

  • $\begingroup$ Are you sure about the '-2's? It is more common to have '-1'. I also don't understand your example; the numbers are not prime and they are not large (and they are not like $10^{14}$ either). $\endgroup$ – Chris Aug 11 '15 at 19:20
  • 3
    $\begingroup$ For clarification purposes: do you target “cryptographically secure randomness” or just “randomness”? (Because randInt is not known to be cryptographically secure…) $\endgroup$ – e-sushi Aug 11 '15 at 19:21
  • $\begingroup$ @e-sushi I only need randomness as random as 'randInt'. $\endgroup$ – LLCryptographer Aug 11 '15 at 22:13
  • $\begingroup$ @Chris I used commas to separate digit groups, not different 3-digit numbers, but my answer was edited. I am using -2 because I want to use this number as an exponent for a generator modulo $p$. Since $g^{0}$ and $g^{p-1}$ both equal 1 mod $p$, I want to generate an exponent in the interval $[0, p-2]$. $\endgroup$ – LLCryptographer Aug 11 '15 at 22:32
  • 1
    $\begingroup$ That's too small to be secure; there are known ways to solve the DLog problem practically against a prime that small. Instead, you need a $p$ at least around $2^{1024}$, and nowaways $2^{2048}$ is considered prudent $\endgroup$ – poncho Aug 12 '15 at 1:17

Let's assume that randInt gives you cryptographically random (independent) numbers in the range $[0, N)$. Then you can generate a larger number by taking two of those, $x_1$ and $x_2$ and adding $x_1 + x_2 \cdot N$ (which is just bit concatenation if $N = 2^n$). That's a random number in the range $[0, N^2)$, assuming the original numbers were random and independent. If $N=2^n$, you can also drop bits off, i.e. take the value modulo some smaller power of two, without introducing biases.

To get a range that isn't a power of two in size, like a prime, you must use a modulus that's sufficiently small, or the low values will be more likely to show up. I.e. you must first overshoot the prime sufficiently, and then take the modulo. A factor of e.g. $2^{128}$ would be sufficient for 128-bit security. (Alternatively, you can use rejection sampling, but you wished to avoid that.)

If the original range isn't a power of two in size, which seems unlikely with a CSPRNG, you would likewise have to overshoot + modulo to get to a power of two range. Or directly to a prime range.

Now, if randInt isn't a CSPRNG, it may have biases that the above procedure compounds. But then, you shouldn't be using it for cryptography.


Your Answer

