A better random generator :-)?

If the randomness really matters, then however you implement it you will probably have some kind of systematic error that might cause problems.

Implement it in several completely different ways and then XOR them together. The final result will probably be very good.

John

Hi !

Agreed with "systematic error that might cause problems ...." XOR between them (i.e. different ways of randomness) is not a guarantee of success. We are far from an analog based solution as Larkin's idea.

BR, Habib.

ote:

I would certainly include analog solutions as part of that mix.

I first came across this issue when using a digital random noise generator chip for acoustic work a long time ago. It was possible to hear the repeat cycle of the pseudo-random noise even though it looked perfect on a spectr um analyzer. Taking two such chips and XORing their outputs together gave a very good result. (They had on-chip clock oscillators with slightly diff erent frequencies.) The suggestion to do it this way came I think from my colleague BCJ Moore.

John

On Saturday, 20 December 2014 20:44:59 UTC, Habib Bouaziz-Viallet wrote: I've done it again - now reformatted!

I would certainly include analog solutions as part of that mix.

Of course, analog methods can have bias just as digital ones are ultimately predictable.

I first came across this issue when using a digital random noise generator chip for acoustic work a long time ago. It was possible to hear the repeat cycle of the pseudo-random noise even though it looked perfect on a spectrum analyzer. Taking two such chips and XORing their outputs together gave a very good result. (They had on-chip clock oscillators with slightly different frequencies.) The suggestion to do it this way came I think from my colleague BCJ Moore.

John

It was my idea.

You could start with a zener diode, amplify its noise, and run that through a comparator. That's physically random but has bias and some structure.

Now make a long pseudo-random shift register. That is fully random, bias-free, and has no structure, except for repeating every, say,

Now, internal to the shift register, XOR in the zener noise, preferaby without first syncing to the shift register clock. That causes the PN register to randomly jump states and breaks the periodicity.

Build a dozen of those and XOR them, just in case one breaks.

When people want to generate random numbers on a pure digital chip, one trick is to build a lot of asynchronous ring oscillators, sample them at the system clock frequency, and scramble the results. There's a lot of literature on that. I've seen hundreds of oscillators mentioned.

Mixing several random sources avoid many issues ; Ok if you're sure that one random source decorrelated of the others on long term. Building a truely random source (not a pseudo one base on LFSR on thing like that) is really really a business.

My opinion is that no human on the surface of the earth can ever produce a truely randomness source on long term.

Habib.

Johnson noise, shot noise, zener noise, radioactive decay, Brownian motion, are all physically random.

snip

A really good random generator is one with really bad, old points, that only starts about once every seventh attempt. They all have capacitive ignition now. ;-)

Actually, that spark 'signature' could likely be found to be different each time, if analysed closely. Spark gaps *should be* a great way the get a random number, if harnessed correctly. The only problem then is the EMI such events produce.

I would take 16 iterations (or 32 or 64 or...) of his idea, and make each bit random, making the word more likely random. (very natural).

"Do you have hair piece?" --Cheech Marin

Or, one could take a pseudo-random sample from a continually changing and growing database of say iris scans, and then take a random position in that file (those files)to make the "RandCoin" word bit portion of the final result. Each sample only creates one bit position of the final byte word. Many samples just to make a single byte further insures no repetition.

The odds of a repetition are way out there, right next to astronomical.

Ok John, your method is to periodically inject a "random" seed in your LFSR to break the periodicity. Nevertheless it did not transform an LFSR (even with a period = 2^32 - 1) to a true random generator. It's just a artifice to make hard to predict the sequences of the LFSR.

You're right, white noise (like the thermal noise) is a natural random source, but components will bias or mask initial noise information. That's why i doubt a real random source really exists.

Best Regards, Habib.

radioactive decay, I've seen someone modify a webcam to look at an americium source from a smoke detector. When and where you see a bright pixel event should be truly random

-Lasse

Ok John, your method is to periodically inject a "random" seed in your LFSR to break the periodicity. Nevertheless it did not transform an LFSR (even with a period = 2^32 - 1) to a true random generator. It's just a artifice to make hard to predict the sequences of the LFSR.

You're right, white noise (like the thermal noise) is a natural random source, but components will bias or mask initial noise information. That's why i doubt a real random source really exists.

Best Regards, Habib.

If you build a 128 stage LFSR with maximal length feedback and belt it with

Andy

If you want to generate analog or digital noise for testing, LFSRs, once stirred a few cycles, are fine. Our customers don't care if the analog noise that we generate repeats every few years. For cryptography, people seem to have objections to using LFSRs.

Even as an Analog Designer, I still often rely on 'simple' digital solutions: Store a HUGE quantity of random data, any pdf and spectrum you want. then play out through a decent DAC, and be done with it. After all, memory is cheap.

Else for CHEAP, I used to use 9+ Vdc through 1MEG to reverse bias a 2N3904 base emitter junction. Produced 'decent' noise at over 1 Vpp.

Andy, I had some experience on LFSR implementation with a FPGA, In 2000/2001 during my studies at CNAM in France, i designed a PCI card which produced random numbers in the space [0..2^32 - 1]. This card replace the functions srand(), rand() of the glibc, (srand() inject the seed and rand() returns a random number as an integer). I read many thesis and papers from IEEE on that subject and finally i wrote an LFSR (the one shown in Seminumerical ... D. Knuth) the algorithm itself is very easy to implement in verilog. The math behind the theory of Linear Congruential generators was and remains hard to master for me, but i know very well that implementing your own LFSR will not guarantee any succes on Die-Hard Tests. Many scientific applications need to replay some pseudo-random sequences but i know that other applications need to rely on a real random generator (uniform statistical distribution and not biased).

Larking idea on mixing random analog source with digital means may produce decent generators, in that way it will be funny to build the random distribution after a a week of free running.

Habib.

Yes, LFSRs make bad PRNGs. Do not use them for generating "random" numbers when you care about the quality of the numbers.

They fail particularly badly in the forward & reverse secrecy sense - if you know (or can guess) the output or state at any time you can calculate all previous and future states and outputs. This is obviously bad if you are trying to keep secrets. Also, the internal structure of the LFSR can be discovered without too much difficulty (see Berlekamp Massey algorithm).

Read NIST Special Publication 800-90A, -90B, -90C to see some better ways of doing it. (Better = more reliable numbers, not easier or faster to generate.)

The German BSI agency also has guidelines that are better than the NIST ones, in the sense that they explain and justify what they are doing.

Regards, Allan

BTW, if reading NIST Special Publication 800-90A, please ignore any references to Dual_EC_DRBG. That particular method contains a backdoor.

Regards, Allan

Are you trying for a cryptographically secure true random number generator?