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.

i'm trying to figure out the best way to generate a cryptographically secure random number between 0 and 200 from a cryptographically random string of bytes (ie. read from /dev/urandom or some such)

i could do random[0] % 201 but then numbers 0-54 would be more likely than 55-200 which would make the resultant number more predictable than it should be it seems to me.

any ideas?

share|improve this question
add comment

2 Answers

A trivial way to achieve this is to use the number is it's smaller than 201 and discard it (move on to the the next byte) if it's not.

The derived numbers will be truly random provided that the bytes are:

Since the sequence is random, every possible value of every number in the original sequence has probability $\frac{1}{256}$. Thus, at any given point, the probability that the next byte will be $k\leq200$ is also $p_0=\frac{1}{256}$.

However, the probability that the byte will be discarded is $\frac{55}{256}$. Because of this and the fact that the numbers are independent, the probability that the second byte provides us with the number $k$ is $p_1=\frac{55}{256}\cdot\frac{1}{256}$.

Continuing this reasoning, the probability that the first $j$ bytes will be discarded and that the next byte is $k$ is $p_j=\left(\frac{55}{256}\right)\cdot\frac{1}{256}$. Thus, the probability of the next derived number being 42 is $$p=p_0 + p_1 + p_2 + \cdots = \sum_{n=0}^{+\infty}\left(\frac{55}{256}\right)^n\cdot\frac{1}{256}.$$

This is a geometric series, and the probability is $$p = \frac{1}{1-\frac{55}{256}}\cdot\frac{1}{256} = \frac{1}{\frac{201}{256}}\cdot\frac{1}{256} = \frac{256}{201}\cdot\frac{1}{256} = \frac{1}{201}.$$

Since this holds for every of the 201 possible values of $k$, the derived sequence is random.

In general, if your RNG outputs numbers $x\in\{0,\cdots,n - 1\}$ and you need to derive a random sequence of numbers $y\in\{0,\cdots,k - 1\}$, you can take $y = x\bmod k$ if $x < \left\lfloor\frac{n}{k}\right\rfloor\cdot k$ and discard $x$ otherwise.

Since $\left\lfloor\frac{n}{k}\right\rfloor\cdot k$ is an entire multiple of $k$, there is no bias.

share|improve this answer
    
Could you add a few words about why this is true? This might be of additional value to the OP, especially in cryptography you don't want to take anything for granted unless you have a proof or a solid reference. –  Thomas Dec 15 '12 at 17:08
    
@Thomas: I took this a premise, since the numbers of a random sequence should be completely independent, so it cannot matter which numbers we use (and in which order). But other than the quote each nameable subsequence of random sequence should be random as well from Infinity and the mind (hardly solid cryptography), I can't find any reference. –  Dennis Dec 15 '12 at 17:24
    
Well, yes, each number in the sequence is independent, but it may not immediately be obvious to one with little knowledge of probability why discarding a number and trying with the next (independent) one is a valid strategy. That's what I meant. By the way, did you make a typo with X < (N / K) * K? I think you meant X < K. –  Thomas Dec 15 '12 at 17:39
    
I think you're right Thomas in that a typo was made. With (N / K) * K the K's would cancel each other out leaving you with N, which X is already pretty much guaranteed to be less than. –  neubert Dec 15 '12 at 19:10
    
@Thomas: I see what you mean. I'll expand on that when I have a little more time. The division in X < (N / K) * K is integer division. If we were interested in integers below 100, we can use all X such that X < (256 / 100) * 100 = 2 * 100 = 200. With X < K, there would be no need for the modulus. –  Dennis Dec 15 '12 at 20:34
show 3 more comments

The method given in this other answer is correct: to choose a uniformly random integer in range $[0,k-1]$ given a string of uniformly random integers in range $[0,n-1]$ with $1<k≤n$, get one integer $x$ from the string until $x<⌊n/k⌋⋅k$, then output $y=x\bmod k$. If we have $k≤n<2k$ (as in the question where $k=201$, $n=256$), that simplifies to: get one integer $x$ from the string until $x<k$, then output $x$.

