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.