Newsgroups: sci.crypt Path: illuminati.io.com!uunet!gatech!howland.reston.ans.net!news.sprintlink. + net!news.dorsai.org!stevalln From: stevalln@news.dorsai.org (Steve Allen) Subject: Re: How random is "random data"? Message-ID:Sender: news@dorsai.org (Keeper of the News) Organization: The Dorsai Embassy - New York X-Newsreader: TIN [version 1.2 PL2] References: Date: Sat, 10 Dec 1994 19:08:08 GMT Lines: 37 rutger@euronet.nl writes >- How can I check how random "random data" is? > I could of course count frequencies, but an array > filled with the bytes 00..FF (ascending) would then > be considered random, as there isn't any preference. Consider throwing a die until you get a six. The odds of getting it on the first throw are 1/6. The odds of getting it on the second throw are 5/6*1/6. On the third throw, 5/6*5/6*1/6, and so on. Rolling a die and generating truly random numbers share 3 properties: 1) Only one number is generated at a time (this is important theoretically). 2) At any time t+s, the odds are the same as at time t. 3) At any time, the process is independent of all that has happened before. For any process that has these properties, the distribution of times between successive occurences of the same value is exponential. You can test the exponentiality of your random source's inter-arrival times by taking the logs of those times and forming an average. If that average matches well with the theoretical value, you've got good randomness. See Ueli Maurer's "A Universal Statistical Test For Random Bit Generators", Advances In Cryptology-- Crypto '90 (Springer-Verlag). This test does exactly that: for your n-bit generator (n=1..16), it takes the logs of inter-arrival times for all values 0..2^n-1, and compares the average to a perfect reference. He claims, as I understand it, that this test reveals *any* weakness in a RNG due to memory (violates rule 3 above). I recently posted a C version of this test, for PC-DOS, to the net. -Steve