Newsgroups: comp.security.misc,sci.crypt,alt.security
Path: news.io.com!news.tamu.edu!news.utdallas.edu!news.starnet.net!wupost!
+     howland.reston.ans.net!xlink.net!xlink100!snert!juliet.pond.sub.org!
+     ullisys.pond.sub.org!felix
From: felix@ullisys.pond.sub.org (Felix Schroeter)

Subject: Re: Random Number Generators
Message-ID: <1995Jun5.165619.175@ullisys.pond.sub.org>
Organization: K1, Germany
Date: Mon, 5 Jun 1995 16:56:19 GMT
References:  <1995May28.131614.
+           4713@ullisys.pond.sub.org> <3qfbkc$pnp@sol.ctr.columbia.edu>
X-Newsreader: TIN [version 1.2 PL2]
Followup-To: comp.security.misc,sci.crypt,alt.security
Lines: 81
Xref: news.io.com comp.security.misc:17563 sci.crypt:38298 alt.security:25411

Hello!

Seth Robertson (seth@soscorp.com) wrote:
: [...]
: >secret information: seed (64 bit), key (56 bit)
: >Generation of a random number:
: >seed = des_encrypt (seed, key);
: >return seed%100000000; /* this returns a number from 0 to 99 999 999 */

: Your last line is a *serious* flaw--since you used mod, you no longer
: have uniform random numbers.

In a strict sense, you are right. The numbers 0 to (2^64-1)%100000000
have probability (2^64 div 100000000+1)/(2^64), the numbers
from (2^64)%100000000 to 99999999 "only" probability
(2^64 div 100000000)/(2^64).

Let's start bc...

(< marks input, > marks output)

< scale=0
< a=2^64
< a
> 18446744073709551616
< b=a/100000000
< c=a%100000000
< scale=100
< (b+1)/a
> .00000001000000000004903216721530156974040437489748001098632812500000\
> 00000000000000000000000000000000
< b/a
> .00000000999999999999482205859102634804003173485398292541503906250000\
> 00000000000000000000000000000000
< c
> 9551616

So, the numbers from 0 to 9551615 have probability 0.00000001000000000005
(approx), those from 9551616 to 99999999 "only" 0.0000000099999999999948.
The difference of these probabilities is therefore 0.0000000000000000000552.
This is a relative error of 0.00000000000552, compared to the probability
of an ideal RNG (i.e. 1/100000000). So I think, your statement is of theortical
importance only.

: By way of example, let us say that des_encrypt produces numbers
: between 0 and 2^27 (it does not matter what exact range it produces as
: long as it is not a multiple of 100 million).

It doesn't matter for theory's sake, but for practical sake, because
the relative error of the probabilities is the smaller, the bigger the
range of "raw" numbers produced (e.g. by des_encrypt) is...

: [...]

: There are two solutions to this.  The first is if the number is 100
: million or more, you loop back until you get a number less than 100
: million.

Or loop only if the number is greater or equal
((2^64 div 100000000)/100000000). Then the range produced after leaving
the loop is just a multiple of those 100000000 big. And you have a rather
low chance of having to loop anyway :-)

:           The other is to use division to normalize the numbers.
: Something like: ((double)seed) / ((double)(1<<27)) * 100000000.0
: should work if I didn't make a stupid mistake.  I prefer the former
: method since on the average it is faster and you will never get into
: trouble because of precision limitation on various machines.

Hmmm. Your former method is rather slow, because the probability that
des_encrypt yields a number <100000000 is 100000000/(2^64), which is
(bc)

< scale=100
< 100000000/(2^64)
> .00000000000542101086242752217003726400434970855712890625000000000000\
> 00000000000000000000000000000000

: [... other (P)RNG suggestions ...]

Regards, Felix.