However, that's not the best method, as asked: it consumes more from the input string than strictly needed. Otherwise said, when the input string is of limited length, odds that the algorithm fails are higher than needed. If there are $m$ values in the input string, odds of failure are $(1-⌊n/k⌋⋅k/n)^m$. For $k=201$, $n=256$, $m=3$, that's nearly $1\%$. It can get much worse: for $k=129$, $n=256$, $m=3$, odds of failure are over $12\%$.

We can modify the algorithm to improve on that; and also remove the $k≤n$ requirement.

  1. Set $r←0$, $s←1$.
  2. Get one new $x$ from the random string, set $r←r⋅n+x$ and $s←s⋅n$.
  3. If $r≥⌊s/k⌋⋅k$, set $r←r-⌊s/k⌋\cdot k$ and $s←s-⌊s/k⌋⋅k$, and proceed to step 2.
  4. Output $y=r\bmod k$, and stop.

Sketch of proof of correctness: by induction, before step 2 and before step 3, $r$ is a uniformly random integer with $0≤r<s$.

The integers $r$ and $s$ never exceed $(k-1)⋅n$, and thus the algorithm does not require arbitrary-precision arithmetic. It minimize odds of failure for a given input string of length $m$, to the bare minimum possible for exactly uniform output: $(n^m\bmod k)/n^m$; that is $≈0.0009\%$ (rather than $≈1\%$) for $k=201$, $n=256$, $m=3$; or $≈0.0007\%$ (rather than $≈12\%$) for $k=129$, $n=256$, $m=3$.

The algorithm works if the input string contains bits, or dice rolls with any number of faces, including variable (just change $n$ at step 2 according to the $x$ extracted from the input string).

If we need to generate more than one output $y$, there are several options:

  • The easiest is to start over; but that's clearly sub-optimal, especially when $n≫k$.
  • We can change "stop" at step 4 to: "set $r←⌊r/k⌋$, set $s←⌊s/k⌋$ (then, if desired, change $k$ for the next output); and proceed to step 3". The resulting algorithm still produce uniformly distributed output (the recurrence in the proof sketch holds), drastically reduce the consumption from the input string when $n≫k$, but I'm uncertain about optimality is not optimal (that's blatant for $k=2$, $n=3$).
  • If we know the number $j$ of desired outputs $y$ in advance, we can set $\hat k=k^j$, generate one $\hat y$ uniform in $[0,\hat k-1]$ using the optimal algorithm, then split $\hat y$ into $j$ outputs by expressing $\hat y$ as a $j$-digit number in base $k$. That's back to optimal, but is not a sequential algorithm, and requires arbitrary precision arithmetic when $j$ grows, with $O(j)$ extra memory.
  • We can generate any number of outputs using several batches of $j$ as in the previous tweak, but using the suboptimal sequential algorithm described above. That allows using bounded extra memory, and becomes close to optimality as $\hat k=k^j$ grows. However this is not a sequential algorithm.

I now lean towards belief that any optimum algorithm is bound to require $O(\log m)$ extra memory in some worst case. However it is possible to make a sequential algorithm using bounded extra memory, much less than above, and closer to optimality. I plan to detail such an algorithm (if someone else finds a reference, or otherwise has a suitable algorithm, please tell us!).

share|improve this answer
    
Excellent answer. –  Stephen Touset Dec 17 '12 at 22:18
    
@Stephen Touset: Thanks. Notice that the subject is not over: I realized that the algorithm is sub-optimal for multiple outputs. –  fgrieu Dec 18 '12 at 10:11
1  
i don't see how this is supposed to work. Let's say k = 140, n = 256 and the first x = 139. it'd loop at least once then per pastebin.com/zHxm9LD6. it doesn't seem like it should be looping at all, however, since 139 < 140... –  paynes_bay Aug 2 '13 at 20:24
1  
Never mind.. floor(s/k)*k == floor(256/140)*140 == 140 - not 1. –  paynes_bay Aug 2 '13 at 22:26
add comment

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.