3
$\begingroup$

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?

|improve this question
$\endgroup$
  • $\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
2
$\begingroup$

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.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.