Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Say that we have a secure random number generation that outputs 32 bit random numbers, so it's output is a true random number between 0 and a MAX.

What is the best way to map this random number to a defined range (say I want something random between X and Y) without loosing too much entropy?

share|improve this question
2  
This seems to be essentially a duplicate of crypto.stackexchange.com/q/5708/351 Ideally, the two would be merged. –  D.W. Apr 16 '13 at 1:26

1 Answer 1

up vote 7 down vote accepted

Let $m = Y-X$. Generating a random integer in the $X$ to $Y$ range is equivalent to generating a random integer in the $0$ to $m$ range (if you generate $r$, then just use $r+X$). For ease of notation, I assume that the low boundary is included and the high boundary is excluded (you want a random $s$ such that $X \leq s \lt Y$).

In most cases, you cannot get a truly uniform random generation by processing a fixed number $n$ of 32-bit integers. Indeed, $n$ 32-bit integers represent exactly $2^{32n}$ possible outcomes. If $m$ is not a power of $2$, then $2^{32m}$ cannot be divided into $m$ sets of identical cardinal.

The usual method is a rejection process:

  1. Let $u$ be such that $2^u \geq m$.
  2. Let $t = m \times \lfloor \frac{2^u}{m} \rfloor$.
  3. Generate $x$, a $u$-bit value (from your generator of 32-bit integers, just append 32-bit values until you reach the size $u$ or more, and truncate to $u$ bits). We have $0 \leq x \lt 2^u$.
  4. If $x \geq t$ then loop to the previous step.
  5. Return $r = x \mod m$.

The idea of the method is that the $2^u$ range is split into a sub-range of size $t$ (a multiple of $m$) and another sub-range (of size less than $m$). If the $u$-bit value $x$ fall in the first sub-range, then you take it modulo $m$, which yields a uniform value since $t$ is a multiple of $m$. Otherwise, you just discard $x$ and try again. With the constraints above, it can easily be seen that the probability of $x$ falling in the wrong sub-range is less then $0.5$, so the average number of invocations of the PRNG will be less than $2$ (less than two invocations for a $k$-bit integer, which may involve a lot of invocations of the underlying PRNG which produces only 32 bits at a time, depending on your parameters).

Then you have a choice, namely what $u$ to use. One extreme is to use the smallest possible $u$, i.e. $2^{u-1} \lt m \leq 2^u$. This is the choice that maximizes the average number of loops; however, it means that the final "modulo" operation is a no-operation (with $u$ as small as possible, you have $t = m$). For small parameters ($m$ is less then 32 bits), this is often an appropriate choice, because PRNG invocations are usually cheaper than integer division (if you use an efficient PRNG, such as these ones, of course).

The other extreme is to make $u$ much bigger, so that the probability that $x$ falls in the wrong range becomes negligible; at that point, you can often just skip the computation of $t$ and the test $x \geq t$, and proceed directly to the modulo operation: this will imply a slight bias, but a bias lower than what can be detected, let alone be acted upon.

See DSA, annex B.2: for each DSA (or ECDSA) signature, a new value $k$ must be generated for each signature, in the $1$ to $q-1$ range (inclusive), and it must be as uniform as possible. The annex presents the two methods, one with 64 bits of extra space ($u \geq 64 + \log q$), the other with the smallest possible $u$. Which one is preferable is a question of performance and convenience; a DSA implementation (as opposed to ECDSA) must have some code to reduce big values modulo $q$, so using the extra bits is probably simplest; ECDSA implementations, on the other hand, especially hardware implementations which work with binary fields, will probably prefer the "small $u$" method. For security, both are safe.

share|improve this answer
3  
This algorithm is great when random input is cheap, and is most used; for example by java.util.Random.nextint(int n), with $u=31$. But it often consumes significantly more input than necessary, and that's an issue in some applications (e.g when the input is expensive/slow, e.g. coins throws). This, while remaining practical, manages to reduce $u$ dynamically when possible, which is most often; and recycling some (not all) of the previously gathered entropy, rather than loosing it as occurs at step 4 when looping back; it is not optimal, though. –  fgrieu Apr 15 '13 at 20:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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